#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__