// Copyright (C) 2003 Davis E. King (davisking@users.sourceforge.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 "../memory_manager/memory_manager_kernel_abstract.h" #include <functional> namespace dlib { template < typename domain, typename range, unsigned long expnum, typename mem_manager = memory_manager<char>::kernel_1a, 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. 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_