Example of C Smart Differencer Output
This page contains an example of the output generated by SD's
C Smart Differencer tool
when
applied to an original file
and an updated version of the same file.
Output from C Smart Differencer on original and updated file
This page contains an example of the output generated by SD's
C Smart Differencer tool.
Observe that the Smart Differencer produces only 45 lines of output,
compared to diff's 228 lines of output; the programmer simply has to look at less code.
Note the added precision of Smart Differencer output:
precise deltas with line and column number (l.c) ranges, rather than simple line deltas.
It notes renamed variables ('oldname' ->'newname') across a block (lines 116-355) just once
rather than report many small blocks of code in which the variable name has simply changed as diff does.
(With enough information, the Smart Difference will note that a name changed has occurred consistently
throughout out a scope, and therefore isn't an intereseting difference).
Notice that source code formatting (different line breaks in line 58-87) don't fool the smart differencer,
that changed comments don't confuse it, that radix changes on the numeric constant (line 1060)
are ignored, and that different but equivalent escape sequences in strings are ignored (lines 1082-1150).
Finally, a block is code noted as deleted/added (moved) at line 1060.
For comparison, see deltas generated from a standard diff tool.
Insert 4.1-4.23 >#include <sys\timeb.h> Rename 116.3-355.38 to 114.3-353.42 with 'Dummy'~>'DummyNode' Substitute 886.8-886.42 by 884.8-884.39 < SplayTreeInsertProbableNonDuplicate > SplayTreeInsertProbableDuplicate Insert 887.3-896.4 moving 897.3-906.4 to 887.3-896.4 > NodeT* NewNodeP; > NewNodeP=SplayTreeAccess(SplayTreeP,Key); > if (NewNodeP!=NIL) > return NewNodeP; // fast/frequent exit > { // Create new node and insert into tree > NewNodeP=new(NodeT); > NewNodeP->Key=Key; > SplayTreeInsert(SplayTreeP,NewNodeP); > return NewNodeP; > }; Delete 891.4-891.59 moving 891.4-891.59 to 904.4-904.59 < return SplayTreeInsertProbableDuplicate(SplayTreeP,Key); Substitute 894.8-894.39 by 899.8-899.42 < SplayTreeInsertProbableDuplicate > SplayTreeInsertProbableNonDuplicate Insert 904.4-904.59 moving 891.4-891.59 to 904.4-904.59 > return SplayTreeInsertProbableDuplicate(SplayTreeP,Key); Delete 897.3-906.4 moving 897.3-906.4 to 887.3-896.4 < NodeT* NewNodeP; < NewNodeP=SplayTreeAccess(SplayTreeP,Key); < if (NewNodeP!=NIL) < return NewNodeP; // fast/frequent exit < { // Create new node and insert into tree < NewNodeP=new(NodeT); < NewNodeP->Key=Key; < SplayTreeInsert(SplayTreeP,NewNodeP); < return NewNodeP; < }; Insert 1060.1-1063.2 moving 1067.1-1070.2 to 1060.1-1063.2 >unsigned int myrand(range) >{ seed=(seed+1)*3141597237; > return seed%range; >}; Delete 1067.1-1070.2 moving 1067.1-1070.2 to 1060.1-1063.2 <unsigned int myrand(range) <{ seed=(seed+1)*3141597237; < return seed%range; <};
Output from Cygwin diff tool
Note absence of column number data, absence of identifier rename detection, failure
to recognize reformatted code as unchanged (diff thinks the block of code
at lines 58-87 has changed), failure to notice same numeric
values in the face radix change (line 1060, and failure to ignore comments.
See the actual deltas generated from C Smart Differencer.
See original file and updated version of the same file.
3a4 > #include <sys\timeb.h> 58,61c59,63 < unsigned int SplayTreeSanityNodeTest < (NodeT* parentP,NodeT* subtreeP,KeyT MinKey, // Key must be >= this < KeyT MaxKey, // Key must be < this < unsigned int mass) --- > unsigned int SplayTreeSanityNodeTest(NodeT* parentP, > NodeT* subtreeP, > KeyT MinKey, // Key must be >= this > KeyT MaxKey, // Key must be < this > unsigned int mass) 68,75c70,73 < if (mass==0) < return 0; // oops, we have a bigger-than-expected subtree here < if (subtreeP->parentP!=parentP) < return 0; // bad parent pointer < if (subtreeP->Key<MinKey<) < return 0; // bad key value < if (subtreeP->Key>MaxKey) < return 0; // bad key value --- > if (mass==0) return 0; // oops, we have a bigger-than-expected subtree here > if (subtreeP->parentP!=parentP) return 0; // bad parent pointer > if (subtreeP->Key<MinKey) return 0; // bad key value > if (subtreeP->Key>MaxKey) return 0; // bad key value 79c77,78 < subtreeP->leftP,MinKey, --- > subtreeP->leftP, > MinKey, 86,87c85 < else { < RightSubtreeMass=SplayTreeSanityNodeTest(subtreeP, /* new parent */ --- > else { RightSubtreeMass=SplayTreeSanityNodeTest(subtreeP, // new parent 120c118 < NodeT Dummy; --- > NodeT DummyNode; 129c127 < { /* We use Dummy to hold Lroot and Rroot in its left and right children. --- > { /* We use DummyNode to hold Lroot and Rroot in its left and right children. 131,132c129,130 < LeftSubtreeRightmostNodeP=&Dummy; // set to rightmost son of empty L < RightSubtreeLeftmostNodeP=&Dummy; // set to leftmost son of empty R --- > LeftSubtreeRightmostNodeP=&DummyNode; // set to rightmost son of empty L > RightSubtreeLeftmostNodeP=&DummyNode; // set to leftmost son of empty R 155,160c153,158 < UnsplitMSubtreeP->leftP=Dummy.rightP; < UnsplitMSubtreeP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=UnsplitMSubtreeP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=UnsplitMSubtreeP; --- > UnsplitMSubtreeP->leftP=DummyNode.rightP; > UnsplitMSubtreeP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=UnsplitMSubtreeP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=UnsplitMSubtreeP; 181,186c179,184 < UnsplitMSubtreeP->leftP=Dummy.rightP; < UnsplitMSubtreeP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=UnsplitMSubtreeP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=UnsplitMSubtreeP; --- > UnsplitMSubtreeP->leftP=DummyNode.rightP; > UnsplitMSubtreeP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=UnsplitMSubtreeP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=UnsplitMSubtreeP; 236,241c234,239 < NextChildP->leftP=Dummy.rightP; < NextChildP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=NextChildP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=NextChildP; --- > NextChildP->leftP=DummyNode.rightP; > NextChildP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=NextChildP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=NextChildP; 255,260c253,258 < NextChildP->leftP=Dummy.rightP; < NextChildP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=NextChildP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=NextChildP; --- > NextChildP->leftP=DummyNode.rightP; > NextChildP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=NextChildP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=NextChildP; 276,281c274,279 < UnsplitMSubtreeP->leftP=Dummy.rightP; < UnsplitMSubtreeP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=UnsplitMSubtreeP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=UnsplitMSubtreeP; --- > UnsplitMSubtreeP->leftP=DummyNode.rightP; > UnsplitMSubtreeP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=UnsplitMSubtreeP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=UnsplitMSubtreeP; 331,336c329,334 < NextChildP->leftP=Dummy.rightP; < NextChildP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=NextChildP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=NextChildP; --- > NextChildP->leftP=DummyNode.rightP; > NextChildP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=NextChildP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=NextChildP; 350,355c348,353 < NextChildP->leftP=Dummy.rightP; < NextChildP->rightP=Dummy.leftP; < if (Dummy.leftP!=NIL) < Dummy.leftP->parentP=NextChildP; < if (Dummy.rightP!=NIL) < Dummy.rightP->parentP=NextChildP; --- > NextChildP->leftP=DummyNode.rightP; > NextChildP->rightP=DummyNode.leftP; > if (DummyNode.leftP!=NIL) > DummyNode.leftP->parentP=NextChildP; > if (DummyNode.rightP!=NIL) > DummyNode.rightP->parentP=NextChildP; 886,893d883 < NodeT* SplayTreeInsertProbableNonDuplicate(SplayTreeT* SplayTreeP, KeyT Key) < // Insert a node according to its key into a splay tree, assuming it is probably in tree < // Returns pointer to node found/inserted < { // Bad implementation. A better implementation would split tree going down, < // mich like SplayTreeInsert does, and recover if it finds the desired node. < return SplayTreeInsertProbableDuplicate(SplayTreeP,Key); < }; < 908a899,906 > NodeT* SplayTreeInsertProbableNonDuplicate(SplayTreeT* SplayTreeP, KeyT Key) > // Insert a node according to its key into a splay tree, assuming it is probably in tree > // Returns pointer to node found/inserted > { // Bad implementation. A better implementation would split tree going down, > // mich like SplayTreeInsert does, and recover if it finds the desired node. > return SplayTreeInsertProbableDuplicate(SplayTreeP,Key); > }; > 1060,1065c1058 < #define TestSize 0x4E20 < < void ComplainIfInsane(SplayTreeT* SplayTreeP,KeyT k) < { if (!SplayTreeSanity(SplayTreeP)) < printf("Splay tree insert failure on key %d\012",k); < }; --- > #define TestSize 20000 1071a1065,1070 > void ComplainIfInsane(SplayTreeT* SplayTreeP,KeyT k) > { if (!SplayTreeSanity(SplayTreeP)) > printf("Splay tree insert failure on key %d\n",k); > }; > > 1082c1081 < printf("Running Splay Tree test...\012"); --- > printf("Running Splay Tree test...\n"); 1084c1083 < { printf("Test inserting small set of values\012"); --- > { printf("Test inserting small set of values\n"); 1116c1115 < { printf("Test increasing access of small set of inserted values\012"); --- > { printf("Test increasing access of small set of inserted values\n"); 1119c1118 < printf("Accessing value %d\012",k);; --- > printf("Accessing value %d\n",k);; 1122c1121 < printf("Splay tree lookup failure on iteration %d with key %d\012",i,k); --- > printf("Splay tree lookup failure on iteration %d with key %d\n",i,k); 1126c1125 < { printf("Test deleting minimum values keys for small set\012"); --- > { printf("Test deleting minimum values keys for small set\n"); 1129c1128 < printf("Deleting minimum key %d\012",i);; --- > printf("Deleting minimum key %d\n",i);; 1132c1131 < printf("Splay tree delete minimum deleted wrong key %d on iteration %d with key %d\012", --- > printf("Splay tree delete minimum deleted wrong key %d on iteration %d with key %d\n", 1135c1134 < printf("Splay tree DeleteMinimum failure on iteration %d with key %d\012",i,k); --- > printf("Splay tree DeleteMinimum failure on iteration %d with key %d\n",i,k); 1142c1141 < { printf("Test insert in increasing order\012"); --- > { printf("Test insert in increasing order\n"); 1150c1149 < printf("Inserting value %d\012",k); --- > printf("Inserting value %d\n",k);
Source Code before Change
This code is a splay tree procedure, taken from SD's internal tools.
A number of cleanups were made from before and after.
See updated version of the same file.
#include <windows.h> #include <time.h> #include <sys\types.h> #include <io.h> #include <stdlib.h> #include <memory.h> // access to memcpy #include <errno.h> #include <stdio.h> #define new(type) malloc(sizeof(type)) #define true 1 #define false 0 /* ...Stupid language... */ #define NIL 0 #define Infinity ((unsigned int)-1) typedef unsigned int KeyT; #define CollectStatistics 1 #if CollectStatistics unsigned int InsertCompareCount=0; unsigned int AccessCompareCount=0; #endif #define NodeT struct NodeType struct NodeType // A node in a Splay Tree { NodeT* parentP; // points to parent node KeyT Key; NodeT* leftP; // points to nodes with smaller or equal keys NodeT* rightP; // points to nodes with larger keys //ContentT Content; }; #define SplayTreeT struct SplayTreeType struct SplayTreeType // A Splay Tree { NodeT* rootP; // root of Splay tree unsigned int mass; // number of nodes in splay tree }; SplayTreeT* newSplayTreeT() // Returns pointer to new splay tree { SplayTreeT* SplayTreeP; SplayTreeP=new(SplayTreeT); SplayTreeP->rootP=NIL; SplayTreeP->mass=0; return SplayTreeP; }; NodeT* newNodeT(KeyT NewKey) { NodeT* NodeP; NodeP=new(NodeT); NodeP->Key=NewKey; return NodeP; }; unsigned int SplayTreeSanityNodeTest (NodeT* parentP,NodeT* subtreeP,KeyT MinKey, // Key must be >= this KeyT MaxKey, // Key must be < this unsigned int mass) // Check that subtreeP is a legal subree of parentP, with fewer than mass nodes // Returns nonzero count of subtree mass if subtree is valid. // Returns 0 if subtree invalid. { // Assert: subtreeP!=NIL unsigned int LeftSubtreeMass; unsigned int RightSubtreeMass; if (mass==0) return 0; // oops, we have a bigger-than-expected subtree here if (subtreeP->parentP!=parentP) return 0; // bad parent pointer if (subtreeP->Key<MinKey) return 0; // bad key value if (subtreeP->Key>MaxKey) return 0; // bad key value if (subtreeP->leftP==NIL) LeftSubtreeMass=0; else { LeftSubtreeMass=SplayTreeSanityNodeTest(subtreeP, // new parent subtreeP->leftP,MinKey, subtreeP->Key, // all keys less or equal to this mass-1); if (LeftSubtreeMass==0) return 0; // propagate error } if (subtreeP->rightP==NIL) RightSubtreeMass=0; else { RightSubtreeMass=SplayTreeSanityNodeTest(subtreeP, /* new parent */ subtreeP->rightP, subtreeP->Key+1, // all keys less or equal to this MaxKey, mass-LeftSubtreeMass-1); if (RightSubtreeMass==0) return 0; // propagate error }; return 1+LeftSubtreeMass+RightSubtreeMass; }; boolean SplayTreeSanity(SplayTreeT* SplayTreeP) // Tests sanity of splay tree { unsigned int subtreeMass; if (SplayTreeP==NIL) return false; if (SplayTreeP->rootP==NIL) return (SplayTreeP->mass==0); subtreeMass=SplayTreeSanityNodeTest(NIL, // parent, SplayTreeP->rootP, 0, // Min key Infinity, // Max key SplayTreeP->mass); if (subtreeMass!=SplayTreeP->mass) return false; return true; }; NodeT* SplayTreeAccess(SplayTreeT* SplayTreeP,KeyT DesiredKey) // Find a node in splay tree having given key, and splay the tree at that node // (This procedure can be used to splay for Key max/min by supplying +-KeyInfinity) // Returns NIL if no such node { NodeT* LeftSubtreeRightmostNodeP; // rightmost node L in left subtree during top-down splay NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP NodeT Dummy; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay if (UnsplitMSubtreeP==NIL) { // Empty tree, Key can't be found return NIL; }; // else check for key at root of non-empty tree if (UnsplitMSubtreeP->Key == DesiredKey) return UnsplitMSubtreeP; // found node with key, return without dirtying cache { /* We use Dummy to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ LeftSubtreeRightmostNodeP=&Dummy; // set to rightmost son of empty L RightSubtreeLeftmostNodeP=&Dummy; // set to leftmost son of empty R }; // Search for node having Key, performing top-down splay // make initial direction decision #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->Key > DesiredKey) goto SEARCHLEFT; else goto SEARCHRIGHT; MATCHKEY: // See if key matches if (UnsplitMSubtreeP->Key == DesiredKey) { // Found desired key!. // Case4: finish by splaying at M RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP->leftP; if (UnsplitMSubtreeP->leftP!=NIL) UnsplitMSubtreeP->leftP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=Dummy.rightP; UnsplitMSubtreeP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=UnsplitMSubtreeP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=UnsplitMSubtreeP; return UnsplitMSubtreeP; // the node where we found the answer }; #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->Key > DesiredKey) goto SEARCHLEFT; else goto SEARCHRIGHT; SEARCHLEFT: // assert: UnsplitMSubtreeP->Key > DesiredKey NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=Dummy.rightP; UnsplitMSubtreeP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=UnsplitMSubtreeP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1LEFTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key < DesiredKey) { if (NextChildP->rightP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key > DesiredKey if (NextChildP->leftP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; }; CASE1LEFTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=Dummy.rightP; NextChildP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=NextChildP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NextChildP; CASE1LEFTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=Dummy.rightP; NextChildP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=NextChildP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; SEARCHRIGHT: // assert: UnsplitMSubtreeP->Key < DesiredKey NextChildP=UnsplitMSubtreeP->rightP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP->leftP; if (UnsplitMSubtreeP->leftP!=NIL) UnsplitMSubtreeP->leftP->parentP=LeftSubtreeRightmostNodeP; RightSubtreeLeftmostNodeP->leftP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=Dummy.rightP; UnsplitMSubtreeP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=UnsplitMSubtreeP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1RIGHTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key > DesiredKey) { if (NextChildP->leftP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key < DesiredKey if (NextChildP->rightP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; }; CASE1RIGHTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=RightSubtreeLeftmostNodeP; NextChildP->leftP=Dummy.rightP; NextChildP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=NextChildP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NextChildP; CASE1RIGHTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=RightSubtreeLeftmostNodeP; NextChildP->leftP=Dummy.rightP; NextChildP->rightP=Dummy.leftP; if (Dummy.leftP!=NIL) Dummy.leftP->parentP=NextChildP; if (Dummy.rightP!=NIL) Dummy.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; }; NodeT* SplayTreeDelete(SplayTreeT* SplayTreeP,KeyT DesiredKey) // INCOMPLETE IMPLEMENTATION! // Find a node in splay tree having given key, and delete that node // Returns NIL if no such node { NodeT* LeftSubtreeRightmostNodeP; // rightmost node L in left subtree during top-down splay NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP NodeT DummyNode; NodeT* ResultNodeP; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay if (UnsplitMSubtreeP==NIL) { // Empty tree, Key can't be found return NIL; }; { /* We use DummyNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ LeftSubtreeRightmostNodeP=&DummyNode; // set to rightmost son of empty L RightSubtreeLeftmostNodeP=&DummyNode; // set to leftmost son of empty R }; MATCHKEY: // See if key matches if (UnsplitMSubtreeP->Key == DesiredKey) { // Found node with desired key! ResultNodeP=UnsplitMSubtreeP; // remember desired node goto FOUNDKEY; } #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->Key > DesiredKey) goto SEARCHLEFT; else goto SEARCHRIGHT; SEARCHLEFT: // assert: UnsplitMSubtreeP->Key > DesiredKey NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1LEFTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key < DesiredKey) { if (NextChildP->rightP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key > DesiredKey if (NextChildP->leftP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; }; CASE1LEFTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey // Case 1 ResultNodeP=NextChildP; // remember node to delete RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; goto FOUNDKEY; CASE1LEFTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; SEARCHRIGHT: // assert: UnsplitMSubtreeP->Key < DesiredKey NextChildP=UnsplitMSubtreeP->rightP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP->leftP; if (UnsplitMSubtreeP->leftP!=NIL) UnsplitMSubtreeP->leftP->parentP=LeftSubtreeRightmostNodeP; RightSubtreeLeftmostNodeP->leftP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1RIGHTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key > DesiredKey) { if (NextChildP->leftP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key < DesiredKey if (NextChildP->rightP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; }; CASE1RIGHTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey ResultNodeP=NextChildP; // remember node to delete LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; goto FOUNDKEY; CASE1RIGHTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=RightSubtreeLeftmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; FOUNDKEY: SplayTreeP->mass--; // since we will delete this node if (ResultNodeP->leftP==NIL) { if (ResultNodeP->rightP==NIL) { // Desired node has no children. // Reassemble tree using just L and R. RightSubtreeLeftmostNodeP->leftP=NIL; // cauterize R LeftSubtreeRightmostNodeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=LeftSubtreeRightmostNodeP; SplayTreeP->rootP=DummyNode.rightP; return ResultNodeP; } else { // Desired node has only right son UnsplitMSubtreeP=ResultNodeP->rightP; // ResultNodeP->rightP=NIL; goto SPLAYLEFTTOLEAF; }; } else { // ResultNodeP->leftP!=NIL) if (ResultNodeP->rightP==NIL) { // Desired node has only left son UnsplitMSubtreeP=ResultNodeP->leftP; goto SPLAYLEFTTOLEAF; } else { // Desired node has both sons // INCOMPLETE! Splay both children... }; }; SPLAYLEFTTOLEAF: ; // splay leftmost leaf #if CollectStatistics AccessCompareCount++; // we effectively compare, and discover desired key is to left... #endif // assert: UnsplitMSubtreeP->Key > "DesiredKey" NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Can't go futher left // Finalize2: RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return ResultNodeP; }; #if CollectStatistics AccessCompareCount++; // we effectively compare, and discover desired key is to left... #endif // Assert: NextChildP->Key > DesiredKey if (NextChildP->leftP!=NIL) { // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto SPLAYLEFTTOLEAF; } // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == Minimum key // Treat like Case 1 final. RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return ResultNodeP; }; NodeT* SplayTreeDeleteMinimum(SplayTreeT* SplayTreeP) // Find a node in splay tree having least key, and delete that node // Returns NIL if no such node { NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP NodeT DummyNode; NodeT* ResultNodeP; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay if (UnsplitMSubtreeP==NIL) { // Empty tree, Key can't be found return NIL; }; { /* We use DummyNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ RightSubtreeLeftmostNodeP=&DummyNode; // set to leftmost son of empty R }; MATCHKEY: ; // See if found minimum key node #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->leftP == NIL) { // Found node with desired key! ResultNodeP=UnsplitMSubtreeP; // remember desired node goto FOUNDKEY; }; // SEARCHLEFT: // assert: UnsplitMSubtreeP->Key > DesiredKey NextChildP=UnsplitMSubtreeP->leftP; #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->leftP == NIL) goto CASE1LEFTSUCCESS; // Case 1: Zig case, found desired key { // Assert: NextChildP->Key > DesiredKey // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; CASE1LEFTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey // Case 1 ResultNodeP=NextChildP; // remember node to delete RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; goto FOUNDKEY; FOUNDKEY: SplayTreeP->mass--; // since we will delete this node // Assert: (ResultNodeP->leftP==NIL) UnsplitMSubtreeP=ResultNodeP->rightP; RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; if (UnsplitMSubtreeP!=NIL) UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; SplayTreeP->rootP=DummyNode.leftP; if (SplayTreeP->rootP!=NIL) SplayTreeP->rootP->parentP=NIL; return ResultNodeP; }; void SplayTreeInsert(SplayTreeT* SplayTreeP,NodeT* NewNodeP) // Insert a node according to its key into a splay tree // No duplicates allowed! // (This leaves NewNodeP as root of splay tree) { NodeT* LeftSubtreeRightmostNodeP; // rightmost node L in left subtree during top-down splay NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP KeyT NewNodeKey; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay SplayTreeP->rootP=NewNodeP; // new node becomes root of tree SplayTreeP->mass++; if (UnsplitMSubtreeP==NIL) { // Insert NewNode into empty tree NewNodeP->leftP=NIL; // mark node as having no children NewNodeP->rightP=NIL; NewNodeP->parentP=NIL; // for cleanliness return; }; // else insert NewNode into non-empty tree NewNodeKey=NewNodeP->Key; // extract key to use for insertion { /* We use NewNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ LeftSubtreeRightmostNodeP=NewNodeP; // set to rightmost son of empty L RightSubtreeLeftmostNodeP=NewNodeP; // set to leftmost son of empty R }; /* This procedure essentially does insert(i,t) by carrying out split(i,t), whose logic is just like top-down splay, but but we don't bother forming final splay tree */ // make initial direction decision #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; SEARCHLEFT: // assert: UnsplitMSubtreeP->Key >= NewNodeKey NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Case4: finish split at M (to allow final insert) RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; goto DONE; } #if CollectStatistics InsertCompareCount++; #endif if (NextChildP->Key < NewNodeKey) { // Case 3: zig-zag case RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; if (UnsplitMSubtreeP==NIL) { RightSubtreeLeftmostNodeP->leftP=NIL; goto DONE; }; #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; } else { // Assert: NextChildP->Key >= NewNodeKey // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP==NIL) { LeftSubtreeRightmostNodeP->rightP=NIL; goto DONE; } if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; }; SEARCHRIGHT: // assert: UnsplitMSubtreeP->Key < NewNodeKey NextChildP=UnsplitMSubtreeP->rightP; if (NextChildP==NIL) { // case 4: finish split at M (to allow final insert) LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; RightSubtreeLeftmostNodeP->leftP=NIL; goto DONE; }; #if CollectStatistics InsertCompareCount++; #endif if (NextChildP->Key >= NewNodeKey) { // Case 3: zig-zag case LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; if (UnsplitMSubtreeP==NIL) { LeftSubtreeRightmostNodeP->rightP=NIL; goto DONE; }; #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; } else { // Assert: NextChildP->Key < NewNodeKey // Case 2: zig-zig case UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; if (UnsplitMSubtreeP==NIL) { RightSubtreeLeftmostNodeP->leftP=NIL; goto DONE; } #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; }; DONE: // Swap subtrees of new node to complete. UnsplitMSubtreeP=NewNodeP->leftP; NewNodeP->leftP=NewNodeP->rightP; NewNodeP->rightP=UnsplitMSubtreeP; if (NewNodeP->leftP!=NIL) NewNodeP->leftP->parentP=NewNodeP; if (NewNodeP->rightP!=NIL) NewNodeP->rightP->parentP=NewNodeP; NewNodeP->parentP=NIL; // mark parent with null pointer return; }; NodeT* SplayTreeInsertProbableNonDuplicate(SplayTreeT* SplayTreeP, KeyT Key) // Insert a node according to its key into a splay tree, assuming it is probably in tree // Returns pointer to node found/inserted { // Bad implementation. A better implementation would split tree going down, // mich like SplayTreeInsert does, and recover if it finds the desired node. return SplayTreeInsertProbableDuplicate(SplayTreeP,Key); }; NodeT* SplayTreeInsertProbableDuplicate(SplayTreeT* SplayTreeP, KeyT Key) // Insert a node according to its key into a splay tree, assuming it is probably in tree // Returns pointer to node found/inserted { NodeT* NewNodeP; NewNodeP=SplayTreeAccess(SplayTreeP,Key); if (NewNodeP!=NIL) return NewNodeP; // fast/frequent exit { // Create new node and insert into tree NewNodeP=new(NodeT); NewNodeP->Key=Key; SplayTreeInsert(SplayTreeP,NewNodeP); return NewNodeP; }; }; /* Splay tree code Operations: access(i,t): if i is in tree, return pointer to i, else null Procedure: Find i, then splay tree at i. If i not in tree, splay last node accessed looking for i. join(a,b): Return tree formed by combining tree a and tree b. Assumes every item in tree a has keys less than items in b. Procedure: Splay largest item in a, then add b as right child of root of a. split (i,t): Split tree t, containing i, into two trees: "a", containing all items with keys less or equal to i, and b, containing all items with key greater than i. Procedure: Perform access(i,t), then split tree at root insert(i,t): insert i in tree t Procedure: Perform split (i,t), then make i root of two trees returned by split delete(i,t): delete i from tree t Procedure: Perform access(i,t) then perform join on t's subtrees. Top down splay/split procedure. Keep 3 trees: L, M, R, where all keys in L are less than keys in M, and all keys in M are less than keys in R. (We are searching down a tree M, and inspecting the keys of M and possibly an M-child Y; assume left=children have smaller keys than right children.) Capital letter represent nodes for which algorithm holds explicit pointers. Lsubtree and Rsubtrees each require *two* pointers: one for Lroot and one for rightmost son, L, of Lroot one for Rroot and one for leftmost son, R, of Rroot Case 1: Y is the node we are splaying (Y matches key, or a or b is null) L M R L Y R L M R L Y R / / \ \ / / \ / \ / / \ \ / \ / \ \ Y c ==> a b M OR c Y ==> M b a / \ \ / \ / a b c b a c (this is always followed by Case 4) (this is always followed by case 4) Y Y / \ / \ for splay ==> L R L R / \ / \ / \ / \ a M M a / \ / \ b c c b Case 2: (zig-zig) The node we are splaying is in the subtree rooted at X L M R L X R L M R L X R / / \ \ / / \ / \ / / \ \ / \ / \ \ Y d ==> a b Y OR d Y ==> Y b a / \ \ / \ / X c M c X M / \ / \ / \ / \ a b c d b a d c Case 3: (zig-zag) The node we are splaying is in the subtree rooted at X L M R L X R L M R L X R / / \ \ / \ / \ / \ / / \ \ / \ / \ / \ Y d ==> Y b c M OR d Y ==> M c b Y / \ / \ / \ / \ a X a d X a d a / \ / \ b c c b Case 4: (last step) for splay: M is the node we wish to splay: L M R M / / \ \ / \ Y b ==> L R Note: L,R here represents Lroot/Rroot and L,R / \ / \ Y b Case 4: (last step) for split: M is the node we wish to splay: L M R L R / / \ \ / \ / \ Y b ==> Y M \ b ---------------------------------------------------------------------------------- To delete a node: move down tree performing rotates until desired node M found. One of 3 cases occurs: 1) M has no children, build final result: L M R L / \ / \ ==> R \ 2a) M has left child, but no right child: L M R L Y R / / \ ==> / \ \ Y goto finalize2; 2b) M has no left child, but has right child L M R L Y R / \ \ ==> / \ Y goto finalize2: finalize2) Finding way to leftmost node with null son. rotating zig-zig as required, and then perform the following reassembly: L Y R Y / \ \ / \ b ==> L R / b 3) M has both children: L M R / / \ \ Y b / \ ... / bmin Then delete bmin from b giving b`, and reassemble as follows: bmin / \ ==> L R / \ / \ Y b' ----------------------------------------------------------------------------------- */ unsigned int seed=0; #define TestSize 0x4E20 void ComplainIfInsane(SplayTreeT* SplayTreeP,KeyT k) { if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure on key %d\012",k); }; unsigned int myrand(range) { seed=(seed+1)*3141597237; return seed%range; }; void TestSplayTree() // Test Splay Tree for correct operation { SplayTreeT* SplayTreeP; NodeT* NodeP; NodeT* minNodeP; unsigned int i; unsigned int slot; KeyT k; KeyT KeyArray[TestSize]; printf("Running Splay Tree test...\012"); { printf("Test inserting small set of values\012"); SplayTreeP=newSplayTreeT(); { NodeP=newNodeT(1); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,1); }; { NodeP=newNodeT(2); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,2); }; { NodeP=newNodeT(3); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,3); }; { NodeP=newNodeT(4); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,4); }; { NodeP=newNodeT(5); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,5); }; { NodeP=newNodeT(6); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,6); }; { NodeP=newNodeT(0); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,0); }; }; { printf("Test increasing access of small set of inserted values\012"); for (i=0;i<6;i++) { k=i; printf("Accessing value %d\012",k);; SplayTreeAccess(SplayTreeP,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree lookup failure on iteration %d with key %d\012",i,k); }; }; { printf("Test deleting minimum values keys for small set\012"); for (i=0;i<=6;i++) { k=i; printf("Deleting minimum key %d\012",i);; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP->Key!=k) printf("Splay tree delete minimum deleted wrong key %d on iteration %d with key %d\012", minNodeP->Key,i,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree DeleteMinimum failure on iteration %d with key %d\012",i,k); }; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP!=NIL) printf("Splay tree delete min failure when empty"); }; { printf("Test insert in increasing order\012"); #if CollectStatistics InsertCompareCount=0; #endif SplayTreeP=newSplayTreeT(); for (i=1;i<TestSize;i++) { // Insert keys in increasing order k=i; printf("Inserting value %d\012",k); NodeP=newNodeT(k); SplayTreeInsert(SplayTreeP,NodeP); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure increasing keys %d\n",k); }; #if CollectStatistics printf("For %d inserts, there were %d compares.\n",TestSize,InsertCompareCount); #endif }; { printf("Test insert in decreasing order\n"); #if CollectStatistics InsertCompareCount=0; #endif SplayTreeP=newSplayTreeT(); for (i=1;i<TestSize;i++) { // Insert keys in increasing order k=TestSize-i; printf("Inserting value %d\n",k); NodeP=newNodeT(k); SplayTreeInsert(SplayTreeP,NodeP); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure decreasing keys %d\n",k); }; #if CollectStatistics printf("For %d inserts, there were %d compares.\n",TestSize,InsertCompareCount); #endif }; { printf("Test insert random key sequence\n"); #if CollectStatistics InsertCompareCount=0; #endif SplayTreeP=newSplayTreeT(); for (i=0;i<TestSize;i++) { // set up a dense set of keys KeyArray[i]=i; // set up a list of keys }; for (i=0;i<TestSize;i++) { // Now shuffle dense set of keys around slot=myrand(TestSize); k=KeyArray[slot]; // swap a pair of keys KeyArray[slot]=KeyArray[i]; KeyArray[i]=k; }; for (i=0;i<TestSize;i++) { k=KeyArray[i]; printf("Iteration %d inserting value %d\n",i,k); NodeP=newNodeT(k); // force duplicate keys SplayTreeInsert(SplayTreeP,NodeP); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure on iteration %d with key %d\n",i,k); }; #if CollectStatistics printf("For %d inserts, there were %d compares.\n",TestSize,InsertCompareCount); #endif }; { printf("Test increasing access of randomly inserted values\n"); #if CollectStatistics AccessCompareCount=0; #endif for (i=0;i<TestSize;i++) { k=i; printf("Accessing value %d\n",k); SplayTreeAccess(SplayTreeP,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree lookup failure on iteration %d with key %d\n",i,k); }; #if CollectStatistics printf("For %d linear accesses, there were %d compares.\n",TestSize,AccessCompareCount); #endif }; { printf("Test random access of randomly inserted values\n"); #if CollectStatistics AccessCompareCount=0; #endif for (i=0;i<TestSize;i++) { k=KeyArray[i]; printf("Iteration %d accessing value %d\n",i,k); SplayTreeAccess(SplayTreeP,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree lookup failure on iteration %d with key %d\n",i,k); }; #if CollectStatistics printf("For %d random accesses, there were %d compares.\n",TestSize,AccessCompareCount); #endif }; { printf("Test deleting minimum values keys from randomly accessed set\n"); #if CollectStatistics AccessCompareCount=0; #endif for (i=0;i<TestSize;i++) { k=i; printf("Deleting minimum key %d\n",i);; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP->Key!=k) printf("Splay tree delete minimum deleted wrong key %d on iteration %d with key %d\n", minNodeP->Key,i,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree DeleteMinimum failure on iteration %d with key %d\n",i,k); }; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP!=NIL) printf("Splay tree delete min failure when empty"); #if CollectStatistics printf("For %d deleteMin after random accesses, there were %d compares.\n",TestSize,AccessCompareCount); #endif }; }; void main() { TestSplayTree(); };
Source Code after Change
This code is that same file at the next checkin with a number of changes.
It is hard to see the differences by simply looking at the text, partly just from the sheer
size of it. This is why you want a diff tool of some kind.
See the actual deltas generated from C Smart Differencer.
For comparison, see deltas generated from a standard diff tool.
#include <windows.h> #include <time.h> #include <sys\types.h> #include <sys\timeb.h> #include <io.h> #include <stdlib.h> #include <memory.h> // access to memcpy #include <errno.h> #include <stdio.h> #define new(type) malloc(sizeof(type)) #define true 1 #define false 0 /* ...Stupid language... */ #define NIL 0 #define Infinity ((unsigned int)-1) typedef unsigned int KeyT; #define CollectStatistics 1 #if CollectStatistics unsigned int InsertCompareCount=0; unsigned int AccessCompareCount=0; #endif #define NodeT struct NodeType struct NodeType // A node in a Splay Tree { NodeT* parentP; // points to parent node KeyT Key; NodeT* leftP; // points to nodes with smaller or equal keys NodeT* rightP; // points to nodes with larger keys //ContentT Content; }; #define SplayTreeT struct SplayTreeType struct SplayTreeType // A Splay Tree { NodeT* rootP; // root of Splay tree unsigned int mass; // number of nodes in splay tree }; SplayTreeT* newSplayTreeT() // Returns pointer to new splay tree { SplayTreeT* SplayTreeP; SplayTreeP=new(SplayTreeT); SplayTreeP->rootP=NIL; SplayTreeP->mass=0; return SplayTreeP; }; NodeT* newNodeT(KeyT NewKey) { NodeT* NodeP; NodeP=new(NodeT); NodeP->Key=NewKey; return NodeP; }; unsigned int SplayTreeSanityNodeTest(NodeT* parentP, NodeT* subtreeP, KeyT MinKey, // Key must be >= this KeyT MaxKey, // Key must be < this unsigned int mass) // Check that subtreeP is a legal subree of parentP, with fewer than mass nodes // Returns nonzero count of subtree mass if subtree is valid. // Returns 0 if subtree invalid. { // Assert: subtreeP!=NIL unsigned int LeftSubtreeMass; unsigned int RightSubtreeMass; if (mass==0) return 0; // oops, we have a bigger-than-expected subtree here if (subtreeP->parentP!=parentP) return 0; // bad parent pointer if (subtreeP->Key<MinKey) return 0; // bad key value if (subtreeP->Key>MaxKey) return 0; // bad key value if (subtreeP->leftP==NIL) LeftSubtreeMass=0; else { LeftSubtreeMass=SplayTreeSanityNodeTest(subtreeP, // new parent subtreeP->leftP, MinKey, subtreeP->Key, // all keys less or equal to this mass-1); if (LeftSubtreeMass==0) return 0; // propagate error } if (subtreeP->rightP==NIL) RightSubtreeMass=0; else { RightSubtreeMass=SplayTreeSanityNodeTest(subtreeP, // new parent subtreeP->rightP, subtreeP->Key+1, // all keys less or equal to this MaxKey, mass-LeftSubtreeMass-1); if (RightSubtreeMass==0) return 0; // propagate error }; return 1+LeftSubtreeMass+RightSubtreeMass; }; boolean SplayTreeSanity(SplayTreeT* SplayTreeP) // Tests sanity of splay tree { unsigned int subtreeMass; if (SplayTreeP==NIL) return false; if (SplayTreeP->rootP==NIL) return (SplayTreeP->mass==0); subtreeMass=SplayTreeSanityNodeTest(NIL, // parent, SplayTreeP->rootP, 0, // Min key Infinity, // Max key SplayTreeP->mass); if (subtreeMass!=SplayTreeP->mass) return false; return true; }; NodeT* SplayTreeAccess(SplayTreeT* SplayTreeP,KeyT DesiredKey) // Find a node in splay tree having given key, and splay the tree at that node // (This procedure can be used to splay for Key max/min by supplying +-KeyInfinity) // Returns NIL if no such node { NodeT* LeftSubtreeRightmostNodeP; // rightmost node L in left subtree during top-down splay NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP NodeT DummyNode; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay if (UnsplitMSubtreeP==NIL) { // Empty tree, Key can't be found return NIL; }; // else check for key at root of non-empty tree if (UnsplitMSubtreeP->Key == DesiredKey) return UnsplitMSubtreeP; // found node with key, return without dirtying cache { /* We use DummyNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ LeftSubtreeRightmostNodeP=&DummyNode; // set to rightmost son of empty L RightSubtreeLeftmostNodeP=&DummyNode; // set to leftmost son of empty R }; // Search for node having Key, performing top-down splay // make initial direction decision #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->Key > DesiredKey) goto SEARCHLEFT; else goto SEARCHRIGHT; MATCHKEY: // See if key matches if (UnsplitMSubtreeP->Key == DesiredKey) { // Found desired key!. // Case4: finish by splaying at M RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP->leftP; if (UnsplitMSubtreeP->leftP!=NIL) UnsplitMSubtreeP->leftP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return UnsplitMSubtreeP; // the node where we found the answer }; #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->Key > DesiredKey) goto SEARCHLEFT; else goto SEARCHRIGHT; SEARCHLEFT: // assert: UnsplitMSubtreeP->Key > DesiredKey NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1LEFTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key < DesiredKey) { if (NextChildP->rightP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key > DesiredKey if (NextChildP->leftP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; }; CASE1LEFTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NextChildP; CASE1LEFTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; SEARCHRIGHT: // assert: UnsplitMSubtreeP->Key < DesiredKey NextChildP=UnsplitMSubtreeP->rightP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP->leftP; if (UnsplitMSubtreeP->leftP!=NIL) UnsplitMSubtreeP->leftP->parentP=LeftSubtreeRightmostNodeP; RightSubtreeLeftmostNodeP->leftP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1RIGHTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key > DesiredKey) { if (NextChildP->leftP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key < DesiredKey if (NextChildP->rightP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; }; CASE1RIGHTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=RightSubtreeLeftmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NextChildP; CASE1RIGHTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=RightSubtreeLeftmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; }; NodeT* SplayTreeDelete(SplayTreeT* SplayTreeP,KeyT DesiredKey) // INCOMPLETE IMPLEMENTATION! // Find a node in splay tree having given key, and delete that node // Returns NIL if no such node { NodeT* LeftSubtreeRightmostNodeP; // rightmost node L in left subtree during top-down splay NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP NodeT DummyNode; NodeT* ResultNodeP; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay if (UnsplitMSubtreeP==NIL) { // Empty tree, Key can't be found return NIL; }; { /* We use DummyNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ LeftSubtreeRightmostNodeP=&DummyNode; // set to rightmost son of empty L RightSubtreeLeftmostNodeP=&DummyNode; // set to leftmost son of empty R }; MATCHKEY: // See if key matches if (UnsplitMSubtreeP->Key == DesiredKey) { // Found node with desired key! ResultNodeP=UnsplitMSubtreeP; // remember desired node goto FOUNDKEY; } #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->Key > DesiredKey) goto SEARCHLEFT; else goto SEARCHRIGHT; SEARCHLEFT: // assert: UnsplitMSubtreeP->Key > DesiredKey NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1LEFTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key < DesiredKey) { if (NextChildP->rightP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key > DesiredKey if (NextChildP->leftP==NIL) goto CASE1LEFTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; }; CASE1LEFTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey // Case 1 ResultNodeP=NextChildP; // remember node to delete RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; goto FOUNDKEY; CASE1LEFTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; SEARCHRIGHT: // assert: UnsplitMSubtreeP->Key < DesiredKey NextChildP=UnsplitMSubtreeP->rightP; if (NextChildP==NIL) { // Can't find desired key. // Case4: finish splay at M LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP->leftP; if (UnsplitMSubtreeP->leftP!=NIL) UnsplitMSubtreeP->leftP->parentP=LeftSubtreeRightmostNodeP; RightSubtreeLeftmostNodeP->leftP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return NIL; }; if (NextChildP->Key == DesiredKey) goto CASE1RIGHTSUCCESS; // Case 1: Zig case, found desired key #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->Key > DesiredKey) { if (NextChildP->leftP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 3: zig-zag case LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; } else { // Assert: NextChildP->Key < DesiredKey if (NextChildP->rightP==NIL) goto CASE1RIGHTFAILURE; // Case 1: Zig case, but didn't find key else { // Case 2: zig-zig case UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; goto MATCHKEY; }; }; CASE1RIGHTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey ResultNodeP=NextChildP; // remember node to delete LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; goto FOUNDKEY; CASE1RIGHTFAILURE: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key != DesiredKey LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=RightSubtreeLeftmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return NIL; FOUNDKEY: SplayTreeP->mass--; // since we will delete this node if (ResultNodeP->leftP==NIL) { if (ResultNodeP->rightP==NIL) { // Desired node has no children. // Reassemble tree using just L and R. RightSubtreeLeftmostNodeP->leftP=NIL; // cauterize R LeftSubtreeRightmostNodeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=LeftSubtreeRightmostNodeP; SplayTreeP->rootP=DummyNode.rightP; return ResultNodeP; } else { // Desired node has only right son UnsplitMSubtreeP=ResultNodeP->rightP; // ResultNodeP->rightP=NIL; goto SPLAYLEFTTOLEAF; }; } else { // ResultNodeP->leftP!=NIL) if (ResultNodeP->rightP==NIL) { // Desired node has only left son UnsplitMSubtreeP=ResultNodeP->leftP; goto SPLAYLEFTTOLEAF; } else { // Desired node has both sons // INCOMPLETE! Splay both children... }; }; SPLAYLEFTTOLEAF: ; // splay leftmost leaf #if CollectStatistics AccessCompareCount++; // we effectively compare, and discover desired key is to left... #endif // assert: UnsplitMSubtreeP->Key > "DesiredKey" NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Can't go futher left // Finalize2: RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP->rightP; if (UnsplitMSubtreeP->rightP!=NIL) UnsplitMSubtreeP->rightP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; UnsplitMSubtreeP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=UnsplitMSubtreeP; UnsplitMSubtreeP->leftP=DummyNode.rightP; UnsplitMSubtreeP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=UnsplitMSubtreeP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=UnsplitMSubtreeP; return ResultNodeP; }; #if CollectStatistics AccessCompareCount++; // we effectively compare, and discover desired key is to left... #endif // Assert: NextChildP->Key > DesiredKey if (NextChildP->leftP!=NIL) { // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto SPLAYLEFTTOLEAF; } // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == Minimum key // Treat like Case 1 final. RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=DummyNode.rightP; NextChildP->rightP=DummyNode.leftP; if (DummyNode.leftP!=NIL) DummyNode.leftP->parentP=NextChildP; if (DummyNode.rightP!=NIL) DummyNode.rightP->parentP=NextChildP; NextChildP->parentP=NIL; // for cleanliness, although we don't use this SplayTreeP->rootP=NextChildP; return ResultNodeP; }; NodeT* SplayTreeDeleteMinimum(SplayTreeT* SplayTreeP) // Find a node in splay tree having least key, and delete that node // Returns NIL if no such node { NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP NodeT DummyNode; NodeT* ResultNodeP; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay if (UnsplitMSubtreeP==NIL) { // Empty tree, Key can't be found return NIL; }; { /* We use DummyNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ RightSubtreeLeftmostNodeP=&DummyNode; // set to leftmost son of empty R }; MATCHKEY: ; // See if found minimum key node #if CollectStatistics AccessCompareCount++; #endif if (UnsplitMSubtreeP->leftP == NIL) { // Found node with desired key! ResultNodeP=UnsplitMSubtreeP; // remember desired node goto FOUNDKEY; }; // SEARCHLEFT: // assert: UnsplitMSubtreeP->Key > DesiredKey NextChildP=UnsplitMSubtreeP->leftP; #if CollectStatistics AccessCompareCount++; #endif if (NextChildP->leftP == NIL) goto CASE1LEFTSUCCESS; // Case 1: Zig case, found desired key { // Assert: NextChildP->Key > DesiredKey // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; goto MATCHKEY; }; CASE1LEFTSUCCESS: // Assert: (NextChildP=UnsplitMSubtreeP->leftP)->Key == DesiredKey // Case 1 ResultNodeP=NextChildP; // remember node to delete RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; goto FOUNDKEY; FOUNDKEY: SplayTreeP->mass--; // since we will delete this node // Assert: (ResultNodeP->leftP==NIL) UnsplitMSubtreeP=ResultNodeP->rightP; RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; if (UnsplitMSubtreeP!=NIL) UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; SplayTreeP->rootP=DummyNode.leftP; if (SplayTreeP->rootP!=NIL) SplayTreeP->rootP->parentP=NIL; return ResultNodeP; }; void SplayTreeInsert(SplayTreeT* SplayTreeP,NodeT* NewNodeP) // Insert a node according to its key into a splay tree // No duplicates allowed! // (This leaves NewNodeP as root of splay tree) { NodeT* LeftSubtreeRightmostNodeP; // rightmost node L in left subtree during top-down splay NodeT* RightSubtreeLeftmostNodeP; // leftmost node R in right subtree during top-down splay NodeT* UnsplitMSubtreeP; // root M of unsplit part during top-down splay NodeT* NextChildP; // left or right child of UnsplitMSubtreeP KeyT NewNodeKey; UnsplitMSubtreeP=SplayTreeP->rootP; // extract tree to splay SplayTreeP->rootP=NewNodeP; // new node becomes root of tree SplayTreeP->mass++; if (UnsplitMSubtreeP==NIL) { // Insert NewNode into empty tree NewNodeP->leftP=NIL; // mark node as having no children NewNodeP->rightP=NIL; NewNodeP->parentP=NIL; // for cleanliness return; }; // else insert NewNode into non-empty tree NewNodeKey=NewNodeP->Key; // extract key to use for insertion { /* We use NewNode to hold Lroot and Rroot in its left and right children. this avoids having to keep track of whether L and R are empty */ LeftSubtreeRightmostNodeP=NewNodeP; // set to rightmost son of empty L RightSubtreeLeftmostNodeP=NewNodeP; // set to leftmost son of empty R }; /* This procedure essentially does insert(i,t) by carrying out split(i,t), whose logic is just like top-down splay, but but we don't bother forming final splay tree */ // make initial direction decision #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; SEARCHLEFT: // assert: UnsplitMSubtreeP->Key >= NewNodeKey NextChildP=UnsplitMSubtreeP->leftP; if (NextChildP==NIL) { // Case4: finish split at M (to allow final insert) RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; LeftSubtreeRightmostNodeP->rightP=NIL; goto DONE; } #if CollectStatistics InsertCompareCount++; #endif if (NextChildP->Key < NewNodeKey) { // Case 3: zig-zag case RightSubtreeLeftmostNodeP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; if (UnsplitMSubtreeP==NIL) { RightSubtreeLeftmostNodeP->leftP=NIL; goto DONE; }; #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; } else { // Assert: NextChildP->Key >= NewNodeKey // Case 2: zig-zig case UnsplitMSubtreeP->leftP=NextChildP->rightP; if (NextChildP->rightP!=NIL) NextChildP->rightP->parentP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; NextChildP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP==NIL) { LeftSubtreeRightmostNodeP->rightP=NIL; goto DONE; } if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; }; SEARCHRIGHT: // assert: UnsplitMSubtreeP->Key < NewNodeKey NextChildP=UnsplitMSubtreeP->rightP; if (NextChildP==NIL) { // case 4: finish split at M (to allow final insert) LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; RightSubtreeLeftmostNodeP->leftP=NIL; goto DONE; }; #if CollectStatistics InsertCompareCount++; #endif if (NextChildP->Key >= NewNodeKey) { // Case 3: zig-zag case LeftSubtreeRightmostNodeP->rightP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=LeftSubtreeRightmostNodeP; LeftSubtreeRightmostNodeP=UnsplitMSubtreeP; RightSubtreeLeftmostNodeP->leftP=NextChildP; NextChildP->parentP=RightSubtreeLeftmostNodeP; RightSubtreeLeftmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->leftP; if (UnsplitMSubtreeP==NIL) { LeftSubtreeRightmostNodeP->rightP=NIL; goto DONE; }; #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; } else { // Assert: NextChildP->Key < NewNodeKey // Case 2: zig-zig case UnsplitMSubtreeP->rightP=NextChildP->leftP; if (NextChildP->leftP!=NIL) NextChildP->leftP->parentP=UnsplitMSubtreeP; LeftSubtreeRightmostNodeP->rightP=NextChildP; NextChildP->parentP=LeftSubtreeRightmostNodeP; NextChildP->leftP=UnsplitMSubtreeP; UnsplitMSubtreeP->parentP=NextChildP; LeftSubtreeRightmostNodeP=NextChildP; UnsplitMSubtreeP=NextChildP->rightP; if (UnsplitMSubtreeP==NIL) { RightSubtreeLeftmostNodeP->leftP=NIL; goto DONE; } #if CollectStatistics InsertCompareCount++; #endif if (UnsplitMSubtreeP->Key >= NewNodeKey) goto SEARCHLEFT; else goto SEARCHRIGHT; }; DONE: // Swap subtrees of new node to complete. UnsplitMSubtreeP=NewNodeP->leftP; NewNodeP->leftP=NewNodeP->rightP; NewNodeP->rightP=UnsplitMSubtreeP; if (NewNodeP->leftP!=NIL) NewNodeP->leftP->parentP=NewNodeP; if (NewNodeP->rightP!=NIL) NewNodeP->rightP->parentP=NewNodeP; NewNodeP->parentP=NIL; // mark parent with null pointer return; }; NodeT* SplayTreeInsertProbableDuplicate(SplayTreeT* SplayTreeP, KeyT Key) // Insert a node according to its key into a splay tree, assuming it is probably in tree // Returns pointer to node found/inserted { NodeT* NewNodeP; NewNodeP=SplayTreeAccess(SplayTreeP,Key); if (NewNodeP!=NIL) return NewNodeP; // fast/frequent exit { // Create new node and insert into tree NewNodeP=new(NodeT); NewNodeP->Key=Key; SplayTreeInsert(SplayTreeP,NewNodeP); return NewNodeP; }; }; NodeT* SplayTreeInsertProbableNonDuplicate(SplayTreeT* SplayTreeP, KeyT Key) // Insert a node according to its key into a splay tree, assuming it is probably in tree // Returns pointer to node found/inserted { // Bad implementation. A better implementation would split tree going down, // mich like SplayTreeInsert does, and recover if it finds the desired node. return SplayTreeInsertProbableDuplicate(SplayTreeP,Key); }; /* Splay tree code Operations: access(i,t): if i is in tree, return pointer to i, else null Procedure: Find i, then splay tree at i. If i not in tree, splay last node accessed looking for i. join(a,b): Return tree formed by combining tree a and tree b. Assumes every item in tree a has keys less than items in b. Procedure: Splay largest item in a, then add b as right child of root of a. split (i,t): Split tree t, containing i, into two trees: "a", containing all items with keys less or equal to i, and b, containing all items with key greater than i. Procedure: Perform access(i,t), then split tree at root insert(i,t): insert i in tree t Procedure: Perform split (i,t), then make i root of two trees returned by split delete(i,t): delete i from tree t Procedure: Perform access(i,t) then perform join on t's subtrees. Top down splay/split procedure. Keep 3 trees: L, M, R, where all keys in L are less than keys in M, and all keys in M are less than keys in R. (We are searching down a tree M, and inspecting the keys of M and possibly an M-child Y; assume left=children have smaller keys than right children.) Capital letter represent nodes for which algorithm holds explicit pointers. Lsubtree and Rsubtrees each require *two* pointers: one for Lroot and one for rightmost son, L, of Lroot one for Rroot and one for leftmost son, R, of Rroot Case 1: Y is the node we are splaying (Y matches key, or a or b is null) L M R L Y R L M R L Y R / / \ \ / / \ / \ / / \ \ / \ / \ \ Y c ==> a b M OR c Y ==> M b a / \ \ / \ / a b c b a c (this is always followed by Case 4) (this is always followed by case 4) Y Y / \ / \ for splay ==> L R L R / \ / \ / \ / \ a M M a / \ / \ b c c b Case 2: (zig-zig) The node we are splaying is in the subtree rooted at X L M R L X R L M R L X R / / \ \ / / \ / \ / / \ \ / \ / \ \ Y d ==> a b Y OR d Y ==> Y b a / \ \ / \ / X c M c X M / \ / \ / \ / \ a b c d b a d c Case 3: (zig-zag) The node we are splaying is in the subtree rooted at X L M R L X R L M R L X R / / \ \ / \ / \ / \ / / \ \ / \ / \ / \ Y d ==> Y b c M OR d Y ==> M c b Y / \ / \ / \ / \ a X a d X a d a / \ / \ b c c b Case 4: (last step) for splay: M is the node we wish to splay: L M R M / / \ \ / \ Y b ==> L R Note: L,R here represents Lroot/Rroot and L,R / \ / \ Y b Case 4: (last step) for split: M is the node we wish to splay: L M R L R / / \ \ / \ / \ Y b ==> Y M \ b ---------------------------------------------------------------------------------- To delete a node: move down tree performing rotates until desired node M found. One of 3 cases occurs: 1) M has no children, build final result: L M R L / \ / \ ==> R \ 2a) M has left child, but no right child: L M R L Y R / / \ ==> / \ \ Y goto finalize2; 2b) M has no left child, but has right child L M R L Y R / \ \ ==> / \ Y goto finalize2: finalize2) Finding way to leftmost node with null son. rotating zig-zig as required, and then perform the following reassembly: L Y R Y / \ \ / \ b ==> L R / b 3) M has both children: L M R / / \ \ Y b / \ ... / bmin Then delete bmin from b giving b`, and reassemble as follows: bmin / \ ==> L R / \ / \ Y b' ----------------------------------------------------------------------------------- */ unsigned int seed=0; #define TestSize 20000 unsigned int myrand(range) { seed=(seed+1)*3141597237; return seed%range; }; void ComplainIfInsane(SplayTreeT* SplayTreeP,KeyT k) { if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure on key %d\n",k); }; void TestSplayTree() // Test Splay Tree for correct operation { SplayTreeT* SplayTreeP; NodeT* NodeP; NodeT* minNodeP; unsigned int i; unsigned int slot; KeyT k; KeyT KeyArray[TestSize]; printf("Running Splay Tree test...\n"); { printf("Test inserting small set of values\n"); SplayTreeP=newSplayTreeT(); { NodeP=newNodeT(1); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,1); }; { NodeP=newNodeT(2); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,2); }; { NodeP=newNodeT(3); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,3); }; { NodeP=newNodeT(4); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,4); }; { NodeP=newNodeT(5); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,5); }; { NodeP=newNodeT(6); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,6); }; { NodeP=newNodeT(0); SplayTreeInsert(SplayTreeP,NodeP); ComplainIfInsane(SplayTreeP,0); }; }; { printf("Test increasing access of small set of inserted values\n"); for (i=0;i<6;i++) { k=i; printf("Accessing value %d\n",k);; SplayTreeAccess(SplayTreeP,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree lookup failure on iteration %d with key %d\n",i,k); }; }; { printf("Test deleting minimum values keys for small set\n"); for (i=0;i<=6;i++) { k=i; printf("Deleting minimum key %d\n",i);; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP->Key!=k) printf("Splay tree delete minimum deleted wrong key %d on iteration %d with key %d\n", minNodeP->Key,i,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree DeleteMinimum failure on iteration %d with key %d\n",i,k); }; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP!=NIL) printf("Splay tree delete min failure when empty"); }; { printf("Test insert in increasing order\n"); #if CollectStatistics InsertCompareCount=0; #endif SplayTreeP=newSplayTreeT(); for (i=1;i<TestSize;i++) { // Insert keys in increasing order k=i; printf("Inserting value %d\n",k); NodeP=newNodeT(k); SplayTreeInsert(SplayTreeP,NodeP); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure increasing keys %d\n",k); }; #if CollectStatistics printf("For %d inserts, there were %d compares.\n",TestSize,InsertCompareCount); #endif }; { printf("Test insert in decreasing order\n"); #if CollectStatistics InsertCompareCount=0; #endif SplayTreeP=newSplayTreeT(); for (i=1;i<TestSize;i++) { // Insert keys in increasing order k=TestSize-i; printf("Inserting value %d\n",k); NodeP=newNodeT(k); SplayTreeInsert(SplayTreeP,NodeP); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure decreasing keys %d\n",k); }; #if CollectStatistics printf("For %d inserts, there were %d compares.\n",TestSize,InsertCompareCount); #endif }; { printf("Test insert random key sequence\n"); #if CollectStatistics InsertCompareCount=0; #endif SplayTreeP=newSplayTreeT(); for (i=0;i<TestSize;i++) { // set up a dense set of keys KeyArray[i]=i; // set up a list of keys }; for (i=0;i<TestSize;i++) { // Now shuffle dense set of keys around slot=myrand(TestSize); k=KeyArray[slot]; // swap a pair of keys KeyArray[slot]=KeyArray[i]; KeyArray[i]=k; }; for (i=0;i<TestSize;i++) { k=KeyArray[i]; printf("Iteration %d inserting value %d\n",i,k); NodeP=newNodeT(k); // force duplicate keys SplayTreeInsert(SplayTreeP,NodeP); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree insert failure on iteration %d with key %d\n",i,k); }; #if CollectStatistics printf("For %d inserts, there were %d compares.\n",TestSize,InsertCompareCount); #endif }; { printf("Test increasing access of randomly inserted values\n"); #if CollectStatistics AccessCompareCount=0; #endif for (i=0;i<TestSize;i++) { k=i; printf("Accessing value %d\n",k); SplayTreeAccess(SplayTreeP,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree lookup failure on iteration %d with key %d\n",i,k); }; #if CollectStatistics printf("For %d linear accesses, there were %d compares.\n",TestSize,AccessCompareCount); #endif }; { printf("Test random access of randomly inserted values\n"); #if CollectStatistics AccessCompareCount=0; #endif for (i=0;i<TestSize;i++) { k=KeyArray[i]; printf("Iteration %d accessing value %d\n",i,k); SplayTreeAccess(SplayTreeP,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree lookup failure on iteration %d with key %d\n",i,k); }; #if CollectStatistics printf("For %d random accesses, there were %d compares.\n",TestSize,AccessCompareCount); #endif }; { printf("Test deleting minimum values keys from randomly accessed set\n"); #if CollectStatistics AccessCompareCount=0; #endif for (i=0;i<TestSize;i++) { k=i; printf("Deleting minimum key %d\n",i);; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP->Key!=k) printf("Splay tree delete minimum deleted wrong key %d on iteration %d with key %d\n", minNodeP->Key,i,k); if (!SplayTreeSanity(SplayTreeP)) printf("Splay tree DeleteMinimum failure on iteration %d with key %d\n",i,k); }; minNodeP=SplayTreeDeleteMinimum(SplayTreeP); if (minNodeP!=NIL) printf("Splay tree delete min failure when empty"); #if CollectStatistics printf("For %d deleteMin after random accesses, there were %d compares.\n",TestSize,AccessCompareCount); #endif }; }; void main() { TestSplayTree(); };