hashtable.hpp

Go to the documentation of this file.

#ifndef HASHTABLE_HPP
#define HASHTABLE_HPP

#ifndef END
#define END nullptr
#endif

#ifndef ARRAYSIZE
#define ARRAYSIZE 25
#endif

// included files section
#include <string>
#include <cassert>
#include <utility>
#include <forward_list>

// will desactive cassert
#define NDEBUG

using std::string;
using std::pair;
using std::forward_list;

template <typename K> unsigned computehash(K element);

class HashtableException : std::exception {
    private:
        const char* _cause; 
    public:
        HashtableException(const char* cause):
        _cause(cause)
        {}

        virtual ~HashtableException() throw(){
            // do nothing
        }

        virtual const char* what()const throw(){
            return _cause;
        }
};

// TODO: implement iterator to browse within alveoles very quickly and easely
template <typename K, typename V>
class Alveole{
    private:
        K _key; 
        V _value; 
        Alveole<K,V>* _next; 
    public:
        Alveole(const Alveole<K,V> &other):
        _key(other._key),
        _value(other._value)
        {
            // if there are elements coming next
            if(END != other._next){
                _next = new Alveole(other._next);
            }
            else {
                _next = END;
            }
        }

        Alveole(K key, V value) :
        _key(key), _value(value),
        _next(END)
        {}

        Alveole() : _next(END){};

        Alveole(K key, V value, Alveole<K,V>* next):
        _key(key),
        _value(value),
        _next(next)
        {}

        ~Alveole(){
            //delete &_key;
            //delete &_value;
            //delete _next;
        }

        K getKey(){ return _key; }

        V getValue(){ return _value; }

        Alveole<K,V>* getNext(){ return _next; }

        void setValue(V n_value){ _value = n_value; }

        void setNext(Alveole<K,V>* n_next){ _next = n_next; }

        string toString(){
            string desc = "{" + _key + ", " + _value + "}";
            if(END == _next){
                return desc;
            } else {
                return desc + ", " + _next->toString();
            }
        }
};

template <typename K, typename V>
class Hashtable {

    private:
        Alveole<K,V>** _table; 
    public:
        Hashtable(){
            _table = new Alveole<K,V>*[ARRAYSIZE];
            for(int i = 0; i<ARRAYSIZE; ++i){
                _table[i] = END;
            }
        }

        ~Hashtable(){
            delete[] _table;
        }

        bool contains(const K &key){
            bool here = false;
            int index = computehash<K>(key)%ARRAYSIZE;
            assert(index>=0);
            assert(index<ARRAYSIZE);
            Alveole<K,V>* browser = _table[index];
            while(not here and END != browser){
                if(key == browser->getKey()){
                    here = true;
                }
                browser = browser->getNext();
                }
            return here;
        }

        V get(const K &key){
            int index = computehash<K>(key)%ARRAYSIZE;
            assert(index>=0);
            assert(index<ARRAYSIZE);
            Alveole<K,V>* browser = _table[index];
            bool undone = true;
            while(undone and END != browser){
                if(key == browser->getKey()){
                    undone = false;
                }
                else {
                    browser = browser->getNext();
                }
            }
            if(undone){
                throw HashtableException("Key not found!");
            } else {
                return browser->getValue();
            }
        }

        bool isEmpty(){
            bool empty = true;
            int i = 0;
            while(empty and i<ARRAYSIZE){
                empty = (END == _table[i++]);
            }
            return empty;
        }

        // TODO: optimize this fucking code
        void put(K key, V value){
            // where to put the pair ?
            int index = computehash<K>(key)%ARRAYSIZE;
            assert(index>=0);
            assert(index<ARRAYSIZE);
            // browse alveoles at this place
            Alveole<K,V>* browser = _table[index];
            bool undone = true;
            while(undone and END != browser){
                if(key == browser->getKey()){
                    //std::cout << "Updating (" << key << ", " << value <<") at " << index << std::endl; // debug line
                    browser->setValue(value);
                    undone = false;
                }
                browser = browser->getNext();
            }
            if(undone){
                _table[index] = new Alveole<K,V>(key, value, _table[index]);
                //std::cout << "Adding (" << key << ", " << value <<") at " << index << std::endl; // debug line
            }
        }

        void remove(const K &key){
            int index = computehash<K>(key)%ARRAYSIZE;
            assert(index>=0);
            assert(index<ARRAYSIZE);
            Alveole<K,V>* bef = new Alveole<K,V>();
            bef->setNext(_table[index]);
            Alveole<K,V>* cur = _table[index];
            bool undone = true;
            while(undone and END != cur){
                //std::cout << cur->toString() << std::endl; // debug line
                if(key == cur->getKey()){
                    bef->setNext(cur->getNext());
                    assert(bef->getNext() == cur->getNext());
                    undone = false;
                    delete cur;
                }
                else {
                    assert(cur != END);
                    bef = cur;
                    cur = cur->getNext();
                }
            }
            if(undone) throw HashtableException("Key is not here!");
        }

        string toString(){
            string desc = "[";
            for(int i = 0; i<ARRAYSIZE; ++i){
                if(END != _table[i]){
                    desc.size()<2?desc += (_table[i]->toString()):desc += ", " + (_table[i]->toString());
                }
            }
            return desc + "]";
        }
        
         void getPairs(forward_list<pair<string, int>> &pairs){
            // we can browse Alveole with it
            Alveole<K, V>* browser;
            // For each cell in _table
            for(int i=0; i<ARRAYSIZE; ++i){
                // browse alveoli here
                browser = _table[i];
                while(END != browser){
                    pairs.push_front(pair<string, int>(browser->getKey(), browser->getValue()));
                    browser = browser->getNext();
                }
            }
        }

};

#endif // HASHTABLE_HPP