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 to merge
//           Budd's hash_table with an interface similar to std::set,
//           added erase function, replaced == comparison of elements
//           by a comparison functor template parameter, added const's

#include <algorithm>
#include <functional>


enum HashStatus { Occupied, Empty, Deleted };

template <class T>
struct HashEntry
{
  T data;
  HashStatus info;

  HashEntry(): info(Empty) {}
  HashEntry(const T& v, HashStatus status)
    : data(v), info(status) {}

};


template <class T, int hSize, class HashFun, class CompareEQ=equal_to<T> >
class hash_set
{
public:
  hash_set (): theSize(0) {}

  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;
      }
  }
  
  
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