Adding upstream version 2.1.1.upstream/2.1.1upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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;
+}