hashset.h~

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

#ifndef HASHSET_H
#define HASHSET_H

//
//	Hash table implementation of set
//
//	Described in Chapter 17 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, [e-mail]
//	Oregon State University
//
//      SJZ: Heavily modified, combined two classes,
//           used list for set container, added erase function,
//           added comparison template parameter, const's
#include <utils/visint.h>
#include <utils/visptr.h>

#include <algorithm>
#include <functional>


template <class T>
struct ListNode: public Visible
{
  T data;
  ListNode<T>* next;
  
  ListNode(AlgAE::Color c = AlgAE::PaleMagenta)
    : Visible(c)
    {next = 0;};

  virtual ~ListNode() {}

  ListNode(const T& t, ListNode<T>* n,
           AlgAE::Color c = AlgAE::PaleMagenta)
    : data(t), Visible(c)   {next = n;}


  ////////////////////////////////////////////////
  // Required for animation
  virtual void touchAllPointers() const
    {
      touch (next, AlgAE::E);
    }
  
  virtual void writeText (ostream & out) const
    {
      out << data;
    }
};


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

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

  int size() const  {return theSize;}

  int count (const T& element) const
    {/*{*/algae->FRAME("starting count");
      const Bucket& theBucket = bucket(element);
/*{*/theBucket.highlight(); algae->FRAME("found the bucket, search for the element");	  
     return findInBucket(theBucket, element) != 0;
     }

  void insert (const T& element)
    {/*{*/algae->FRAME("starting insert");
      Bucket& theBucket = bucket(element);
/*{*/algae->FRAME("found the bucket, search for the element.");	  
      Bucket pos = findInBucket(theBucket, element);
/*{*/theBucket.highlight(); pos.setName("pos"); pos.show(); 
      if (pos == 0)
        {/*{*/algae->FRAME("this is a new element - add to chain");	  
	  Bucket newNode = new ListNode<T>(element, theBucket);
	  theBucket = newNode;
	  ++theSize;
	}
      else /*{*/{algae->FRAME("this element is already in the chain - replace");	  
        pos->data = element;/*{*/} /*}*/
/*{*/algae->FRAME("completed insert");
    }

  void erase (const T& element)
    {/*{*/algae->FRAME("starting erase");
      Bucket& theBucket = bucket(element);
/*{*/algae->FRAME("found the bucket, search for the element to remove");
      Bucket pos = findInBucket(theBucket, element);
/*{*/theBucket.highlight(); pos.setName("pos"); pos.show(); 
      if (pos != 0)
        {/*{*/algae->FRAME("found the element - remove it");	  
	 if (theBucket == pos)
	   {
	     theBucket = pos->next;
	   } 
	 else
	   {
	     Bucket prev = theBucket;
	     while (prev->next != pos)
	       prev = prev->next;
	     prev->next = pos->next;
	   }
	 delete pos/*{*/.operator->()/*}*/;
	 --theSize;
	}/*{*/else algae->FRAME("element is not in the set");	  
/*{*/algae->FRAME("completed erase");
    }


  void clear()
    {
      theSize = 0;
      for (int i = 0; i < hSize; ++i)
	{
/*{*/	  buckets[i].setName(itos(i));/*}*/
	  ListNode<T>* p;
	  while (buckets[i] != 0)
	    {
	      p = buckets[i];
	      buckets[i] = buckets[i]->next;
	      delete p;
	    }
	  
	} 
    }

  

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

/*{*/  Bucket& bucket (const T& element)
/*{*/ // /*}*/  ListNode<T>*& bucket (const T& element)
    {/*{*/VisibleInteger h = hash(element);
/*{*/h.setName("hash value"); h.show();
/*{*/buckets[h % hSize].highlight();
/*{*/algae->FRAME("hashing to this bucket");
      return buckets[hash(element) % hSize];
    }

/*{*/  Bucket bucket (const T& element) const
/*{*/ // /*}*/  const ListNode<T>* bucket (const T& element) const
    {/*{*/VisibleInteger h = hash(element);
/*{*/h.setName("hash value"); h.show();
/*{*/buckets[h % hSize].highlight();
/*{*/algae->FRAME("hashing to this bucket.");
     return buckets[hash(element) % hSize];
    }
  
  ListNode<T>* findInBucket (Bucket b, const T& element)
    {
      ListNode<T>* p = b;
      while (p != 0 && !compare(p->data, element))
	p = p->next;
      return p;
    }
  
  const ListNode<T>* findInBucket (Bucket b, const T& element) const
    {
      const ListNode<T>* p = b;
      while (p != 0 && !compare(p->data, element))
	p = p->next;
      return p;
    }
  

  Bucket buckets[hSize];
  HashFun hash;
  CompareEQ compare;
  int theSize;
};


#endif