summaryrefslogtreecommitdiffstats
path: root/test/point_quad_tree/test_main.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'test/point_quad_tree/test_main.cpp')
-rw-r--r--test/point_quad_tree/test_main.cpp477
1 files changed, 477 insertions, 0 deletions
diff --git a/test/point_quad_tree/test_main.cpp b/test/point_quad_tree/test_main.cpp
new file mode 100644
index 0000000..605e410
--- /dev/null
+++ b/test/point_quad_tree/test_main.cpp
@@ -0,0 +1,477 @@
+/*************************************************************************
+ *
+ * Copyright (c) 2010 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/point_quad_tree.hpp"
+
+#include <algorithm>
+#include <memory>
+#include <vector>
+#include <sstream>
+#include <boost/cstdint.hpp>
+
+using namespace std;
+using namespace mdds;
+using ::boost::uint16_t;
+
+struct data_printer
+{
+ void operator()(const string* p)
+ {
+ cout << *p << " ";
+ }
+};
+
+template<typename _DbType>
+struct search_result_printer
+{
+ void operator()(const pair<const typename _DbType::point, const typename _DbType::value_type>& r) const
+ {
+ cout << " (x=" << r.first.x << ", y=" << r.first.y << ", value='" << *r.second << "')" << endl;
+ }
+};
+
+void pqt_test_basic()
+{
+ stack_printer __stack_printer__("::pqt_test");
+ typedef point_quad_tree<uint16_t, const string*> db_type;
+ db_type db;
+
+ string A("A");
+ string B("B");
+ string C("C");
+ string D("D");
+ string E("E");
+ string F("F");
+ string G("G");
+ string H("H");
+ string I("I");
+ string J("J");
+ string K("K");
+ string L("L");
+ string M("M");
+ string N("N");
+
+ db.insert(25, 32, &A);
+ db.insert(5, 45, &B);
+ db.insert(52, 10, &C);
+ db.insert(80, 5, &D);
+ db.insert(40, 50, &E);
+ db.insert(10, 10, &F);
+ db.insert(20, 20, &G);
+ db.insert(80, 80, &H);
+ db.insert(58, 46, &I);
+ db.insert(36, 55, &J);
+ db.insert(26, 52, &K);
+ db.insert(38, 68, &L);
+ db.insert(39, 78, &M);
+ db.insert(72, 52, &N);
+
+ assert(db.size() == 14);
+
+ cout << "node count = " << get_node_instance_count() << endl;
+ db.dump_tree_svg("./obj/test.svg");
+
+ {
+ db_type::data_array_type result;
+ db.search_region(10, 10, 60, 20, result);
+ cout << "search region: (10, 10, 60, 20)" << endl;
+ cout << "result: ";
+ for_each(result.begin(), result.end(), data_printer());
+ cout << endl;
+
+ result.clear();
+ db.search_region(10, 10, 61, 61, result);
+ cout << "search region: (10, 10, 61, 61)" << endl;
+ cout << "result: ";
+ for_each(result.begin(), result.end(), data_printer());
+ cout << endl;
+ }
+
+ db_type::search_results result = db.search_region(10, 10, 60, 20);
+ db_type::search_results::const_iterator itr = result.begin(), itr_end = result.end();
+ cout << "result: " << endl;
+ for_each(result.begin(), result.end(), search_result_printer<db_type>());
+
+ result = db.search_region(10, 10, 61, 61);
+ itr = result.begin(), itr_end = result.end();
+ cout << "result: " << endl;
+ for_each(result.begin(), result.end(), search_result_printer<db_type>());
+
+ db.remove(20, 20);
+ db.remove(40, 50);
+ assert(db.size() == 12);
+ db.dump_tree_svg("./obj/test-remove.svg");
+
+ db.clear();
+ assert(db.empty());
+ assert(db.size() == 0);
+}
+
+void pqt_test_insertion_removal()
+{
+ stack_printer __stack_printer__("::pqt_test_insertion_removal");
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ db_type db;
+
+ // Check its empty-ness...
+ assert(db.empty());
+ assert(db.size() == 0);
+
+ // Create all data instances.
+ vector<unique_ptr<string>> data_store;
+ data_store.reserve(100);
+ for (size_t i = 0; i < 100; ++i)
+ {
+ ostringstream os;
+ os << "0x" << hex << i;
+ data_store.emplace_back(new string(os.str()));
+ }
+
+ vector<db_type::node_data> expected;
+
+ // Insert data one by one, and verify each insertion.
+ for (int32_t i = 0; i < 10; ++i)
+ {
+ for (int32_t j = 0; j < 10; ++j)
+ {
+ int32_t x = i * 10 + 1, y = j * 10 + 1;
+ size_t index = i * 10 + j;
+ const string* data_ptr = data_store[index].get();
+ cout << "inserting '" << *data_ptr << "' at (" << x << "," << y << ")" << endl;
+ db.insert(x, y, data_ptr);
+ expected.push_back(db_type::node_data(x, y, data_ptr));
+
+ vector<db_type::node_data> stored_data;
+ db.get_all_stored_data(stored_data);
+ assert(stored_data.size() == (index + 1));
+ assert(db.size() == (index + 1));
+ assert(!db.empty());
+ bool success = db.verify_data(expected);
+ assert(success);
+ }
+ }
+ db.dump_tree_svg("./obj/pqt_test_insertion.svg");
+
+ // Remove data one by one, and check the size after each removal.
+ size_t node_count = 100;
+ for (int32_t i = 0; i < 10; ++i)
+ {
+ for (int32_t j = 0; j < 10; ++j)
+ {
+ int32_t x = i * 10 + 1, y = j * 10 + 1;
+ db.remove(x, y);
+ size_t n = db.size();
+ cout << "removing node at (" << x << "," << y << ") "
+ << "size after removal: " << n << endl;
+ --node_count;
+ assert(node_count == n);
+ }
+ }
+}
+
+void pqt_test_remove_root()
+{
+ stack_printer __stack_printer__("::pqt_test_remove_root");
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ string O("O");
+ string NW("NW");
+ string NE("NE");
+ string SW("SW");
+ string SE("SE");
+ db_type db;
+
+ // Insert all data and verify their storage.
+ db.insert(10, 10, &O);
+ db.insert(20, 0, &NE);
+ db.insert(0, 0, &NW);
+ db.insert(20, 20, &SE);
+ db.insert(0, 20, &SW);
+ db.dump_tree_svg("./obj/pqt_test_remove_root-1.svg");
+
+ vector<db_type::node_data> expected;
+ expected.push_back(db_type::node_data(10, 10, &O));
+ expected.push_back(db_type::node_data(20, 0, &NE));
+ expected.push_back(db_type::node_data(0, 0, &NW));
+ expected.push_back(db_type::node_data(20, 20, &SE));
+ expected.push_back(db_type::node_data(0, 20, &SW));
+ bool success = db.verify_data(expected);
+ assert(success);
+ assert(db.size() == 5);
+
+ // Now, remove the root node.
+ db.remove(10, 10);
+ db.dump_tree_svg("./obj/pqt_test_remove_root-2.svg");
+ expected.clear();
+ expected.push_back(db_type::node_data(20, 0, &NE));
+ expected.push_back(db_type::node_data(0, 0, &NW));
+ expected.push_back(db_type::node_data(20, 20, &SE));
+ expected.push_back(db_type::node_data(0, 20, &SW));
+ success = db.verify_data(expected);
+ assert(success);
+ assert(db.size() == 4);
+}
+
+void pqt_test_equality()
+{
+ stack_printer __stack_printer__("::pqt_test_equality");
+
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ db_type db1, db2;
+
+ string A("A");
+ string B("B");
+ string C("C");
+ string D("D");
+ string E("E");
+ string F("F");
+
+ assert(db1 == db2); // both are empty.
+
+ db1.insert(0, 0, &A);
+ db2.insert(0, 0, &A);
+ assert(db1 == db2);
+ db1.remove(0, 0);
+ assert(db1 != db2);
+ db1.insert(0, 0, &B);
+ assert(db1 != db2);
+ db2.insert(0, 0, &B); // B overwrites A.
+ assert(db1 == db2); // Both should have B at (0,0).
+ db1.insert(1, 1, &C);
+ db2.insert(2, 2, &C);
+ assert(db1 != db2);
+ db1.insert(2, 2, &C);
+ db2.insert(1, 1, &C);
+ assert(db1 == db2);
+
+ // Inserting data in different orders should make no difference in equality.
+ db1.insert(1, 3, &D);
+ db1.insert(1, 4, &E);
+ db1.insert(1, 5, &F);
+
+ db2.insert(1, 5, &F);
+ db2.insert(1, 4, &E);
+ db2.insert(1, 3, &D);
+ assert(db1 == db2);
+ db1.remove(1, 4);
+ db2.remove(1, 4);
+ assert(db1 == db2);
+
+ // Make them empty again.
+ db1.clear();
+ db2.clear();
+ assert(db1 == db2);
+}
+
+void pqt_test_assignment()
+{
+ stack_printer __stack_printer__("::pqt_test_assignment");
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ db_type db1, db2;
+ string A("A");
+ string B("B");
+ string C("C");
+ string D("D");
+ string E("E");
+ string F("F");
+
+ db1.insert(0, 10, &A);
+ db1.insert(2, 5, &B);
+ db1.insert(-10, 2, &C);
+ db1.insert(5, 7, &D);
+ vector<db_type::node_data> expected;
+ expected.push_back(db_type::node_data(0, 10, &A));
+ expected.push_back(db_type::node_data(2, 5, &B));
+ expected.push_back(db_type::node_data(-10, 2, &C));
+ expected.push_back(db_type::node_data(5, 7, &D));
+ bool success = db1.verify_data(expected);
+ assert(success);
+
+ db2 = db1;
+ success = db2.verify_data(expected);
+ assert(success);
+ success = db1.verify_data(expected);
+ assert(success);
+
+ db2.insert(12, 45, &E);
+ db2.insert(20, 42, &F);
+ success = db2.verify_data(expected); // This should fail.
+ assert(!success);
+ db2 = db1; // Assign once again.
+ success = db2.verify_data(expected); // This now should succeed.
+ assert(success);
+}
+
+void pqt_test_swap()
+{
+ stack_printer __stack_printer__("::pqt_test_swap");
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ db_type db1, db2;
+ string A("A");
+ string B("B");
+ string C("C");
+ string D("D");
+ string E("E");
+ string F("F");
+
+ db1.insert(0, 10, &A);
+ db1.insert(2, 5, &B);
+ db1.insert(-10, 2, &C);
+ db1.insert(5, 7, &D);
+ vector<db_type::node_data> expected;
+ expected.push_back(db_type::node_data(0, 10, &A));
+ expected.push_back(db_type::node_data(2, 5, &B));
+ expected.push_back(db_type::node_data(-10, 2, &C));
+ expected.push_back(db_type::node_data(5, 7, &D));
+ bool success = db1.verify_data(expected);
+ assert(success);
+ assert(db2.empty());
+
+ db1.swap(db2);
+ assert(db1.empty());
+ assert(!db2.empty());
+ success = db2.verify_data(expected);
+ assert(success);
+}
+
+template<typename _DbType>
+bool verify_find(
+ const _DbType& db, typename _DbType::key_type x, typename _DbType::key_type y,
+ const typename _DbType::value_type data)
+{
+ try
+ {
+ typename _DbType::value_type found = db.find(x, y);
+ cout << "found at (" << x << "," << y << "): " << found << endl;
+ if (found == data)
+ return true;
+ }
+ catch (const typename _DbType::data_not_found&)
+ {
+ cout << "nothing found at (" << x << "," << y << ")" << endl;
+ }
+ return false;
+}
+
+void pqt_test_find()
+{
+ stack_printer __stack_printer__("::pqt_test_find");
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ db_type db;
+ string A("A");
+ string B("B");
+ string C("C");
+ string D("D");
+ string E("E");
+ string F("F");
+ db.insert(92, 27, &A);
+ db.insert(53, 26, &B);
+ db.insert(69, 18, &C);
+ db.insert(0, 78, &D);
+ db.insert(17, 7, &E);
+ db.insert(91, 88, &F);
+ assert(db.size() == 6);
+ db.dump_tree_svg("obj/pqt_test_find.svg");
+
+ bool check;
+ check = verify_find(db, 92, 27, &A);
+ assert(check);
+ check = verify_find(db, 53, 26, &B);
+ assert(check);
+ check = verify_find(db, 69, 18, &C);
+ assert(check);
+ check = verify_find(db, 0, 78, &D);
+ assert(check);
+ check = verify_find(db, 17, 7, &E);
+ assert(check);
+ check = verify_find(db, 91, 88, &F);
+ assert(check);
+
+ // Check for non-existent data.
+ check = verify_find(db, 34, 86, &A);
+ assert(!check);
+ check = verify_find(db, -1, 7, &A);
+ assert(!check);
+ check = verify_find(db, 91, 27, &A);
+ assert(!check);
+}
+
+void pqt_test_node_access()
+{
+ stack_printer __stack_printer__("::pqt_test_node_access");
+ typedef point_quad_tree<int32_t, const string*> db_type;
+ db_type db;
+ db_type::node_access nac = db.get_node_access();
+ assert(!nac);
+ string A("A");
+ string B("B");
+ string C("C");
+ string D("D");
+ string E("E");
+ string F("F");
+ db.insert(92, 27, &A);
+ db.insert(53, 26, &B);
+ db.insert(69, 18, &C);
+ db.insert(0, 78, &D);
+ db.insert(17, 7, &E);
+ db.insert(91, 88, &F);
+ assert(db.size() == 6);
+
+ nac = db.get_node_access();
+ // Test root node.
+ assert(nac);
+ assert(nac.x() == 92);
+ assert(nac.y() == 27);
+ assert(nac.data() == &A);
+
+ bool success = db.verify_node_iterator(nac);
+ assert(success);
+}
+
+int main()
+{
+ try
+ {
+ pqt_test_basic();
+ pqt_test_insertion_removal();
+ pqt_test_remove_root();
+ pqt_test_equality();
+ pqt_test_assignment();
+ pqt_test_swap();
+ pqt_test_find();
+ pqt_test_node_access();
+ assert(get_node_instance_count() == 0);
+ }
+ catch (const std::exception& e)
+ {
+ cout << "Test failed: " << e.what() << endl;
+ return EXIT_FAILURE;
+ }
+
+ cout << "Test finished successfully!" << endl;
+ return EXIT_SUCCESS;
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-03 17:12:49 +0000