// equivset.hpp
// Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_LEXER_EQUIVSET_HPP
#define BOOST_LEXER_EQUIVSET_HPP

#include <algorithm>
#include "../parser/tree/node.hpp"
#include <set>
#include "../size_t.hpp"

namespace boost
{
namespace lexer
{
namespace detail
{
struct equivset
{
    typedef std::set<std::size_t> index_set;
    typedef std::vector<std::size_t> index_vector;
    // Not owner of nodes:
    typedef std::vector<node *> node_vector;

    index_vector _index_vector;
    bool _greedy;
    std::size_t _id;
    node_vector _followpos;

    equivset () :
        _greedy (true),
        _id (0)
    {
    }

    equivset (const index_set &index_set_, const bool greedy_,
        const std::size_t id_, const node_vector &followpos_) :
        _greedy (greedy_),
        _id (id_),
        _followpos (followpos_)
    {
        index_set::const_iterator iter_ = index_set_.begin ();
        index_set::const_iterator end_ = index_set_.end ();

        for (; iter_ != end_; ++iter_)
        {
            _index_vector.push_back (*iter_);
        }
    }

    bool empty () const
    {
        return _index_vector.empty () && _followpos.empty ();
    }

    void intersect (equivset &rhs_, equivset &overlap_)
    {
        intersect_indexes (rhs_._index_vector, overlap_._index_vector);

        if (!overlap_._index_vector.empty ())
        {
            // Note that the LHS takes priority in order to
            // respect rule ordering priority in the lex spec.
            overlap_._id = _id;
            overlap_._greedy = _greedy;
            overlap_._followpos = _followpos;

            node_vector::const_iterator overlap_begin_ =
                overlap_._followpos.begin ();
            node_vector::const_iterator overlap_end_ =
                overlap_._followpos.end ();
            node_vector::const_iterator rhs_iter_ =
                rhs_._followpos.begin ();
            node_vector::const_iterator rhs_end_ =
                rhs_._followpos.end ();

            for (; rhs_iter_ != rhs_end_; ++rhs_iter_)
            {
                node *node_ = *rhs_iter_;

                if (std::find (overlap_begin_, overlap_end_, node_) ==
                    overlap_end_)
                {
                    overlap_._followpos.push_back (node_);
                    overlap_begin_ = overlap_._followpos.begin ();
                    overlap_end_ = overlap_._followpos.end ();
                }
            }

            if (_index_vector.empty ())
            {
                _followpos.clear ();
            }

            if (rhs_._index_vector.empty ())
            {
                rhs_._followpos.clear ();
            }
        }
    }

private:
    void intersect_indexes (index_vector &rhs_, index_vector &overlap_)
    {
        index_vector::iterator iter_ = _index_vector.begin ();
        index_vector::iterator end_ = _index_vector.end ();
        index_vector::iterator rhs_iter_ = rhs_.begin ();
        index_vector::iterator rhs_end_ = rhs_.end ();

        while (iter_ != end_ && rhs_iter_ != rhs_end_)
        {
            const std::size_t index_ = *iter_;
            const std::size_t rhs_index_ = *rhs_iter_;

            if (index_ < rhs_index_)
            {
                ++iter_;
            }
            else if (index_ > rhs_index_)
            {
                ++rhs_iter_;
            }
            else
            {
                overlap_.push_back (index_);
                iter_ = _index_vector.erase (iter_);
                end_ = _index_vector.end ();
                rhs_iter_ = rhs_.erase (rhs_iter_);
                rhs_end_ = rhs_.end ();
            }
        }
    }
};
}
}
}

#endif