Code Search (Find, Follow), Analysis (Metrics, Static, Dynamic, Bugs) and Change (Modernization, Migration, Generation, Optimization, Rearchitecting)

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();
};