hashmap.h

#ifndef HASHMAP_H
#define HASHMAP_H

#include <ctype.h>  //isalnum()
#include <fstream>  //obsluga plikow
#include <string>
#include <iterator>
#include <utility>
#define HASH_SIZE 64000         //wielkosc tablicy hashujacej
#include <iostream>
using namespace std;
void otwieranie_pliku(string nazwa);
template <class Key>
inline int  _compFunc(const Key& key1,const Key& key2) //funkcja sprawdza, czy klucze sa rowne
{
   return (key2!=key1);
};

template <class K>
inline unsigned int hashF(const K &hash)
{   unsigned int baza = 5381; //liczba pierwsza, dobra do hashowania, metoda DJB
    const char *klucz = hash.c_str();
    int znak;
    while(znak=*klucz++) baza= ((baza <<5)+baza)+znak;
    return baza % HASH_SIZE; //zeby nie wyskoczyc poza obszar tablicy hashujacej
};
///Mapa podobna do STLowej
template<class K, class V,
         unsigned int hashFunc(const K&),
         int compFunc(const K&,const K&)=&_compFunc<K> >
class HashMap
{

    struct Cell
    {
      pair<K,V> data;       //zawiera klucz i wartosc (Key, Value)
      Cell *next;
      Cell *prev;
      unsigned int hash;

      Cell(){};             //konstruktor
      Cell(const struct Cell &n) : data(n.data), next(n.next), prev(n.prev) {}; //kopiujacy
      Cell(const pair<K, V> d, Cell *n = NULL, Cell *p = NULL) :
           data(d), next(n), prev(p) {};
    };


      unsigned int map_size;
      Cell *sentinel;          //wskaznik na sentinela

public:
   typedef pair<K, V> T;
 Cell *tablica_hash[HASH_SIZE];  //tworzymy tablice hashujaca////////////////////////////////////wrzuc do priva
   HashMap(): map_size(0)
    { sentinel=new Cell (make_pair(K(), V()));    //ustawienie sentinela
      sentinel->next = sentinel;
      sentinel->prev = sentinel;
      sentinel->hash = 0;

      Cell **ptr = tablica_hash;                     //tworzymy wskaznik na pierwszy element tablicy hashujacej
      for(int i=0; i<HASH_SIZE; ++i) *(ptr++)=NULL;  //i ustawiamy wszystkie elementy na NULL
    }

   ~HashMap()
    { Cell *tmp = sentinel->next;
      while(tmp !=sentinel){tmp = tmp->next; delete(tmp->prev);} // usuwamy kazdy element hashtabla

      delete(sentinel); //na koniec sprzatamy po sobie kasujac sentinela
    };

   /// Coping constructor.
   explicit HashMap(const HashMap<K, V, hashFunc, compFunc>& a)
    { sentinel = new Cell(make_pair(K(), V()));
      sentinel->hash=0; //ustawiamy sentinela

       map_size = a.map_size;  //ustawiamy ilosc elementow
      Cell **ptr = tablica_hash;
      for(int i=0; i<HASH_SIZE; ++i) *(ptr++)= NULL;

      Cell *tmp = sentinel;
      Cell *tmp2 = a.sentinel->next;
     unsigned int prev_hash = tmp2->hash;

    for(;tmp2!=a.sentinel; tmp = tmp->next, tmp2=tmp2->next)
        {tmp->nast = new Cell(tmp2->data, NULL, tmp);
         tmp->nast->hash = tmp2->hash;

        if(prev_hash != tmp->nast->hash) //czy nie trzeba wstawic elementu do tab
            {prev_hash = tmp->nast->hash;
             tablica_hash[prev_hash] = tmp->nast;
            }
        }//zamyka fora

    tmp->nast = sentinel;
    sentinel->prev = tmp;  //wskazujemy straznikowi koniec hashmapy
    };



void otwieraniePliku()
{
    string nazwa;
    cout<<"Podaj nazwe pliku: ";
    cin>>nazwa;
    fstream plik;
    plik.open( nazwa.c_str(), ios::in );
     if( plik.good() )
     {
         parsujTekst(plik);
     }
     else cout<< "Nie udalo sie otworzyc pliku!"<<endl;
// Mozliwy blad -> podano zla nazwe ;d

};

void parsujTekst(fstream &plik)
{
    string linia;
    while(!plik.eof())
        {
            unsigned int i=0;
            string wyraz;
            getline(plik, linia);
            if(linia[0]=='#')
            {
                cout<< "HASH!"<<endl;
                liniaHash(linia);
            }
            while(linia.size()!=0)
            {
                wyraz = pobierzWyraz(linia);
                if(!wyraz.empty())cout <<"wyraz: "<<wyraz<<endl;
            }
        }
};
string do_zamiany;
void liniaHash(string &linia)
{
    string zamiennik;// do_zamiany;
    pobierzWyraz(linia);
    if(pobierzWyraz(linia)=="define")
    {
        do_zamiany = pobierzWyraz(linia);
        zamiennik = pobierzWyrazenie(linia);
        cout<< "wtf : "<<do_zamiany<<endl;
        insert(make_pair(do_zamiany, zamiennik));
        cout<< "wtf2 : "<<do_zamiany<<endl;
    }
};

string pobierzWyrazenie(string &linia)
{
    string wyraz;
    for (unsigned int i=0; i<= linia.size();++i)
    {
        if (linia[i]>= ' ' && !(linia[i]=='/'&&linia[i+1]=='/') ) //dopoki nalezy do znakow drukowalnych i nie jest komentarzem
        {
            wyraz+=linia[i];
        }
        else
        {
            linia.erase(0,i+1);
        }
    }
};
string pobierzWyraz(string &linia)
{
    string wyraz;
    for (unsigned int i=0; i<= linia.size();++i)
    {
        if (isalnum(linia[i])||linia[i]=='_')
        {
            wyraz+=linia[i];
        }
        else
        {
            linia.erase(0,i+1);
            return wyraz;
        }
    }

};




