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

// 
// SimpleHeap.h
//
#ifndef __SimpleHeap_h
#define __SimpleHeap_h

#ifdef __GNUC__
#pragma interface
#endif

#include "_generic.h"
#include "AbstractHeap.h"
#include "compare.h"

template <class T>
class SimpleHeap;


template <class T>
class SimpleHeapItem 
{
  friend class AbstractHeap<SimpleHeapItem<T>,T>;
  friend class SimpleHeap<T>;

public:

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

private:

  T Key;
  int element;
  int ctr;

  SimpleHeapItem(const T* Key_) : Key(*Key_), element(0), ctr(1) {}
};



template <class T>
class SimpleHeap : public AbstractHeap<SimpleHeapItem<T>,T>
{
public:

  SimpleHeap(const char* nameBuff = "Unnamed")
        : AbstractHeap<SimpleHeapItem<T>,T>(nameBuff), 
                duplicate_flag(true), check_duplicates_flag(false) {}

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

protected:
 
  bool duplicate_flag;
  bool check_duplicates_flag;

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

};


template <class T>
SimpleHeapItem<T>* SimpleHeap<T>::insert(T* key)
{
duplicate_flag = false;
if (check_duplicates_flag) {
   SimpleHeapItem<T>* item = find(*key);  
   if (item) {
      item->ctr++;
      duplicate_flag = true;
      return item;
      }
   }
return AbstractHeap<SimpleHeapItem<T>,T>::insert(key);
}


template <class T>
void SimpleHeap<T>::extract(SimpleHeapItem<T>* item, bool& status)
{
if (check_duplicates_flag) {
   SimpleHeapItem<T>* item = find(item->key());
   if (item) {
      item->ctr--;
      if (item->ctr > 0) {
         status=true;
         return;
         }
      }
   }
AbstractHeap<SimpleHeapItem<T>,T>::extract(item,status);
}

#endif