dlib C++ Library - binary_search_tree.h

    // Copyright (C) 2003  Davis E. King (davisking@users.sourceforge.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_CASSERT(test.count(3) == 0,"");

            enumerable<map_pair<int,int> >& e = test;
            DLIB_CASSERT(e.at_start() == true,"");

            DLIB_CASSERT(test.count(3) == 0,"");

            for (int i = 0; i < 4; ++i)
            {
                DLIB_CASSERT(test.size() == 0,"");
                DLIB_CASSERT(test.count(3) == 0,"");
                DLIB_CASSERT(test.height() == 0,"");
                DLIB_CASSERT(test[5] == 0,"");
                DLIB_CASSERT(test[0] == 0,"");
                DLIB_CASSERT(test.at_start(),"");
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.count(3) == 0,"");

                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.count(3) == 0,"");

                DLIB_CASSERT(test.at_start() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                test.clear();
                test.position_enumerator(5);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false, "");
                test.position_enumerator(5);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false, "");
                test.position_enumerator(9);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false, "");
                test.clear();
                test.position_enumerator(5);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false, "");
                test.position_enumerator(5);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false, "");
                test.position_enumerator(9);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false, "");
                test.clear();
                DLIB_CASSERT(test.at_start() == true,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                DLIB_CASSERT(test.count(3) == 0,"");

                DLIB_CASSERT(test.size() == 0,"");
                DLIB_CASSERT(test.height() == 0,"");
                DLIB_CASSERT(test[5] == 0,"");
                DLIB_CASSERT(test[0] == 0,"");
                DLIB_CASSERT(const_cast<const bst&>(test)[5] == 0,"");
                DLIB_CASSERT(const_cast<const bst&>(test)[0] == 0,"");
                DLIB_CASSERT(test.at_start(),"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");

                DLIB_CASSERT(test.at_start() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                DLIB_CASSERT(test.count(3) == 0,"");
                test.reset();
                DLIB_CASSERT(test.count(3) == 0,"");

                DLIB_CASSERT(test.at_start(),"");
                DLIB_CASSERT(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_CASSERT(test.count(temp) == count+1,"");
                }

                {
                    unsigned long count = test.count(3);

                    a = 3; test.add(a,b); ++count;
                    DLIB_CASSERT(test.count(3) == count,"");
                    a = 3; test.add(a,b); ++count;
                    DLIB_CASSERT(test.count(3) == count,"");
                    a = 3; test.add(a,b); ++count;
                    DLIB_CASSERT(test.count(3) == count,"");
                    a = 3; test.add(a,b); ++count;
                    DLIB_CASSERT(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_CASSERT(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_CASSERT(test.size() == 10000,"");
                DLIB_CASSERT(test.at_start() == true,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                DLIB_CASSERT(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_CASSERT(a <= test.element().key(),"the numers are out of order but they should be in order");
                    a = test.element().key();
                    ++count;

                    DLIB_CASSERT(test.at_start() == false,"");
                    DLIB_CASSERT(test.current_element_valid() == true,"");
                }

                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.move_next() == false,"");

                DLIB_CASSERT(count == 10000,"");

                DLIB_CASSERT(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_CASSERT(test.at_start() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.size() == 10000,"");

                swap(test,test2);

                test2.reset();
                count = 0;
                a = 0;
                while (test2.move_next())
                {
                    DLIB_CASSERT(a <= test2.element().key(),"the numers are out of order but they should be in order");
                    a = test2.element().key();
                    ++count;

                    DLIB_CASSERT(test2.at_start() == false,"");
                    DLIB_CASSERT(test2.current_element_valid() == true,"");

                    if (count == 5000)
                    {
                        break;
                    }
                }

                DLIB_CASSERT(test2.move_next() == true,"");
                DLIB_CASSERT(test2.move_next() == true,"");
                DLIB_CASSERT(test2.move_next() == true,"");

                test2.reset();

                count = 0;
                a = 0;
                while (test2.move_next())
                {
                    DLIB_CASSERT(a <= test2.element().key(),"the numers are out of order but they should be in order");
                    a = test2.element().key();
                    ++count;

                    DLIB_CASSERT(test2.at_start() == false,"");
                    DLIB_CASSERT(test2.current_element_valid() == true,"");
                }

                DLIB_CASSERT(count == 10000,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");

                int last = 0;
                asc_pair_remover<int,int,typename bst::compare_type>& asdf = test2;
                DLIB_CASSERT(asdf.size() > 0,"");
                while (asdf.size() > 0)
                {
                    asdf.remove_any(a,b);
                    DLIB_CASSERT(last <= a,"");
                    last = a;
                    --count;
                    DLIB_CASSERT(asdf.size() == count,"");
                }

                DLIB_CASSERT(test2.size() == 0,"");
                DLIB_CASSERT(test2.height() ==0,"");
                DLIB_CASSERT(test2.at_start() == true,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");

                for (int i = 0; i < 10000; ++i)
                {
                    a = i;
                    b = i;
                    test2.add(a,b);
                    DLIB_CASSERT(test2.size() == (unsigned int)(i +1),"");
                    DLIB_CASSERT(test2.count(i) == 1,"");
                }

                a = 0;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.element().key() == a, "");
                DLIB_CASSERT(test2.element().value() == a, "");
                a = 0;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.element().key() == a, "");
                DLIB_CASSERT(test2.element().value() == a, "");
                a = 8;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.element().key() == a, "");
                DLIB_CASSERT(test2.element().value() == a, "");
                a = 1;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.element().key() == a, "");
                DLIB_CASSERT(test2.element().value() == a, "");
                a = -29;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.element().key() == 0, "");
                DLIB_CASSERT(test2.element().value() == 0, "");
                a = 10000;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                a = -29;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.element().key() == 0, "");
                DLIB_CASSERT(test2.element().value() == 0, "");
                a = 8;
                test2.position_enumerator(a);
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.element().key() == a, "");
                DLIB_CASSERT(test2.element().value() == a, "");
                test2.reset();

                DLIB_CASSERT(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_CASSERT(test2.at_start() == true,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.size() == 10000,"");

                for (int i = 0; i < 10000; ++i)
                {
                    DLIB_CASSERT(test2.move_next() == true,"");
                    DLIB_CASSERT(test2.element().key() == i,"");
                }

                DLIB_CASSERT(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_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == true,"");
                DLIB_CASSERT(test2.size() == 10000,"");

                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");

                a = 3;
                test2.add(a,b);
                DLIB_CASSERT(test2.count(3) == 2,"");

                for (int i = 0; i < 10000; ++i)
                {
                    test2.remove(i,a,b);
                    DLIB_CASSERT(i == a,"");
                }
                test2.remove(3,a,b);

                DLIB_CASSERT(test2.size() == 0,"");
                DLIB_CASSERT(test2.height() == 0,"");
                DLIB_CASSERT(test2.at_start() == true,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(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_CASSERT(test2.at_start() == true,"");
                DLIB_CASSERT(test2.move_next() == true,"");
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == true,"");
                DLIB_CASSERT(test2.move_next() == true,"");
                DLIB_CASSERT(test2.current_element_valid() == true,"");
                DLIB_CASSERT(test2.move_next() == true,"");
                DLIB_CASSERT(test2.current_element_valid() == true,"");
                DLIB_CASSERT(test2.move_next() == true,"");
                DLIB_CASSERT(test2.current_element_valid() == true,"");
                DLIB_CASSERT(test2.at_start() == false,"");

                for (int i = 0; i < 10000; ++i)
                {
                    a = ::rand()&0xFFFF;
                    test2.position_enumerator(a);
                    if (test2[a])
                    {
                        DLIB_CASSERT(test2.element().key() == a,"");
                    }
                    else if (a <= m)
                    {
                        DLIB_CASSERT(test2.element().key() > a,"");
                    }
                }

                test2.clear();

                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.at_start() == true,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.at_start() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.move_next() == false,"");
                DLIB_CASSERT(test2.current_element_valid() == false,"");
                DLIB_CASSERT(test2.at_start() == false,"");

                DLIB_CASSERT(test2.size() == 0,"");
                DLIB_CASSERT(test2.height() == 0,"");

                for (int i = 0; i < 20000; ++i)
                {
                    a = ::rand()&0x7FFF;
                    b = a;
                    test2.add(a,b);
                }

                DLIB_CASSERT(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_CASSERT(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_CASSERT(test2.at_start() == true,"");
                    while (test2.move_next())
                    {
                        *tmp = test2.element().key();
                        ++tmp;
                    }

                    DLIB_CASSERT(test2.at_start() == false,"");
                    DLIB_CASSERT(test2.current_element_valid() == false,"");
                    DLIB_CASSERT(test2.move_next() == false,"");

                    tmp = array;
                    for (int i = 0; i < 10000; ++i)
                    {
                        DLIB_CASSERT(*test2[*tmp] == *tmp,"");
                        DLIB_CASSERT(*test2[*tmp] == *tmp,"");
                        DLIB_CASSERT(*test2[*tmp] == *tmp,"");
                        DLIB_CASSERT(*const_cast<const bst&>(test2)[*tmp] == *tmp,"");
                        ++tmp;
                    }

                    tmp = array;
                    while (test2.size() > 0)
                    {
                        unsigned long count = test2.count(*tmp);
                        test2.destroy(*tmp);
                        DLIB_CASSERT(test2.count(*tmp)+1 == count,"");
                        ++tmp;
                    }

                    DLIB_CASSERT(test2.at_start() == true,"");
                    DLIB_CASSERT(test2.current_element_valid() == false,"");
                    DLIB_CASSERT(test2.move_next() == false,"");
                    DLIB_CASSERT(test2.at_start() == false,"");
                    test.swap(test2);
                    test.reset();

                    delete [] array;
                }

                DLIB_CASSERT(test.size() == 0,"");
                DLIB_CASSERT(test.height() == 0,"");

                for (unsigned long i = 1; i < 100; ++i)
                {
                    a = 1234;
                    test.add(a,b);
                    DLIB_CASSERT(test.count(1234) == i,"");
                }

                test.clear();

                for (int m = 0; m < 3; ++m)
                {

                    test2.clear();

                    DLIB_CASSERT(test2.current_element_valid() == false,"");
                    DLIB_CASSERT(test2.at_start() == true,"");
                    DLIB_CASSERT(test2.move_next() == false,"");
                    DLIB_CASSERT(test2.at_start() == false,"");
                    DLIB_CASSERT(test2.current_element_valid() == false,"");
                    DLIB_CASSERT(test2.move_next() == false,"");
                    DLIB_CASSERT(test2.current_element_valid() == false,"");
                    DLIB_CASSERT(test2.move_next() == false,"");
                    DLIB_CASSERT(test2.current_element_valid() == false,"");
                    DLIB_CASSERT(test2.at_start() == false,"");

                    DLIB_CASSERT(test2.size() == 0,"");
                    DLIB_CASSERT(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_CASSERT(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_CASSERT(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_CASSERT(test2.at_start() == true,"");
                        int count = 0;
                        while (test2.move_next())
                        {
                            *tmp = test2.element().key();
                            ++tmp;
                            *tmp_val = test2.element().value();
                            ++tmp_val;

                            DLIB_CASSERT(*test2[*(tmp-1)] == *(tmp_val-1),"");
                            ++count;
                        }

                        DLIB_CASSERT(count == (int)test2.size(),"");
                        DLIB_CASSERT(test2.at_start() == false,"");
                        DLIB_CASSERT(test2.current_element_valid() == false,"");
                        DLIB_CASSERT(test2.move_next() == false,"");

                        tmp = array;
                        tmp_val = array_val;
                        for (unsigned long i = 0; i < test2.size(); ++i)
                        {
                            DLIB_CASSERT(*test2[*tmp] == *tmp_val,i);
                            DLIB_CASSERT(*test2[*tmp] == *tmp_val,"");
                            DLIB_CASSERT(*test2[*tmp] == *tmp_val,"");
                            DLIB_CASSERT(*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_CASSERT(test2.count(*tmp)+1 == count,"");
                            ++tmp;
                        }

                        DLIB_CASSERT(test2.at_start() == true,"");
                        DLIB_CASSERT(test2.current_element_valid() == false,"");
                        DLIB_CASSERT(test2.move_next() == false,"");
                        DLIB_CASSERT(test2.at_start() == false,"");
                        test.swap(test2);
                        test.reset();

                        delete [] array;
                        delete [] array_val;
                    }

                    DLIB_CASSERT(test.size() == 0,"");
                    DLIB_CASSERT(test.height() == 0,"");

                    for (unsigned long i = 1; i < 100; ++i)
                    {
                        a = 1234;
                        test.add(a,b);
                        DLIB_CASSERT(test.count(1234) == i,"");
                    }

                    test.clear();

                }

                a = 1;
                b = 2;

                test.add(a,b);

                test.position_enumerator(0);
                a = 0;
                b = 0;
                DLIB_CASSERT(test.height() == 1,"");
                test.remove_current_element(a,b);
                DLIB_CASSERT(a == 1, "");
                DLIB_CASSERT(b == 2, "");
                DLIB_CASSERT(test.at_start() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.height() == 0,"");
                DLIB_CASSERT(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_CASSERT(test.height() == 2,"");
                test.remove_current_element(a,b);
                DLIB_CASSERT(a == 1, "");
                DLIB_CASSERT(b == 2, "");
                DLIB_CASSERT(test.at_start() == false,"");
                DLIB_CASSERT(test.current_element_valid() == true,"");
                DLIB_CASSERT(test.height() == 1,"");
                DLIB_CASSERT(test.size() == 1,"");

                test.remove_current_element(a,b);
                DLIB_CASSERT(a == 1, "");
                DLIB_CASSERT(b == 2, "");
                DLIB_CASSERT(test.at_start() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.height() == 0,"");
                DLIB_CASSERT(test.size() == 0,"");

                for (int i = 0; i < 100; ++i)
                {
                    a = i;
                    b = i;
                    test.add(a,b);
                }

                DLIB_CASSERT(test.size() == 100,"");
                test.remove_last_in_order(a,b);
                DLIB_CASSERT(a == 99, "");
                DLIB_CASSERT(b == 99, "");
                DLIB_CASSERT(test.size() == 99,"");
                test.remove_last_in_order(a,b);
                DLIB_CASSERT(a == 98, "");
                DLIB_CASSERT(b == 98, "");
                DLIB_CASSERT(test.size() == 98,"");

                test.position_enumerator(-10);
                for (int i = 0; i < 97; ++i)
                {
                    DLIB_CASSERT(test.element().key() == i, "");
                    DLIB_CASSERT(test.element().value() == i, "");
                    DLIB_CASSERT(test.move_next(), "");
                }
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                test.position_enumerator(10);
                for (int i = 10; i < 97; ++i)
                {
                    DLIB_CASSERT(test.element().key() == i, "");
                    DLIB_CASSERT(test.element().value() == i, "");
                    DLIB_CASSERT(test.move_next(), "");
                }
                DLIB_CASSERT(test.move_next() == false,"");
                DLIB_CASSERT(test.current_element_valid() == false,"");

                test.reset();
                DLIB_CASSERT(test.at_start(),"");
                DLIB_CASSERT(test.current_element_valid() == false,"");
                for (int i = 0; i < 98; ++i)
                {
                    DLIB_CASSERT(test.move_next(), "");
                    DLIB_CASSERT(test.element().key() == i, "");
                    DLIB_CASSERT(test.element().value() == i, "");
                }
                DLIB_CASSERT(test.size() == 98, test.size());
                DLIB_CASSERT(test.move_next() == false,"");

                test.position_enumerator(98);
                DLIB_CASSERT(test.current_element_valid() == false,"");
                DLIB_CASSERT(test.at_start() == false,"");

                test.position_enumerator(50);
                DLIB_CASSERT(test.element().key() == 50,"");
                DLIB_CASSERT(test.element().value() == 50,"");
                DLIB_CASSERT(test[50] != 0,"");
                test.remove_current_element(a,b);
                DLIB_CASSERT(test[50] == 0,"");
                DLIB_CASSERT(test.size() == 97, test.size());
                DLIB_CASSERT(a == 50,"");
                DLIB_CASSERT(b == 50,"");
                DLIB_CASSERT(test.element().key() == 51,"");
                DLIB_CASSERT(test.element().value() == 51,"");
                DLIB_CASSERT(test.current_element_valid(),"");
                test.remove_current_element(a,b);
                DLIB_CASSERT(test.size() == 96, test.size());
                DLIB_CASSERT(a == 51,"");
                DLIB_CASSERT(b == 51,"");
                DLIB_CASSERT(test.element().key() == 52,test.element().key());
                DLIB_CASSERT(test.element().value() == 52,test.element().value());
                DLIB_CASSERT(test.current_element_valid(),"");
                test.remove_current_element(a,b);
                DLIB_CASSERT(test.size() == 95, test.size());
                DLIB_CASSERT(a == 52,"");
                DLIB_CASSERT(b == 52,"");
                DLIB_CASSERT(test.element().key() == 53,test.element().key());
                DLIB_CASSERT(test.element().value() == 53,test.element().value());
                DLIB_CASSERT(test.current_element_valid(),"");
                test.position_enumerator(50);
                DLIB_CASSERT(test.element().key() == 53,test.element().key());
                DLIB_CASSERT(test.element().value() == 53,test.element().value());
                DLIB_CASSERT(test.current_element_valid(),"");
                test.position_enumerator(51);
                DLIB_CASSERT(test.element().key() == 53,test.element().key());
                DLIB_CASSERT(test.element().value() == 53,test.element().value());
                DLIB_CASSERT(test.current_element_valid(),"");
                test.position_enumerator(52);
                DLIB_CASSERT(test.element().key() == 53,test.element().key());
                DLIB_CASSERT(test.element().value() == 53,test.element().value());
                DLIB_CASSERT(test.current_element_valid(),"");
                test.position_enumerator(53);
                DLIB_CASSERT(test.element().key() == 53,test.element().key());
                DLIB_CASSERT(test.element().value() == 53,test.element().value());
                DLIB_CASSERT(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_CASSERT(c == a,"");
                    DLIB_CASSERT(d == a,"");
                    DLIB_CASSERT(lasta < a,"");
                    DLIB_CASSERT(lastb < b,"");
                    lasta = a;
                    lastb = b;
                }
                DLIB_CASSERT(count == 95, count);
                DLIB_CASSERT(test.size() == 0,"");
                DLIB_CASSERT(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_CASSERT(test.move_next(),"");
                    }
                    DLIB_CASSERT(test.current_element_valid(),"size: " << test.size() << "   num: " << num);
                    test.remove_current_element(a,b);
                    DLIB_CASSERT(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_CASSERT(a == 1,"");
                    DLIB_CASSERT(b == 1,"");
                }

                test.clear();

            }

            test.clear();
            test2.clear();

        }

    }

    #endif // DLIB_BINARY_SEARCH_TREE_KERNEl_TEST_H_