AVL tree/Java

Project

Calculus has many more classes included.

Code

<lang java>import java.util.Iterator; import java.util.Comparator; import java.io.*;

@SuppressWarnings("unchecked")

    public enum State
    {
        Header,
        LeftHigh,
        Balanced,
        RightHigh
    }

   public class Node
   {
       public Node Left;
       public Node Right;
       public Node Parent;
       public State Balance;

       public Node()
       {
           Left = this;
           Right = this;
           Parent = null;
           Balance = State.Header;
       }

       public Node(Node p)
       {
           Left = null;
           Right = null;
           Parent = p;
           Balance = State.Balanced;
       }
       
       public Boolean isHeader ()
       { return Balance == State.Header;  }
   }

public class Utility {

       static int depth(Node root)
       {
           if (root != null)
           {
               int Left = root.Left != null ? depth(root.Left) : 0;
               int Right = root.Right != null ? depth(root.Right) : 0;
               return Left < Right ? Right + 1 : Left + 1;
           }
           else
               return 0;
       }

       static void swapNodes(Node A, Node B)
       {
           if (B == A.Left)
           {
               if (B.Left != null) B.Left.Parent = A;
               if (B.Right != null) B.Right.Parent = A;

               if (A.Right != null) A.Right.Parent = B;

               if (!A.Parent.isHeader())
               {
                   if (A.Parent.Left == A)
                       A.Parent.Left = B;
                   else
                       A.Parent.Right = B;
               }
               else A.Parent.Parent = B;

               B.Parent = A.Parent;
               A.Parent = B;

               A.Left = B.Left;
               B.Left = A;

               Node Temp = A.Right;
               A.Right = B.Right;
               B.Right = Temp;
           }
           else if (B == A.Right)
           {
               if (B.Right != null) B.Right.Parent = A;
               if (B.Left != null) B.Left.Parent = A;

               if (A.Left != null) A.Left.Parent = B;

               if (!A.Parent.isHeader())
               {
                   if (A.Parent.Left == A)
                       A.Parent.Left = B;
                   else
                       A.Parent.Right = B;
               }
               else A.Parent.Parent = B;

               B.Parent = A.Parent;
               A.Parent = B;

               A.Right = B.Right;
               B.Right = A;

               Node Temp=A.Left;
               A.Left = B.Left;
               B.Left = Temp;
           }
           else if (A == B.Left)
           {
               if (A.Left != null) A.Left.Parent = B;
               if (A.Right != null) A.Right.Parent = B;

               if (B.Right != null) B.Right.Parent = A;

               if (!B.Parent.isHeader())
               {
                   if (B.Parent.Left == B)
                       B.Parent.Left = A;
                   else
                       B.Parent.Right = A;
               }
               else B.Parent.Parent = A;

               A.Parent = B.Parent;
               B.Parent = A;

               B.Left = A.Left;
               A.Left = B;

               Node Temp = A.Right;
               A.Right = B.Right;
               B.Right = Temp;
           }
           else if (A == B.Right)
           {
               if (A.Right != null) A.Right.Parent = B;
               if (A.Left != null) A.Left.Parent = B;

               if (B.Left != null) B.Left.Parent = A;

               if (!B.Parent.isHeader())
               {
                   if (B.Parent.Left == B)
                       B.Parent.Left = A;
                   else
                       B.Parent.Right = A;
               }
               else B.Parent.Parent = A;

               A.Parent = B.Parent;
               B.Parent = A;

               B.Right = A.Right;
               A.Right = B;

               Node Temp = A.Left;
               A.Left = B.Left;
               B.Left = Temp;
           }
           else
           {
               if (A.Parent == B.Parent)
               {
                   Node Temp = A.Parent.Left;
                   A.Parent.Left = A.Parent.Right;
                   A.Parent.Right = Temp;
               }
               else
               {
                   if (!A.Parent.isHeader())
                   {
                       if (A.Parent.Left == A)
                           A.Parent.Left = B;
                       else
                           A.Parent.Right = B;
                   }
                   else A.Parent.Parent = B;

                   if (!B.Parent.isHeader())
                   {
                       if (B.Parent.Left == B)
                           B.Parent.Left = A;
                       else
                           B.Parent.Right = A;
                   }
                   else B.Parent.Parent = A;
               }

               if (B.Left != null) B.Left.Parent = A;
               if (B.Right != null) B.Right.Parent = A;

               if (A.Left != null) A.Left.Parent = B;
               if (A.Right != null) A.Right.Parent = B;

               Node Temp1 = A.Left;
               A.Left = B.Left;
               B.Left = Temp1;
               
               Node Temp2 = A.Right;
               A.Right = B.Right;
               B.Right = Temp2;

               Node Temp3 = A.Parent;
               A.Parent = B.Parent;
               B.Parent = Temp3;
           }

           State Balance = A.Balance; A.Balance = B.Balance; B.Balance = Balance;
       }

