/**
@file aisdihashmap.h

AISDIHashMap and related functions interface.

@author
Pawel Cichocki

@date
last revision
- 2006.03.24 Pawel Cichocki: wrote it

COPYRIGHT:
Copyright (c) 2006 Instytut Informatyki, Politechnika Warszawska
ALL RIGHTS RESERVED
*******************************************************************************/

#include <utility>
#include <string>
#include <iterator>

#define SIZE 65536
/// Default keys' comparing function for AISDIHashMap - it uses
/// operator== by default.
/// @returns true if keys are equal, false otherwise.
/// @param key1 First key to compare.
/// @param key2 Second key to compare.
template <class Key>
inline bool _compFunc(const Key& key1, const Key& key2)
{
    return (key1 == key2);
};

inline unsigned hashF(const std::string& m)
{
    unsigned h = 0;
    int i;

    for (i = 0; i < m.length(); i++)
        h ^= (h << 5) + (h >> 2) + m[i];
    return h & 0xFFFF;
};
/// A map with a similar interface to std::map.
template<class K, class V,
    unsigned hashFunc(const K&),
    bool compFunc(const K&, const K&) = &_compFunc<K> >
class AISDIHashMap
{
public:
    typedef K key_type;
    typedef V value_type;
    typedef unsigned size_type;

    /* klasa reprezentujaca element pierscienia*/
    class Node
    {
    public:
        std::pair<K, V> data;
        Node* next;
        Node* prev;
        unsigned hashIndex; /* indeks w tablicy z hashowaniem */
        Node(const std::pair<K, V>& d, unsigned hashnr) : data(d), next(NULL), prev(NULL), hashIndex(hashnr) { }
    };

private:
    Node* sentinel; /* wskaznik na straznika */
    Node* hashTable[SIZE];  /* tablica 65536 wskaznikow na elementy pierscienia*/

public:
    AISDIHashMap()
    {
        sentinel = new Node(std::make_pair(K(), V()));  /* tworzymy straznika */
        sentinel->next = sentinel;  /* "uszy" straznika - pokazuje na siebie */
        sentinel->prev = sentinel;
        for (int i = 0; i < SIZE; i++)  /* inicjalizacja tablicy wskaznikow NULLem*/
            hashTable[i] = NULL;
    }
    ~AISDIHashMap()
    {
        clear();    /* usuwamy wszystkie elementy */
        delete sentinel; /* i jeszcze straznik */
    }

    /// Coping constructor.
    explicit AISDIHashMap(const AISDIHashMap<K, V, hashFunc, compFunc>& a)
    {
        const_iterator i;                       /* kopiujemy pozostale elementy */
        Node* ptr = NULL;   /* wskaznik na ostatnio wstawiany element, na poczatku rowny NULL*/
        Node* first;
        int flag = 0;
        for (i = a.begin(); i != a.end(); ++i)
        {
            Node* new_ptr = new Node(a.node->data, a.node->hashIndex);
            if (ptr == NULL)    /* kopiujemy pierwszy element */
            {
                first = new_ptr;
                flag = 1;
            }
            else /* kopiujemy kolejne elementy juz oprocz pierwszego */
            {
                new_ptr->prev = ptr;
                ptr->next = new_ptr;
            }
            if (a.node->hashIndex != a.node->prev->hashIndex)   /* przypisanie wskazania jesli pierwszy hash */
            {
                hashTable[hashIndex] = new_ptr;
            }
            ptr = new_ptr;
        }
        sentinel = new Node(std::make_pair(K(), V()));  /* tworzymy straznika nowej listy*/
        if (flag == 1)
        {   /* laczymy straznika z ostatnim i tworzymy pierscien */
            sentinel->prev = ptr;
            sentinel->next = first;
            first->prev = sentinel;
            ptr->next = sentinel;
        }
        else
        {
            /* jesli tylko straznik */
            sentinel->next = sentinel;
            sentinel->prev = sentinel;
        }
    }
    /// const_iterator.
    class const_iterator : public std::iterator < std::forward_iterator_tag,
        std::pair<K, V> >
    {
    protected:
        Node* node;     /* iterator przechowujacy wskaznik na element */
        friend class AISDIHashMap;
        const_iterator(Node* x) : node(x) {}
    public:
        typedef std::pair<K, V> T;
        const_iterator() {}
        const_iterator(const const_iterator& a) : node(a.node) {}
        // operatory
        inline const T& operator*() const
        {
            return node->data;
        }

        inline const T* operator->() const
        {
            return &(node->data);
        }
        /* preincrementacja */
        const_iterator& operator++()
        {
            node = node->next;
            return *this;
        }
        /* postincrementacja */
        const_iterator operator++(int)
        {
            const_iterator temp = *this;
            ++*this;
            return temp;
        }
        /* predekrementacja */
        const_iterator& operator--()
        {
            node = node->prev;
            return *this;
        }
        /* postdekrementacja */
        const_iterator operator--(int)
        {
            const_iterator temp = *this;
            --*this;
            return temp;
        }
        inline bool operator==(const const_iterator& a) const
        {
            return node == a.node;
        }
        inline bool operator!=(const const_iterator& a) const
        {
            return node != a.node;
        }
    };

