aboutsummaryrefslogtreecommitdiffstats
path: root/meowpp.test/src
diff options
context:
space:
mode:
Diffstat (limited to 'meowpp.test/src')
-rw-r--r--meowpp.test/src/BinaryIndexTree.cpp57
-rw-r--r--meowpp.test/src/DisjointSet.cpp82
-rw-r--r--meowpp.test/src/KD_Tree.cpp190
-rw-r--r--meowpp.test/src/Matrix.cpp45
-rw-r--r--meowpp.test/src/MergeableHeap.cpp74
-rw-r--r--meowpp.test/src/SegmentTree.cpp157
-rw-r--r--meowpp.test/src/SplayTree.cpp477
-rw-r--r--meowpp.test/src/SplayTree_Range.cpp561
-rw-r--r--meowpp.test/src/VP_Tree.cpp189
-rw-r--r--meowpp.test/src/autostitch.cpp618
-rw-r--r--meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp73
-rw-r--r--meowpp.test/src/autostitch_K_Match.cpp36
-rw-r--r--meowpp.test/src/autostitch_RansacCheck.cpp121
-rw-r--r--meowpp.test/src/dsa.cpp80
-rw-r--r--meowpp.test/src/oo.cpp100
15 files changed, 2860 insertions, 0 deletions
diff --git a/meowpp.test/src/BinaryIndexTree.cpp b/meowpp.test/src/BinaryIndexTree.cpp
new file mode 100644
index 0000000..e9a4544
--- /dev/null
+++ b/meowpp.test/src/BinaryIndexTree.cpp
@@ -0,0 +1,57 @@
+#include "meowpp/dsa/BinaryIndexTree.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <vector>
+
+static int N = 100000;
+
+static std::vector<int> array;
+
+inline int sum(int k){
+ int x = 0;
+ for(int i = 0; i <= k; i++){
+ x += array[i];
+ }
+ return x;
+}
+
+static meow::BinaryIndexTree<int> bit;
+
+TEST(BinaryIndexTree, "Test with large data"){
+ size_t tMe = 0, tBi = 0, t0;
+ for(int z = 0; z < 10; z++){
+ meow::messagePrintf(1, "test %d", z);
+ bit.reset(N, 0);
+ array.clear();
+ array.resize(N, 0);
+
+ int NN = rand() % 10000;
+ for(int i = 0; i < NN; i++){
+ int index = rand() % N;
+ if(rand() & 1){
+ int val = rand() % 1000;
+ t0 = clock(); array[i] += val; tMe += clock() - t0;
+ t0 = clock(); bit.update(i, val); tBi += clock() - t0;
+ }else{
+ if(sum(index) != bit.query(index)){
+ meow::messagePrintf(-1, "range-sum query fail");
+ return false;
+ }
+ }
+ }
+ int s = 0;
+ for(int i = 0; i < N; i++){
+ s += array[i];
+ if(s != bit.query(i)){
+ meow::messagePrintf(-1, "range-sum query fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tBi * 1.0 / CLOCKS_PER_SEC,
+ tMe * 1.0 / CLOCKS_PER_SEC);
+ }
+ return true;
+}
diff --git a/meowpp.test/src/DisjointSet.cpp b/meowpp.test/src/DisjointSet.cpp
new file mode 100644
index 0000000..4a8750b
--- /dev/null
+++ b/meowpp.test/src/DisjointSet.cpp
@@ -0,0 +1,82 @@
+#include "meowpp/dsa/DisjointSet.h"
+
+#include "dsa.h"
+
+#include <vector>
+
+
+TEST(DisjointSet, "..."){
+ int N = 10000000;
+ meow::DisjointSet dsj(N);
+
+ meow::messagePrintf(1, "merge(0, 1) merge(0, 2) merge(0, 3) ... (N = %d)", N);
+ for(int i = 1; i < N; i++){
+ dsj.merge(0, i);
+ }
+ int root = dsj.root(0);
+ for(int i = 1; i < N; i++){
+ if(root != (int)dsj.root(i)){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok");
+ //
+
+ dsj.reset(N);
+ meow::messagePrintf(1, "merge(0, 1) merge(1, 2) merge(2, 3) ... (N = %d)", N);
+ for(int i = 1; i < N; i++){
+ dsj.merge(i - 1, i);
+ }
+ root = dsj.root(0);
+ for(int i = 1; i < N; i++){
+ if(root != (int)dsj.root(i)){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok");
+ //
+
+ int M = 1000;
+ N = 1000000;
+ dsj.reset(N);
+ std::vector<int> used(N, -1);
+ std::vector<std::vector<int> > nums(M);
+
+ meow::messagePrintf(1, "random test (N = %d)", N);
+ for(int i = 0; i < N / 10; i++){
+ int grp = rand() % M;
+ int who;
+ while(used[who = rand() % N] != -1);
+ nums[grp].push_back(who);
+ used[who] = grp;
+ }
+ meow::messagePrintf(0, "data created");
+ for(int i = 0; i < M; i++){
+ for(int k = 0; k < 100; k++){
+ int j1 = rand() % nums[i].size();
+ int j2 = rand() % nums[i].size();
+ dsj.merge(nums[i][j1], nums[i][j2]);
+ }
+ for(size_t j = 1; j < nums[i].size(); j++){
+ dsj.merge(nums[i][0], nums[i][j]);
+ }
+ }
+ for(int i = 0; i < N; i++){
+ bool ok = false;
+ if((int)used[i] == -1 && (int)dsj.root(i) == i){
+ ok = true;
+ }else{
+ if(dsj.root(i) == dsj.root(nums[used[i]][0])){
+ ok = true;
+ }
+ }
+ if(!ok){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok");
+ return true;
+}
diff --git a/meowpp.test/src/KD_Tree.cpp b/meowpp.test/src/KD_Tree.cpp
new file mode 100644
index 0000000..8d4232e
--- /dev/null
+++ b/meowpp.test/src/KD_Tree.cpp
@@ -0,0 +1,190 @@
+#include "meowpp/dsa/KD_Tree.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <vector>
+
+#include <cmath>
+#include <cstdlib>
+#include <algorithm>
+#include <ctime>
+#include <queue>
+
+static int N = 10000;
+static int D = 5;
+
+static double dist2(std::vector<double> const& v1, std::vector<double> const& v2){
+ double ret = 0;
+ for(int i = 0; i < D; i++){
+ ret += meow::squ(v1[i] - v2[i]);
+ }
+ return ret;
+}
+
+static std::vector< std::vector<double> > data;
+static std::vector< double > dist;
+static std::vector< int > order;
+
+
+struct Answer{
+ double dist;
+ int id;
+ Answer(double _dist, int _id): dist(_dist), id(_id){ }
+ bool operator<(Answer const& b) const{
+ if(dist != b.dist) return (dist < b.dist);
+ return (id < b.id);
+ }
+};
+
+
+static void find(std::vector<double> const& v, int k){
+ std::priority_queue<Answer> qu;
+ for(int i = 0; i < k; i++){
+ qu.push(Answer(dist2(v, data[i]), i));
+ }
+ for(int i = k; i < N; i++){
+ qu.push(Answer(dist2(v, data[i]), i));
+ qu.pop();
+ }
+ order.resize(k);
+ for(int i = qu.size() - 1; i >= 0; i--){
+ order[i] = qu.top().id;
+ qu.pop();
+ }
+}
+
+static std::vector<double> v;
+
+/*
+static bool sf(const int& a, const int& b){
+ if(dist[a] != dist[b])
+ return (dist[a] < dist[b]);
+ return (a < b);
+}
+
+static void show(std::vector<double> const& ask, std::vector<int> kd, std::vector<int> me, int k){
+ if(N <= 30 && D <= 3){
+ printf("\nData:\n");
+ for(int i = 0; i < N; i++){
+ printf(" %2d) <", i);
+ for(int j = 0; j < D; j++){
+ printf("%.7f", data[i][j]);
+ if(j < D - 1) printf(", ");
+ else printf(">");
+ }
+ printf("\n");
+ }
+ printf("Ask <");
+ for(int j = 0; j < D; j++){
+ printf("%.7f", ask[j]);
+ if(j < D - 1) printf(", ");
+ else printf(">");
+ }
+ printf("\n");
+ printf("MyAnswer: ");
+ for(int i = 0; i < k; i++) printf("%d ", me[i]);
+ printf("\n");
+ printf("KdAnswer: ");
+ for(int i = 0; i < k; i++) printf("%d ", kd[i]);
+ printf("\n");
+ order.resize(N);
+ dist .resize(N);
+ for(int i = 0; i < N; i++){
+ dist [i] = dist2(ask, data[i]);
+ order[i] = i;
+ }
+ std::sort(order.begin(), order.end(), sf);
+ printf("Sorted:\n");
+ for(int i = 0; i < N; i++){
+ printf(" %2d) <", order[i]);
+ for(int j = 0; j < D; j++){
+ printf("%.7f", data[order[i]][j]);
+ if(j < D - 1) printf(", ");
+ else printf(">");
+ }
+ printf(" ((%.7f))", dist[order[i]]);
+ printf("\n");
+ }
+ }
+}
+// */
+
+struct Node{
+ std::vector<double> v;
+ int id;
+ double& operator[](size_t d) { return v[d]; }
+ double operator[](size_t d) const { return v[d]; }
+ bool operator<(Node const& n) const{ return (id < n.id); }
+};
+
+TEST(KD_Tree, "It is very slow"){
+
+ int t0, t1, t2;
+
+ meow::KD_Tree<Node, double> tree(D);
+
+ meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D);
+ data.resize(N);
+ for(int i = 0; i < N; i++){
+ data[i].resize(D);
+ Node nd;
+ nd.v.resize(D);
+ nd.id = i;
+ for(int j = 0; j < D; j++){
+ data[i][j] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3);
+ nd[j] = data[i][j];
+ }
+ tree.insert(nd);
+ }
+ meow::messagePrintf(-1, "ok");
+ meow::messagePrintf(1, "build");
+ t0 = clock();
+ tree.build();
+ meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC);
+
+ meow::messagePrintf(1, "query...");
+ v.resize(D);
+ meow::KD_Tree<Node, double>::Vectors ret;
+ for(int k = 1; k <= std::min(100, N); k++){
+ meow::messagePrintf(1, "range k = %d", k);
+ t1 = t2 = 0;
+ for(int i = 0; i < 10; i++){
+ Node nd;
+ nd.v.resize(D);
+ for(int d = 0; d < D; d++){
+ v[d] = 12345.0 * (1.0 * rand() / RAND_MAX - 0.3);
+ nd[d] = v[d];
+ }
+ t0 = clock();
+ tree.build();
+ ret = tree.query(nd, k, true);
+ t1 += clock() - t0;
+
+ t0 = clock();
+ find(v, k);
+ t2 += clock() - t0;
+ if((int)ret.size() != (int)std::min(k, N)){
+ meow::messagePrintf(-1, "(%d)query fail, size error", i);
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ for(int kk = 1; kk <= k; kk++){
+ if(order[kk - 1] != ret[kk - 1].id){
+ //show(v, ret, order, k);
+ meow::messagePrintf(-1, "(%d)query fail", i);
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ t1 * 1.0 / CLOCKS_PER_SEC,
+ t2 * 1.0 / CLOCKS_PER_SEC
+ );
+ }
+ meow::messagePrintf(-1, "ok");
+
+
+ return true;
+}
diff --git a/meowpp.test/src/Matrix.cpp b/meowpp.test/src/Matrix.cpp
new file mode 100644
index 0000000..2579b0b
--- /dev/null
+++ b/meowpp.test/src/Matrix.cpp
@@ -0,0 +1,45 @@
+#include "meowpp/math/Matrix.h"
+
+#include "dsa.h"
+
+#include <cmath>
+#include <cstdlib>
+
+using namespace meow;
+
+
+
+void print(Matrix<int> const& m){
+ for(size_t r = 0; r < m.rows(); r++){
+ printf("[");
+ for(size_t c = 0; c < m.cols(); c++){
+ printf("%8d", m(r, c));
+ }
+ printf("]\n");
+ }
+}
+
+TEST(Matrix, "Unfinished"){
+ Matrix<int> a(3, 4, 0);
+ Matrix<int> b(3, 4, 0);
+ Matrix<int> c(4, 5, 0);
+ for(int i = 0; i < 3; i++){
+ for(int j = 0; j < 4; j++){
+ a.entry(i, j, rand() % 100);
+ b.entry(i, j, rand() % 100);
+ }
+ }
+ for(int i = 0; i < 4; i++){
+ for(int j = 0; j < 5; j++){
+ c.entry(i, j, rand() % 100);
+ }
+ }
+ printf("A = \n"); print(a);
+ printf("B = \n"); print(b);
+ printf("C = \n"); print(b);
+ printf("A + B = \n"); print(a + b);
+ printf("A * C = \n"); print(a * c);
+ printf("A * B^T = \n"); print(a * b.transpose());
+
+ return true;
+};
diff --git a/meowpp.test/src/MergeableHeap.cpp b/meowpp.test/src/MergeableHeap.cpp
new file mode 100644
index 0000000..e8183ca
--- /dev/null
+++ b/meowpp.test/src/MergeableHeap.cpp
@@ -0,0 +1,74 @@
+#include "meowpp/dsa/MergeableHeap.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <vector>
+#include <queue>
+#include <cstdlib>
+
+
+TEST(MergeableHeap, "..."){
+ int N = 10;
+ std::vector<std::priority_queue<int> > nhp;
+ std::vector<meow::MergeableHeap<int> > mhp;
+ for(int i = 0; i < 10; i++){
+ int MM = 5000 + rand() % 10000;
+ meow::messagePrintf(1, "%d-th test (M = %5d)", i, MM);
+ nhp.clear(); nhp.resize(N);
+ mhp.clear(); mhp.resize(N);
+ int tn = 0, tm = 0, t0;
+ for(int j = 0; j < MM; j++){
+ if((rand() & 3) == 0){
+ int a = rand() % N;
+ int num = rand();
+ t0 = clock(); nhp[a].push(num); tn += clock() - t0;
+ t0 = clock(); mhp[a].push(num); tm += clock() - t0;
+ }else if(rand() & 1){
+ int a = rand() % N;
+ t0 = clock();
+ if(!nhp[a].empty()) nhp[a].pop();
+ tn += clock() - t0;
+ t0 = clock();
+ if(!mhp[a].empty()) mhp[a].pop();
+ tm += clock() - t0;
+ }else{
+ int a = rand() % N, b = rand() % N;
+ if(b == a) b = (b + 1) % N;
+ t0 = clock();
+ for( ; !nhp[b].empty(); nhp[b].pop()){
+ nhp[a].push(nhp[b].top());
+ }
+ tn += clock() - t0;
+ t0 = clock();
+ mhp[a].merge(&mhp[b]);
+ tm += clock() - t0;
+ }
+ }
+ bool ok = true;
+ for(int j = 0; j < N; j++){
+ while(!nhp[j].empty() && !mhp[j].empty()){
+ if(nhp[j].top() != mhp[j].top()){
+ ok = false;
+ break;
+ }
+ nhp[j].pop();
+ mhp[j].pop();
+ }
+ if(mhp[j].empty() != nhp[j].empty()){
+ ok = false;
+ }
+ if(ok == false) break;
+ }
+ ok = true;
+ if(!ok){
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }else{
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tm * 1.0 / CLOCKS_PER_SEC,
+ tn * 1.0 / CLOCKS_PER_SEC );
+ }
+ }
+ return true;
+}
diff --git a/meowpp.test/src/SegmentTree.cpp b/meowpp.test/src/SegmentTree.cpp
new file mode 100644
index 0000000..c795477
--- /dev/null
+++ b/meowpp.test/src/SegmentTree.cpp
@@ -0,0 +1,157 @@
+#include "meowpp/dsa/SegmentTree.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <ctime>
+#include <algorithm>
+
+struct RangeMax{
+ int value;
+ //
+ RangeMax(){}
+ RangeMax(int _value): value(_value){ }
+ RangeMax(RangeMax const& b): value(b.value){ }
+ //
+ RangeMax operator*(size_t n) const{ return RangeMax(value); }
+ RangeMax operator|(RangeMax const& b) const{ return RangeMax(std::max(value, b.value)); }
+ RangeMax operator+(RangeMax const& b) const{ return RangeMax(b.value + value); }
+ bool operator==(RangeMax const& b) const{ return (value == b.value); }
+};
+struct RangeSum{
+ int value;
+ //
+ RangeSum(){}
+ RangeSum(int _value): value(_value){ }
+ RangeSum(RangeSum const& b): value(b.value){ }
+ //
+ RangeSum operator*(size_t n) const{ return RangeSum(n * value); }
+ RangeSum operator|(RangeSum const& b) const{ return RangeSum(value + b.value); }
+ RangeSum operator+(RangeSum const& b) const{ return RangeSum(b.value + value); }
+ bool operator==(RangeSum const& b) const{ return (value == b.value); }
+};
+
+meow::SegmentTree<RangeMax> s_max;
+meow::SegmentTree<RangeSum> s_sum;
+
+static int N = 1000000;
+
+std::vector<int> array;
+
+void override(int a, int b, int c){
+ for(int i = a; i <= b; i++)
+ array[i] = c;
+}
+void offset(int a, int b, int c){
+ for(int i = a; i <= b; i++)
+ array[i] += c;
+}
+int bmax(int a, int b){
+ int ret = array[a];
+ for(int i = a + 1; i <= b; i++)
+ ret = std::max(ret, array[i]);
+ return ret;
+}
+int bsum(int a, int b){
+ int sum = 0;
+ for(int i = a; i <= b; i++)
+ sum += array[i];
+ return sum;
+}
+
+void show(){
+ if(N <= 20){
+ printf("\n");
+ printf("Me : ");
+ for(int i = 0; i < N; i++){
+ printf("%4d ", array[i]);
+ }
+ printf("\n");
+ printf("Sum: ");
+ for(int i = 0; i < N; i++){
+ printf("%4d ", s_sum.query(i, i).value);
+ }
+ printf("\n");
+ printf("Max: ");
+ for(int i = 0; i < N; i++){
+ printf("%4d ", s_max.query(i, i).value);
+ }
+ printf("\n");
+ }
+}
+
+TEST(SegmentTree, "..."){
+ s_max.reset(N);
+ s_sum.reset(N);
+ s_max.override(0, N - 1, RangeMax(0));
+ s_sum.override(0, N - 1, RangeSum(0));
+ array.resize(N, 0);
+
+ for(int z = 0; z < 10; z++){
+ meow::messagePrintf(1, "test %d", z);
+ int tMe = 0, tSeg = 0, t0;
+ int NN = 1 + rand() % 100;
+ for(int i = 0; i < NN; i++){
+ int a = rand() % N;
+ int b = rand() % (N - a) + a;
+ int k = rand() % 20000 - 10000;
+ bool over = (rand() % 2 == 1);
+ if(over){
+ t0 = clock();
+ s_max.override(a, b, RangeMax(k));
+ s_sum.override(a, b, RangeSum(k));
+ tSeg += clock() - t0;
+ t0 = clock();
+ override(a, b, k);
+ tMe += clock() - t0;
+ }else{
+ t0 = clock();
+ s_max.offset(a, b, RangeMax(k));
+ s_sum.offset(a, b, RangeSum(k));
+ tSeg = clock() - t0;
+ t0 = clock();
+ offset(a, b, k);
+ tMe += clock() - t0;
+ }
+ /*
+ printf("\n");
+ printf("%s %d~%d with %d", over ? "override" : "offset", a, b, k);
+ show();
+ printf("max:"); s_max.print();
+ printf("sum:"); s_sum.print();
+ // */
+ }
+ NN = 1 + rand() % 100;
+ for(int i = 0; i < NN; i++){
+ int a = rand() % N;
+ int b = rand() % (N - a) + a;
+
+ t0 = clock();
+ RangeMax m(s_max.query(a, b));
+ RangeSum s(s_sum.query(a, b));
+ tSeg += clock() - t0;
+ t0 = clock();
+ int mm = bmax(a, b);
+ int ss = bsum(a, b);
+ tMe += clock() - t0;
+ if(m.value != mm){
+ printf("ask %d~%d, me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+ meow::messagePrintf(-1, "range-max query fail");
+ return false;
+ }
+ if(s.value != ss){
+ printf("ask %d~%d, max/sum = me %d/%d seg %d/%d\n", a, b, mm, ss, m.value, s.value);
+ meow::messagePrintf(-1, "range-sum query fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok, %.3f/%.3f",
+ 1.0 * tSeg / CLOCKS_PER_SEC,
+ 1.0 * tMe / CLOCKS_PER_SEC);
+ s_max.reset(N);
+ s_sum.reset(N);
+ array.clear();
+ array.resize(N, 0);
+ }
+ return true;
+}
diff --git a/meowpp.test/src/SplayTree.cpp b/meowpp.test/src/SplayTree.cpp
new file mode 100644
index 0000000..ea24fb8
--- /dev/null
+++ b/meowpp.test/src/SplayTree.cpp
@@ -0,0 +1,477 @@
+#include "meowpp/dsa/SplayTree.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <algorithm>
+#include <utility>
+#include <map>
+#include <cstdlib>
+
+static int N;
+
+static bool detail_fg;
+
+typedef typename std::map <int, double>:: iterator IterN;
+typedef typename std::map <int, double>::reverse_iterator IterR;
+typedef typename meow::SplayTree<int, double>::Element IterS;
+
+static std::vector< std::map <int, double> > normal;
+static std::vector<meow::SplayTree<int, double> > splay;
+
+static void show(bool fg = false){
+ if(fg){
+ for(int i = 0; i < N; i++){
+ printf("normal %d-%lu: ", i, normal[i].size());
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ printf("%d/%.2f ", it->first, it->second);
+ }
+ printf("\n");
+ printf("splay %d-%lu: ", i, splay[i].size());
+ for(size_t j = 0; j < splay[i].size(); j++){
+ IterS it = splay[i].order(j);
+ printf("%d/%.2f ", it->first, it->second);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ }
+}
+
+static bool lowerBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= lowerBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool upperBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= upperBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay [i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay [i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a, z;
+ if(normal[i].size() == 0 || normal[i].begin()->first > key){
+ a = normal[i].end();
+ }else{
+ for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){
+ if(z->first > key){
+ break;
+ }
+ }
+ }
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a, z;
+ if(normal[i].begin() == normal[i].end()){
+ a = normal[i].end();
+ }else{
+ if(normal[i].begin()->first >= key) a = normal[i].end();
+ else{
+ for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){
+ if(z->first >= key)
+ break;
+ }
+ }
+ }
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool find(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= find(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool order(int i, int order, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= order(%d, %d)\n", i, order);
+ t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a = normal[i].begin();
+ for(int k = 0; k < order; k++) a++;
+ (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second == b->second);
+}
+static bool first_last(int i, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= first_last(%d)\n", i);
+ IterN a;
+ t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0;
+ t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end());
+ else{
+ if((a->first == b->first && a->second == b->second) == false){
+ return false;
+ }
+ }
+ t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0;
+ t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (r == normal[i].rend()) ? 0 : r->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (r == normal[i].rend()) ? 0 : r->second,
+ (b == splay[i].end()) ? 0 : b->second);
+ if((r == normal[i].rend()) != (b == splay[i].end())) return false;
+ if(r == normal[i].rend());
+ else{
+ if((r->first == b->first && r->second == b->second) == false){
+ return false;
+ }
+ }
+ return true;
+}
+/*
+static bool insert(int i, int key, double val, size_t* tN, size_t* tS){
+ size_t t0;
+ if(rand() & 1){
+ t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0;
+ t0 = clock(); normal[i].insert(std::pair<int, double>(key, val)); (*tN) += clock() - t0;
+ }else{
+ t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0;
+ t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0;
+ }
+ detail_fg && printf("============= insert(%d, %d)\n", i, key);
+ show(detail_fg);
+ return true;
+}
+// */
+static bool split(int i, int j, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ if(i == j){
+ return true;
+ }
+ detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key);
+ t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0;
+ t0 = clock();
+ normal[j].clear();
+ for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){
+ normal[j].insert(*it);
+ normal[i].erase(it);
+ }
+ *tN += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool merge(int i, int j, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ if(i == j){
+ return true;
+ }
+ if(rand() & 1){
+ t0 = clock();
+ if(splay[i].size() > 0)
+ while(splay[j].size() > 0 &&
+ splay[j].first()->first <= splay[i].last()->first){
+ splay[j].erase(splay[j].first()->first);
+ }
+ *tS += clock() - t0;
+ t0 = clock();
+ if(normal[i].size() > 0)
+ while(normal[j].size() > 0 &&
+ normal[j].begin()->first <= normal[i].rbegin()->first)
+ normal[j].erase(normal[j].begin());
+ *tN += clock() - t0;
+ }
+ t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0;
+ t0 = clock();
+ if(normal[i].size() == 0 || normal[j].size() == 0 ||
+ normal[i].rbegin()->first < normal[j].begin()->first ||
+ normal[j].rbegin()->first < normal[i].begin()->first
+ ){
+ for(IterN it = normal[j].begin(); it != normal[j].end(); it++){
+ normal[i].insert(*it);
+ }
+ normal[j].clear();
+ }
+ *tN += clock() - t0;
+ detail_fg && printf("============= merge(%d, %d)\n", i, j);
+ show(detail_fg);
+ return true;
+}
+static bool erase(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= erase(%d, %d)\n", i, key);
+ t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0;
+ t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta);
+ t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0;
+ t0 = clock();
+ std::map<int, double> tmp = normal[i];
+ normal[i].clear();
+ for(IterN it = tmp.begin(); it != tmp.end(); it++){
+ normal[i].insert(std::pair<int, double>(it->first + delta, it->second));
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+/*
+static bool valueOffset(int i, double delta, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta);
+ t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0;
+ t0 = clock();
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ it->second += delta;
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+// */
+static bool copy(int i, int j, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("copy(%d, %d)\n", i, j);
+ t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0;
+ t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+
+static bool check(){
+ for(int i = 0; i < N; i++){
+ if(normal[i].size() != splay[i].size()) return false;
+ int j = 0;
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){
+ if(it->first != splay[i].order(j)->first ||
+ it->second != splay[i].order(j)->second)
+ return false;
+ }
+ }
+ return true;
+}
+
+TEST(SplayTree, "Seems buggy"){
+ detail_fg = false;
+ N = 5;
+ for(int i = 0; i < 10; i++){
+ normal.clear();
+ splay .clear();
+ normal.resize(N);
+ splay .resize(N);
+ size_t tn = 0, tm = 0;
+ int op = 1 + rand() % 2000000;
+ meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op);
+ while(op--){
+ int wh = rand() % 60;
+ int i1 = rand() % N, i2, k = rand() % 60;
+ while((i2 = rand() % N) == i1);
+ switch(wh){
+ case 0:
+ if(lowerBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "lowerBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 1:
+ if(rUpperBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "rUpperBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 2:
+ if(rLowerBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "rLowerBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 3:
+ if(upperBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "upperBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 4:
+ case 5:
+ case 6:
+ if(find(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "find");
+ show(true);
+ return false;
+ }
+ break;
+ case 7:
+ case 8:
+ case 9:
+ if(normal[i1].size() > 0){
+ if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "order");
+ show(true);
+ return false;
+ }
+ break;
+ }
+ case 10:
+ if(first_last(i1, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "first_last");
+ show(true);
+ return false;
+ }
+ break;
+ case 21:
+ case 22:
+ case 23:
+ case 24:
+ case 25:
+ case 26:
+ if(split(i1, i2, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "split");
+ show(true);
+ return false;
+ }
+ break;
+ case 27:
+ case 28:
+ case 29:
+ case 30:
+ case 31:
+ case 32:
+ case 33:
+ case 34:
+ case 35:
+ case 36:
+ if(merge(i1, i2, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "merge");
+ show(true);
+ return false;
+ }
+ break;
+ case 37:
+ case 38:
+ case 39:
+ case 40:
+ if(erase(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "erase");
+ show(true);
+ return false;
+ }
+ break;
+ case 41:
+ case 42:
+ case 43:
+ case 44:
+ case 45:
+ case 46:
+ case 47:
+ case 48:
+ case 49:
+ if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "keyOffset");
+ show(true);
+ return false;
+ }
+ break;
+ case 50:
+ case 51:
+ case 52:
+ if(copy(i1, i2, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "copy");
+ show(true);
+ return false;
+ }
+ break;
+ case 53:
+ case 54:
+ case 55:
+ case 56:
+ case 57:
+ case 58:
+ case 59:
+ op++;
+ /*
+ if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+ show(true);
+ return false;
+ }
+ break;
+ // */
+ }
+ }
+ if(!check()){
+ meow::messagePrintf(-1, "fail");
+ show(true);
+ return false;
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tm * 1.0 / CLOCKS_PER_SEC,
+ tn * 1.0 / CLOCKS_PER_SEC);
+ }
+ return true;
+}
diff --git a/meowpp.test/src/SplayTree_Range.cpp b/meowpp.test/src/SplayTree_Range.cpp
new file mode 100644
index 0000000..e6d857b
--- /dev/null
+++ b/meowpp.test/src/SplayTree_Range.cpp
@@ -0,0 +1,561 @@
+#include "meowpp/dsa/SplayTree.h"
+#include "meowpp/utility.h"
+
+#include "dsa.h"
+
+#include <algorithm>
+#include <utility>
+#include <map>
+#include <cstdlib>
+#include <cmath>
+
+static int min_sum;
+struct Double{
+ double k;
+ Double(): k(0){ }
+ Double(double _k): k(0){ }
+ bool operator==(const Double& b) const{ return fabs(k - b.k) <= 1e-9; }
+ bool operator!=(const Double& b) const{ return fabs(k - b.k) > 1e-9; }
+ bool operator<(const Double& b) const{ return k < b.k; }
+ Double operator+(const Double& b) const{ return Double(k + b.k); }
+ Double operator*(size_t& b) const{
+ if(min_sum == 0) return Double(k);
+ else return Double(k * b);
+ }
+ Double operator|(const Double& b) const{
+ if(min_sum == 0) return Double(std::min(k, b.k));
+ else return Double(k + b.k);
+ }
+};
+
+static int N;
+
+static bool detail_fg;
+
+typedef typename std::map <int, Double>:: iterator IterN;
+typedef typename std::map <int, Double>::reverse_iterator IterR;
+typedef typename meow::SplayTree_Range<int, Double>::Element IterS;
+
+static std::vector< std::map <int, Double> > normal;
+static std::vector<meow::SplayTree_Range<int, Double> > splay;
+
+static void show(bool fg = false){
+ if(fg){
+ for(int i = 0; i < N; i++){
+ printf("normal %d-%lu: ", i, normal[i].size());
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ printf("%d/%.2f ", it->first, it->second.k);
+ }
+ printf("\n");
+ printf("splay %d-%lu: ", i, splay[i].size());
+ for(size_t j = 0; j < splay[i].size(); j++){
+ IterS it = splay[i].order(j);
+ printf("%d/%.2f ", it->first, it->second.k);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ }
+}
+
+static bool lowerBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= lowerBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].lowerBound (key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].lower_bound(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool upperBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= upperBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].upperBound (key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].upper_bound(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay [i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay [i].end()) ? 0 : b->second.k);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool rLowerBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= rLowerBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].rLowerBound(key); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a, z;
+ if(normal[i].size() == 0 || normal[i].begin()->first > key){
+ a = normal[i].end();
+ }else{
+ for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); z++, a++){
+ if(z->first > key){
+ break;
+ }
+ }
+ }
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool rUpperBound(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= rUpperBound(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].rUpperBound(key); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a, z;
+ if(normal[i].begin() == normal[i].end()){
+ a = normal[i].end();
+ }else{
+ if(normal[i].begin()->first >= key) a = normal[i].end();
+ else{
+ for(a = normal[i].begin(), z = a, z++; z != normal[i].end(); a++, z++){
+ if(z->first >= key)
+ break;
+ }
+ }
+ }
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool find(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= find(%d, %d)\n", i, key);
+ t0 = clock(); IterS b = splay [i].find(key); (*tS) += clock() - t0;
+ t0 = clock(); IterN a = normal[i].find(key); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool order(int i, int order, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= order(%d, %d)\n", i, order);
+ t0 = clock(); IterS b = splay[i].order(order); (*tS) += clock() - t0;
+ t0 = clock();
+ IterN a = normal[i].begin();
+ for(int k = 0; k < order; k++) a++;
+ (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ show(detail_fg);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end()) return true;
+ return (a->first == b->first && a->second.k == b->second.k);
+}
+static bool first_last(int i, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= first_last(%d)\n", i);
+ IterN a;
+ t0 = clock(); IterS b = splay[i].first (); (*tS) += clock() - t0;
+ t0 = clock(); a = normal[i].begin(); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (a == normal[i].end()) ? 0 : a->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (a == normal[i].end()) ? 0 : a->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ if((a == normal[i].end()) != (b == splay[i].end())) return false;
+ if( a == normal[i].end());
+ else{
+ if((a->first == b->first && a->second.k == b->second.k) == false){
+ return false;
+ }
+ }
+ t0 = clock(); b = splay[i].last (); (*tS) += clock() - t0;
+ t0 = clock(); IterR r = normal[i].rbegin(); (*tN) += clock() - t0;
+ detail_fg && printf(">>get (%d)-(%d) %.2f %.2f\n",
+ (r == normal[i].rend()) ? 0 : r->first,
+ (b == splay[i].end()) ? 0 : b->first,
+ (r == normal[i].rend()) ? 0 : r->second.k,
+ (b == splay[i].end()) ? 0 : b->second.k);
+ if((r == normal[i].rend()) != (b == splay[i].end())) return false;
+ if(r == normal[i].rend());
+ else{
+ if((r->first == b->first && r->second.k == b->second.k) == false){
+ return false;
+ }
+ }
+ return true;
+}
+static bool insert(int i, int key, Double val, size_t* tN, size_t* tS){
+ size_t t0;
+ if(rand() & 1){
+ t0 = clock(); splay [i].insert(key, val); (*tS) += clock() - t0;
+ t0 = clock(); normal[i].insert(std::pair<int, Double>(key, val)); (*tN) += clock() - t0;
+ }else{
+ t0 = clock(); splay [i][key] = val; (*tS) += clock() - t0;
+ t0 = clock(); normal[i][key] = val; (*tN) += clock() - t0;
+ }
+ detail_fg && printf("============= insert(%d, %d)\n", i, key);
+ show(detail_fg);
+ return true;
+}
+static bool split(int i, int j, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ if(i == j){
+ return true;
+ }
+ detail_fg && printf("============= split(%d, %d, %d)\n", i, j, key);
+ t0 = clock(); splay[i].splitOut(key, &splay[j]); *tS += clock() - t0;
+ t0 = clock();
+ normal[j].clear();
+ for(IterN it; (it = normal[i].upper_bound(key)) != normal[i].end(); ){
+ normal[j].insert(*it);
+ normal[i].erase(it);
+ }
+ *tN += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool merge(int i, int j, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ if(i == j){
+ return true;
+ }
+ if(rand() & 1){
+ t0 = clock();
+ if(splay[i].size() > 0)
+ while(splay[j].size() > 0 &&
+ splay[j].first()->first <= splay[i].last()->first){
+ splay[j].erase(splay[j].first()->first);
+ }
+ *tS += clock() - t0;
+ t0 = clock();
+ if(normal[i].size() > 0)
+ while(normal[j].size() > 0 &&
+ normal[j].begin()->first <= normal[i].rbegin()->first)
+ normal[j].erase(normal[j].begin());
+ *tN += clock() - t0;
+ }
+ t0 = clock(); splay[i].merge(&splay[j]); *tS += clock() - t0;
+ t0 = clock();
+ if(normal[i].size() == 0 || normal[j].size() == 0 ||
+ normal[i].rbegin()->first < normal[j].begin()->first ||
+ normal[j].rbegin()->first < normal[i].begin()->first
+ ){
+ for(IterN it = normal[j].begin(); it != normal[j].end(); it++){
+ normal[i].insert(*it);
+ }
+ normal[j].clear();
+ }
+ *tN += clock() - t0;
+ detail_fg && printf("============= merge(%d, %d)\n", i, j);
+ show(detail_fg);
+ return true;
+}
+static bool erase(int i, int key, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= erase(%d, %d)\n", i, key);
+ t0 = clock(); splay[i].erase(key); (*tS) += clock() - t0;
+ t0 = clock(); normal[i].erase(key); (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool keyOffset(int i, int delta, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= keyOffset(%d, %d)\n", i, delta);
+ t0 = clock(); splay[i].keyOffset(delta); (*tS) += clock() - t0;
+ t0 = clock();
+ std::map<int, Double> tmp = normal[i];
+ normal[i].clear();
+ for(IterN it = tmp.begin(); it != tmp.end(); it++){
+ normal[i].insert(std::pair<int, Double>(it->first + delta, it->second.k));
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool valueOffset(int i, Double delta, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= valueOffset(%d, %f)\n", i, delta.k);
+ t0 = clock(); splay[i].valueOffset(delta); (*tS) += clock() - t0;
+ t0 = clock();
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ it->second = it->second + delta;
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool valueOverride(int i, Double value, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= valueOverride(%d, %f)\n", i, value.k);
+ t0 = clock(); splay[i].valueOverride(value); (*tS) += clock() - t0;
+ t0 = clock();
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ it->second.k = value.k;
+ }
+ (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+static bool query(int i, int a, int b, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("============= query(%d, %d, %d)\n", i, a, b);
+ Double ans1, ans2 = 0;
+ if((rand() & 3) == 3){
+ t0 = clock(); ans1 = splay[i].query(); (*tS) += clock() - t0;
+ t0 = clock();
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ ans2 = ans2 | it->second.k;
+ }
+ }else{
+ t0 = clock(); ans1 = splay[i].query(a, b); (*tS) += clock() - t0;
+ t0 = clock();
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++){
+ if(a <= it->first && it->first <= b)
+ ans2 = ans2 | it->second.k;
+ }
+ }
+ detail_fg && printf(">>get %f %f\n", ans1.k, ans2.k);
+ show(detail_fg);
+ return true;
+}
+static bool copy(int i, int j, size_t* tN, size_t* tS){
+ size_t t0;
+ detail_fg && printf("copy(%d, %d)\n", i, j);
+ t0 = clock(); splay[i] = splay[j]; (*tS) += clock() - t0;
+ t0 = clock(); normal[i] = normal[j]; (*tN) += clock() - t0;
+ show(detail_fg);
+ return true;
+}
+
+static bool check(){
+ for(int i = 0; i < N; i++){
+ if(normal[i].size() != splay[i].size()) return false;
+ int j = 0;
+ for(IterN it = normal[i].begin(); it != normal[i].end(); it++, j++){
+ if(it->first != splay[i].order(j)->first ||
+ it->second.k != splay[i].order(j)->second.k)
+ return false;
+ }
+ }
+ return true;
+}
+
+TEST(SplayTree_Range, "..."){
+ detail_fg = false;
+ N = 5;
+ for(int i = 0; i < 10; i++){
+ normal.clear();
+ splay .clear();
+ normal.resize(N);
+ splay .resize(N);
+ size_t tn = 0, tm = 0;
+ int op = 1 + rand() % 2000000;
+ min_sum = rand() & 1;
+ meow::messagePrintf(1, "%d-th test, N = %d, op = %7d", i, N, op);
+ while(op--){
+ int wh = rand() % 100;
+ int i1 = rand() % N, i2, k = rand() % 60;
+ while((i2 = rand() % N) == i1);
+ switch(wh){
+ case 0:
+ if(lowerBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "lowerBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 1:
+ if(rUpperBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "rUpperBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 2:
+ if(rLowerBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "rLowerBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 3:
+ if(upperBound(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "upperBound");
+ show(true);
+ return false;
+ }
+ break;
+ case 4:
+ case 5:
+ case 6:
+ if(find(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "find");
+ show(true);
+ return false;
+ }
+ break;
+ case 7:
+ case 8:
+ case 9:
+ if(normal[i1].size() > 0){
+ if(order(i1, rand() % normal[i1].size(), &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "order");
+ show(true);
+ return false;
+ }
+ break;
+ }
+ case 10:
+ if(first_last(i1, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "first_last");
+ show(true);
+ return false;
+ }
+ break;
+ case 11:
+ case 12:
+ case 13:
+ case 14:
+ case 15:
+ case 16:
+ case 17:
+ case 18:
+ case 19:
+ case 20:
+ if(insert(i1, k, rand() * 1.0 / RAND_MAX * 50 + 1, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "insert");
+ show(true);
+ return false;
+ }
+ break;
+ case 21:
+ case 22:
+ case 23:
+ case 24:
+ case 25:
+ case 26:
+ if(split(i1, i2, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "split");
+ show(true);
+ return false;
+ }
+ break;
+ case 27:
+ case 28:
+ case 29:
+ case 30:
+ case 31:
+ case 32:
+ case 33:
+ case 34:
+ case 35:
+ case 36:
+ if(merge(i1, i2, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "merge");
+ show(true);
+ return false;
+ }
+ break;
+ case 37:
+ case 38:
+ case 39:
+ case 40:
+ if(erase(i1, k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "erase");
+ show(true);
+ return false;
+ }
+ break;
+ case 41:
+ case 42:
+ case 43:
+ case 44:
+ case 45:
+ case 46:
+ case 47:
+ case 48:
+ case 49:
+ if(keyOffset(i1, ((rand() & 2) - 1) * k, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "keyOffset");
+ show(true);
+ return false;
+ }
+ break;
+ case 50:
+ case 51:
+ case 52:
+ if(copy(i1, i2, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "copy");
+ show(true);
+ return false;
+ }
+ break;
+ case 53:
+ case 54:
+ case 55:
+ case 56:
+ case 57:
+ case 58:
+ case 59:
+ if(valueOverride(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+ show(true);
+ return false;
+ }
+ break;
+ case 60:
+ case 61:
+ case 62:
+ case 63:
+ case 64:
+ case 65:
+ case 66:
+ if(valueOffset(i1, 1.0 * rand() / RAND_MAX * 100 + 1, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "valueOffset");
+ show(true);
+ return false;
+ }
+ break;
+ default:
+ if(query(i1, rand() % 200 - 100, rand() % 200 - 100, &tn, &tm) == false){
+ meow::messagePrintf(-1, "fail(%s)", "query");
+ show(true);
+ return false;
+ }
+ break;
+ }
+ }
+ if(!check()){
+ meow::messagePrintf(-1, "fail");
+ show(true);
+ return false;
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ tm * 1.0 / CLOCKS_PER_SEC,
+ tn * 1.0 / CLOCKS_PER_SEC);
+ }
+ return true;
+}
diff --git a/meowpp.test/src/VP_Tree.cpp b/meowpp.test/src/VP_Tree.cpp
new file mode 100644
index 0000000..8e93224
--- /dev/null
+++ b/meowpp.test/src/VP_Tree.cpp
@@ -0,0 +1,189 @@
+#include "meowpp/dsa/VP_Tree.h"
+#include "meowpp/dsa/KD_Tree.h"
+#include "meowpp/utility.h"
+
+
+#include "dsa.h"
+
+#include <vector>
+
+#include <cmath>
+#include <cstdlib>
+#include <algorithm>
+#include <ctime>
+
+extern "C" {
+#include <sys/types.h>
+}
+
+#include <queue>
+
+static int N = 100000;
+static int D = 32;
+static int MAX = 1000;
+
+typedef int64_t lnt;
+
+struct MyVector{
+ std::vector<lnt> v;
+ int w;
+ //
+ MyVector(MyVector const& _v): v(_v.v), w(_v.w){ }
+ MyVector( ):v(D){ for(int i = 0; i < D; i++){ v[i] = (lnt)rand() % MAX; } }
+ MyVector(lnt k):v(D){ for(int i = 0; i < D; i++){ v[i] = k; } }
+ //
+ lnt & operator[](size_t n) { return v[n]; }
+ lnt const& operator[](size_t n) const{ return v[n]; }
+ bool operator<(MyVector const& v2) const{ return (w < v2.w); }
+ bool operator==(MyVector const& v2) const{
+ for(int i = 0; i < D; i++) if(v[i] != v2[i]) return false;
+ return (w == v2.w);
+ }
+};
+
+
+static lnt dist2(MyVector const& v1, MyVector const& v2){
+ lnt k = 0;
+ for(int i = 0; i < D; i++){
+ k += (v1[i] - v2[i]) * (v1[i] - v2[i]);
+ }
+ return k;
+}
+
+static std::vector<MyVector> data;
+
+void show(MyVector const& v, std::vector<MyVector> const& r1, std::vector<MyVector> const& r2){
+ if(N <= 20 && r1.size() <= 7){
+ printf("\n");
+ for(int i = 0; i < N; i++){
+ printf("%3d) ", data[i].w);
+ for(int j = 0; j < D; j++)
+ printf("%8ld ", data[i][j]);
+ printf(" ===> %ld\n", dist2(data[i], v));
+ }
+ printf("\n");
+ printf("ask) ");
+ for(int j = 0; j < D; j++)
+ printf("%8ld ", v[j]);
+ printf("\n");
+ printf("---------\n");
+ for(size_t i = 0; i < r1.size(); i++){
+ printf("%3d) ", r1[i].w);
+ for(int j = 0; j < D; j++)
+ printf("%8ld ", r1[i][j]);
+ printf(" ===> %ld\n", dist2(r1[i], v));
+ }
+ printf("---------\n");
+ for(size_t i = 0; i < r2.size(); i++){
+ printf("%3d) ", r2[i].w);
+ for(int j = 0; j < D; j++)
+ printf("%8ld ", r2[i][j]);
+ printf(" ===> %ld\n", dist2(r2[i], v));
+ }
+ }
+}
+
+namespace VP{
+ struct Answer{
+ int i;
+ lnt d;
+ //
+ Answer(int _i, lnt _d): i(_i), d(_d){ }
+ Answer(Answer const& _a): i(_a.i), d(_a.d){ }
+ //
+ bool operator<(Answer const& b) const{
+ if(d != b.d) return (d < b.d);
+ else return (data[i] < data[b.i]);
+ }
+ };
+}
+
+static std::vector<MyVector> find(MyVector const& v, int k){
+ std::priority_queue<VP::Answer> qu;
+ for(int i = 0; i < std::min(k, N); i++){
+ qu.push(VP::Answer(i, dist2(v, data[i])));
+ }
+ for(int i = std::min(k, N); i < N; i++){
+ qu.push(VP::Answer(i, dist2(v, data[i])));
+ qu.pop();
+ }
+ std::vector<MyVector> ret(qu.size());
+ for(int i = (ssize_t)qu.size() - 1; i >= 0; i--){
+ ret[i] = data[qu.top().i];
+ qu.pop();
+ }
+ return ret;
+}
+
+TEST(VP_Tree, "A little bit slow"){
+ int t0, t1, t2;
+
+ meow::VP_Tree<MyVector, lnt> tree(D);
+
+ meow::messagePrintf(1, "Create data (N = %d, D = %d)", N, D);
+ data.resize(N);
+ for(int i = 0; i < N; i++){
+ if(i <= N / 10)
+ data[i] = MyVector((lnt)i);
+ else{
+ for(int j = 0; j < D; j++){
+ data[i][j] = rand() % MAX;
+ }
+ }
+ }
+ for(int i = 0; i < N; i++){
+ data[i].w = i;
+ }
+ for(int i = 0; i < N; i++){
+ tree.insert(data[i]);
+ }
+ meow::messagePrintf(-1, "ok");
+ meow::messagePrintf(1, "build");
+ t0 = clock();
+ tree.build();
+ //tree.print();
+ meow::messagePrintf(-1, "ok, %.3f seconds", (clock() - t0) * 1.0 / CLOCKS_PER_SEC);
+
+ meow::messagePrintf(1, "query...");
+ meow::KD_Tree<MyVector, lnt>::Vectors ret1, ret2;
+ for(int k = 1; k <= std::min(100, N); k++){
+ meow::messagePrintf(1, "range k = %d", k);
+ t1 = t2 = 0;
+ for(int i = 0; i < 10; i++){
+ MyVector ask;
+
+ t0 = clock();
+ tree.build();
+ ret1 = tree.query(ask, k, true);
+ t1 += clock() - t0;
+
+ t0 = clock();
+ ret2 = find(ask, k);
+ t2 += clock() - t0;
+
+ if(ret1.size() != ret2.size() && false){
+ meow::messagePrintf(-1, "(%d)query fail, size error", i);
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ for(int kk = 0, KK = ret1.size(); kk < KK; kk++){
+ if(ret1[kk] == ret2[kk]){
+ continue;
+ }
+ show(ask, ret1, ret2);
+ meow::messagePrintf(-1, "(%d)query fail", i);
+ meow::messagePrintf(-1, "fail");
+ return false;
+ }
+ }
+ meow::messagePrintf(-1, "ok %.3f/%.3f",
+ t1 * 1.0 / CLOCKS_PER_SEC,
+ t2 * 1.0 / CLOCKS_PER_SEC
+ );
+ }
+ meow::messagePrintf(-1, "ok");
+
+
+ return true;
+}
+
diff --git a/meowpp.test/src/autostitch.cpp b/meowpp.test/src/autostitch.cpp
new file mode 100644
index 0000000..e63ef43
--- /dev/null
+++ b/meowpp.test/src/autostitch.cpp
@@ -0,0 +1,618 @@
+#include <cstdio>
+
+#include "autostitch.h"
+
+#include <opencv/cv.h>
+#include <opencv/highgui.h>
+
+#include "meowpp/Usage.h"
+
+#include "meowpp/colors/RGB_Space.h"
+
+#include "meowpp/dsa/DisjointSet.h"
+
+#include "meowpp/geo/Vectors.h"
+
+#include "meowpp/gra/Bitmap.h"
+#include "meowpp/gra/Photo.h"
+#include "meowpp/gra/Camera.h"
+#include "meowpp/gra/WatchBall.h"
+
+#include "meowpp/math/utility.h"
+#include "meowpp/math/methods.h"
+
+
+extern "C"{
+#include <sys/types.h>
+#include <dirent.h>
+}
+
+#include <vector>
+#include <algorithm>
+#include <string>
+#include <cstdlib>
+
+
+using namespace meow;
+
+//////////////////////////////////////////////////////////////////////
+
+Usage usg("autostitch");
+
+double p0 = 0.07, P = 0.99;
+double q = 0.7, r = 0.01, Q = 0.97;
+double stop = 1;
+double o_radius = 500;
+
+MyK_Match match;
+std::vector<Bitmap<RGBf_Space> > input_bitmap;
+std::vector<Bitmap<RGBf_Space> > output_bitmap;
+
+std::vector<std::vector<FeaturePoint<double, double> > > fps;
+std::vector<std::vector<Vector<double> > > fpsv;
+std::vector<std::vector<FeaturePointIndexPairs > > pairs;
+
+struct OutputSet {
+ struct Edge {
+ std::vector<Vector<double> > v1;
+ std::vector<Vector<double> > v2;
+ size_t i1, i2;
+ bool done;
+ Edge(size_t ii1, size_t ii2): i1(ii1), i2(ii2) {
+ done = false;
+ }
+ bool operator<(Edge const& e) const {
+ return (v1.size() < e.v1.size());
+ }
+ };
+ std::vector<Camera<RGBf_Space> > cameras;
+ std::vector<Edge> edges;
+};
+
+std::vector<OutputSet> outputs;
+
+//////////////////////////// **# setup #** ///////////////////////////
+bool setup(int argc, char** argv) {
+ usg.optionAdd('h', "Display this help document.");
+ usg.optionAdd('i',
+ "Specify the input images are in <type> "
+ "instead of specifying from arguments",
+ "<dirname>", "",
+ false);
+ usg.optionAdd('o',
+ "Output file name, (not include '.jpg' suffix)",
+ "<filename>",
+ "output",
+ false);
+ usg.optionAdd('d',
+ "Specify which Feature-Point-Detect algorithm to use",
+ "<algorithm>",
+ "",
+ true);
+ usg.optionAdd('p',
+ "Pribabilicity for RANSAC to choose a right feature point",
+ "<floating point>", stringPrintf("%.10f", p0),
+ false);
+ usg.optionAdd('P',
+ "Pribabilicity for RANSAC access",
+ "<floating point>", stringPrintf("%.10f", P),
+ false);
+ usg.optionAdd('q',
+ "p1 for Prob. Model",
+ "<floationg Point>", stringPrintf("%.10f", q),
+ false);
+ usg.optionAdd('r',
+ "p0 for Prob. Model",
+ "<floationg Point>", stringPrintf("%.10f", r),
+ false);
+ usg.optionAdd('Q',
+ "p_min for Prob. Model",
+ "<floationg Point>", stringPrintf("%.10f", Q),
+ false);
+ usg.optionAdd('s',
+ "stop threshold for boundle adjustment",
+ "<floationg Point>", stringPrintf("%.10f", stop),
+ false);
+ usg.optionAdd('O',
+ "output ball radius",
+ "<floationg Point>", stringPrintf("%.10f", o_radius),
+ false);
+ std::vector<std::string> fpsd_algorithm_list = ObjSelector<FPSD_ID>::names();
+ for (size_t i = 0, I = fpsd_algorithm_list.size(); i < I; i++) {
+ const ObjBase* tmp = ObjSelector<FPSD_ID>::get(fpsd_algorithm_list[i]);
+ usg.optionValueAcceptAdd('d',
+ fpsd_algorithm_list[i],
+ tmp->type());
+ usg.import(((MyFeaturePointsDetector*)tmp)->usage());
+ }
+ usg.import(match.usage());
+ usg.import(MyRansacCheck::usage());
+ // set arg
+ std::string err_msg;
+ bool ok = usg.arguments(argc, argv, &err_msg);
+ if (usg.hasOptionSetup('h')) {
+ printf("%s\n", usg.usage().c_str());
+ exit(0);
+ }
+ if (!ok) {
+ fprintf(stderr, "%s\n", err_msg.c_str());
+ exit(-1);
+ }
+ return true;
+}
+
+
+//////////////// **# Input images and convert it #** /////////////////
+bool input() {
+ std::vector<std::string> input_name;
+ if (!usg.hasOptionSetup('i')) {
+ input_name = usg.procArgs();
+ }
+ else {
+ std::string base = usg.optionValue('i', 0);
+ if (base.length() == 0 || base[base.length() - 1] != '/') {
+ base += "/";
+ }
+ DIR* dir = opendir(base.c_str());
+ if (!dir) {
+ fprintf(stderr, "can't open dir '%s'\n", base.c_str());
+ return -1;
+ }
+ for (dirent* ent; (ent = readdir(dir)) != NULL; ) {
+ if (!cstringEndWith(ent->d_name, 4, ".jpeg", ".jpg", ".JPG", ".JPEG")) {
+ continue;
+ }
+ input_name.push_back(base + std::string(ent->d_name));
+ }
+ }
+ messagePrintf(1, "Loading images");
+ for (size_t i = 0; i < input_name.size(); i++) {
+ messagePrintf(1, "%s", input_name[i].c_str());
+ cv::Mat img = cv::imread(input_name[i], CV_LOAD_IMAGE_COLOR);
+ if (!img.data) {
+ messagePrintf(-1, "opencv read error!, ignore");
+ continue;
+ }
+ size_t width = img.size().width ;
+ size_t height = img.size().height;
+ size_t index = input_bitmap.size();
+ input_bitmap.resize(index + 1);
+ input_bitmap[index].size(height, width, RGBf_Space(0));
+ for (size_t x = 0; x < width; x++) {
+ for (size_t y = 0; y < height; y++) {
+ RGBi_Space tmp(Vector3D<int>(
+ img.at<cv::Vec3b>(y, x)[2],
+ img.at<cv::Vec3b>(y, x)[1],
+ img.at<cv::Vec3b>(y, x)[0]));
+ RGBf_Space p;
+ colorTransformate(tmp, &p);
+ input_bitmap[index].pixel(y, x, p);
+ }
+ }
+ messagePrintf(-1, "%lux%lu, ok", width, height);
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+//////////////////////// **# FeaturePoint #** ////////////////////////
+bool detect() {
+ std::string fpsd_algo_name = usg.optionValue('d', 0);
+ MyFeaturePointsDetector* detector(
+ (MyFeaturePointsDetector*)ObjSelector<FPSD_ID>::create(fpsd_algo_name));
+ detector->usage(usg);
+ fps .resize(input_bitmap.size());
+ fpsv.resize(input_bitmap.size());
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ messagePrintf(1, "Detect the feature points for %lu-th pic", i);
+ fps[i] = detector->detect(input_bitmap[i]);
+ messagePrintf(-1, "ok, %lu", fps[i].size());
+ for (size_t j = 0, J = fps[i].size(); j < J; j++) {
+ fpsv[i].push_back(fps[i][j].position());
+ }
+ }
+ delete detector;
+ return true;
+}
+
+
+//////////////////////////// **# k-match #** /////////////////////////
+bool kmatch() {
+ match.usage(usg);
+ messagePrintf( 1, "run k-match");
+ FeaturePointIndexPairs mat(match.match(fps));
+ pairs.resize(input_bitmap.size());
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ pairs[i].resize(I);
+ }
+ for (size_t i = 0, I = mat.size(); i < I; ++i) {
+ pairs[mat[i].from.first][mat[i].to.first].push_back(mat[i]);
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+//////////////////////////// **# RANSAC #** //////////////////////////
+bool ransac() {
+ messagePrintf( 1, "RANSAC");
+ MyRansacCheck::usage(usg);
+ // tmp output
+ p0 = inRange(0.00001, 0.9999, atof(usg.optionValue('p', 0).c_str()));
+ P = inRange(0.00001, 0.9999, atof(usg.optionValue('P', 0).c_str()));
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ for (size_t j = 0, J = input_bitmap.size(); j < J; j++) {
+ size_t num = 3u;
+ messagePrintf( 1, "ransac %lu --- %lu", i, j);
+ MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]));
+ FeaturePointIndexPairs ret = ransac(pairs[i][j], chk, num, p0, P);
+ if (!ret.empty()) {
+ chk.rememberVCalc(ret);
+ FeaturePointIndexPairs ok(ret);
+ for (size_t k = 0, K = pairs[i][j].size(); k < K; k++) {
+ bool chk_again = true;
+ for (size_t l = 0, L = ret.size(); chk_again && l < L; l++) {
+ if (ret[l] == pairs[i][j][k]) {
+ chk_again = false;
+ }
+ }
+ if (chk_again && chk.ok(pairs[i][j][k])) {
+ ok.push_back(pairs[i][j][k]);
+ }
+ }
+ if (ok.size() >= num) pairs[i][j] = ok;
+ else pairs[i][j].clear();
+ messagePrintf(-1, "ok(%lu)", pairs[i][j].size());
+ }
+ else {
+ pairs[i][j].clear();
+ messagePrintf(-1, "empty");
+ }
+ }
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+///////////////////////// **# prob module #** ////////////////////////
+bool prob_mod() {
+ q = inRange(0.00001, 0.99999, atof(usg.optionValue('q', 0).c_str()));
+ r = inRange(0.00001, 0.99999, atof(usg.optionValue('r', 0).c_str()));
+ Q = inRange(0.00001, 0.99999, atof(usg.optionValue('Q', 0).c_str()));
+ double m_ni = log(q * (1 - r)) - log(r * (1 - q));
+ double c = log(Q) - log(1 - Q);
+ double m_nf = log(1 - r) - log(1 - q);
+ messagePrintf(1, "run prob_mod, ni * %.7f > %.7f + nf * %.7f ???",
+ m_ni, c, m_nf);
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ for (size_t j = 0, J = input_bitmap.size(); j < J; j++) {
+ if (pairs[i][j].empty()) {
+ continue;
+ }
+ double ni = pairs[i][j].size(), nf = 0;
+ MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]));
+ chk.rememberVCalc(pairs[i][j]);
+ for (size_t k = 0, K = fpsv[i].size(); k < K; k++) {
+ Vector2D<double> to(chk.to(Vector2D<double>(fpsv[i][k](0),
+ fpsv[i][k](1))));
+ if (0 <= to.x() && to.x() <= (double)input_bitmap[j].width() &&
+ 0 <= to.y() && to.y() <= (double)input_bitmap[j].height()) {
+ nf++;
+ }
+ }
+ if (ni * m_ni > c + m_nf * nf) {
+ messagePrintf(0, "accept %lu --- %lu", i, j);
+ messagePrintf(0,
+ "%.0f * %.3f = %.3f ?? %.3f = %.3f + %.3f * %.0f",
+ ni, m_ni, ni * m_ni, c + m_nf * nf, c, m_nf, nf);
+ continue;
+ }
+ else {
+ pairs[i][j].clear();
+ }
+ }
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+///////////////////// **# group them together #** ////////////////////
+bool group() {
+ messagePrintf(1, "group");
+ // union
+ DisjointSet dsj(input_bitmap.size());
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ for (size_t j = 0; j < I; j++) {
+ if(pairs[i][j].empty()) continue;
+ dsj.merge(i, j);
+ }
+ }
+ std::vector<size_t> root;
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ if (dsj.root(i) == i) {
+ root.push_back(i);
+ }
+ }
+ // split into groups
+ outputs.resize(root.size());
+ for (size_t i = 0, I = root.size(); i < I; i++) {
+ messagePrintf(1, "Group %d", i);
+ std::vector<size_t> ids;
+ for (size_t j = 0, J = input_bitmap.size(); j < J; j++) {
+ if (dsj.root(j) != root[i]) continue;
+ outputs[i].cameras.push_back(Camera<RGBf_Space>());
+ outputs[i].cameras[outputs[i].cameras.size() - 1].photo(
+ Photo<RGBf_Space>(input_bitmap[j])
+ );
+ ids.push_back(j);
+ messagePrintf(0, "camera %lu from bitmap %lu",
+ outputs[i].cameras.size() - 1, j);
+ }
+ for (size_t j = 0, J = ids.size(); j < J; ++j) {
+ for (size_t k = 0; k < J; ++k) {
+ if (j == k) continue;
+ size_t i1 = ids[j], i2 = ids[k];
+ if (pairs[i1][i2].empty()) continue;
+ outputs[i].edges.push_back(OutputSet::Edge(j, k));
+ size_t index = outputs[i].edges.size() - 1;
+ for (size_t n = 0, N = pairs[i1][i2].size(); n < N; ++n) {
+ outputs[i].edges[index].v1.push_back(
+ fpsv[i1][pairs[i1][i2][n].from.second]
+ );
+ outputs[i].edges[index].v2.push_back(
+ fpsv[i1][pairs[i1][i2][n].to.second]
+ );
+ }
+ messagePrintf(0, "Edge %lu---%lu, size = %lu",
+ i1, i2, outputs[i].edges[index].v1.size());
+ }
+ }
+ std::sort(outputs[i].edges.begin(), outputs[i].edges.end());
+ messagePrintf(-1, "");
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+////////////////////// **# boundle adjustment #** ////////////////////
+bool boundle() {
+ stop = inRange(0.01, 100000.0, atof(usg.optionValue('s', 0).c_str()));
+ messagePrintf(1, "boundle adjustment");
+ for (size_t i = 0, I = outputs.size(); i < I; i++) {
+ int id = 0;
+ std::set<size_t> in;
+ size_t i1 = outputs[i].edges[0].i1;
+ size_t i2 = outputs[i].edges[0].i2;
+ for (size_t j = 0, J = outputs[i].edges[0].v1.size(); j < J; ++j) {
+ outputs[i].cameras[i1].fixedPoints2DGet().identityPointAdd(
+ id, outputs[i].edges[0].v1[j]);
+ outputs[i].cameras[i2].fixedPoints2DGet().identityPointAdd(
+ id, outputs[i].edges[0].v2[j]);
+ id++;
+ }
+ in.insert(i1);
+ in.insert(i2);
+ double r_lst = Camera<RGBf_Space>::boundleAdjustment2D(
+ &(outputs[i].cameras),
+ stop
+ );
+ for (size_t j = 1, J = outputs[i].edges.size(); j < J; ++j) {
+ size_t best;
+ for (best = 0; best < J; ++best) {
+ if (in.find(outputs[i].edges[best].i1) == in.end() &&
+ in.find(outputs[i].edges[best].i2) == in.end()) continue;
+ break;
+ }
+ i1 = outputs[i].edges[best].i1;
+ i2 = outputs[i].edges[best].i2;
+ for (size_t j = 0, J = outputs[i].edges[best].v1.size(); j < J; ++j) {
+ outputs[i].cameras[i1].fixedPoints2DGet().identityPointAdd(
+ id, outputs[i].edges[best].v1[j]);
+ outputs[i].cameras[i2].fixedPoints2DGet().identityPointAdd(
+ id, outputs[i].edges[best].v2[j]);
+ id++;
+ }
+ in.insert(i1);
+ in.insert(i2);
+ std::vector<Camera<RGBf_Space> > tmp(outputs[i].cameras);
+ double r = Camera<RGBf_Space>::boundleAdjustment2D(&tmp, stop);
+ if (r > r_lst * 1.5) continue;
+ outputs[i].cameras = tmp;
+ }
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+bool expand() {
+ o_radius = inRange(100.0, 1000000.0, atof(usg.optionValue('O', 0).c_str()));
+ output_bitmap.resize(outputs.size());
+ for (size_t i = 0, I = outputs.size(); i < I; ++i) {
+ WatchBall<RGBf_Space> wb;
+ wb.cameras(outputs[i].cameras);
+ output_bitmap[i] = wb.expand(o_radius);
+ }
+ return true;
+}
+
+////////////////////// **# Write to output file #** //////////////////
+bool output() {
+ messagePrintf(1, "Write images");
+ for (size_t i = 0; i < output_bitmap.size(); i++) {
+ size_t width = output_bitmap[i].width ();
+ size_t height = output_bitmap[i].height();
+ cv::Mat img(height, width, CV_8UC3);
+ for (size_t x = 0; x < width; x++) {
+ for (size_t y = 0; y < height; y++) {
+ RGBi_Space tmp;
+ colorTransformate(output_bitmap[i].pixel(y, x), &tmp);
+ img.at<cv::Vec3b>(y, x)[0] = tmp.b();
+ img.at<cv::Vec3b>(y, x)[1] = tmp.g();
+ img.at<cv::Vec3b>(y, x)[2] = tmp.r();
+ }
+ }
+ std::string output_name(usg.optionValue('o', 0)
+ + (output_bitmap.size() > 1
+ ? stringPrintf("%lu", i)
+ : "")
+ + ".jpg");
+ messagePrintf(1, "Write to file '%s'", output_name.c_str());
+ if (imwrite(output_name, img) == false) {
+ messagePrintf(-1, "opencv fail, ignore");
+ }
+ else {
+ messagePrintf(-1, "%lux%lu, ok", width, height);
+ }
+ }
+ messagePrintf(-1, "ok");
+ return true;
+}
+
+//*
+bool tmp_output() {
+ output_bitmap = input_bitmap;
+ for (size_t i = 0, I = input_bitmap.size(); i < I; i++) {
+ for (size_t j = 0, J = fpsv[i].size(); j < J; j++) {
+ ssize_t x = fpsv[i][j](0);
+ ssize_t y = fpsv[i][j](1);
+ ssize_t dx[2] = {0, 1}, x0[2] = {0, -10};
+ ssize_t dy[2] = {1, 0}, y0[2] = {-10, 0};
+ for(size_t k = 0; k < 2; k++){
+ for(size_t count = 0; count < 20; count++){
+ ssize_t xx = x + dx[k] * count + x0[k];
+ ssize_t yy = y + dy[k] * count + y0[k];
+ if(0 <= xx && xx < (ssize_t)input_bitmap[i].width() &&
+ 0 <= yy && yy < (ssize_t)input_bitmap[i].height()){
+ output_bitmap[i].pixel(yy, xx, Vector3D<double>(1.0, 1.0, 0.0));
+ }
+ }
+ }
+ }
+ }
+ return output();
+}
+// */
+
+/*
+bool g_output(){
+ output_bitmap.resize(input_bitmap.size() * 2);
+ for(size_t i = 0, I = input_bitmap.size(); i < I; i++){
+ output_bitmap[i * 2 ] = input_bitmap[i];
+ output_bitmap[i * 2 + 1] = input_bitmap[i];
+ output_bitmap[i * 2 ].gradiancedX(3, 3);
+ output_bitmap[i * 2 + 1].gradiancedY(3, 3);
+ for(size_t x = 0, X = output_bitmap[i * 2].width(); x < X; x++){
+ for(size_t y = 0, Y = output_bitmap[i * 2].height(); y < Y; y++){
+ Vector3D<double> v;
+ v = output_bitmap[i * 2](y, x);
+ output_bitmap[i * 2](y, x) = Vector3D<double>(v.length() / sqrt(2.0));
+ v = output_bitmap[i * 2 + 1](y, x);
+ output_bitmap[i * 2 + 1](y, x) = Vector3D<double>(v.length() / sqrt(2.0));
+ }
+ }
+ }
+ return output();
+}
+
+// */
+
+bool pair_output(){
+ for(size_t i = 0, I = input_bitmap.size(); i < I; i++){
+ for(size_t j = 0, J = input_bitmap.size(); j < J; j++){
+ if(pairs[i][j].empty()) continue;
+ MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]));
+ chk.rememberVCalc(pairs[i][j]);
+ size_t index = output_bitmap.size();
+ output_bitmap.push_back(input_bitmap[i]);
+ for(ssize_t x = 0, X = input_bitmap[i].width(); x < X; x++){
+ for(ssize_t y = 0, Y = input_bitmap[i].height(); y < Y; y++){
+ Vector2D<double> to(chk.to(Vector2D<double>(x, y)));
+ ssize_t x2 = to.x(), y2 = to.y();
+ if(0 <= x2 && x2 <= (ssize_t)input_bitmap[j].width() &&
+ 0 <= y2 && y2 <= (ssize_t)input_bitmap[j].height()){
+ output_bitmap[index].pixel(y, x, (input_bitmap[i].pixel(y, x) +
+ input_bitmap[j].pixel(y2,x2)) / 2
+ );
+ }
+ }
+ }
+ }
+ }
+ return output();
+}
+/*
+bool pair_output2(){
+ for(size_t i = 0, I = input_bitmap.size(); i < I; i++){
+ for(size_t j = 0, J = input_bitmap.size(); j < J; j++){
+ if((i + 1) % I != j && (j + 1) % J != i) continue;
+ messagePrintf(0, "%3lu--%3lu: %lu", i, j, pairs[i][j].size());
+ if(pairs[i][j].empty()) continue;
+ MyRansacCheck chk(&(fpsv[i]), &(fpsv[j]));
+ chk.rememberVCalc(pairs[i][j]);
+ size_t index = output_bitmap.size();
+ output_bitmap.push_back(input_bitmap[i]);
+ for(ssize_t x = 0, X = input_bitmap[i].width(); x < X; x++){
+ for(ssize_t y = 0, Y = input_bitmap[i].height(); y < Y; y++){
+ Vector2D<double> to(chk.to(Vector2D<double>(x, y)));
+ ssize_t x2 = to.x(), y2 = to.y();
+ if(0 <= x2 && x2 <= (ssize_t)input_bitmap[j].width() &&
+ 0 <= y2 && y2 <= (ssize_t)input_bitmap[j].height()){
+ output_bitmap[index].pixel(y, x, (input_bitmap[i].pixel(y, x) +
+ input_bitmap[j].pixel(y2,x2)) / 2
+ );
+ }
+ }
+ }
+ for(size_t k = 0, K = fpsv[i].size(); k < K; k++){
+ ssize_t dy[2] = {0, 1}, dx[2] = {1, 0};
+ ssize_t y0[2] = {0, -10}, x0[2] = {-10, 0};
+ ssize_t x = fpsv[i][k](0), y = fpsv[i][k](1);
+ for(ssize_t m = 0; m < 2; m++){
+ for(ssize_t n = 0; n < 20; n++){
+ ssize_t xx = x + x0[m] + dx[m] * n;
+ ssize_t yy = y + y0[m] + dy[m] * n;
+ if(0 <= xx && xx <= (ssize_t)input_bitmap[j].width() &&
+ 0 <= yy && yy <= (ssize_t)input_bitmap[j].height()){
+ output_bitmap[index].pixel(yy, xx,
+ Vector3D<double>(1.0, 1.0, 0));
+ }
+ }
+ }
+ }
+ for(size_t k = 0, K = pairs[i][j].size(); k < K; k++){
+ ssize_t dy[2] = {0, 1}, dx[2] = {1, 0};
+ ssize_t y0[2] = {0, -10}, x0[2] = {-10, 0};
+ ssize_t x = fpsv[i][pairs[i][j][k].from.second](0);
+ ssize_t y = fpsv[i][pairs[i][j][k].from.second](1);
+ for(ssize_t m = 0; m < 2; m++){
+ for(ssize_t n = 0; n < 20; n++){
+ ssize_t xx = x + x0[m] + dx[m] * n;
+ ssize_t yy = y + y0[m] + dy[m] * n;
+ if(0 <= xx && xx <= (ssize_t)input_bitmap[j].width() &&
+ 0 <= yy && yy <= (ssize_t)input_bitmap[j].height()){
+ output_bitmap[index].pixel(yy, xx,
+ Vector3D<double>(1.0, 0.0, 0));
+ }
+ }
+ }
+ }
+ }
+ }
+ return output();
+}
+// */
+
+
+int main(int argc, char** argv){
+ setup(argc, argv);
+ input();
+ detect();
+ kmatch();
+ ransac();
+ prob_mod();
+ group();
+ pair_output(); return 0;
+ boundle();
+ expand();
+ output();
+ return 0;
+}
diff --git a/meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp b/meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp
new file mode 100644
index 0000000..ebcca5b
--- /dev/null
+++ b/meowpp.test/src/autostitch_FeaturePointsDetector_Harris.cpp
@@ -0,0 +1,73 @@
+#include "autostitch.h"
+
+#include "meowpp/oo/ObjBase.h"
+#include "meowpp/oo/ObjSelector.h"
+#include "meowpp/geo/Vectors.h"
+#include "meowpp/gra/FeaturePointsDetector_Harris.h"
+
+using namespace meow;
+
+class Harris: public MyFeaturePointsDetector{
+ private:
+ FeaturePointsDetector_Harris<RGBf_Space> _body;
+ public:
+ Usage usage() const{
+ Usage ret;
+ ret.optionAdd('K',
+ "Specify the constant K of 'R = detM - KtraceM'",
+ "<floating point>", stringPrintf("%.10f", _body.paramK()),
+ false);
+ ret.optionAdd('R',
+ "Specify the threshold of R to determind whether is "
+ "featuer point or not",
+ "<floating point>", stringPrintf("%.10f", _body.paramR()),
+ false);
+ ret.optionAdd('W',
+ "Specify the sigma of the gaussian blur",
+ "<floating point>", stringPrintf("%.10f", _body.paramW()),
+ false);
+ ret.optionAdd('N',
+ "Specify the sigma of the gaussian blur to de-noise",
+ "<floating point>", stringPrintf("%.10f", _body.paramN()),
+ false);
+ ret.optionAdd('G',
+ "Specify the sigma of the gaussian blur to generate feature",
+ "<floating point>", stringPrintf("%.10f", _body.paramG()),
+ false);
+ ret.optionAdd('L',
+ ".........",
+ "<floating point>", stringPrintf("%.10f", _body.paramL()),
+ false);
+ ret.optionAdd('B',
+ "Description size",
+ "<number>", stringPrintf("%lu", _body.paramB()),
+ false);
+ return ret;
+ }
+ bool usage(meow::Usage const& usg){
+ double K = atof(usg.optionValue('K', 0).c_str());
+ double R = atof(usg.optionValue('R', 0).c_str());
+ double W = atof(usg.optionValue('W', 0).c_str());
+ double N = atof(usg.optionValue('N', 0).c_str());
+ double L = atof(usg.optionValue('L', 0).c_str());
+ double G = atof(usg.optionValue('G', 0).c_str());
+ size_t B = atoi(usg.optionValue('B', 0).c_str());
+ _body.paramK(K);
+ _body.paramR(R);
+ _body.paramW(W);
+ _body.paramN(N);
+ _body.paramL(L);
+ _body.paramG(G);
+ _body.paramB(B);
+ return true;
+ }
+ std::vector<meow::FeaturePoint<double, double> >
+ detect(meow::Bitmap<RGBf_Space> const& bmp){
+ return _body.detect(bmp);
+ }
+
+ std::string type() const{ return std::string("Harris"); }
+ ObjBase* create() const{ return new Harris(); }
+};
+
+static meow::ObjSelector<FPSD_ID> __(new Harris(), true);
diff --git a/meowpp.test/src/autostitch_K_Match.cpp b/meowpp.test/src/autostitch_K_Match.cpp
new file mode 100644
index 0000000..d2fe8c6
--- /dev/null
+++ b/meowpp.test/src/autostitch_K_Match.cpp
@@ -0,0 +1,36 @@
+#include "autostitch.h"
+
+#include "meowpp/utility.h"
+
+#include "meowpp/gra/FeaturePointsMatch_K_Match.h"
+
+#include "meowpp/Usage.h"
+
+using namespace meow;
+
+MyK_Match::MyK_Match(){
+}
+
+
+MyK_Match::~MyK_Match(){
+}
+
+
+Usage MyK_Match::usage() const{
+ Usage usg;
+ usg.optionAdd('k',
+ "k nearest neighbors",
+ "<number>", stringPrintf("%d", 5),
+ false);
+ return usg;
+}
+
+bool MyK_Match::usage(meow::Usage const& usg){
+ _body.paramK(atoi(usg.optionValue('k', 0).c_str()));
+ return true;
+}
+
+FeaturePointIndexPairs MyK_Match::match(
+ std::vector<std::vector<FeaturePoint<double, double> > > const& fp) {
+ return _body.match(fp[0][0].description().dimension(), fp);
+}
diff --git a/meowpp.test/src/autostitch_RansacCheck.cpp b/meowpp.test/src/autostitch_RansacCheck.cpp
new file mode 100644
index 0000000..0410396
--- /dev/null
+++ b/meowpp.test/src/autostitch_RansacCheck.cpp
@@ -0,0 +1,121 @@
+#include "autostitch.h"
+
+#include "meowpp/math/Matrix.h"
+#include "meowpp/math/Vector.h"
+#include <utility>
+
+using namespace meow;
+
+double MyRansacCheck::threshold = 5.0;
+
+meow::Usage MyRansacCheck::usage(){
+ Usage usg;
+ usg.optionAdd('t',
+ "Threshold for RANSAC",
+ "<floating point>", stringPrintf("%.10f", threshold),
+ false);
+ return usg;
+}
+
+bool MyRansacCheck::usage(Usage const& usg){
+ threshold = inRange(0.0000001, 1000.0,
+ atof(usg.optionValue('t', 0).c_str()));
+ return true;
+}
+
+MyRansacCheck::MyRansacCheck(){
+}
+
+
+MyRansacCheck::MyRansacCheck(MyRansacCheck const& __rc):
+_from(__rc._from),
+_to(__rc._to){
+}
+
+
+MyRansacCheck::MyRansacCheck(std::vector<Vector<double> > const* __from,
+ std::vector<Vector<double> > const* __to):
+_from(__from),
+_to(__to){
+}
+
+
+MyRansacCheck::~MyRansacCheck(){
+}
+
+
+std::pair<Vector3D<double>, Vector3D<double> > MyRansacCheck::vCalc(
+ std::vector<FeaturePointIndexPair> const& __sample
+) const{
+ Matrix<double> m(6, 7, 0.0);
+ for(size_t i = 0; i < 3u; i++){
+ m(i * 2 , 0, (*_from)[__sample[i].from.second](0));
+ m(i * 2 , 1, (*_from)[__sample[i].from.second](1));
+ m(i * 2 , 2, 1.0);
+ m(i * 2 , 6, (*_to)[__sample[i].to.second](0));
+ m(i * 2 + 1, 3, (*_from)[__sample[i].from.second](0));
+ m(i * 2 + 1, 4, (*_from)[__sample[i].from.second](1));
+ m(i * 2 + 1, 5, 1.0);
+ m(i * 2 + 1, 6, (*_to)[__sample[i].to.second](1));
+ }
+ m.triangulared();
+ Vector<double> x(6, 0.0);
+ for(ssize_t i = 5; i >= 0; i--){
+ double sum = 0;
+ for(size_t j = i + 1; j < 6u; j++){
+ sum += x(j) * m(i, j);
+ }
+ x.entry(i, (m(i, 6) - sum) / m(i, i));
+ }
+ Vector3D<double> vX(x(0), x(1), x(2));
+ Vector3D<double> vY(x(3), x(4), x(5));
+ return std::pair<Vector3D<double>, Vector3D<double> >(vX, vY);
+}
+
+
+void MyRansacCheck::rememberVCalc(std::vector<FeaturePointIndexPair>
+ const& __sample){
+ std::pair<Vector3D<double>, Vector3D<double> > p(vCalc(__sample));
+ _vX = p.first;
+ _vY = p.second;
+}
+
+
+bool MyRansacCheck::ok(FeaturePointIndexPair const& __m) const{
+ Vector2D<double> from(
+ (*_from)[__m.from.second](0),
+ (*_from)[__m.from.second](1));
+ Vector2D<double> me(
+ (*_to)[__m.to.second](0),
+ (*_to)[__m.to.second](1));
+ Vector2D<double> me2(to(from));
+ return ((me - me2).length2() <= threshold);
+}
+
+
+double MyRansacCheck::operator()(std::vector<FeaturePointIndexPair>
+ const& __sample,
+ std::vector<FeaturePointIndexPair>
+ const& __data) const{
+ for(size_t i = 0, I = __sample.size(); i < I; i++){
+ for(size_t j = 0, J = __sample.size(); j < J; j++){
+ if(i == j) continue;
+ if(__sample[i].from.second == __sample[j].from.second) return -1;
+ if(__sample[i].to .second == __sample[j].to .second) return -1;
+ }
+ }
+ ((MyRansacCheck*)this)->rememberVCalc(__sample);
+ size_t ret = 0;
+ for(size_t i = 0, I = __data.size(); i < I; i++){
+ if(ok(__data[i])){
+ ret++;
+ }
+ }
+ return 0.001 + ret;
+}
+
+
+Vector2D<double> MyRansacCheck::to(Vector2D<double> const& __v) const{
+ Vector3D<double> v(__v(0), __v(1), 1);
+ return Vector2D<double>(v.dot(_vX), v.dot(_vY));
+}
diff --git a/meowpp.test/src/dsa.cpp b/meowpp.test/src/dsa.cpp
new file mode 100644
index 0000000..9b93395
--- /dev/null
+++ b/meowpp.test/src/dsa.cpp
@@ -0,0 +1,80 @@
+#include "dsa.h"
+
+#include <vector>
+#include <string>
+#include <cstdlib>
+#include <ctime>
+
+#include "meowpp/Usage.h"
+
+////////////////////////////
+meow::Usage usg("meowpp"), usg2;
+int count = 0;
+////////////////////////
+
+int main(int argc, char** argv){
+ std::vector<std::string> ids(meow::ObjSelector<0>::names());
+ usg2.optionAdd('t', "Select which subject to test",
+ "<number>", "",
+ false);
+ for(size_t i = 0; i < ids.size(); i++){
+ TestFunction* tmp = (TestFunction*)meow::ObjSelector<0>::get(ids[i]);
+ usg2.optionValueAcceptAdd('t', ids[i], tmp->name() + ", " + tmp->description());
+ }
+
+ usg.optionAdd('h', "Display this help document");
+ usg.usageBeginAdd("<name> is a little test program to check whether"
+ "the data structures in the template is correct by"
+ "random generate lots of data to test");
+ usg.usageEndAdd ("zzzzzzzzzzzzzzz....");
+ usg.import(usg2);
+
+ std::string err;
+ if(usg.arguments(argc, argv, &err) == false){
+ printf("%s\n\n%s\n", err.c_str(), usg.usage().c_str());
+ return 1;
+ }else if(usg.hasOptionSetup('h')){
+ printf("%s", usg.usage().c_str());
+ return 0;
+ }else{
+ usg2.update(usg);
+ if(usg2.optionValuesSize('t') > 0){
+ for(int i = 0, I = usg2.optionValuesSize('t'); i < I; i++){
+ std::string wh = usg2.optionValue('t', i);
+ TestFunction* f = (TestFunction*)meow::ObjSelector<0>::get(wh);
+ if(f->run() == false){
+ printf("error occure on %s\n", f->name().c_str());
+ return 1;
+ }else{
+ printf("%s success\n", f->name().c_str());
+ }
+ }
+ }else{
+ while(true){
+ for(int i = 0, I = ids.size(); i < I; i++){
+ TestFunction* tmp = (TestFunction*)meow::ObjSelector<0>::get(ids[i]);
+ printf(" %s) %s\n", ids[i].c_str(), tmp->name().c_str());
+ }
+ printf("please select(EOF to quit): ");
+ int id;
+ if(!~scanf("%d", &id)){
+ break;
+ }
+ printf("\n");
+ TestFunction* f = (TestFunction*)meow::ObjSelector<0>::get(meow::stringPrintf("%d", id));
+ if(f == NULL){
+ printf("Bad value!\n\n");
+ continue;
+ }
+ if(f->run() == false){
+ printf("error occure on %s\n", f->name().c_str());
+ return 1;
+ }else{
+ printf("%s success\n", f->name().c_str());
+ }
+ }
+ printf("\n");
+ }
+ }
+ return 0;
+}
diff --git a/meowpp.test/src/oo.cpp b/meowpp.test/src/oo.cpp
new file mode 100644
index 0000000..54c69d5
--- /dev/null
+++ b/meowpp.test/src/oo.cpp
@@ -0,0 +1,100 @@
+#include <cstdio>
+
+#include "meowpp/Self.h"
+#include <vector>
+#include <string>
+#include <algorithm>
+
+#include <ctime>
+
+using namespace meow;
+
+class A {
+private:
+ struct Myself{
+ int n;
+ Myself() { }
+ ~Myself() { }
+ void copyFrom(Myself const& m){ n = m.n; }
+ };
+ Self<Myself> const self;
+public:
+ A(): self(true){ self()->n = 0; }
+ A(A const& b): self(false) { copyFrom(b); }
+ ~A() { }
+ int num() const { return self->n; }
+ int num(int k) { return (self()->n = k); }
+ void copyFrom(A const& v) { self().copyFrom(v.self); }
+ void referenceFrom(A const& v) { self().referenceFrom(v.self); }
+};
+
+struct B {
+ int n;
+ int count;
+ B() { n = 0; count = 1; }
+};
+
+static A as[100];
+static B *bs[100];
+
+static size_t N = 100;
+
+
+int main(){
+ for (size_t i = 0; i < N; i++) {
+ bs[i] = new B;
+ }
+ for (size_t i = 0; i < 1000; i++) {
+ int k = rand();
+ if (k % 3 == 0) {
+ int x, y;
+ do {
+ x = rand() % N;
+ y = rand() % N;
+ } while(x == y);
+ as[x].copyFrom(as[y]);
+ bs[x]->count--;
+ if (bs[x]->count == 0) {
+ delete bs[x];
+ }
+ bs[x] = new B;
+ bs[x]->n = bs[y]->n;
+ }
+ else if (k % 3 == 1) {
+ int x, y;
+ do {
+ x = rand() % N;
+ y = rand() % N;
+ } while(x == y);
+ as[x].referenceFrom(as[y]);
+ bs[x]->count--;
+ if (bs[x]->count == 0) {
+ delete bs[x];
+ }
+ bs[x] = bs[y];
+ bs[x]->count++;
+ }
+ else {
+ int x = rand() % N, v = rand() % 100;
+ as[x].num(v);
+ bs[x]->n = v;
+ }
+ bool chk = true;
+ for (size_t n = 0; n < N; n++) {
+ if (as[n].num() != bs[n]->n) {
+ chk = false;
+ break;
+ }
+ }
+ if (!chk) {
+ printf("false!\n");
+ return 1;
+ }
+ }
+ for (size_t i = 0; i < N; i++) { printf("%d ", as[i].num()); }
+ printf("\n");
+ for (size_t i = 0; i < N; i++) { printf("%d ", bs[i]->n); }
+ printf("\n");
+ printf("true\n");
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-09-28 10:17:47 +0800