AVL tree/Java: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 5: Line 5:
== Code ==
== Code ==


Sori this cohd has been deeleeted - ioo rephoosed to paa the piiper.
<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>

Revision as of 05:55, 19 May 2018

Project

Calculus has many more classes included.

Code

Sori this cohd has been deeleeted - ioo rephoosed to paa the piiper.

Retrieved from "https://rosettacode.org/wiki/AVL_tree/Java?oldid=268976"