/Users/jab/Documents/Teaching/02585/GEL2_and_demos/GEL/src/Util/HashTable.h

#ifndef __UTIL_HASHTABLE_H
#define __UTIL_HASHTABLE_H

#include "HashKey.h"

#include <functional>
#include <iostream>

namespace Util
{

        namespace
        {
                const int HASH_EXPAND_LOAD = 80;
        };

        template<class KEY_T, class VAL_T>
        class HashTable
        {
                struct EntryType
                {
                        // Hash key
                        KEY_T key;

                        VAL_T val;

                        signed char ref;
                
                public:
                        EntryType(): ref(-1) {}
                };
        
                EntryType* table;   

        private:

                int items;          
  
                int size;       

                void resize(int new_size);

                bool find_entry_priv(const KEY_T&, int&) const;
  
        public:

                HashTable(): items(0), size(1) 
                {
                        table = new EntryType[size];
                }

                ~HashTable() { delete [] table; }

                bool create_entry(const KEY_T&, const VAL_T&,int=0);

                bool create_entry(const KEY_T& kv, VAL_T*& val, int incr=0);



                bool remove_entry(const KEY_T&);

                bool find_entry(const KEY_T&, VAL_T&) const;

                bool decr_reference(const KEY_T&, VAL_T&, int=1);


                bool change_entry(const KEY_T&, const VAL_T&);

                void print() const;

                bool get_first(int& idx, KEY_T&,VAL_T& val,int&) const;

                bool get_next(int& idx, KEY_T&,VAL_T& val,int&) const;

                int integrate() const; 


                int no_items() const {return items;}

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

                int total_size() const {return sizeof(*this) + sizeof(EntryType)*size;}

                static int entry_size() {return sizeof(EntryType);}
        
        };


        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::find_entry_priv(const KEY_T& kv, int& k) const
        {
                k = kv.hash(size);
                int fk = k;
                while(table[k].ref != -1)
                        {
                                if (table[k].key == kv) 
                                        return (table[k].ref > 0) ? true : false;
                                k = (k+1)&(size-1);
                                if (k==fk) break;
                        }
                return false;
        }

        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::find_entry(const KEY_T& kv, VAL_T& val) const
        {
                int k;
                if(find_entry_priv(kv,k))
                        {
                                val = table[k].val;
                                return true;
                        }
                return false;
        }

        template<class KEY_T, class VAL_T>
        void HashTable<KEY_T, VAL_T>::resize(int new_size)
        { 
                int j=0;
                EntryType* tmp_table = new EntryType[new_size];
                for(int i=0; i<size;i++)
                        if (table[i].ref >0)
                                {
                                        j++;
                                        int k = table[i].key.hash(new_size);
                                
                                        while(tmp_table[k].ref != -1) 
                                                k=(k+1)&(new_size-1); 
                                
                                        tmp_table[k].key = table[i].key;
                                        tmp_table[k].val = table[i].val;
                                        tmp_table[k].ref = table[i].ref;
                                }
      
                delete table;
                table = tmp_table;
                size = new_size;
        }

        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::create_entry(const KEY_T& kv, 
                                                                                                                                                                                 const VAL_T& val,
                                                                                                                                                                                 int incr)
        {
                if (items*100 >= HASH_EXPAND_LOAD * size) 
                        resize(size*2);

                int k;
                if(!find_entry_priv(kv,k))
                        {
                                ++items;
                                table[k].ref = (incr==0? 1: incr);
                                table[k].key = kv;
                                table[k].val = val;
                                return true;
                        }
                table[k].ref += incr;
                table[k].val = val;
                return false;
        }

        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::create_entry(const KEY_T& kv, 
                                                                                                                                                                                 VAL_T*& val,
                                                                                                                                                                                 int incr)
        {
                if (items*100 >= HASH_EXPAND_LOAD * size) 
                        resize(size*2);

                int k;
                if(!find_entry_priv(kv,k))
                        {
                                ++items;
                                table[k].ref = (incr==0? 1: incr);
                                table[k].key = kv;
                                val = &table[k].val;
                                return true;
                        }
                table[k].ref += incr;
                val=&table[k].val;
                return false;
        }


        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::remove_entry(const KEY_T& kv)
        {
                int k;
                if(find_entry_priv(kv,k))
                        {
                                table[k].ref = 0;
                                --items;
                                if(items*100 < (HASH_EXPAND_LOAD * size) / 2)
                                        resize(size/2);
                                return true;
                        }
                return false;
        }



        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::decr_reference(const KEY_T& kv,  
                                                                                                                                                                                         VAL_T& val, 
                                                                                                                                                                                         int decr)
        {
                int k;
                if(find_entry_priv(kv,k))
                        {
                                table[k].ref -= decr;
                                val = table[k].val;
                                if(table[k].ref == 0)
                                        {
                                                --items;
                                                if(items*100 < (HASH_EXPAND_LOAD * size) / 2)
                                                        resize(size/2);
                                        }
                                return true;
                        }
                return false;
        }

        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::change_entry(const KEY_T& kv,  
                                                                                                                                                                                 const VAL_T& val)
        {
                int k;
                if(find_entry_priv(kv,k))
                        {
                                table[k].val = val;
                                return true;
                        }
                return false;
        }


        template<class KEY_T, class VAL_T>
        void HashTable<KEY_T, VAL_T>::print() const
        {
                std::cout << "Entry size " << sizeof(EntryType) << " bytes\n"
                                                        << "Max number of items " << size       << "\n" 
                                                        << "Number of items " << items << std::endl;
        }

        template<class KEY_T, class VAL_T>
        int HashTable<KEY_T, VAL_T>::integrate() const 
        {
                int integral =0;
                for(int i=0;i<size; i++)
                        if(table[i].ref>0) integral += table[i].ref;
                return integral;
        }

        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::get_first(int& idx, 
                                                                                                                                                                        KEY_T& key,
                                                                                                                                                                        VAL_T& val,
                                                                                                                                                                        int& r) const 
        {
                if(size==0) return false;
        
                idx=0;
                while(table[idx].ref <= 0)
                        {
                                ++idx;
                                if(idx==size) return false;
                        }
                key = table[idx].key;
                val = table[idx].val;
                r   = table[idx].ref;
                return true;
        }

        template<class KEY_T, class VAL_T>
        bool HashTable<KEY_T, VAL_T>::get_next(int& idx, 
                                                                                                                                                                 KEY_T& key,
                                                                                                                                                                 VAL_T& val,
                                                                                                                                                                 int& r) const
        {
                idx++;
                if(idx==size) return false;
                while(table[idx].ref <= 0)
                        {
                                ++idx;
                                if(idx==size) return false;
                        }
                key = table[idx].key;
                val = table[idx].val;
                r   = table[idx].ref;
                return true;
        }

}


#endif