// Copyright (C) 2003 Davis E. King (davis@dlib.net) // License: Boost Software License See LICENSE.txt for the full license. #ifndef DLIB_HASH_TABLE_KERNEl_2_ #define DLIB_HASH_TABLE_KERNEl_2_ #include "hash_table_kernel_abstract.h" #include "../general_hash/general_hash.h" #include "../algs.h" #include "../interfaces/map_pair.h" #include "../interfaces/enumerable.h" #include "../interfaces/remover.h" #include "../assert.h" #include "../serialize.h" #include namespace dlib { template < typename domain, typename range, typename bst_base, typename mem_manager = default_memory_manager, typename compare = std::less > class hash_table_kernel_2 : public enumerable >, public pair_remover { /*! REQUIREMENTS ON bst_base bst_base is instantiated with domain and range and implements binray_search_tree/binary_search_tree_kernel_abstract.h INITIAL VALUE hash_size == 0 table == pointer to an array of num_of_buckets bst_base objects num_of_buckets == the number of buckets in the hash table current_bucket == 0 at_start_ == true CONVENTION current_element_valid() == (current_bucket != 0) element() == current_bucket->element() at_start_ == at_start() mask == num_of_buckets-1 for all integers i where &table[i] != current_bucket table[i].at_start() == true hash_size = size() == the number of elements in the hash_table and table == pointer to an array of num_of_buckets bst_base objects num_of_buckets == the number of buckets in the hash table and the elements in this hash table are stored in the bst_base objects in the array table !*/ public: typedef domain domain_type; typedef range range_type; typedef compare compare_type; typedef mem_manager mem_manager_type; explicit hash_table_kernel_2( unsigned long expnum ); virtual ~hash_table_kernel_2( ) { pool.deallocate_array(table); } void clear( ); unsigned long count ( const domain& item ) const; inline void add ( domain& d, range& r ); void destroy ( const domain& d ); void remove ( const domain& d, domain& d_copy, range& r ); const range* operator[] ( const domain& item ) const; range* operator[] ( const domain& item ); inline void swap ( hash_table_kernel_2& item ); // functions from the remover interface void remove_any ( domain& d, range& r ); // functions from the enumerable interface inline size_t size ( ) const; inline bool at_start ( ) const; inline void reset ( ) const; bool current_element_valid ( ) const; inline const map_pair& element ( ) const; inline map_pair& element ( ); bool move_next ( ) const; private: // data members typename mem_manager::template rebind::other pool; unsigned long mask; unsigned long hash_size; unsigned long num_of_buckets; bst_base* table; general_hash hash; mutable bst_base* current_bucket; mutable bool at_start_; compare comp; // restricted functions hash_table_kernel_2(hash_table_kernel_2&); hash_table_kernel_2& operator=(hash_table_kernel_2&); }; template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > inline void swap ( hash_table_kernel_2& a, hash_table_kernel_2& b ) { a.swap(b); } template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void deserialize ( hash_table_kernel_2& item, std::istream& in ) { try { item.clear(); unsigned long size; deserialize(size,in); domain d; range r; for (unsigned long i = 0; i < size; ++i) { deserialize(d,in); deserialize(r,in); item.add(d,r); } } catch (serialization_error e) { item.clear(); throw serialization_error(e.info + "\n while deserializing object of type hash_table_kernel_2"); } } // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // member function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > hash_table_kernel_2:: hash_table_kernel_2( unsigned long expnum ) : hash_size(0), current_bucket(0), at_start_(true) { num_of_buckets = 1; while (expnum != 0) { --expnum; num_of_buckets <<= 1; } mask = num_of_buckets-1; table = pool.allocate_array(num_of_buckets); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: clear( ) { if (hash_size != 0) { hash_size = 0; for (unsigned long i = 0; i < num_of_buckets; ++i) table[i].clear(); } // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > size_t hash_table_kernel_2:: size( ) const { return hash_size; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > unsigned long hash_table_kernel_2:: count( const domain& item ) const { return table[hash(item)&mask].count(item); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: destroy( const domain& item ) { table[hash(item)&mask].destroy(item); --hash_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: add( domain& d, range& r ) { table[hash(d)&mask].add(d,r); ++hash_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: remove( const domain& d, domain& d_copy, range& r ) { table[hash(d)&mask].remove(d,d_copy,r); --hash_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: remove_any( domain& d, range& r ) { unsigned long i = 0; while (table[i].size() == 0) { ++i; } table[i].remove_any(d,r); --hash_size; // reset the enumerator reset(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > const range* hash_table_kernel_2:: operator[]( const domain& d ) const { return table[hash(d)&mask][d]; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > range* hash_table_kernel_2:: operator[]( const domain& d ) { return table[hash(d)&mask][d]; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: swap( hash_table_kernel_2& item ) { pool.swap(item.pool); exchange(mask,item.mask); exchange(hash_size,item.hash_size); exchange(num_of_buckets,item.num_of_buckets); exchange(table,item.table); exchange(current_bucket,item.current_bucket); exchange(at_start_,item.at_start_); exchange(comp,item.comp); } // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // enumerable function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > bool hash_table_kernel_2:: at_start ( ) const { return at_start_; } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > void hash_table_kernel_2:: reset ( ) const { at_start_ = true; if (current_bucket != 0) { current_bucket->reset(); current_bucket = 0; } } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > bool hash_table_kernel_2:: current_element_valid ( ) const { return (current_bucket != 0); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > const map_pair& hash_table_kernel_2:: element ( ) const { return current_bucket->element(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > map_pair& hash_table_kernel_2:: element ( ) { return current_bucket->element(); } // ---------------------------------------------------------------------------------------- template < typename domain, typename range, typename bst_base, typename mem_manager, typename compare > bool hash_table_kernel_2:: move_next ( ) const { if (at_start_) { at_start_ = false; // if the queue is empty then there is nothing to do if (hash_size == 0) { return false; } else { // find the first element in the hash table current_bucket = table; while (current_bucket->size() == 0) { ++current_bucket; } current_bucket->move_next(); return true; } } else { // if we have already enumerated every element if (current_bucket == 0) { return false; } else { if (current_bucket->move_next()) { // if there is another element in this current bucket then use that return true; } else { // find the next bucket bst_base* end = table + num_of_buckets; current_bucket->reset(); while (true) { ++current_bucket; // if we ran out of buckets and didn't find anything if (current_bucket == end) { current_bucket = 0; return false; } if (current_bucket->size() > 0) { current_bucket->move_next(); return true; } } } } } } // ---------------------------------------------------------------------------------------- } #endif // DLIB_HASH_TABLE_KERNEl_2_