change0

7 files changed, 127 insertions, 55 deletions

diff --git a/Makefile b/Makefile
index 12c9cb8..7daa38c 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,11 @@
+CXX      = g++
 CXXFLAGS = -g -Imeowpp
 
+ASCIIDOC       = asciidoc
+ASCIIDOC_FLAGS = -a toc2 -a data-uri -a max-width=70em\
+		 -b html5 \
+		 --theme=volnitsky
+
 README = README.asciidoc
 
 TEST  = _test
@@ -11,9 +17,10 @@ all: $(TESTS)
 
 readme:
 	./readme_generate.py $(README)
+	$(ASCIIDOC) $(ASCIIDOC_FLAGS) $(README)
 	
 $(TEST)/meowpp: $(TEST)/meowpp.cpp
-	g++ -o $@ $(CXXFLAGS) $^
+	$(CXX) -o $@ $(CXXFLAGS) $^
 
 $(TESTS): %: $(TEST)/%
 	$^
diff --git a/_test/.gitignore b/_test/.gitignore
new file mode 100644
index 0000000..1839056
--- /dev/null
+++ b/_test/.gitignore
@@ -0,0 +1 @@
+meowpp
diff --git a/_test/meowpp b/_test/meowpp
deleted file mode 100755
index c84d3b3..0000000
--- a/_test/meowpp
+++ /dev/null
diff --git a/_test/meowpp.cpp b/_test/meowpp.cpp
index ae89e73..e03edaa 100644
--- a/_test/meowpp.cpp
+++ b/_test/meowpp.cpp
@@ -1,59 +1,32 @@
 #include "dsa/KD_Tree.h"
-#include "dsa/SplayTree.h"
-#include "dsa/DisjointSet.h"
-#include "dsa/Heaps.h"
 #include "Usage.h"
 
-#include <cstdio>
-#include <vector>
+bool testColors(){
+}
+bool testDisjointSet(){
+}
+bool testMergeableHeap(){
+}
 
-int main(){
-  meow::Usage usg("hi!");
-  printf("==%s==\n", usg.getUsage().c_str());
-  meow::DisjointSet dsj(10);
-  for(int i = 0; i < 10; i++) printf("%2d ", (int)dsj.root(i));
-  dsj.merge(1, 2);
-  dsj.merge(1, 2);
-  dsj.merge(1, 3);
-  dsj.merge(2, 3);
-  dsj.merge(1, 5);
-  printf("\n");
-  for(int i = 0; i < 10; i++) printf("%2d ", (int)dsj.root(i));
-  printf("\n");
-  dsj.reset(7);
-  meow::MergeableHeap<double> hp;
-  hp.push(5.7);
-  hp.push(5.3);
-  hp.push(5.2);//
-  hp.push(5.1);//
-  meow::MergeableHeap<double> hp2;
-  hp2.push(6.7);
-  hp2.push(4.3);
-  hp2.push(2.2);
-  hp2.push(8.1);//
-  hp.pop();
-  hp2.pop();
-  hp.pop();
-  hp.merge(&hp2);
-  while(!hp.empty()){
-    printf("==%f==\n", hp.top());
-    hp.pop();
-  }
-  meow::KD_Tree<std::vector<double>, double, double> kd(3);
-  std::vector<double> v(3); double k;
-  v[0] = 0; v[1] = 0; v[2] = 0; k = 0.0; kd.insert(v, k);
-  v[0] = 2; v[1] = 0; v[2] = 0; k = 0.1; kd.insert(v, k);
-  v[0] = 0; v[1] = 2; v[2] = 0; k = 0.2; kd.insert(v, k);
-  v[0] = 0; v[1] = 0; v[2] = 2; k = 0.3; kd.insert(v, k);
-  v[0] = 2; v[1] = 2; v[2] = 0; k = 0.4; kd.insert(v, k);
-  v[0] = 2; v[1] = 0; v[2] = 2; k = 0.5; kd.insert(v, k);
-  v[0] = 0; v[1] = 2; v[2] = 2; k = 0.6; kd.insert(v, k);
-  v[0] = 2; v[1] = 2; v[2] = 2; k = 0.7; kd.insert(v, k);
-  v[0] = 0.1; v[1] = 0.9; v[2] = 0.1; k = kd.query(v, 1); printf("//%f//\n", k);
-  v[0] = 0.1; v[1] = 1.9; v[2] = 0.1; k = kd.query(v, 1); printf("//%f//\n", k);
-  v[0] = 1.1; v[1] = 1.9; v[2] = 1.1; k = kd.query(v, 1); printf("//%f//\n", k);
-  v[0] = 0.1; v[1] = 1.9; v[2] = 3.1; k = kd.query(v, 1); printf("//%f//\n", k);
-  v[0] = 0.1; v[1] = -51.9; v[2] = 10.1; k = kd.query(v, 1); printf("//%f//\n", k);
+int main(int argc, char** argv){
+  Usage usg("meowpp"), usg2;
+  usg .addOption('h', "Display this help document");
+  usg2.addOption('t',
+                 "Test the i-th part of the meowpp and then quit",
+                 "<number>", "",
+                 false);
   
+      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);
   return 0;
 }
