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 
14 namespace boost
15 {
16 namespace lexer
17 {
18 namespace detail
19 {
20 struct 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 
equivsetboost::lexer::detail::equivset32     equivset () :
33         _greedy (true),
34         _id (0)
35     {
36     }
37 
equivsetboost::lexer::detail::equivset38     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 (*iter_);
50         }
51     }
52 
emptyboost::lexer::detail::equivset53     bool empty () const
54     {
55         return _index_vector.empty () && _followpos.empty ();
56     }
57 
intersectboost::lexer::detail::equivset58     void intersect (equivset &rhs_, equivset &overlap_)
59     {
60         intersect_indexes (rhs_._index_vector, 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 (overlap_begin_, overlap_end_, node_) ==
84                     overlap_end_)
85                 {
86                     overlap_._followpos.push_back (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 
104 private:
intersect_indexesboost::lexer::detail::equivset105     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 (index_);
128                 iter_ = _index_vector.erase (iter_);
129                 end_ = _index_vector.end ();
130                 rhs_iter_ = rhs_.erase (rhs_iter_);
131                 rhs_end_ = rhs_.end ();
132             }
133         }
134     }
135 };
136 }
137 }
138 }
139 
140 #endif
141