Rosetta Code

AVL tree/Managed C++: Difference between revisions

Page Discussion

AVL tree/Managed C++ (view source)

Revision as of 11:31, 13 July 2016

168 bytes removed ,  7 years ago
→‎Code
(added page for AVL_tree/Managed C++)
 
Line 2:
<lang cpp>// AVL in Managed C++
// AVL in Managed C++
 
using namespace System;
using namespace System;
Line 8 ⟶ 10:
using namespace System::Threading;
using namespace System::Runtime::Serialization;
 
namespace ISharp
{
 
public enum class State
{
Line 19 ⟶ 21:
RightHigh
};
 
public enum class Direction { FromLeft, FromRight };
 
public ref struct Node
{
Line 28 ⟶ 30:
Node^ Parent;
State Balance;
 
Node()
{
Line 36 ⟶ 38:
Balance = State::Header;
}
 
Node(Node^ p)
{
Line 44 ⟶ 46:
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
Line 66 ⟶ 68:
int GetHashCode(T t);
};
 
generic<typename T>
[Serializable]
Line 72 ⟶ 74:
{
public:
 
static property Hasher<T>^ Default { Hasher<T>^ get(); }
 
virtual int GetHashCode(T t) = 0;
};
 
generic<typename T>
[Serializable]
Line 83 ⟶ 85:
{
public:
 
virtual int GetHashCode(T t) override
{
Line 89 ⟶ 91:
}
};
 
generic<typename T>
Hasher<T>^ Hasher<T>::Default::get() { return gcnew DefaultHasher<T>(); }
 
 
generic<typename T>
public interface struct ICloneable
Line 99 ⟶ 101:
T Clone();
};
 
generic<typename T>
public interface class ICloner { T Clone(T t); };
 
generic<typename T>
[Serializable]
Line 108 ⟶ 110:
{
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]
Line 124 ⟶ 126:
}
};
 
generic<typename T>
[Serializable]
Line 135 ⟶ 137:
}
};
 
generic<typename T>
[Serializable]
Line 145 ⟶ 147:
}
};
 
generic<typename T>
Cloner<T>^ Cloner<T>::Default::get()
Line 159 ⟶ 161:
return gcnew DefaultNoCloner<T>();
}
 
generic<typename T>
Cloner<T>^ Cloner<T>::Invisible::get() { return gcnew DefaultNoCloner<T>(); }
Line 165 ⟶ 167:
{
static String^ message = gcnew String("A tree was found to be out of key order.");
 
OutOfKeyOrderException() : Exception(message)
{
Line 172 ⟶ 174:
}
};
 
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)
{
Line 183 ⟶ 185:
}
};
 
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)
{
Line 194 ⟶ 196:
}
};
 
public ref struct InvalidEmptyTreeException : public Exception
{
static String^ message = gcnew String("The validation routines detected that an empty tree is invalid.");
 
InvalidEmptyTreeException() : Exception(message)
{
Line 205 ⟶ 207:
}
};
 
 
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)
{
Line 217 ⟶ 219:
}
};
 
public ref struct EntryAlreadyExistsException : public Exception
{
static String^ message = gcnew String("An entry already exists in the collection.");
 
EntryAlreadyExistsException() : Exception(message)
{
Line 228 ⟶ 230:
}
};
 
public ref struct DifferentKeysException : public Exception
{
static String^ message = gcnew String("The specified items have different keys.");
 
DifferentKeysException() : Exception(message)
{
Line 239 ⟶ 241:
}
};
 
public ref struct AddSubTreeFailedException : public Exception
{
static String^ message = gcnew String("Subtree creation failed.");
 
AddSubTreeFailedException() : Exception(message)
{
Line 250 ⟶ 252:
}
};
 
public ref struct IsEndItemException : public Exception
{
static String^ message = gcnew String("The requested action cannot be performed on an end item.");
 
IsEndItemException() : Exception(message)
{
Line 261 ⟶ 263:
}
};
 
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)
{
Line 272 ⟶ 274:
}
};
 
public ref struct InvalidSetOperationException : public Exception
{
static String^ message = gcnew String("An invalid set operation was specified.");
 
InvalidSetOperationException() : Exception(message)
{
Line 283 ⟶ 285:
}
};
 
