summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/static_map
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/static_map')
-rw-r--r--ml/dlib/dlib/static_map/static_map_kernel_1.h756
-rw-r--r--ml/dlib/dlib/static_map/static_map_kernel_abstract.h181
-rw-r--r--ml/dlib/dlib/static_map/static_map_kernel_c.h89
3 files changed, 1026 insertions, 0 deletions
diff --git a/ml/dlib/dlib/static_map/static_map_kernel_1.h b/ml/dlib/dlib/static_map/static_map_kernel_1.h
new file mode 100644
index 000000000..a7b627ae6
--- /dev/null
+++ b/ml/dlib/dlib/static_map/static_map_kernel_1.h
@@ -0,0 +1,756 @@
+// Copyright (C) 2005 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_STATIC_MAP_KERNEl_1_
+#define DLIB_STATIC_MAP_KERNEl_1_
+
+#include "static_map_kernel_abstract.h"
+#include "../interfaces/map_pair.h"
+#include "../interfaces/enumerable.h"
+#include "../interfaces/remover.h"
+#include "../algs.h"
+#include "../serialize.h"
+#include <functional>
+
+namespace dlib
+{
+
+ template <
+ typename domain,
+ typename range,
+ typename compare = std::less<domain>
+ >
+ class static_map_kernel_1 : public enumerable<map_pair<domain,range> >
+ {
+
+ /*!
+ INITIAL VALUE
+ - map_size == 0
+ - d == 0
+ - r == 0
+ - mp.d = 0;
+ - at_start_ == true
+
+
+ CONVENTION
+ - size() == map_size
+ - if (size() > 0) then
+ - d == pointer to an array containing all the domain elements
+ - r == pointer to an array containing all the range elements
+ - for every i: operator[](d[i]) == r[i]
+ - d is sorted according to operator<
+ - else
+ - d == 0
+ - r == 0
+
+ - current_element_valid() == (mp.d != 0)
+ - at_start() == (at_start_)
+ - if (current_element_valid()) then
+ - element() == mp
+ !*/
+
+ class mpair : public map_pair<domain,range>
+ {
+ public:
+ const domain* d;
+ range* r;
+
+ const domain& key(
+ ) const { return *d; }
+
+ const range& value(
+ ) const { return *r; }
+
+ range& value(
+ ) { return *r; }
+ };
+
+
+ // I would define this outside the class but Borland 5.5 has some problems
+ // with non-inline templated friend functions.
+ friend void deserialize (
+ static_map_kernel_1& item,
+ std::istream& in
+ )
+ {
+ try
+ {
+ item.clear();
+ unsigned long size;
+ deserialize(size,in);
+ item.map_size = size;
+ item.d = new domain[size];
+ item.r = new range[size];
+ for (unsigned long i = 0; i < size; ++i)
+ {
+ deserialize(item.d[i],in);
+ deserialize(item.r[i],in);
+ }
+ }
+ catch (serialization_error& e)
+ {
+ item.map_size = 0;
+ if (item.d)
+ {
+ delete [] item.d;
+ item.d = 0;
+ }
+ if (item.r)
+ {
+ delete [] item.r;
+ item.r = 0;
+ }
+
+ throw serialization_error(e.info + "\n while deserializing object of type static_map_kernel_1");
+ }
+ catch (...)
+ {
+ item.map_size = 0;
+ if (item.d)
+ {
+ delete [] item.d;
+ item.d = 0;
+ }
+ if (item.r)
+ {
+ delete [] item.r;
+ item.r = 0;
+ }
+
+ throw;
+ }
+ }
+
+
+ public:
+
+ typedef domain domain_type;
+ typedef range range_type;
+ typedef compare compare_type;
+
+ static_map_kernel_1(
+ );
+
+ virtual ~static_map_kernel_1(
+ );
+
+ void clear (
+ );
+
+ void load (
+ pair_remover<domain,range>& source
+ );
+
+ void load (
+ asc_pair_remover<domain,range,compare>& source
+ );
+
+ inline const range* operator[] (
+ const domain& d
+ ) const;
+
+ inline range* operator[] (
+ const domain& d
+ );
+
+ inline void swap (
+ static_map_kernel_1& 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 map_pair<domain,range>& element (
+ ) const;
+
+ inline map_pair<domain,range>& element (
+ );
+
+ inline bool move_next (
+ ) const;
+
+
+ private:
+
+ bool binary_search (
+ const domain& item,
+ unsigned long& pos
+ ) const;
+ /*!
+ ensures
+ - if (there is an item in d equivalent to item) then
+ - returns true
+ - d[#pos] is equivalent item
+ - else
+ - returns false
+ !*/
+
+ void sort_arrays (
+ unsigned long left,
+ unsigned long right
+ );
+ /*!
+ requires
+ - left and right are within the bounts of the array
+ ensures
+ - everything in the convention is still true and d[left] though
+ d[right] is sorted according to operator<
+ !*/
+
+ void qsort_partition (
+ unsigned long& partition_element,
+ const unsigned long left,
+ const unsigned long right
+ );
+ /*!
+ requires
+ - left < right
+ - left and right are within the bounts of the array
+ ensures
+ - the convention is still true
+ - left <= #partition_element <= right
+ - all elements in #d < #d[#partition_element] have
+ indices >= left and < #partition_element
+ - all elements in #d >= #d[#partition_element] have
+ indices >= #partition_element and <= right
+ !*/
+
+ unsigned long median (
+ unsigned long one,
+ unsigned long two,
+ unsigned long three
+ );
+ /*!
+ requires
+ - one, two, and three are valid indexes into d
+ ensures
+ - returns the median of d[one], d[two], and d[three]
+ !*/
+
+
+
+
+ // data members
+ unsigned long map_size;
+ domain* d;
+ range* r;
+ mutable mpair mp;
+ mutable bool at_start_;
+ compare comp;
+
+ // restricted functions
+ static_map_kernel_1(static_map_kernel_1&); // copy constructor
+ static_map_kernel_1& operator=(static_map_kernel_1&); // assignment operator
+ };
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ inline void swap (
+ static_map_kernel_1<domain,range,compare>& a,
+ static_map_kernel_1<domain,range,compare>& b
+ ) { a.swap(b); }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ static_map_kernel_1<domain,range,compare>::
+ static_map_kernel_1(
+ ) :
+ map_size(0),
+ d(0),
+ r(0),
+ at_start_(true)
+ {
+ mp.d = 0;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ static_map_kernel_1<domain,range,compare>::
+ ~static_map_kernel_1(
+ )
+ {
+ if (map_size > 0)
+ {
+ delete [] d;
+ delete [] r;
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ clear (
+ )
+ {
+ if (map_size > 0)
+ {
+ map_size = 0;
+ delete [] d;
+ delete [] r;
+ d = 0;
+ r = 0;
+ }
+ reset();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ load (
+ pair_remover<domain,range>& source
+ )
+ {
+ if (source.size() > 0)
+ {
+ domain* old_d = d;
+ d = new domain[source.size()];
+ try { r = new range[source.size()]; }
+ catch (...) { delete [] d; d = old_d; throw; }
+
+ map_size = source.size();
+
+ for (unsigned long i = 0; source.size() > 0; ++i)
+ source.remove_any(d[i],r[i]);
+
+ sort_arrays(0,map_size-1);
+ }
+ else
+ {
+ clear();
+ }
+ reset();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ load (
+ asc_pair_remover<domain,range,compare>& source
+ )
+ {
+ if (source.size() > 0)
+ {
+ domain* old_d = d;
+ d = new domain[source.size()];
+ try { r = new range[source.size()]; }
+ catch (...) { delete [] d; d = old_d; throw; }
+
+ map_size = source.size();
+
+ for (unsigned long i = 0; source.size() > 0; ++i)
+ source.remove_any(d[i],r[i]);
+ }
+ else
+ {
+ clear();
+ }
+ reset();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ const range* static_map_kernel_1<domain,range,compare>::
+ operator[] (
+ const domain& d_item
+ ) const
+ {
+ unsigned long pos;
+ if (binary_search(d_item,pos))
+ return r+pos;
+ else
+ return 0;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ range* static_map_kernel_1<domain,range,compare>::
+ operator[] (
+ const domain& d_item
+ )
+ {
+ unsigned long pos;
+ if (binary_search(d_item,pos))
+ return r+pos;
+ else
+ return 0;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ size_t static_map_kernel_1<domain,range,compare>::
+ size (
+ ) const
+ {
+ return map_size;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ swap (
+ static_map_kernel_1<domain,range,compare>& item
+ )
+ {
+ exchange(map_size,item.map_size);
+ exchange(d,item.d);
+ exchange(r,item.r);
+ exchange(mp,item.mp);
+ exchange(at_start_,item.at_start_);
+ exchange(comp,item.comp);
+ }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // enumerable function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ bool static_map_kernel_1<domain,range,compare>::
+ at_start (
+ ) const
+ {
+ return (at_start_);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ reset (
+ ) const
+ {
+ mp.d = 0;
+ at_start_ = true;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ bool static_map_kernel_1<domain,range,compare>::
+ current_element_valid (
+ ) const
+ {
+ return (mp.d != 0);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ const map_pair<domain,range>& static_map_kernel_1<domain,range,compare>::
+ element (
+ ) const
+ {
+ return mp;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ map_pair<domain,range>& static_map_kernel_1<domain,range,compare>::
+ element (
+ )
+ {
+ return mp;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ bool static_map_kernel_1<domain,range,compare>::
+ move_next (
+ ) const
+ {
+ // if at_start() && size() > 0
+ if (at_start_ && map_size > 0)
+ {
+ at_start_ = false;
+ mp.r = r;
+ mp.d = d;
+ return true;
+ }
+ // else if current_element_valid()
+ else if (mp.d != 0)
+ {
+ ++mp.d;
+ ++mp.r;
+ if (static_cast<unsigned long>(mp.d - d) < map_size)
+ {
+ return true;
+ }
+ else
+ {
+ mp.d = 0;
+ return false;
+ }
+ }
+ else
+ {
+ at_start_ = false;
+ return false;
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // private member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ bool static_map_kernel_1<domain,range,compare>::
+ binary_search (
+ const domain& item,
+ unsigned long& pos
+ ) const
+ {
+ unsigned long high = map_size;
+ unsigned long low = 0;
+ unsigned long p = map_size;
+ unsigned long idx;
+ while (p > 0)
+ {
+ p = (high-low)>>1;
+ idx = p+low;
+ if (comp(item , d[idx]))
+ {
+ high = idx;
+ }
+ else if (comp(d[idx] , item))
+ {
+ low = idx;
+ }
+ else
+ {
+ pos = idx;
+ return true;
+ }
+ }
+ return false;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ sort_arrays (
+ unsigned long left,
+ unsigned long right
+ )
+ {
+ if ( left < right)
+ {
+ unsigned long partition_element;
+ qsort_partition(partition_element,left,right);
+
+ if (partition_element > 0)
+ sort_arrays(left,partition_element-1);
+ sort_arrays(partition_element+1,right);
+ }
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void static_map_kernel_1<domain,range,compare>::
+ qsort_partition (
+ unsigned long& partition_element,
+ const unsigned long left,
+ const unsigned long right
+ )
+ {
+ partition_element = right;
+
+ unsigned long med = median(partition_element,left,((right-left)>>1) +left);
+ exchange(d[partition_element],d[med]);
+ exchange(r[partition_element],r[med]);
+
+ unsigned long right_scan = right-1;
+ unsigned long left_scan = left;
+
+ while (true)
+ {
+ // find an element to the left of partition_element that needs to be moved
+ while ( comp( d[left_scan] , d[partition_element]) )
+ {
+ ++left_scan;
+ }
+
+ // find an element to the right of partition_element that needs to be moved
+ while (
+ !(comp (d[right_scan] , d[partition_element])) &&
+ (right_scan > left_scan)
+ )
+ {
+ --right_scan;
+ }
+ if (left_scan >= right_scan)
+ break;
+
+ exchange(d[left_scan],d[right_scan]);
+ exchange(r[left_scan],r[right_scan]);
+
+ }
+ exchange(d[left_scan],d[partition_element]);
+ exchange(r[left_scan],r[partition_element]);
+ partition_element = left_scan;
+
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ unsigned long static_map_kernel_1<domain,range,compare>::
+ median (
+ unsigned long one,
+ unsigned long two,
+ unsigned long three
+ )
+ {
+ if ( comp( d[one] , d[two]) )
+ {
+ // one < two
+ if ( comp( d[two] , d[three]) )
+ {
+ // one < two < three : two
+ return two;
+ }
+ else
+ {
+ // one < two >= three
+ if (comp( d[one] , d[three]))
+ {
+ // three
+ return three;
+ }
+ }
+
+ }
+ else
+ {
+ // one >= two
+ if ( comp(d[three] , d[one] ))
+ {
+ // three <= one >= two
+ if ( comp(d[three] , d[two]) )
+ {
+ // two
+ return two;
+ }
+ else
+ {
+ // three
+ return three;
+ }
+ }
+ }
+ return one;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_STATIC_MAP_KERNEl_1_
+
diff --git a/ml/dlib/dlib/static_map/static_map_kernel_abstract.h b/ml/dlib/dlib/static_map/static_map_kernel_abstract.h
new file mode 100644
index 000000000..0821367b5
--- /dev/null
+++ b/ml/dlib/dlib/static_map/static_map_kernel_abstract.h
@@ -0,0 +1,181 @@
+// Copyright (C) 2005 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#undef DLIB_STATIC_MAP_KERNEl_ABSTRACT_
+#ifdef DLIB_STATIC_MAP_KERNEl_ABSTRACT_
+
+#include "../interfaces/map_pair.h"
+#include "../interfaces/enumerable.h"
+#include "../interfaces/remover.h"
+#include "../serialize.h"
+#include <functional>
+
+namespace dlib
+{
+
+ template <
+ typename domain,
+ typename range,
+ typename compare = std::less<domain>
+ >
+ class static_map : public enumerable<map_pair<domain,range> >
+ {
+
+ /*!
+ REQUIREMENTS ON domain
+ domain must be comparable by compare where compare is a functor compatible with std::less and
+ domain is swappable by a global swap() and
+ domain must have a default constructor
+
+ REQUIREMENTS ON range
+ range is swappable by a global swap() and
+ range must have a default constructor
+
+ POINTERS AND REFERENCES TO INTERNAL DATA
+ Only the destructor and load_from() will invalidate pointers or
+ references to internal data.
+
+ INITIAL VALUE
+ size() == 0
+
+ ENUMERATION ORDER
+ The enumerator will iterate over the domain (and each associated
+ range element) elements in ascending order according to the compare functor.
+ (i.e. the elements are enumerated in sorted order)
+
+ WHAT THIS OBJECT REPRESENTS
+ static_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.
+
+ Also note that unless specified otherwise, no member functions
+ of this object throw exceptions.
+
+ NOTE
+ 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;
+
+ static_map (
+ );
+ /*!
+ ensures
+ - #*this is properly initialized
+ throws
+ - std::bad_alloc or any exception thrown by domain's or range's
+ constructor.
+ !*/
+
+ virtual ~static_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 load (
+ pair_remover<domain,range>& source
+ );
+ /*!
+ ensures
+ - #size() == source.size()
+ - #source.size() == 0
+ - all the pairs in source are removed and placed into #*this
+ - #at_start() == true
+ throws
+ - std::bad_alloc or any exception thrown by domain's or range's
+ constructor.
+ If this exception is thrown then the call to load() will have
+ no effect on #*this.
+ !*/
+
+ const range* operator[] (
+ const domain& d
+ ) const;
+ /*!
+ ensures
+ - if (there is an element in the domain equivalent to d) then
+ - returns a pointer to an element in the range of *this that
+ is associated with an element in the domain of *this
+ equivalent to d.
+ - else
+ - returns 0
+ !*/
+
+ range* operator[] (
+ const domain& d
+ );
+ /*!
+ ensures
+ - if (there is an element in the domain equivalent to d) then
+ - returns a pointer to an element in the range of *this that
+ is associated with an element in the domain of *this
+ equivalent to d.
+ - else
+ - returns 0
+ !*/
+
+ void swap (
+ static_map& item
+ );
+ /*!
+ ensures
+ - swaps *this and item
+ !*/
+
+ private:
+
+ // restricted functions
+ static_map(static_map&); // copy constructor
+ static_map& operator=(static_map&); // assignment operator
+ };
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ inline void swap (
+ static_map<domain,range,compare>& a,
+ static_map<domain,range,compare>& b
+ ) { a.swap(b); }
+ /*!
+ provides a global swap function
+ !*/
+
+ template <
+ typename domain,
+ typename range,
+ typename compare
+ >
+ void deserialize (
+ static_map<domain,range,compare>& item,
+ std::istream& in
+ );
+ /*!
+ provides deserialization support
+ !*/
+}
+
+#endif // DLIB_STATIC_MAP_KERNEl_ABSTRACT_
+
diff --git a/ml/dlib/dlib/static_map/static_map_kernel_c.h b/ml/dlib/dlib/static_map/static_map_kernel_c.h
new file mode 100644
index 000000000..576d79374
--- /dev/null
+++ b/ml/dlib/dlib/static_map/static_map_kernel_c.h
@@ -0,0 +1,89 @@
+// Copyright (C) 2005 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_STATIC_MAP_KERNEl_C_
+#define DLIB_STATIC_MAP_KERNEl_C_
+
+#include "static_map_kernel_abstract.h"
+#include "../algs.h"
+#include "../assert.h"
+#include "../interfaces/map_pair.h"
+#include "../interfaces/remover.h"
+
+namespace dlib
+{
+
+ template <
+ typename map_base
+ >
+ class static_map_kernel_c : public map_base
+ {
+ typedef typename map_base::domain_type domain;
+ typedef typename map_base::range_type range;
+
+ public:
+ const map_pair<domain,range>& element (
+ ) const;
+
+ map_pair<domain,range>& element (
+ );
+
+ };
+
+ template <
+ typename map_base
+ >
+ inline void swap (
+ static_map_kernel_c<map_base>& a,
+ static_map_kernel_c<map_base>& b
+ ) { a.swap(b); }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename map_base
+ >
+ const map_pair<typename map_base::domain_type,typename map_base::range_type>& static_map_kernel_c<map_base>::
+ element (
+ ) const
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT(this->current_element_valid() == true,
+ "\tconst map_pair<domain,range>& static_map::element"
+ << "\n\tyou can't access the current element if it doesn't exist"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ return map_base::element();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename map_base
+ >
+ map_pair<typename map_base::domain_type,typename map_base::range_type>& static_map_kernel_c<map_base>::
+ element (
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT(this->current_element_valid() == true,
+ "\tmap_pair<domain,range>& static_map::element"
+ << "\n\tyou can't access the current element if it doesn't exist"
+ << "\n\tthis: " << this
+ );
+
+ // call the real function
+ return map_base::element();
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_STATIC_MAP_KERNEl_C_
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-10 11:31:59 +0000