Merging upstream version 1.44.3.

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

1 files changed, 1897 insertions, 0 deletions

diff --git a/ml/dlib/dlib/binary_search_tree/binary_search_tree_kernel_2.h b/ml/dlib/dlib/binary_search_tree/binary_search_tree_kernel_2.h
new file mode 100644
index 000000000..098d38c2e
--- /dev/null
+++ b/ml/dlib/dlib/binary_search_tree/binary_search_tree_kernel_2.h
@@ -0,0 +1,1897 @@
+// Copyright (C) 2003  Davis E. King (davis@dlib.net)
+// License: Boost Software License   See LICENSE.txt for the full license.
+#ifndef DLIB_BINARY_SEARCH_TREE_KERNEl_2_
+#define DLIB_BINARY_SEARCH_TREE_KERNEl_2_
+
+#include "binary_search_tree_kernel_abstract.h"
+#include "../algs.h"
+#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 mem_manager,
+        typename compare = std::less<domain>
+        >
+    class binary_search_tree_kernel_2 : public enumerable<map_pair<domain,range> >,
+                                        public asc_pair_remover<domain,range,compare>
+    {
+
+        /*!
+            INITIAL VALUE
+                NIL == pointer to a node that represents a leaf
+                tree_size == 0
+                tree_root == NIL     
+                at_start == true
+                current_element == 0
+
+
+            CONVENTION
+                current_element_valid() == (current_element != 0)
+                if (current_element_valid()) then
+                    element() == current_element->d and current_element->r
+                at_start_ == at_start()
+
+
+                tree_size   == size()
+
+                NIL == pointer to a node that represents a leaf
+
+                if (tree_size != 0)
+                    tree_root == pointer to the root node of the binary search tree
+                else
+                    tree_root == NIL
+
+                tree_root->color == black                    
+                Every leaf is black and all leafs are the NIL node.
+                The number of black nodes in any path from the root to a leaf is the 
+                same. 
+
+                for all nodes:
+                {
+                    - left points to the left subtree or NIL if there is no left subtree  
+                    - right points to the right subtree or NIL if there is no right 
+                      subtree                                                             
+                    - parent points to the parent node or NIL if the node is the root     
+                    - ordering of nodes is determined by comparing each node's d member  
+                    - all elements in a left subtree are <= the node                      
+                    - all elements in a right subtree are >= the node                     
+                    - color == red or black                                               
+                    - if (color == red)                                                   
+                        - the node's children are black
+                }
+
+        !*/
+    
+        class node
+        {
+        public:            
+            node* left;
+            node* right;
+            node* parent;
+            domain d;
+            range r;
+            char color;
+        };
+
+        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; }
+        };
+        
+     
+        const static char red = 0;
+        const static char black = 1;
+
+
+        public:
+
+            typedef domain domain_type;
+            typedef range range_type;
+            typedef compare compare_type;
+            typedef mem_manager mem_manager_type;
+
+            binary_search_tree_kernel_2(
+            ) :
+                NIL(pool.allocate()),
+                tree_size(0),
+                tree_root(NIL),
+                current_element(0),
+                at_start_(true)
+            {
+                NIL->color = black;
+                NIL->left = 0;
+                NIL->right = 0;
+                NIL->parent = 0;
+            }
+
+            virtual ~binary_search_tree_kernel_2(
+            ); 
+    
+            inline void clear(
+            );
+
+            inline short height (
+            ) const;
+
+            inline unsigned long count (
+                const domain& d
+            ) const;
+
+            inline void add (
+                domain& d,
+                range& r
+            );
+
+            void remove (
+                const domain& d,
+                domain& d_copy,
+                range& r
+            );
+
+            void destroy (
+                const domain& d
+            );
+
+            void remove_any (
+                domain& d,
+                range& r
+            );
+
+            inline const range* operator[] (
+                const domain& item
+            ) const;
+
+            inline range* operator[] (
+                const domain& item
+            );
+
+            inline void swap (
+                binary_search_tree_kernel_2& item
+            );
+
+            // functions from the enumerable interface
+            inline size_t size (
+            ) const;
+
+            bool at_start (
+            ) const;
+
+            inline void reset (
+            ) const;
+
+            bool current_element_valid (
+            ) const;
+
+            const map_pair<domain,range>& element (
+            ) const;
+
+            map_pair<domain,range>& element (
+            );
+
+            bool move_next (
+            ) const;
+
+            void remove_last_in_order (
+                domain& d,
+                range& r
+            );
+
+            void remove_current_element (
+                domain& d,
+                range& r
+            );
+
+            void position_enumerator (
+                const domain& d
+            ) const;
+
+        private:
+
+            inline void rotate_left (
+                node* t
+            );
+            /*!
+                requires
+                    - t != NIL 
+                    - t->right != NIL
+                ensures
+                    - performs a left rotation around t and its right child
+            !*/
+
+            inline void rotate_right (
+                node* t
+            );
+            /*!
+                requires
+                    - t != NIL 
+                    - t->left != NIL
+                ensures
+                    - performs a right rotation around t and its left child
+            !*/
+
+            inline void double_rotate_right (
+                node* t
+            );
+            /*!
+                requires
+                    - t != NIL 
+                    - t->left != NIL 
+                    - t->left->right != NIL 
+                    - double_rotate_right() is only called in fix_after_add()
+                ensures
+                    - performs a left rotation around t->left 
+                    - then performs a right rotation around t
+            !*/
+
+            inline void double_rotate_left (
+                node* t
+            );
+            /*!
+                requires
+                    - t != NIL 
+                    - t->right != NIL 
+                    - t->right->left != NIL 
+                    - double_rotate_left() is only called in fix_after_add()
+                ensures
+                    - performs a right rotation around t->right 
+                    - then performs a left rotation around t
+            !*/
+
+            void remove_biggest_element_in_tree (
+                node* t,
+                domain& d,
+                range& r
+            );
+            /*!
+                requires
+                    - t != NIL  (i.e. there must be something in the tree to remove)
+                ensures
+                    - the biggest node in t has been removed 
+                    - the biggest node element in t has been put into #d and #r 
+                    - #t is still a binary search tree 
+            !*/
+
+            bool remove_least_element_in_tree (
+                node* t,
+                domain& d,
+                range& r
+            );
+            /*!
+                requires
+                    - t != NIL  (i.e. there must be something in the tree to remove)
+                ensures
+                    - the least node in t has been removed 
+                    - the least node element in t has been put into #d and #r 
+                    - #t is still a binary search tree 
+                    - if (the node that was removed was the one pointed to by current_element) then
+                        - returns true
+                    - else
+                        - returns false
+            !*/
+
+            void add_to_tree (
+                node* t,
+                domain& d,
+                range& r
+            );
+            /*!
+                requires
+                    - t != NIL
+                ensures
+                    - d and r are now in #t
+                    - there is a mapping from d to r in #t
+                    - #d and #r have initial values for their types
+                    - #t is still a binary search tree 
+            !*/
+
+            void remove_from_tree (
+                node* t,
+                const domain& d,
+                domain& d_copy,
+                range& r
+            );
+            /*!
+                requires
+                    - return_reference(t,d) != 0
+                ensures
+                    - #d_copy is equivalent to d                                     
+                    - the first element in t equivalent to d that is encountered when searching down the tree
+                      from t has been removed and swapped into #d_copy.  Also, the associated range element 
+                      has been removed and swapped into #r.
+                    - if (the node that got removed wasn't current_element) then
+                        - adjusts the current_element pointer if the data in the node that it points to gets moved.
+                    - else
+                        - the value of current_element is now invalid
+                    - #t is still a binary search tree 
+            !*/
+
+            void remove_from_tree (
+                node* t,
+                const domain& d
+            );
+            /*!
+                requires
+                    - return_reference(t,d) != 0
+                ensures                                  
+                    - an element in t equivalent to d has been removed                
+                    - #t is still a binary search tree 
+            !*/
+
+            const range* return_reference (
+                const node* t,
+                const domain& d
+            ) const;
+            /*!
+                ensures
+                    - if (there is a domain element equivalent to d in t) then
+                        - returns a pointer to the element in the range equivalent to d
+                    - else
+                        - returns 0
+            !*/
+
+            range* return_reference (
+                node* t,
+                const domain& d
+            );
+            /*!
+                ensures
+                    - if (there is a domain element equivalent to d in t) then
+                        - returns a pointer to the element in the range equivalent to d
+                    - else
+                        - returns 0
+            !*/
+
+            void fix_after_add (
+                node* t
+            );
+            /*!
+                requires
+                    - t == pointer to the node just added
+                    - t->color == red 
+                    - t->parent != NIL (t must not be the root)
+                    - fix_after_add() is only called after a new node has been added
+                      to t
+                ensures
+                    - fixes any deviations from the CONVENTION caused by adding a node
+            !*/
+
+            void fix_after_remove (
+                node* t
+            );
+            /*!
+                requires
+                    - t == pointer to the only child of the node that was spliced out 
+                    - fix_after_remove() is only called after a node has been removed
+                      from t
+                    - the color of the spliced out node was black
+                ensures
+                    - fixes any deviations from the CONVENTION causes by removing a node
+            !*/            
+
+
+            short tree_height (
+                node* t
+            ) const;
+            /*!
+                ensures
+                    - returns the number of nodes in the longest path from the root of the 
+                      tree to a leaf
+            !*/
+
+            void delete_tree (
+                node* t
+            );
+            /*!
+                requires
+                    - t == root of binary search tree
+                    - t != NIL
+                ensures
+                    - deletes all nodes in t except for NIL
+            !*/
+
+            unsigned long get_count (
+                const domain& item,
+                node* tree_root
+            ) const;
+            /*!
+                requires
+                    - tree_root == the root of a binary search tree or NIL
+                ensures
+                    - if (tree_root == NIL) then
+                        - returns 0
+                    - else
+                        - returns the number of elements in tree_root that are 
+                          equivalent to item
+            !*/
+
+
+
+            // data members
+            typename mem_manager::template rebind<node>::other pool;
+            node* NIL;
+            unsigned long tree_size;
+            node* tree_root;
+            mutable node* current_element;
+            mutable bool at_start_;
+            mutable mpair p;
+            compare comp;
+
+            
+
+            // restricted functions
+            binary_search_tree_kernel_2(binary_search_tree_kernel_2&);        
+            binary_search_tree_kernel_2& operator=(binary_search_tree_kernel_2&);
+
+
+    };
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >   
+    inline void swap (
+        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& a, 
+        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& b 
+    ) { a.swap(b); }
+
+
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >   
+    void deserialize (
+        binary_search_tree_kernel_2<domain,range,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 binary_search_tree_kernel_2"); 
+        }
+    }
+
+
+
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+    // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    ~binary_search_tree_kernel_2 (
+    )
+    {     
+        if (tree_root != NIL)
+            delete_tree(tree_root);
+        pool.deallocate(NIL);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    clear (
+    )
+    {
+        if (tree_size > 0)
+        {
+            delete_tree(tree_root);
+            tree_root = NIL;
+            tree_size = 0;
+        }
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    size_t binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    size (
+    ) const
+    {
+        return tree_size;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    short binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    height (
+    ) const
+    {
+        return tree_height(tree_root);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    unsigned long binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    count (
+        const domain& item
+    ) const
+    {
+        return get_count(item,tree_root);        
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    add (
+        domain& d,
+        range& r
+    ) 
+    {
+        if (tree_size == 0)
+        {
+            tree_root = pool.allocate();
+            tree_root->color = black;
+            tree_root->left = NIL;
+            tree_root->right = NIL;
+            tree_root->parent = NIL;
+            exchange(tree_root->d,d);
+            exchange(tree_root->r,r);
+        }
+        else 
+        {
+            add_to_tree(tree_root,d,r);
+        }
+        ++tree_size;
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove (
+        const domain& d,
+        domain& d_copy,
+        range& r
+    ) 
+    {
+        remove_from_tree(tree_root,d,d_copy,r);
+        --tree_size;
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    destroy (
+        const domain& item
+    ) 
+    {
+        remove_from_tree(tree_root,item);
+        --tree_size;
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_any (
+        domain& d,
+        range& r
+    ) 
+    {
+        remove_least_element_in_tree(tree_root,d,r);
+        --tree_size;
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    operator[] (
+        const domain& d
+    ) 
+    {
+        return return_reference(tree_root,d);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    const range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    operator[] (
+        const domain& d
+    ) const
+    {
+        return return_reference(tree_root,d);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    swap (
+        binary_search_tree_kernel_2<domain,range,mem_manager,compare>& item
+    ) 
+    {
+        pool.swap(item.pool);
+        
+        exchange(p,item.p);
+        exchange(comp,item.comp);
+
+        node* tree_root_temp            = item.tree_root;
+        unsigned long tree_size_temp    = item.tree_size;
+        node* const NIL_temp            = item.NIL;
+        node* current_element_temp      = item.current_element;
+        bool at_start_temp              = item.at_start_;
+        
+        item.tree_root                  = tree_root;
+        item.tree_size                  = tree_size;
+        item.NIL                        = NIL;
+        item.current_element            = current_element;
+        item.at_start_                  = at_start_;
+        
+        tree_root                       = tree_root_temp;
+        tree_size                       = tree_size_temp;
+        NIL                             = NIL_temp;
+        current_element                 = current_element_temp;
+        at_start_                       = at_start_temp;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_last_in_order (
+        domain& d,
+        range& r
+    )
+    {
+        remove_biggest_element_in_tree(tree_root,d,r);
+        --tree_size;
+        // reset the enumerator
+        reset();
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_current_element (
+        domain& d,
+        range& r
+    )
+    {
+        node* t = current_element;
+        move_next();
+        remove_from_tree(t,t->d,d,r);
+        --tree_size;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    position_enumerator (
+        const domain& d
+    ) const
+    {
+        // clear the enumerator state and make sure the stack is empty
+        reset();
+        at_start_ = false;
+        node* t = tree_root;
+        node* parent = NIL;
+        bool went_left = false;
+        while (t != NIL)
+        {
+            if ( comp(d , t->d ))
+            {
+                // if item is on the left then look in left
+                parent = t;
+                t = t->left;
+                went_left = true;
+            }
+            else if (comp(t->d , d))
+            {
+                // if item is on the right then look in right
+                parent = t;
+                t = t->right;
+                went_left = false;
+            }
+            else
+            {
+                current_element = t;
+                return;
+            }
+        }
+
+        // if we didn't find any matches but there might be something after the
+        // d in this tree.
+        if (parent != NIL)
+        {
+            current_element = parent;
+            // if we went left from this node then this node is the next
+            // biggest.
+            if (went_left)
+            {
+                return;
+            }
+            else
+            {
+                move_next();
+            }
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+    // enumerable function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    at_start (
+    ) const
+    {
+        return at_start_;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    reset (
+    ) const
+    {
+        at_start_ = true;
+        current_element = 0;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    current_element_valid (
+    ) const
+    {
+        return (current_element != 0);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    const map_pair<domain,range>& binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    element (
+    ) const
+    {
+        p.d = &(current_element->d);
+        p.r = &(current_element->r);
+        return p;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    map_pair<domain,range>& binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    element (
+    )
+    {
+        p.d = &(current_element->d);
+        p.r = &(current_element->r);
+        return p;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    move_next (
+    ) const
+    {
+        // if we haven't started iterating yet
+        if (at_start_)
+        {
+            at_start_ = false;
+            if (tree_size == 0)
+            {
+                return false;
+            }
+            else
+            {
+                // find the first element in the tree
+                current_element = tree_root;
+                node* temp = current_element->left;
+                while (temp != NIL)
+                {
+                    current_element = temp;
+                    temp = current_element->left;
+                }
+                return true;
+            }
+        }
+        else
+        {
+            if (current_element == 0)
+            {
+                return false;
+            }
+            else
+            {
+                bool went_up;  // true if we went up the tree from a child node to parent
+                bool from_left = false; // true if we went up and were coming from a left child node
+                // find the next element in the tree
+                if (current_element->right != NIL)
+                {
+                    // go right and down                    
+                    current_element = current_element->right;
+                    went_up = false;
+                }
+                else
+                {
+                    went_up = true;
+                    node* parent = current_element->parent;
+                    if (parent == NIL)
+                    {
+                        // in this case we have iterated over all the element of the tree
+                        current_element = 0;
+                        return false;
+                    }
+
+                    from_left = (parent->left == current_element);
+                    // go up to parent
+                    current_element = parent;
+                }
+
+
+                while (true)
+                {
+                    if (went_up)
+                    {
+                        if (from_left)
+                        {
+                            // in this case we have found the next node
+                            break;
+                        }
+                        else
+                        {
+                            // we should go up
+                            node* parent = current_element->parent;
+                            from_left = (parent->left == current_element);                            
+                            current_element = parent;
+                            if (current_element == NIL)
+                            {
+                                // in this case we have iterated over all the elements
+                                // in the tree
+                                current_element = 0;
+                                return false;
+                            }
+                        }
+                    }
+                    else
+                    {
+                        // we just went down to a child node
+                        if (current_element->left != NIL)
+                        {
+                            // go left
+                            went_up = false;
+                            current_element = current_element->left;
+                        }
+                        else
+                        {
+                            // if there is no left child then we have found the next node
+                            break;
+                        }
+                    }
+                }
+
+                return true;               
+            }
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+    // private member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    delete_tree (
+        node* t
+    )  
+    {
+        if (t->left != NIL)
+            delete_tree(t->left);
+        if (t->right != NIL)
+            delete_tree(t->right);
+        pool.deallocate(t);
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    rotate_left (
+        node* t
+    ) 
+    {
+
+        // perform the rotation
+        node* temp = t->right;
+        t->right = temp->left;
+        if (temp->left != NIL)
+            temp->left->parent = t;
+        temp->left = t;
+        temp->parent = t->parent;
+
+
+        if (t == tree_root)
+            tree_root = temp;
+        else 
+        {
+            // if t was on the left
+            if (t->parent->left == t)
+                t->parent->left = temp;
+            else
+                t->parent->right = temp;
+        }
+
+        t->parent = temp;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    rotate_right (
+        node* t
+    ) 
+    {
+        // perform the rotation
+        node* temp = t->left;
+        t->left = temp->right;
+        if (temp->right != NIL)
+            temp->right->parent = t;
+        temp->right = t;
+        temp->parent = t->parent;
+
+        if (t == tree_root)
+            tree_root = temp;
+        else 
+        {
+            // if t is a left child
+            if (t->parent->left == t)
+                t->parent->left = temp;
+            else
+                t->parent->right = temp;
+        }
+
+        t->parent = temp;
+    }
+
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    double_rotate_right (
+        node* t
+    )
+    {
+
+        // preform the rotation
+        node& temp = *(t->left->right);
+        t->left = temp.right;
+        temp.right->parent = t;
+        temp.left->parent = temp.parent;
+        temp.parent->right = temp.left;
+        temp.parent->parent = &temp;
+        temp.right = t;
+        temp.left = temp.parent;
+        temp.parent = t->parent;  
+
+
+        if (tree_root == t)
+            tree_root = &temp;
+        else
+        {
+            // t is a left child
+            if (t->parent->left == t)
+                t->parent->left = &temp;
+            else
+                t->parent->right = &temp;
+        }
+        t->parent = &temp;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    double_rotate_left (
+        node* t
+    )
+    {
+
+
+        // preform the rotation
+        node& temp = *(t->right->left);
+        t->right = temp.left;
+        temp.left->parent = t;
+        temp.right->parent = temp.parent;
+        temp.parent->left = temp.right;
+        temp.parent->parent = &temp;
+        temp.left = t;
+        temp.right = temp.parent;
+        temp.parent = t->parent;  
+
+
+        if (tree_root == t)
+            tree_root = &temp;
+        else
+        {
+            // t is a left child
+            if (t->parent->left == t)
+                t->parent->left = &temp;
+            else
+                t->parent->right = &temp;
+        }
+        t->parent = &temp;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_biggest_element_in_tree (
+        node* t,
+        domain& d,
+        range& r
+    ) 
+    {
+
+        node* next = t->right;
+        node* child;  // the child node of the one we will slice out
+
+        if (next == NIL)
+        {
+            // need to determine if t is a right or left child
+            if (t->parent->right == t)
+                child = t->parent->right = t->left;
+            else
+                child = t->parent->left = t->left;
+
+            // update tree_root if necessary
+            if (t == tree_root)
+                tree_root = child;
+        }
+        else
+        {
+            // find the least node
+            do 
+            {
+                t = next;
+                next = next->right;
+            } while (next != NIL);
+            // t is a right child
+            child = t->parent->right = t->left;
+
+        }
+        
+        // swap the item from this node into d and r
+        exchange(d,t->d);
+        exchange(r,t->r);
+
+        // plug hole right by removing this node
+        child->parent = t->parent;
+
+        // keep the red-black properties true
+        if (t->color == black)
+            fix_after_remove(child);
+
+        // free the memory for this removed node
+        pool.deallocate(t);        
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    bool binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_least_element_in_tree (
+        node* t,
+        domain& d,
+        range& r
+    ) 
+    {
+
+        node* next = t->left;
+        node* child;  // the child node of the one we will slice out
+
+        if (next == NIL)
+        {
+            // need to determine if t is a left or right child
+            if (t->parent->left == t)
+                child = t->parent->left = t->right;
+            else
+                child = t->parent->right = t->right;
+
+            // update tree_root if necessary
+            if (t == tree_root)
+                tree_root = child;
+        }
+        else
+        {
+            // find the least node
+            do 
+            {
+                t = next;
+                next = next->left;
+            } while (next != NIL);
+            // t is a left child
+            child = t->parent->left = t->right;
+
+        }
+        
+        // swap the item from this node into d and r
+        exchange(d,t->d);
+        exchange(r,t->r);
+
+        // plug hole left by removing this node
+        child->parent = t->parent;
+
+        // keep the red-black properties true
+        if (t->color == black)
+            fix_after_remove(child);
+
+        bool rvalue = (t == current_element);
+        // free the memory for this removed node
+        pool.deallocate(t);        
+        return rvalue;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    add_to_tree (
+        node* t,
+        domain& d,
+        range& r
+    ) 
+    {
+        // parent of the current node
+        node* parent;
+
+        // find a place to add node
+        while (true)
+        {
+            parent = t;
+            // if item should be put on the left then go left
+            if (comp(d , t->d))
+            {
+                t = t->left;
+                if (t == NIL)
+                {
+                    t = parent->left = pool.allocate();
+                    break;
+                }
+            }
+            // if item should be put on the right then go right
+            else
+            {
+                t = t->right;
+                if (t == NIL)
+                {
+                    t = parent->right = pool.allocate();
+                    break;
+                }
+            }
+        }
+
+        // t is now the node where we will add item and
+        // parent is the parent of t
+
+        t->parent = parent;
+        t->left = NIL;
+        t->right = NIL;
+        t->color = red;
+        exchange(t->d,d);
+        exchange(t->r,r);
+
+
+        // keep the red-black properties true
+        fix_after_add(t);
+    } 
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_from_tree (
+        node* t,
+        const domain& d,
+        domain& d_copy,
+        range& r
+    ) 
+    {
+        while (true)
+        {
+            if ( comp(d , t->d) )
+            {
+                // if item is on the left then look in left
+                t = t->left;
+            }
+            else if (comp(t->d , d))
+            {
+                // if item is on the right then look in right
+                t = t->right;
+            }
+            else
+            {
+                // found the node we want to remove
+
+                // swap out the item into d_copy and r
+                exchange(d_copy,t->d);
+                exchange(r,t->r);
+
+                if (t->left == NIL)
+                {
+                    // if there is no left subtree
+
+                    node* parent = t->parent;
+                    
+                    // plug hole with right subtree
+
+
+                    // if t is on the left
+                    if (parent->left == t)
+                        parent->left = t->right;  
+                    else
+                        parent->right = t->right;
+                    t->right->parent = parent;
+
+                    // update tree_root if necessary
+                    if (t == tree_root)
+                        tree_root = t->right;
+
+                    if (t->color == black)
+                        fix_after_remove(t->right);
+
+                    // delete old node
+                    pool.deallocate(t);  
+                }
+                else if (t->right == NIL)
+                {
+                    // if there is no right subtree
+
+                    node* parent = t->parent;
+                    
+                    // plug hole with left subtree
+                    if (parent->left == t)
+                        parent->left = t->left;  
+                    else
+                        parent->right = t->left;
+                    t->left->parent = parent;
+
+                    // update tree_root if necessary
+                    if (t == tree_root)
+                        tree_root = t->left;
+
+                    if (t->color == black)
+                        fix_after_remove(t->left);
+
+                    // delete old node
+                    pool.deallocate(t);
+                }
+                else
+                {
+                    // if there is both a left and right subtree
+                    // get an element to fill this node now that its been swapped into 
+                    // item_copy
+                    if (remove_least_element_in_tree(t->right,t->d,t->r))
+                    {
+                        // the node removed was the one pointed to by current_element so we
+                        // need to update it so that it points to the right spot.
+                        current_element = t;
+                    }
+                }
+
+                // quit loop
+                break;
+            }
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    remove_from_tree (
+        node* t,
+        const domain& d
+    ) 
+    {
+        while (true)
+        {
+            if ( comp(d , t->d) )
+            {
+                // if item is on the left then look in left
+                t = t->left;
+            }
+            else if (comp(t->d , d))
+            {
+                // if item is on the right then look in right
+                t = t->right;
+            }
+            else
+            {
+                // found the node we want to remove
+
+
+                if (t->left == NIL)
+                {
+                    // if there is no left subtree
+
+                    node* parent = t->parent;
+                    
+                    // plug hole with right subtree
+
+
+                    if (parent->left == t)
+                        parent->left = t->right;  
+                    else
+                        parent->right = t->right;
+                    t->right->parent = parent;
+
+                    // update tree_root if necessary
+                    if (t == tree_root)
+                        tree_root = t->right;
+
+                    if (t->color == black)
+                        fix_after_remove(t->right);
+
+                    // delete old node
+                    pool.deallocate(t);  
+                }
+                else if (t->right == NIL)
+                {
+                    // if there is no right subtree
+
+                    node* parent = t->parent;
+                    
+                    // plug hole with left subtree
+                    if (parent->left == t)
+                        parent->left = t->left;  
+                    else
+                        parent->right = t->left;
+                    t->left->parent = parent;
+
+                    // update tree_root if necessary
+                    if (t == tree_root)
+                        tree_root = t->left;
+
+                    if (t->color == black)
+                        fix_after_remove(t->left);
+
+                    // delete old node
+                    pool.deallocate(t);
+                }
+                else
+                {
+                    // if there is both a left and right subtree
+                    // get an element to fill this node now that its been swapped into 
+                    // item_copy
+                    remove_least_element_in_tree(t->right,t->d,t->r);
+
+                }
+
+                // quit loop
+                break;
+            }
+        }
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    return_reference (
+        node* t,
+        const domain& d
+    ) 
+    {
+        while (t != NIL)
+        {
+            if ( comp(d , t->d ))
+            {
+                // if item is on the left then look in left
+                t = t->left;
+            }
+            else if (comp(t->d , d))
+            {
+                // if item is on the right then look in right
+                t = t->right;
+            }
+            else
+            {
+                // if it's found then return a reference to it
+                return &(t->r);
+            }
+        }
+        return 0;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    const range* binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    return_reference (
+        const node* t,
+        const domain& d
+    ) const
+    {
+        while (t != NIL)
+        {
+            if ( comp(d , t->d) )
+            {
+                // if item is on the left then look in left
+                t = t->left;
+            }
+            else if (comp(t->d , d))
+            {
+                // if item is on the right then look in right
+                t = t->right;
+            }
+            else
+            {
+                // if it's found then return a reference to it
+                return &(t->r);
+            }
+        }
+        return 0;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    fix_after_add (
+        node* t
+    )
+    {
+
+        while (t->parent->color == red)
+        {
+            node& grandparent = *(t->parent->parent);
+
+            // if both t's parent and its sibling are red 
+            if (grandparent.left->color == grandparent.right->color)
+            {
+                grandparent.color = red;
+                grandparent.left->color = black;
+                grandparent.right->color = black;
+                t = &grandparent;
+            }
+            else
+            {
+                // if t is a left child
+                if (t == t->parent->left)
+                {
+                    // if t's parent is a left child
+                    if (t->parent == grandparent.left)
+                    {
+                        grandparent.color = red;
+                        grandparent.left->color = black;
+                        rotate_right(&grandparent);
+                    }
+                    // if t's parent is a right child
+                    else
+                    {
+                        t->color = black;
+                        grandparent.color = red;
+                        double_rotate_left(&grandparent);
+                    }
+                }
+                // if t is a right child
+                else
+                {
+                    // if t's parent is a left child
+                    if (t->parent == grandparent.left)
+                    {
+                        t->color = black;
+                        grandparent.color = red;                        
+                        double_rotate_right(&grandparent);
+                    }
+                    // if t's parent is a right child
+                    else
+                    {
+                        grandparent.color = red;
+                        grandparent.right->color = black;
+                        rotate_left(&grandparent);
+                    }
+                }
+                break;
+            }
+        }
+        tree_root->color = black;
+    }       
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    void binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    fix_after_remove (
+        node* t
+    )
+    {
+
+        while (t != tree_root && t->color == black)
+        {
+            if (t->parent->left == t)
+            {
+                node* sibling = t->parent->right;
+                if (sibling->color == red)
+                {
+                    sibling->color = black;
+                    t->parent->color = red;
+                    rotate_left(t->parent);
+                    sibling = t->parent->right;
+                }
+
+                if (sibling->left->color == black && sibling->right->color == black)
+                {
+                    sibling->color = red;
+                    t = t->parent;
+                }
+                else
+                {
+                    if (sibling->right->color == black)
+                    {
+                        sibling->left->color = black;
+                        sibling->color = red;
+                        rotate_right(sibling);
+                        sibling = t->parent->right;
+                    }
+
+                    sibling->color = t->parent->color;
+                    t->parent->color = black;
+                    sibling->right->color = black;
+                    rotate_left(t->parent);
+                    t = tree_root;
+
+                }
+
+
+            }
+            else
+            {
+
+                node* sibling = t->parent->left;
+                if (sibling->color == red)
+                {
+                    sibling->color = black;
+                    t->parent->color = red;
+                    rotate_right(t->parent);
+                    sibling = t->parent->left;
+                }
+
+                if (sibling->left->color == black && sibling->right->color == black)
+                {
+                    sibling->color = red;
+                    t = t->parent;
+                }
+                else
+                {
+                    if (sibling->left->color == black)
+                    {
+                        sibling->right->color = black;
+                        sibling->color = red;
+                        rotate_left(sibling);
+                        sibling = t->parent->left;
+                    }
+
+                    sibling->color = t->parent->color;
+                    t->parent->color = black;
+                    sibling->left->color = black;
+                    rotate_right(t->parent);
+                    t = tree_root;
+
+                }
+
+
+            }
+
+        }
+        t->color = black;
+    
+    }         
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    short binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    tree_height (
+        node* t
+    ) const
+    {
+        if (t == NIL)
+            return 0;
+
+        short height1 = tree_height(t->left);
+        short height2 = tree_height(t->right);        
+        if (height1 > height2)
+            return height1 + 1;
+        else
+            return height2 + 1;
+    }       
+
+// ----------------------------------------------------------------------------------------
+
+    template <
+        typename domain,
+        typename range,
+        typename mem_manager,
+        typename compare
+        >
+    unsigned long binary_search_tree_kernel_2<domain,range,mem_manager,compare>::
+    get_count (
+        const domain& d,
+        node* tree_root
+    ) const
+    {
+        if (tree_root != NIL)
+        {
+            if (comp(d , tree_root->d))
+            {
+                // go left
+                return get_count(d,tree_root->left);                
+            }
+            else if (comp(tree_root->d , d))
+            {
+                // go right
+                return get_count(d,tree_root->right);
+            }
+            else
+            {
+                // go left and right to look for more matches
+                return   get_count(d,tree_root->left) 
+                       + get_count(d,tree_root->right) 
+                       + 1;
+            }
+        }
+        return 0;
+    }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_BINARY_SEARCH_TREE_KERNEl_2_
+