       static Node rotateLeft(Node root)
       {
           Node Parent = root.Parent;
           Node x = root.Right;

           root.Parent = x;
           x.Parent = Parent;
           if (x.Left != null) x.Left.Parent = root;

           root.Right = x.Left;
           x.Left = root;
           return x;
       }

       static Node rotateRight(Node root)
       {
           Node Parent = root.Parent;
           Node x = root.Left;

           root.Parent = x;
           x.Parent = Parent;
           if (x.Right != null) x.Right.Parent = root;

           root.Left = x.Right;
           x.Right = root;
           return x;
       }
       
       
       static Node balanceLeft(Node root)
       {
           Node left = root.Left;

           switch (left.Balance)
           {
               case LeftHigh:
                   root.Balance = State.Balanced;
                   left.Balance = State.Balanced;
                   root = rotateRight(root);
                   break;

               case RightHigh:
                   {
                       Node subRight = left.Right;
                       switch (subRight.Balance)
                       {
                           case Balanced:
                               root.Balance = State.Balanced;
                               left.Balance = State.Balanced;
                               break;

                           case RightHigh:
                               root.Balance = State.Balanced;
                               left.Balance = State.LeftHigh;
                               break;

                           case LeftHigh:
                               root.Balance = State.RightHigh;
                               left.Balance = State.Balanced;
                               break;
                       }
                       subRight.Balance = State.Balanced;
                       left = rotateLeft(left);
                       root.Left = left;
                       root = rotateRight(root);
                   }
                   break;

               case Balanced:
                   root.Balance = State.LeftHigh;
                   left.Balance = State.RightHigh;
                   root = rotateRight(root);
                   break;
           }
           
           return root;
       }

       static Node balanceRight(Node root)
       {
           Node right = root.Right;

           switch (right.Balance)
           {
               case RightHigh:
                   root.Balance = State.Balanced;
                   right.Balance = State.Balanced;
                   root = rotateLeft(root);
                   break;

               case LeftHigh:
                   {
                       Node subLeft = right.Left; // Left Subtree of Right
                       switch (subLeft.Balance)
                       {
                           case Balanced:
                               root.Balance = State.Balanced;
                               right.Balance = State.Balanced;
                               break;

                           case LeftHigh:
                               root.Balance = State.Balanced;
                               right.Balance = State.RightHigh;
                               break;

                           case RightHigh:
                               root.Balance = State.LeftHigh;
                               right.Balance = State.Balanced;
                               break;
                       }
                       subLeft.Balance = State.Balanced;
                       right = rotateRight(right);
                       root.Right = right;
                       root = rotateLeft(root);
                   }
                   break;

               case Balanced:
                   root.Balance = State.RightHigh;
                   right.Balance = State.LeftHigh;
                   root = rotateLeft(root);
                   break;
           }
           
           return root;
       }

