AVL tree/Managed C++: Difference between revisions
No edit summary |
(→Code) |
||
Line 162:
generic<typename T>
Cloner<T>^ Cloner<T>::Invisible::get() { return gcnew DefaultNoCloner<T>(); }
public ref struct OutOfKeyOrderException : public Exception
{
Line 168 ⟶ 169:
OutOfKeyOrderException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 179 ⟶ 180:
TreeInvalidParentException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 190 ⟶ 191:
TreeOutOfBalanceException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 201 ⟶ 202:
InvalidEmptyTreeException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 213 ⟶ 214:
InvalidEndItemException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 224 ⟶ 225:
EntryAlreadyExistsException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 235 ⟶ 236:
DifferentKeysException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 246 ⟶ 247:
AddSubTreeFailedException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 257 ⟶ 258:
IsEndItemException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 268 ⟶ 269:
EntryNotFoundException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 279 ⟶ 280:
InvalidSetOperationException() : Exception(message)
{
HelpLink = gcnew String("
Source = gcnew String("
}
};
Line 1,013 ⟶ 1,014:
Header = gcnew Node();
TComparer = System::Collections::Generic::Comparer<T>::Default;
TCloner =
THasher =
}
Line 1,022 ⟶ 1,023:
Header = gcnew Node();
TComparer = TCompare;
TCloner =
THasher =
}
Line 1,041 ⟶ 1,042:
Header = gcnew Node();
TComparer = System::Collections::Generic::Comparer<T>::Default;
TCloner =
THasher =
for each (T t in Collection) Add(TCloner->Clone(t));
Line 1,052 ⟶ 1,053:
Header = gcnew Node();
TComparer = System::Collections::Generic::Comparer<T>::Default;
TCloner =
THasher =
for each (T t in Collection) Add(TCloner->Clone(t));
Line 1,064 ⟶ 1,065:
Header = gcnew Node();
TComparer = TCompare;
TCloner =
THasher =
for each (T t in Collection) Add(TCloner->Clone(t));
Line 1,086 ⟶ 1,087:
Nodes=0;
System::Collections::Generic::IComparer<T>^ TCompare = (System::Collections::Generic::IComparer<T>^)si->GetValue("TComparer", System::Collections::Generic::IComparer<T>::typeid);
Header = gcnew Node();
Line 1,393 ⟶ 1,394:
virtual void GetObjectData(SerializationInfo^ si, StreamingContext sc)
{
si->SetType(
Type^ type = T::typeid;
Line 2,012 ⟶ 2,013:
{
System::Collections::Generic::IComparer<T>^ TComparer = R->TComparer;
SetEntry<T> first1 = A->Begin;
Line 2,244 ⟶ 2,245:
}
using namespace
int main(array<System::String ^> ^args)
|
Revision as of 21:36, 10 January 2017
Code
<lang cpp> // AVL in Managed C++
using namespace System; using namespace System::Collections; using namespace System::Collections::Generic; using namespace System::Threading; using namespace System::Runtime::Serialization;
namespace Calculus {
public enum class State {
Header, LeftHigh, Balanced, RightHigh
};
public enum class Direction { FromLeft, FromRight };
public ref struct Node {
Node^ Left; Node^ Right; Node^ Parent; State Balance;
Node() { Left = this; Right = this; Parent = nullptr; Balance = State::Header; }
Node(Node^ p) { Left = nullptr; Right = nullptr; Parent = p; Balance = State::Balanced; }
property Boolean IsHeader { Boolean get() { return Balance == State::Header; } }
};
generic <typename T> public delegate void TypeFound(Object^ O, T type);
generic <typename T> public delegate void TypeAdded(Object^ O, T type);
generic <typename T> public delegate void TypeRemoved(Object^ O, T type);
generic <typename T> public delegate void TypeUpdated(Object^ O, T before, T after);
generic<typename T> public interface struct IHasher {
int GetHashCode(T t);
};
generic<typename T> [Serializable] public ref class Hasher abstract : IHasher<T> {
public:
static property Hasher<T>^ Default { Hasher<T>^ get(); }
virtual int GetHashCode(T t) = 0;
};
generic<typename T> [Serializable] public ref class DefaultHasher : Hasher<T> {
public:
virtual int GetHashCode(T t) override { return t->GetHashCode(); }
};
generic<typename T> Hasher<T>^ Hasher<T>::Default::get() { return gcnew DefaultHasher<T>(); }
generic<typename T>
public interface struct ICloneable { T Clone(); };
generic<typename T> public interface class ICloner { T Clone(T t); };
generic<typename T> [Serializable]
public ref struct Cloner abstract : ICloner<T>
{
static property Cloner<T>^ Default { Cloner<T>^ get(); }
static property Cloner<T>^ Invisible { Cloner<T>^ get(); }
virtual T Clone(T t) = 0;
};
generic<typename T> [Serializable] public ref struct DefaultCloner1 : Cloner<T> {
virtual T Clone(T t) override { ICloneable<T>^ copier = (ICloneable<T>^)t; return copier->Clone(); }
};
generic<typename T> [Serializable] public ref struct DefaultCloner2 : Cloner<T> {
virtual T Clone(T t) override { ICloneable<T>^ copier = (ICloneable<T>^)t; return (T)copier->Clone(); }
};
generic<typename T> [Serializable] public ref struct DefaultNoCloner : Cloner<T> {
virtual T Clone(T t) override { return t; }
};
generic<typename T> Cloner<T>^ Cloner<T>::Default::get() {
Type^ TypeT = T::typeid; Type^ TypeIC1 = ICloneable<T>::typeid; Type^ TypeIC2 = ICloneable::typeid; if (TypeIC1->IsAssignableFrom(TypeT)) return gcnew DefaultCloner1<T>(); else if (TypeIC2->IsAssignableFrom(TypeT)) return gcnew DefaultCloner2<T>(); else return gcnew DefaultNoCloner<T>();
}
generic<typename T> Cloner<T>^ Cloner<T>::Invisible::get() { return gcnew DefaultNoCloner<T>(); }
public ref struct OutOfKeyOrderException : public Exception { static String^ message = gcnew String("A tree was found to be out of key order.");
OutOfKeyOrderException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct TreeInvalidParentException : public Exception { static String^ message = gcnew String("The validation routines detected that the parent structure of a tree is invalid.");
TreeInvalidParentException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct TreeOutOfBalanceException : public Exception { static String^ message = gcnew String("The validation routines detected that the tree is out of balance.");
TreeOutOfBalanceException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct InvalidEmptyTreeException : public Exception { static String^ message = gcnew String("The validation routines detected that an empty tree is invalid.");
InvalidEmptyTreeException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct InvalidEndItemException : public Exception { static String^ message = gcnew String("The validation routines detected that the end item of a tree is invalid.");
InvalidEndItemException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct EntryAlreadyExistsException : public Exception { static String^ message = gcnew String("An entry already exists in the collection.");
EntryAlreadyExistsException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct DifferentKeysException : public Exception { static String^ message = gcnew String("The specified items have different keys.");
DifferentKeysException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct AddSubTreeFailedException : public Exception { static String^ message = gcnew String("Subtree creation failed.");
AddSubTreeFailedException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct IsEndItemException : public Exception { static String^ message = gcnew String("The requested action cannot be performed on an end item.");
IsEndItemException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct EntryNotFoundException : public Exception { static String^ message = gcnew String("The requested entry could not be located in the specified collection.");
EntryNotFoundException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
public ref struct InvalidSetOperationException : public Exception { static String^ message = gcnew String("An invalid set operation was specified.");
InvalidSetOperationException() : Exception(message) { HelpLink = gcnew String("Benedict@NNcNannara.net"); Source = gcnew String("Calculus Subsystem"); } };
Node^ PreviousItem(Node^ node) {
if (node->IsHeader) {return node->Right;}
else if (node->Left != nullptr) { Node^ y = node->Left; while (y->Right != nullptr) y = y->Right; node = y; } else { Node^ y = node->Parent; if (y->IsHeader) return y; while (node == y->Left) {node = y; y = y->Parent;} node = y; } return node;
}
Node^ NextItem(Node^ node) {
if (node->IsHeader) return node->Left;
if (node->Right != nullptr) { node = node->Right; while (node->Left != nullptr) 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;
}
void SwapNodeReference(Node^% first, Node^% second) {Node^ temporary = first; first = second; second = temporary;}
void LeftNodeSwap(Node^ Root, Node^ Replace) {
if (Replace->Left) Replace->Left->Parent = Root; if (Replace->Right) Replace->Right->Parent = Root;
if (Root->Right) Root->Right->Parent = Replace;
if (Replace == Root->Left) { Replace->Parent = Root->Parent; Root->Parent = Replace;
Root->Left = Replace->Left; Replace->Left = Root; } else { Root->Left->Parent = Replace;
if (Replace->Parent->Left == Replace) Replace->Parent->Left = Root; else Replace->Parent->Right = Root;
SwapNodeReference(Root->Left,Replace->Left); SwapNodeReference(Root->Parent,Replace->Parent); }
SwapNodeReference(Root->Right,Replace->Right);
State Balance = Root->Balance; Root->Balance = Replace->Balance; Replace->Balance=Balance;
}
void SwapNodes(Node^ A, Node^ B) {
if (B == A->Left) { if (B->Left) B->Left->Parent = A; if (B->Right) B->Right->Parent = A;
if (A->Right) 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;
SwapNodeReference(A->Right,B->Right); } else if (B == A->Right) { if (B->Right) B->Right->Parent = A; if (B->Left) B->Left->Parent = A;
if (A->Left) 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;
SwapNodeReference(A->Left,B->Left); } else if (A == B->Left) { if (A->Left) A->Left->Parent = B; if (A->Right) A->Right->Parent = B;
if (B->Right) 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;
SwapNodeReference(A->Right,B->Right); } else if (A == B->Right) { if (A->Right) A->Right->Parent = B; if (A->Left) A->Left->Parent = B;
if (B->Left) 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;
SwapNodeReference(A->Left,B->Left); } else { if (A->Parent == B->Parent) SwapNodeReference(A->Parent->Left,A->Parent->Right); 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) B->Left->Parent = A; if (B->Right) B->Right->Parent = A;
if (A->Left) A->Left->Parent = B; if (A->Right) A->Right->Parent = B;
SwapNodeReference(A->Left,B->Left); SwapNodeReference(A->Right,B->Right); SwapNodeReference(A->Parent,B->Parent); }
State Balance = A->Balance; A->Balance = B->Balance; B->Balance=Balance;
}
void RotateLeft(Node^% Root) {
Node^ Parent = Root->Parent; Node^ x = Root->Right;
Root->Parent = x; x->Parent = Parent; if (x->Left) x->Left->Parent = Root;
Root->Right = x->Left; x->Left = Root; Root = x;
}
void RotateRight(Node^% Root) {
Node^ Parent = Root->Parent; Node^ x = Root->Left;
Root->Parent = x; x->Parent = Parent; if (x->Right) x->Right->Parent = Root;
Root->Left = x->Right; x->Right = Root; Root = x;
}
void BalanceLeft(Node^% Root) {
Node^ Left = Root->Left; // Left Subtree of Root Node
switch (Left->Balance) { case State::LeftHigh: Root->Balance = State::Balanced; Left->Balance = State::Balanced; RotateRight(Root); break; case State::RightHigh: { Node^ subRight = Left->Right; // Right subtree of Left switch (subRight->Balance) { case State::Balanced: Root->Balance = State::Balanced; Left->Balance = State::Balanced; break;
case State::RightHigh: Root->Balance = State::Balanced; Left->Balance = State::LeftHigh; break;
case State::LeftHigh: Root->Balance = State::RightHigh; Left->Balance = State::Balanced; break; } subRight->Balance = State::Balanced; RotateLeft(Left); Root->Left = Left; RotateRight(Root); } break;
case State::Balanced: Root->Balance = State::LeftHigh; Left->Balance = State::RightHigh; RotateRight(Root); break; }
}
void BalanceRight(Node^% Root) {
Node^ Right = Root->Right; // Right Subtree of Root Node
switch (Right->Balance) { case State::RightHigh: Root ->Balance = State::Balanced; Right->Balance = State::Balanced; RotateLeft(Root); break;
case State::LeftHigh: { Node^ subLeft = Right->Left; // Left Subtree of Right switch (subLeft->Balance) { case State::Balanced: Root ->Balance = State::Balanced; Right->Balance = State::Balanced; break;
case State::LeftHigh: Root ->Balance = State::Balanced; Right->Balance = State::RightHigh; break;
case State::RightHigh: Root ->Balance = State::LeftHigh; Right->Balance = State::Balanced; break; } subLeft->Balance = State::Balanced; RotateRight(Right); Root->Right = Right; RotateLeft(Root); } break;
case State::Balanced: Root ->Balance = State::RightHigh; Right->Balance = State::LeftHigh; RotateLeft(Root); break; }
}
void BalanceTree(Node^ Root, Direction From) {
bool 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 State::LeftHigh: if (Parent->IsHeader) BalanceLeft(Parent->Parent); else if (Parent->Left == Root) BalanceLeft(Parent->Left); else BalanceLeft(Parent->Right); Taller = false; break;
case State::Balanced: Root->Balance = State::LeftHigh; Taller = true; break;
case State::RightHigh: Root->Balance = State::Balanced; Taller = false; break; } } else { switch (Root->Balance) { case State::LeftHigh: Root->Balance = State::Balanced; Taller = false; break;
case State::Balanced: Root->Balance = State::RightHigh; Taller = true; break;
case State::RightHigh: if (Parent->IsHeader) BalanceRight(Parent->Parent); else if (Parent->Left == Root) BalanceRight(Parent->Left); else BalanceRight(Parent->Right); Taller = false; break; } }
if (Taller) // skip up a level { if (Parent->IsHeader) Taller = false; else { Root = Parent; From = NextFrom; } } } }
void BalanceTreeRemove(Node^ Root, Direction From) {
if (Root->IsHeader) return; bool 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 State::LeftHigh: Root->Balance = State::Balanced; Shorter = true; break;
case State::Balanced: Root->Balance = State::RightHigh; Shorter = false; break;
case State::RightHigh: if (Root->Right->Balance == State::Balanced) Shorter = false; else Shorter = true; if (Parent->IsHeader) BalanceRight(Parent->Parent); else if (Parent->Left == Root) BalanceRight(Parent->Left); else BalanceRight(Parent->Right); break; } } else { switch (Root->Balance) { case State::RightHigh: Root->Balance = State::Balanced; Shorter = true; break;
case State::Balanced: Root->Balance = State::LeftHigh; Shorter = false; break;
case State::LeftHigh: if (Root->Left->Balance == State::Balanced) Shorter = false; else Shorter = true; if (Parent->IsHeader) BalanceLeft(Parent->Parent); else if (Parent->Left == Root) BalanceLeft(Parent->Left); else BalanceLeft(Parent->Right); break; } }
if (Shorter) { if (Parent->IsHeader) Shorter = false; else { From = NextFrom; Root = Parent; } } }
}
Node^ Minimum(Node^ node) {
while (node->Left) node=node->Left; return node;
}
Node^ Maximum(Node^ node) {
while (node->Right) node=node->Right; return node;
}
void AdjustAdd(Node^ Root) {
Node^ Header = Root->Parent; while (!Header->IsHeader) Header=Header->Parent;
if (Root->Parent->Left == Root) { BalanceTree(Root->Parent,Direction::FromLeft); if (Header->Left == Root->Parent) Header->Left = Root; } else { BalanceTree(Root->Parent,Direction::FromRight); if (Header->Right == Root->Parent) Header->Right = Root; }
}
void AdjustRemove(Node^ Parent, Direction Direction) {
BalanceTreeRemove(Parent,Direction); Node^ Header = Parent; while (!Header->IsHeader) Header=Header->Parent;
if (Header->Parent == nullptr) { Header->Left = Header; Header->Right = Header; } else { Header->Left = Minimum(Header->Parent); Header->Right = Maximum(Header->Parent); }
}
unsigned long long Depth(Node^ Root) {
if (Root) { unsigned long long Left = Root->Left ? Depth(Root->Left) : 0; unsigned long long Right = Root->Right ? Depth(Root->Right) : 0; return Left < Right ? Right+1 : Left+1; } else return 0;
}
unsigned long long Count(Node^ Root) {
if (Root) { unsigned long long left = Root->Left ? Count(Root->Left) : 0; unsigned long long right = Root->Right ? Count(Root->Right) : 0; return left + right + 1; } else return 0;
}
public enum class SetOperation { Union, Intersection, SymmetricDifference, Difference, Equality, Inequality, Subset, Superset };
generic<typename T> public ref class SetNode : Node {
public:
T Data;
SetNode(T dataType, Node^ Parent) : Node(Parent) {Data = dataType; }
};
generic<typename T> public value struct SetEntry : System::Collections::Generic::IEnumerator<T> {
public:
SetEntry(Node^ n) { _Node = n; }
property T Value { T get() { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return ((SetNode<T>^)_Node)->Data; } void set(T Value) { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); ((SetNode<T>^)_Node)->Data = Value; } }
property Boolean IsHeader { Boolean get() { return _Node->IsHeader; } }
virtual Boolean MoveNext() { _Node = NextItem(_Node); return _Node->IsHeader ? false : true; }
Boolean MovePrevious() { _Node = PreviousItem(_Node); return _Node->IsHeader ? false : true; }
static SetEntry<T> operator ++(SetEntry<T> entry) { entry._Node = NextItem(entry._Node); return entry; }
static SetEntry<T> operator --(SetEntry<T> entry) { entry._Node = PreviousItem(entry._Node); return entry; }
static SetEntry<T> operator +(SetEntry<T> C, unsigned long long Increment) { SetEntry<T> Result = SetEntry<T>(C._Node); for (unsigned long long i = 0; i < Increment; i++) ++Result; return Result; }
static SetEntry<T> operator +(unsigned long long Increment, SetEntry<T> C) { SetEntry<T> Result = SetEntry<T>(C._Node); for (unsigned long long i = 0; i < Increment; i++) ++Result; return Result; }
static SetEntry<T> operator -(SetEntry<T> C, unsigned long long Decrement) { SetEntry<T> Result = SetEntry<T>(C._Node); for (unsigned long long i = 0; i < Decrement; i++) --Result; return Result; }
virtual void Reset() { while (!_Node->IsHeader) _Node = NextItem(_Node); }
virtual property Object^ InterfaceCurrentA { Object^ get() = System::Collections::IEnumerator::Current::get { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return ((SetNode<T>^)_Node)->Data; } }
virtual property T InterfaceCurrentB { T get() = System::Collections::Generic::IEnumerator<T>::Current::get { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return ((SetNode<T>^)_Node)->Data; } }
static Boolean operator ==(SetEntry<T> x, SetEntry<T> y) { return x._Node == y._Node; } static Boolean operator !=(SetEntry<T> x, SetEntry<T> y) { return x._Node != y._Node; }
static long long operator -(SetEntry<T> This, SetEntry<T> iter) { long long Result = 0; while (This._Node != iter._Node) { iter.MoveNext(); Result++; } return Result; }
virtual String^ ToString() override { if (_Node->Balance == State::Header) throw gcnew IsEndItemException(); return Value->ToString(); }
Node^ _Node;
};
generic<typename T>
[Serializable]
public ref class Set : public System::Collections::Generic::ICollection<T>,
public System::ICloneable, public ISerializable, public IComparable<Set<T>^>, public IEquatable<Set<T>^>
{
public: event TypeAdded<T>^ Added; event TypeRemoved<T>^ Removed; event TypeUpdated<T>^ Updated;
protected: Node^ Header; System::Collections::Generic::IComparer<T>^ TComparer; ICloner<T>^ TCloner; IHasher<T>^ THasher; unsigned long long Nodes;
property Node^ Root { Node^ get() { return Header->Parent; } void set(Node^ Value) { Header->Parent = Value; } }
//*** Constructors ***
public:
Set() { Nodes=0; Header = gcnew Node(); TComparer = System::Collections::Generic::Comparer<T>::Default; TCloner = Calculus::Cloner<T>::Default; THasher = Calculus::Hasher<T>::Default; }
Set(System::Collections::Generic::IComparer<T>^ TCompare) { Nodes=0; Header = gcnew Node(); TComparer = TCompare; TCloner = Calculus::Cloner<T>::Default; THasher = Calculus::Hasher<T>::Default; }
Set(Set<T>^ SetToCopy) { Nodes=0; Header = gcnew Node(); TComparer = SetToCopy->TComparer; TCloner = SetToCopy->TCloner; THasher = SetToCopy->THasher; Copy((SetNode<T>^)SetToCopy->Root); }
Set(System::Collections::Generic::IEnumerable<T>^ Collection) { Nodes=0; Header = gcnew Node(); TComparer = System::Collections::Generic::Comparer<T>::Default; TCloner = Calculus::Cloner<T>::Default; THasher = Calculus::Hasher<T>::Default;
for each (T t in Collection) Add(TCloner->Clone(t)); }
Set(... array<T>^ Collection) { Nodes=0; Header = gcnew Node(); TComparer = System::Collections::Generic::Comparer<T>::Default; TCloner = Calculus::Cloner<T>::Default; THasher = Calculus::Hasher<T>::Default;
for each (T t in Collection) Add(TCloner->Clone(t)); }
Set(System::Collections::Generic::IEnumerable<T>^ Collection, System::Collections::Generic::IComparer<T>^ TCompare) { Nodes=0; Header = gcnew Node(); TComparer = TCompare; TCloner = Calculus::Cloner<T>::Default; THasher = Calculus::Hasher<T>::Default; for each (T t in Collection) Add(TCloner->Clone(t)); }
Set(Set<T>^ A, Set<T>^ B, SetOperation operation) { Nodes=0; Header = gcnew Node(); TComparer = A->TComparer; TCloner = A->TCloner; THasher = A->THasher; CombineSets(A, B, this, operation); }
Set(SerializationInfo^ si, StreamingContext sc) { Nodes=0; System::Collections::Generic::IComparer<T>^ TCompare = (System::Collections::Generic::IComparer<T>^)si->GetValue("TComparer", System::Collections::Generic::IComparer<T>::typeid); Calculus::ICloner<T>^ TClone = (Calculus::ICloner<T>^)si->GetValue("TCloner", ICloner<T>::typeid); Calculus::IHasher<T>^ THasher = (Calculus::IHasher<T>^)si->GetValue("THasher", IHasher<T>::typeid);
Header = gcnew Node(); TComparer = TCompare; TCloner = TClone;
Type^ type = T::typeid;
unsigned long long LoadCount = si->GetUInt64("Count");
for (unsigned long long i = 0; i < LoadCount; i++) { Object^ obj = si->GetValue(i.ToString(), type); Add((T)obj, false); } }
//*** Operators ***
static Set<T>^ operator |(Set<T>^ A, Set<T>^ B) { Set<T>^ U = gcnew Set<T>(A->TComparer); U->TCloner = A->TCloner; U->THasher = A->THasher; CombineSets(A, B, U, SetOperation::Union); return U; }
static Set<T>^ operator &(Set<T>^ A, Set<T>^ B) { Set<T>^ I = gcnew Set<T>(A->TComparer); I->TCloner = A->TCloner; I->THasher = A->THasher; CombineSets(A, B, I, SetOperation::Intersection); return I; }
static Set<T>^ operator ^(Set<T>^ A, Set<T>^ B) { Set<T>^ S = gcnew Set<T>(A->TComparer); S->TCloner = A->TCloner; S->THasher = A->THasher; CombineSets(A, B, S, SetOperation::SymmetricDifference); return S; }
static Set<T>^ operator -(Set<T>^ A, Set<T>^ B) { Set<T>^ S = gcnew Set<T>(A->TComparer); S->TCloner = A->TCloner; S->THasher = A->THasher; CombineSets(A, B, S, SetOperation::Difference); return S; }
static Boolean operator ==(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Equality); }
static Boolean operator !=(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Inequality); }
static Boolean operator <(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Subset); }
static Boolean operator >(Set<T>^ A, Set<T>^ B) { return CheckSets(A, B, SetOperation::Superset); }
property Boolean default [T] { Boolean get(T key) { if (Root == nullptr) return false; else { Node^ search = Root;
do { int Result = TComparer->Compare(key, static_cast<SetNode<T>^>(search)->Data);
if (Result < 0) search = search->Left;
else if (Result > 0) search = search->Right;
else break;
} while (search != nullptr);
return search != nullptr; } } }
static Set<T>^ operator +(Set<T>^ set, T t) { set->Add(t, false); return set; }
static Set<T>^ operator -(Set<T>^ set, T t) { set->Remove(t); return set; }
//*** Properties ***
property SetEntry<T> Begin { SetEntry<T> get() { return SetEntry<T>(Header->Left); } }
property ICloner<T>^ TypeCloner { ICloner<T>^ get() { return TCloner; } void set(ICloner<T>^ Value) { TCloner = Value; } } property System::Collections::Generic::IComparer<T>^ Comparer {System::Collections::Generic::IComparer<T>^ get() { return TComparer; } }
virtual property int Count { int get() { return (int)Length; } }
property SetEntry<T> End { SetEntry<T> get() { return SetEntry<T>(Header); } }
property T First { T get() { return ((SetNode<T>^)LeftMost)->Data; } }
property int Hash { int get() { return GetHashCode(); } }
property IHasher<T>^ Hasher { IHasher<T>^ get() { return THasher; } void set(IHasher<T>^ Value) { THasher = Value; } }
virtual property Boolean IsReadOnly { Boolean get() { return false; } }
virtual property Boolean IsSynchronized { Boolean get() { return true; } }
property T Last { T get() { return ((SetNode<T>^)RightMost)->Data; } }
property Node^ LeftMost { Node^ get() { return Header->Left; } void set(Node^ Value) { Header->Left = Value; } }
property unsigned long long Length { unsigned long long get() { return Count;} }
property Node^ RightMost { Node^ get() { return Header->Right; } void set(Node^ Value) { Header->Right = Value; } } property Object^ SyncRoot { Object^ get() { return this; } }
//*** Public Methods ***
SetEntry<T> After(T Value, Boolean equals) { return SetEntry<T>(equals ? AfterEquals(Value) : After(Value)); }
virtual void Add(T t) { Add(t, false); }
void Add(SetEntry<T> cse) { Add(TCloner->Clone(cse.Value), false); }
unsigned long long Add(System::Collections::Generic::IEnumerable<T>^ copy) { unsigned long long count = 0;
for each(T t in copy) { Add(TCloner->Clone(t), false); count++; }
return count; }
SetEntry<T> Before(T value, bool equals) { return SetEntry<T>(equals ? BeforeEquals(value) : Before(value)); }
virtual void Clear() { Remove(); }
void CallRemoved(T data) { Removed(this, data); }
virtual Object^ Clone() { Set<T>^ setOut = gcnew Set<T>(TComparer); setOut->TCloner = TCloner; setOut->THasher = THasher; setOut->Copy((SetNode<T>^)Root); return setOut; }
virtual int CompareTo(Set<T>^ B) { return CompareSets(this, B); }
virtual bool Contains(T t) { Node^ found = Search(t); return found != nullptr ? true : false; }
virtual Boolean Contains(Set<T>^ ss) { for each (T t in ss) if (Search(t) == nullptr) return false;
return true; }
virtual void CopyTo(array<T>^ arr, int i) { SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left); SetEntry<T> end = SetEntry<T>(Header);
while (begin != end) { arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i); i++; begin.MoveNext(); } }
virtual void CopyTo(System::Array^ arr, int i) { SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left); SetEntry<T> end = SetEntry<T>(Header);
while (begin != end) { arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i); i++; begin.MoveNext(); } }
virtual Boolean Equals(Set<T>^ compare) { SetEntry<T> first1 = Begin; SetEntry<T> last1 = End; SetEntry<T> first2 = compare->Begin; SetEntry<T> last2 = compare->End;
Boolean equals = true;
while (first1 != last1 && first2 != last2) { if (TComparer->Compare(first1.Value, first2.Value) == 0) { first1.MoveNext(); first2.MoveNext(); } else { equals = false; break; } }
if (equals) { if (first1 != last1) equals = false; if (first2 != last2) equals = false; }
return equals; }
T Find(T value) { Node^ _Node = Search(value); if (_Node == nullptr) throw gcnew EntryNotFoundException(); return ((SetNode<T>^)_Node)->Data; }
virtual System::Collections::IEnumerator^ InterfaceGetEnumeratorSimple() sealed = System::Collections::IEnumerable::GetEnumerator { return gcnew SetEntry<T>(Header); }
virtual System::Collections::Generic::IEnumerator<T>^ InterfaceGetEnumerator() sealed = System::Collections::Generic::IEnumerable<T>::GetEnumerator { return gcnew SetEntry<T>(Header); }
virtual Int32 GetHashCode() override { Int32 HashCode = 0; for each (T t in this) HashCode += THasher->GetHashCode(t); return HashCode; }
virtual void GetObjectData(SerializationInfo^ si, StreamingContext sc) { si->SetType(Calculus::Set<T>::typeid);
Type^ type = T::typeid;
unsigned long long index = 0; for each (T e in *this) { si->AddValue(index.ToString(), e, type); index++; }
si->AddValue("Count", index); si->AddValue("TComparer", TComparer, TComparer->GetType()); si->AddValue("TCloner", TCloner, TCloner->GetType()); si->AddValue("THasher", THasher, THasher->GetType()); }
SetEntry<T> Insert(T t) { return SetEntry<T>(Add(t, false)); }
SetEntry<T> Locate(T value) { Node^ _Node = Search(value); if (_Node == nullptr) throw gcnew EntryNotFoundException(); return SetEntry<T>(_Node); }
void Notify() { Notify((SetNode<T>^)Root); }
unsigned long long Remove() { for each (T t in this) Removed(this, t); unsigned long long count = Nodes; Root = nullptr; LeftMost = Header; RightMost = Header; Nodes = 0; return count; }
virtual bool Remove(T data) { Node^ root = Root;
for (; ; ) { if (root == nullptr) throw gcnew EntryNotFoundException();
int compare = TComparer->Compare(data, ((SetNode<T>^)root)->Data);
if (compare < 0) root = root->Left;
else if (compare > 0) root = root->Right;
else // Item is found { if (root->Left != nullptr && root->Right != nullptr) { Node^ replace = root->Left; while (replace->Right != nullptr) replace = replace->Right; SwapNodes(root, replace); }
Node^ Parent = root->Parent;
Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;
if (LeftMost == root) { Node^ n = NextItem(root);
if (n->IsHeader) { LeftMost = Header; RightMost = Header; } else LeftMost = n; } else if (RightMost == root) { Node^ p = PreviousItem(root);
if (p->IsHeader) { LeftMost = Header; RightMost = Header; } else RightMost = p; }
if (root->Left == nullptr) { if (Parent == Header) Header->Parent = root->Right; else if (Parent->Left == root) Parent->Left = root->Right; else Parent->Right = root->Right;
if (root->Right != nullptr) 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 != nullptr) root->Left->Parent = Parent; }
AdjustRemove(Parent, From); Nodes--; Removed(this, ((SetNode<T>^)root)->Data); break; } } return true; }
void Remove(SetEntry<T> i) { Remove(i._Node); }
Node^ Search(T data) { if (Root == nullptr) return nullptr; else { Node^ search = Root;
do { int Result = TComparer->Compare(data, ((SetNode<T>^)search)->Data);
if (Result < 0) search = search->Left;
else if (Result > 0) search = search->Right;
else break;
} while (search != nullptr);
return search; } }
virtual String^ ToString() override { String^ StringOut = gcnew String("{");
SetEntry<T> start = Begin; SetEntry<T> end = End; SetEntry<T> last = End - 1;
while (start != end) { String^ NewStringOut = start.Value->ToString(); if (start != last) NewStringOut = NewStringOut + gcnew String(","); StringOut = StringOut + NewStringOut; ++start; }
StringOut = StringOut + gcnew String("}"); return StringOut; }
void Update(T value) { if (Root == nullptr) throw gcnew EntryNotFoundException(); else { Node^ search = Root;
do { int Result = TComparer->Compare(value, ((SetNode<T>^)search)->Data);
if (Result < 0) search = search->Left;
else if (Result > 0) search = search->Right;
else break;
} while (search != nullptr);
if (search == nullptr) throw gcnew EntryNotFoundException();
T saved = ((SetNode<T>^)search)->Data; ((SetNode<T>^)search)->Data = value; Updated(this, saved, value); } }
void Update(SetEntry<T>^ entry, T after) { Update((SetNode<T>^)entry->_Node, after); }
void Validate() { if (Nodes == 0 || Root == nullptr) { if (Nodes != 0) { throw gcnew InvalidEmptyTreeException(); } if (Root != nullptr) { throw gcnew InvalidEmptyTreeException(); } if (LeftMost != Header) { throw gcnew InvalidEndItemException(); } if (RightMost != Header) { throw gcnew InvalidEndItemException(); } }
Validate((SetNode<T>^)Root);
if (Root != nullptr) { Node^ x = Root; while (x->Left != nullptr) x = x->Left;
if (LeftMost != x) throw gcnew InvalidEndItemException();
Node^ y = Root; while (y->Right != nullptr) y = y->Right;
if (RightMost != y) throw gcnew InvalidEndItemException(); } }
//*** Private Methods ***
protected:
Node^ After(T data) { Node^ y = Header; Node^ x = Root;
while (x != nullptr) if (TComparer->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 = Root;
while (x != nullptr) { int c = TComparer->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; }
SetNode<T>^ Add(T data, bool exist) { Node^ root = Root;
if (root == nullptr) { Root = gcnew SetNode<T>(data, Header); Nodes++; LeftMost = Root; RightMost = Root; Added(this, ((SetNode<T>^)Root)->Data); return (SetNode<T>^)Root; } else { for (; ; ) { int compare = TComparer->Compare(data, static_cast<SetNode<T>^>(root)->Data);
if (compare == 0) // Item Exists { if (exist) { T saved = ((SetNode<T>^)root)->Data; ((SetNode<T>^)root)->Data = data; Updated(this, saved, data); return (SetNode<T>^)root; } else throw gcnew EntryAlreadyExistsException(); }
else if (compare < 0) { if (root->Left != nullptr) root = root->Left; else { SetNode<T>^ NewNode = gcnew SetNode<T>(data, root); Nodes++; root->Left = NewNode; AdjustAdd(NewNode); Added(this, NewNode->Data); return NewNode; } }
else { if (root->Right != nullptr) root = root->Right; else { SetNode<T>^ NewNode = gcnew SetNode<T>(data, root); Nodes++; root->Right = NewNode; AdjustAdd(NewNode); Added(this, NewNode->Data); return NewNode; } } } } }
unsigned long long Add(Node^ begin, Node^ end) { bool success = true; unsigned long long count = 0;
SetEntry<T> i(begin);
while (success && i._Node != end) { if (!i._Node->IsHeader) { try { Add(TCloner->Clone(i.Value), false); count++; i.MoveNext(); } catch (Exception^) { success = false; } } else i.MoveNext(); } if (!success) { if (count != 0) { i.MovePrevious(); SetEntry<T> start(begin); start.MovePrevious();
while (i != start) { SetEntry<T> j(i._Node); j.MovePrevious(); if (!i._Node->IsHeader) Remove(i.Value); i = j; } } throw gcnew AddSubTreeFailedException(); } return Count; }
Node^ Before(T data) { Node^ y = Header; Node^ x = Root;
while (x != nullptr) if (TComparer->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 = Root;
while (x != nullptr) { int c = TComparer->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; }
void Bounds() { LeftMost = GetFirst(); RightMost = GetLast(); }
void Copy(SetNode<T>^ CopyRoot) { if (Root != nullptr) Remove(); if (CopyRoot != nullptr) { Copy(Header->Parent, CopyRoot, Header); LeftMost = GetFirst(); RightMost = GetLast(); } }
void Copy(Node^% root, SetNode<T>^ CopyRoot, Node^ Parent) { root = gcnew SetNode<T>(TCloner->Clone(CopyRoot->Data), Parent); Nodes++;
root->Balance = CopyRoot->Balance;
if (CopyRoot->Left != nullptr) Copy(root->Left, (SetNode<T>^)CopyRoot->Left, (SetNode<T>^)root);
if (CopyRoot->Right != nullptr) Copy(root->Right, (SetNode<T>^)CopyRoot->Right, (SetNode<T>^)root);
Added(this, ((SetNode<T>^)root)->Data); }
Node^ GetFirst() { if (Root == nullptr) return Header;
else { Node^ search = Root; while (search->Left != nullptr) search = search->Left; return search; } }
Node^ GetLast() { if (Root == nullptr) return Header;
else { Node^ search = Root; while (search->Right != nullptr) search = search->Right; return search; } }
void Import(SetNode<T>^ n) { if (n != nullptr) ImportTree(n); }
void ImportTree(SetNode<T>^ n) { if (n->Left != nullptr) ImportTree((SetNode<T>^)n->Left); Add(n->Data, false); if (n->Right != nullptr) ImportTree((SetNode<T>^)n->Right); }
void Notify(SetNode<T>^ root) { if (root != nullptr) { if (root->Left != nullptr) Notify((SetNode<T>^)root->Left);
Added(this, root->Data);
if (root->Right != nullptr) Notify((SetNode<T>^)root->Right); } }
void Remove(Node^ root) { if (root->Left != nullptr && root->Right != nullptr) { Node^ replace = root->Left; while (replace->Right != nullptr) replace = replace->Right; SwapNodes(root, replace); }
Node^ Parent = root->Parent;
Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;
if (LeftMost == root) { Node^ n = NextItem(root);
if (n->IsHeader) { LeftMost = Header; RightMost = Header; } else LeftMost = n; } else if (RightMost == root) { Node^ p = PreviousItem(root);
if (p->IsHeader) { LeftMost = Header; RightMost = Header; } else RightMost = p; }
if (root->Left == nullptr) { if (Parent == Header) Header->Parent = root->Right; else if (Parent->Left == root) Parent->Left = root->Right; else Parent->Right = root->Right;
if (root->Right != nullptr) 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 != nullptr) root->Left->Parent = Parent; }
AdjustRemove(Parent, From); Nodes--; Removed(this, ((SetNode<T>^)root)->Data); }
unsigned long long Remove(Node^ i, Node^ j) { if (i == LeftMost && j == Header) return Remove(); else { unsigned long long count = 0; while (i != j) { SetEntry<T> iter(i); iter.MoveNext(); if (i != Header) { Remove(i); count++; } i = iter._Node; }
return count; } }
void Update(SetNode<T>^ Node, T value) { if (TComparer->Compare(Node->Data, value) != 0) throw gcnew DifferentKeysException(); T saved = Node->Data; Node->Data = value; Updated(this, saved, value); }
void Validate(SetNode<T>^ root) { if (root == nullptr) return;
if (root->Left != nullptr) { SetNode<T>^ Left = (SetNode<T>^)root->Left;
if (TComparer->Compare(Left->Data, root->Data) >= 0) throw gcnew OutOfKeyOrderException();
if (Left->Parent != root) throw gcnew TreeInvalidParentException();
Validate((SetNode<T>^)root->Left); }
if (root->Right != nullptr) { SetNode<T>^ Right = (SetNode<T>^)root->Right;
if (TComparer->Compare(Right->Data, root->Data) <= 0) throw gcnew OutOfKeyOrderException();
if (Right->Parent != root) throw gcnew TreeInvalidParentException();
Validate((SetNode<T>^)root->Right); }
unsigned long long DepthLeft = root->Left != nullptr ? Depth(root->Left) : 0; unsigned long long DepthRight = root->Right != nullptr ? Depth(root->Right) : 0;
if (DepthLeft > DepthRight && DepthLeft - DepthRight > 2) throw gcnew TreeOutOfBalanceException();
if (DepthLeft < DepthRight && DepthRight - DepthLeft > 2) throw gcnew TreeOutOfBalanceException(); }
//*** Static Methods
static void CombineSets(Set<T>^ A, Set<T>^ B, Set<T>^ R, SetOperation operation)
{
System::Collections::Generic::IComparer<T>^ TComparer = R->TComparer; Calculus::ICloner<T>^ TCloner = R->TCloner;
SetEntry<T> first1 = A->Begin; SetEntry<T> last1 = A->End; SetEntry<T> first2 = B->Begin; SetEntry<T> last2 = B->End;
switch (operation) { case SetOperation::Union: while (first1 != last1 && first2 != last2) { int order = TComparer->Compare(first1.Value, first2.Value);
if (order < 0) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); }
else if (order > 0) { R->Add(TCloner->Clone(first2.Value)); first2.MoveNext(); }
else { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); first2.MoveNext(); } } while (first1 != last1) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); } while (first2 != last2) { R->Add(TCloner->Clone(first2.Value)); first2.MoveNext(); } return;
case SetOperation::Intersection: while (first1 != last1 && first2 != last2) { int order = TComparer->Compare(first1.Value, first2.Value);
if (order < 0) first1.MoveNext();
else if (order > 0) first2.MoveNext();
else { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); first2.MoveNext(); } } return;
case SetOperation::SymmetricDifference: while (first1 != last1 && first2 != last2) { int order = TComparer->Compare(first1.Value, first2.Value);
if (order < 0) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); }
else if (order > 0) { R->Add(TCloner->Clone(first2.Value)); first2.MoveNext(); }
else { first1.MoveNext(); first2.MoveNext(); } }
while (first1 != last1) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); }
while (first2 != last2) { R->Add(TCloner->Clone(first2.Value)); first2.MoveNext(); } return;
case SetOperation::Difference: while (first1 != last1 && first2 != last2) { int order = TComparer->Compare(first1.Value, first2.Value);
if (order < 0) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); }
else if (order > 0) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); first2.MoveNext(); }
else { first1.MoveNext(); first2.MoveNext(); } }
while (first1 != last1) { R->Add(TCloner->Clone(first1.Value)); first1.MoveNext(); } return; }
throw gcnew InvalidSetOperationException(); }
static Boolean CheckSets(Set<T>^ A, Set<T>^ B, SetOperation operation) { System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;
SetEntry<T> first1 = A->Begin; SetEntry<T> last1 = A->End; SetEntry<T> first2 = B->Begin; SetEntry<T> last2 = B->End;
switch (operation) { case SetOperation::Equality: case SetOperation::Inequality: { bool equals = true;
while (first1 != last1 && first2 != last2) { if (TComparer->Compare(first1.Value, first2.Value) == 0) { first1.MoveNext(); first2.MoveNext(); } else { equals = false; break; } }
if (equals) { if (first1 != last1) equals = false; if (first2 != last2) equals = false; }
if (operation == SetOperation::Equality) return equals; else return !equals; }
case SetOperation::Subset: case SetOperation::Superset: { bool subset = true;
while (first1 != last1 && first2 != last2) { int order = TComparer->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 != last1) subset = false;
if (operation == SetOperation::Subset) return subset; else return !subset; } }
throw gcnew InvalidSetOperationException(); }
static int CompareSets(Set<T>^ A, Set<T>^ B) { System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;
SetEntry<T> first1 = A->Begin; SetEntry<T> last1 = A->End; SetEntry<T> first2 = B->Begin; SetEntry<T> last2 = B->End;
int Result = 0;
while (first1 != last1 && first2 != last2) { Result = TComparer->Compare(first1.Value, first2.Value); if (Result == 0) { first1.MoveNext(); first2.MoveNext(); } else return Result; }
if (first1 != last1) return 1; if (first2 != last2) return -1;
return 0; } };
}
using namespace Calculus;
int main(array<System::String ^> ^args) {
Set<int>^ S = gcnew Set<int>(1, 3, 5 , 6, 7, 9); Set<int>^ T = gcnew Set<int>(2, 4, 6 , 7, 8, 9); Set<int>^ U = S | T; Console::WriteLine(S + " | " + T + " == " + U); return 0;
} </lang>