summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/set
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/set')
-rw-r--r--ml/dlib/dlib/set/set_compare_1.h122
-rw-r--r--ml/dlib/dlib/set/set_compare_abstract.h96
-rw-r--r--ml/dlib/dlib/set/set_kernel_1.h372
-rw-r--r--ml/dlib/dlib/set/set_kernel_abstract.h192
-rw-r--r--ml/dlib/dlib/set/set_kernel_c.h194
5 files changed, 976 insertions, 0 deletions
diff --git a/ml/dlib/dlib/set/set_compare_1.h b/ml/dlib/dlib/set/set_compare_1.h
new file mode 100644
index 000000000..d4b5e76ca
--- /dev/null
+++ b/ml/dlib/dlib/set/set_compare_1.h
@@ -0,0 +1,122 @@
+// Copyright (C) 2005 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_SET_COMPARe_1_
+#define DLIB_SET_COMPARe_1_
+
+#include "set_compare_abstract.h"
+
+#include "../algs.h"
+
+
+
+namespace dlib
+{
+
+ template <
+ typename set_base
+ >
+ class set_compare_1 : public set_base
+ {
+
+ public:
+
+ bool operator< (
+ const set_compare_1& rhs
+ ) const;
+
+ bool operator== (
+ const set_compare_1& rhs
+ ) const;
+
+ };
+
+
+ template <
+ typename set_base
+ >
+ inline void swap (
+ set_compare_1<set_base>& a,
+ set_compare_1<set_base>& b
+ ) { a.swap(b); }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ bool set_compare_1<set_base>::
+ operator< (
+ const set_compare_1<set_base>& rhs
+ ) const
+ {
+ bool result = false;
+ if (set_base::size() < rhs.size())
+ result = true;
+
+ if (set_base::size() == rhs.size())
+ {
+ rhs.reset();
+ set_base::reset();
+ while (rhs.move_next())
+ {
+ set_base::move_next();
+ if (set_base::element() < rhs.element())
+ {
+ result = true;
+ break;
+ }
+ else if (rhs.element() < set_base::element())
+ {
+ break;
+ }
+ }
+ }
+
+ set_base::reset();
+ rhs.reset();
+
+ return result;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ bool set_compare_1<set_base>::
+ operator== (
+ const set_compare_1<set_base>& rhs
+ ) const
+ {
+ bool result = true;
+ if (set_base::size() != rhs.size())
+ result = false;
+
+
+ rhs.reset();
+ set_base::reset();
+ while (rhs.move_next() && set_base::move_next())
+ {
+ if (!(rhs.element() == set_base::element()))
+ {
+ result = false;
+ break;
+ }
+ }
+
+ set_base::reset();
+ rhs.reset();
+
+ return result;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_SET_COMPARe_1_
+
diff --git a/ml/dlib/dlib/set/set_compare_abstract.h b/ml/dlib/dlib/set/set_compare_abstract.h
new file mode 100644
index 000000000..ff06218f8
--- /dev/null
+++ b/ml/dlib/dlib/set/set_compare_abstract.h
@@ -0,0 +1,96 @@
+// Copyright (C) 2005 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#undef DLIB_SET_COMPARe_ABSTRACT_
+#ifdef DLIB_SET_COMPARe_ABSTRACT_
+
+#include "set_kernel_abstract.h"
+
+#include "../algs.h"
+
+
+namespace dlib
+{
+
+ template <
+ typename set_base
+ >
+ class set_compare : public set_base
+ {
+
+ /*!
+ REQUIREMENTS ON set_base
+ must be an implementation of set/set_kernel_abstract.h
+
+ POINTERS AND REFERENCES TO INTERNAL DATA
+ operator== and operator< invalidate pointers or references to
+ data members.
+
+ WHAT THIS EXTENSION DOES FOR set
+ This gives a set the ability to compare itself to other
+ sets using the < and == operators.
+
+ The < operator is conceptually weird for sets. It is useful
+ though because it allows you to make sets of sets since
+ sets require that their containing type implement operator<.
+
+ Also note that it is the case that for any two sets a and b
+ if (a<b) == false and (b<a) == false then a == b.
+
+ Also note that unless specified otherwise, no member functions
+ of this object throw exceptions.
+
+
+ NOTATION
+ For the purposes of defining what these operators do I will
+ use the operator[] to reference the elements of the sets.
+ operator[] is defined to access the elements of the set in
+ the same order they would be enumerated by the enumerable
+ interface.
+ !*/
+
+ public:
+
+ bool operator< (
+ const set_compare& rhs
+ ) const;
+ /*!
+ ensures
+ - #at_start() == true
+ - if (size() < rhs.size()) then
+ - returns true
+ - else if (size() > rhs.size()) then
+ - returns false
+ - else
+ - returns true if there exists an integer j such that 0 <= j < size()
+ and for all integers i such that 0 <= i < j where it is true that
+ (*this)[i] == rhs[i] and (*this)[j] < rhs[j]
+ - returns false if there is no j that will satisfy the above conditions.
+ !*/
+
+ bool operator== (
+ const set_compare& rhs
+ ) const;
+ /*!
+ ensures
+ - #at_start() == true
+ - returns true if *this and rhs contain the same elements.
+ returns false otherwise.
+ !*/
+ };
+
+
+ template <
+ typename set_base
+ >
+ inline void swap (
+ set_compare<set_base>& a,
+ set_compare<set_base>& b
+ ) { a.swap(b); }
+ /*!
+ provides a global swap function
+ !*/
+
+}
+
+#endif // DLIB_SET_COMPARe_ABSTRACT_
+
diff --git a/ml/dlib/dlib/set/set_kernel_1.h b/ml/dlib/dlib/set/set_kernel_1.h
new file mode 100644
index 000000000..9df96e671
--- /dev/null
+++ b/ml/dlib/dlib/set/set_kernel_1.h
@@ -0,0 +1,372 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_SET_KERNEl_1_
+#define DLIB_SET_KERNEl_1_
+
+#include "set_kernel_abstract.h"
+#include "../algs.h"
+#include "../interfaces/enumerable.h"
+#include "../interfaces/remover.h"
+#include "../serialize.h"
+
+namespace dlib
+{
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager = default_memory_manager
+ >
+ class set_kernel_1 : public enumerable<const T>,
+ public asc_remover<T,typename bst_base::compare_type>
+ {
+
+ /*!
+ REQUIREMENTS ON bst_base
+ bst_base is instantiated with <domain=T,range=char> and
+ implements binray_search_tree/binary_search_tree_kernel_abstract.h
+
+ INITIAL VALUE
+ bst has its initial value
+
+ CONVENTION
+ bst.size() == the number of elements in the set and
+ the elements in the set are stored in bst
+ !*/
+
+
+ public:
+
+ typedef T type;
+ typedef typename bst_base::compare_type compare_type;
+ typedef mem_manager mem_manager_type;
+
+ set_kernel_1(
+ )
+ {
+ }
+
+ virtual ~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 (
+ 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:
+
+ bst_base bst;
+ char junk;
+
+ // restricted functions
+ set_kernel_1(set_kernel_1&);
+ set_kernel_1& operator=(set_kernel_1&);
+
+ };
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ inline void swap (
+ set_kernel_1<T,bst_base,mem_manager>& a,
+ set_kernel_1<T,bst_base,mem_manager>& b
+ ) { a.swap(b); }
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void deserialize (
+ set_kernel_1<T,bst_base,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 set_kernel_1");
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ clear (
+ )
+ {
+ bst.clear();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ add (
+ T& item
+ )
+ {
+ bst.add(item,junk);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ bool set_kernel_1<T,bst_base,mem_manager>::
+ is_member(
+ const T& item
+ ) const
+ {
+ return (bst[item] != 0);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ remove_any (
+ T& item
+ )
+ {
+ bst.remove_any(item,junk);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ remove(
+ const T& item,
+ T& item_copy
+ )
+ {
+ bst.remove(item,item_copy,junk);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ destroy(
+ const T& item
+ )
+ {
+ bst.destroy(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ size_t set_kernel_1<T,bst_base,mem_manager>::
+ size (
+ ) const
+ {
+ return bst.size();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ swap (
+ set_kernel_1<T,bst_base,mem_manager>& item
+ )
+ {
+ bst.swap(item.bst);
+ }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // enumerable function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ bool set_kernel_1<T,bst_base,mem_manager>::
+ at_start (
+ ) const
+ {
+ return bst.at_start();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ void set_kernel_1<T,bst_base,mem_manager>::
+ reset (
+ ) const
+ {
+ bst.reset();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ bool set_kernel_1<T,bst_base,mem_manager>::
+ current_element_valid (
+ ) const
+ {
+ return bst.current_element_valid();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ const T& set_kernel_1<T,bst_base,mem_manager>::
+ element (
+ ) const
+ {
+ return bst.element().key();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ const T& set_kernel_1<T,bst_base,mem_manager>::
+ element (
+ )
+ {
+ return bst.element().key();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename T,
+ typename bst_base,
+ typename mem_manager
+ >
+ bool set_kernel_1<T,bst_base,mem_manager>::
+ move_next (
+ ) const
+ {
+ return bst.move_next();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_SET_KERNEl_1_
+
diff --git a/ml/dlib/dlib/set/set_kernel_abstract.h b/ml/dlib/dlib/set/set_kernel_abstract.h
new file mode 100644
index 000000000..72a0a98b3
--- /dev/null
+++ b/ml/dlib/dlib/set/set_kernel_abstract.h
@@ -0,0 +1,192 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#undef DLIB_SET_KERNEl_ABSTRACT_
+#ifdef DLIB_SET_KERNEl_ABSTRACT_
+
+#include "../interfaces/enumerable.h"
+#include "../interfaces/remover.h"
+#include "../serialize.h"
+#include "../algs.h"
+#include <functional>
+
+namespace dlib
+{
+
+ template <
+ typename T,
+ typename mem_manager = default_memory_manager,
+ typename compare = std::less<T>
+ >
+ class set : public enumerable<const T>,
+ public asc_remover<T,compare>
+ {
+
+ /*!
+ REQUIREMENTS ON T
+ T must be comparable by compare where compare is a functor compatible with std::less and
+ T must be swappable by a global swap() and
+ T must have a default constructor
+
+ 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
+ The enumerator will iterate over the elements in the set in
+ ascending order according to the compare functor.
+ (i.e. the elements are enumerated in sorted order)
+
+ WHAT THIS OBJECT REPRESENTS
+ set contains items of type T
+
+ This object represents an unaddressed collection of items.
+ Every element in a 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;
+
+ set(
+ );
+ /*!
+ ensures
+ - #*this is properly initialized
+ throws
+ - std::bad_alloc or any exception thrown by T's constructor
+ !*/
+
+ virtual ~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 (
+ set& item
+ );
+ /*!
+ ensures
+ - swaps *this and item
+ !*/
+
+ private:
+
+ // restricted functions
+ set(set&); // copy constructor
+ set& operator=(set&); // assignment operator
+
+ };
+
+ template <
+ typename T,
+ typename mem_manager,
+ typename compare
+ >
+ inline void swap (
+ set<T,mem_manager,compare>& a,
+ set<T,mem_manager,compare>& b
+ ) { a.swap(b); }
+ /*!
+ provides a global swap function
+ !*/
+
+ template <
+ typename T,
+ typename mem_manager,
+ typename compare
+ >
+ void deserialize (
+ set<T,mem_manager,compare>& item,
+ std::istream& in
+ );
+ /*!
+ provides deserialization support
+ !*/
+}
+
+#endif // DLIB_SET_KERNEl_ABSTRACT_
+
diff --git a/ml/dlib/dlib/set/set_kernel_c.h b/ml/dlib/dlib/set/set_kernel_c.h
new file mode 100644
index 000000000..679f9fae4
--- /dev/null
+++ b/ml/dlib/dlib/set/set_kernel_c.h
@@ -0,0 +1,194 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_SET_KERNEl_C_
+#define DLIB_SET_KERNEl_C_
+
+#include "set_kernel_abstract.h"
+#include "../algs.h"
+#include "../assert.h"
+
+namespace dlib
+{
+
+ template <
+ typename set_base
+ >
+ class set_kernel_c : public set_base
+ {
+ typedef typename 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 T& element (
+ ) const;
+ };
+
+
+ template <
+ typename set_base
+ >
+ inline void swap (
+ set_kernel_c<set_base>& a,
+ set_kernel_c<set_base>& b
+ ) { a.swap(b); }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+// member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ void set_kernel_c<set_base>::
+ add(
+ T& item
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( !this->is_member(item),
+ "\tvoid set::add"
+ << "\n\titem being added must not already be in the set"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ set_base::add(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ void set_kernel_c<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 set::remove"
+ << "\n\titem should be in the set if it's going to be removed"
+ << "\n\tthis: " << this
+ << "\n\t&item: " << &item
+ << "\n\t&item_copy: " << &item_copy
+ << "\n\tis_member(item): " << (this->is_member(item)?"true":"false")
+ );
+
+ // call the real function
+ set_base::remove(item,item_copy);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ void set_kernel_c<set_base>::
+ destroy (
+ const T& item
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( this->is_member(item),
+ "\tvoid set::destroy"
+ << "\n\titem should be in the set if it's going to be removed"
+ << "\n\tthis: " << this
+ << "\n\t&item: " << &item
+ );
+
+ // call the real function
+ set_base::destroy(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ void set_kernel_c<set_base>::
+ remove_any (
+ T& item
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( this->size() != 0,
+ "\tvoid set::remove_any"
+ << "\n\tsize must be greater than zero if an item is to be removed"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ set_base::remove_any(item);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ const typename set_base::type& set_kernel_c<set_base>::
+ element (
+ ) const
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT(this->current_element_valid() == true,
+ "\tconst T& set::element() const"
+ << "\n\tyou can't access the current element if it doesn't exist"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ return set_base::element();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename set_base
+ >
+ const typename set_base::type& set_kernel_c<set_base>::
+ element (
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT(this->current_element_valid() == true,
+ "\tconst T& set::element"
+ << "\n\tyou can't access the current element if it doesn't exist"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ return set_base::element();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+
+}
+
+#endif // DLIB_SET_KERNEl_C_
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-10 12:04:29 +0000