Node^ PreviousItem(Node^ node)
{
if (node->IsHeader) {return node->Right;}
 
else if (node->Left != nullptr)
{
Line 303 ⟶ 305:
return node;
}
 
Node^ NextItem(Node^ node)
{
if (node->IsHeader) return node->Left;
 
if (node->Right != nullptr)
{
Line 322 ⟶ 324:
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;
Line 344 ⟶ 346:
{
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)
{
Line 367 ⟶ 369:
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)
{
Line 378 ⟶ 380:
}
else A->Parent->Parent = B;
 
B->Parent = A->Parent;
A->Parent = B;
 
A->Left = B->Left;
B->Left = A;
 
SwapNodeReference(A->Right,B->Right);
}
Line 391 ⟶ 393:
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)
{
Line 402 ⟶ 404:
}
else A->Parent->Parent = B;
 
B->Parent = A->Parent;
A->Parent = B;
 
A->Right = B->Right;
B->Right = A;
 
SwapNodeReference(A->Left,B->Left);
}
Line 415 ⟶ 417:
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)
{
Line 426 ⟶ 428:
}
else B->Parent->Parent = A;
 
A->Parent = B->Parent;
B->Parent = A;
 
B->Left = A->Left;
A->Left = B;
 
SwapNodeReference(A->Right,B->Right);
}
Line 439 ⟶ 441:
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)
{
Line 450 ⟶ 452:
}
else B->Parent->Parent = A;
 
A->Parent = B->Parent;
B->Parent = A;
 
B->Right = A->Right;
A->Right = B;
 
SwapNodeReference(A->Left,B->Left);
}
Line 473 ⟶ 475:
}
else A->Parent->Parent = B;
 
if (!B->Parent->IsHeader)
{
Line 483 ⟶ 485:
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:
{
Line 545 ⟶ 547:
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;
Line 566 ⟶ 568:
}
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:
{
Line 592 ⟶ 594:
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;
Line 613 ⟶ 615:
}
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)
Line 644 ⟶ 646:
Taller = false;
break;
 
case State::Balanced:
Root->Balance = State::LeftHigh;
Taller = true;
break;
 
case State::RightHigh:
Root->Balance = State::Balanced;
Taller = false;
Line 660 ⟶ 662:
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);
Line 681 ⟶ 683:
}
}
 
if (Taller) // skip up a level
{
Line 694 ⟶ 696:
}
}
 
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)
Line 713 ⟶ 715:
Shorter = true;
break;
 
case State::Balanced:
Root->Balance = State::RightHigh;
Shorter = false;
break;
 
case State::RightHigh:
if (Root->Right->Balance == State::Balanced)
Shorter = false;
Line 741 ⟶ 743:
Shorter = true;
break;
 
case State::Balanced:
Root->Balance = State::LeftHigh;
Shorter = false;
break;
 
case State::LeftHigh:
if (Root->Left->Balance == State::Balanced)
Shorter = false;
Line 761 ⟶ 763:
}
}
 
if (Shorter)
{
Line 774 ⟶ 776:
}
}
 
Node^ Minimum(Node^ node)
{
Line 780 ⟶ 782:
return node;
}
 
Node^ Maximum(Node^ node)
{
Line 786 ⟶ 788:
return node;
}
 
void AdjustAdd(Node^ Root)
{
Node^ Header = Root->Parent;
while (!Header->IsHeader) Header=Header->Parent;
 
if (Root->Parent->Left == Root)
{
Line 803 ⟶ 805:
}
}
 
void AdjustRemove(Node^ Parent, Direction Direction)
{
Line 810 ⟶ 812:
Node^ Header = Parent;
while (!Header->IsHeader) Header=Header->Parent;
 
if (Header->Parent == nullptr)
{
Line 822 ⟶ 824:
}
}
 
unsigned long long Depth(Node^ Root)
{
Line 834 ⟶ 836:
return 0;
}
 
unsigned long long Count(Node^ Root)
{
Line 846 ⟶ 848:
return 0;
}
 
public enum class SetOperation
{
Line 858 ⟶ 860:
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
{
Line 889 ⟶ 891:
}
}
 
property Boolean IsHeader { Boolean get() { return _Node->IsHeader; } }
 
virtual Boolean MoveNext()
{
Line 897 ⟶ 899:
return _Node->IsHeader ? false : true;
}
 
Boolean MovePrevious()
{
Line 903 ⟶ 905:
return _Node->IsHeader ? false : true;
}
 
static SetEntry<T> operator ++(SetEntry<T> entry)
{
Line 909 ⟶ 911:
return entry;
}
 
static SetEntry<T> operator --(SetEntry<T> entry)
{
Line 915 ⟶ 917:
return entry;
}
 
static SetEntry<T> operator +(SetEntry<T> C, unsigned long long Increment)
{
Line 922 ⟶ 924:
return Result;
}
 
static SetEntry<T> operator +(unsigned long long Increment, SetEntry<T> C)
{
Line 929 ⟶ 931:
return Result;
}
 
