dlib C++ Library - hash_map_kernel_abstract.h

    // 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_