#include "SW.h"

// From Stout and Warren - translated from Pascal to C by Tim Rolfe,
// expanded and with an additional function re. node height and parent

// Rebalance procedure:  go from tree to vine, then
// return from vine to tree.

// To avoid the special case of processing at the root, this uses
// a "pseudo-root" is passed --- comparable with a dummy header node
// for a linked list.

// Reference:  Quentin F. Stout and Bette L. Warren,
// "Tree Rebalancing in Optimal Time and Space",
// Communications of the ACM, Vol. 29, No. 9
// (September 1986), p. 904.

// NOTE:  for ACM members, the full text is available through 
// http://www.acm.org/pubs/contents/journals/cacm/
// --- Navigate to Vol. 29, No. 9.

void SW::rebalance()
// Public member function:  Do the DSW algorithm to balance the tree
{//Declare as automatic variable; remember to pass as pointer
   BaseCell pseudo_root( -1, NULL, NULL, Root );

   int size;

   tree_to_vine (&pseudo_root, size);

   vine_to_tree (&pseudo_root, size);

   Root = pseudo_root.Right;
   correctTree (Root, NULL);
}

// Tree to Vine algorithm:  a "pseudo-root" is passed ---
// comparable with a dummy header for a linked list.

void SW::tree_to_vine ( BasePtr root, int &size )
{  BasePtr vineTail, remainder, tempPtr;

   vineTail = root;
   remainder = vineTail->Right;
   size = 0;

   while ( remainder != NULL )
   {//If no leftward subtree, move rightward
      if ( remainder->Left == NULL )
      {  vineTail = remainder;
         remainder = remainder->Right;
         size++;
      }
//    else eliminate the leftward subtree by rotations
      else  /* Rightward rotation */
      {  tempPtr = remainder->Left;
         remainder->Left = tempPtr->Right;
         tempPtr->Right = remainder;
         remainder = tempPtr;
         vineTail->Right = tempPtr;
      }
   }
}

// Stout and Warren have a nested procedure --- not
// supported by C.  So the nested procedure is given
// here prior to the code that uses it.

void SW::compression ( BasePtr root, int count )
{  BasePtr scanner, child;
   int     j;

   scanner = root;
   for ( j = 0; j < count; j++ )
   {//Leftward rotation
      child = scanner->Right;
      scanner->Right = child->Right;
      scanner = scanner->Right;
      child->Right = scanner->Left;
      scanner->Left = child;
   }  // end for
}  // end compression

// Code added by Tim Rolfe:  Expands on Warren & Stout's
// notation involving powers, floors, and base-2 logs
int FullSize ( int size )    // Full portion complete tree
{  int Rtn = 1;
   while ( Rtn <= size )      // Drive one step PAST FULL
      Rtn = Rtn + Rtn + 1;   // next pow(2,k)-1
   return Rtn/2;
}

void SW::vine_to_tree ( BasePtr root, int size )
{
   int full_count = FullSize (size);
   compression(root, size - full_count);
   for ( size = full_count ; size > 1 ; size /= 2 )
      compression ( root, size / 2 );
}

// Code added by Tim Rolfe
inline int Max( int l, int r)     // used by correctHeight
{  return l > r ? l : r;  }

// Traverse entire tree, correcting heights and parents
void SW::correctTree( BasePtr node, BasePtr Parent )
{  if ( node != NULL )
   {  int LtHt, RtHt;

      correctTree (node->Left, node);
      correctTree (node->Right, node);
      node->Parent = Parent;
      LtHt = node->Left  ? node->Left->Height  : 0;
      RtHt = node->Right ? node->Right->Height : 0;
      node->Height = 1 + Max( LtHt, RtHt );
   }
}