AbstractSplayTree.h

/*  _________________________________________________________________________
 *
 *  UTILIB: A utility library for developing portable C++ codes.
 *  Copyright (c) 2001, Sandia National Laboratories.
 *  This software is distributed under the GNU Lesser General Public License.
 *  For more information, see the README file in the top UTILIB directory.
 *  _________________________________________________________________________
 */

//
// AbstractSplayTree.h
//
#ifndef __AbstractSplayTree_h
#define __AbstractSplayTree_h

#ifdef __GNUC__
#pragma interface
#endif
 
#ifdef NON_ANSI
#include <iostream.h>
#else
#include <iostream>
using namespace std;
#endif
#ifndef ANSI_HDRS
#include <stdio.h>
#else
#include <cstdio>
#endif
#include "_generic.h"
#include "AbstractSplayTree.h"
#include "errmsg.h"
#ifdef _MSC_VER
#include "crtdbg.h"
#endif
#include "compare.h"

#define node_size(x)   (((x)==NULL) ? 0 : ((x)->size))



template <class T, class KEY>
class AbstractSplayTree 
{
public:

  explicit AbstractSplayTree(const char* nameBuff = "Unnamed");
  virtual ~AbstractSplayTree() {}
  
  bool empty() const {return (tree == 0);}
  operator bool() const {return (tree != 0);}
  int size() const { return (tree ? tree->size : 0); }

  OrderSense sense() {return Sense;}
  void setSense(OrderSense sense_) {Sense=sense_;}

  void splay(const KEY& key)
                {tree = exec_splay(&key,tree);}

  virtual T* find_rank(int r);
  virtual T* find(const KEY& key)
                {
                splay(key);
                if (!tree) return tree;
                if (tree->compare(key) == 0) return tree;
                else                          return (T*)0;
                }
  T* top()      {return tree;}

  virtual void add(KEY& key)
                {insert(&key);}
  virtual void add(KEY& key, T*& item)
                {item = insert(&key);}
  virtual void remove(KEY& key, bool& status)
                {
                T* tmp = find(key);
                if (tmp) extract(tmp,status);
                else     status = false;
                }
  virtual void remove(T*& item, bool& status)
                {
                if (!item)
                   status = false;
                else {
                   extract(item,status);
                   item = 0;
                   }
                }
  virtual void remove(T*& item, KEY& key, bool& status)
                {
                if (!item)
                   status = false;
                else {
                   key = item->key();
                   extract(item,status);
                   item = 0;
                   }
                }

  int write(ostream& os);
  int read(istream& is);
  int rank(const KEY& key)
                {
                splay(key);
                return (tree->left ? tree->left->size : 0);
                }
  void clear();

protected:

//  void print_tree(ostream& os, int d, T* item);


  T* exec_splay(const KEY* key, T* item);
  virtual T* insert(KEY* key);
  virtual void extract(T* item, bool& status);

  T* tree;
  OrderSense Sense;
  const char* name;

};


 
template <class T, class KEY>
inline UTILIB_API ostream& operator<<(ostream& output, 
                                                AbstractSplayTree<T,KEY>& tree)
{ tree.write(output); return(output); }
 


template <class T, class KEY>
inline UTILIB_API istream& operator>>(istream& input,
                                                AbstractSplayTree<T,KEY>& tree)
{ tree.read(input); return(input); }
 


template <class T, class KEY>
AbstractSplayTree<T,KEY>::AbstractSplayTree(const char* nameBuff)
        : tree(0),
          Sense(increasing),
          name(nameBuff)
{
if (!name)
   name = "";
}



