AVL tree/Java: Difference between revisions
< AVL tree
Content added Content deleted
m (→Project) |
(→Code) |
||
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.