// Copyright (C) 2005  Davis E. King (davisking@users.sourceforge.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_STATIC_MAP_KERNEl_1_
#define DLIB_STATIC_MAP_KERNEl_1_

#include "static_map_kernel_abstract.h"
#include "../interfaces/map_pair.h"
#include "../interfaces/enumerable.h"
#include "../interfaces/remover.h"
#include "../algs.h"
#include "../serialize.h"
#include <functional>

namespace dlib
{

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

        /*!
            INITIAL VALUE
                - map_size == 0
                - d == 0
                - r == 0
                - mp.d = 0;
                - at_start_ == true


            CONVENTION                
                - size() == map_size
                - if (size() > 0) then
                    - d == pointer to an array containing all the domain elements
                    - r == pointer to an array containing all the range elements
                    - for every i:  operator[](d[i]) == r[i]
                    - d is sorted according to operator<
                - else
                    - d == 0
                    - r == 0

                - current_element_valid() == (mp.d != 0)
                - at_start() == (at_start_)
                - if (current_element_valid()) then
                    - element() == mp
        !*/
        
        class mpair : public map_pair<domain,range>
        {
        public:
            const domain* d;
            range* r;

            const domain& key( 
            ) const { return *d; }

            const range& value(
            ) const { return *r; }

            range& value(
            ) { return *r; }
        };


        // I would define this outside the class but Borland 5.5 has some problems
        // with non-inline templated friend functions.          
        friend void deserialize (
            static_map_kernel_1& item, 
            std::istream& in
        )
        {
            try
            {
                item.clear();
                unsigned long size;
                deserialize(size,in);
                item.map_size = size;
                item.d = new domain[size];
                item.r = new range[size];
                for (unsigned long i = 0; i < size; ++i)
                {
                    deserialize(item.d[i],in);
                    deserialize(item.r[i],in);
                }
            }
            catch (serialization_error& e)
            { 
                item.map_size = 0;
                if (item.d)
                {
                    delete [] item.d;
                    item.d = 0;
                }
                if (item.r)
                {
                    delete [] item.r;
                    item.r = 0;
                }

                throw serialization_error(e.info + "\n   while deserializing object of type static_map_kernel_1"); 
            }
            catch (...)
            {
                item.map_size = 0;
                if (item.d)
                {
                    delete [] item.d;
                    item.d = 0;
                }
                if (item.r)
                {
                    delete [] item.r;
                    item.r = 0;
                }

                throw;
            }
        }


        public:

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

            static_map_kernel_1(
            );

            virtual ~static_map_kernel_1(
            ); 

            void clear (
            );

            void load (
                pair_remover<domain,range>& source
            );

            void load (
                asc_pair_remover<domain,range,compare>& source
            );

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

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

            inline void swap (
                static_map_kernel_1& item
            );
    
            // functions from the enumerable interface
            inline unsigned long size (
            ) const;

            inline bool at_start (
            ) const;

            inline void reset (
            ) const;

            inline bool current_element_valid (
            ) const;

            inline const map_pair<domain,range>& element (
            ) const;

            inline map_pair<domain,range>& element (
            );

            inline bool move_next (
            ) const;


        private:

            bool binary_search (
                const domain& item,
                unsigned long& pos
            ) const;
            /*!
                ensures
                    - if (there is an item in d equivalent to item) then
                        - returns true
                        - d[#pos] is equivalent item
                    - else
                        - returns false
            !*/

            void sort_arrays (
                unsigned long left,
                unsigned long right
            );
            /*!
                requires    
                    - left and right are within the bounts of the array
                ensures 
                    - everything in the convention is still true and d[left] though
                      d[right] is sorted according to operator<
            !*/

            void qsort_partition (
                unsigned long& partition_element,
                const unsigned long left,
                const unsigned long right
            );    
            /*!
                requires                   
                    - left < right
                    - left and right are within the bounts of the array
                ensures
                    - the convention is still true
                    - left <= #partition_element <= right                              
                    - all elements in #d < #d[#partition_element] have 
                      indices >= left and < #partition_element                         
                    - all elements in #d >= #d[#partition_element] have 
                      indices >= #partition_element and <= right
            !*/