    /// iterator.
    class iterator : public const_iterator
    {
        iterator(Node* x) : const_iterator(x) {}
        friend class AISDIHashMap;
    public:
        iterator() {}
        iterator(const iterator& a) { node = a.node; }

        inline T& operator*() const
        {
            return node->data;
        }
        inline T* operator->() const
        {
            return &(node->data);
        }
        /* preinkrementacja */
        iterator& operator++()
        {
            ++(*(const_iterator*)this);
            return (*this);
        }
        /* postinkrementacja */
        iterator operator++(int)
        {
            iterator temp = *this;
            ++*this;
            return temp;
        }
        /* predekrementacja */
        iterator& operator--()
        {
            --(*(const_iterator*)this);
            return (*this);
        }
        /* postdekrementacja */
        iterator operator--(int)
        {
            iterator temp = *this;
            --*this;
            return temp;
        }
    };

    /// Returns an iterator addressing the first element in the map.
    inline iterator begin()
    {
        return iterator(sentinel->next);
    }
    inline const_iterator begin() const
    {
        return const_iterator(sentinel->next);
    }

    /// Returns an iterator that addresses the location succeeding the last element in a map.
    inline iterator end()
    {
        return iterator(sentinel);
    }
    inline const_iterator end() const
    {
        return const_iterator(sentinel);
    }

    /// Inserts an element into the map.
    /// @returns A pair whose bool component is true if an insertion was
    ///          made and false if the map already contained an element
    ///          associated with that key, and whose iterator component coresponds to
    ///          the address where a new element was inserted or where the element
    ///          was already located.
    std::pair<iterator, bool> insert(const std::pair<K, V>& entry)
    {
        iterator i = find(entry.first);
        if (i != end())
            return std::make_pair(i, false);            /* jesli juz istnieje element o danym kluczu, to wstawianie nie powiodlo sie */
        /* element nie istnieje, dlatego musimy go wstawic */
        unsigned hash = hashFunc(entry.first);  /* liczymy hash elementu */
        i.node = hashTable[hash];

        if (hashTable[hash] != NULL)    /* jesli jest element o danym hashu, to nowy wstawiamy na poczatku */
        {
            Node* newElement = new Node(entry, hash);
            newElement->next = i.node;
            newElement->prev = i.node->prev;
            i.node->prev->next = newElement;
            i.node->prev = newElement;
            hashTable[hash] = newElement;
            return std::make_pair(i, true); /* wstawianie powiodlo sie */
        }
        else    /* jesli nie ma elementow o takim hashu, to wstawiamy element za straznikiem */
        {
            Node* newElement = new Node(entry, hash);
            newElement->next = sentinel->next;
            newElement->prev = sentinel;
            sentinel->next->prev = newElement;
            sentinel->next = newElement;
            hashTable[hash] = newElement;
            return std::make_pair(i, true); /* wstawianie powiodlo sie */
        }
    }

