text: #ifndef HASHTABLE_H
  #define HASHTABLE_H
  
  #include <functional>
  #include <iostream>
  #include <vector>
  namespace SDFGen
  {
  template<class Key, class Data>
  struct HashEntry
  {
     Key key;
     Data data;
     int next;
  };
  
  // a useful core hash function
  inline unsigned int hash(unsigned int k)
  { return k*2654435769u; }
  
  // default hash function object
  struct DefaultHashFunction
  {
     template<typename Key>
     unsigned int operator() (const Key &k) const { return hash(k); }
  };
  
  struct equal
  {
     template<typename T>
     bool operator() (const T &a, const T &b) const { return a==b; }
  };
  
  template<typename Key, typename Data, class HashFunction=DefaultHashFunction, class KeyEqual=equal>
  struct HashTable
  {
     unsigned int table_rank;
     unsigned int table_bits;
     std::vector<int> table;
     unsigned int num_entries;
     std::vector<HashEntry<Key, Data> > pool;
     int free_list;
     const HashFunction hash_function;
     const KeyEqual key_equal;
  
     explicit HashTable(unsigned int expected_size=64)
        : hash_function(HashFunction()), key_equal(KeyEqual())
     { init(expected_size); }
  
     explicit HashTable(const HashFunction &hf, unsigned int expected_size=64)
        : hash_function(hf), key_equal(KeyEqual())
     { init(expected_size); }
  
     void init(unsigned int expected_size)
     {
        unsigned int i;
        num_entries=0;
        table_rank=4;
        while(1u<<table_rank < expected_size)
           ++table_rank;
        ++table_rank; // give us some extra room
        table_bits=(1u<<table_rank)-1;
        table.resize(1u<<table_rank);
        for(i=0; i<table.size(); ++i)
           table[i]=-1; // empty list
        pool.resize(1u<<table_rank);
        free_list=0;
        for(unsigned int i=0; i<pool.size()-1; ++i)
           pool[i].next=i+1;
        pool[pool.size()-1].next=-1; // end of free list
     }
  
     void add(const Key &k, const Data &d)
     {
        if(free_list==-1)
           reserve(1u<<(table_rank+1));
        int i=free_list; // where we're going to put the new entry
        free_list=pool[i].next;
        unsigned int t=hash_function(k)&table_bits; // index into table
        pool[i].key=k;
        pool[i].data=d;
        pool[i].next=table[t]; // put the new entry at the start of table[t]'s list
        table[t]=i;
        ++num_entries;
     }
  
     void delete_entry(const Key &k, const Data &d) // delete first entry that matches both key and data
     {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t], *p_i=&table[t];
        while(i!=-1){
           if(key_equal(k, pool[i].key) && d==pool[i].data){
              *p_i=pool[i].next; // make list skip over this entry
              pool[i].next=free_list; // and put it on the front of the free list
              free_list=i;
              return; // and we're done
           }
           p_i=&pool[i].next;
           i=*p_i;
        }
     }
  
     unsigned int size() const
     { return num_entries; }
  
     void clear()
     {
        unsigned int i=0;
        num_entries=0;
        for(i=0; i<table.size(); ++i)
           table[i]=-1; // empty list
        free_list=0;
        for(i=0; i<pool.size()-1; ++i)
           pool[i].next=i+1;
        pool[pool.size()-1].next=-1;
     }
  
     void reserve(unsigned int expected_size)
     {
        if(expected_size<=pool.size())
           return;
        while(1u<<table_rank < expected_size)
           ++table_rank;
        table_bits=(1u<<table_rank)-1;
        // increase room for new entries
        unsigned int old_size=(unsigned int)pool.size(), i;
        pool.resize(1u<<table_rank);
        for(i=old_size; i<pool.size()-1; ++i)
           pool[i].next=i+1;
        pool[i].next=free_list;
        free_list=old_size;
        // And finally need to redo table (rehash entries)
        old_size=(unsigned int)table.size();
        table.resize(1u<<table_rank);
        unsigned int t;
        for(t=old_size; t<table.size(); ++t)
           table[t]=-1; // initially make new lists empty
        int j, *p_j;
        for(t=0; t<old_size; ++t){
           j=table[t]; 
           p_j=&table[t];
           while(j!=-1){
              unsigned int new_t=hash_function(pool[j].key)&table_bits;
              if(new_t!=t){ // j doesn't belong in this list anymore?
                 // delete from this list
                 *p_j=pool[j].next;
                 // add to correct list
                 pool[j].next=table[new_t];
                 table[new_t]=j;
              }else
                 p_j=&(pool[j].next);
              j=*p_j;
           }
        }
     }
  
     bool has_entry(const Key &k) const
     {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
           if(key_equal(k, pool[i].key))
              return true;
           i=pool[i].next;
        }
        return false;
     }
  
     bool get_entry(const Key &k, Data &data_return) const
     {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
           if(key_equal(k, pool[i].key)){
              data_return=pool[i].data;
              return true;
           }
           i=pool[i].next;
        }
        return false;
     }
  
     void append_all_entries(const Key& k, std::vector<Data>& data_return) const
     {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
           if(key_equal(k, pool[i].key)) data_return.push_back(pool[i].data);
           i=pool[i].next;
        }
     }
  
     Data &operator() (const Key &k, const Data &missing_data)
     {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
           if(key_equal(k, pool[i].key))
              return pool[i].data;
           i=pool[i].next;
        }
        add(k, missing_data); // note - this could cause the table to be resized, and t made out-of-date
        return pool[table[hash_function(k)&table_bits]].data; // we know that add() puts it here!
     }
  
     const Data &operator() (const Key &k, const Data &missing_data) const
     {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
           if(key_equal(k, pool[i].key))
              return pool[i].data;
           i=pool[i].next;
        }
        return missing_data;
     }
  
     void output_statistics() const
     {
        std::vector<int> lengthcount(table.size());
        unsigned int t;
        int total=0;
        for(t=0; t<table.size(); ++t){
           int i=table[t], length=0;
           while(i!=-1){
              ++length;
              i=pool[i].next;
           }
           ++lengthcount[length];
           ++total;
        }
        int subtotal=0;
        int maxlength=0;
        for(t=0; t<lengthcount.size() && t<10; ++t){
           subtotal+=lengthcount[t];
           if(lengthcount[t]>0){
              std::cout<<"length "<<t<<": "<<lengthcount[t]<<"   ("<<lengthcount[t]/(float)total*100.0<<"%)"<<std::endl;
              maxlength=t;
           }
        }
        std::cout<<"rest: "<<total-subtotal<<"   ("<<100.0*(1.0-subtotal/(float)total)<<"%)"<<std::endl;
        for(; t<lengthcount.size(); ++t)
           if(lengthcount[t]>0)
              maxlength=t;
        std::cout<<"longest list: "<<maxlength<<std::endl;
     }
  };
  }
  #endif
  