Project: finder, src: unordered_map.h

#ifndef STD_UNORDERED_MAP_H_
#define STD_UNORDERED_MAP_H_

#include <list>
#include <utility>
#include "EOFObjectException.h"

namespace std {

template<typename K, typename V, typename H>
class unordered_map {
  struct UOMPair : public pair<K, V> {
    bool operator == (const UOMPair &p) const {
      return (this->first == p.first);
    }
    UOMPair(const K &key, const V &value) : pair<K,V>(key, value) {}
    UOMPair() : pair<K, V>() {}
  };
#define HASH_SIZE (1024)
  H hash;
  std::list<UOMPair> *hashtable;

 public:
  unordered_map<K, V, H>() {
    hashtable = new std::list<UOMPair>[HASH_SIZE];
  };

  ~unordered_map<K, V, H>() {
    delete [] hashtable;
  }

  void clear() {
    for (int i = 0; i < HASH_SIZE; ++i) {
      hashtable[i].clear();
    }
  }

  V &operator[](const K &key) {
    std::list<UOMPair> &p = hashtable[hash(key) % HASH_SIZE];
    for (typename std::list<UOMPair>::iterator i = p.begin(); i != p.end(); ++i) {
      if (key == i->first) {
        return i->second;
      }
    }
    UOMPair tmp(key, V());
    p.push_back(tmp);
    return p.back().second;
  }

  // iterators
  class iterator {
    int pos;
    typename std::list<UOMPair>::iterator current;
    std::list<UOMPair> *hashtable;
    bool isEnd() {
      return pos == HASH_SIZE - 1 && current == hashtable[pos].end();
    }

   public:
    iterator() {}
    iterator(int pos, const typename std::list<UOMPair>::iterator &c, std::list<UOMPair> *h) : pos(pos), current(c), hashtable(h) {}
    bool operator == (const iterator &i) const {
      return pos == i.pos && current == i.current && hashtable == i.hashtable;
    }
    bool operator != (const iterator &i) const {
      return !(*this == i);
    }
    pair<K, V> operator *() {
      if (!isEnd()) {
        return pair<K, V>(*current);
      }
      throw EOFObjectException(__FILE__, __LINE__, "EOFObjectException");
    }
    iterator & operator ++() {
      if (!isEnd()) {
        if (current == hashtable[pos].end()) {
          current = hashtable[++pos].begin();
        } else {
          ++current;
        }
      }
      return *this;
    }
    iterator &operator ++(int dummy) {
      if (!isEnd()) {
        if (current == hashtable[pos].end()) {
          current = hashtable[++pos].begin();
        } else {
          ++current;
        }
      }
      return *this;
    }
  };
  typedef iterator const_iterator;

  // iterator operations
  iterator begin() {
    return iterator(0, hashtable[0].begin(), hashtable);
  }
  iterator end() {
    return iterator(HASH_SIZE - 1, hashtable[HASH_SIZE - 1].end(), hashtable);
  }
  iterator find(const K &key) {
    size_t h = hash(key) % HASH_SIZE;
    std::list<UOMPair> &p = hashtable[h];
    for (typename std::list<UOMPair>::iterator i = p.begin(); i != p.end(); ++i) {
      if (key == i->first) {
        return iterator(h, i, hashtable);
      }
    }
    return end();
  }
};

}

#endif //STD_UNORDERED_MAP_H_