static SetEntry<T> operator -(SetEntry<T> C, unsigned long long Decrement)
{
Line 936 ⟶ 938:
return Result;
}
 
virtual void Reset()
{ while (!_Node->IsHeader) _Node = NextItem(_Node); }
 
virtual property Object^ InterfaceCurrentA
{
Line 948 ⟶ 950:
}
}
 
virtual property T InterfaceCurrentB
{
Line 957 ⟶ 959:
}
}
 
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)
{
Line 967 ⟶ 969:
return Result;
}
 
virtual String^ ToString() override
{
Line 973 ⟶ 975:
return Value->ToString();
}
 
Node^ _Node;
};
 
 
generic<typename T>
[Serializable]
Line 990 ⟶ 992:
event TypeRemoved<T>^ Removed;
event TypeUpdated<T>^ Updated;
 
protected:
Node^ Header;
Line 997 ⟶ 999:
IHasher<T>^ THasher;
unsigned long long Nodes;
 
property Node^ Root
{
Line 1,003 ⟶ 1,005:
void set(Node^ Value) { Header->Parent = Value; }
}
 
//*** Constructors ***
 
public:
 
Set()
{
Nodes=0;
Header = gcnew Node();
TComparer = System::Collections::Generic::Comparer<T>::Default;
TCloner = ISharp::Cloner<T>::Default;
THasher = ISharp::Hasher<T>::Default;
}
 
Set(System::Collections::Generic::IComparer<T>^ TCompare)
{
Line 1,025 ⟶ 1,027:
THasher = ISharp::Hasher<T>::Default;
}
 
Set(Set<T>^ SetToCopy)
{
Line 1,035 ⟶ 1,037:
Copy((SetNode<T>^)SetToCopy->Root);
}
 
Set(System::Collections::Generic::IEnumerable<T>^ Collection)
{
Line 1,043 ⟶ 1,045:
TCloner = ISharp::Cloner<T>::Default;
THasher = ISharp::Hasher<T>::Default;
 
for each (T t in Collection) Add(TCloner->Clone(t));
}
 
Set(... array<T>^ Collection)
{
Line 1,054 ⟶ 1,056:
TCloner = ISharp::Cloner<T>::Default;
THasher = ISharp::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)
Line 1,069 ⟶ 1,071:
for each (T t in Collection) Add(TCloner->Clone(t));
}
 
Set(Set<T>^ A,
Set<T>^ B,
Line 1,081 ⟶ 1,083:
CombineSets(A, B, this, operation);
}
 
Set(SerializationInfo^ si, StreamingContext sc)
{
Line 1,088 ⟶ 1,090:
ISharp::ICloner<T>^ TClone = (ISharp::ICloner<T>^)si->GetValue("TCloner", ICloner<T>::typeid);
ISharp::IHasher<T>^ THasher = (ISharp::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++)
{
Line 1,103 ⟶ 1,105:
}
}
 
//*** Operators ***
 
static Set<T>^ operator |(Set<T>^ A, Set<T>^ B)
{
Line 1,114 ⟶ 1,116:
return U;
}
 
static Set<T>^ operator &(Set<T>^ A, Set<T>^ B)
{
Line 1,123 ⟶ 1,125:
return I;
}
 
static Set<T>^ operator ^(Set<T>^ A, Set<T>^ B)
{
Line 1,132 ⟶ 1,134:
return S;
}
 
