summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/hash_set
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/hash_set')
-rw-r--r--ml/dlib/dlib/hash_set/hash_set_kernel_1.h391
-rw-r--r--ml/dlib/dlib/hash_set/hash_set_kernel_abstract.h207
-rw-r--r--ml/dlib/dlib/hash_set/hash_set_kernel_c.h190
3 files changed, 788 insertions, 0 deletions
diff --git a/ml/dlib/dlib/hash_set/hash_set_kernel_1.h b/ml/dlib/dlib/hash_set/hash_set_kernel_1.h
new file mode 100644
index 000000000..c40770b91
--- /dev/null
+++ b/ml/dlib/dlib/hash_set/hash_set_kernel_1.h
@@ -0,0 +1,391 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_HASH_SET_KERNEl_1_
+#define DLIB_HASH_SET_KERNEl_1_
+
+#include "hash_set_kernel_abstract.h"
+#include "../algs.h"
+#include "../general_hash/general_hash.h"
+#include "../interfaces/enumerable.h"
+#include "../interfaces/remover.h"
+#include "../assert.h"
+#include "../serialize.h"
+
+namespace dlib
+{
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager = default_memory_manager
+ >
+ class hash_set_kernel_1 : public enumerable<const T>,
+ public remover<T>
+ {
+
+ /*!
+ REQUIREMENTS ON hash_table
+ hash_table is instantiated with <domain=T,range=char> and
+ T_is_POD must be set to false and
+ is an implementation of hash_table/hash_table_kernel_abstract.h
+
+ INITIAL VALUE
+ table.size() == 0
+
+ CONVENTION
+ table.size() = size() == the number of elements in the set and
+ the elements in this hash_set are stored in table
+ !*/
+
+ public:
+
+ typedef T type;
+ typedef typename hash_table::compare_type compare_type;
+ typedef mem_manager mem_manager_type;
+
+ hash_set_kernel_1(
+ ) :
+ table(expnum)
+ {
+ COMPILE_TIME_ASSERT(expnum < 32);
+ }
+
+ virtual ~hash_set_kernel_1(
+ )
+ {}
+
+ inline void clear(
+ );
+
+ inline void add (
+ T& item
+ );
+
+ inline bool is_member (
+ const T& item
+ ) const;
+
+ inline void remove (
+ const T& item,
+ T& item_copy
+ );
+
+ inline void destroy (
+ const T& item
+ );
+
+ inline void swap (
+ hash_set_kernel_1& item
+ );
+
+ // functions from the remover interface
+ inline void remove_any (
+ T& item
+ );
+
+ // 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 T& element (
+ ) const;
+
+ inline const T& element (
+ );
+
+ inline bool move_next (
+ ) const;
+
+ private:
+
+ hash_table table;
+ char junk;
+
+ // restricted functions
+ hash_set_kernel_1(hash_set_kernel_1&);
+ hash_set_kernel_1& operator= ( hash_set_kernel_1&);
+
+ };
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ inline void swap (
+ hash_set_kernel_1<T,expnum,hash_table,mem_manager>& a,
+ hash_set_kernel_1<T,expnum,hash_table,mem_manager>& b
+ ) { a.swap(b); }
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void deserialize (
+ hash_set_kernel_1<T,expnum,hash_table,mem_manager>& item,
+ std::istream& in
+ )
+ {
+ try
+ {
+ item.clear();
+ unsigned long size;
+ deserialize(size,in);
+ T temp;
+ for (unsigned long i = 0; i < size; ++i)
+ {
+ deserialize(temp,in);
+ item.add(temp);
+ }
+ }
+ catch (serialization_error e)
+ {
+ item.clear();
+ throw serialization_error(e.info + "\n while deserializing object of type hash_set_kernel_1");
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ clear (
+ )
+ {
+ table.clear();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ add (
+ T& item
+ )
+ {
+ table.add(item,junk);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ bool hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ is_member(
+ const T& item
+ ) const
+ {
+ return (table[item] != 0);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ remove_any (
+ T& item
+ )
+ {
+ table.remove_any(item,junk);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ remove(
+ const T& item,
+ T& item_copy
+ )
+ {
+ table.remove(item,item_copy,junk);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ destroy(
+ const T& item
+ )
+ {
+ table.destroy(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ size_t hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ size (
+ ) const
+ {
+ return table.size();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ swap (
+ hash_set_kernel_1<T,expnum,hash_table,mem_manager>& item
+ )
+ {
+ table.swap(item.table);
+ }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // enumerable function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ bool hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ at_start (
+ ) const
+ {
+ return table.at_start();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ void hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ reset (
+ ) const
+ {
+ table.reset();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ bool hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ current_element_valid (
+ ) const
+ {
+ return table.current_element_valid();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ const T& hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ element (
+ ) const
+ {
+ return table.element().key();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ const T& hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ element (
+ )
+ {
+ return table.element().key();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename hash_table,
+ typename mem_manager
+ >
+ bool hash_set_kernel_1<T,expnum,hash_table,mem_manager>::
+ move_next (
+ ) const
+ {
+ return table.move_next();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_HASH_SET_KERNEl_1_
+
diff --git a/ml/dlib/dlib/hash_set/hash_set_kernel_abstract.h b/ml/dlib/dlib/hash_set/hash_set_kernel_abstract.h
new file mode 100644
index 000000000..35d1de74e
--- /dev/null
+++ b/ml/dlib/dlib/hash_set/hash_set_kernel_abstract.h
@@ -0,0 +1,207 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.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 "../algs.h"
+#include <functional>
+
+namespace dlib
+{
+
+ template <
+ typename T,
+ unsigned long expnum,
+ typename mem_manager = default_memory_manager,
+ 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.
+
+ 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 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_
+
diff --git a/ml/dlib/dlib/hash_set/hash_set_kernel_c.h b/ml/dlib/dlib/hash_set/hash_set_kernel_c.h
new file mode 100644
index 000000000..bd0abd848
--- /dev/null
+++ b/ml/dlib/dlib/hash_set/hash_set_kernel_c.h
@@ -0,0 +1,190 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_HASH_SET_KERNEl_C_
+#define DLIB_HASH_SET_KERNEl_C_
+
+#include "hash_set_kernel_abstract.h"
+#include "../algs.h"
+#include "../assert.h"
+
+namespace dlib
+{
+
+ template <
+ typename hash_set_base
+ >
+ class hash_set_kernel_c : public hash_set_base
+ {
+ typedef typename hash_set_base::type T;
+ public:
+
+ void add (
+ T& item
+ );
+
+ void remove_any (
+ T& item
+ );
+
+ void remove (
+ const T& item,
+ T& item_copy
+ );
+
+ void destroy (
+ const T& item
+ );
+
+ const T& element (
+ ) const;
+
+ const T& element (
+ );
+
+
+ };
+
+
+ template <
+ typename hash_set_base
+ >
+ inline void swap (
+ hash_set_kernel_c<hash_set_base>& a,
+ hash_set_kernel_c<hash_set_base>& b
+ ) { a.swap(b); }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename hash_set_base
+ >
+ void hash_set_kernel_c<hash_set_base>::
+ add(
+ T& item
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( !this->is_member(item),
+ "\tvoid hash_set::add"
+ << "\n\titem being added must not already be in the hash_set"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ hash_set_base::add(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename hash_set_base
+ >
+ void hash_set_kernel_c<hash_set_base>::
+ remove (
+ const T& item,
+ T& item_copy
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( this->is_member(item) &&
+ (static_cast<const void*>(&item) != static_cast<void*>(&item_copy)),
+ "\tvoid hash_set::remove"
+ << "\n\titem should be in the hash_set if it's going to be removed"
+ << "\n\tthis: " << this
+ << "\n\t&item: " << &item
+ << "\n\t&item_copy: " << &item_copy
+ );
+
+ // call the real function
+ hash_set_base::remove(item,item_copy);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename hash_set_base
+ >
+ void hash_set_kernel_c<hash_set_base>::
+ destroy (
+ const T& item
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( this->is_member(item),
+ "\tvoid hash_set::destroy"
+ << "\n\titem should be in the hash_set if it's going to be removed"
+ << "\n\tthis: " << this
+ << "\n\t&item: " << &item
+ );
+
+ // call the real function
+ hash_set_base::destroy(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename hash_set_base
+ >
+ void hash_set_kernel_c<hash_set_base>::
+ remove_any (
+ T& item
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( this->size() != 0,
+ "\tvoid hash_set::remove_any"
+ << "\n\tsize must be greater than zero if an item is to be removed"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ hash_set_base::remove_any(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename hash_set_base
+ >
+ const typename hash_set_base::type& hash_set_kernel_c<hash_set_base>::
+ element (
+ ) const
+ {
+ DLIB_CASSERT(this->current_element_valid() == true,
+ "\tconst T& hash_set::element()"
+ << "\n\tyou can't access the current element if it doesn't exist"
+ << "\n\tthis: " << this
+ );
+
+ return hash_set_base::element();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename hash_set_base
+ >
+ const typename hash_set_base::type& hash_set_kernel_c<hash_set_base>::
+ element (
+ )
+ {
+ DLIB_CASSERT(this->current_element_valid() == true,
+ "\tT& hash_set::element()"
+ << "\n\tyou can't access the current element if it doesn't exist"
+ << "\n\tthis: " << this
+ );
+
+ return hash_set_base::element();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_HASH_SET_KERNEl_C_
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-10 20:35:43 +0000