#ifndef   VP_Tree_H__
#define   VP_Tree_H__

#include <list>
#include <vector>
#include <cstdlib>
#include <queue>
#include "../utility.h"

namespace meow{
  //#
  //#=== meow:: *VP_Tree<Vector, Scalar>* (C++ class)
  //#==== Description
  //#  `VP_Tree` 用來維護由 *N個K維度向量所成的集合*, 
  //#  並可於該set中查找 *前i個離給定向量最接近的向量*. +
  //#  不像 `KD_Tree` 二分樹每次都選擇一個維度去分, 分成小的跟大的, 
  //#  `VP_Tree` 每次選一個點, 將資料分成 離這個點近的, 跟離這個點遠的.
  //#  至於怎麼選呢...., 嘛還沒研究, 先random
  //#
  //#  .參考資料連結: 
  //#  * http://stevehanov.ca/blog/index.php?id=130[link]
  //#  * http://pnylab.com/pny/papers/vptree/vptree[link]
  //#
  //#==== 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`) | Vector&    | copy operator
  //#|const |  Vector|operator<  |(Vector `v`) | bool       | 權重比較
  //#|const |  Scalar| 'Scalar'  |(int    `n`) | Scalar     | 建構子,
  //#                                                         其中一定`n=0 or 4`
  //#|const |  Scalar|operator*  |(Scalar `s`) | Scalar     | 相乘
  //#|const |  Scalar|operator+  |(Scalar `s`) | Scalar     | 相加
  //#|const |  Scalar|operator-  |(Scalar `s`) | Scalar     | 相差
  //#|const |  Scalar|operator-  |(          ) | Scalar     | 取負號
  //#|const |  Scalar|operator<  |(Scalar `s`) | bool       | 大小比較
  //#|=====================================================================
  //#
  template<class Vector, class Scalar>
  class VP_Tree{
    public:
      //#==== Custom Type Definitions
      //# * `Vectors` <- `std::vector<Vector>`
      //#
      typedef typename std::vector<Vector> Vectors;
    private:
      //
      struct Node{
        size_t _index;
        Scalar _threshold;
        Node*  _nearChild;
        Node*  _farChild;
        Node(size_t __index);
      };
      struct Answer{
        size_t _index;
        Scalar _dist2;
        //
        Answer(size_t __index, Scalar const& __dist2);
        Answer(Answer const& __answer2);
      };
      class AnswerCompare{
        private:
          Vectors const* _vectors;
          bool           _cmpValue;
        public:
          AnswerCompare(Vectors const* __vectors, bool __cmpValue);
          bool operator()(Answer const& __a, Answer const& __b) const;
      };
      typedef std::vector<Answer> AnswerV;
      typedef std::priority_queue<Answer, AnswerV, AnswerCompare> Answers;
      //
      Vectors _vectors;
      Node*   _root;
      size_t  _dimension;
      bool    _needRebuild;
      //
      Scalar distance2(Vector const& __v1, Vector const& __v2) const;
      int distanceCompare(Scalar const& __a2, Scalar const& __b2,
                          Scalar const& __c2) const;
      Scalar split(ssize_t __first, ssize_t __last, size_t __order,
                   Vector const& __center);
      //
      Node* build(ssize_t __first, ssize_t __last);
      void query(Vector const&        __vector,
                 size_t               __k,
                 AnswerCompare const& __cmp,
                 Node const*          __node,
                 Answers*             __out) const;
      void clear(Node* __root);
      Node* dup(Node* __root);
      //
      void print(Node* __node, int depth = 1,
                 Node* __parent = NULL, bool __near = true) const;
    public:
      VP_Tree();
      VP_Tree(VP_Tree const& __tree2);
      VP_Tree(size_t __dimension);
      ~VP_Tree();
      VP_Tree& operator=(VP_Tree const& __tree2);

      //#==== Support Methods
      //#
      //# * N <- `this` 中擁有的資料數
      //# * D <- `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(logN) ~Expected~
      //#|於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`)|size_t|O(1)
      //#|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度
      size_t reset(size_t __dimension);


      //#|=====================================================================
      
      void print() const;
  };
  //#
  //#[NOTE]
  //#========================================
  //# * 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有
  //#   'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到
  //#   一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響
  //# * 'TODO' `insert()`, `erase()` 算是未完成功能
  //#
  //#========================================
  //#
  //# '''
}

#include "VP_Tree.hpp"

#endif // VP_Tree_H__