Merging upstream version 1.44.3.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 612 insertions, 0 deletions

diff --git a/ml/dlib/dlib/hash_table/hash_table_kernel_2.h b/ml/dlib/dlib/hash_table/hash_table_kernel_2.h
new file mode 100644
index 000000000..58646413c
--- /dev/null
+++ b/ml/dlib/dlib/hash_table/hash_table_kernel_2.h
@@ -0,0 +1,612 @@
+// Copyright (C) 2003  Davis E. King (davis@dlib.net)
+// License: Boost Software License   See LICENSE.txt for the full license.
+#ifndef DLIB_HASH_TABLE_KERNEl_2_
+#define DLIB_HASH_TABLE_KERNEl_2_
+
+#include "hash_table_kernel_abstract.h"
+#include "../general_hash/general_hash.h"
+#include "../algs.h"
+#include "../interfaces/map_pair.h"
+#include "../interfaces/enumerable.h"
+#include "../interfaces/remover.h"
+#include "../assert.h"
+#include "../serialize.h"
+#include <functional>
+
+namespace dlib 
+{
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager = default_memory_manager,
+        typename compare = std::less<domain>
+        >
+    class hash_table_kernel_2 : public enumerable<map_pair<domain,range> >,
+                                public pair_remover<domain,range>
+    {
+
+        /*!
+            REQUIREMENTS ON bst_base
+                bst_base is instantiated with domain and range and
+                implements binray_search_tree/binary_search_tree_kernel_abstract.h
+
+             INITIAL VALUE
+                hash_size == 0
+                table == pointer to an array of num_of_buckets bst_base objects
+                num_of_buckets == the number of buckets in the hash table
+                current_bucket == 0
+                at_start_ == true
+
+            CONVENTION
+                current_element_valid() == (current_bucket != 0)
+                element() == current_bucket->element()
+                at_start_ == at_start()
+
+                mask == num_of_buckets-1
+
+                for all integers i where &table[i] != current_bucket
+                    table[i].at_start() == true
+
+
+                hash_size = size() == the number of elements in the hash_table and
+                table == pointer to an array of num_of_buckets bst_base objects
+                num_of_buckets == the number of buckets in the hash table and
+                the elements in this hash table are stored in the bst_base objects in the
+                array table
+
+        !*/
+        
+
+ 
+        public:
+
+            typedef domain domain_type;
+            typedef range range_type;
+            typedef compare compare_type;
+            typedef mem_manager mem_manager_type;
+
+            explicit hash_table_kernel_2(
+                unsigned long expnum
+            );
+
+            virtual ~hash_table_kernel_2(
+            )
+            { pool.deallocate_array(table); }
+
+            void clear(
+            );
+
+            unsigned long count (
+                const domain& item
+            ) const;
+
+            inline void add (
+                domain& d,
+                range& r
+            );
+
+            void destroy (
+                const domain& d
+            );
+
+            void remove (
+                const domain& d,
+                domain& d_copy,
+                range& r
+            );
+
+            const range* operator[] (
+                const domain& item
+            ) const;
+
+            range* operator[] (
+                const domain& item
+            );
+
+            inline void swap (
+                hash_table_kernel_2& item
+            );
+
+            // functions from the remover interface
+            void remove_any (
+                domain& d,
+                range& r
+            );
+
+            // functions from the enumerable interface
+            inline size_t size (
+            ) const;
+
+            inline bool at_start (
+            ) const;
+
+            inline void reset (
+            ) const;
+
+            bool current_element_valid (
+            ) const;
+
+            inline const map_pair<domain,range>& element (
+            ) const;
+
+            inline map_pair<domain,range>& element (
+            );
+
+            bool move_next (
+            ) const;
+
+        private:
+
+            // data members   
+            typename mem_manager::template rebind<bst_base>::other pool;         
+            unsigned long mask;
+            unsigned long hash_size;
+            unsigned long num_of_buckets;
+            bst_base* table;
+            general_hash<domain> hash;
+            mutable bst_base* current_bucket;
+            mutable bool at_start_;
+            compare comp;
+
+            // restricted functions
+            hash_table_kernel_2(hash_table_kernel_2&);      
+            hash_table_kernel_2& operator=(hash_table_kernel_2&);
+
+    };
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    inline void swap (
+        hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>& a, 
+        hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>& b 
+    ) { a.swap(b); }
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void deserialize (
+        hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>& item, 
+        std::istream& in
+    )
+    {
+        try
+        {
+            item.clear();
+            unsigned long size;
+            deserialize(size,in);
+            domain d;
+            range r;
+            for (unsigned long i = 0; i < size; ++i)
+            {
+                deserialize(d,in);
+                deserialize(r,in);
+                item.add(d,r);
+            }
+        }
+        catch (serialization_error e)
+        { 
+            item.clear();
+            throw serialization_error(e.info + "\n   while deserializing object of type hash_table_kernel_2"); 
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+    // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    hash_table_kernel_2(
+        unsigned long expnum
+    ) :
+        hash_size(0),
+        current_bucket(0),
+        at_start_(true)
+    {
+
+        num_of_buckets = 1;
+        while (expnum != 0)
+        {
+            --expnum;
+            num_of_buckets <<= 1;            
+        }
+        mask = num_of_buckets-1;
+
+        table = pool.allocate_array(num_of_buckets);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    clear(
+    )
+    {
+        if (hash_size != 0)
+        {
+            hash_size = 0;
+            for (unsigned long i = 0; i < num_of_buckets; ++i)
+                table[i].clear();
+        }
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    size_t hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    size(
+    ) const
+    {
+        return hash_size;
+    }
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    unsigned long hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    count(
+        const domain& item
+    ) const
+    {
+        return table[hash(item)&mask].count(item);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    destroy(
+        const domain& item
+    ) 
+    {
+        table[hash(item)&mask].destroy(item);
+        --hash_size;
+
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    add(
+        domain& d,
+        range& r
+    )
+    {
+        table[hash(d)&mask].add(d,r);
+        ++hash_size;
+
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    remove(
+        const domain& d,
+        domain& d_copy,
+        range& r
+    )
+    {
+        table[hash(d)&mask].remove(d,d_copy,r);
+        --hash_size;
+
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    remove_any(
+        domain& d,
+        range& r
+    )
+    {
+        unsigned long i = 0;
+        while (table[i].size() == 0)
+        {
+            ++i;
+        }
+        table[i].remove_any(d,r);
+        --hash_size;
+
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    const range* hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    operator[](
+        const domain& d
+    ) const
+    {
+        return table[hash(d)&mask][d];
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    range* hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    operator[](
+        const domain& d
+    )
+    {
+        return table[hash(d)&mask][d];
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    swap(
+        hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>& item
+    )
+    {
+        pool.swap(item.pool);
+        exchange(mask,item.mask);
+        exchange(hash_size,item.hash_size);
+        exchange(num_of_buckets,item.num_of_buckets);
+        exchange(table,item.table);
+        exchange(current_bucket,item.current_bucket);
+        exchange(at_start_,item.at_start_);        
+        exchange(comp,item.comp);
+    }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+    // enumerable function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    bool hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    at_start (
+    ) const
+    {
+        return at_start_;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    void hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    reset (
+    ) const
+    {
+        at_start_ = true;
+        if (current_bucket != 0)
+        {
+            current_bucket->reset();
+            current_bucket = 0;
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    bool hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    current_element_valid (
+    ) const
+    {
+        return (current_bucket != 0);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    const map_pair<domain,range>& hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    element (
+    ) const
+    {
+        return current_bucket->element();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    map_pair<domain,range>& hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    element (
+    )
+    {
+        return current_bucket->element();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename bst_base,
+        typename mem_manager,
+        typename compare
+        >
+    bool hash_table_kernel_2<domain,range,bst_base,mem_manager,compare>::
+    move_next (
+    ) const
+    {
+        if (at_start_)
+        {
+            at_start_ = false;
+            // if the queue is empty then there is nothing to do
+            if (hash_size == 0)
+            {
+                return false;
+            }
+            else
+            {
+                // find the first element in the hash table
+                current_bucket = table;
+                while (current_bucket->size() == 0)
+                {
+                    ++current_bucket;
+                }
+
+                current_bucket->move_next();
+                
+                return true;
+            }
+        }
+        else
+        {
+            // if we have already enumerated every element
+            if (current_bucket == 0)
+            {
+                return false;
+            }
+            else
+            {
+                if (current_bucket->move_next())
+                {
+                    // if there is another element in this current bucket then use that
+                    return true;
+                }
+                else
+                {
+                    // find the next bucket
+                    bst_base* end = table + num_of_buckets;
+                    current_bucket->reset();
+                    
+                    while (true)
+                    {   
+                        ++current_bucket;
+                        // if we ran out of buckets and didn't find anything
+                        if (current_bucket == end)
+                        {
+                            current_bucket = 0;
+                            return false;
+                        }
+                        if (current_bucket->size() > 0)
+                        {
+                            current_bucket->move_next();
+                            return true;
+                        }
+                    }
+                }
+            }
+        }
+    }
+    
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_HASH_TABLE_KERNEl_2_
+