static Set<T>^ operator -(Set<T>^ A, Set<T>^ B)
{
Line 1,141 ⟶ 1,143:
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]
{
Line 1,171 ⟶ 1,173:
{
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)
{
Line 1,194 ⟶ 1,196:
return set;
}
 
static Set<T>^ operator -(Set<T>^ set, T t)
{
Line 1,200 ⟶ 1,202:
return set;
}
 
//*** Properties ***
 
property SetEntry<T> Begin
{ SetEntry<T> get() { return SetEntry<T>(Header->Left); } }
 
property ICloner<T>^ TypeCloner
{
Line 1,213 ⟶ 1,215:
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
{
Line 1,229 ⟶ 1,231:
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
{
Line 1,242 ⟶ 1,244:
void set(Node^ Value) { Header->Left = Value; }
}
 
property unsigned long long Length { unsigned long long get() { return Count;} }
 
property Node^ RightMost
{
Line 1,252 ⟶ 1,254:
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)
{
Line 1,279 ⟶ 1,281:
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()
{
Line 1,300 ⟶ 1,302:
return setOut;
}
 
virtual int CompareTo(Set<T>^ B)
{
return CompareSets(this, B);
}
 
virtual bool Contains(T t)
{
Line 1,311 ⟶ 1,313:
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)
{
Line 1,331 ⟶ 1,333:
}
}
 
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)
{
Line 1,343 ⟶ 1,345:
}
}
 
virtual Boolean Equals(Set<T>^ compare)
{
Line 1,350 ⟶ 1,352:
SetEntry<T> first2 = compare->Begin;
SetEntry<T> last2 = compare->End;
 
Boolean equals = true;
 
while (first1 != last1 && first2 != last2)
{
Line 1,360 ⟶ 1,362:
{ equals = false; break; }
}
 
if (equals)
{
Line 1,366 ⟶ 1,368:
if (first2 != last2) equals = false;
}
 
return equals;
}
 
T Find(T value)
{
Line 1,377 ⟶ 1,379:
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
{
Line 1,390 ⟶ 1,392:
return HashCode;
}
 
virtual void GetObjectData(SerializationInfo^ si, StreamingContext sc)
{
si->SetType(ISharp::Set<T>::typeid);
 
Type^ type = T::typeid;
 
unsigned long long index = 0;
for each (T e in *this)
Line 1,403 ⟶ 1,405:
index++;
}
 
si->AddValue("Count", index);
si->AddValue("TComparer", TComparer, TComparer->GetType());
Line 1,409 ⟶ 1,411:
si->AddValue("THasher", THasher, THasher->GetType());
}
 
SetEntry<T> Insert(T t) { return SetEntry<T>(Add(t, false)); }
 
SetEntry<T> Locate(T value)
{
Line 1,419 ⟶ 1,421:
return SetEntry<T>(_Node);
}
 
void Notify()
{
Notify((SetNode<T>^)Root);
}
 
unsigned long long Remove()
{
Line 1,435 ⟶ 1,437:
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
{
Line 1,460 ⟶ 1,462:
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; }
Line 1,477 ⟶ 1,479:
{
Node^ p = PreviousItem(root);
 
if (p->IsHeader)
{ LeftMost = Header; RightMost = Header; }
Line 1,483 ⟶ 1,485:
RightMost = p;
}
 
if (root->Left == nullptr)
{
if (Parent == Header)
Line 1,492 ⟶ 1,494:
else
Parent->Right = root->Right;
 
if (root->Right != nullptr) root->Right->Parent = Parent;
}
else
Line 1,503 ⟶ 1,505:
else
Parent->Right = root->Left;
 
if (root->Left != nullptr) root->Left->Parent = Parent;
}
 
AdjustRemove(Parent, From);
Nodes--;
Line 1,515 ⟶ 1,517:
return true;
}
 
void Remove(SetEntry<T> i) { Remove(i._Node); }
 
Node^ Search(T data)
{
Line 1,525 ⟶ 1,527:
{
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)
{
Line 1,557 ⟶ 1,559:
++start;
}
 
StringOut = StringOut + gcnew String("}");
return StringOut;
}
 
void Update(T value)
{
Line 1,569 ⟶ 1,571:
{
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;
Line 1,589 ⟶ 1,591:
}
}
 
void Update(SetEntry<T>^ entry, T after) { Update((SetNode<T>^)entry->_Node, after); }
 
void Validate()
{
Line 1,601 ⟶ 1,603:
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)
Line 1,632 ⟶ 1,634:
else
x = x->Right;
 
return y;
}
 
Node^ AfterEquals(T data)
{
Node^ y = Header;
Node^ x = Root;
 
while (x != nullptr)
{
Line 1,651 ⟶ 1,653:
x = x->Right;
}
 
return y;
}
 
SetNode<T>^ Add(T data, bool exist)
{
Node^ root = Root;
 
if (root == nullptr)
{
Line 1,673 ⟶ 1,675:
{
int compare = TComparer->Compare(data, static_cast<SetNode<T>^>(root)->Data);
 
if (compare == 0) // Item Exists
{
Line 1,686 ⟶ 1,688:
throw gcnew EntryAlreadyExistsException();
}
 
else if (compare < 0)
{
Line 1,701 ⟶ 1,703:
}
}
 
else
{
Line 1,719 ⟶ 1,721:
}
}
 
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)
{
Line 1,747 ⟶ 1,749:
i.MovePrevious();
SetEntry<T> start(begin); start.MovePrevious();
 
while (i != start)
{
Line 1,759 ⟶ 1,761:
return Count;
}
 
Node^ Before(T data)
{
Node^ y = Header;
Node^ x = Root;
 
while (x != nullptr)
if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) <= 0)
Line 1,770 ⟶ 1,772:
else
{ y = x; x = x->Right; }
 
return y;
}
 
