SimpleSplayTree.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.
 *  _________________________________________________________________________
 */

// 
// SimpleSplayTree.h
//
#ifndef __SimpleSplayTree_h
#define __SimpleSplayTree_h

#ifdef __GNUC__
#pragma interface
#endif

#include "_generic.h"
#include "AbstractSplayTree.h"
#include "compare.h"

template <class T>
class SimpleSplayTree;


template <class T>
class SimpleSplayTreeItem 
{
  friend class AbstractSplayTree<SimpleSplayTreeItem<T>,T>;
  friend class SimpleSplayTree<T>;

public:

  int  Size() {return size;}
  void write(ostream& os) {os << Key;}
  int counter() {return ctr;}
  T& key() {return Key;}
  int compare(const T& key)
                {return ::compare(Key,key);}

private:

  T Key;
  int ctr;
 
  SimpleSplayTreeItem<T> *left;
  SimpleSplayTreeItem<T> *right;
  int size;

  SimpleSplayTreeItem(const T* Key_) : Key(*Key_), ctr(1),left(0),right(0),
                                  size(0) {}
};



template <class T>
class SimpleSplayTree : public AbstractSplayTree<SimpleSplayTreeItem<T>,T>
{
public:

  SimpleSplayTree(const char* nameBuff = "Unnamed")
        : AbstractSplayTree<SimpleSplayTreeItem<T>,T>(nameBuff), 
                duplicate_flag(true), check_duplicates_flag(true) {}

  bool& duplicate() {return duplicate_flag;}
  bool& check_duplicates() {return check_duplicates_flag;}

protected:
 
  bool duplicate_flag;
  bool check_duplicates_flag;

  SimpleSplayTreeItem<T>* insert(T* key);
  void extract(SimpleSplayTreeItem<T>* item, bool& status);

};


template <class T>
SimpleSplayTreeItem<T>* SimpleSplayTree<T>::insert(T* key)
{
tree = exec_splay(key,tree);
SimpleSplayTreeItem<T>* treeitem = top();

duplicate_flag = false;
if (check_duplicates_flag && (treeitem != NULL)) {
   if (treeitem->compare(*key)==0) {    // it's already there
      treeitem->ctr++;
      duplicate_flag = true;
      return treeitem;
      }
   }
return AbstractSplayTree<SimpleSplayTreeItem<T>,T>::insert(key);
}


template <class T>
void SimpleSplayTree<T>::extract(SimpleSplayTreeItem<T>* item, bool& status)
{
if (check_duplicates_flag) {
   tree = exec_splay(&(item->key()),tree);
   SimpleSplayTreeItem<T>* treeitem = top();
   if (treeitem && (treeitem->compare(item->key()) == 0)) {
      treeitem->ctr--;
      if (treeitem->ctr > 0) {
         status=true;
         return;
         }
      }
   }
AbstractSplayTree<SimpleSplayTreeItem<T>,T>::extract(item,status);
}

#endif