p96705831
/
mdds
forked from openkylin/mdds
1
0
Fork 0
Code Issues Pull Requests Projects Releases Wiki Activity
mdds/test/flat_segment_tree_test.cpp

2178 lines
63 KiB
C++
Raw Permalink Blame History

/*************************************************************************
*
* Copyright (c) 2008-2018 Kohei Yoshida
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*
************************************************************************/
#include "test_global.hpp" // This must be the first header to be included.
#include "mdds/flat_segment_tree.hpp"
#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <iterator>
#include <algorithm>
#include <memory>
#define ARRAY_SIZE(x) sizeof(x) / sizeof(x[0])
using namespace std;
using namespace mdds;
void print_title(const char* msg)
{
cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
cout << " " << msg << endl;
cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
}
void fst_test_leaf_search()
{
{
print_title("Simple insert test");
flat_segment_tree<int, int> int_ranges(0, 100, -1);
for (int i = 0; i < 20; ++i)
{
int start = i * 5;
int end = start + 5;
int_ranges.insert_front(start, end, i);
}
int_ranges.dump_leaf_nodes();
}
{
print_title("Merge test 1");
flat_segment_tree<int, int> merge_test(0, 100, -1);
merge_test.insert_front(10, 20, 5);
merge_test.dump_leaf_nodes();
merge_test.insert_front(15, 30, 5);
merge_test.dump_leaf_nodes();
merge_test.insert_front(30, 50, 5);
merge_test.dump_leaf_nodes();
merge_test.insert_front(8, 11, 5);
merge_test.dump_leaf_nodes();
merge_test.insert_front(5, 8, 5);
merge_test.dump_leaf_nodes();
}
{
print_title("Merge test 2");
flat_segment_tree<int, int> merge_test(0, 100, -1);
// This should not change the node configuration.
merge_test.insert_front(10, 90, -1);
merge_test.dump_leaf_nodes();
for (int i = 10; i <= 80; i += 10)
merge_test.insert_front(i, i + 10, i);
merge_test.dump_leaf_nodes();
merge_test.insert_front(10, 90, -1);
merge_test.dump_leaf_nodes();
for (int i = 10; i <= 80; i += 10)
merge_test.insert_front(i, i + 10, i);
merge_test.dump_leaf_nodes();
merge_test.insert_front(8, 92, -1);
merge_test.dump_leaf_nodes();
for (int i = 10; i <= 80; i += 10)
merge_test.insert_front(i, i + 10, i);
merge_test.dump_leaf_nodes();
merge_test.insert_front(12, 88, 25);
merge_test.dump_leaf_nodes();
}
{
print_title("Search test");
flat_segment_tree<int, int> db(0, 100, -1);
for (int i = 0; i < 10; ++i)
{
int key = i * 10;
int val = i * 5;
db.insert_front(key, key + 10, val);
}
db.dump_leaf_nodes();
for (int i = 0; i <= 100; ++i)
{
int val = 0;
if (db.search(i, val).second)
cout << "key = " << i << "; value = " << val << endl;
else
cout << "key = " << i << "; (value not found)" << endl;
}
for (int i = 0; i <= 100; ++i)
{
int val = 0, start, end;
if (db.search(i, val, &start, &end).second)
cout << "key = " << i << "; value = " << val << "(span: " << start << " - " << end << ")" << endl;
else
cout << "key = " << i << "; (value not found)" << endl;
}
}
}
/**
* Test tree construction of flat_segment_tree.
*/
void fst_test_tree_build()
{
stack_printer __stack_printer__("::fst_test_tree_build");
{
int lower = 0, upper = 100, delta = 10;
flat_segment_tree<int, int> db(lower, upper, 0);
{
stack_printer __stack_printer2__("::fst_test_tree_build insertion");
for (int i = lower; i < upper; i += delta)
db.insert_front(i, i + delta, i * 2);
}
db.dump_leaf_nodes();
{
stack_printer __stack_printer2__("::fst_test_tree_build tree construction");
db.build_tree();
db.dump_tree();
}
}
{
flat_segment_tree<int, int> db(0, 10, 0);
db.dump_leaf_nodes();
}
}
void fst_perf_test_search_leaf()
{
stack_printer __stack_printer__("fst_perf_test_search_leaf");
int lower = 0, upper = 50000;
flat_segment_tree<int, int> db(lower, upper, 0);
for (int i = upper - 1; i >= lower; --i)
db.insert_front(i, i + 1, i);
int success = 0, failure = 0;
int val;
for (int i = lower; i < upper; ++i)
{
if (db.search(i, val).second)
++success;
else
++failure;
}
fprintf(stdout, "fst_perf_test_search_leaf: success (%d) failure (%d)\n", success, failure);
}
void fst_perf_test_search_tree()
{
stack_printer __stack_printer__("fst_perf_test_leaf_search");
int lower = 0, upper = 5000000;
flat_segment_tree<int, int> db(lower, upper, 0);
for (int i = upper - 1; i >= lower; --i)
db.insert_front(i, i + 1, i);
{
stack_printer sp2("::fst_perf_test_search_tree (build tree)");
db.build_tree();
}
int success = 0, failure = 0;
{
stack_printer sp2("::fst_perf_test_search_tree (search tree)");
int val;
for (int i = lower; i < upper; ++i)
{
if (db.search_tree(i, val).second)
++success;
else
++failure;
}
}
fprintf(stdout, "fst_perf_test_search: success (%d) failure (%d)\n", success, failure);
}
void fst_test_tree_search()
{
stack_printer __stack_printer__("::fst_test_tree_search");
typedef flat_segment_tree<int, int> fst_type;
int lower = 0, upper = 200, delta = 5;
fst_type db(lower, upper, 0);
for (int i = lower; i < upper; i += delta)
db.insert_front(i, i + delta, i);
db.build_tree();
db.dump_tree();
db.dump_leaf_nodes();
int val, start, end;
int success = 0, failure = 0;
for (int i = lower - 10; i < upper + 10; ++i)
{
if (db.search_tree(i, val, &start, &end).second)
{
cout << "key = " << i << "; value = " << val << " (" << start << "-" << end << ")" << endl;
++success;
}
else
{
++failure;
cout << "key = " << i << " (search failed)" << endl;
}
}
cout << "search: success (" << success << ") failure (" << failure << ")" << endl;
// Make sure search_tree() returns correct iterator position.
db.clear();
db.insert_back(5, 10, 2);
db.insert_back(15, 18, 3);
db.insert_back(23, 28, 4);
db.build_tree();
typedef pair<fst_type::const_iterator, bool> ret_type;
ret_type ret = db.search_tree(0, val, &start, &end);
assert(ret.second);
assert(start == 0 && end == 5 && val == 0);
assert(ret.first == db.begin());
ret = db.search_tree(6, val, &start, &end);
assert(ret.second);
assert(start == 5 && end == 10 && val == 2);
fst_type::const_iterator check = db.begin();
++check; // 5-10 is the 2nd segment from the top.
assert(ret.first == check);
ret = db.search_tree(17, val, &start, &end);
assert(ret.second);
assert(start == 15 && end == 18 && val == 3);
std::advance(check, 2);
assert(ret.first == check);
ret = db.search_tree(55, val, &start, &end);
assert(ret.second);
assert(start == 28 && end == upper && val == 0);
std::advance(check, 3);
assert(ret.first == check);
ret = db.search_tree(upper + 10, val, &start, &end);
assert(!ret.second); // This search should fail.
assert(ret.first == db.end());
}
void test_single_tree_search(const flat_segment_tree<int, int>& db, int key, int val, int start, int end)
{
int r_val, r_start, r_end;
if (db.search_tree(key, r_val, &r_start, &r_end).second)
assert(r_val == val && r_start == start && r_end == end);
else
assert(!"tree search failed!");
}
template<typename key_type, typename value_type>
void build_and_dump(flat_segment_tree<key_type, value_type>& db)
{
db.build_tree();
db.dump_tree();
db.dump_leaf_nodes();
}
template<typename key_type, typename value_type>
bool check_leaf_nodes(
const flat_segment_tree<key_type, value_type>& db, const key_type* keys, const value_type* values, size_t key_size)
{
if (key_size <= 1)
return false;
vector<key_type> key_checks;
key_checks.reserve(key_size);
for (size_t i = 0; i < key_size; ++i)
key_checks.push_back(keys[i]);
if (!db.verify_keys(key_checks))
return false;
vector<value_type> value_checks;
value_checks.reserve(key_size - 1);
for (size_t i = 0; i < key_size - 1; ++i)
value_checks.push_back(values[i]);
if (!db.verify_values(value_checks))
return false;
return true;
}
template<typename key_type, typename value_type>
bool is_iterator_valid(
const typename flat_segment_tree<key_type, value_type>::const_iterator& beg,
const typename flat_segment_tree<key_type, value_type>::const_iterator& end, const key_type* keys,
const value_type* values, size_t key_size)
{
assert(key_size > 1);
typedef flat_segment_tree<key_type, value_type> container;
typename container::const_iterator itr;
size_t idx = 0;
for (itr = beg; itr != end; ++itr, ++idx)
{
if (idx >= key_size)
// out-of-bound index
return false;
// Check the key first.
if (keys[idx] != itr->first)
return false;
if (idx < key_size - 1)
{
// Check the value only if it's not the last node. The last node
// may have an arbitrary value.
if (values[idx] != itr->second)
return false;
}
}
// At this point, the iterator should be at the end position.
if (itr != end)
return false;
// Check the keys and values again but go to the opposite direction.
do
{
--itr;
--idx;
// key
if (keys[idx] != itr->first)
return false;
// value
if (idx < key_size - 1)
{
if (values[idx] != itr->second)
return false;
}
} while (itr != beg);
return true;
}
template<typename key_type, typename value_type>
bool is_iterator_valid(
const typename flat_segment_tree<key_type, value_type>::const_reverse_iterator& beg,
const typename flat_segment_tree<key_type, value_type>::const_reverse_iterator& end, const key_type* keys,
const value_type* values, size_t key_size)
{
assert(key_size > 1);
typedef flat_segment_tree<key_type, value_type> container;
typename container::const_reverse_iterator itr;
size_t idx = key_size - 1;
for (itr = beg; itr != end; ++itr, --idx)
{
if (idx >= key_size)
// out-of-bound index
return false;
// Check the key first.
if (keys[idx] != itr->first)
return false;
if (idx < key_size - 1)
{
// Check the value only if it's not the last node. The last node
// may have an arbitrary value.
if (values[idx] != itr->second)
return false;
}
}
// At this point, the iterator should be at the end position.
if (itr != end)
return false;
// Check the keys and values again but go to the opposite direction.
do
{
--itr;
++idx;
// key
if (keys[idx] != itr->first)
return false;
// value
if (idx < key_size - 1)
{
if (values[idx] != itr->second)
return false;
}
} while (itr != beg);
return true;
}
void fst_test_insert_search_mix()
{
stack_printer __stack_printer__("fst_test_insert_search_mix");
typedef flat_segment_tree<int, int> db_type;
db_type db(0, 100, 0);
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 0, 0, 0, 100);
test_single_tree_search(db, 99, 0, 0, 100);
db.insert_front(0, 10, 1);
assert(!db.is_tree_valid());
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 0, 1, 0, 10);
test_single_tree_search(db, 5, 1, 0, 10);
test_single_tree_search(db, 9, 1, 0, 10);
test_single_tree_search(db, 10, 0, 10, 100);
db.insert_front(0, 100, 0);
assert(!db.is_tree_valid());
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 0, 0, 0, 100);
test_single_tree_search(db, 99, 0, 0, 100);
db.insert_front(10, 20, 5);
db.insert_front(30, 40, 5);
assert(!db.is_tree_valid());
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 10, 5, 10, 20);
test_single_tree_search(db, 20, 0, 20, 30);
test_single_tree_search(db, 30, 5, 30, 40);
test_single_tree_search(db, 40, 0, 40, 100);
db.insert_front(18, 22, 6);
assert(!db.is_tree_valid());
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 18, 6, 18, 22);
test_single_tree_search(db, 22, 0, 22, 30);
test_single_tree_search(db, 30, 5, 30, 40);
db.insert_front(19, 30, 5);
assert(!db.is_tree_valid());
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 19, 5, 19, 40);
db.insert_front(-100, 500, 999);
assert(!db.is_tree_valid());
build_and_dump(db);
assert(db_type::node::get_instance_count() == db.leaf_size());
assert(db.is_tree_valid());
test_single_tree_search(db, 30, 999, 0, 100);
}
void fst_test_shift_left()
{
stack_printer __stack_printer__("fst_test_shift_segment_left");
typedef flat_segment_tree<int, int> db_type;
db_type db(0, 100, 0);
db.insert_front(20, 40, 5);
db.insert_front(50, 60, 10);
db.insert_front(70, 80, 15);
build_and_dump(db);
// invalid segment ranges -- these should not modify the state of the
// tree, hence the tree should remain valid.
db.shift_left(5, 0);
assert(db.is_tree_valid());
db.shift_left(95, 120);
assert(db.is_tree_valid());
db.shift_left(105, 120);
assert(db.is_tree_valid());
db.shift_left(-10, -5);
assert(db.is_tree_valid());
db.shift_left(-10, 5);
assert(db.is_tree_valid());
// shift without removing nodes (including the lower bound).
db.shift_left(0, 5);
assert(!db.is_tree_valid());
build_and_dump(db);
{
vector<int> key_checks;
key_checks.push_back(0);
key_checks.push_back(15);
key_checks.push_back(35);
key_checks.push_back(45);
key_checks.push_back(55);
key_checks.push_back(65);
key_checks.push_back(75);
key_checks.push_back(100);
assert(db.verify_keys(key_checks));
}
// shift without removing nodes (not including the lower bound).
db.shift_left(1, 6);
assert(!db.is_tree_valid());
build_and_dump(db);
{
vector<int> key_checks;
key_checks.push_back(0);
key_checks.push_back(10);
key_checks.push_back(30);
key_checks.push_back(40);
key_checks.push_back(50);
key_checks.push_back(60);
key_checks.push_back(70);
key_checks.push_back(100);
assert(db.verify_keys(key_checks));
}
// shift without removing nodes (the upper bound of the removed segment
// coincides with a node).
db.shift_left(5, 10);
assert(!db.is_tree_valid());
build_and_dump(db);
{
vector<int> key_checks;
key_checks.push_back(0);
key_checks.push_back(5);
key_checks.push_back(25);
key_checks.push_back(35);
key_checks.push_back(45);
key_checks.push_back(55);
key_checks.push_back(65);
key_checks.push_back(100);
assert(db.verify_keys(key_checks));
}
// shift with one overlapping node.
db.shift_left(1, 11);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 1, 15, 25, 35, 45, 55, 100};
int vals[] = {0, 5, 0, 10, 0, 15, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// shift with two overlapping nodes.
db.shift_left(2, 30);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 1, 2, 7, 17, 27, 100};
int vals[] = {0, 5, 10, 0, 15, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// shift with both ends at existing nodes, but no nodes in between.
db.shift_left(0, 1);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 1, 6, 16, 26, 100};
int vals[] = {5, 10, 0, 15, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// shift with both ends at existing nodes, no nodes in between, and
// removing the segment results in two consecutive segments with identical
// value. The segments should get combined into one.
db.shift_left(16, 26);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 1, 6, 100};
int vals[] = {5, 10, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// insert two new segments for the next test....
db.insert_front(10, 20, 400);
db.insert_front(30, 40, 400);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 1, 6, 10, 20, 30, 40, 100};
int vals[] = {5, 10, 0, 400, 0, 400, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// same test as the previous one, but the value of the combined segment
// differs from the value of the rightmost leaf node.
db.shift_left(20, 30);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 1, 6, 10, 30, 100};
int vals[] = {5, 10, 0, 400, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// remove all.
db.shift_left(0, 100);
assert(!db.is_tree_valid());
build_and_dump(db);
}
void fst_test_shift_left_right_edge()
{
stack_printer __stack_printer__("fst_test_shift_segment_left_right_edge");
flat_segment_tree<int, bool> db(0, 100, false);
build_and_dump(db);
// This should not change the tree state.
db.shift_left(2, 100);
build_and_dump(db);
{
int keys[] = {0, 100};
bool vals[] = {false};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
db.insert_front(20, 100, true);
build_and_dump(db);
{
int keys[] = {0, 20, 100};
bool vals[] = {false, true};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// This should insert a new segment at the end with the initial base value.
db.shift_left(80, 100);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 20, 80, 100};
bool vals[] = {false, true, false};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// This should not modify the tree since the removed segment already has
// the initial base value.
db.shift_left(85, 100);
assert(db.is_tree_valid()); // tree must still be valid.
build_and_dump(db);
{
int keys[] = {0, 20, 80, 100};
bool vals[] = {false, true, false};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Insert a new segment at the end with the value 'true' again...
db.insert_front(85, 100, true);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 20, 80, 85, 100};
bool vals[] = {false, true, false, true};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
db.shift_left(90, 95);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 20, 80, 85, 95, 100};
bool vals[] = {false, true, false, true, false};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
}
void fst_test_shift_left_append_new_segment()
{
stack_printer __stack_printer__("fst_test_shift_segment_left_append_new_segment");
flat_segment_tree<int, bool> db(0, 100, false);
db.insert_front(0, 100, true);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 100};
bool vals[] = {true};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
db.shift_left(10, 20);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 90, 100};
bool vals[] = {true, false};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
db.insert_front(0, 10, true);
db.insert_front(10, 20, false);
db.insert_front(20, 60, true);
db.insert_front(60, 80, false);
db.insert_front(80, 100, true);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 10, 20, 60, 80, 100};
bool vals[] = {true, false, true, false, true};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
db.shift_left(0, 70);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 10, 30, 100};
bool vals[] = {false, true, false};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
}
void fst_test_shift_right_init0()
{
stack_printer __stack_printer__("fst_test_shift_segment_right_init0");
flat_segment_tree<int, int> db(0, 100, 0);
db.insert_front(0, 10, 15);
db.insert_front(10, 20, 1);
db.insert_front(20, 30, 2);
db.insert_front(30, 40, 3);
db.insert_front(40, 50, 4);
db.insert_front(50, 60, 5);
db.insert_front(60, 70, 6);
db.insert_front(70, 80, 7);
db.insert_front(80, 90, 8);
assert(!db.is_tree_valid());
build_and_dump(db);
// shifting position is at the lower bound. The leftmost segment has a
// non-zero value which needs to be preserved after the shift by adding a
// new node.
db.shift_right(0, 5, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 5, 15, 25, 35, 45, 55, 65, 75, 85, 95, 100};
int vals[] = {0, 15, 1, 2, 3, 4, 5, 6, 7, 8, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// shifting position is at the lower bound, and after the shift, the upper
// bound of the last non-zero segment (10) becomes the upper bound of the
// global range.
db.shift_right(0, 5, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int vals[] = {0, 15, 1, 2, 3, 4, 5, 6, 7, 8};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Shift by some odd number.
db.shift_right(0, 49, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 59, 69, 79, 89, 99, 100};
int vals[] = {0, 15, 1, 2, 3, 4};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Shift so that the 2nd node from the right-most node becomes the new
// right-most node.
db.shift_right(0, 11, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 70, 80, 90, 100};
int vals[] = {0, 15, 1, 2};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// This should remove all segments.
db.shift_right(0, 30, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 100};
int vals[] = {0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Insert a few new segments for the next series of tests...
db.insert_front(5, 10, 5);
db.insert_front(20, 30, 5);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 5, 10, 20, 30, 100};
int vals[] = {0, 5, 0, 5, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Inserting at a non-node position. This should simply extend that
// segment and shift all the others.
db.shift_right(6, 20, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 5, 30, 40, 50, 100};
int vals[] = {0, 5, 0, 5, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Inserting at a node position.
db.shift_right(5, 20, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 25, 50, 60, 70, 100};
int vals[] = {0, 5, 0, 5, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Inserting at a non-node position, pushing a node out-of-bound.
db.shift_right(65, 40, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 25, 50, 60, 100};
int vals[] = {0, 5, 0, 5};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
// Inserting at a node position, pushing a node out-of-bound.
db.shift_right(50, 40, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int keys[] = {0, 25, 90, 100};
int vals[] = {0, 5, 0};
assert(check_leaf_nodes(db, keys, vals, ARRAY_SIZE(keys)));
}
}
void fst_test_shift_right_init999()
{
stack_printer __stack_printer__("fst_test_shift_segment_right_init999");
// Initialize the tree with a default value of 999.
flat_segment_tree<int, int> db(0, 100, 999);
db.insert_front(0, 10, 0);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int k[] = {0, 10, 100};
int v[] = {0, 999};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// This should only extend the first segment.
db.shift_right(1, 10, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int k[] = {0, 20, 100};
int v[] = {0, 999};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// Inserting at the leftmost node position should create a new segment
// with a default value of 999.
db.shift_right(0, 10, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
int k[] = {0, 10, 30, 100};
int v[] = {999, 0, 999};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// Invalid shifts -- these should not invalidate the tree.
db.shift_right(-10, 10, false);
assert(db.is_tree_valid());
db.shift_right(100, 10, false);
assert(db.is_tree_valid());
db.shift_right(0, 0, false);
assert(db.is_tree_valid());
}
void fst_test_shift_right_bool()
{
flat_segment_tree<long, bool> db(0, 1048576, false);
db.insert_front(3, 7, true);
assert(!db.is_tree_valid());
build_and_dump(db);
{
long k[] = {0, 3, 7, 1048576};
bool v[] = {false, true, false};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.shift_right(1, 1, false);
assert(!db.is_tree_valid());
build_and_dump(db);
{
long k[] = {0, 4, 8, 1048576};
bool v[] = {false, true, false};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
}
void fst_test_shift_right_skip_start_node()
{
stack_printer __stack_printer__("fst_test_shift_segment_right_skip_start_node");
flat_segment_tree<long, short> db(0, 1048576, 0);
db.insert_front(3, 7, 5);
assert(!db.is_tree_valid());
build_and_dump(db);
{
long k[] = {0, 3, 7, 1048576};
short v[] = {0, 5, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.shift_right(3, 2, true);
assert(!db.is_tree_valid());
build_and_dump(db);
{
long k[] = {0, 3, 9, 1048576};
short v[] = {0, 5, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// shift_right from the leftmost node should not change its value
db.insert_front(0, 4, 2);
assert(!db.is_tree_valid());
build_and_dump(db);
{
long k[] = {0, 4, 9, 1048576};
short v[] = {2, 5, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.shift_right(0, 2, true);
build_and_dump(db);
{
long k[] = {0, 6, 11, 1048576};
short v[] = {2, 5, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
}
/**
* Right all nodes right so that all existing nodes get pushed out of the
* range.
*/
void fst_test_shift_right_all_nodes()
{
typedef flat_segment_tree<unsigned, unsigned> fst_type;
fst_type db(0, 10, 0);
{
unsigned k[] = {0, 10};
unsigned v[] = {0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(0, 8, 2);
db.dump_leaf_nodes();
{
unsigned k[] = {0, 8, 10};
unsigned v[] = {2, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// Shift all nodes out of range. After this, there should be only the
// left and right most nodes left.
db.shift_right(0, 15, false);
db.dump_leaf_nodes();
{
unsigned k[] = {0, 10};
unsigned v[] = {0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
}
template<typename key_type, typename value_type>
struct leaf_node_functor
{
void operator()(const pair<key_type, value_type>&) const
{}
};
void fst_test_const_iterator()
{
stack_printer __stack_printer__("::fst_test_const_iterator");
{
typedef unsigned int key_type;
typedef unsigned short value_type;
unsigned short max_value = numeric_limits<value_type>::max();
typedef flat_segment_tree<key_type, value_type> container_type;
container_type db(0, 1000, max_value);
build_and_dump(db);
{
unsigned int k[] = {0, 1000};
unsigned short v[] = {max_value};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_front(10, 20, 10);
db.insert_front(20, 50, 20);
db.insert_front(100, 300, 55);
build_and_dump(db);
{
unsigned int k[] = {0, 10, 20, 50, 100, 300, 1000};
unsigned short v[] = {max_value, 10, 20, max_value, 55, max_value};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
fprintf(stdout, "fst_test_const_iterator: leaf nodes valid\n");
// Check the forward iterator's integrity.
assert(is_iterator_valid(db.begin(), db.end(), k, v, ARRAY_SIZE(k)));
fprintf(stdout, "fst_test_const_iterator: forward iterator valid\n");
// Check the reverse iterator's integrity.
assert(is_iterator_valid(db.rbegin(), db.rend(), k, v, ARRAY_SIZE(k)));
fprintf(stdout, "fst_test_const_iterator: reverse iterator valid\n");
}
// Make sure it works with for_each.
for_each(db.begin(), db.end(), leaf_node_functor<key_type, value_type>());
}
{
typedef flat_segment_tree<int, bool> container_type;
container_type db(0, 100, true);
db.insert_front(0, 50, false);
{
cout << "-- forward" << endl;
container_type::const_iterator it = db.begin(), it_end = db.end();
// 0 -> 50 -> 100 -> end
cout << "key: " << it->first << " value: " << it->second << endl;
assert(it->first == 0);
assert(it->second == false);
++it;
cout << "key: " << it->first << " value: " << it->second << endl;
assert(it->first == 50);
assert(it->second == true);
++it;
cout << "key: " << it->first << " value: " << it->second << endl;
assert(it->first == 100);
assert(it != it_end);
++it;
assert(it == it_end);
}
{
cout << "-- reverse" << endl;
container_type::const_reverse_iterator it = db.rbegin(), it_end = db.rend();
// 100 -> 50 -> 0 -> end
cout << "key: " << it->first << " value: " << it->second << endl;
assert(it->first == 100);
++it;
cout << "key: " << it->first << " value: " << it->second << endl;
assert(it->first == 50);
assert(it->second == true);
++it;
cout << "key: " << it->first << " value: " << it->second << endl;
assert(it->first == 0);
assert(it->second == false);
assert(it != it_end);
++it;
assert(it == it_end);
}
}
}
template<typename key_type, typename value_type>
void fst_test_insert_front_back(key_type start_key, key_type end_key, value_type default_value)
{
typedef flat_segment_tree<key_type, value_type> container_type;
typedef typename container_type::const_iterator itr_type;
value_type val = 0;
// insert a series of segments from the front.
container_type db_front(start_key, end_key, default_value);
for (key_type i = start_key; i < end_key - 10; ++i)
{
itr_type itr = db_front.insert_front(i, i + 1, val).first;
assert(itr->first == i);
assert(itr->second == val);
if (++val > 10)
val = 0;
}
// insert the same series of segments from the back.
container_type db_back(start_key, end_key, default_value);
val = 0;
for (key_type i = start_key; i < end_key - 10; ++i)
{
itr_type itr = db_back.insert_back(i, i + 1, val).first;
assert(itr->first == i);
assert(itr->second == val);
if (++val > 10)
val = 0;
}
// Now, these two must be identical.
if (db_front != db_back)
{
// They are not identical!
db_front.dump_leaf_nodes();
db_back.dump_leaf_nodes();
cout << "start_key = " << start_key << " end_key = " << end_key << " default_value = " << default_value
<< endl;
assert(!"Contents of the two containers are not identical!");
}
}
void fst_perf_test_insert_front_back()
{
typedef unsigned long key_type;
typedef int value_type;
typedef flat_segment_tree<key_type, value_type> container_type;
key_type upper_bound = 20000;
{
stack_printer __stack_printer__("::fst_perf_test_insert (front insertion)");
container_type db(0, upper_bound, 0);
value_type val = 0;
for (key_type i = 0; i < upper_bound; ++i)
{
db.insert_front(i, i + 1, val);
if (++val > 10)
val = 0;
}
}
{
stack_printer __stack_printer__("::fst_perf_test_insert (back insertion)");
container_type db(0, upper_bound, 0);
value_type val = 0;
for (key_type i = 0; i < upper_bound; ++i)
{
db.insert_back(i, i + 1, val);
if (++val > 10)
val = 0;
}
}
}
void fst_test_copy_ctor()
{
stack_printer __stack_printer__("::fst_test_copy_ctor");
typedef unsigned long key_type;
typedef int value_type;
typedef flat_segment_tree<key_type, value_type> fst;
// Test copy construction of node first.
{
// Original node.
fst::node_ptr node1(new fst::node);
node1->value_leaf.key = 10;
node1->value_leaf.value = 500;
assert(node1->is_leaf);
assert(!node1->parent);
assert(!node1->prev);
assert(!node1->next);
// Copy it to new node.
fst::node_ptr node2(new fst::node(*node1));
assert(node2->is_leaf);
assert(!node2->parent);
assert(!node2->prev);
assert(!node2->next);
assert(node2->value_leaf.key == 10);
assert(node2->value_leaf.value == 500);
// Changing the values of the original should not modify the second node.
node1->value_leaf.key = 35;
node1->value_leaf.value = 200;
assert(node2->value_leaf.key == 10);
assert(node2->value_leaf.value == 500);
}
{
// Test non-leaf node objects.
fst::nonleaf_node node1;
node1.value_nonleaf.low = 123;
node1.value_nonleaf.high = 789;
// Test the copying of non-leaf values.
fst::nonleaf_node node2(node1);
assert(!node2.is_leaf);
assert(!node2.parent);
assert(!node2.left);
assert(!node2.right);
assert(node2.value_nonleaf.low == 123);
assert(node2.value_nonleaf.high == 789);
}
// Now, test the copy construction of the flat_segment_tree.
// Simple copying by copy construction.
fst db(0, 100, 5);
fst db_copied(db);
assert(db == db_copied);
{
key_type k[] = {0, 100};
value_type v[] = {5};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// Inserting the same segment value to both instances. They should still
// be equal.
db.insert_front(5, 10, 0);
db_copied.insert_front(5, 10, 0);
assert(db == db_copied);
{
key_type k[] = {0, 5, 10, 100};
value_type v[] = {5, 0, 5};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
// Inserting a new segment only to the 2nd instance. They should differ.
db_copied.insert_front(15, 20, 35);
assert(db != db_copied);
{
key_type k[] = {0, 5, 10, 15, 20, 100};
value_type v[] = {5, 0, 5, 35, 5};
assert(check_leaf_nodes(db_copied, k, v, ARRAY_SIZE(k)));
}
// Make sure that copying will leave the tree invalid.
assert(!db_copied.is_tree_valid());
db_copied.build_tree();
assert(db_copied.is_tree_valid());
fst db_copied_again(db_copied);
assert(db_copied == db_copied_again);
assert(!db_copied_again.is_tree_valid());
assert(!db_copied_again.get_root_node());
// Make sure we can still perform tree search correctly.
value_type answer = 0;
db_copied_again.build_tree();
db_copied_again.search_tree(18, answer);
assert(db_copied_again.is_tree_valid());
assert(answer == 35);
}
void fst_test_equality()
{
stack_printer __stack_printer__("::fst_test_equality");
typedef unsigned long key_type;
typedef int value_type;
typedef flat_segment_tree<key_type, value_type> container_type;
container_type db1(0, 100, 0);
container_type db2(0, 100, 0);
assert(db1 == db2);
db1.insert_front(0, 1, 1);
assert(db1 != db2);
db2.insert_front(0, 1, 1);
assert(db1 == db2);
// Same node count, but with different value.
db2.insert_front(0, 1, 2);
assert(db1 != db2);
// Set the value back.
db2.insert_front(0, 1, 1);
assert(db1 == db2);
db1.insert_front(4, 10, 10);
db1.insert_front(4, 10, 0);
assert(db1 == db2);
db1.insert_front(20, 40, 5);
db1.insert_front(30, 35, 6);
assert(db1 != db2);
db2.insert_front(20, 30, 5);
db2.insert_front(30, 35, 6);
db2.insert_front(35, 40, 5);
assert(db1 == db2);
}
void fst_test_back_insert()
{
stack_printer __stack_printer__("::fst_test_back_insert");
typedef unsigned int key_type;
typedef unsigned short value_type;
typedef flat_segment_tree<key_type, value_type> container_type;
container_type db(0, 100, 0);
db.insert_back(1, 2, 1);
{
unsigned int k[] = {0, 1, 2, 100};
unsigned short v[] = {0, 1, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(3, 4, 2);
{
unsigned int k[] = {0, 1, 2, 3, 4, 100};
unsigned short v[] = {0, 1, 0, 2, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(4, 5, 2);
{
unsigned int k[] = {0, 1, 2, 3, 5, 100};
unsigned short v[] = {0, 1, 0, 2, 0};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(90, 120, 10);
{
unsigned int k[] = {0, 1, 2, 3, 5, 90, 100};
unsigned short v[] = {0, 1, 0, 2, 0, 10};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(0, 10, 20);
{
unsigned int k[] = {0, 10, 90, 100};
unsigned short v[] = {20, 0, 10};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(5, 20, 20);
{
unsigned int k[] = {0, 20, 90, 100};
unsigned short v[] = {20, 0, 10};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(15, 30, 5);
{
unsigned int k[] = {0, 15, 30, 90, 100};
unsigned short v[] = {20, 5, 0, 10};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.insert_back(0, 1, 2);
{
unsigned int k[] = {0, 1, 15, 30, 90, 100};
unsigned short v[] = {2, 20, 5, 0, 10};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
db.dump_leaf_nodes();
}
template<typename A, typename B>
void print_iterator(typename flat_segment_tree<A, B>::const_iterator& itr)
{
cout << "iterator: (key=" << itr->first << ",value=" << itr->second << ")" << endl;
}
void fst_test_insert_iterator()
{
stack_printer __stack_printer__("::fst_test_insert_iterator");
typedef long key_type;
typedef short value_type;
typedef flat_segment_tree<key_type, value_type> db_type;
db_type db(0, 100, 0);
db_type::const_iterator itr;
itr = db.insert_front(0, 5, 4).first;
assert(itr->first == 0);
assert(itr->second == 4);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(3, 10, 100).first;
assert(itr->first == 3);
assert(itr->second == 100);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(5, 8, 100).first;
assert(itr->first == 3);
assert(itr->second == 100);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(5, 8, 50).first;
assert(itr->first == 5);
assert(itr->second == 50);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(6, 9, 50).first;
assert(itr->first == 5);
assert(itr->second == 50);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(9, 20, 24).first;
assert(itr->first == 9);
assert(itr->second == 24);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(19, 24, 34).first;
assert(itr->first == 19);
assert(itr->second == 34);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(24, 26, 0).first;
assert(itr->first == 24);
assert(itr->second == 0);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(30, 50, 2).first;
assert(itr->first == 30);
assert(itr->second == 2);
print_iterator<key_type, value_type>(itr);
itr = db.insert_front(120, 140, 34).first;
assert(itr == db.end());
itr = db.insert_front(-20, -10, 20).first;
assert(itr == db.end());
}
void fst_test_insert_state_changed()
{
stack_printer __stack_printer__("::fst_test_insert_state_changed");
typedef long key_type;
typedef short value_type;
typedef flat_segment_tree<key_type, value_type> db_type;
typedef pair<db_type::const_iterator, bool> ret_type;
db_type db(0, 1000, 0);
// Inserting a segment with the default value. This should not change the
// state.
ret_type r = db.insert_front(10, 15, 0);
assert(!r.second);
// New segment with a different value.
r = db.insert_front(0, 10, 1);
assert(r.second);
// Inserting the same segment should not change the state.
r = db.insert_front(0, 10, 1);
assert(!r.second);
r = db.insert_front(0, 1, 1);
assert(!r.second);
r = db.insert_front(8, 10, 1);
assert(!r.second);
// This extends the segment, therefore the state should change.
r = db.insert_front(8, 11, 1);
assert(r.second);
r = db.insert_front(11, 15, 0);
assert(!r.second);
// This extends the segment. At this point, 0 - 15 should have a value of 1.
r = db.insert_front(11, 15, 1);
assert(r.second);
{
db_type::const_iterator itr = r.first;
assert(itr->first == 0);
assert(itr->second == 1);
++itr;
assert(itr->first == 15);
}
r = db.insert_front(2, 4, 1);
assert(!r.second);
// Different value segment. This should change the state.
r = db.insert_front(2, 4, 0);
assert(r.second);
// Ditto.
r = db.insert_front(2, 4, 1);
assert(r.second);
r = db.insert_front(1, 8, 1);
assert(!r.second);
// Different value segment.
r = db.insert_front(1, 8, 2);
assert(r.second);
r = db.insert_front(8, 20, 2);
assert(r.second);
// The 0-1 segment should still have a value of 1. So this won't change
// the state.
r = db.insert_front(0, 1, 1);
assert(!r.second);
// Partially out-of-bound segment, but this should modify the value of 0-2.
r = db.insert_front(-50, 2, 10);
assert(r.second);
{
db_type::const_iterator itr = r.first;
assert(itr->first == 0);
assert(itr->second == 10);
++itr;
assert(itr->first == 2);
}
// Entirely out-of-bound.
r = db.insert_front(-50, -2, 20);
assert(!r.second);
// Likewise, partially out-of-bound at the higher end.
r = db.insert_front(800, 1200, 20);
assert(r.second);
// Entirely out-of-bound.
r = db.insert_front(1300, 1400, 25);
assert(!r.second);
}
void fst_perf_test_insert_position()
{
typedef flat_segment_tree<long, bool> db_type;
typedef pair<db_type::const_iterator, bool> ret_type;
long upper = 60000;
{
stack_printer __stack_printer__("::fst_perf_test_insert_position (front)");
// Much smaller upper boundary because front insertion is very slow.
db_type db(0, upper, false);
bool val = false;
for (long i = 0; i < upper; ++i)
{
db.insert_front(i, i + 1, val);
val = !val;
}
}
{
stack_printer __stack_printer__("::fst_perf_test_insert_position (back)");
db_type db(0, upper, false);
bool val = false;
for (long i = 0; i < upper; ++i)
{
db.insert_back(i, i + 1, val);
val = !val;
}
}
{
db_type db(0, upper, false);
{
stack_printer __stack_printer__("::fst_perf_test_insert_position (position)");
db_type::const_iterator itr = db.begin();
bool val = false;
for (long i = 0; i < upper; ++i)
{
ret_type ret = db.insert(itr, i, i + 1, val);
val = !val;
itr = ret.first;
}
}
{
stack_printer __stack_printer__("::fst_perf_test_insert_position (position re-insert)");
db_type::const_iterator itr = db.begin();
bool val = true;
for (long i = 0; i < upper; ++i)
{
ret_type ret = db.insert(itr, i, i + 1, val);
val = !val;
itr = ret.first;
}
}
}
}
void fst_perf_test_position_search()
{
typedef flat_segment_tree<long, bool> db_type;
typedef pair<db_type::const_iterator, bool> ret_type;
long upper = 60000;
db_type db(0, upper, false);
// Fill the leaf nodes first.
db_type::const_iterator itr = db.begin();
bool val = false;
for (long i = 0; i < upper; ++i)
{
ret_type ret = db.insert(itr, i, i + 1, val);
val = !val;
itr = ret.first;
}
{
stack_printer __stack_printer__("::fst_perf_test_position_search (normal)");
for (long i = 0; i < upper; ++i)
{
bool val2;
ret_type ret = db.search(i, val2);
assert(ret.second);
}
}
{
stack_printer __stack_printer__("::fst_perf_test_position_search (positioned)");
itr = db.begin();
for (long i = 0; i < upper; ++i)
{
bool val2;
ret_type ret = db.search(itr, i, val2);
assert(ret.second);
itr = ret.first;
}
}
}
template<typename K, typename V>
bool check_pos_search_result(
const flat_segment_tree<K, V>& db, typename flat_segment_tree<K, V>::const_iterator& itr, K key, K start_expected,
K end_expected, V value_expected)
{
typedef flat_segment_tree<K, V> db_type;
typedef pair<typename db_type::const_iterator, bool> ret_type;
V _val;
K _start = -1, _end = -1;
ret_type r = db.search(itr, key, _val, &_start, &_end);
cout << "expected: start=" << start_expected << " end=" << end_expected << " value=" << value_expected << endl;
cout << "observed: start=" << _start << " end=" << _end << " value=" << _val << endl;
bool result = _start == start_expected && _end == end_expected && _val == value_expected &&
r.first->first == start_expected && r.first->second == value_expected;
itr = r.first;
return result;
}
void fst_test_position_search()
{
stack_printer __stack_printer__("::fst_test_position_search");
typedef flat_segment_tree<long, short> db_type;
typedef pair<db_type::const_iterator, bool> ret_type;
db_type db(0, 100, 0);
db.insert_front(10, 20, 1);
db.insert_front(30, 50, 5);
db_type db2(-10, 10, 1);
struct
{
long start_range;
long end_range;
short value_expected;
} params[] = {{0, 10, 0}, {10, 20, 1}, {20, 30, 0}, {30, 50, 5}, {50, 100, 0}};
size_t n = sizeof(params) / sizeof(params[0]);
cout << "Testing for searches with various valid and invalid iterators." << endl;
for (size_t i = 0; i < n; ++i)
{
for (long j = params[i].start_range; j < params[i].end_range; ++j)
{
db_type::const_iterator itr;
bool success = false;
// empty iterator - should fall back to normal search.
success = check_pos_search_result(
db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
assert(success);
// iterator returned from the previous search.
success = check_pos_search_result(
db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
assert(success);
// begin iterator.
itr = db.begin();
success = check_pos_search_result(
db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
assert(success);
// end iterator.
itr = db.end();
success = check_pos_search_result(
db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
assert(success);
// iterator from another container - should fall back to normal search.
itr = db2.begin();
success = check_pos_search_result(
db, itr, j, params[i].start_range, params[i].end_range, params[i].value_expected);
assert(success);
}
}
cout << "Testing for continuous searching by re-using the iteraotr from the previous search." << endl;
db_type::const_iterator itr;
short val;
long start = 0, end = 0;
for (size_t i = 0; i < n; ++i)
{
ret_type r = db.search(itr, end, val, &start, &end);
assert(start == params[i].start_range);
assert(end == params[i].end_range);
assert(val == params[i].value_expected);
assert(r.second);
itr = r.first;
}
}
void fst_test_min_max_default()
{
typedef flat_segment_tree<long, short> db_type;
db_type db(0, 100, 2);
assert(db.min_key() == 0);
assert(db.max_key() == 100);
assert(db.default_value() == 2);
}
void fst_test_swap()
{
typedef flat_segment_tree<long, int> db_type;
db_type db1(0, 200, 20);
db_type db2(20, 40, 0);
db1.insert_back(20, 30, 1);
db1.insert_back(30, 40, 2);
db1.insert_back(40, 50, 3);
db1.build_tree();
// Check the content of db1.
{
db_type::key_type k[] = {0, 20, 30, 40, 50, 200};
db_type::value_type v[] = {20, 1, 2, 3, 20};
assert(check_leaf_nodes(db1, k, v, ARRAY_SIZE(k)));
}
assert(db1.min_key() == 0);
assert(db1.max_key() == 200);
assert(db1.default_value() == 20);
assert(db1.is_tree_valid());
db1.swap(db2);
// Now db2 should inherit the content of db1.
{
db_type::key_type k[] = {0, 20, 30, 40, 50, 200};
db_type::value_type v[] = {20, 1, 2, 3, 20};
assert(check_leaf_nodes(db2, k, v, ARRAY_SIZE(k)));
}
assert(db2.min_key() == 0);
assert(db2.max_key() == 200);
assert(db2.default_value() == 20);
assert(db2.is_tree_valid());
// Tree search should work on db2.
db_type::value_type val = 0;
assert(db2.search_tree(35, val).second);
assert(val == 2);
}
void fst_test_swap_tree_memory()
{
stack_printer __stack_printer__("::fst_test_swap_tree_memory");
typedef flat_segment_tree<long, int> db_type;
auto db1 = std::make_unique<db_type>(0, 100, 0);
db1->insert_back(10, 40, 999);
db1->build_tree();
int value = -1;
db1->search_tree(20, value);
assert(value == 999);
db_type db2(-10, 10, -99);
db2.swap(*db1);
db1.reset();
// Make sure that the tree is valid, and you can still search through the tree.
assert(db2.is_tree_valid());
value = -1;
db2.search_tree(20, value);
assert(value == 999);
}
void fst_test_clear()
{
stack_printer __stack_printer__("::fst_test_clear");
typedef flat_segment_tree<long, int> db_type;
db_type db(0, 100, 42);
db.insert_back(0, 10, 0);
db.insert_back(10, 20, 1);
db.insert_back(20, 30, 2);
db.build_tree();
{
db_type::key_type k[] = {0, 10, 20, 30, 100};
db_type::value_type v[] = {0, 1, 2, 42};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
assert(db.min_key() == 0);
assert(db.max_key() == 100);
assert(db.default_value() == 42);
assert(db.is_tree_valid());
db.clear();
{
db_type::key_type k[] = {0, 100};
db_type::value_type v[] = {42};
assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k)));
}
assert(db.min_key() == 0);
assert(db.max_key() == 100);
assert(db.default_value() == 42);
assert(!db.is_tree_valid());
}
void fst_test_assignment()
{
stack_printer __stack_printer__("::fst_test_assignment");
typedef flat_segment_tree<long, int> db_type;
db_type db1(0, 100, 42);
db1.insert_back(0, 10, 0);
db1.insert_back(10, 20, 1);
db1.insert_back(20, 30, 2);
db1.build_tree();
{
db_type::key_type k[] = {0, 10, 20, 30, 100};
db_type::value_type v[] = {0, 1, 2, 42};
assert(check_leaf_nodes(db1, k, v, ARRAY_SIZE(k)));
}
assert(db1.min_key() == 0);
assert(db1.max_key() == 100);
assert(db1.default_value() == 42);
assert(db1.is_tree_valid());
db_type db2(20, 40, 0);
db2.insert_back(20, 30, 8);
db2.build_tree();
{
db_type::key_type k[] = {20, 30, 40};
db_type::value_type v[] = {8, 0};
assert(check_leaf_nodes(db2, k, v, ARRAY_SIZE(k)));
}
assert(db2.min_key() == 20);
assert(db2.max_key() == 40);
assert(db2.default_value() == 0);
assert(db2.is_tree_valid());
db_type db3(10, 80, 4);
db3.build_tree();
{
db_type::key_type k[] = {10, 80};
db_type::value_type v[] = {4};
assert(check_leaf_nodes(db3, k, v, ARRAY_SIZE(k)));
}
assert(db3.min_key() == 10);
assert(db3.max_key() == 80);
assert(db3.default_value() == 4);
assert(db3.is_tree_valid());
db3 = db2 = db1;
{
db_type::key_type k[] = {0, 10, 20, 30, 100};
db_type::value_type v[] = {0, 1, 2, 42};
assert(check_leaf_nodes(db1, k, v, ARRAY_SIZE(k)));
}
assert(db1.min_key() == 0);
assert(db1.max_key() == 100);
assert(db1.default_value() == 42);
assert(db1.is_tree_valid());
{
db_type::key_type k[] = {0, 10, 20, 30, 100};
db_type::value_type v[] = {0, 1, 2, 42};
assert(check_leaf_nodes(db2, k, v, ARRAY_SIZE(k)));
}
assert(db2.min_key() == 0);
assert(db2.max_key() == 100);
assert(db2.default_value() == 42);
assert(!db2.is_tree_valid());
{
db_type::key_type k[] = {0, 10, 20, 30, 100};
db_type::value_type v[] = {0, 1, 2, 42};
assert(check_leaf_nodes(db3, k, v, ARRAY_SIZE(k)));
}
assert(db3.min_key() == 0);
assert(db3.max_key() == 100);
assert(db3.default_value() == 42);
assert(!db3.is_tree_valid());
}
void fst_test_non_numeric_value()
{
stack_printer __stack_printer__("::fst_test_non_numeric_value");
typedef flat_segment_tree<int, std::string> db_type;
db_type db(0, 4, "42");
db.insert_back(1, 2, "hello world");
assert(db.default_value() == "42");
std::string result;
db.search(1, result);
assert(result == "hello world");
db_type db2(db);
assert(db == db2);
}
void fst_test_insert_out_of_bound()
{
stack_printer __stack_printer__("::fst_test_insert_out_of_bound");
typedef flat_segment_tree<int, bool> db_type;
db_type db(0, 10, false);
// An out-of-bound range, whether it's in part or in its entirety, should
// be handled gracefully without throwing exceptions or causing segfaults.
// ranges that are entirely out-of-bound.
auto ret = db.insert_front(-10, -8, false);
assert(!ret.second);
db.insert_back(12, 13, false);
assert(!ret.second);
db_type::const_iterator pos = db.end();
ret = db.insert(pos, -10, -8, false);
assert(!ret.second);
pos = ret.first;
ret = db.insert(pos, 12, 13, false);
assert(!ret.second);
pos = ret.first;
// partial overflows.
ret = db.insert(pos, -2, 2, true);
assert(ret.second); // content modified
pos = ret.first;
ret = db.insert(pos, 8, 20, true);
assert(ret.second); // content modified
pos = ret.first;
}
void fst_test_insert_out_of_bound_2()
{
stack_printer __stack_printer__("::fst_test_insert_out_of_bound_2");
typedef flat_segment_tree<int, bool> db_type;
db_type db(0, 256, false);
// The range is entirely out-of-bound, but the start range equals the
// upper bound of the valid range.
auto ret = db.insert_back(256, 1024, true);
// Insertion never took place.
assert(ret.first == db.end());
assert(!ret.second);
}
void fst_test_segment_iterator()
{
stack_printer __stack_printer__("::fst_test_segment_iterator");
typedef flat_segment_tree<int16_t, bool> db_type;
db_type db(0, 100, false);
db_type::const_segment_iterator it = db.begin_segment();
db_type::const_segment_iterator ite = db.end_segment();
assert(it != ite);
assert(it->start == 0);
assert(it->end == 100);
assert(it->value == false);
const auto& v = *it;
assert(v.start == 0);
assert(v.end == 100);
assert(v.value == false);
++it;
assert(it == ite);
--it;
assert(it != ite);
assert(it->start == 0);
assert(it->end == 100);
assert(it->value == false);
db_type::const_segment_iterator it2; // default constructor
it2 = it; // assignment operator
assert(it2 == it);
assert(it2->start == 0);
assert(it2->end == 100);
assert(it2->value == false);
auto it3(it2); // copy constructor
assert(it3 == it2);
assert(it3->start == 0);
assert(it3->end == 100);
assert(it3->value == false);
db.insert_back(20, 50, true); // this invalidates the iterators.
it = db.begin_segment();
ite = db.end_segment();
assert(it->start == 0);
assert(it->end == 20);
assert(it->value == false);
it2 = it++; // post-increment
assert(it2->start == 0);
assert(it2->end == 20);
assert(it2->value == false);
assert(it->start == 20);
assert(it->end == 50);
assert(it->value == true);
++it;
assert(it->start == 50);
assert(it->end == 100);
assert(it->value == false);
++it;
assert(it == ite);
it2 = it--; // post-decrement.
assert(it2 == ite);
it = db.begin_segment();
auto it_moved{std::move(it)}; // move construction
assert(it_moved->start == 0);
assert(it_moved->end == 20);
assert(it_moved->value == false);
}
int main(int argc, char** argv)
{
try
{
cmd_options opt;
if (!parse_cmd_options(argc, argv, opt))
return EXIT_FAILURE;
if (opt.test_func)
{
fst_test_equality();
fst_test_copy_ctor();
fst_test_back_insert();
{
typedef unsigned int key_type;
typedef unsigned short value_type;
for (value_type i = 0; i <= 100; ++i)
fst_test_insert_front_back<key_type, value_type>(0, 100, i);
}
{
typedef int key_type;
typedef short value_type;
for (value_type i = 0; i <= 100; ++i)
fst_test_insert_front_back<key_type, value_type>(0, 100, i);
}
{
typedef long key_type;
typedef unsigned int value_type;
for (value_type i = 0; i <= 100; ++i)
fst_test_insert_front_back<key_type, value_type>(0, 100, i);
}
fst_test_leaf_search();
fst_test_tree_build();
fst_test_tree_search();
fst_test_insert_search_mix();
fst_test_shift_left();
fst_test_shift_left_right_edge();
fst_test_shift_left_append_new_segment();
fst_test_shift_right_init0();
fst_test_shift_right_init999();
fst_test_shift_right_bool();
fst_test_shift_right_skip_start_node();
fst_test_shift_right_all_nodes();
fst_test_const_iterator();
fst_test_insert_iterator();
fst_test_insert_state_changed();
fst_test_position_search();
fst_test_min_max_default();
fst_test_swap();
fst_test_swap_tree_memory();
fst_test_clear();
fst_test_assignment();
fst_test_non_numeric_value();
fst_test_insert_out_of_bound();
fst_test_insert_out_of_bound_2();
fst_test_segment_iterator();
}
if (opt.test_perf)
{
fst_perf_test_search_leaf();
fst_perf_test_search_tree();
fst_perf_test_insert_front_back();
fst_perf_test_insert_position();
fst_perf_test_position_search();
}
}
catch (const std::exception& e)
{
fprintf(stdout, "Test failed: %s\n", e.what());
return EXIT_FAILURE;
}
fprintf(stdout, "Test finished successfully!\n");
return 0;
}
Reference in New Issue View Git Blame Copy Permalink