| // 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 |