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(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=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)
  {/*{*/algae->FRAME("starting insert");
    unsigned h0 = hash(element);
    unsigned h = find(element, h0);
/*{*/algae->FRAME("insert: is element already in table?");
    if (h == hSize) {
      unsigned count = 0;
      h = h0;
/*{*/ algae->FRAME("start searching for an open spot");
      while (table[h].info == Occupied 
	     && count < hSize)
	{/*{*/algae->FRAME("not here - keep going.");
	  ++count;
	  h = (h0 + /*f(count)*/ count) % hSize;
	}
/*{*/algae->FRAME("insert: did we find a spot?");
      if (count >= hSize)
	return false;  // could not add
      else
	{ /*{*/algae->FRAME("insert: put the data here");
	  table[h].info = Occupied;
          table[h].data = element;
/*{*/algae->FRAME("inserted");
	  return true;
	}
    }
    else {/*{*/algae->FRAME("item is already in set"); /*}*/ // replace
      table[h].data = element;
/*{*/ algae->FRAME("inserted.");
      return true;
    }
  }



  int count (const T& element)
  {/*{*/algae->FRAME("starting count");
    unsigned h0 = hash(element);
    unsigned h = find(element, h0);
   /*{*/algae->FRAME("count: is element in table?");
    return  (h != hSize) ? 1 : 0;
  }




  void erase (const T& element)
  {/*{*/algae->FRAME("starting erase");
    unsigned h0 = hash(element);
    unsigned h = find(element, h0);
/*{*/algae->FRAME("erase: is element already in table?");
    if (h != hSize)
      table[h].info = Deleted;
/*{*/algae->FRAME("erased");
  }


  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
    {/*{*/algae->FRAME("starting find");
      unsigned h = h0 % hSize;
      unsigned count = 0;
/*{*/ algae->FRAME("start the search");
      while ((table[h].info == Deleted ||
	      (table[h].info == Occupied 
	       && (!compare(table[h].data, element))))
	     && count < hSize)
	{/*{*/algae->FRAME("not here - keep going");
          ++count;
          h = (h0 + /*f(count)*/ count) % hSize;
        }
/*{*/ algae->FRAME("find: did we find it?");
      if (count >= hSize 
          || table[h].info == Empty)
        return hSize;
      else 
        return h;
    }

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


#endif