       static void balanceTree(Node root, Direction From)
       {
           Boolean Taller = true;

           while (Taller)
           {
               Node Parent = root.Parent;
               Direction NextFrom = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;

               if (From == Direction.FromLeft)
               {
                   switch (root.Balance)
                   {
                       case LeftHigh:
                           if (Parent.isHeader())
                               Parent.Parent = balanceLeft(Parent.Parent);
                           else if (Parent.Left == root)
                               Parent.Left = balanceLeft(Parent.Left);
                           else
                               Parent.Right = balanceLeft(Parent.Right);
                           Taller = false;
                           break;

                       case Balanced:
                           root.Balance = State.LeftHigh;
                           Taller = true;
                           break;

                       case RightHigh:
                           root.Balance = State.Balanced;
                           Taller = false;
                           break;
                   }
               }
               else
               {
                   switch (root.Balance)
                   {
                       case LeftHigh:
                           root.Balance = State.Balanced;
                           Taller = false;
                           break;

                       case Balanced:
                           root.Balance = State.RightHigh;
                           Taller = true;
                           break;

                       case RightHigh:
                           if (Parent.isHeader())
                               Parent.Parent = balanceRight(Parent.Parent);
                           else if (Parent.Left == root)
                               Parent.Left = balanceRight(Parent.Left);
                           else
                               Parent.Right = balanceRight(Parent.Right);
                           Taller = false;
                           break;
                   }
               }

               if (Taller) // skip up a level
               {
                   if (Parent.isHeader())
                       Taller = false;
                   else
                   {
                       root = Parent;
                       From = NextFrom;
                   }
               }
           }
       }    
       
       static void balanceTreeRemove(Node root, Direction From)
       {
           if (root.isHeader()) return;

           Boolean Shorter = true;

           while (Shorter)
           {
               Node Parent = root.Parent;
               Direction NextFrom = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;

               if (From == Direction.FromLeft)
               {
                   switch (root.Balance)
                   {
                       case LeftHigh:
                           root.Balance = State.Balanced;
                           Shorter = true;
                           break;

                       case Balanced:
                           root.Balance = State.RightHigh;
                           Shorter = false;
                           break;

                       case RightHigh:
                           if (root.Right.Balance == State.Balanced)
                               Shorter = false;
                           else
                               Shorter = true;
                           if (Parent.isHeader())
                               Parent.Parent = balanceRight(Parent.Parent);
                           else if (Parent.Left == root)
                               Parent.Left = balanceRight(Parent.Left);
                           else
                               Parent.Right = balanceRight(Parent.Right);
                           break;
                   }
               }
               else
               {
                   switch (root.Balance)
                   {
                       case RightHigh:
                           root.Balance = State.Balanced;
                           Shorter = true;
                           break;

                       case Balanced:
                           root.Balance = State.LeftHigh;
                           Shorter = false;
                           break;

                       case LeftHigh:
                           if (root.Left.Balance == State.Balanced)
                               Shorter = false;
                           else
                               Shorter = true;
                           if (Parent.isHeader())
                               Parent.Parent = balanceLeft(Parent.Parent);
                           else if (Parent.Left == root)
                               Parent.Left = balanceLeft(Parent.Left);
                           else
                               Parent.Right = balanceLeft(Parent.Right);
                           break;
                   }
               }

               if (Shorter)
               {
                   if (Parent.isHeader())
                       Shorter = false;
                   else
                   {
                       From = NextFrom;
                       root = Parent;
                   }
               }
           }
       }
       
       static Node previousNode(Node Node)
       {
           if (Node.isHeader()) { return Node.Right; }

           if (Node.Left != null)
           {
               Node = Node.Left;
               while (Node.Right != null) Node = Node.Right;
           }
           else
           {
               Node y = Node.Parent;
               if (y.isHeader()) return y;
               while (Node == y.Left) { Node = y; y = y.Parent; }
               Node = y;
           }
           return Node;
       }

