/*=============================================================================
    Copyright (c) 2001-2003 Joel de Guzman
    http://spirit.sourceforge.net/

    Use, modification and distribution is subject to the Boost Software
    License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
    http://www.boost.org/LICENSE_1_0.txt)
=============================================================================*/
#ifndef BOOST_SPIRIT_RANGE_RUN_IPP
#define BOOST_SPIRIT_RANGE_RUN_IPP

///////////////////////////////////////////////////////////////////////////////
#include <algorithm> // for std::lower_bound
#include <boost/spirit/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
#include <boost/spirit/utility/impl/chset/range_run.hpp>
#include <boost/spirit/debug.hpp>
#include <boost/limits.hpp>

///////////////////////////////////////////////////////////////////////////////
namespace boost { namespace spirit {

    namespace utility { namespace impl {

        ///////////////////////////////////////////////////////////////////////
        //
        //  range class implementation
        //
        ///////////////////////////////////////////////////////////////////////
        template <typename CharT>
        inline range<CharT>::range(CharT first_, CharT last_)
        : first(first_), last(last_) {}

        //////////////////////////////////
        template <typename CharT>
        inline bool
        range<CharT>::is_valid() const
        { return first <= last; }

        //////////////////////////////////
        template <typename CharT>
        inline bool
        range<CharT>::includes(range const& r) const
        { return (first <= r.first) && (last >= r.last); }

        //////////////////////////////////
        template <typename CharT>
        inline bool
        range<CharT>::includes(CharT v) const
        { return (first <= v) && (last >= v); }

        //////////////////////////////////
        template <typename CharT>
        inline bool
        range<CharT>::overlaps(range const& r) const
        {
            CharT decr_first =
                first == (std::numeric_limits<CharT>::min)() ? first : first-1;
            CharT incr_last =
                last == (std::numeric_limits<CharT>::max)() ? last : last+1;

            return (decr_first <= r.last) && (incr_last >= r.first);
        }

        //////////////////////////////////
        template <typename CharT>
        inline void
        range<CharT>::merge(range const& r)
        {
            first = (std::min)(first, r.first);
            last = (std::max)(last, r.last);
        }

        ///////////////////////////////////////////////////////////////////////
        //
        //  range_run class implementation
        //
        ///////////////////////////////////////////////////////////////////////
        template <typename CharT>
        inline bool
        range_run<CharT>::test(CharT v) const
        {
            if (!run.empty())
            {
                const_iterator iter =
                    std::lower_bound(
                        run.begin(), run.end(), v,
                        range_char_compare<CharT>()
                    );

                if (iter != run.end() && iter->includes(v))
                    return true;
                if (iter != run.begin())
                    return (--iter)->includes(v);
            }
            return false;
        }

        //////////////////////////////////
        template <typename CharT>
        inline void
        range_run<CharT>::swap(range_run& rr)
        { run.swap(rr.run); }

        //////////////////////////////////
        template <typename CharT>
        void
        range_run<CharT>::merge(iterator iter, range<CharT> const& r)
        {
            iter->merge(r);
            iterator i = iter + 1;

            while (i != run.end() && iter->overlaps(*i))
                iter->merge(*i++);

            run.erase(iter+1, i);
        }

        //////////////////////////////////
        template <typename CharT>
        void
        range_run<CharT>::set(range<CharT> const& r)
        {
            BOOST_SPIRIT_ASSERT(r.is_valid());
            if (!run.empty())
            {
                iterator iter =
                    std::lower_bound(
                        run.begin(), run.end(), r,
                        range_compare<CharT>()
                    );

                if ((iter != run.end() && iter->includes(r)) ||
                    ((iter != run.begin()) && (iter - 1)->includes(r)))
                    return;

                if (iter != run.begin() && (iter - 1)->overlaps(r))
                    merge(--iter, r);

                else if (iter != run.end() && iter->overlaps(r))
                    merge(iter, r);

                else
                    run.insert(iter, r);
            }
            else
            {
                run.push_back(r);
            }
        }

        //////////////////////////////////
        template <typename CharT>
        void
        range_run<CharT>::clear(range<CharT> const& r)
        {
            BOOST_SPIRIT_ASSERT(r.is_valid());
            if (!run.empty())
            {
                iterator iter =
                    std::lower_bound(
                        run.begin(), run.end(), r,
                        range_compare<CharT>()
                    );

                iterator left_iter;

                if ((iter != run.begin()) &&
                        (left_iter = (iter - 1))->includes(r.first))
                {
                    if (left_iter->last > r.last)
                    {
                        CharT save_last = left_iter->last;
                        left_iter->last = r.first-1;
                        run.insert(iter, range<CharT>(r.last+1, save_last));
                        return;
                    }
                    else
                    {
                        left_iter->last = r.first-1;
                    }
                }
                
                iterator i = iter;
                while (i != run.end() && r.includes(*i))
                    i++;
                if (i != run.end() && i->includes(r.last))
                    i->first = r.last+1;
                run.erase(iter, i);
            }
        }

        //////////////////////////////////
        template <typename CharT>
        inline void
        range_run<CharT>::clear()
        { run.clear(); }

        //////////////////////////////////
        template <typename CharT>
        inline typename range_run<CharT>::const_iterator
        range_run<CharT>::begin() const
        { return run.begin(); }

        //////////////////////////////////
        template <typename CharT>
        inline typename range_run<CharT>::const_iterator
        range_run<CharT>::end() const
        { return run.end(); }

    }} // namespace utility::impl

}} // namespace boost::spirit

#endif