// 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 unsigned long 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
        >
    unsigned long 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_