    /// Returns an iterator addressing the location of the entry in the map
    /// that has a key equivalent to the specified one or the location succeeding the
    /// last element in the map if there is no match for the key.
    iterator find(const K& k)
    {
        unsigned hash = hashFunc(k);    /* liczymy hash elementu */

        if (hashTable[hash] == NULL)    /* jesli nie ma elementow o takim hashu, to zwracamy straznika */
            return end();

        iterator i;
        i.node = hashTable[hash];   /* ustawiamy iterator na wyliczonym hashu */

        while (i.node->hashIndex == hash)   /* przegladamy elementy o takim samym hashu */
        {
            if (i.node->data.first == k)            /* jesli znajdziemy element o takim samym kluczu, to zwracamy iterator ustawiony na tym elemencie */
                return i;
            i++;
        }
        return end();                       /* nie ma elementu o kluczu k; zwracamy straznika */
    }

    /// Returns an const iterator
    const_iterator find(const K& k) const
    {
        unsigned hash = hashFunc(k);    /* liczymy hash elementu */

        if (hashTable[hash] == NULL)    /* jesli nie ma elementow o takim hashu, to zwracamy straznika */
            return end();

        iterator i;
        i.node = hashTable[hash];   /* ustawiamy iterator na wyliczonym hashu */
        while (i.node->hashIndex == hash)   /* przegladamy elementy o takim samym hashu */
        {
            if (i.node->data.first == k)            /* jesli znajdziemy element o takim samym kluczu, to zwracamy iterator ustawiony na tym elemencie */
                return i;
            i++;
        }
        return end();                       /* nie ma elementu o kluczu k; zwracamy straznika */
    }

    /// Inserts an element into a map with a specified key value
    /// if one with such a key value does not exist.
    /// @returns Reference to the value component of the element defined by the key.
    V& operator[](const K& k)
    {
        return insert(std::make_pair(k, V())).first->second;
    }

    /// Tests if a map is empty.
    bool empty() const
    {
        return sentinel->next == sentinel;
    }

    /// Returns the number of elements in the map.
    size_type size() const
    {
        iterator i;
        size_type mapSize = 0;
        for (i = begin(); i != end(); i++)
            mapSize++;
        return mapSize;
    }

    /// Returns the number of elements in a map whose key matches a parameter-specified key.
    size_type count(const K& _Key) const
    {
        return find(_Key) != end();
    }

    /// Removes an element from the map.
    /// @returns The iterator that designates the first element remaining beyond any elements removed.
    iterator erase(iterator i)
    {
        if (i == end())     /* jest tylko straznik - pusta mapa */
            return end();
        if (i.node == hashTable[i.node->hashIndex])
        {
            if (i.node->hashIndex == i.node->next->hashIndex && i.node->next != sentinel)   /* jesli pierwszy element o danym hashu */
                hashTable[i.node->hashIndex] = i.node->next;
            else
                hashTable[i.node->hashIndex] = NULL;
        }
        Node* temp = i.node->next;              /* usuwanie elementu */
        i.node->next->prev = i.node->prev;
        i.node->prev->next = i.node->next;
        delete i.node;
        return iterator(temp);
    }
    /// Removes a range of elements from the map.
    /// The range is defined by the key values of the first and last iterators
    /// first is the first element removed and last is the element just beyond the last element removed.
    /// @returns The iterator that designates the first element remaining beyond any elements removed.
    iterator erase(iterator first, iterator last)
    {
        iterator i = first;
        while (i != last)
        {
            Node* temp = i.node->next;
            erase(i);
            i.node = temp;
        }
        return last;
    }

    /// Removes an element from the map.
    /// @returns The number of elements that have been removed from the map.
    ///          Since this is not a multimap it should be 1 or 0.
    size_type erase(const K& key)
    {
        iterator i = find(key);
        if (i != end())
        {
            erase(i);
            return 1;
        }
        else
            return 0;
    }
    /// Erases all the elements of a map.
    void clear()
    {
        erase(begin(), end());
    }
};