/*=============================================================================
    Copyright (c) 2001-2010 Joel de Guzman

    Distributed under 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)
==============================================================================*/
#if !defined(BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM)
#define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/spirit/home/support/char_set/range_functions.hpp>
#include <boost/assert.hpp>
#include <boost/integer_traits.hpp>
#include <algorithm>

namespace boost { namespace spirit { namespace support { namespace detail
{
    template <typename Run, typename Iterator, typename Range>
    inline bool
    try_merge(Run& run, Iterator iter, Range const& range)
    {
        // if *iter intersects with, or is adjacent to, 'range'...
        if (can_merge(*iter, range))
        {
            typedef typename Range::value_type value_type;
            typedef integer_traits<value_type> integer_traits;

            // merge range and *iter
            merge(*iter, range);

            // collapse all subsequent ranges that can merge with *iter:
            Iterator i = iter+1;
            // 1. skip subsequent ranges completely included in *iter
            while (i != run.end() && i->last <= iter->last)
                ++i;
            // 2. collapse next range if adjacent or overlapping with *iter
            if (i != run.end() && i->first-1 <= iter->last)
            {
                iter->last = i->last;
                ++i;
            }

            // erase all ranges that were collapsed
            run.erase(iter+1, i);
            return true;
        }
        return false;
    }

    template <typename Char>
    inline bool
    range_run<Char>::test(Char val) const
    {
        if (run.empty())
            return false;

        // search the ranges for one that potentially includes val
        typename storage_type::const_iterator iter =
            std::upper_bound(
                run.begin(), run.end(), val,
                range_compare<range_type>()
            );

        // return true if *(iter-1) includes val
        return iter != run.begin() && includes(*(--iter), val);
    }

    template <typename Char>
    inline void
    range_run<Char>::swap(range_run& other)
    {
        run.swap(other.run);
    }

    template <typename Char>
    void
    range_run<Char>::set(range_type const& range)
    {
        BOOST_ASSERT(is_valid(range));
        if (run.empty())
        {
            // the vector is empty, insert 'range'
            run.push_back(range);
            return;
        }

        // search the ranges for one that potentially includes 'range'
        typename storage_type::iterator iter =
            std::upper_bound(
                run.begin(), run.end(), range,
                range_compare<range_type>()
            );

        if (iter != run.begin())
        {
            // if *(iter-1) includes 'range', return early
            if (includes(*(iter-1), range))
            {
                return;
            }

            // if *(iter-1) can merge with 'range', merge them and return
            if (try_merge(run, iter-1, range))
            {
                return;
            }
        }

        // if *iter can merge with with 'range', merge them
        if (iter == run.end() || !try_merge(run, iter, range))
        {
            // no overlap, insert 'range'
            run.insert(iter, range);
        }
    }

    template <typename Char>
    void
    range_run<Char>::clear(range_type const& range)
    {
        BOOST_ASSERT(is_valid(range));
        if (!run.empty())
        {
            // search the ranges for one that potentially includes 'range'
            typename storage_type::iterator iter =
                std::upper_bound(
                    run.begin(), run.end(), range,
                    range_compare<range_type>()
                );

            // 'range' starts with or after another range:
            if (iter != run.begin())
            {
                typename storage_type::iterator const left_iter = iter-1;

                // 'range' starts after '*left_iter':
                if (left_iter->first < range.first)
                {
                    // if 'range' is completely included inside '*left_iter':
                    // need to break it apart into two ranges (punch a hole),
                    if (left_iter->last > range.last)
                    {
                        Char save_last = left_iter->last;
                        left_iter->last = range.first-1;
                        run.insert(iter, range_type(range.last+1, save_last));
                        return;
                    }
                    // if 'range' contains 'left_iter->last':
                    // truncate '*left_iter' (clip its right)
                    else if (left_iter->last >= range.first)
                    {
                        left_iter->last = range.first-1;
                    }
                }

                // 'range' has the same left bound as '*left_iter': it
                // must be removed or truncated by the code below
                else
                {
                    iter = left_iter;
                }
            }

            // remove or truncate subsequent ranges that overlap with 'range':
            typename storage_type::iterator i = iter;
            // 1. skip subsequent ranges completely included in 'range'
            while (i != run.end() && i->last <= range.last)
                ++i;
            // 2. clip left of next range if overlapping with 'range'
            if (i != run.end() && i->first <= range.last)
                i->first = range.last+1;

            // erase all ranges that 'range' contained
            run.erase(iter, i);
        }
    }

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

#endif