#ifndef   dsa_KD_Tree_H__
#define   dsa_KD_Tree_H__

#include <cstdlib>

#include <vector>
#include <queue>

namespace meow{
  //#
  //#=== meow:: *KD_Tree<Vector, Scalar>* (C++ class)
  //#==== Description
  //#  `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*, 
  //#  並可於該set中查找 *前i個離給定向量最接近的向量*
  //#
  //#==== Template Class Operators Request
  //#[options="header",width="70%",cols="1>m,1<,3<s,5<,3<,15<",grid="rows"]
  //#|=====================================================================
  //#|Const?|Typename| Operator  | Parameters  | Return_Type| Description
  //#|const |  Vector|operator[] |(size_t `n`) | Scalar     | 取得第 `n` 維度量
  //#|const |  Vector|operator<  |(Vector `v`) | bool       | 權重比較
  //#|const |  Scalar|operator*  |(Scalar `s`) | Scalar     | 相乘
  //#|const |  Scalar|operator+  |(Scalar `s`) | Scalar     | 相加
  //#|const |  Scalar|operator-  |(Scalar `s`) | Scalar     | 相差
  //#|const |  Scalar|operator<  |(Scalar `s`) | bool       | 大小比較
  //#|=====================================================================
  //#
  template<class Vector, class Scalar>
  class KD_Tree{
    private:
      struct Node{
        Vector  _vector;
        ssize_t _lChild;
        ssize_t _rChild;
        //
        Node(Vector __vector, ssize_t __lChild, ssize_t __rChild);
      };
      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;
      };
      struct Answer{
        ssize_t _index;
        Scalar  _dist2;
        //
        Answer(ssize_t __index, Scalar __dist2);
        Answer(Answer const& __answer2);
      };
      class AnswerCompare{
        private:
          Nodes const* _nodes;
          bool         _cmpValue;
        public:
          AnswerCompare(Nodes const* __nodes, bool __cmpValue);
          bool operator()(Answer const& __a, Answer const& __b) const;
      };
      typedef std::vector<Answer> AnswerV;
      typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers;
      //
      const ssize_t _NIL;
      //
      Nodes  _nodes;
      size_t _root;
      bool   _needRebuild;
      size_t _dimension;
      //
      Scalar distance2(Vector const& __v1, Vector const& __v2) const;
      //
      void query(Vector const&        __vector,
                 size_t               __nearestNumber,
                 AnswerCompare const& __answerCompare,
                 size_t               __index,
                 int                  __depth,
                 std::vector<Scalar>& __dist2Vector,
                 Scalar               __dist2Minimum,
                 Answers             *__out) const;
      ssize_t build(ssize_t              __beg,
                    ssize_t              __end,
                    std::vector<size_t>* __orders,
                    int                  __depth);
    public:
      //#==== Custom Type Definitions
      //# * `Vectors` <- `std::vector<Vector>`
      //#
      typedef typename std::vector<Vector> Vectors;
      //
      KD_Tree();
      KD_Tree(size_t __dimension);
      ~KD_Tree();

      //#==== Support Methods
      //#
      //# * N <- `this` 中擁有的資料數
      //# * K <- `this` 資料維度
      //#
      //#[options="header",width="100%",cols="1>m,3>s,7<,3<,3^,20<",grid="rows"]
      //#|=====================================================================
      //#|Const?|Name | Parameters   | Return_Type| Time_Complexity| Description


      //#||insert|(Vector const& `v`)|void| O(1)
      //#|將向量 `v` 加到set中
      void insert(Vector const& __vector);


      //#||erase|(Vector const& `v`)|bool| O(N)
      //#|將向量 `v` 從set中移除, '~TODO:可以再優化~'
      bool erase (Vector const& __vector);


      //#||build|()|void|O(KN logN) or O(1)
      //#|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫,
      //# 若有, 重新建樹, 否則不做事
      void build();


      //#||forceBuild|()|void|O(KN logN)
      //#|重新建樹
      void forceBuild();


      //#|const|query|(Vector const& `v`,\size_t `i`,\bool `cmp`)|Vectors
      //#|O(KN ^1-1/K^ )
      //#|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序.
      //# 如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照
      //# `v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解.
      Vectors query(Vector const& __vector,
                    size_t        __nearestNumber,
                    bool          __compareWholeVector) const;


      //#||clear|()|void|O(1)
      //#|清空所有資料
      void clear();


      //#||reset|(size_t `dimension`)|void|O(1)
      //#|清空所有資料並且指定維度為 `dimension`
      void reset(size_t __dimension);


      //#|=====================================================================
  };
  //#
  //#[NOTE]
  //#========================================
  //# * 此資料結構只有在 N >> 2 ^K^ 時才比較有優勢,
  //#   當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣
  //#========================================
  //#
  //# '''
}

#include "KD_Tree.hpp"

#endif // dsa_KD_Tree_H__