2 // Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
4 // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 // file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 #ifndef BOOST_LEXER_EQUIVSET_HPP
7 #define BOOST_LEXER_EQUIVSET_HPP
10 #include "../parser/tree/node.hpp"
12 #include "../size_t.hpp"
22 typedef std::set<std::size_t> index_set;
23 typedef std::vector<std::size_t> index_vector;
24 // Not owner of nodes:
25 typedef std::vector<node *> node_vector;
27 index_vector _index_vector;
30 node_vector _followpos;
38 equivset (const index_set &index_set_, const bool greedy_,
39 const std::size_t id_, const node_vector &followpos_) :
42 _followpos (followpos_)
44 index_set::const_iterator iter_ = index_set_.begin ();
45 index_set::const_iterator end_ = index_set_.end ();
47 for (; iter_ != end_; ++iter_)
49 _index_vector.push_back (*iter_);
55 return _index_vector.empty () && _followpos.empty ();
58 void intersect (equivset &rhs_, equivset &overlap_)
60 intersect_indexes (rhs_._index_vector, overlap_._index_vector);
62 if (!overlap_._index_vector.empty ())
64 // Note that the LHS takes priority in order to
65 // respect rule ordering priority in the lex spec.
67 overlap_._greedy = _greedy;
68 overlap_._followpos = _followpos;
70 node_vector::const_iterator overlap_begin_ =
71 overlap_._followpos.begin ();
72 node_vector::const_iterator overlap_end_ =
73 overlap_._followpos.end ();
74 node_vector::const_iterator rhs_iter_ =
75 rhs_._followpos.begin ();
76 node_vector::const_iterator rhs_end_ =
77 rhs_._followpos.end ();
79 for (; rhs_iter_ != rhs_end_; ++rhs_iter_)
81 node *node_ = *rhs_iter_;
83 if (std::find (overlap_begin_, overlap_end_, node_) ==
86 overlap_._followpos.push_back (node_);
87 overlap_begin_ = overlap_._followpos.begin ();
88 overlap_end_ = overlap_._followpos.end ();
92 if (_index_vector.empty ())
97 if (rhs_._index_vector.empty ())
99 rhs_._followpos.clear ();
105 void intersect_indexes (index_vector &rhs_, index_vector &overlap_)
107 index_vector::iterator iter_ = _index_vector.begin ();
108 index_vector::iterator end_ = _index_vector.end ();
109 index_vector::iterator rhs_iter_ = rhs_.begin ();
110 index_vector::iterator rhs_end_ = rhs_.end ();
112 while (iter_ != end_ && rhs_iter_ != rhs_end_)
114 const std::size_t index_ = *iter_;
115 const std::size_t rhs_index_ = *rhs_iter_;
117 if (index_ < rhs_index_)
121 else if (index_ > rhs_index_)
127 overlap_.push_back (index_);
128 iter_ = _index_vector.erase (iter_);
129 end_ = _index_vector.end ();
130 rhs_iter_ = rhs_.erase (rhs_iter_);
131 rhs_end_ = rhs_.end ();