dlib C++ Library - hash_set_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_SET_KERNEl_ABSTRACT_
    #ifdef DLIB_HASH_SET_KERNEl_ABSTRACT_

    #include "../general_hash/general_hash.h"
    #include "../interfaces/enumerable.h"
    #include "../interfaces/remover.h"
    #include "../serialize.h"
    #include "../memory_manager/memory_manager_kernel_abstract.h"
    #include <functional>

    namespace dlib
    {

        template <
            typename T,
            unsigned long expnum,
            typename mem_manager = memory_manager<char>::kernel_1a,
            typename compare = std::less<T>
            >
        class hash_set : public enumerable<const T>,
                         public remover<T>
        {

            /*!
                REQUIREMENTS ON T
                    domain must be comparable by compare where compare is a functor compatible with std::less and
                    T must be hashable by general_hash
                    (general_hash is defined in dlib/general_hash) and
                    T must be swappable by a global swap() and
                    T 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() and is_member() functions do not invalidate
                    pointers or references to internal data.
                    All other functions have no such guarantee.

                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_set contains items of type T

                    This object represents an unaddressed collection
                    of items.  Every element in a hash_set is unique.

                    definition of equivalent:
                    a is equivalent to b if
                    a < b == false and
                    b < a == false
            !*/

            public:

                typedef T type;
                typedef compare compare_type;
                typedef mem_manager mem_manager_type;

                hash_set(
                );
                /*!
                    ensures
                        - #*this is properly initialized
                    throws
                        - std::bad_alloc or any exception thrown by T's constructor
                !*/

                virtual ~hash_set(
                );
                /*!
                    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 T's constructor
                            if this exception is thrown then *this is unusable
                            until clear() is called and succeeds
                !*/

                void add (
                    T& item
                );
                /*!
                    requires
                        - is_member(item) == false
                    ensures
                        - #is_member(item) == true
                        - #item has an initial value for its type
                        - #size() == size() + 1
                        - #at_start() == true
                    throws
                        - std::bad_alloc or any exception thrown by T's constructor
                            if add() throws then it has no effect
                !*/

                bool is_member (
                    const T& item
                ) const;
                /*!
                    ensures
                        - returns whether or not there is an element in *this equivalent
                          to item
                !*/

                void remove (
                    const T& item,
                    T& item_copy
                );
                /*!
                    requires
                        - is_member(item) == true
                        - &item != &item_copy (i.e. item and item_copy cannot be the
                          same variable)
                    ensures
                        - #is_member(item) == false
                        - the element in *this equivalent to item has been removed and
                          swapped into #item_copy
                        - #size() == size() - 1
                        - #at_start() == true
                !*/

                void destroy (
                    const T& item
                );
                /*!
                    requires
                        - is_member(item) == true
                    ensures
                        - #is_member(item) == false
                        - #size() == size() - 1
                        - #at_start() == true
                !*/

                void swap (
                    hash_set& item
                );
                /*!
                    ensures
                        - swaps *this and item
                !*/

            private:

                // restricted functions
                hash_set(hash_set&);        // copy constructor
                hash_set& operator=(hash_set&);    // assignment operator

        };

        template <
            typename T,
            unsigned long expnum,
            typename mem_manager,
            typename compare
            >
        inline void swap (
            hash_set<T,expnum,mem_manager,compare>& a,
            hash_set<T,expnum,mem_manager,compare>& b
        ) { a.swap(b); }
        /*!
            provides a global swap function
        !*/

        template <
            typename T,
            unsigned long expnum,
            typename mem_manager,
            typename compare
            >
        void deserialize (
            hash_set<T,expnum,mem_manager,compare>& item,
            std::istream& in
        );
        /*!
            provides deserialization support
        !*/
    }

    #endif // DLIB_HASH_SET_KERNEl_ABSTRACT_