#ifndef   dsa_HashTable_H__
#define   dsa_HashTable_H__

#include <vector>
#include <list>

namespace meow {

/*!
 * @brief 一個當key相撞時會用list解決的hash_table
 *
 * @author cat_leopard
 */
template<class Data, class HashFunc>
class HashTableList {
private:
  std::vector<std::list<Data> > table_;
  HashFunc                          func_;
public:
  /*!
   * @brief constructor
   */
  HashTableList() {
  }

  /*!
   * @brief constructor
   * 
   * 設定table size, hash function
   */
  HashTableList(size_t size, HashFunc const& func): table_(size), func_(func) {
  }

  /*!
   * @brief destructor
   */
  ~HashTableList() {
  }

  /*!
   * @brief copy
   */
  HashTableList& copyFrom(HashTableList const& b) {
    table_ = b.table_;
    func_  = b.func_;
    return *this;
  }

  /*!
   * @brief 清除資料
   */
  void clear() {
    for (size_t i = 0, I = table_.size(); i < I; i++) {
      table_[i].clear();
    }
  }

  /*!
   * @brief 清除資料, 指定新的size與hash function
   */
  void reset(size_t size, HashFunc const& func) {
    table_.clear();
    table_.resize(std::max(size, 1u));
    func_ = func;
  }

  /*!
   * @brief 回傳table size
   */
  size_t tableSize() const {
    return table_.size();
  }

  /*!
   * @brief 回傳目前有多少element在其中
   */
  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;
  }

  /*!
   * @brief 回傳hash function
   */
  HashFunc const& func() const {
    return func_;
  }

  /*!
   * @brief 加入新的element
   */
  bool add(Data const& e) {
    size_t index = func_(e) % size();
    table_[index].push_back(e);
    return true;
  }

  /*!
   * @brief 把給定的HashTableList中所有的element全加進來
   */
  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;
  }

  /*!
   * @brief 刪除element
   */
  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;
  }

  /*!
   * @brief 刪除有出現在給定的的HashTableList中的element
   */
  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;
  }

  /*!
   * @brief 查看某element是否已經擁有
   */
  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;
  }

  /*!
   * @brief 回傳所有存下來的資料
   */
  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;
  }

  /*!
   * @brief 回傳所有存下來且key為index的資料
   */
  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;
  }
  
  //! @brief same as \c copyFrom(h)
  HashTableList& operator=(HashTableList const& h) {
    return copyFrom(h);
  }
  
  //! @brief same as \c add(h)
  HashTableList& operator+=(HashTableList const& h) {
    add(h);
    return *this;
  }
  
  //! @brief same as \c del(h)
  HashTableList& operator-=(HashTableList const& h) {
    del(h);
    return *this;
  }
};

}

#endif // dsa_HashTable_H__