update readme

1 files changed, 77 insertions, 0 deletions

diff --git a/README.asciidoc b/README.asciidoc
index 3d93e0a..bdaaeee 100644
--- a/README.asciidoc
+++ b/README.asciidoc
@@ -32,6 +32,7 @@
 ** *KD_Tree.h* `class KD_Tree<Vector, Scalar>`
 ** *SegemenTree.h* `class SegmentTree<Value>`
 ** *SplayTree.h* `class SplayTree<Key, Value>`
+** *VP_Tree.h* `class VP_Tree<Vector, Scalar>`
 * *oo/*
 ** *Register_Implement.h* `class RegisterInterface` ,
                             `class ImplementInterface` 
@@ -264,6 +265,76 @@ size_t `number2`)| size_t  | very fast
 '''
 
 
+=== 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       | 大小比較
+|=====================================================================
+
+==== Custom Type Definitions
+* `Vectors` <- `std::vector<Vector>`
+
+==== 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中
+||erase|(Vector const& `v`)|bool| O(N)
+|將向量 `v` 從set中移除, '~TODO:可以再優化~'
+||build|()|void|O(KN logN) or O(1)
+|檢查距上一次 `build()` 至今是否有 `insert/erase` 被呼叫,
+若有, 重新建樹, 否則不做事
+||forceBuild|()|void|O(KN logN)
+|重新建樹
+|const|query|(Vector const& `v`, +
+size_t `i`, +
+bool `cmp`)|Vectors
+|O(logN) ~Expected~
+|於set中找尋距離 `v` 前 `i` 近的向量, 並依照由近而遠的順序排序.
+如果有兩個向量 `v1`,`v2` 距離一樣, 且 `cmp` 為 `true` , 則直接依照
+`v1 < v2` 來決定誰在前面. 最後回傳一陣列包含所有解.
+||clear|()|void|O(1)
+|清空所有資料
+||reset|(size_t `dimension`)|size_t|O(1)
+|清空所有資料並且指定維度為 `max(1, dimension)` 並且回傳指定後的維度
+|=====================================================================
+
+[NOTE]
+========================================
+* 實測結果發覺比 `KD_Tree` 有效率多了...
+* 'TODO' `insert()`, `erase()` 算是未完成功能
+
+========================================
+
+'''
+
 === meow:: *KD_Tree<Vector, Scalar>* (C++ class)
 ==== Description
 `KD_Tree` 全名k-dimension tree, 用來維護由 *N個K維度向量所成的集合*, 
@@ -472,3 +543,9 @@ Value const& `delta`)
 
 '''
 
+
+== Test
+
+
+== Bug Report / Contact
+  * E-Mail: cat.hook31894 \~在~ gmail.com