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