HashTable.h

Go to the documentation of this file.

#ifndef   dsa_HashTable_H__
#define   dsa_HashTable_H__

#include <vector>
#include <list>

namespace meow {

template<class Data, class HashFunc>
class HashTableList {
private:
  std::vector<std::list<Data> > table_;
  HashFunc                          func_;
public:
  HashTableList() {
  }

  HashTableList(size_t size, HashFunc const& func): table_(size), func_(func) {
  }

  ~HashTableList() {
  }

  HashTableList& copyFrom(HashTableList const& b) {
    table_ = b.table_;
    func_  = b.func_;
    return *this;
  }

  void clear() {
    for (size_t i = 0, I = table_.size(); i < I; i++) {
      table_[i].clear();
    }
  }

  void reset(size_t size, HashFunc const& func) {
    table_.clear();
    table_.resize(std::max(size, 1u));
    func_ = func;
  }

  size_t tableSize() const {
    return table_.size();
  }

  size_t size() const {
    size_t ret = 0;
    for (size_t i = 0, I = table_.size(); i < I; i++) {
      ret += table_[i].size();
    }
    return ret;
  }

  HashFunc const& func() const {
    return func_;
  }

  bool add(Data const& e) {
    size_t index = func_(e) % size();
    table_[index].push_back(e);
    return true;
  }

  bool add(HashTableList const& h) {
    for (size_t i = 0, I = h.table_.size(); i < I; i++) {
      for (std::list<Data>::const_iterator
           it = h.table_[index].begin(); it != h.table_[index].end(); ++it) {
        insert(*it);
      }
    }
    return true;
  }

  bool del(Data const& e) {
    size_t index = func_(e) % size();
    for (std::list<Data>::const_iterator
         it = table_[index].begin(); it != table_[index].end(); ++it) {
      if ((*it) == e) {
        table_[index].erase(i);
        return true;
      }
    }
    return false;
  }

  bool del(HashTableList const& h) {
    if (size() > h.size()) {
      for (size_t i = 0, I = h.table_.size(); i < I; i++) {
        for (std::list<Data>::const_iterator
             it = h.table_[index].begin(); it != h.table_[index].end(); ++it) {
          erase(*it);
        }
      }
    }
    else {
      for (size_t i = 0, I = table_.size(); i < I; i++) {
        for (std::list<Data>::const_iterator
             it = table_[index].begin(); it != table_[index].end(); ) {
          if (h.exist(*it)) {
            table_[index].erase(it);
          }
          else {
            ++it;
          }
        }
      }
    }
    return true;
  }

  bool exist(Data const& e) const {
    size_t index = func_(e) % size();
    for (std::list<Data>::const_iterator
         it = table_[index].begin(); it != table_[index].end(); ++it) {
      if ((*it) == e)
        return true;
    }
    return false;
  }

  std::vector<Data> all() const {
    std::vector<Data> ret;
    for (size_t i = 0, I = table_.size(); i < I; i++) {
      for (std::list<Data>::const_iterator
           it = table_[i].begin(); it != table_[i].end(); ++it) {
        ret.push_back(*it);
      }
    }
    return ret;
  }

  std::vector<Data> all(size_t index) const {
    index %= table_.size();
    std::vector<Data> ret;
    for (std::list<Data>::const_iterator
         it = table_[index].begin(); it != table_[index].end(); ++it) {
      ret.push_back(*it);
    }
    return ret;
  }

  HashTableList& operator=(HashTableList const& h) {
    return copyFrom(h);
  }

  HashTableList& operator+=(HashTableList const& h) {
    add(h);
    return *this;
  }

  HashTableList& operator-=(HashTableList const& h) {
    del(h);
    return *this;
  }
};

}

#endif // dsa_HashTable_H__