diff options
Diffstat (limited to 'ml/dlib/dlib/hash_map')
| -rw-r--r-- | ml/dlib/dlib/hash_map/hash_map_kernel_1.h | 460 | ||||
| -rw-r--r-- | ml/dlib/dlib/hash_map/hash_map_kernel_abstract.h | 247 | ||||
| -rw-r--r-- | ml/dlib/dlib/hash_map/hash_map_kernel_c.h | 276 |
3 files changed, 983 insertions, 0 deletions
diff --git a/ml/dlib/dlib/hash_map/hash_map_kernel_1.h b/ml/dlib/dlib/hash_map/hash_map_kernel_1.h new file mode 100644 index 000000000..e8b1d6d71 --- /dev/null +++ b/ml/dlib/dlib/hash_map/hash_map_kernel_1.h @@ -0,0 +1,460 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_HASH_MAP_KERNEl_1_ +#define DLIB_HASH_MAP_KERNEl_1_ + +#include "hash_map_kernel_abstract.h" +#include "../algs.h" +#include "../general_hash/general_hash.h" +#include "../interfaces/enumerable.h" +#include "../interfaces/map_pair.h" +#include "../interfaces/remover.h" +#include "../assert.h" +#include "../serialize.h" + +namespace dlib +{ + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager = default_memory_manager + > + class hash_map_kernel_1 : public enumerable<map_pair<domain,range> >, + public pair_remover<domain,range> + { + + /*! + REQUIREMENTS ON hash_table + hash_table is instantiated with domain and range and + T_is_POD must be set to false and + implements hash_table/hash_table_kernel_abstract.h + + INITIAL VALUE + table.size() == 0 + + CONVENTION + table.size() = size() == the number of elements in the map + the elements in this hash_map are stored in table + !*/ + + + public: + + typedef domain domain_type; + typedef range range_type; + typedef typename hash_table::compare_type compare_type; + typedef mem_manager mem_manager_type; + + hash_map_kernel_1( + ) : + table(expnum) + { + COMPILE_TIME_ASSERT(expnum < 32); + } + + virtual ~hash_map_kernel_1( + ) + {} + + inline void clear( + ); + + void add ( + domain& d, + range& r + ); + + inline bool is_in_domain ( + const domain& d + ) const; + + void remove ( + const domain& d, + domain& d_copy, + range& r + ); + + void destroy ( + const domain& d + ); + + range& operator[] ( + const domain& d + ); + + const range& operator[] ( + const domain& d + ) const; + + inline void swap ( + hash_map_kernel_1& item + ); + + // functions from the remover interface + inline 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; + + inline bool current_element_valid ( + ) const; + + inline const map_pair<domain,range>& element ( + ) const; + + inline map_pair<domain,range>& element ( + ); + + inline bool move_next ( + ) const; + + private: + + hash_table table; + + // restricted functions + hash_map_kernel_1(hash_map_kernel_1&); + hash_map_kernel_1& operator= ( hash_map_kernel_1&); + + }; + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + inline void swap ( + hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>& a, + hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>& b + ) { a.swap(b); } + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void deserialize ( + hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>& 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_map_kernel_1"); + } + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + clear ( + ) + { + table.clear(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + add ( + domain& d, + range& r + ) + { + table.add(d,r); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + bool hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + is_in_domain( + const domain& d + ) const + { + return (table[d] != 0); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + remove_any ( + domain& d, + range& r + ) + { + table.remove_any(d,r); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + remove( + const domain& d, + domain& d_copy, + range& r + ) + { + table.remove(d,d_copy,r); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + destroy( + const domain& d + ) + { + table.destroy(d); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + range& hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + operator[]( + const domain& d + ) + { + return *table[d]; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + const range& hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + operator[]( + const domain& d + ) const + { + return *table[d]; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + size_t hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + size ( + ) const + { + return table.size(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + swap ( + hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>& item + ) + { + table.swap(item.table); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // enumerable function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + bool hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + at_start ( + ) const + { + return table.at_start(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + void hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + reset ( + ) const + { + table.reset(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + bool hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + current_element_valid ( + ) const + { + return table.current_element_valid(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + const map_pair<domain,range>& hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + element ( + ) const + { + return table.element(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + map_pair<domain,range>& hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + element ( + ) + { + return table.element(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename domain, + typename range, + unsigned long expnum, + typename hash_table, + typename mem_manager + > + bool hash_map_kernel_1<domain,range,expnum,hash_table,mem_manager>:: + move_next ( + ) const + { + return table.move_next(); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_HASH_MAP_KERNEl_1_ + diff --git a/ml/dlib/dlib/hash_map/hash_map_kernel_abstract.h b/ml/dlib/dlib/hash_map/hash_map_kernel_abstract.h new file mode 100644 index 000000000..cee404f54 --- /dev/null +++ b/ml/dlib/dlib/hash_map/hash_map_kernel_abstract.h @@ -0,0 +1,247 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_HASH_MAP_KERNEl_ABSTRACT_ +#ifdef DLIB_HASH_MAP_KERNEl_ABSTRACT_ + +#include "../general_hash/general_hash.h" +#include "../interfaces/enumerable.h" +#include "../interfaces/remover.h" +#include "../interfaces/map_pair.h" +#include "../serialize.h" +#include "../algs.h" +#include <functional> + +namespace dlib +{ + + template < + typename domain, + typename range, + unsigned long expnum, + typename mem_manager = default_memory_manager, + typename compare = std::less<T> + > + class hash_map : public enumerable<map_pair<domain,range> >, + public pair_remover<domain,range> + { + + /*! + REQUIREMENTS ON domain + domain must be comparable by compare where compare is a functor compatible with std::less and + domain must be hashable by general_hash + (general_hash is defined in dlib/general_hash) and + domain must be swappable by a global swap() and + domain must have a default constructor + + REQUIREMENTS ON range + range must be swappable by a global swap() and + range must have a default constructor + + REQUIREMENTS ON expnum + expnum < 32 + 2^expnum is the number of buckets to hash items of type T into. + Note that this is really just a suggestion to the hash table. + Implementations are free to manage the table size however is most + appropriate. + + REQUIREMENTS ON mem_manager + must be an implementation of memory_manager/memory_manager_kernel_abstract.h or + must be an implementation of memory_manager_global/memory_manager_global_kernel_abstract.h or + must be an implementation of memory_manager_stateless/memory_manager_stateless_kernel_abstract.h + mem_manager::type can be set to anything. + + POINTERS AND REFERENCES TO INTERNAL DATA + swap(), is_in_domain(), and operator[] functions do + not invalidate pointers or references to internal data. + All other functions have no such guarantees. + + INITIAL VALUE + size() == 0 + + ENUMERATION ORDER + No order is specified. Only that each element will be visited once + and only once. + + WHAT THIS OBJECT REPRESENTS + hash_map contains items of type domain and range + + This object is similar an array. It maps items of type domain on to + items of type range. + + Also note that unless specified otherwise, no member functions + of this object throw exceptions. + + definition of equivalent: + a is equivalent to b if + a < b == false and + b < a == false + !*/ + + public: + + typedef domain domain_type; + typedef range range_type; + typedef compare compare_type; + typedef mem_manager mem_manager_type; + + hash_map( + ); + /*! + ensures + - #*this is properly initialized + throws + - std::bad_alloc or any exception thrown by domain's or range's + constructor. + !*/ + + virtual ~hash_map( + ); + /*! + ensures + - all memory associated with *this has been released + !*/ + + void clear( + ); + /*! + ensures + - #*this has its initial value + throws + - std::bad_alloc or any exception thrown by domain's or range's + constructor. + if this exception is thrown then *this is unusable + until clear() is called and succeeds + !*/ + + void add ( + domain& d, + range& r + ); + /*! + requires + - &d != &r (i.e. d and r cannot be the same variable) + - is_in_domain(d) == false + ensures + - #is_in_domain(d) == true + - #operator[](d) == r + - #d and #r have initial values for their types + - #size() == size() + 1 + - #at_start() == true + throws + - std::bad_alloc or any exception thrown by domain's or range's + constructor. + if add() throws then it has no effect + !*/ + + bool is_in_domain ( + const domain& d + ) const; + /*! + ensures + - returns whether or not an element equivalent to d is in the + domain of *this + !*/ + + void remove ( + const domain& d, + domain& d_copy, + range& r + ); + /*! + requires + - &d != &r (i.e. d and r cannot be the same variable) + - &d != &d_copy (i.e. d and d_copy cannot be the same variable) + - &r != &d_copy (i.e. r and d_copy cannot be the same variable) + - is_in_domain(d) == true + ensures + - #is_in_domain(d) == false + - #d_copy is equivalent to d + - the element in the range of *this associated with #d_copy has + been swapped into #r + - #size() == size() - 1 + - #at_start() == true + !*/ + + void destroy ( + const domain& d + ); + /*! + requires + - is_in_domain(d) == true + ensures + - #is_in_domain(d) == false + - #size() == size() - 1 + - #at_start() == true + !*/ + + range& operator[] ( + const domain& d + ); + /*! + requires + - is_in_domain(d) == true + ensures + - returns a non-const reference to the element in the range of *this + associated with the element equivalent to d + !*/ + + const range& operator[] ( + const domain& d + ) const; + /*! + requires + - is_in_domain(d) == true + ensures + - returns a const reference to the element in the range of *this + associated with the element equivalent to d + !*/ + + void swap ( + hash_map& item + ); + /*! + ensures + - swaps *this and item + !*/ + + + private: + + // restricted functions + hash_map(hash_map&); + hash_map& operator=(hash_map&); + }; + + template < + typename domain, + typename range, + unsigned long expnum, + typename mem_manager, + typename compare + > + inline void swap ( + hash_map<domain,range,expnum,mem_manager,compare>& a, + hash_map<domain,range,expnum,mem_manager,compare>& b + ) { a.swap(b); } + /*! + provides a global swap function + !*/ + + template < + typename domain, + typename range, + unsigned long expnum, + typename mem_manager, + typename compare + > + void deserialize ( + hash_map<domain,range,expnum,mem_manager,compare>& item, + std::istream& in + ); + /*! + provides deserialization support + !*/ +} + +#endif // DLIB_HASH_MAP_KERNEl_ABSTRACT_ + diff --git a/ml/dlib/dlib/hash_map/hash_map_kernel_c.h b/ml/dlib/dlib/hash_map/hash_map_kernel_c.h new file mode 100644 index 000000000..4db937249 --- /dev/null +++ b/ml/dlib/dlib/hash_map/hash_map_kernel_c.h @@ -0,0 +1,276 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_HASH_MAP_KERNEl_C_ +#define DLIB_HASH_MAP_KERNEl_C_ + +#include "hash_map_kernel_abstract.h" +#include "../algs.h" +#include "../assert.h" + +namespace dlib +{ + + template < + typename hash_map_base + > + class hash_map_kernel_c : public hash_map_base + { + + typedef typename hash_map_base::domain_type domain; + typedef typename hash_map_base::range_type range; + + + public: + void add ( + domain& d, + range& r + ); + + void remove_any ( + domain& d, + range& r + ); + + void remove ( + const domain& d, + domain& d_copy, + range& r + ); + + void destroy ( + const domain& d + ); + + range& operator[] ( + const domain& d + ); + + const range& operator[] ( + const domain& d + ) const; + + const map_pair<domain,range>& element ( + ) const; + + map_pair<domain,range>& element ( + ); + }; + + template < + typename hash_map_base + > + inline void swap ( + hash_map_kernel_c<hash_map_base>& a, + hash_map_kernel_c<hash_map_base>& b + ) { a.swap(b); } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + void hash_map_kernel_c<hash_map_base>:: + add ( + domain& d, + range& r + ) + { + + // make sure requires clause is not broken + DLIB_CASSERT( (!this->is_in_domain(d)) && + (static_cast<void*>(&d) != static_cast<void*>(&r)), + "\tvoid hash_map::add" + << "\n\tdomain element being added must not already be in the hash_map" + << "\n\tand d and r must not be the same variable" + << "\n\tis_in_domain(d): " << (this->is_in_domain(d) ? "true" : "false") + << "\n\tthis: " << this + << "\n\t&d: " << static_cast<void*>(&d) + << "\n\t&r: " << static_cast<void*>(&r) + ); + + + // call the real function + hash_map_base::add(d,r); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + void hash_map_kernel_c<hash_map_base>:: + remove_any ( + domain& d, + range& r + ) + { + + + // make sure requires clause is not broken + DLIB_CASSERT( (this->size() > 0) && + (static_cast<void*>(&d) != static_cast<void*>(&r)), + "\tvoid hash_map::remove_any" + << "\n\tsize() must be greater than zero if something is going to be removed" + << "\n\tand d and r must not be the same variable." + << "\n\tsize(): " << this->size() + << "\n\tthis: " << this + << "\n\t&d: " << static_cast<void*>(&d) + << "\n\t&r: " << static_cast<void*>(&r) + ); + + + // call the real function + hash_map_base::remove_any(d,r); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + void hash_map_kernel_c<hash_map_base>:: + remove ( + const domain& d, + domain& d_copy, + range& r + ) + { + + + // make sure requires clause is not broken + DLIB_CASSERT( (this->is_in_domain(d)) && + (static_cast<const void*>(&d) != static_cast<void*>(&r)) && + (static_cast<void*>(&r) != static_cast<void*>(&d_copy)) && + (static_cast<const void*>(&d) != static_cast<void*>(&d_copy)), + "\tvoid hash_map::remove" + << "\n\tcan't remove something that isn't in the hash_map or if the paremeters" + << "\n\tare actually the same variable. Either way can't remove." + << "\n\tis_in_domain(d): " << (this->is_in_domain(d) ? "true" : "false") + << "\n\tthis: " << this + << "\n\t&d: " << static_cast<const void*>(&d) + << "\n\t&r: " << static_cast<void*>(&r) + << "\n\t&d_copy: " << static_cast<void*>(&d_copy) + ); + + + // call the real function + hash_map_base::remove(d,d_copy,r); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + void hash_map_kernel_c<hash_map_base>:: + destroy ( + const domain& d + ) + { + + + // make sure requires clause is not broken + DLIB_CASSERT( this->is_in_domain(d), + "\tvoid hash_map::destroy" + << "\n\tcan't remove something that isn't in the hash_map" + << "\n\tthis: " << this + << "\n\t&d: " << static_cast<const void*>(&d) + ); + + + // call the real function + hash_map_base::destroy(d); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + typename hash_map_base::range_type& hash_map_kernel_c<hash_map_base>:: + operator[] ( + const domain& d + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( this->is_in_domain(d), + "\trange& hash_map::operator[]" + << "\n\td must be in the domain of the hash_map" + << "\n\tthis: " << this + ); + + // call the real function + return hash_map_base::operator[](d); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + const typename hash_map_base::range_type& hash_map_kernel_c<hash_map_base>:: + operator[] ( + const domain& d + ) const + { + // make sure requires clause is not broken + DLIB_CASSERT( this->is_in_domain(d), + "\tconst range& hash_map::operator[]" + << "\n\td must be in the domain of the hash_map" + << "\n\tthis: " << this + ); + + // call the real function + return hash_map_base::operator[](d); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + const map_pair<typename hash_map_base::domain_type,typename hash_map_base::range_type>& hash_map_kernel_c<hash_map_base>:: + element ( + ) const + { + // make sure requires clause is not broken + DLIB_CASSERT(this->current_element_valid() == true, + "\tconst map_pair<domain,range>& hash_map::element" + << "\n\tyou can't access the current element if it doesn't exist" + << "\n\tthis: " << this + ); + + // call the real function + return hash_map_base::element(); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename hash_map_base + > + map_pair<typename hash_map_base::domain_type,typename hash_map_base::range_type>& hash_map_kernel_c<hash_map_base>:: + element ( + ) + { + // make sure requires clause is not broken + DLIB_CASSERT(this->current_element_valid() == true, + "\tmap_pair<domain,range>& hash_map::element" + << "\n\tyou can't access the current element if it doesn't exist" + << "\n\tthis: " << this + ); + + // call the real function + return hash_map_base::element(); + } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_HASH_MAP_KERNEl_C_ + |