/**
@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 <iostream>
#include <utility>
#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)
{
  // djb2
  unsigned hash = 5381;
  for(auto c : m)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
  return hash & 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;
private:

   struct Node {
      std::pair <key_type, value_type> data;
      unsigned hash; // hash for key
      Node *next;
      Node(const Node &a) : data(a.data),hash(a.hash), next(a.next) {}
      Node(std::pair<K, V> d, unsigned h, Node *ptr = nullptr):
         data(d), hash(h), next(ptr) {}

   };

   Node* hashtab[SIZE];
   unsigned counter;

public:
   AISDIHashMap(){
      for(unsigned i=0; i<SIZE; ++i)
         hashtab[i] = nullptr;
      counter = 0;

   }
   ~AISDIHashMap(){
      clear();
   }

   /// Coping constructor.
   explicit AISDIHashMap(const AISDIHashMap<K, V, hashFunc, compFunc>& a){
      counter = 0;
      for(unsigned i=0; i<SIZE; ++i)
         hashtab[i] = nullptr;
      const_iterator end_loop = a.end();
      for ( const_iterator i = a.begin(); i != end_loop; ++i)
        insert(i.node->data);
   }

   /// const_iterator.
   class const_iterator: public std::iterator<std::forward_iterator_tag,
                                              std::pair<K, V> > {
      friend class AISDIHashMap;

   protected:
      Node * node;
      AISDIHashMap * map;
   public:
      typedef std::pair<K, V> T;
      const_iterator() {}
      const_iterator(const const_iterator& a) : node(a.node), map(a.map) {}
      const_iterator(Node* n, AISDIHashMap* m): node(n), map(m) {}

        inline const T* operator*() const
        {
          return (T&)node->data;
        }

        inline const T* operator->() const
        {
          return &(node->data);
        }

      const_iterator& operator++() {
            if( node == nullptr) return *this;
            if( node->next != nullptr) {
               node = node->next;
               return *this;
            }
            //starting looking for new node but we know that it is not
            //in current_index so we have to increment it when we start
            unsigned current_index = node->hash + 1;
            for(; current_index < SIZE; ++current_index) {
               node = map->hashtab[current_index];
               if (node != nullptr) break;
            }
            return *this;
        }


      const_iterator operator++(int) {
        const_iterator temp = *this;
        ++(*this);
        return temp;
      }

      bool operator==(const const_iterator& a) const
      {
        return node == a.node;
      }

      bool operator!=(const const_iterator& a) const
      {
        return node != a.node;
      }

   };
   /// iterator.
   class iterator : public std::iterator<std::forward_iterator_tag,
                                              std::pair<K, V> > {
      friend class AISDIHashMap;
      // inheritance doesnt work for these two:
      Node * node;
      AISDIHashMap * map;
    public:
      typedef std::pair<K, V> T;
      iterator() {}
      iterator(const iterator& a) : node(a.node), map(a.map) {}
      iterator(Node* n, AISDIHashMap* m): node(n), map(m) {}

      inline T* operator*()
      {
          return (T&)node->data;
      }

      inline T* operator->()
      {
          return &(node->data);
      }

      iterator& operator++()   // pre
      {
         if( node == nullptr) return *this;
         if( node->next != nullptr) {
            node = node->next;
            return *this;
         }
         //starting looking for new node but we know that it is not
         //in current_index so we have to increment it when we start
         unsigned current_index = node->hash + 1;
         for(; current_index < SIZE; ++current_index) {
            node = map->hashtab[current_index];
            if (node != nullptr) break;
         }
         return *this;
      }

      iterator operator++(int) // post
      {
        iterator temp = *this;
        ++*this;
        return temp;
      }

      bool operator==(const iterator& a)
      {
        return node == a.node;
      }

      bool operator!=(const iterator& a)
      {
        return node != a.node;
      }

   };

   /// Returns an iterator addressing the first element in the map.
   inline iterator begin(){
      Node *node = nullptr;
      for(unsigned current_index = 0; current_index < SIZE; ++current_index){
         node = hashtab[current_index];
         if (node != nullptr) break;
      }
      return iterator(node, this);
   }

   inline const_iterator begin() const{
      Node *node = nullptr;
      for(unsigned current_index = 0; current_index < SIZE; ++current_index){
         node = hashtab[current_index];
         if (node != nullptr) break;
      }
      return const_iterator(node, const_cast<AISDIHashMap*> (this));
   }

   /// Returns an iterator that addresses the location succeeding the last element in a map.
   inline iterator end() {
     return iterator(nullptr, this);
   }
   inline const_iterator end() const{
     return const_iterator(nullptr, const_cast<AISDIHashMap*> (this) );
   }

   /// 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) {
      unsigned entry_hash = hashFunc(entry.first);

      if ( hashtab[entry_hash] == nullptr ) {
         hashtab[entry_hash] = new Node(entry, entry_hash, nullptr);
         ++counter;
         return std::make_pair(iterator(hashtab[entry_hash], this), true);
      }

      iterator i = find(entry.first);

      if( i != end())
         return std::make_pair(i, false);

      Node *curr = hashtab[entry_hash];
      while (curr->next != nullptr)
         curr = curr->next;
      curr->next = new Node(entry, entry_hash);
      ++counter;
      return std::make_pair(iterator(curr->next, this), true);

   }

   /// 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) {
      Node *ptr = hashtab[hashFunc(k)];
      if( ptr == nullptr) return end();
      while (ptr != nullptr) {
         if (compFunc(ptr->data.first, k) ) return iterator(ptr, this);
         ptr = ptr->next;
      }
      return end();
   }

   /// Returns an const iterator
   const_iterator find(const K& k) const {
       Node *ptr = hashtab[hashFunc(k)];
       if (ptr == nullptr) return end();
       while (ptr != nullptr) {
         if (compFunc(ptr->data.first, k) ) return const_iterator(ptr,
                                       const_cast<AISDIHashMap*>(this));
         ptr = ptr->next;
       }
       return end();
   }

   /// 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) {

      std::pair<iterator, bool> temp = insert ( std::make_pair (k, V() ) );
      return temp.first.node->data.second;
   }

   /// Tests if a map is empty.
   bool empty( ) const {
    return static_cast<bool>(counter); //Casting count_ to bool. Only if
   }                                  // was 0 it will return false


   /// Returns the number of elements in the map.
   size_type size() const {
    return counter;
   }

   /// 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() ) ? 0 : 1; // if element found return 1  else return 0
   }

   /// 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.node == nullptr) return iterator(nullptr, this);

      iterator to_return = i;
      ++to_return;

      unsigned elem_hash = i.node->hash;
      Node *to_delete = i.node;
      if (hashtab[elem_hash] == to_delete) {
         hashtab[elem_hash] = to_delete->next;
         delete to_delete;
         --counter;
         return to_return;
      }
      else {
         Node *curr = hashtab[elem_hash];
         while (curr -> next!= to_delete ) {
            curr = curr->next;
         }
         to_delete = curr->next;
         curr->next = to_delete->next;
         delete to_delete;
         --counter;
         return to_return;
      }
   }
   /// 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 elemnt removed.
   /// @returns The iterator that designates the first element remaining beyond any elements removed.
   iterator erase(iterator f, iterator l) {
    for (; f != l && f.node != nullptr; ++f) // extra condition to avoid
      erase (f);                             // deleting not in order
    return l;
  }

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

   /// Erases all the elements of a map.
   void clear() {
    //erase ( begin(), end() );
      iterator temp = begin();
      while ( temp != end())
         erase(temp++);
   }
};