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

//
// AbstractHeap.h
//
#ifndef __AbstractHeap_h
#define __AbstractHeap_h

#ifdef __GNUC__
#pragma interface
#endif

#ifdef NON_ANSI
#include <iostream.h>
#else
#include <iostream>
using namespace std;
#endif

#include "_generic.h"
#include "errmsg.h"



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

  explicit AbstractHeap(const char* nameBuff = "Unnamed",
       int initSize = defaultSize, 
       int quantumChoice = defaultQuantum);
  virtual ~AbstractHeap();
  
  bool empty() const {return (used == 0);}
  operator bool() const {return (used != 0);}
  int size() const { return used; }

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

  T* top() const
                { 
                if (used <= 0) 
                   cerr << "Empty heap: " << name << endl;
                return tree[1]; 
                }
  T* member(int element) const
                { return tree[element]; }
  T* find(KEY& key);

  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) const;
  int read(istream& is);

  int prune();

  static const int defaultSize;
  static const int defaultQuantum;
  void clear();

protected:

  OrderSense Sense;

  virtual T* insert(KEY* item);
  virtual void extract(T* item, bool& status);
  int refloatElement(int element);

  virtual int  prunable(T* /*item*/) {return 0;}

  virtual void moveEffect(T* /*item*/) {}
  virtual void addEffect(T* /*item*/) {}
  virtual void removeEffect(T* item)
                {item->element=0;}
  virtual void pruneEffect(T* /*item*/) {}

  int    used;
  int    allocated;
  int    quantum;
  T** tree;
  const char*  name;

  void swap(int a,int b);
  int floatUp(int element);
  int sinkDown(int element);

};


template <class T, class KEY>
const int AbstractHeap<T,KEY>::defaultSize    = 256;
template <class T, class KEY>
const int AbstractHeap<T,KEY>::defaultQuantum = 256;

template <class T, class KEY>
inline ostream& operator<<(ostream& output, const AbstractHeap<T,KEY>& heap)
{ heap.write(output); return(output); }


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



template <class T, class KEY>
AbstractHeap<T,KEY>::AbstractHeap(const char* nameBuff,
           int initSize, 
           int quantumChoice) :
           Sense(increasing),
           used(0),
           allocated(initSize),
           quantum(quantumChoice),
           name(nameBuff)
{
if (!name)
   name = "";
tree = (new (T*[initSize])) - 1;
}


template <class T, class KEY>
AbstractHeap<T,KEY>::~AbstractHeap()
{
delete[] (tree + 1);
}



template <class T, class KEY>
void AbstractHeap<T,KEY>::swap(int a,int b) 
{
register T* t1 = tree[a];
register T* t2 = tree[b];
tree[a] = t2;
tree[b] = t1;
t1->element=b;
t2->element=a;
moveEffect(t1);
moveEffect(t2);
}



template <class T, class KEY>
int AbstractHeap<T,KEY>::floatUp(int element)
{
int next;
while (((next = element >> 1) >= 1) && 
       ((Sense* tree[element]->compare(tree[next]->key())) < 0))
  {
  swap(element,next);
  element = next;
  }
return element;
}


template <class T, class KEY>
int AbstractHeap<T,KEY>::sinkDown(int element)
{
int child;
while ((child = element << 1) <= used) 
  {
  if ((child < used) && ((Sense*tree[child+1]->compare(tree[child]->key()))<0))
     child++;
  if ((Sense*tree[element]->compare(tree[child]->key()))<0)
     return(element);
  swap(element,child);
  element = child;
  }
return element;
}


template <class T, class KEY>
int AbstractHeap<T,KEY>::refloatElement(int element)
{
int newLocation = floatUp(element);
if (newLocation == element)
   return sinkDown(element);
else
   return element;
}


template <class T, class KEY>
T* AbstractHeap<T,KEY>::insert(KEY* newkey) 
{
if (used == allocated) {
   if (quantum > 0) {
      allocated += quantum;
      T** oldTree = tree;
      tree = (new (T*[allocated])) - 1; 
      for (int i=1; i<=used; i++)
        tree[i] = oldTree[i];
      delete [] (oldTree + 1);
      }
   else 
      cerr << name << "heap overflowed at " << (used+1) << " elements" << endl;
   }

T* item = new T(newkey);
tree[++used] = item;
addEffect(item);
item->element=used;
moveEffect(item);
floatUp(used);
return item;
}


template <class T, class KEY>
void AbstractHeap<T,KEY>::extract(T* item, bool& status) 
{
int element = item->element;
if ((element < 1) || (element > used)) {
   status=false;
   return;
   }

removeEffect(item);
delete item;
if (element < used) {
   T* t = tree[used];
   tree[element] = t;
   used--;
   t->element=element;
   moveEffect(t);
   refloatElement(element);
   }
else
   used--;

status=true;
}


template <class T, class KEY>
int AbstractHeap<T,KEY>::prune() 
{
int n = used;
while (n > (used >> 1)) {
  if (prunable(tree[n])) {
     T* item = tree[n];
     pruneEffect(item);
     deleteElement(n);
     if (n > used)
        n = used;
     }
  else 
     n--;
  }
return used;
}


template <class T, class KEY>
int AbstractHeap<T,KEY>::write(ostream& os) const
{
os << size() << endl;
for (int i=1; i<=size(); i++) {
  member(i)->write(os);
  os << endl;
  }
os << endl;
return OK;
}

             
template <class T, class KEY>
int AbstractHeap<T,KEY>::read(istream& is)
{
clear();
int Size;
is >> Size;
for (int i=1; i<=Size; i++) {
  T* item;
  item->read(is);
  add(item);
  }
return OK;
}          



//
// For right now, this is done with a linear search through the
// heap array.  A more efficient method could be designed, but I don't
// expect to use this method much, so...
//
template <class T, class KEY>
T* AbstractHeap<T,KEY>::find(KEY& key)
{
for (int i=1; i<= size(); i++)
  if (member(i)->compare(key) == 0)
     return member(i);

return 0;
}


template <class T, class KEY>
void AbstractHeap<T,KEY>::clear()
{
bool status;
while (size()>0) {
  remove(top(),status);
  if (!status)
     ErrAbort("AbstractHeap<T,KEY>::clear - problem removing the root of the heap.");
  }
}


#endif