   /// const_iterator.
   class const_iterator: public iterator<forward_iterator_tag,
                                                 pair<K, V> >
    {
       protected:
        Cell *sentinel;     //wskazanie na sentinela
        Cell *cell;         //          na element
        friend class HashMap;
       public:
        const_iterator(){};
        const_iterator(Cell *n, Cell *s) : cell(n), sentinel(s) {}
        const_iterator(const const_iterator &n) : cell(n.cell), sentinel(n.sentinel) {}

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

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

              inline const_iterator& operator++() {
              if(cell != sentinel) cell = cell->next;
              return *this;
            }

            inline const_iterator operator++(int) {
              if(cell == sentinel) return *this;
              const_iterator tmp = *this;
             cell = cell->next;
              return tmp;
           }
     inline const_iterator& operator--() {
              if(cell->prev != sentinel) cell = cell->prev;
              return *this;
            }

            inline const_iterator operator--(int) {
              if(cell->prev == sentinel) return *this;
              const_iterator tmp = *this;
              cell = cell->prev;
              return tmp;
            }

            inline bool operator==(const const_iterator &inny) const
            {return (cell == inny.cell);}

            inline bool operator!=(const const_iterator &inny) const
            {return (cell != inny.cell);}
    };
   /// iterator.
   class iterator: public const_iterator
    {
      private:
        friend class HashMap;
      public:
         iterator() {}
            iterator(Cell *x, Cell *s) : const_iterator(x, s) {}
            iterator(const iterator &a) {
              this->cell = a.cell;
              this->sentinel = a.sentinel;
            }

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

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

            inline iterator& operator++()
            {++(*(const_iterator*)this);
              return (*this);
            }

         inline iterator operator++(int)
            {
              iterator tmp = *this;
              ++*this;
              return tmp;
            }

            inline iterator& operator--()
            {
              --(*(const_iterator*)this);
              return (*this);
            }

            inline iterator operator--(int)
            {
              iterator tmp = *this;
              --*this;
              return tmp;
            }
        };

   /// Returns an iterator addressing the first element in the map.

    inline iterator begin(){return iterator(sentinel->next, sentinel);}
    inline const_iterator begin() const {return const_iterator(sentinel->next, sentinel);};

   /// Returns an iterator that addresses the location succeeding the last element in a map.

