// 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_1_
#define DLIB_BINARY_SEARCH_TREE_KERNEl_1_

#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 <cstdlib>
#include <functional>

namespace dlib 
{

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare = std::less<domain>
        >
    class binary_search_tree_kernel_1 : public enumerable<map_pair<domain,range> >,
                                        public asc_pair_remover<domain,range,compare>
    {

        /*!
            INITIAL VALUE
                tree_size == 0
                tree_root == 0
                tree_height == 0
                at_start_ == true
                current_element == 0
                stack == array of 50 node pointers
                stack_pos == 0


            CONVENTION
                tree_size   == size()
                tree_height == height()

                stack[stack_pos-1] == pop()

                current_element_valid() == (current_element != 0)
                if (current_element_valid()) then
                    element() == current_element->d and current_element->r
                at_start_ == at_start()
                if (current_element != 0 && current_element != tree_root) then
                    stack[stack_pos-1] == the parent of the node pointed to by current_element

                if (tree_size != 0)
                    tree_root == pointer to the root node of the binary search tree
                else
                    tree_root == 0


                for all nodes:
                {
                    left points to the left subtree or 0 if there is no left subtree and
                    right points to the right subtree or 0 if there is no right subtree and
                    all elements in a left subtree are <= the root and
                    all elements in a right subtree are >= the root and
                    d is the item in the domain of *this contained in the node
                    r is the item in the range of *this contained in the node
                    balance:
                        balance == 0 if both subtrees have the same height
                        balance == -1 if the left subtree has a height that is greater 
                                   than the height of the right subtree by 1
                        balance == 1 if the right subtree has a height that is greater 
                                   than the height of the left subtree by 1
                    for all trees:
                        the height of the left and right subtrees differ by at most one
                }

        !*/
    
        class node
        {
        public:
            node* left;
            node* right;
            domain d;
            range r;
            signed char balance;
        };

        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; }
        };

   
        public:

            typedef domain domain_type;
            typedef range range_type;
            typedef compare compare_type;
            typedef mem_manager mem_manager_type;

            binary_search_tree_kernel_1(
            ) :
                tree_size(0),
                tree_root(0),
                current_element(0),
                tree_height(0),
                at_start_(true),
                stack_pos(0),
                stack(ppool.allocate_array(50))
            {
            }

            virtual ~binary_search_tree_kernel_1(
            ); 
    
            inline void clear(
            );

            inline short height (
            ) const;

            inline unsigned long count (
                const domain& item
            ) const;

            inline void add (
                domain& d,
                range& r
            );

            void remove (
                const domain& d,
                domain& d_copy,
                range& r
            );

            void destroy (
                const domain& item
            );

            inline const range* operator[] (
                const domain& item
            ) const;

            inline range* operator[] (
                const domain& item
            );

            inline void swap (
                binary_search_tree_kernel_1& item
            );

            // function from the asc_pair_remover interface
            void remove_any (
                domain& d,
                range& r
            );

            // 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->balance == 2 
                    - t->right->balance == 0 or 1 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - #t is still a binary search tree 
                    - #t->balance is between 1 and -1 
                    - #t now has a height smaller by 1 if #t->balance == 0
            !*/

            inline void rotate_right (
                node*& t
            );
            /*!
                requires
                    - t->balance == -2 
                    - t->left->balance == 0 or -1 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - #t is still a binary search tree 
                    - #t->balance is between 1 and -1 
                    - #t now has a height smaller by 1 if #t->balance == 0

            !*/

            inline void double_rotate_right (
                node*& t
            );
            /*!
                requires
                    - t->balance == -2 
                    - t->left->balance == 1 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - #t is still a binary search tree 
                    - #t now has a balance of 0 
                    - #t now has a height smaller by 1             
            !*/

            inline void double_rotate_left (
                node*& t
            );
            /*!
                requires
                    - t->balance == 2 
                    - t->right->balance == -1 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - #t is still a binary search tree 
                    - #t now has a balance of 0 
                    - #t now has a height smaller by 1
            !*/

            bool remove_biggest_element_in_tree (
                node*& t,
                domain& d,
                range& r
            );
            /*!
                requires
                    - t != 0  (i.e. there must be something in the tree to remove) 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - the biggest node in t has been removed 
                    - the biggest node domain element in t has been put into #d 
                    - the biggest node range element in t has been put into #r
                    - #t is still a binary search tree 
                    - returns false if the height of the tree has not changed 
                    - returns true if the height of the tree has shrunk by one
            !*/

            bool remove_least_element_in_tree (
                node*& t,
                domain& d,
                range& r
            );
            /*!
                requires
                    - t != 0  (i.e. there must be something in the tree to remove) 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - the least node in t has been removed 
                    - the least node domain element in t has been put into #d 
                    - the least node range element in t has been put into #r
                    - #t is still a binary search tree 
                    - returns false if the height of the tree has not changed 
                    - returns true if the height of the tree has shrunk by one
            !*/

            bool add_to_tree (
                node*& t,
                domain& d,
                range& r
            );
            /*!
                requires
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - the mapping (d --> r) has been added to #t 
                    - #d and #r have initial values for their types
                    - #t is still a binary search tree 
                    - returns false if the height of the tree has not changed 
                    - returns true if the height of the tree has grown by one
            !*/

            bool remove_from_tree (
                node*& t,
                const domain& d,
                domain& d_copy,
                range& r
            );
            /*!
                requires
                    - return_reference(t,d) != 0
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - #d_copy is equivalent to d                                    
                    - an element in t equivalent to d has been removed and swapped 
                      into #d_copy and its associated range object has been 
                      swapped into #r
                    - #t is still a binary search tree                                     
                    - returns false if the height of the tree has not changed 
                    - returns true if the height of the tree has shrunk by one
            !*/

            bool remove_from_tree (
                node*& t,
                const domain& item
            );
            /*!
                requires
                    - return_reference(t,item) != 0
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - an element in t equivalent to item has been removed                      
                    - #t is still a binary search tree                                     
                    - returns false if the height of the tree has not changed 
                    - returns true if the height of the tree has shrunk by one
            !*/

            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
            !*/


            inline bool keep_node_balanced (
                node*& t
            );
            /*!
                requires
                    - t != 0 
                    - t == reference to the pointer in t's parent node that points to t
                ensures
                    - if (t->balance is < 1 or > 1) then 
                        - keep_node_balanced() will ensure that #t->balance == 0, -1, or 1
                    - #t is still a binary search tree
                    - returns true if it made the tree one height shorter 
                    - returns false if it didn't change the height
            !*/


            unsigned long get_count (
                const domain& item,
                node* tree_root
            ) const;
            /*!
                requires
                    - tree_root == the root of a binary search tree or 0
                ensures
                    - if (tree_root == 0) then
                        - returns 0
                    - else
                        - returns the number of elements in tree_root that are 
                          equivalent to item
            !*/


            void delete_tree (
                node* t
            );
            /*!
                requires
                    - t != 0
                ensures
                    - deallocates the node pointed to by t and all of t's left and right children
            !*/


            void push (
                node* n
            ) const { stack[stack_pos] = n; ++stack_pos; }
            /*!
                ensures
                    - pushes n onto the stack
            !*/
            

            node* pop (
            ) const { --stack_pos; return stack[stack_pos]; }
            /*!
                ensures
                    - pops the top of the stack and returns it
            !*/



            bool fix_stack (
                node* t,
                unsigned char depth = 0
            );
            /*!
                requires
                    - current_element != 0
                    - depth == 0
                    - t == tree_root
                ensures
                    - makes the stack contain the correct set of parent pointers.
                      also adjusts stack_pos so it is correct.
                    - #t is still a binary search tree                                     
            !*/

            bool remove_current_element_from_tree (
                node*& t,
                domain& d,
                range& r,
                unsigned long cur_stack_pos = 1
            ); 
            /*!
                requires
                    - t == tree_root
                    - cur_stack_pos == 1
                    - current_element != 0
                ensures
                    - removes the data in the node given by current_element and swaps it into 
                      #d and #r.  
                    - #t is still a binary search tree                                     
                    - the enumerator is advances on to the next element but its stack is 
                      potentially corrupted.  so you must call fix_stack(tree_root) to fix
                      it.
                    - returns false if the height of the tree has not changed 
                    - returns true if the height of the tree has shrunk by one
            !*/


            // data members

            mutable mpair p;
            unsigned long tree_size;            
            node* tree_root;
            mutable node* current_element;            
            typename mem_manager::template rebind<node>::other pool;
            typename mem_manager::template rebind<node*>::other ppool;
            short tree_height;
            mutable bool at_start_;
            mutable unsigned char stack_pos;
            mutable node** stack;
            compare comp; 

            // restricted functions
            binary_search_tree_kernel_1(binary_search_tree_kernel_1&);        
            binary_search_tree_kernel_1& operator=(binary_search_tree_kernel_1&); 


    };

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    inline void swap (
        binary_search_tree_kernel_1<domain,range,mem_manager,compare>& a, 
        binary_search_tree_kernel_1<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_1<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_1"); 
        }
    }



// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    ~binary_search_tree_kernel_1 (
    )
    {
        ppool.deallocate_array(stack);
        if (tree_size != 0)
        {
            delete_tree(tree_root);
        }        
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    void binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    clear (
    )
    {
        if (tree_size > 0)
        {
            delete_tree(tree_root);
            tree_root = 0;
            tree_size = 0;
            tree_height = 0;
        }
        // reset the enumerator
        reset();
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    size_t binary_search_tree_kernel_1<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_1<domain,range,mem_manager,compare>::
    height (
    ) const
    {
        return tree_height;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    unsigned long binary_search_tree_kernel_1<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_1<domain,range,mem_manager,compare>::
    add (
        domain& d,
        range& r
    ) 
    {
        tree_height += 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_1<domain,range,mem_manager,compare>::
    remove (
        const domain& d,
        domain& d_copy,
        range& r
    ) 
    {
        tree_height -= 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_1<domain,range,mem_manager,compare>::
    destroy (
        const domain& item
    ) 
    {
        tree_height -= 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_1<domain,range,mem_manager,compare>::
    remove_any (
        domain& d,
        range& r
    ) 
    {
        tree_height -= 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_1<domain,range,mem_manager,compare>::
    operator[] (
        const domain& item
    ) 
    {
        return return_reference(tree_root,item);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    const range* binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    operator[] (
        const domain& item
    ) const
    {
        return return_reference(tree_root,item);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    void binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    swap (
        binary_search_tree_kernel_1<domain,range,mem_manager,compare>& item
    ) 
    {
        pool.swap(item.pool);
        ppool.swap(item.ppool);
        exchange(p,item.p);
        exchange(stack,item.stack);
        exchange(stack_pos,item.stack_pos);
        exchange(comp,item.comp);
        

        node* tree_root_temp            = item.tree_root;
        unsigned long tree_size_temp    = item.tree_size;
        short tree_height_temp          = item.tree_height;
        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.tree_height = tree_height;
        item.current_element = current_element;
        item.at_start_   = at_start_;

        tree_root   = tree_root_temp;
        tree_size   = tree_size_temp;
        tree_height = tree_height_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_1<domain,range,mem_manager,compare>::
    remove_last_in_order (
        domain& d,
        range& r
    )
    {
        tree_height -= 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_1<domain,range,mem_manager,compare>::
    remove_current_element (
        domain& d,
        range& r
    )
    {
        tree_height -= remove_current_element_from_tree(tree_root,d,r);
        --tree_size;

        // fix the enumerator stack if we need to
        if (current_element)
            fix_stack(tree_root);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >
    void binary_search_tree_kernel_1<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;
        bool went_left = false;
        while (t != 0)
        {
            if ( comp(d , t->d) )
            {
                push(t);
                // if item is on the left then look in left
                t = t->left;
                went_left = true;
            }
            else if (comp(t->d , d))
            {
                push(t);
                // if item is on the right then look in right
                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 (stack_pos > 0)
        {
            current_element = pop();
            // 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_1<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_1<domain,range,mem_manager,compare>::
    reset (
    ) const
    {
        at_start_ = true;
        current_element = 0;
        stack_pos = 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<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_1<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_1<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_1<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 != 0)
                {
                    push(current_element);
                    current_element = temp;
                    temp = current_element->left;
                }
                return true;
            }
        }
        else
        {
            if (current_element == 0)
            {
                return false;
            }
            else
            {
                node* temp;
                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 != 0)
                {
                    // go right and down    
                    temp = current_element;
                    push(current_element);
                    current_element = temp->right;
                    went_up = false;
                }
                else
                {
                    // go up to the parent if we can
                    if (current_element == tree_root)
                    {
                        // in this case we have iterated over all the element of the tree
                        current_element = 0;
                        return false;
                    }
                    went_up = true;
                    node* parent = pop();


                    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
                        {
                            if (current_element == tree_root)
                            {
                                // in this case we have iterated over all the elements
                                // in the tree
                                current_element = 0;
                                return false;
                            }
                            // we should go up
                            node* parent = pop();
                            from_left = (parent->left == current_element);                            
                            current_element = parent;
                        }
                    }
                    else
                    {
                        // we just went down to a child node
                        if (current_element->left != 0)
                        {
                            // go left
                            went_up = false;
                            temp = current_element;
                            push(current_element);
                            current_element = temp->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_1<domain,range,mem_manager,compare>::
    delete_tree (
        node* t
    ) 
    {
        if (t->left != 0)
            delete_tree(t->left);
        if (t->right != 0)
            delete_tree(t->right);
        pool.deallocate(t);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    void binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    rotate_left (
        node*& t
    ) 
    {

        // set the new balance numbers
        if (t->right->balance == 1)
        {
            t->balance = 0;
            t->right->balance = 0;
        }
        else
        {
            t->balance = 1;
            t->right->balance = -1;            
        }

        // perform the rotation
        node* temp = t->right;
        t->right = temp->left;
        temp->left = t;
        t = temp;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    void binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    rotate_right (
        node*& t
    ) 
    {
        // set the new balance numbers
        if (t->left->balance == -1)
        {
            t->balance = 0;
            t->left->balance = 0;
        }
        else
        {
            t->balance = -1;
            t->left->balance = 1;            
        }

        // preform the rotation
        node* temp = t->left;
        t->left = temp->right;
        temp->right = t;
        t = temp;    

    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    void binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    double_rotate_right (
        node*& t
    )
    {

        node* temp = t;
        t = t->left->right;
        
        temp->left->right = t->left;
        t->left = temp->left;

        temp->left = t->right;
        t->right = temp;

        if (t->balance < 0)
        {  
            t->left->balance = 0;
            t->right->balance = 1;
        }
        else if (t->balance > 0)
        {
            t->left->balance = -1;
            t->right->balance = 0;
        }
        else 
        {
            t->left->balance = 0;
            t->right->balance = 0;
        }
        t->balance = 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    void binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    double_rotate_left (
        node*& t
    )
    {
        node* temp = t;
        t = t->right->left;
        
        temp->right->left = t->right;
        t->right = temp->right;

        temp->right = t->left;
        t->left = temp;

        if (t->balance < 0)
        {  
            t->left->balance = 0;
            t->right->balance = 1;
        }
        else if (t->balance > 0)
        {
            t->left->balance = -1;
            t->right->balance = 0;
        }
        else 
        {
            t->left->balance = 0;
            t->right->balance = 0;
        }

        t->balance = 0;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    remove_biggest_element_in_tree (
        node*& t,
        domain& d,
        range& r
    ) 
    {
        // make a reference to the current node so we don't have to dereference a 
        // pointer a bunch of times
        node& tree = *t;

        // if the right tree is an empty tree
        if ( tree.right == 0)
        {
            // swap nodes domain and range elements into d and r
            exchange(d,tree.d);
            exchange(r,tree.r);

            // plug hole left by removing this node
            t = tree.left;

            // delete the node that was just removed
            pool.deallocate(&tree);    

            // return that the height of this part of the tree has decreased
            return true;
        }
        else
        {

            // keep going right

            // if remove made the tree one height shorter
            if ( remove_biggest_element_in_tree(tree.right,d,r) ) 
            {
                // if this caused the current tree to strink then report that
                if ( tree.balance == 1)
                {
                    --tree.balance;
                    return true;
                }
                else
                {
                    --tree.balance;
                    return keep_node_balanced(t);
                }                
            }

            return false;            
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    remove_least_element_in_tree (
        node*& t,
        domain& d,
        range& r
    ) 
    {
        // make a reference to the current node so we don't have to dereference a 
        // pointer a bunch of times
        node& tree = *t;

        // if the left tree is an empty tree
        if ( tree.left == 0)
        {
            // swap nodes domain and range elements into d and r
            exchange(d,tree.d);
            exchange(r,tree.r);

            // plug hole left by removing this node
            t = tree.right;

            // delete the node that was just removed
            pool.deallocate(&tree);    

            // return that the height of this part of the tree has decreased
            return true;
        }
        else
        {

            // keep going left

            // if remove made the tree one height shorter
            if ( remove_least_element_in_tree(tree.left,d,r) ) 
            {
                // if this caused the current tree to strink then report that
                if ( tree.balance == -1)
                {
                    ++tree.balance;
                    return true;
                }
                else
                {
                    ++tree.balance;
                    return keep_node_balanced(t);
                }                
            }

            return false;            
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    add_to_tree (
        node*& t,
        domain& d,
        range& r
    ) 
    {

        // if found place to add
        if (t == 0)
        {
            // create a node to add new item into
            t = pool.allocate(); 

            // make a reference to the current node so we don't have to dereference a 
            // pointer a bunch of times
            node& tree = *t;


            // set left and right pointers to NULL to indicate that there are no 
            // left or right subtrees
            tree.left = 0;
            tree.right = 0;
            tree.balance = 0;

            // put d and r into t
            exchange(tree.d,d);
            exchange(tree.r,r);

            // indicate that the height of this tree has increased
            return true;
        }
        else  // keep looking for a place to add the new item
        {
            // make a reference to the current node so we don't have to dereference 
            // a pointer a bunch of times
            node& tree = *t;
            signed char old_balance = tree.balance;

            // add the new item to whatever subtree it should go into
            if (comp( d , tree.d) )
                tree.balance -= add_to_tree(tree.left,d,r);
            else
                tree.balance += add_to_tree(tree.right,d,r);


            // if the tree was balanced to start with
            if (old_balance == 0)
            {
                // if its not balanced anymore then it grew in height
                if (tree.balance != 0)
                    return true;
                else
                    return false;
            }
            else
            {
                // if the tree is now balanced then it didn't grow
                if (tree.balance == 0)
                {
                    return false;
                }
                else
                {
                    // if the tree needs to be balanced
                    if (tree.balance != old_balance)
                    {
                        return !keep_node_balanced(t);
                    }
                    // if there has been no change in the heights
                    else
                    {
                        return false;
                    }
                }
            }
        }
    } 

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    fix_stack (
        node* t,
        unsigned char depth 
    ) 
    {
        // if we found the node we were looking for
        if (t == current_element)
        {
            stack_pos = depth;
            return true;
        }
        else if (t == 0)
        {
            return false;
        }

        if (!( comp(t->d , current_element->d)))
        {
            // go left
            if (fix_stack(t->left,depth+1))
            {
                stack[depth] = t;
                return true;
            }            
        }
        if (!(comp(current_element->d , t->d)))
        {
            // go right
            if (fix_stack(t->right,depth+1))
            {
                stack[depth] = t;
                return true;
            }            
        }
        return false;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    remove_current_element_from_tree (
        node*& t,
        domain& d,
        range& r,
        unsigned long cur_stack_pos 
    ) 
    {
        // make a reference to the current node so we don't have to dereference 
        // a pointer a bunch of times
        node& tree = *t;

        // if we found the node we were looking for
        if (t == current_element)
        {

            // swap nodes domain and range elements into d_copy and r
            exchange(d,tree.d);
            exchange(r,tree.r);

            // if there is no left node
            if (tree.left == 0)
            {
                // move the enumerator on to the next element before we mess with the 
                // tree
                move_next();

                // plug hole left by removing this node and free memory
                t = tree.right;  // plug hole with right subtree
                
                // delete old node
                pool.deallocate(&tree);  

                // indicate that the height has changed
                return true;
            }
            // if there is no right node
            else if (tree.right == 0)
            {
                // move the enumerator on to the next element before we mess with the 
                // tree
                move_next();

                // plug hole left by removing this node and free memory
                t = tree.left;  // plug hole with left subtree

                // delete old node
                pool.deallocate(&tree);  

                // indicate that the height of this tree has changed
                return true;
            }
            // if there are both a left and right sub node
            else
            {

                // in this case the next current element is going to get swapped back
                // into this t node.
                current_element = t;

                // get an element that can replace the one being removed and do this 
                // if it made the right subtree shrink by one
                if (remove_least_element_in_tree(tree.right,tree.d,tree.r))
                {
                    // adjust the tree height
                    --tree.balance;

                    // if the height of the current tree has dropped by one
                    if (tree.balance == 0)
                    {
                        return true;
                    }
                    else
                    {
                        return keep_node_balanced(t);
                    }
                }
                // else this remove did not effect the height of this tree
                else
                {
                    return false;
                }

            }

        }
        else if (  (cur_stack_pos < stack_pos && stack[cur_stack_pos] == tree.left) || 
                    tree.left == current_element )
        {
            // go left
            if (tree.balance == -1)
            {
                int balance = tree.balance;
                balance += remove_current_element_from_tree(tree.left,d,r,cur_stack_pos+1);
                tree.balance = balance;
                return !tree.balance;
            }
            else
            {
                int balance = tree.balance;
                balance += remove_current_element_from_tree(tree.left,d,r,cur_stack_pos+1);
                tree.balance = balance;
                return keep_node_balanced(t);
            }
        }
        else if (  (cur_stack_pos < stack_pos && stack[cur_stack_pos] == tree.right) || 
                    tree.right == current_element )
        {
            // go right
            if (tree.balance == 1)
            {
                int balance = tree.balance;
                balance -= remove_current_element_from_tree(tree.right,d,r,cur_stack_pos+1);
                tree.balance = balance;
                return !tree.balance;
            }
            else
            {
                int balance = tree.balance;
                balance -= remove_current_element_from_tree(tree.right,d,r,cur_stack_pos+1);
                tree.balance = balance;
                return keep_node_balanced(t);
            }
        }
        
        // this return should never happen but do it anyway to suppress compiler warnings
        return false;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    remove_from_tree (
        node*& t,
        const domain& d,
        domain& d_copy,
        range& r
    ) 
    {
        // make a reference to the current node so we don't have to dereference 
        // a pointer a bunch of times
        node& tree = *t;

        // if item is on the left
        if (comp(d , tree.d))
        {
            // if the left side of the tree has the greatest height
            if (tree.balance == -1)
            {
                int balance = tree.balance;
                balance += remove_from_tree(tree.left,d,d_copy,r);
                tree.balance = balance;
                return !tree.balance;
            }
            else
            {
                int balance = tree.balance;
                balance += remove_from_tree(tree.left,d,d_copy,r);
                tree.balance = balance;
                return keep_node_balanced(t);
            }
             
        }
        // if item is on the right
        else if (comp(tree.d , d))
        {

            // if the right side of the tree has the greatest height
            if (tree.balance == 1)
            {
                int balance = tree.balance;
                balance -= remove_from_tree(tree.right,d,d_copy,r);
                tree.balance = balance;
                return !tree.balance;
            }
            else
            {
                int balance = tree.balance;
                balance -= remove_from_tree(tree.right,d,d_copy,r);
                tree.balance = balance;
                return keep_node_balanced(t);
            }
        }
        // if item is found
        else 
        {

            // swap nodes domain and range elements into d_copy and r
            exchange(d_copy,tree.d);
            exchange(r,tree.r);

            // if there is no left node
            if (tree.left == 0)
            {

                // plug hole left by removing this node and free memory
                t = tree.right;  // plug hole with right subtree
                
                // delete old node
                pool.deallocate(&tree);  

                // indicate that the height has changed
                return true;
            }
            // if there is no right node
            else if (tree.right == 0)
            {

                // plug hole left by removing this node and free memory
                t = tree.left;  // plug hole with left subtree

                // delete old node
                pool.deallocate(&tree);  

                // indicate that the height of this tree has changed
                return true;
            }
            // if there are both a left and right sub node
            else
            {

                // get an element that can replace the one being removed and do this 
                // if it made the right subtree shrink by one
                if (remove_least_element_in_tree(tree.right,tree.d,tree.r))
                {
                    // adjust the tree height
                    --tree.balance;

                    // if the height of the current tree has dropped by one
                    if (tree.balance == 0)
                    {
                        return true;
                    }
                    else
                    {
                        return keep_node_balanced(t);
                    }
                }
                // else this remove did not effect the height of this tree
                else
                {
                    return false;
                }

            }
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    remove_from_tree (
        node*& t,
        const domain& d
    ) 
    {
        // make a reference to the current node so we don't have to dereference 
        // a pointer a bunch of times
        node& tree = *t;

        // if item is on the left
        if (comp(d , tree.d))
        {
            // if the left side of the tree has the greatest height
            if (tree.balance == -1)
            {
                int balance = tree.balance;
                balance += remove_from_tree(tree.left,d);
                tree.balance = balance;
                return !tree.balance;
            }
            else
            {
                int balance = tree.balance;
                balance += remove_from_tree(tree.left,d);
                tree.balance = balance;
                return keep_node_balanced(t);
            }
             
        }
        // if item is on the right
        else if (comp(tree.d , d))
        {

            // if the right side of the tree has the greatest height
            if (tree.balance == 1)
            {
                int balance = tree.balance;
                balance -= remove_from_tree(tree.right,d);
                tree.balance = balance;
                return !tree.balance;
            }
            else
            {
                int balance = tree.balance;
                balance -= remove_from_tree(tree.right,d);
                tree.balance = balance;
                return keep_node_balanced(t);
            }
        }
        // if item is found
        else 
        {

            // if there is no left node
            if (tree.left == 0)
            {

                // plug hole left by removing this node and free memory
                t = tree.right;  // plug hole with right subtree
                
                // delete old node
                pool.deallocate(&tree);  

                // indicate that the height has changed
                return true;
            }
            // if there is no right node
            else if (tree.right == 0)
            {

                // plug hole left by removing this node and free memory
                t = tree.left;  // plug hole with left subtree

                // delete old node
                pool.deallocate(&tree);  

                // indicate that the height of this tree has changed
                return true;
            }
            // if there are both a left and right sub node
            else
            {

                // get an element that can replace the one being removed and do this 
                // if it made the right subtree shrink by one
                if (remove_least_element_in_tree(tree.right,tree.d,tree.r))
                {
                    // adjust the tree height
                    --tree.balance;

                    // if the height of the current tree has dropped by one
                    if (tree.balance == 0)
                    {
                        return true;
                    }
                    else
                    {
                        return keep_node_balanced(t);
                    }
                }
                // else this remove did not effect the height of this tree
                else
                {
                    return false;
                }

            }
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    range* binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    return_reference (
        node* t,
        const domain& d
    ) 
    {
        while (t != 0)
        {

            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_1<domain,range,mem_manager,compare>::
    return_reference (
        const node* t,
        const domain& d
    ) const
    {
        while (t != 0)
        {

            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
        >   
    bool binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    keep_node_balanced (
        node*& t
    )
    {
        // make a reference to the current node so we don't have to dereference 
        // a pointer a bunch of times
        node& tree = *t;
 
        // if tree does not need to be balanced then return false
        if (tree.balance == 0)
            return false;


        // if tree needs to be rotated left
        if (tree.balance == 2)
        {
            if (tree.right->balance >= 0)
                rotate_left(t);
            else
                double_rotate_left(t);
        }
        // else if the tree needs to be rotated right
        else if (tree.balance == -2)
        {
            if (tree.left->balance <= 0)
                rotate_right(t);
            else
                double_rotate_right(t);
        }
   

        if (t->balance == 0)
            return true;
        else
            return false; 
    }

// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename mem_manager,
        typename compare
        >   
    unsigned long binary_search_tree_kernel_1<domain,range,mem_manager,compare>::
    get_count (
        const domain& d,
        node* tree_root
    ) const
    {
        if (tree_root != 0)
        {
            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_1_