diff options
Diffstat (limited to 'meowpp.test/src/BinaryIndexTree.cpp')
-rw-r--r-- | meowpp.test/src/BinaryIndexTree.cpp | 57 |
1 files changed, 0 insertions, 57 deletions
diff --git a/meowpp.test/src/BinaryIndexTree.cpp b/meowpp.test/src/BinaryIndexTree.cpp deleted file mode 100644 index e9a4544..0000000 --- a/meowpp.test/src/BinaryIndexTree.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#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; -} |