       static Node nextNode(Node Node)
       {
           if (Node.isHeader()) return Node.Left;

           if (Node.Right != null)
           {
               Node = Node.Right;
               while (Node.Left != null) Node = Node.Left;
           }
           else
           {
               Node y = Node.Parent;
               if (y.isHeader()) return y;
               while (Node == y.Right) { Node = y; y = y.Parent; }
               Node = y;
           }
           return Node;
       }
       

}

   public class SetNode<T> extends Node
   {
       public T Data;

       public SetNode(T dataType, Node Parent)
       {
           super(Parent);
           Data = dataType;
       }
   }

   public interface Cloneable
   {
       T clone();
   }

   public interface Cloner<T>
   {
       T clone(T t);
   }

   public class DefaultCloner implements Cloner, Serializable
   {
       public T clone(T t)
       {
           try
           {
               Cloneable copier = (Cloneable)t;
               return copier.clone();
           }
           catch(Exception e)
           {
               return t;
           }
       }
   }

   public class DefaultComparator implements Comparator, Serializable
   {
       public int compare(T t1, T t2)
       {
           Comparable key = (Comparable)t1;
           return key.compareTo(t2);
       }

       public boolean equals(T t1, T t2)
       {
           Comparable key = (Comparable)t1;
           return key.compareTo(t2) != 0;
       }

   }

   public enum Direction
   {
           FromLeft,
           FromRight
   }

   public class SetEntry implements Iterator
   {
       public SetEntry(Node n) { _Node = n; }

       public T value()
       {
               return ((SetNode)_Node).Data;
       }

       public Boolean isHeader() { return _Node.isHeader(); }

       public boolean equals(SetEntry other)
       {
           return _Node == other._Node;
       }
       
       public String toString()
       {
           return value().toString();
       }

        public boolean hasNext()
        {
   
           Node _Next = Utility.nextNode(_Node);
           return _Next.isHeader() ? false : true;
        }

       public T next()
       {
           _Node = Utility.nextNode(_Node);
           return ((SetNode)_Node).Data;
       }

       public T previous()
       {
           _Node = Utility.previousNode(_Node);
           return ((SetNode)_Node).Data;
       }

       public Boolean moveNext()
       {
           _Node = Utility.nextNode(_Node);
           return _Node.isHeader() ? false : true;            
       }

       public Boolean movePrevious()
       {
           _Node = Utility.previousNode(_Node);
           return _Node.isHeader() ? false : true;            
       }

       public Node _Node;
   }

   public enum SetOperation
   {
       Union,
       Intersection,
       SymmetricDifference,
       Difference
   }

   public class EntryAlreadyExistsException extends Exception
   {
       public EntryAlreadyExistsException()
       {
           super("An entry already exists in the collection.");            
       }
   }

   public class EntryNotFoundException extends Exception
   {
       public EntryNotFoundException()
       {
           super("An entry could not be found.");            
       }
   }

   public class InvalidSetOperationException extends Exception
   {
       public InvalidSetOperationException()
       {
           super("An invalid set operation was specified.");            
       }
   }

   public class Set<T> implements Iterable<T>,
                                  Cloneable<Set<T>>,
                                  Serializable
   {
       public Node Header;
       public long Nodes;
       Comparator<T> Compare;
       Cloner<T> Clone;
       
       public Set()
       {
           Nodes = 0;
           Header = new Node();
           Compare = new DefaultComparator<T>();
           Clone = new DefaultCloner<T>();
       }

       public Set(Iterable<T> Iterable)
       {
           Nodes = 0;
           Header = new Node();
           Compare = new DefaultComparator<T>();
           Clone = new DefaultCloner<T>();
           
           for(T t : Iterable)
           {
               try
               {
                   add(Clone.clone(t));
               }
               catch (EntryAlreadyExistsException e) {}
           }
       }

       public Set(Comparator<T> ComparatorIn)
       {
           Nodes = 0;
           Header = new Node();
           Compare = ComparatorIn;
           Clone = new DefaultCloner<T>();
       }

       public Set(Iterable<T> Iterable,
                  Comparator<T> ComparatorIn)
       {
           Nodes = 0;
           Header = new Node();
           Compare = ComparatorIn;
           Clone = new DefaultCloner<T>();
           
           for(T t : Iterable)
           {
               try
               {
                   add(Clone.clone(t));
               }
               catch (EntryAlreadyExistsException e) {}
           }
       }

       public Set(T... params)
       {
           Nodes = 0;
           Header = new Node();
           Compare = new DefaultComparator<T>();
           Clone = new DefaultCloner<T>();
           
           for(T t : params)
           {
               try
               {
                   add(Clone.clone(t));
               }
               catch (EntryAlreadyExistsException e) {}
           }
       }
       
       public Set(Set<T> A,
                  Set<T> B,
                  SetOperation operation) throws EntryAlreadyExistsException, InvalidSetOperationException
       {
           synchronized(A)
           {
           synchronized(B)
           {
           
           Compare = A.Compare;
           Nodes = 0;
           Header = new Node();
           Clone = new DefaultCloner<T>();

           SetEntry<T> first1 = A.begin();
           SetEntry<T> last1 = A.end();
           SetEntry<T> first2 = B.begin();
           SetEntry<T> last2 = B.end();

           switch (operation)
           {
               case Union:
                   while (!first1.equals(last1) && !first2.equals(last2))
                   {
                       int order = Compare.compare(first1.value(),first2.value());

                       if (order < 0)
                       {
                           add(Clone.clone(first1.value()));
                           first1.moveNext();
                       }

                       else if (order > 0)
                       {
                           add(Clone.clone(first2.value()));
                           first2.moveNext();
                       }

                       else
                       {
                           add(first1.value());
                           first1.moveNext();
                           first2.moveNext();
                       }
                   }
                   while (!first1.equals(last1))
                   {
                       add(Clone.clone(first1.value()));
                       first1.moveNext();
                   }
                   while (!first2.equals(last2))
                   {
                       add(Clone.clone(first2.value()));
                       first2.moveNext();
                   }
                   return;

               case Intersection:
                   while (!first1.equals(last1) && !first2.equals(last2))
                   {
                       int order = Compare.compare(first1.value(),first2.value());

                       if (order < 0)
                           first1.moveNext();

                       else if (order > 0)
                           first2.moveNext();

                       else
                       {
                           add(Clone.clone(first1.value()));
                           first1.moveNext();
                           first2.moveNext();
                       }
                   }
                   return;

               case SymmetricDifference:
                   while (!first1.equals(last1) && !first2.equals(last2))
                   {
                       int order = Compare.compare(first1.value(),first2.value());

                       if (order < 0)
                       {
                           add(Clone.clone(first1.value()));
                           first1.moveNext();
                       }

                       else if (order > 0)
                       {
                           add(Clone.clone(first2.value()));
                           first2.moveNext();
                       }

                       else
                       { first1.moveNext(); first2.moveNext(); }
                   }

                   while (!first1.equals(last1))
                   {
                       add(Clone.clone(first1.value()));
                       first1.moveNext();
                   }

                   while (!first2.equals(last2))
                   {
                       add(Clone.clone(first2.value()));
                       first2.moveNext();
                   }
                   return;

               case Difference:
                   while (!first1.equals(last1) && !first2.equals(last2))
                   {
                       int order = Compare.compare(first1.value(),first2.value());

                       if (order < 0)
                       {
                           add(Clone.clone(first1.value()));
                           first1.moveNext();
                       }

                       else if (order > 0)
                       {
                           add(Clone.clone(first1.value()));
                           first1.moveNext();
                           first2.moveNext();
                       }

                       else
                       { first1.moveNext(); first2.moveNext(); }
                   }

                   while (!first1.equals(last1))
                   {
                       add(Clone.clone(first1.value()));
                       first1.moveNext();
                   }
                   return;
           }

           throw new InvalidSetOperationException();
           }
           }
       }

       public Set(Set<T> SetToCopy)
       {
           synchronized(SetToCopy)
           {
               Nodes = 0;
               Header = new Node();
               Compare = SetToCopy.Compare;
               Clone = SetToCopy.Clone;
           
               for(T t : SetToCopy)
               {
                   try
                   {
                       add(Clone.clone(t));
                   }
                   catch (EntryAlreadyExistsException e) {}
               }
           }
       }
       
       private void readObject(java.io.ObjectInputStream stream) throws IOException, ClassNotFoundException
       {
           Header = new Node();            
           Nodes = 0;
           
           int Count = stream.readInt();
           Compare = (Comparator<T>)stream.readObject();
           Clone = (Cloner<T>)stream.readObject();
           for (int i=0; i<Count; i++)
              try
              {
                  add((T)stream.readObject());
              }
              catch(EntryAlreadyExistsException e) {}
       }

       private void writeObject(java.io.ObjectOutputStream stream)  throws IOException
       {
           synchronized (this)
           {
               stream.writeInt((int)Nodes);
               stream.writeObject(Compare);
               stream.writeObject(Clone);
               for (T t : this) stream.writeObject(t);
           }
       }

       private void readObjectNoData() throws ObjectStreamException
       {
           Header = new Node();            
           Nodes = 0;
       }
       
       public long length() {return Nodes;}
       
       
       public Iterator<T> iterator()
       {
           return new SetEntry<T>(Header);
       }

       public SetEntry<T> after(T key, boolean equals)
       {
           synchronized (this)
           {
               return new SetEntry<T>(equals ? afterEquals(key) : after(key));
           }
       }
              
       public SetEntry<T> before(T key, boolean equals)
       {
           synchronized (this)
           {
               return new SetEntry<T>(equals ? beforeEquals(key) : before(key));
           }
       }
       
       public Comparator<T> getComparator() { return Compare; }
       
       public Set<T> clone()
       {
           synchronized(this)
           {
               Set<T> Out = new Set<T>(Compare);
               Out.Clone = Clone;
           
               for (T t : this)
               {
                   try
                   {
                       Out.add(Clone.clone(t));
                   }
                   catch (EntryAlreadyExistsException e) {}
               }
           
               return Out;
           }
       }
       
       public long depth()
       {
           synchronized (this)
           {
               return Utility.depth(Header.Parent);
           }
       }
       
       public Cloner<T> getCloner() {synchronized (this) {return Clone;} }
       
       public void setCloner(Cloner<T> C) {synchronized (this) {Clone = C;}}

       public SetEntry<T> insert(T data)  throws EntryAlreadyExistsException
       {
           return new SetEntry<T>(add(data));
       }
       
       public SetNode<T> add(T data) throws EntryAlreadyExistsException
       {
           synchronized(this)
           {
               if (Header.Parent == null)
               {
                   SetNode<T> newNode = new SetNode<T>(data, Header);
                   Header.Parent = newNode;
                   Nodes++;
                   Header.Left = Header.Parent;
                   Header.Right = Header.Parent;
                   return newNode;
               }
               else
               {
                   SetNode<T> newRoot = (SetNode<T>)Header.Parent;
               
                   for (; ; )
                   {
                       int compare = Compare.compare(data,newRoot.Data);

                       if (compare == 0) // Item Exists
                           throw new EntryAlreadyExistsException();

                       else if (compare < 0)
                       {
                           if (newRoot.Left != null)
                               newRoot = (SetNode<T>)newRoot.Left;
                           else
                           {
                               SetNode<T> NewNode = new SetNode<T>(data, newRoot);
                               Nodes++;
                               newRoot.Left = NewNode;
                               if (Header.Left == newRoot) Header.Left = NewNode;
                               Utility.balanceTree(newRoot, Direction.FromLeft);
                               return NewNode;
                           }
                       }

                       else
                       {
                           if (newRoot.Right != null)
                               newRoot = (SetNode<T>)newRoot.Right;
                           else
                           {
                               SetNode<T> NewNode = new SetNode<T>(data, newRoot);
                               Nodes++;
                               newRoot.Right = NewNode;
                               if (Header.Right == newRoot) Header.Right = NewNode;
                               Utility.balanceTree(newRoot, Direction.FromRight);
                               return NewNode;
                           }
                       }
                   }
               }
           }
       }

       public long remove()
       {
           synchronized (this)
           {
               long count = Nodes;
               Header.Parent = null;
               Header.Left = Header;
               Header.Right = Header;
               Nodes = 0;
               return count;
           }

       }

       public void remove(T data) throws EntryNotFoundException
       {
           synchronized (this)
           {
               SetNode<T> root = (SetNode<T>)Header.Parent;

               for (; ; )
               {
                   if (root == null)
                       throw new EntryNotFoundException();

                   int compare = Compare.compare(data,root.Data);

                   if (compare < 0)
                       root = (SetNode<T>)root.Left;

                   else if (compare > 0)
                       root = (SetNode<T>)root.Right;

                   else // Item is found
                   {
                       if (root.Left != null && root.Right != null)
                       {
                           Node replace = root.Left;
                           while (replace.Right != null) replace = replace.Right;
                           Utility.swapNodes(root, replace);
                       }

                       Node Parent = root.Parent;

                       Direction From = (Parent.Left == root) ? Direction.FromLeft : Direction.FromRight;

                       if (Header.Left == root)
                       {
                           Node n = Utility.nextNode(root);

                           if (n.isHeader())
                           { Header.Left = Header; Header.Right = Header; }
                           else
                               Header.Left = n;
                       }
                       else if (Header.Right == root)
                       {
                           Node p = Utility.previousNode(root);

                           if (p.isHeader())
                           { Header.Left = Header; Header.Right = Header; }
                           else
                               Header.Right = p;
                       }

                       if (root.Left == null)
                       {
                           if (Parent == Header)
                               Header.Parent = root.Right;
                           else if (Parent.Left == root)
                               Parent.Left = root.Right;
                           else
                               Parent.Right = root.Right;

                           if (root.Right != null) root.Right.Parent = Parent;
                       }
                       else
                       {
                           if (Parent == Header)
                               Header.Parent = root.Left;
                           else if (Parent.Left == root)
                               Parent.Left = root.Left;
                           else
                               Parent.Right = root.Left;

                           if (root.Left != null) root.Left.Parent = Parent;
                       }

                       Utility.balanceTreeRemove(Parent, From);

                       Nodes--;
                       break;
                   }
               }
           }
       }

       public boolean exists(T data)
       {
           synchronized (this)
           {
               if (Header.Parent == null)
                   return false;
               else
               {
                   Node search = Header.Parent;

                   do
                   {
                       int Result = Compare.compare(data,((SetNode<T>)search).Data);

                       if (Result < 0) search = search.Left;

                       else if (Result > 0) search = search.Right;

                       else break;

                   } while (search != null);

                   return search != null;
               }
           }
       }

       public T find(T data) throws EntryNotFoundException
       {
           synchronized (this)
           {
               if (Header.Parent == null)
                   throw new EntryNotFoundException();
               else
               {
                   Node search = Header.Parent;

                   do
                   {
                       int Result = Compare.compare(data,((SetNode<T>)search).Data);

                       if (Result < 0) search = search.Left;

                       else if (Result > 0) search = search.Right;

                       else break;

                   } while (search != null);

                   if (search != null) throw new EntryNotFoundException();
                   
                   return ((SetNode<T>)search).Data;
               }
           }
       }

       public SetEntry<T> locate(T data) throws EntryNotFoundException
       {
           synchronized (this)
           {
               if (Header.Parent == null)
                   throw new EntryNotFoundException();
               else
               {
                   Node search = Header.Parent;

                   do
                   {
                       int Result = Compare.compare(data,((SetNode<T>)search).Data);

                       if (Result < 0) search = search.Left;

                       else if (Result > 0) search = search.Right;

                       else break;

                   } while (search != null);

                   if (search != null) throw new EntryNotFoundException();
                   
                   return new SetEntry(search);
               }
           }
       }

       public SetEntry<T> begin() { return new SetEntry<T>(Header.Left); }
       
       public SetEntry<T> end() { return new SetEntry<T>(Header); }

       public String toString()
       {
           synchronized(this)
           {
               String StringOut = "{";

               SetEntry<T> start = begin();
               SetEntry<T> end = end();
               SetEntry<T> last = end(); last.movePrevious();

               while (!start.equals(end))
               {
                   String NewStringOut = start.value().toString();
                   if (!start.equals(last)) NewStringOut = NewStringOut + ",";
                   StringOut = StringOut + NewStringOut;
                   start.moveNext();
               }

               StringOut = StringOut + "}";
               return StringOut;
           }
       }

       Node after(T data)
       {
           Node y = Header;
           Node x = Header.Parent;

           while (x != null)
               if (Compare.compare(data,((SetNode<T>)x).Data) < 0)
               { y = x; x = x.Left; }
               else
                   x = x.Right;

           return y;
       }

       Node afterEquals(T data)
       {
           Node y = Header;
           Node x = Header.Parent;

           while (x != null)
           {
               int c = Compare.compare(data,((SetNode<T>)x).Data);
               if (c == 0)
               { y = x; break; }
               else if (c < 0)
               { y = x; x = x.Left; }
               else
                   x = x.Right;
           }

           return y;
       }
       
      Node before(T data)
       {
           Node y = Header;
           Node x = Header.Parent;

           while (x != null)
               if (Compare.compare(data,((SetNode<T>)x).Data) <= 0)
                   x = x.Left;
               else
               { y = x; x = x.Right; }

           return y;
       }

       Node beforeEquals(T data)
       {
           Node y = Header;
           Node x = Header.Parent;

           while (x != null)
           {
               int c = Compare.compare(data,((SetNode<T>)x).Data);
               if (c == 0)
               { y = x; break; }
               else if (c < 0)
                   x = x.Left;
               else
               { y = x; x = x.Right; }
           }

           return y;
       }
       
       public boolean equals(Set<T> compare)
       {
           synchronized (this)
           {
               SetEntry<T> first1 = begin();
               SetEntry<T> last1 = end();
               SetEntry<T> first2 = compare.begin();
               SetEntry<T> last2 = compare.end();

               Boolean equals = true;

               while (!first1.equals(last1) && !first2.equals(last2))
               {
                   if (Compare.compare(first1.value(),first2.value()) == 0)
                   { first1.moveNext(); first2.moveNext(); }
                   else
                   { equals = false; break; }
               }

               if (equals)
               {
                   if (!first1.equals(last1)) equals = false;
                   if (!first2.equals(last2)) equals = false;
               }

               return equals;
           }
       }
       
       public boolean isSubset(Set<T> S)
       {
           synchronized (this)
           {
           synchronized (S)
           {
               SetEntry<T> first1 = begin();
               SetEntry<T> last1 = end();
               SetEntry<T> first2 = S.begin();
               SetEntry<T> last2 = S.end();

               boolean subset = true;

               while (!first1.equals(last1) && !first2.equals(last2))
               {
                   int order = Compare.compare(first1.value(), first2.value());
                   if (order < 0)
                   { subset = false; break; }
                   else if (order > 0)
                      first2.moveNext();
                   else
                   { first1.moveNext(); first2.moveNext(); }
               }

               if (subset)
                  if (!first1.equals(last1)) subset = false;

               return subset;
           }
           }
       }
   }

</lang>