diff --git a/meowpp/dsa/KD_Tree.hpp b/meowpp/dsa/KD_Tree.hpp
index 9e9a925..ac9f868 100644
--- a/meowpp/dsa/KD_Tree.hpp
+++ b/meowpp/dsa/KD_Tree.hpp
@@ -146,7 +146,7 @@ namespace meow{
   template<class Keys, class Key, class Value>
   inline void KD_Tree<Keys, Key, Value>::build(){
     if(needRebuild){
-      std::vector<size_t> orders[dimension + 1];
+      std::vector<size_t> *orders = new std::vector<size_t>[dimension + 1];
       for(int j = 0; j < dimension + 1; j++){
         orders[j].resize(nodes.size());
       }
@@ -158,6 +158,7 @@ namespace meow{
       }
       root = build(0, (ssize_t)nodes.size() - 1, orders, 0);
       needRebuild = false;
+      delete [] orders;
     }
   }
   template<class Keys, class Key, class Value>
diff --git a/meowpp/dsa/MergeableHeap.h b/meowpp/dsa/MergeableHeap.h
new file mode 100644
index 0000000..1e47afd
--- /dev/null
+++ b/meowpp/dsa/MergeableHeap.h
@@ -0,0 +1,90 @@
+#ifndef   Heap_H__
+#define   Heap_H__
+
+#include <cstdlib>
+
+namespace meow{
+  template<class Element>
+  class MergeableHeap{ // maximum-heap
+    private:
+      struct Node{
+        Element value;
+        Node*   l_child;
+        Node*   r_child;
+        size_t  weight;
+        Node(Element const& _value);
+      };
+      //
+      Node* root;
+      //
+      void  clear(Node* _node              );
+      Node* dup  (Node* _node2             );
+      Node* merge(Node* _left, Node* _right);
+    public:
+      MergeableHeap();
+      MergeableHeap(MergeableHeap const& _heap2);
+      //
+      ~MergeableHeap();
+      //
+      MergeableHeap& operator=(MergeableHeap const& _heap2);
+      void              moveTo(MergeableHeap*       _heap2);
+      //
+      Element const& top  () const;
+      size_t         size () const;
+      size_t         empty() const;
+      //
+      void push (Element const& _value);
+      void pop  (                     );
+      void clear(                     );
+      void merge(MergeableHeap* _heap2);
+  };
+  
+  /*********************************************************
+    @asciidoc
+    === meow:: *MergeableHeap<Key, Value>* (C++ class)
+    .Description
+    MergeableHeap is a kind of maximum-heap with a special method `merge`,
+    which will merge another MergeableHeap into itself in O(logN) time.
+    
+   .Template Request
+   * `Key` should has `operator<`
+
+    .Support methods
+   * N <- number of elements in the heap
+   * M <- number of elements in the other heap if need
+   [options="header",width="100%",cols="1>,1<s,3<,1<,1<,10<",grid="rows"]
+   |=======================================================================
+   |Const?|Name| Parameters| Return Type| Time Complexity| Description
+   ||operator= | (MergeableHeap const&)| *this  | O(N)
+   |    Copy operator.
+   ||moveTo    | (MergeableHeap*)      | void   | O(M)
+   |    Transform the this->data to the heap specified in parameters
+   |const|top  | ()    | Element   | O(1)
+   |    Return the maximum element in the heap.
+   |const|size | ()    | size_t    | O(1)
+   |    Return the number of elements in the heap.
+   |const|empty| ()    | bool      | O(1)
+   |     Return whether the heap is empty or not.
+   ||push    |(Element)  |void   | O(log N) 
+   |    Add a element into the heap
+   ||pop     |()         |void   | O(log N) 
+   |    Delete the maximum element from the heap
+   ||merge   |(MergeableHeap*)   |void   | O(log M)
+   |    Merge the specified MergeableHeap(with size=M) into itself
+   ||clear   |()         |void   | O(N)
+   |    Delete all elements from the heap
+   |=======================================================================
+
+WARNING: Consider there are two MergeableHeap `A` and `B`. +
+`B` will become empty after you call `A.merge(&B)`. +
+The data in `B` will override by data in `A` and `A` will become empty after
+you call `A.moveTo(&B)`
+
+'''
+@asciidoc-
+   *********************************************************/
+}
+
+#include "MergeableHeap.hpp"
+
+#endif // Heap_H__
diff --git a/readme_generate.py b/readme_generate.py
index 7eb6782..b7da90c 100755
--- a/readme_generate.py
+++ b/readme_generate.py
@@ -1,4 +1,4 @@
-#! /usr/bin/python
+#! /usr/bin/env python
 
 import sys;
 import os;