1 files changed, 217 insertions, 0 deletions
diff --git a/meowpp/dsa/HashTable.h b/meowpp/dsa/HashTable.h
new file mode 100644
index 0000000..9171c72
--- /dev/null
+++ b/meowpp/dsa/HashTable.h
@@ -0,0 +1,217 @@
+#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__