1 files changed, 75 insertions, 0 deletions
diff --git a/meowpp/dsa/KD_Tree.h b/meowpp/dsa/KD_Tree.h
new file mode 100644
index 0000000..0abc358
--- /dev/null
+++ b/meowpp/dsa/KD_Tree.h
@@ -0,0 +1,75 @@
+#ifndef   KD_Tree_H__
+#define   KD_Tree_H__
+
+#include <list>
+#include <vector>
+#include <cstdlib>
+
+namespace meow{
+  template<class Keys, class Key, class Value>
+  class KD_Tree{
+    private:
+      struct Node{
+        Keys    key;
+        Value   value;
+        ssize_t lChild;
+        ssize_t rChild;
+        Node(Keys _key, Value _value, ssize_t _l_child, ssize_t _r_child);
+      };
+      typedef std::vector<Node> Nodes;
+      class Sorter{
+        private:
+          Nodes const& nodes;
+          size_t       cmp;
+        public:
+          Sorter(Nodes const& _nodes, size_t _cmp);
+          bool operator()(size_t const& a, size_t const& b) const;
+      };
+      typedef std::vector<Value> Values;
+      struct Answer{
+        Node const& node;
+        Key         dist2;
+        Answer(Node const& _node, Key _dist2);
+        bool operator<(Answer const& b) const;
+      };
+      typedef typename std::list<Answer>    AnswerList;
+      typedef typename AnswerList::iterator AnswerListIterator;
+      //
+      const ssize_t NIL;
+      //
+      Nodes  nodes;
+      size_t root;
+      bool   needRebuild;
+      size_t dimension;
+      //
+      Key distance2(Keys const& k1, Keys const& k2) const;
+      size_t query(Keys const& key,
+                   size_t k,
+                   size_t index,
+                   int depth,
+                   std::vector<Key>& dist2_v,
+                   Key               dist2_s,
+                   AnswerList* ret) const;
+      ssize_t build(ssize_t beg,
+                    ssize_t end,
+                    std::vector<size_t>* orders,
+                    int depth);
+    public:
+      KD_Tree();
+      KD_Tree(size_t _dimension);
+      ~KD_Tree();
+      //
+      void   insert(Keys const& key, Value value);
+      void   build();
+      //
+      Value  query     (Keys const& point, int k) const;
+      Values rangeQuery(Keys const& point, int k) const;
+      //
+      void   clear();
+      void   reset(size_t _dimension);
+  };
+}
+
+#include "KD_Tree.hpp"
+
+#endif // KD_Tree_H__