    inline iterator end(){return iterator(sentinel, sentinel);};
    inline const_iterator end() const {return const_iterator(sentinel, 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.
   pair<iterator, bool> insert(const pair<K, V>& entry)
    {
      unsigned hash=hashFunc(entry.first); // hash wstawianego elementu
      Cell *tmp = tablica_hash[hash];
        if(tmp!=NULL) //jest juz element o podanym hashu
        {
           while(tmp->hash == hash && tmp != sentinel)
            {  if(!compFunc(tmp->data.first, entry.first))
                return make_pair(iterator(tmp, sentinel), false);
               tmp = tmp->next;
            }//zamyka while

           Cell *n = new Cell(entry, tmp, tmp->prev);
           tmp->prev->next = n;
           tmp->prev = n;
              n->hash = hash;
              map_size++;
              return make_pair(iterator(n, sentinel), true);
        }//zamyka ifa

        Cell *n= new Cell(entry, sentinel, sentinel->prev);
        sentinel->prev->next = n;
        sentinel->prev = n;
        n->hash = hash;
        tablica_hash[hash] = n;
        map_size++;
        return make_pair(iterator(n, sentinel), 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)
    { unsigned hash = hashFunc(k); //hash elementu

        if(tablica_hash[hash]==NULL) return end(); //jesli nie znalazles elementu zwroc iterator po ostatnim

        Cell *tmp = tablica_hash[hash];
        do{
            if(!compFunc(tmp->data.first, k)) return iterator(tmp, sentinel); //znaleziono element
            tmp = tmp->next;
          }while(tmp->hash == hash && tmp != sentinel);
    return end();       //gdy nie ma takiego elementu
    };




   const_iterator find(const K&k) const
    {unsigned hash = hashFunc(k);     //hash szuk. elementu

      //sprawdzamy miejsce w tablicy hashujacej
       if(tablica_hash[hash] == NULL) return end();

     Cell* tmp = tablica_hash[hash];

    do {
        if(!compFunc(tmp->data.first, k))return const_iterator(tmp, sentinel);
        tmp = tmp->next;
          } while(tmp->hash == hash && tmp != sentinel);

      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)
    {return insert(make_pair(K(k), V())).first->second;
    };

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

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

   /// Returns the number of elements in a map whose key matches a parameter-specified key.
   unsigned count(const K& _Key) const
    { unsigned hash=hashFunc(_Key);
        if(tablica_hash[hash] == NULL) return 0; //znalazlo 0 elementow;
        Cell *tmp = tablica_hash[hash];
      do {
        if(!compFunc(tmp->data.first, _Key))
          return 1;                                //znaleziono
        tmp = tmp->next;
      } while(tmp->hash == hash && tmp != sentinel);

      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)
    {
     //sprawdzamy czy i nie wskazuje na straznika i czy jest z tej mapy
          if(i.cell == sentinel || i.sentinel!= sentinel) return i;

          Cell *tmp = i.cell;
          unsigned int hash = tmp->hash;


          if(tmp == tablica_hash[hash]) {
            if(tmp->next->hash != hash || tmp->next == sentinel) {
              tablica_hash[hash] = NULL;
            } else {
              tablica_hash[hash] = tmp->next;
            }
          }

          tmp->prev->next = tmp->next;
          tmp->next->prev = tmp->prev;
          i = iterator(tmp->next, sentinel);
          delete tmp;
          map_size--;
          return i;
    };

   /// 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 first, iterator last)
    {  if(first == end()) return end();
       //sprawdzamy czy last>=first
          Cell *tmp = last.cell;
          for(; tmp != sentinel; tmp = tmp->next)
        if(tmp == first.cell) return end();
    //kasujemy elementy
          while(first != last) erase(first++);

          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 itshould be 1 or 0.
   unsigned erase(const K& key)
    {unsigned hash = hashFunc(key);
    if(tablica_hash[hash] == NULL) return 0; //jesli nie ma co usunac -> zwroc 0
    Cell *tmp = tablica_hash[hash];

    if(!compFunc(tmp->data.first, key)) {
            if(tmp->next->hash != hash || tmp->next == sentinel) {
              tablica_hash[hash] = NULL;
            } else {//else1
              tablica_hash[hash] = tmp->next;
             }//do else1
          } else {//else2
            do {
              if(tmp == sentinel) return 0;               //doszlismy do konca
              if(tmp->next->hash != hash) return 0;
              tmp = tmp->next;
            } while(compFunc(tmp->data.first, key) != 0);
              }//do elsa2
      tmp->prev->next = tmp->next;
      tmp->next->prev = tmp->prev;
      delete tmp;
      map_size--;
    //  cout << map_size<<endl;
      return 1;
    };

   /// Erases all the elements of a map.
   void clear()
    {Cell *tmp = sentinel;

      while(tmp != sentinel) {
        tmp = tmp->next;                //usuwamy elementy
        delete(tmp->prev);
      }

      sentinel->next =  sentinel;
    sentinel->prev = sentinel;
      Cell **wsk = tablica_hash;
      for(int i=0; i<HASH_SIZE; ++i)    //zerujemy tablice hash
        *(wsk++)= NULL;

      map_size = 0;
    };



};
#include "hashmap.cpp"
#endif