dlib C++ Library - hash_table.cpp

// Copyright (C) 2003 Davis E. King (davis@dlib.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_TEST(test.count(3) == 0);
 enumerable<map_pair<int,int> >& e = test;
 DLIB_TEST(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_TEST(test2.size() == 1);
 DLIB_TEST(*test2[4] == 5);
 DLIB_TEST(test2[99] == 0);
 DLIB_TEST(test2.move_next());
 DLIB_TEST(test2.element().key() == 4);
 DLIB_TEST(test2.element().value() == 5);
 swap(test,test2);
 DLIB_TEST(test.size() == 1);
 DLIB_TEST(*test[4] == 5);
 DLIB_TEST(test[99] == 0);
 test.swap(test2);
 a = 99; 
 b = 35;
 test2.add(a,b);
 DLIB_TEST(test2.size() == 2);
 DLIB_TEST(*test2[4] == 5);
 DLIB_TEST(*test2[99] == 35);
 DLIB_TEST(test2[99] != 0);
 DLIB_TEST(test2[949] == 0);
 test2.destroy(4);
 DLIB_TEST(test2.size() == 1);
 DLIB_TEST(test2[4] == 0);
 DLIB_TEST(*test2[99] == 35);
 DLIB_TEST(test2[99] != 0);
 DLIB_TEST(test2[949] == 0);
 test2.destroy(99);
 DLIB_TEST(test2.size() == 0);
 DLIB_TEST(test2[4] == 0); 
 DLIB_TEST(test2[99] == 0);
 DLIB_TEST(test2[949] == 0);
 test2.clear();
 }
 print_spinner();
 for (int j = 0; j < 4; ++j)
 {
 DLIB_TEST(test.count(3) == 0);
 DLIB_TEST(test.size() == 0);
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(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_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 = b = i;
 unsigned long count = test.count(a);
 test.add(a,b);
 DLIB_TEST(test.count(i) == count+1);
 }
 DLIB_TEST(test.size() == 10000);
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == true);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == true);
 DLIB_TEST(test.move_next() == true);
 DLIB_TEST(test.move_next() == true); 
 DLIB_TEST(test.current_element_valid() == true);
 test.reset();
 DLIB_TEST(test.size() == 10000);
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(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_TEST(test[*tmp] != 0); 
 DLIB_TEST(*tmp == test.element().key());
 DLIB_TEST(*tmp == test.element().value());
 DLIB_TEST(*tmp == test.element().key());
 DLIB_TEST(test.current_element_valid() == true);
 ++tmp;
 }
 DLIB_TEST(count == 10000);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(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_TEST(test2.at_start() == true);
 istringstream sin(sout.str());
 test2.clear();
 deserialize(test2,sin);
 DLIB_TEST(test2.at_start() == true);
 tmp = array;
 for (int i = 0; i < 10000; ++i)
 {
 DLIB_TEST(*test2[*tmp] == *tmp);
 DLIB_TEST(*test2[*tmp] == *tmp);
 DLIB_TEST(*test2[*tmp] == *tmp);
 ++tmp;
 }
 test2.swap(test);
 test.reset();
 DLIB_TEST(test.at_start() == true);
 count = 0;
 tmp = array;
 while (test.size() > 0)
 {
 test.remove(*tmp,a,b);
 ++tmp;
 ++count;
 }
 DLIB_TEST(count == 10000);
 DLIB_TEST(test.size() == 0);
 DLIB_TEST(count == 10000);
 delete [] array;
 }
 test.move_next();
 for (int i = 0; i < 10000; ++i)
 {
 a = ::rand();
 test.add(a,b);
 }
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.move_next() == true);
 DLIB_TEST(test.size() == 10000);
 for (int i = 0; i < 10000; ++i)
 {
 test.remove_any(a,b);
 }
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(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_TEST(test.size() == i+1);
 }
 DLIB_TEST(test.size() == 10000);
 for (int i = 0; i < 10000; ++i)
 {
 DLIB_TEST(*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_TEST(test.count(3) == 0);
 enumerable<map_pair<int,int> >& e = test;
 DLIB_TEST(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_TEST(test2.size() == 1);
 DLIB_TEST(*test2[4] == 5);
 DLIB_TEST(test2[99] == 0);
 DLIB_TEST(test2.move_next());
 DLIB_TEST(test2.element().key() == 4);
 DLIB_TEST(test2.element().value() == 5);
 swap(test,test2);
 DLIB_TEST(test.size() == 1);
 DLIB_TEST(*test[4] == 5);
 DLIB_TEST(test[99] == 0);
 test.swap(test2);
 a = 99; 
 b = 35;
 test2.add(a,b);
 DLIB_TEST(test2.size() == 2);
 DLIB_TEST(*test2[4] == 5);
 DLIB_TEST(*test2[99] == 35);
 DLIB_TEST(test2[99] != 0);
 DLIB_TEST(test2[949] == 0);
 test2.destroy(4);
 DLIB_TEST(test2.size() == 1);
 DLIB_TEST(test2[4] == 0);
 DLIB_TEST(*test2[99] == 35);
 DLIB_TEST(test2[99] != 0);
 DLIB_TEST(test2[949] == 0);
 test2.destroy(99);
 DLIB_TEST(test2.size() == 0);
 DLIB_TEST(test2[4] == 0); 
 DLIB_TEST(test2[99] == 0);
 DLIB_TEST(test2[949] == 0);
 test2.clear();
 }
 print_spinner();
 for (int j = 0; j < 4; ++j)
 {
 DLIB_TEST(test.count(3) == 0);
 DLIB_TEST(test.size() == 0);
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(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_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 = b = i;
 unsigned long count = test.count(a);
 test.add(a,b);
 DLIB_TEST(test.count(i) == count+1);
 }
 DLIB_TEST(test.size() == 10000);
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == true);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == true);
 DLIB_TEST(test.move_next() == true);
 DLIB_TEST(test.move_next() == true); 
 DLIB_TEST(test.current_element_valid() == true);
 test.reset();
 DLIB_TEST(test.size() == 10000);
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(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_TEST(test[*tmp] != 0); 
 DLIB_TEST(*tmp == test.element().key());
 DLIB_TEST(*tmp == test.element().value());
 DLIB_TEST(*tmp == test.element().key());
 DLIB_TEST(test.current_element_valid() == true);
 ++tmp;
 }
 DLIB_TEST(count == 10000);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.at_start() == false);
 DLIB_TEST(test.current_element_valid() == false);
 DLIB_TEST(test.size() == 10000);
 swap(test,test2);
 tmp = array;
 for (int i = 0; i < 10000; ++i)
 {
 DLIB_TEST(*test2[*tmp] == *tmp);
 DLIB_TEST(*test2[*tmp] == *tmp);
 DLIB_TEST(*test2[*tmp] == *tmp);
 ++tmp;
 }
 test2.swap(test);
 test.reset();
 DLIB_TEST(test.at_start() == true);
 count = 0;
 tmp = array;
 while (test.size() > 0)
 {
 test.remove(*tmp,a,b);
 ++tmp;
 ++count;
 }
 DLIB_TEST(count == 10000);
 DLIB_TEST(test.size() == 0);
 DLIB_TEST(count == 10000);
 delete [] array;
 }
 test.move_next();
 for (int i = 0; i < 10000; ++i)
 {
 a = ::rand();
 test.add(a,b);
 }
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.move_next() == true);
 DLIB_TEST(test.size() == 10000);
 for (int i = 0; i < 10000; ++i)
 {
 test.remove_any(a,b);
 }
 DLIB_TEST(test.at_start() == true);
 DLIB_TEST(test.move_next() == false);
 DLIB_TEST(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_TEST(test.size() == i+1);
 }
 DLIB_TEST(test.size() == 10000);
 for (int i = 0; i < 10000; ++i)
 {
 DLIB_TEST(*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;
}