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 <utils/visint.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");
/*{*/VisibleInteger h0 (hash(element), "h0");
/*{*/ // /*}*/      unsigned h0 = hash(element);
/*{*/VisibleInteger h (find(element, h0), "h"); 
/*{*/h.show();
/*{*/h0.show();
/*{*/ // /*}*/      unsigned h = find(element, h0);
/*{*/algae->FRAME("insert: is element already in table?");
     if (h == hSize) {
/*{*/VisibleInteger count (0, "count");
/*{*/count.show();
/*{*/ // /*}*/      unsigned count = 0;
        h = h0;
/*{*/table[h].highlight(AlgAE::PaleGreen);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;/*{*/table[h].highlight(AlgAE::PaleGreen); /*}*/
          }
/*{*/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");
/*{*/VisibleInteger h0 (hash(element), "h0"); 
/*{*/h0.show();
/*{*/ // /*}*/      unsigned h0 = hash(element);
/*{*/VisibleInteger h (find(element, h0), "h"); 
/*{*/h.show();
/*{*/ // /*}*/      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");
/*{*/VisibleInteger h0 (hash(element), "h0"); 
/*{*/ // /*}*/      unsigned h0 = hash(element);
/*{*/VisibleInteger h (find(element, h0), "h"); 
/*{*/h0.show(); 
/*{*/h.show();
/*{*/ // /*}*/      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");
/*{*/VisibleInteger h00 (h0, "h0"); 
/*{*/h00.show();
/*{*/VisibleInteger h (h0 % hSize, "h"); 
/*{*/h.show();
/*{*/ // /*}*/      unsigned h = h0 % hSize;
/*{*/VisibleInteger count (0, "count");
/*{*/count.show();
/*{*/ // /*}*/      unsigned count = 0;
/*{*/table[h].highlight(AlgAE::Yellow);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;/*{*/table[h].highlight(AlgAE::Yellow); /*}*/
        }
/*{*/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