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

// 
// GenericSplayTree.h
//
#ifndef __GenericSplayTree_h
#define __GenericSplayTree_h

#ifdef __GNUC__
#pragma interface
#endif

#include "_generic.h"
#include "AbstractSplayTree.h"
 
template <class T>
class UTILIB_API GenericSplayTree;


template <class T>
class UTILIB_API GenericSplayTreeItem
{
  friend class AbstractSplayTree<GenericSplayTreeItem<T>,T>;
  friend class GenericSplayTree<T>;

public:

  int Size() {return size;}
  void write(ostream& os) {Keyptr->write(os);}
  T& key() {return *Keyptr;}
  int compare(const T& key)
                {return Keyptr->compare(key);}

private:

  T* Keyptr;
  int ctr;

  GenericSplayTreeItem<T> *left;
  GenericSplayTreeItem<T> *right;
  int size;

  GenericSplayTreeItem(T* key_ptr_) : Keyptr(key_ptr_), ctr(1), left(0),
                                right(0), size(0) {}
};



template <class T>
class UTILIB_API GenericSplayTree : public AbstractSplayTree<GenericSplayTreeItem<T>,T>
{
public:

  explicit GenericSplayTree(const char* nameBuff = "Unnamed")
        : AbstractSplayTree<GenericSplayTreeItem<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;

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

};


template <class T>
GenericSplayTreeItem<T>* GenericSplayTree<T>::insert(T* key)
{
tree = exec_splay(key,tree);
GenericSplayTreeItem<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<GenericSplayTreeItem<T>,T>::insert(key);
}


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



#endif