1// equivset.hpp
2// Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
3//
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_SPIRIT_SUPPORT_DETAIL_LEXER_PARTITION_EQUIVSET_HPP
7#define BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARTITION_EQUIVSET_HPP
8
9#include <algorithm>
10#include "../parser/tree/node.hpp"
11#include <set>
12#include "../size_t.hpp"
13
14namespace boost
15{
16namespace lexer
17{
18namespace detail
19{
20struct equivset
21{
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;
26
27 index_vector _index_vector;
28 bool _greedy;
29 std::size_t _id;
30 node_vector _followpos;
31
32 equivset () :
33 _greedy (true),
34 _id (0)
35 {
36 }
37
38 equivset (const index_set &index_set_, const bool greedy_,
39 const std::size_t id_, const node_vector &followpos_) :
40 _greedy (greedy_),
41 _id (id_),
42 _followpos (followpos_)
43 {
44 index_set::const_iterator iter_ = index_set_.begin ();
45 index_set::const_iterator end_ = index_set_.end ();
46
47 for (; iter_ != end_; ++iter_)
48 {
49 _index_vector.push_back (x: *iter_);
50 }
51 }
52
53 bool empty () const
54 {
55 return _index_vector.empty () && _followpos.empty ();
56 }
57
58 void intersect (equivset &rhs_, equivset &overlap_)
59 {
60 intersect_indexes (rhs_&: rhs_._index_vector, overlap_&: overlap_._index_vector);
61
62 if (!overlap_._index_vector.empty ())
63 {
64 // Note that the LHS takes priority in order to
65 // respect rule ordering priority in the lex spec.
66 overlap_._id = _id;
67 overlap_._greedy = _greedy;
68 overlap_._followpos = _followpos;
69
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 ();
78
79 for (; rhs_iter_ != rhs_end_; ++rhs_iter_)
80 {
81 node *node_ = *rhs_iter_;
82
83 if (std::find (first: overlap_begin_, last: overlap_end_, val: node_) ==
84 overlap_end_)
85 {
86 overlap_._followpos.push_back (x: node_);
87 overlap_begin_ = overlap_._followpos.begin ();
88 overlap_end_ = overlap_._followpos.end ();
89 }
90 }
91
92 if (_index_vector.empty ())
93 {
94 _followpos.clear ();
95 }
96
97 if (rhs_._index_vector.empty ())
98 {
99 rhs_._followpos.clear ();
100 }
101 }
102 }
103
104private:
105 void intersect_indexes (index_vector &rhs_, index_vector &overlap_)
106 {
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 ();
111
112 while (iter_ != end_ && rhs_iter_ != rhs_end_)
113 {
114 const std::size_t index_ = *iter_;
115 const std::size_t rhs_index_ = *rhs_iter_;
116
117 if (index_ < rhs_index_)
118 {
119 ++iter_;
120 }
121 else if (index_ > rhs_index_)
122 {
123 ++rhs_iter_;
124 }
125 else
126 {
127 overlap_.push_back (x: index_);
128 iter_ = _index_vector.erase (position: iter_);
129 end_ = _index_vector.end ();
130 rhs_iter_ = rhs_.erase (position: rhs_iter_);
131 rhs_end_ = rhs_.end ();
132 }
133 }
134 }
135};
136}
137}
138}
139
140#endif
141

source code of boost/libs/spirit/include/boost/spirit/home/support/detail/lexer/partition/equivset.hpp