Node^ BeforeEquals(T data)
{
Node^ y = Header;
Node^ x = Root;
 
while (x != nullptr)
{
Line 1,789 ⟶ 1,791:
{ y = x; x = x->Right; }
}
 
return y;
}
 
void Bounds()
{
Line 1,798 ⟶ 1,800:
RightMost = GetLast();
}
 
void Copy(SetNode<T>^ CopyRoot)
{
Line 1,809 ⟶ 1,811:
}
}
 
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
{
Line 1,838 ⟶ 1,840:
}
}
 
Node^ GetLast()
{
if (Root == nullptr)
return Header;
 
else
{
Line 1,851 ⟶ 1,853:
}
}
 
void Import(SetNode<T>^ n)
{
if (n != nullptr) ImportTree(n);
}
 
void ImportTree(SetNode<T>^ n)
{
Line 1,863 ⟶ 1,865:
if (n->Right != nullptr) ImportTree((SetNode<T>^)n->Right);
}
 
void Notify(SetNode<T>^ root)
{
Line 1,870 ⟶ 1,872:
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)
{
Line 1,886 ⟶ 1,888:
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; }
Line 1,903 ⟶ 1,905:
{
Node^ p = PreviousItem(root);
 
if (p->IsHeader)
{ LeftMost = Header; RightMost = Header; }
Line 1,909 ⟶ 1,911:
RightMost = p;
}
 
if (root->Left == nullptr)
{
Line 1,918 ⟶ 1,920:
else
Parent->Right = root->Right;
 
if (root->Right != nullptr) root->Right->Parent = Parent;
}
Line 1,929 ⟶ 1,931:
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)
{
Line 1,951 ⟶ 1,953:
i = iter._Node;
}
 
return count;
}
}
 
void Update(SetNode<T>^ Node, T value)
{
Line 1,963 ⟶ 1,965:
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,
Line 2,013 ⟶ 2,015:
System::Collections::Generic::IComparer<T>^ TComparer = R->TComparer;
ISharp::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)
{
Line 2,025 ⟶ 2,027:
{
int order = TComparer->Compare(first1.Value, first2.Value);
 
if (order < 0)
{
Line 2,031 ⟶ 2,033:
first1.MoveNext();
}
 
else if (order > 0)
{
Line 2,037 ⟶ 2,039:
first2.MoveNext();
}
 
else
{
Line 2,056 ⟶ 2,058:
}
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
{
Line 2,076 ⟶ 2,078:
}
return;
 
case SetOperation::SymmetricDifference:
while (first1 != last1 && first2 != last2)
{
int order = TComparer->Compare(first1.Value, first2.Value);
 
if (order < 0)
{
Line 2,087 ⟶ 2,089:
first1.MoveNext();
}
 
else if (order > 0)
{
Line 2,093 ⟶ 2,095:
first2.MoveNext();
}
 
else
{ first1.MoveNext(); first2.MoveNext(); }
}
 
while (first1 != last1)
{
Line 2,103 ⟶ 2,105:
first1.MoveNext();
}
 
while (first2 != last2)
{
Line 2,110 ⟶ 2,112:
}
return;
 
case SetOperation::Difference:
while (first1 != last1 && first2 != last2)
{
int order = TComparer->Compare(first1.Value, first2.Value);
 
if (order < 0)
{
Line 2,121 ⟶ 2,123:
first1.MoveNext();
}
 
else if (order > 0)
{
Line 2,128 ⟶ 2,130:
first2.MoveNext();
}
 
else
{ first1.MoveNext(); first2.MoveNext(); }
}
 
while (first1 != last1)
{
Line 2,140 ⟶ 2,142:
return;
}
 
throw gcnew InvalidSetOperationException();
}
 
static Boolean CheckSets(Set<T>^ A,
Set<T>^ B,
Line 2,149 ⟶ 2,151:
{
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)
{
Line 2,169 ⟶ 2,171:
{ equals = false; break; }
}
 
if (equals)
{
Line 2,175 ⟶ 2,177:
if (first2 != last2) equals = false;
}
 
if (operation == SetOperation::Equality)
return equals;
Line 2,181 ⟶ 2,183:
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;
Line 2,210 ⟶ 2,212:
}
}
 
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)
{
Line 2,234 ⟶ 2,236:
return Result;
}
 
if (first1 != last1) return 1;
if (first2 != last2) return -1;
 
return 0;
}
};
 
}
 
using namespace ISharp;
 
int main(array<System::String ^> ^args)
{
Set<int> S = gcnew Set<int>(1, 3, 5 , 6, 7, 9);
Console::WriteLine(S.ToString());
return 0;
}
}</lang>
</lang>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/269041"