template <class T, class KEY>
T* AbstractSplayTree<T,KEY>::exec_splay(const KEY* key, T* t)
{
    T N((KEY*)key), *l, *r, *y;
    int comp, l_size, r_size;
    
    if (t == 0) return t;
    comp = Sense*t->compare(*key);
    if (comp == 0) return t;

    N.left = N.right = NULL;
    l = r = &N;
    l_size = r_size = 0;
 
    while (1) {
        if (comp > 0) {
            if (t->left == NULL) break;
            if ((Sense*t->left->compare(*key)) > 0) {
                y = t->left;                           /* rotate right */
                t->left = y->right;
                y->right = t;
                t->size = node_size(t->left) + node_size(t->right) + 1;
                t = y;
                if (t->left == NULL) break;
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
            r_size += 1+ node_size(r->right);
        } else if (comp < 0) {
            if (t->right == NULL) break;
            if ((Sense*t->right->compare(*key)) < 0) {
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
                t->size = node_size(t->left) + node_size(t->right) + 1;
                t = y;
                if (t->right == NULL) break;
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
            l_size += 1+ node_size(l->left);
        } else {
            break;
        }
        comp = Sense*t->compare(*key);
    }
    l_size += node_size(t->left);  /* Now l_size and r_size are the sizes of */
    r_size += node_size(t->right); /* the left and right trees we just built.*/
    t->size = l_size + r_size + 1;

    l->right = r->left = NULL;

    /* The following two loops correct the size fields of the right path  */
    /* from the left child of the root and the right path from the left   */
    /* child of the root.                                                 */
    for (y = N.right; y != NULL; y = y->right) {
        y->size = l_size;
        l_size -= 1+ node_size(y->left);
    }
    for (y = N.left; y != NULL; y = y->left) {
        y->size = r_size;
        r_size -= 1+ node_size(y->right);
    }
 
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;

    return t;
}



template <class T, class KEY>
T* AbstractSplayTree<T,KEY>::insert(KEY* newkey)
{
    T* newroot = new T(newkey);
    if (tree == NULL) {
        newroot->left = newroot->right = NULL;
        }
    else {
        if ((Sense*newroot->compare(tree->key())) < 0) {
           newroot->left = tree->left;
           newroot->right = tree;
           tree->left = NULL;
           tree->size = 1+ node_size(tree->right);
        } else {
           newroot->right = tree->right;
           newroot->left = tree;
           tree->right = NULL;
           tree->size = 1+ node_size(tree->left);
        }
    }
    
    newroot->size = 1 + node_size(newroot->left) + node_size(newroot->right);
    tree = newroot;
    return tree;
}



template <class T, class KEY>
void AbstractSplayTree<T,KEY>::extract(T* node, bool& status) {
    T* x;
    int tsize;

    if (tree==NULL) return;
    tsize = tree->size;
    tree = exec_splay(&(node->key()),tree);
    if ((Sense*node->compare(tree->key())) == 0) {               // found it
        status = true;
        if (tree->left == NULL) {
            x = tree->right;
        } else {
            x = exec_splay(&(node->key()), tree->left);
            x->right = tree->right;
        }
        delete tree;
        if (x != NULL) {
            x->size = tsize-1;
        }
        tree = x;
    }
    else {
        status = false;
        node = 0;
    }
}



template <class T, class KEY>
T* AbstractSplayTree<T,KEY>::find_rank(int r)
{
    T* tmp=tree;
    int lsize;
    if ((r < 0) || (r >= node_size(tmp))) return NULL;
    for (;;) {
        lsize = node_size(tmp->left);
        if (r < lsize) {
            tmp = tmp->left;
        } else if (r > lsize) {
            r = r - lsize - 1;
            tmp = tmp->right;
        } else {
            break;
        }
    }
    tree = exec_splay(&(tmp->key()),tree);
    return tmp;
}

/*
void AbstractSplayTree<T,KEY>::print_tree(ostream& os, int d, 
                                        T* t) {
    int i;
    if (tree == NULL) return;
    print_tree(os,d+1,tree->right);
    for (i=0; i<d; i++) os << "  ";
    dowrite(tree,os);
    //os << "(" << node_size(tree) << "," << tree->ctr << ")" << endl;
    print_tree(os,d+1,tree->left);
}
*/



template <class T, class KEY>
int AbstractSplayTree<T,KEY>::write(ostream& os)
{
os << size() << endl;

T* node;
node = find_rank(0);
int i=1;
while (node) {
  //os << node->ctr << " ";
  node->write(os);
  os << endl;
  node = find_rank(i++);
  }

return 0;
}



template <class T, class KEY>
int AbstractSplayTree<T,KEY>::read(istream& is)
{
int Size;
is >> Size;
for (int i=0; i<Size; i++) {
  T* item;
  item->read(is);
  add(item);
  }

return OK;
}



template <class T, class KEY>
void AbstractSplayTree<T,KEY>::clear()
{
bool status;
while (tree) {
  remove(tree,status);
  if (!status)
     ErrAbort("AbstractSplayTree<T,KEY>::clear - problem removing the root of the splay tree.");
  }
}

#undef node_size
#endif