#ifndef dsa_VP_Tree_H__
#define dsa_VP_Tree_H__
#include "../math/utility.h"
#include <cstdlib>
#include <list>
#include <vector>
#include <queue>
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);
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);
//#|=====================================================================
};
//#
//#[NOTE]
//#========================================
//# * 實測結果發覺, 維度小的時候, 比起中規中矩的 `KD_Tree`, `VP_Tree` 有
//# 'randomp' 於其中, 因此時間複雜度只是期望值 'O(logN)' 但是測資大到
//# 一定程度, `KD_Tree` 效率會一整個大幅掉下, 但 `VP_Tree` 幾乎不受影響
//# * 'TODO' `insert()`, `erase()` 算是未完成功能
//#
//#========================================
//#
//# '''
}
#include "VP_Tree.hpp"
#endif // dsa_VP_Tree_H__
