package {
	
  public class AnderssonTree {
    
    public function AnderssonTree() {}
    
    public override function add( node:TreeNode ):void {
      _root = insert( _root, node );
      _size++;
    }
    
    public override function rem( node:TreeNode ):void {
      _root = remove( _root, node );
      _size--;
    }
    
    private function insert( root:TreeNode, node:TreeNode ):TreeNode {
      if ( !nodeValid(root) ) {
        root = node;
        root.level = 1;
      } else if ( root.compare( node ) == 0 ) {
        return root;
      } else {
        if ( root.compare( node ) < 0 ) {
          root.right = insert( root.right, node );
        } else {
          root.left = insert( root.left, node );
        }
        root = skew( root );
        root = split( root );
      }
      return root;
    }
    
    private function remove( root:TreeNode, node:TreeNode, iteration:uint = 0 ):TreeNode {
      if ( !nodeValid(root) || !nodeValid(node) ) {
        return root;
      }
      if ( root.compare( node ) == 0 ) {
        if ( nodeValid(root.left) && nodeValid(root.right) ) {
          var heir:TreeNode = root.left;
          while ( nodeValid(heir.right) ) {
            heir = heir.right;
          }
          root.copy( heir );
          root.left = remove( root.left, heir, iteration + 1 );
        } else {
          if ( nodeValid( root.left ) ) {
            root = root.left;
          } else {
            root = root.right;
          }
        }
      } else {
        if ( root.compare( node ) < 0 ) {
          root.right = remove( root.right, node, iteration + 1 );
        } else {
          root.left = remove( root.left, node, iteration + 1 );
        }
      }
      if  ( root && ( ( getLevel( root.left ) < root.level - 1 ) || ( getLevel( root.right ) < root.level - 1 ) ) ) {
        root.level--;
        if ( nodeValid( root.right ) && root.right.level > root.level ) {
          root.right.level = root.level;
        }
        root = skew( root );
        root = split( root );
      }      
      return root;
    }
    
    private function skew( root:TreeNode ):TreeNode {
      if ( nodeValid(root) ) {
        if ( nodeValid(root.left) && root.left.level == root.level ) {
          var save:TreeNode = root;
          root = root.left;
          save.left = root.right;
          root.right = save;
        }
        root.right = skew( root.right );
      }
      return root;
    }
    
    private function split( root:TreeNode ):TreeNode {
      if ( nodeValid(root) && nodeValid(root.right) && nodeValid(root.right.right) && root.right.right.level == root.level ) {
        var save:TreeNode = root;
        root = root.right;
        save.right = root.left;
        root.left = save;
        root.level += 1;
        root.right = split( root.right );
      }
      return root;
    }
    
    private function nodeValid( node:TreeNode ):Boolean {
      if ( node && node.level != 0 ) {
        return true;
      }
      return false;
    }
    
    private function getLevel( node:TreeNode ):uint {
      if ( !node ) {
        return 0;
      }
      return node.level;
    }
    
  }

}