            unsigned long median (
                unsigned long one,
                unsigned long two,
                unsigned long three
            );
            /*!
                requires
                    - one, two, and three are valid indexes into d
                ensures
                    - returns the median of d[one], d[two], and d[three]
            !*/




            // data members
            unsigned long map_size;
            domain* d;
            range* r;          
            mutable mpair mp;
            mutable bool at_start_;
            compare comp;

            // restricted functions
            static_map_kernel_1(static_map_kernel_1&);        // copy constructor
            static_map_kernel_1& operator=(static_map_kernel_1&);    // assignment operator
    };

    template <
        typename domain,
        typename range,
        typename compare
        >
    inline void swap (
        static_map_kernel_1<domain,range,compare>& a, 
        static_map_kernel_1<domain,range,compare>& b 
    ) { a.swap(b); }   

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    static_map_kernel_1<domain,range,compare>::
    static_map_kernel_1(
    ) :
        map_size(0),
        d(0),
        r(0),
        at_start_(true)
    {
        mp.d = 0;
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    static_map_kernel_1<domain,range,compare>::
    ~static_map_kernel_1(
    )
    {
        if (map_size > 0)
        {
            delete [] d;
            delete [] r;
        }
    } 

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    clear (
    )
    {
        if (map_size > 0)
        {
            map_size = 0;
            delete [] d;
            delete [] r;
            d = 0;
            r = 0;
        }
        reset();
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    load (
        pair_remover<domain,range>& source
    )
    {        
        if (source.size() > 0)
        {             
            domain* old_d = d;
            d = new domain[source.size()];
            try { r = new range[source.size()]; }
            catch (...) { delete [] d; d = old_d; throw; }

            map_size = source.size();

            for (unsigned long i = 0; source.size() > 0; ++i)
                source.remove_any(d[i],r[i]);
                       
            sort_arrays(0,map_size-1);
        }
        else
        {
            clear();
        }
        reset();
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    load (
        asc_pair_remover<domain,range,compare>& source
    )
    {
        if (source.size() > 0)
        {             
            domain* old_d = d;
            d = new domain[source.size()];
            try { r = new range[source.size()]; }
            catch (...) { delete [] d; d = old_d; throw; }

            map_size = source.size();

            for (unsigned long i = 0; source.size() > 0; ++i)
                source.remove_any(d[i],r[i]);
        }
        else
        {
            clear();
        }
        reset();
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    const range* static_map_kernel_1<domain,range,compare>::
    operator[] (
        const domain& d_item
    ) const
    {
        unsigned long pos;
        if (binary_search(d_item,pos))
            return r+pos;
        else
            return 0;        
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    range* static_map_kernel_1<domain,range,compare>::
    operator[] (
        const domain& d_item
    )
    {
        unsigned long pos;
        if (binary_search(d_item,pos))
            return r+pos;
        else
            return 0;
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    unsigned long static_map_kernel_1<domain,range,compare>::
    size (
    ) const
    {
        return map_size;
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    swap (
        static_map_kernel_1<domain,range,compare>& item
    )
    {
        exchange(map_size,item.map_size);
        exchange(d,item.d);
        exchange(r,item.r);
        exchange(mp,item.mp);
        exchange(at_start_,item.at_start_);
        exchange(comp,item.comp);
    }

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // enumerable function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    bool static_map_kernel_1<domain,range,compare>::
    at_start (
    ) const
    {
        return (at_start_);
    }
    
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    reset (
    ) const
    {        
        mp.d = 0;
        at_start_ = true;
    }
    
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    bool static_map_kernel_1<domain,range,compare>::
    current_element_valid (
    ) const
    {   
        return (mp.d != 0);
    }
    
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    const map_pair<domain,range>& static_map_kernel_1<domain,range,compare>::
    element (
    ) const
    {
        return mp;
    }
    
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    map_pair<domain,range>& static_map_kernel_1<domain,range,compare>::
    element (
    )
    {
        return mp;
    }
    
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    bool static_map_kernel_1<domain,range,compare>::
    move_next (
    ) const
    {
        // if at_start() && size() > 0
        if (at_start_ && map_size > 0)
        {
            at_start_ = false;
            mp.r = r;
            mp.d = d;
            return true;
        }
        // else if current_element_valid()
        else if (mp.d != 0)
        {
            ++mp.d;
            ++mp.r;            
            if (static_cast<unsigned long>(mp.d - d) < map_size)
            {
                return true;
            }
            else
            {
                mp.d = 0;
                return false;
            }
        }
        else
        {      
            at_start_ = false;
            return false;
        }
    }
    
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // private member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename domain,
        typename range,
        typename compare
        >
    bool static_map_kernel_1<domain,range,compare>::
    binary_search (
        const domain& item,
        unsigned long& pos
    ) const
    {
        unsigned long high = map_size;
        unsigned long low = 0;
        unsigned long p = map_size;
        unsigned long idx;
        while (p > 0)
        {
            p = (high-low)>>1;
            idx = p+low;
            if (comp(item , d[idx]))
            {
                high = idx;
            }
            else if (comp(d[idx] , item))
            {
                low = idx;
            }
            else
            {
                pos = idx;
                return true;
            }
        }
        return false;
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    sort_arrays (
        unsigned long left,
        unsigned long right
    ) 
    {
        if ( left < right)
        {
            unsigned long partition_element;
            qsort_partition(partition_element,left,right);
            
            if (partition_element > 0)
                sort_arrays(left,partition_element-1);
            sort_arrays(partition_element+1,right);
        }
    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    void static_map_kernel_1<domain,range,compare>::
    qsort_partition (
        unsigned long& partition_element,
        const unsigned long left,
        const unsigned long right
    )
    {
        partition_element = right;

        unsigned long med = median(partition_element,left,((right-left)>>1) +left);
        exchange(d[partition_element],d[med]);
        exchange(r[partition_element],r[med]);
        
        unsigned long right_scan = right-1;
        unsigned long left_scan = left;

        while (true)
        {
            // find an element to the left of partition_element that needs to be moved
            while ( comp( d[left_scan] , d[partition_element]) )
            {
                ++left_scan;
            }

            // find an element to the right of partition_element that needs to be moved
            while ( 
                !(comp (d[right_scan] , d[partition_element])) &&  
                (right_scan > left_scan) 
            )
            {
                --right_scan;
            }
            if (left_scan >= right_scan)
                break;

            exchange(d[left_scan],d[right_scan]);
            exchange(r[left_scan],r[right_scan]);

        }
        exchange(d[left_scan],d[partition_element]);
        exchange(r[left_scan],r[partition_element]);
        partition_element = left_scan;

    }

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

    template <
        typename domain,
        typename range,
        typename compare
        >
    unsigned long static_map_kernel_1<domain,range,compare>::
    median (
        unsigned long one,
        unsigned long two,
        unsigned long three
    )
    {
        if ( comp( d[one] , d[two]) )
        {
            // one < two
            if ( comp( d[two] , d[three]) )
            {
                // one < two < three : two
                return two;                
            }
            else
            {
                // one < two >= three
                if (comp( d[one] , d[three]))
                {
                    // three
                    return three;
                }
            }
            
        }
        else
        {
            // one >= two
            if ( comp(d[three] , d[one] ))
            {
                // three <= one >= two
                if ( comp(d[three] , d[two]) )
                {
                    // two
                    return two;
                }
                else
                {
                    // three
                    return three;
                }
            }
        }  
        return one;
    }

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

}

#endif // DLIB_STATIC_MAP_KERNEl_1_

