diff options
-rw-r--r-- | Makefile | 9 | ||||
-rw-r--r-- | _test/.gitignore | 1 | ||||
-rwxr-xr-x | _test/meowpp | bin | 410859 -> 0 bytes | |||
-rw-r--r-- | _test/meowpp.cpp | 77 | ||||
-rw-r--r-- | meowpp/dsa/KD_Tree.hpp | 3 | ||||
-rw-r--r-- | meowpp/dsa/MergeableHeap.h | 90 | ||||
-rwxr-xr-x | readme_generate.py | 2 |
7 files changed, 127 insertions, 55 deletions
@@ -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 Binary files differdeleted 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; |