dlib C++ Library - hash_table.cpp

    // Copyright (C) 2003  Davis E. King (davisking@users.sourceforge.net)
    // License: Boost Software License   See LICENSE.txt for the full license.

    #include <sstream>
    #include <string>
    #include <cstdlib>
    #include <ctime>

    #include <dlib/hash_table.h>
    #include "tester.h"

    namespace
    {

        using namespace test;
        using namespace std;
        using namespace dlib;

        logger dlog("test.hash_table");

        template <
            typename hash_table
            >
        void hash_table_kernel_test (
        )
        /*!
            requires
                - hash_table is an implementation of hash_table/hash_table_kernel_abstract.h
                  and is instantiated to map ints to ints
            ensures
                - runs tests on hash_table for compliance with the specs
        !*/
        {

            srand(static_cast<unsigned int>(time(0)));

            {
                hash_table test(16);

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

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

                hash_table test2(16);

                hash_table test3(0);
                hash_table test4(0);

                print_spinner();

                int b;
                for (int j = 0; j < 4; ++j)
                {
                    int a = 4;
                    b = 5;
                    test2.add(a,b);
                    DLIB_CASSERT(test2.size() == 1,"");
                    DLIB_CASSERT(*test2[4] == 5,"");
                    DLIB_CASSERT(test2[99] == 0,"");

                    DLIB_CASSERT(test2.move_next(),"");
                    DLIB_CASSERT(test2.element().key() == 4,"");
                    DLIB_CASSERT(test2.element().value() == 5,"");

                    swap(test,test2);
                    DLIB_CASSERT(test.size() == 1,"");
                    DLIB_CASSERT(*test[4] == 5,"");
                    DLIB_CASSERT(test[99] == 0,"");

                    test.swap(test2);

                    a = 99;
                    b = 35;
                    test2.add(a,b);
                    DLIB_CASSERT(test2.size() == 2,"");
                    DLIB_CASSERT(*test2[4] == 5,"");
                    DLIB_CASSERT(*test2[99] == 35,"");
                    DLIB_CASSERT(test2[99] != 0,"");
                    DLIB_CASSERT(test2[949] == 0,"");

                    test2.destroy(4);
                    DLIB_CASSERT(test2.size() == 1,"");
                    DLIB_CASSERT(test2[4] == 0,"");
                    DLIB_CASSERT(*test2[99] == 35,"");
                    DLIB_CASSERT(test2[99] != 0,"");
                    DLIB_CASSERT(test2[949] == 0,"");

                    test2.destroy(99);
                    DLIB_CASSERT(test2.size() == 0,"");
                    DLIB_CASSERT(test2[4] == 0,"");
                    DLIB_CASSERT(test2[99] == 0,"");
                    DLIB_CASSERT(test2[949] == 0,"");

                    test2.clear();
                }

                print_spinner();

                for (int j = 0; j < 4; ++j)
                {

                    DLIB_CASSERT(test.count(3) == 0,"");
                    DLIB_CASSERT(test.size() == 0,"");
                    DLIB_CASSERT(test.at_start() == true,"");
                    DLIB_CASSERT(test.current_element_valid() == false,"");
                    DLIB_CASSERT(test.move_next() == false,"");
                    DLIB_CASSERT(test.at_start() == false,"");
                    DLIB_CASSERT(test.current_element_valid() == false,"");
                    DLIB_CASSERT(test.move_next() == false,"");
                    DLIB_CASSERT(test.move_next() == false,"");

                    int a;

                    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 = b = i;
                        unsigned long count = test.count(a);
                        test.add(a,b);
                        DLIB_CASSERT(test.count(i) == count+1,"");
                    }

                    DLIB_CASSERT(test.size() == 10000,"");
                    DLIB_CASSERT(test.at_start() == true,"");
                    DLIB_CASSERT(test.current_element_valid() == false,"");
                    DLIB_CASSERT(test.move_next() == true,"");
                    DLIB_CASSERT(test.at_start() == false,"");
                    DLIB_CASSERT(test.current_element_valid() == true,"");
                    DLIB_CASSERT(test.move_next() == true,"");
                    DLIB_CASSERT(test.move_next() == true,"");
                    DLIB_CASSERT(test.current_element_valid() == true,"");

                    test.reset();

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

                    if (test.size() > 0)
                    {
                        int* array = new int[test.size()];
                        int* tmp = array;

                        int count = 0;
                        while (test.move_next())
                        {
                            ++count;
                            *tmp = test.element().key();
                            DLIB_CASSERT(test[*tmp] != 0,"");
                            DLIB_CASSERT(*tmp == test.element().key(),"");
                            DLIB_CASSERT(*tmp == test.element().value(),"");
                            DLIB_CASSERT(*tmp == test.element().key(),"");
                            DLIB_CASSERT(test.current_element_valid() == true,"");
                            ++tmp;
                        }

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

                        DLIB_CASSERT(test.size() == 10000,"");

                        swap(test,test2);

                        // serialize the state of test2, then clear test2, then
                        // load the state back into test2.
                        ostringstream sout;
                        serialize(test2,sout);
                        DLIB_CASSERT(test2.at_start() == true,"");
                        istringstream sin(sout.str());
                        test2.clear();
                        deserialize(test2,sin);
                        DLIB_CASSERT(test2.at_start() == true,"");

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

                        test2.swap(test);
                        test.reset();

                        DLIB_CASSERT(test.at_start() == true,"");
                        count = 0;
                        tmp = array;
                        while (test.size() > 0)
                        {
                            test.remove(*tmp,a,b);

                            ++tmp;
                            ++count;
                        }

                        DLIB_CASSERT(count == 10000,"");
                        DLIB_CASSERT(test.size() == 0,"");

                        DLIB_CASSERT(count == 10000,"");

                        delete [] array;
                    }

                    test.move_next();

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

                    DLIB_CASSERT(test.at_start() == true,"");
                    DLIB_CASSERT(test.move_next() == true,"");

                    DLIB_CASSERT(test.size() == 10000,"");

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

                    DLIB_CASSERT(test.at_start() == true,"");
                    DLIB_CASSERT(test.move_next() == false,"");
                    DLIB_CASSERT(test.size() == 0,"");

                    test.clear();

                    int* dtmp = new int[10000];
                    int* rtmp = new int[10000];

                    int* d = dtmp;
                    int* r = rtmp;
                    for (unsigned long i = 0; i < 10000; ++i)
                    {
                        a = ::rand();
                        b = ::rand();
                        *d = a;
                        *r = b;
                        if (test[a] != 0)
                        {
                            --i;
                            continue;
                        }
                        test.add(a,b);
                        ++d;
                        ++r;
                        DLIB_CASSERT(test.size() == i+1,"");
                    }

                    DLIB_CASSERT(test.size() == 10000,"");

                    for (int i = 0; i < 10000; ++i)
                    {
                        DLIB_CASSERT(*test[dtmp[i]] == rtmp[i],"");
                    }

                    delete [] dtmp;
                    delete [] rtmp;

                    test.clear();
                }}

                print_spinner();

                // now do the same thing as above but with a much smaller hash table
                {
                    hash_table test(13);

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

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

                    hash_table test2(16);

                    hash_table test3(0);
                    hash_table test4(0);

                    int b;
                    for (int j = 0; j < 4; ++j)
                    {
                        int a = 4;
                        b = 5;
                        test2.add(a,b);
                        DLIB_CASSERT(test2.size() == 1,"");
                        DLIB_CASSERT(*test2[4] == 5,"");
                        DLIB_CASSERT(test2[99] == 0,"");

                        DLIB_CASSERT(test2.move_next(),"");
                        DLIB_CASSERT(test2.element().key() == 4,"");
                        DLIB_CASSERT(test2.element().value() == 5,"");

                        swap(test,test2);
                        DLIB_CASSERT(test.size() == 1,"");
                        DLIB_CASSERT(*test[4] == 5,"");
                        DLIB_CASSERT(test[99] == 0,"");

                        test.swap(test2);

                        a = 99;
                        b = 35;
                        test2.add(a,b);
                        DLIB_CASSERT(test2.size() == 2,"");
                        DLIB_CASSERT(*test2[4] == 5,"");
                        DLIB_CASSERT(*test2[99] == 35,"");
                        DLIB_CASSERT(test2[99] != 0,"");
                        DLIB_CASSERT(test2[949] == 0,"");

                        test2.destroy(4);
                        DLIB_CASSERT(test2.size() == 1,"");
                        DLIB_CASSERT(test2[4] == 0,"");
                        DLIB_CASSERT(*test2[99] == 35,"");
                        DLIB_CASSERT(test2[99] != 0,"");
                        DLIB_CASSERT(test2[949] == 0,"");

                        test2.destroy(99);
                        DLIB_CASSERT(test2.size() == 0,"");
                        DLIB_CASSERT(test2[4] == 0,"");
                        DLIB_CASSERT(test2[99] == 0,"");
                        DLIB_CASSERT(test2[949] == 0,"");

                        test2.clear();
                    }

                    print_spinner();

                    for (int j = 0; j < 4; ++j)
                    {

                        DLIB_CASSERT(test.count(3) == 0,"");
                        DLIB_CASSERT(test.size() == 0,"");
                        DLIB_CASSERT(test.at_start() == true,"");
                        DLIB_CASSERT(test.current_element_valid() == false,"");
                        DLIB_CASSERT(test.move_next() == false,"");
                        DLIB_CASSERT(test.at_start() == false,"");
                        DLIB_CASSERT(test.current_element_valid() == false,"");
                        DLIB_CASSERT(test.move_next() == false,"");
                        DLIB_CASSERT(test.move_next() == false,"");

                        int a;

                        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 = b = i;
                            unsigned long count = test.count(a);
                            test.add(a,b);
                            DLIB_CASSERT(test.count(i) == count+1,"");
                        }

                        DLIB_CASSERT(test.size() == 10000,"");
                        DLIB_CASSERT(test.at_start() == true,"");
                        DLIB_CASSERT(test.current_element_valid() == false,"");
                        DLIB_CASSERT(test.move_next() == true,"");
                        DLIB_CASSERT(test.at_start() == false,"");
                        DLIB_CASSERT(test.current_element_valid() == true,"");
                        DLIB_CASSERT(test.move_next() == true,"");
                        DLIB_CASSERT(test.move_next() == true,"");
                        DLIB_CASSERT(test.current_element_valid() == true,"");

                        test.reset();

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

                        if (test.size() > 0)
                        {
                            int* array = new int[test.size()];
                            int* tmp = array;

                            int count = 0;
                            while (test.move_next())
                            {
                                ++count;
                                *tmp = test.element().key();
                                DLIB_CASSERT(test[*tmp] != 0,"");
                                DLIB_CASSERT(*tmp == test.element().key(),"");
                                DLIB_CASSERT(*tmp == test.element().value(),"");
                                DLIB_CASSERT(*tmp == test.element().key(),"");
                                DLIB_CASSERT(test.current_element_valid() == true,"");
                                ++tmp;
                            }

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

                            DLIB_CASSERT(test.size() == 10000,"");

                            swap(test,test2);

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

                            test2.swap(test);
                            test.reset();

                            DLIB_CASSERT(test.at_start() == true,"");
                            count = 0;
                            tmp = array;
                            while (test.size() > 0)
                            {
                                test.remove(*tmp,a,b);

                                ++tmp;
                                ++count;
                            }

                            DLIB_CASSERT(count == 10000,"");
                            DLIB_CASSERT(test.size() == 0,"");

                            DLIB_CASSERT(count == 10000,"");

                            delete [] array;
                        }

                        test.move_next();

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

                        DLIB_CASSERT(test.at_start() == true,"");
                        DLIB_CASSERT(test.move_next() == true,"");

                        DLIB_CASSERT(test.size() == 10000,"");

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

                        DLIB_CASSERT(test.at_start() == true,"");
                        DLIB_CASSERT(test.move_next() == false,"");
                        DLIB_CASSERT(test.size() == 0,"");

                        test.clear();

                        int* dtmp = new int[10000];
                        int* rtmp = new int[10000];

                        int* d = dtmp;
                        int* r = rtmp;
                        for (unsigned long i = 0; i < 10000; ++i)
                        {
                            a = ::rand();
                            b = ::rand();
                            *d = a;
                            *r = b;
                            if (test[a] != 0)
                            {
                                --i;
                                continue;
                            }
                            test.add(a,b);
                            ++d;
                            ++r;
                            DLIB_CASSERT(test.size() == i+1,"");
                        }

                        DLIB_CASSERT(test.size() == 10000,"");

                        for (int i = 0; i < 10000; ++i)
                        {
                            DLIB_CASSERT(*test[dtmp[i]] == rtmp[i],"");
                        }

                        delete [] dtmp;
                        delete [] rtmp;

                        test.clear();
                    }}

        }

        class hash_table_tester : public tester
        {
        public:
            hash_table_tester (
            ) :
                tester ("test_hash_table",
                        "Runs tests on the hash_table component.")
            {}

            void perform_test (
            )
            {
                dlog << LINFO << "testing kernel_1a";
                hash_table_kernel_test<hash_table<int,int>::kernel_1a>  ();
                dlog << LINFO << "testing kernel_1a_c";
                hash_table_kernel_test<hash_table<int,int>::kernel_1a_c>();
                dlog << LINFO << "testing kernel_2a";
                hash_table_kernel_test<hash_table<int,int>::kernel_2a>  ();
                dlog << LINFO << "testing kernel_2a_c";
                hash_table_kernel_test<hash_table<int,int>::kernel_2a_c>();
            }
        } a;

    }