diff options
author | cathook <b01902109@csie.ntu.edu.tw> | 2014-06-01 14:14:52 +0800 |
---|---|---|
committer | cathook <b01902109@csie.ntu.edu.tw> | 2014-06-01 14:14:52 +0800 |
commit | 2d26b8e8d4383f34aa0a37b9d1754be76ba19602 (patch) | |
tree | 90da71e0aae685143f39128e15444d6ccdad042c /meowpp.test/src/SegmentTree.cpp | |
parent | bd7552bc352de4ff83c1d0365df8750c2bc4bf0a (diff) | |
download | meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.tar meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.tar.gz meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.tar.bz2 meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.tar.lz meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.tar.xz meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.tar.zst meow-2d26b8e8d4383f34aa0a37b9d1754be76ba19602.zip |
test...
Diffstat (limited to 'meowpp.test/src/SegmentTree.cpp')
-rw-r--r-- | meowpp.test/src/SegmentTree.cpp | 157 |
1 files changed, 0 insertions, 157 deletions
diff --git a/meowpp.test/src/SegmentTree.cpp b/meowpp.test/src/SegmentTree.cpp deleted file mode 100644 index c795477..0000000 --- a/meowpp.test/src/SegmentTree.cpp +++ /dev/null @@ -1,157 +0,0 @@ -#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; -} |