hashset.h

ALGAE是一个快速创建算法演示的框架。目前支持的算法实现语言包括java和c

#ifndef HASHSET_H
#define HASHSET_H

//
//	Hash table implementation of set, using linear probing
//
//	Based loosely on the hash_table class from Chapter 17
//      of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, [e-mail]
//	Oregon State University
//
//      Steven Zeil: Heavily modified, combined two classes,
//           added erase function,
//           added comparison template parameter, const's
/*{*/ #include <algae/visible.h>
#include <algorithm>
#include <functional>


enum HashStatus { Occupied, Empty, Deleted };

template <class T>
struct HashEntry /*{*/: public Visible /*}*/
{
  T data;
  HashStatus info;

  HashEntry(): info(Empty) /*{*/, Visible(AlgAE::PaleCyan) /*}*/ {}
  HashEntry(const T& v, HashStatus status)
    : data(v), info(status) /*{*/, Visible(AlgAE::PaleCyan) /*}*/{}

/*{*/  virtual void touchAllPointers() const
/*{*/    { }
/*{*/
/*{*/  virtual void writeText(std::ostream& out) const
/*{*/  {
/*{*/    if (info == Deleted)
/*{*/      out << "--del--";
/*{*/    else
/*{*/      {
/*{*/       out << data;
/*{*/       for (int i = data.size(); i <= 8; ++i)
/*{*/         out << ' ';
/*{*/      }
/*{*/  }
};


template <class T, int hSize, class HashFun, class CompareEQ=std::equal_to<T> >
class hash_set /*{*/: public Visible /*}*/ 
{
public:
  hash_set (): /*{*/Visible(AlgAE::Blue), /*}*/ theSize(0) 
  {/*{*/for (int i = 0; i < hSize; ++i) {table[i].setName(itos(i));} /*}*/}

  bool empty() const {return theSize == 0;}

  int size() const  {return theSize;}



  bool insert (const T& element)
  {
    unsigned h0 = hash(element);
    unsigned h = find(element, h0);
    if (h == hSize) {
      unsigned count = 0;
      h = h0;
      while (table[h].info == Occupied 
	     && count < hSize)
	{
	  ++count;
	  h = (h0 + /*f(count)*/ count) % hSize;
	}
      if (count >= hSize)
	return false;  // could not add
      else
	{ 
	  table[h].info = Occupied;
          table[h].data = element;
	  return true;
	}
    }
    else {  // replace
      table[h].data = element;
      return true;
    }
  }



  int count (const T& element)
  {
    unsigned h0 = hash(element);
    unsigned h = find(element, h0);
    return  (h != hSize) ? 1 : 0;
  }




  void erase (const T& element)
  {
    unsigned h0 = hash(element);
    unsigned h = find(element, h0);
    if (h != hSize)
      table[h].info = Deleted;
  }


  void clear()
  {
    for (int i = 0; i < hSize; ++i)
      {
	table[i].info = Empty;
      }
  }
  
  

/*{*/
/*{*/  virtual void writeText (class std::ostream& out) const 
/*{*/  {
/*{*/    out << theSize;
/*{*/  }
/*{*/  virtual void touchAllComponents() const
/*{*/  {
/*{*/    for (int i = 0; i < hSize; ++i)
/*{*/       touch(table[i]);
/*{*/  }
  
private:

  int find (const T& element, int h0) const
    {
      unsigned h = h0 % hSize;
      unsigned count = 0;
      while ((table[h].info == Deleted ||
	      (table[h].info == Occupied 
	       && (!compare(table[h].data, element))))
	     && count < hSize)
	{
          ++count;
          h = (h0 + /*f(count)*/ count) % hSize;
        }
      if (count >= hSize 
          || table[h].info == Empty)
        return hSize;
      else 
        return h;
    }

  
  HashEntry<T> table[hSize];
  int theSize;
  HashFun hash;
  CompareEQ compare;
};


#endif