summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/test/binary_search_tree.h
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/test/binary_search_tree.h')
-rw-r--r--ml/dlib/dlib/test/binary_search_tree.h889
1 files changed, 889 insertions, 0 deletions
diff --git a/ml/dlib/dlib/test/binary_search_tree.h b/ml/dlib/dlib/test/binary_search_tree.h
new file mode 100644
index 000000000..18bdff70d
--- /dev/null
+++ b/ml/dlib/dlib/test/binary_search_tree.h
@@ -0,0 +1,889 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_
+#define DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_
+
+
+#include <sstream>
+#include <string>
+#include <cstdlib>
+#include <ctime>
+
+#include <dlib/memory_manager_global.h>
+#include <dlib/memory_manager_stateless.h>
+#include <dlib/binary_search_tree.h>
+#include "tester.h"
+
+namespace
+{
+
+ using namespace test;
+ using namespace std;
+ using namespace dlib;
+
+ logger dlog("test.binary_search_tree");
+
+ template <
+ typename bst
+ >
+ void binary_search_tree_kernel_test (
+ )
+ /*!
+ requires
+ - bst is an implementation of
+ binary_search_tree/binary_search_tree_kernel_abstract.h is instantiated
+ to map int to int
+ ensures
+ - runs tests on bst for compliance with the specs
+ !*/
+ {
+
+ bst test, test2;
+
+ srand(static_cast<unsigned int>(time(0)));
+
+
+ DLIB_TEST(test.count(3) == 0);
+
+ enumerable<map_pair<int,int> >& e = test;
+ DLIB_TEST(e.at_start() == true);
+
+ DLIB_TEST(test.count(3) == 0);
+
+ for (int i = 0; i < 4; ++i)
+ {
+ DLIB_TEST(test.size() == 0);
+ DLIB_TEST(test.count(3) == 0);
+ DLIB_TEST(test.height() == 0);
+ DLIB_TEST(test[5] == 0);
+ DLIB_TEST(test[0] == 0);
+ DLIB_TEST(test.at_start());
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.count(3) == 0);
+
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.count(3) == 0);
+
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+
+ test.clear();
+ test.position_enumerator(5);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+ test.position_enumerator(5);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+ test.position_enumerator(9);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+ test.clear();
+ test.position_enumerator(5);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+ test.position_enumerator(5);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+ test.position_enumerator(9);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+ test.clear();
+ DLIB_TEST(test.at_start() == true);
+ DLIB_TEST(test.current_element_valid() == false);
+
+
+ DLIB_TEST(test.count(3) == 0);
+
+ DLIB_TEST(test.size() == 0);
+ DLIB_TEST(test.height() == 0);
+ DLIB_TEST(test[5] == 0);
+ DLIB_TEST(test[0] == 0);
+ DLIB_TEST(const_cast<const bst&>(test)[5] == 0);
+ DLIB_TEST(const_cast<const bst&>(test)[0] == 0);
+ DLIB_TEST(test.at_start());
+ DLIB_TEST(test.current_element_valid() == false);
+
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+
+
+ DLIB_TEST(test.count(3) == 0);
+ test.reset();
+ DLIB_TEST(test.count(3) == 0);
+
+ DLIB_TEST(test.at_start());
+ DLIB_TEST(test.current_element_valid() == false);
+
+
+
+
+
+
+ int a = 0, b = 0;
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ a = ::rand()%1000;
+ int temp = a;
+ unsigned long count = test.count(a);
+ test.add(a,b);
+ DLIB_TEST(test.count(temp) == count+1);
+ }
+
+
+ {
+ unsigned long count = test.count(3);
+
+ a = 3; test.add(a,b); ++count;
+ DLIB_TEST(test.count(3) == count);
+ a = 3; test.add(a,b); ++count;
+ DLIB_TEST(test.count(3) == count);
+ a = 3; test.add(a,b); ++count;
+ DLIB_TEST(test.count(3) == count);
+ a = 3; test.add(a,b); ++count;
+ DLIB_TEST(test.count(3) == count);
+ }
+
+
+ test.clear();
+
+
+
+
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ b = 0;
+ int temp = a;
+ unsigned long count = test.count(a);
+ test.add(a,b);
+ DLIB_TEST(test.count(temp) == count+1);
+ }
+
+ // serialize the state of test, then clear test, then
+ // load the state back into test.
+ ostringstream sout;
+ serialize(test,sout);
+ istringstream sin(sout.str());
+ test.clear();
+ deserialize(test,sin);
+
+ DLIB_TEST(test.size() == 10000);
+ DLIB_TEST(test.at_start() == true);
+ DLIB_TEST(test.current_element_valid() == false);
+
+
+ DLIB_TEST_MSG(test.height() > 13 && test.height() <= 26,"this is somewhat of an implementation dependent "
+ << "but really it should be in this range or the implementation is just crap");
+
+ a = 0;
+ unsigned long count = 0;
+ while (test.move_next())
+ {
+ DLIB_TEST_MSG(a <= test.element().key(),"the numers are out of order but they should be in order");
+ a = test.element().key();
+ ++count;
+
+
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == true);
+ }
+
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.move_next() == false);
+
+ DLIB_TEST(count == 10000);
+
+
+
+
+ DLIB_TEST_MSG(test.height() > 13 && test.height() <= 26,"this is somewhat of an implementation dependent "
+ << "but really it should be in this range or the implementation is just crap");
+
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.size() == 10000);
+
+
+ swap(test,test2);
+
+
+ test2.reset();
+ count = 0;
+ a = 0;
+ while (test2.move_next())
+ {
+ DLIB_TEST_MSG(a <= test2.element().key(),"the numers are out of order but they should be in order");
+ a = test2.element().key();
+ ++count;
+
+
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == true);
+
+ if (count == 5000)
+ {
+ break;
+ }
+ }
+
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.move_next() == true);
+
+
+ test2.reset();
+
+ count = 0;
+ a = 0;
+ while (test2.move_next())
+ {
+ DLIB_TEST_MSG(a <= test2.element().key(),"the numers are out of order but they should be in order");
+ a = test2.element().key();
+ ++count;
+
+
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == true);
+ }
+
+ DLIB_TEST(count == 10000);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.move_next() == false);
+
+
+
+
+
+
+
+
+ int last = 0;
+ asc_pair_remover<int,int,typename bst::compare_type>& asdf = test2;
+ DLIB_TEST(asdf.size() > 0);
+ while (asdf.size() > 0)
+ {
+ asdf.remove_any(a,b);
+ DLIB_TEST(last <= a);
+ last = a;
+ --count;
+ DLIB_TEST(asdf.size() == count);
+ }
+
+
+ DLIB_TEST(test2.size() == 0);
+ DLIB_TEST(test2.height() ==0);
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.move_next() == false);
+
+
+
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ a = i;
+ b = i;
+ test2.add(a,b);
+ DLIB_TEST(test2.size() == (unsigned int)(i +1));
+ DLIB_TEST(test2.count(i) == 1);
+ }
+
+ a = 0;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.element().key() == a);
+ DLIB_TEST(test2.element().value() == a);
+ a = 0;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.element().key() == a);
+ DLIB_TEST(test2.element().value() == a);
+ a = 8;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.element().key() == a);
+ DLIB_TEST(test2.element().value() == a);
+ a = 1;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.element().key() == a);
+ DLIB_TEST(test2.element().value() == a);
+ a = -29;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.element().key() == 0);
+ DLIB_TEST(test2.element().value() == 0);
+ a = 10000;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ a = -29;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.element().key() == 0);
+ DLIB_TEST(test2.element().value() == 0);
+ a = 8;
+ test2.position_enumerator(a);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.element().key() == a);
+ DLIB_TEST(test2.element().value() == a);
+ test2.reset();
+
+
+ DLIB_TEST_MSG(test2.height() > 13 && test2.height() <= 26,"this is somewhat of an implementation dependent "
+ << "but really it should be in this range or the implementation is just crap");
+
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.size() == 10000);
+
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.element().key() == i);
+ }
+
+
+
+ DLIB_TEST_MSG(test2.height() > 13 && test2.height() <= 26,"this is somewhat of an implementation dependent "
+ << "but really it should be in this range or the implementation is just crap");
+
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == true);
+ DLIB_TEST(test2.size() == 10000);
+
+
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+
+ a = 3;
+ test2.add(a,b);
+ DLIB_TEST(test2.count(3) == 2);
+
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ test2.remove(i,a,b);
+ DLIB_TEST(i == a);
+ }
+ test2.remove(3,a,b);
+
+
+ DLIB_TEST(test2.size() == 0);
+ DLIB_TEST(test2.height() == 0);
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+
+
+
+ test2.clear();
+
+
+ int m = 0;
+ for (int i = 0; i < 10000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ m = max(a,m);
+ test2.add(a,b);
+ }
+
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == true);
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.current_element_valid() == true);
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.current_element_valid() == true);
+ DLIB_TEST(test2.move_next() == true);
+ DLIB_TEST(test2.current_element_valid() == true);
+ DLIB_TEST(test2.at_start() == false);
+
+ for (int i = 0; i < 10000; ++i)
+ {
+ a = ::rand()&0xFFFF;
+ test2.position_enumerator(a);
+ if (test2[a])
+ {
+ DLIB_TEST(test2.element().key() == a);
+ }
+ else if (a <= m)
+ {
+ DLIB_TEST(test2.element().key() > a);
+ }
+ }
+
+ test2.clear();
+
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.at_start() == false);
+
+
+ DLIB_TEST(test2.size() == 0);
+ DLIB_TEST(test2.height() == 0);
+
+
+ for (int i = 0; i < 20000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ b = a;
+ test2.add(a,b);
+ }
+
+
+ DLIB_TEST(test2.size() == 20000);
+
+
+
+ // remove a bunch of elements randomly
+ int c;
+ for (int i = 0; i < 50000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ if (test2[a] != 0)
+ {
+ test2.remove(a,b,c);
+ DLIB_TEST(a == b);
+ }
+ }
+
+
+ // now add a bunch more
+ for (int i = 0; i < 10000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ b = a;
+ test2.add(a,b);
+ }
+
+
+ // now iterate over it all and then remove all elements
+ {
+ int* array = new int[test2.size()];
+ int* tmp = array;
+ DLIB_TEST(test2.at_start() == true);
+ while (test2.move_next())
+ {
+ *tmp = test2.element().key();
+ ++tmp;
+ }
+
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+
+ tmp = array;
+ for (int i = 0; i < 10000; ++i)
+ {
+ DLIB_TEST(*test2[*tmp] == *tmp);
+ DLIB_TEST(*test2[*tmp] == *tmp);
+ DLIB_TEST(*test2[*tmp] == *tmp);
+ DLIB_TEST(*const_cast<const bst&>(test2)[*tmp] == *tmp);
+ ++tmp;
+ }
+
+ tmp = array;
+ while (test2.size() > 0)
+ {
+ unsigned long count = test2.count(*tmp);
+ test2.destroy(*tmp);
+ DLIB_TEST(test2.count(*tmp)+1 == count);
+ ++tmp;
+ }
+
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.at_start() == false);
+ test.swap(test2);
+ test.reset();
+
+ delete [] array;
+ }
+
+
+ DLIB_TEST(test.size() == 0);
+ DLIB_TEST(test.height() == 0);
+
+ for (unsigned long i = 1; i < 100; ++i)
+ {
+ a = 1234;
+ test.add(a,b);
+ DLIB_TEST(test.count(1234) == i);
+ }
+
+ test.clear();
+
+
+
+
+
+
+ for (int m = 0; m < 3; ++m)
+ {
+
+ test2.clear();
+
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.at_start() == false);
+
+
+ DLIB_TEST(test2.size() == 0);
+ DLIB_TEST(test2.height() == 0);
+
+
+ int counter = 0;
+ while (counter < 10000)
+ {
+ a = ::rand()&0x7FFF;
+ b = ::rand()&0x7FFF;
+ if (test2[a] == 0)
+ {
+ test2.add(a,b);
+ ++counter;
+ }
+
+ }
+
+
+
+ DLIB_TEST(test2.size() == 10000);
+
+
+
+ // remove a bunch of elements randomly
+ for (int i = 0; i < 20000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ if (test2[a] != 0)
+ {
+ test2.remove(a,b,c);
+ DLIB_TEST(a == b);
+ }
+ }
+
+
+ // now add a bunch more
+ for (int i = 0; i < 20000; ++i)
+ {
+ a = ::rand()&0x7FFF;
+ b = ::rand()&0x7FFF;
+ if (test2[a] == 0)
+ test2.add(a,b);
+ }
+
+
+ // now iterate over it all and then remove all elements
+ {
+ int* array = new int[test2.size()];
+ int* array_val = new int[test2.size()];
+ int* tmp = array;
+ int* tmp_val = array_val;
+ DLIB_TEST(test2.at_start() == true);
+ int count = 0;
+ while (test2.move_next())
+ {
+ *tmp = test2.element().key();
+ ++tmp;
+ *tmp_val = test2.element().value();
+ ++tmp_val;
+
+ DLIB_TEST(*test2[*(tmp-1)] == *(tmp_val-1));
+ ++count;
+ }
+
+ DLIB_TEST(count == (int)test2.size());
+ DLIB_TEST(test2.at_start() == false);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+
+ tmp = array;
+ tmp_val = array_val;
+ for (unsigned long i = 0; i < test2.size(); ++i)
+ {
+ DLIB_TEST_MSG(*test2[*tmp] == *tmp_val,i);
+ DLIB_TEST(*test2[*tmp] == *tmp_val);
+ DLIB_TEST(*test2[*tmp] == *tmp_val);
+ DLIB_TEST(*const_cast<const bst&>(test2)[*tmp] == *tmp_val);
+ ++tmp;
+ ++tmp_val;
+ }
+
+ // out << "\nsize: " << test2.size() << endl;
+ // out << "height: " << test2.height() << endl;
+
+ tmp = array;
+ while (test2.size() > 0)
+ {
+ unsigned long count = test2.count(*tmp);
+ test2.destroy(*tmp);
+ DLIB_TEST(test2.count(*tmp)+1 == count);
+ ++tmp;
+ }
+
+ DLIB_TEST(test2.at_start() == true);
+ DLIB_TEST(test2.current_element_valid() == false);
+ DLIB_TEST(test2.move_next() == false);
+ DLIB_TEST(test2.at_start() == false);
+ test.swap(test2);
+ test.reset();
+
+ delete [] array;
+ delete [] array_val;
+ }
+
+
+ DLIB_TEST(test.size() == 0);
+ DLIB_TEST(test.height() == 0);
+
+ for (unsigned long i = 1; i < 100; ++i)
+ {
+ a = 1234;
+ test.add(a,b);
+ DLIB_TEST(test.count(1234) == i);
+ }
+
+ test.clear();
+
+ }
+
+
+
+ a = 1;
+ b = 2;
+
+ test.add(a,b);
+
+ test.position_enumerator(0);
+ a = 0;
+ b = 0;
+ DLIB_TEST(test.height() == 1);
+ test.remove_current_element(a,b);
+ DLIB_TEST(a == 1);
+ DLIB_TEST(b == 2);
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.height() == 0);
+ DLIB_TEST(test.size() == 0);
+
+
+ a = 1;
+ b = 2;
+ test.add(a,b);
+ a = 1;
+ b = 2;
+ test.add(a,b);
+
+ test.position_enumerator(0);
+ a = 0;
+ b = 0;
+ DLIB_TEST(test.height() == 2);
+ test.remove_current_element(a,b);
+ DLIB_TEST(a == 1);
+ DLIB_TEST(b == 2);
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == true);
+ DLIB_TEST(test.height() == 1);
+ DLIB_TEST(test.size() == 1);
+
+ test.remove_current_element(a,b);
+ DLIB_TEST(a == 1);
+ DLIB_TEST(b == 2);
+ DLIB_TEST(test.at_start() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.height() == 0);
+ DLIB_TEST(test.size() == 0);
+
+ for (int i = 0; i < 100; ++i)
+ {
+ a = i;
+ b = i;
+ test.add(a,b);
+ }
+
+ DLIB_TEST(test.size() == 100);
+ test.remove_last_in_order(a,b);
+ DLIB_TEST(a == 99);
+ DLIB_TEST(b == 99);
+ DLIB_TEST(test.size() == 99);
+ test.remove_last_in_order(a,b);
+ DLIB_TEST(a == 98);
+ DLIB_TEST(b == 98);
+ DLIB_TEST(test.size() == 98);
+
+ test.position_enumerator(-10);
+ for (int i = 0; i < 97; ++i)
+ {
+ DLIB_TEST(test.element().key() == i);
+ DLIB_TEST(test.element().value() == i);
+ DLIB_TEST(test.move_next());
+ }
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+
+
+ test.position_enumerator(10);
+ for (int i = 10; i < 97; ++i)
+ {
+ DLIB_TEST(test.element().key() == i);
+ DLIB_TEST(test.element().value() == i);
+ DLIB_TEST(test.move_next());
+ }
+ DLIB_TEST(test.move_next() == false);
+ DLIB_TEST(test.current_element_valid() == false);
+
+ test.reset();
+ DLIB_TEST(test.at_start());
+ DLIB_TEST(test.current_element_valid() == false);
+ for (int i = 0; i < 98; ++i)
+ {
+ DLIB_TEST(test.move_next());
+ DLIB_TEST(test.element().key() == i);
+ DLIB_TEST(test.element().value() == i);
+ }
+ DLIB_TEST_MSG(test.size() == 98, test.size());
+ DLIB_TEST(test.move_next() == false);
+
+ test.position_enumerator(98);
+ DLIB_TEST(test.current_element_valid() == false);
+ DLIB_TEST(test.at_start() == false);
+
+
+ test.position_enumerator(50);
+ DLIB_TEST(test.element().key() == 50);
+ DLIB_TEST(test.element().value() == 50);
+ DLIB_TEST(test[50] != 0);
+ test.remove_current_element(a,b);
+ DLIB_TEST(test[50] == 0);
+ DLIB_TEST_MSG(test.size() == 97, test.size());
+ DLIB_TEST(a == 50);
+ DLIB_TEST(b == 50);
+ DLIB_TEST(test.element().key() == 51);
+ DLIB_TEST(test.element().value() == 51);
+ DLIB_TEST(test.current_element_valid());
+ test.remove_current_element(a,b);
+ DLIB_TEST_MSG(test.size() == 96, test.size());
+ DLIB_TEST(a == 51);
+ DLIB_TEST(b == 51);
+ DLIB_TEST_MSG(test.element().key() == 52,test.element().key());
+ DLIB_TEST_MSG(test.element().value() == 52,test.element().value());
+ DLIB_TEST(test.current_element_valid());
+ test.remove_current_element(a,b);
+ DLIB_TEST_MSG(test.size() == 95, test.size());
+ DLIB_TEST(a == 52);
+ DLIB_TEST(b == 52);
+ DLIB_TEST_MSG(test.element().key() == 53,test.element().key());
+ DLIB_TEST_MSG(test.element().value() == 53,test.element().value());
+ DLIB_TEST(test.current_element_valid());
+ test.position_enumerator(50);
+ DLIB_TEST_MSG(test.element().key() == 53,test.element().key());
+ DLIB_TEST_MSG(test.element().value() == 53,test.element().value());
+ DLIB_TEST(test.current_element_valid());
+ test.position_enumerator(51);
+ DLIB_TEST_MSG(test.element().key() == 53,test.element().key());
+ DLIB_TEST_MSG(test.element().value() == 53,test.element().value());
+ DLIB_TEST(test.current_element_valid());
+ test.position_enumerator(52);
+ DLIB_TEST_MSG(test.element().key() == 53,test.element().key());
+ DLIB_TEST_MSG(test.element().value() == 53,test.element().value());
+ DLIB_TEST(test.current_element_valid());
+ test.position_enumerator(53);
+ DLIB_TEST_MSG(test.element().key() == 53,test.element().key());
+ DLIB_TEST_MSG(test.element().value() == 53,test.element().value());
+ DLIB_TEST(test.current_element_valid());
+
+ test.reset();
+ test.move_next();
+ int lasta = -1, lastb = -1;
+ count = 0;
+ while (test.current_element_valid() )
+ {
+ ++count;
+ int c = test.element().key();
+ int d = test.element().value();
+ test.remove_current_element(a,b);
+ DLIB_TEST(c == a);
+ DLIB_TEST(d == a);
+ DLIB_TEST(lasta < a);
+ DLIB_TEST(lastb < b);
+ lasta = a;
+ lastb = b;
+ }
+ DLIB_TEST_MSG(count == 95, count);
+ DLIB_TEST(test.size() == 0);
+ DLIB_TEST(test.height() == 0);
+
+ test.clear();
+
+ for (int i = 0; i < 1000; ++i)
+ {
+ a = 1;
+ b = 1;
+ test.add(a,b);
+ }
+
+ for (int i = 0; i < 40; ++i)
+ {
+ int num = ::rand()%800 + 1;
+ test.reset();
+ for (int j = 0; j < num; ++j)
+ {
+ DLIB_TEST(test.move_next());
+ }
+ DLIB_TEST_MSG(test.current_element_valid(),"size: " << test.size() << " num: " << num);
+ test.remove_current_element(a,b);
+ DLIB_TEST_MSG(test.current_element_valid(),"size: " << test.size() << " num: " << num);
+ test.remove_current_element(a,b);
+ test.position_enumerator(1);
+ if (test.current_element_valid())
+ test.remove_current_element(a,b);
+ DLIB_TEST(a == 1);
+ DLIB_TEST(b == 1);
+ }
+
+ test.clear();
+
+ }
+
+
+ test.clear();
+ test2.clear();
+
+ }
+
+}
+
+#endif // DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-19 12:38:11 +0000