lexer/partition/equivset.hpp

0001 // equivset.hpp
0002 // Copyright (c) 2007-2009 Ben Hanson (http://www.benhanson.net/)
0003 //
0004 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0005 // file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 #ifndef BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARTITION_EQUIVSET_HPP
0007 #define BOOST_SPIRIT_SUPPORT_DETAIL_LEXER_PARTITION_EQUIVSET_HPP
0008
0009 #include <algorithm>
0010 #include "../parser/tree/node.hpp"
0011 #include <set>
0012 #include "../size_t.hpp"
0013
0014 namespace boost
0015 {
0016 namespace lexer
0017 {
0018 namespace detail
0019 {
0020 struct equivset
0021 {
0022     typedef std::set<std::size_t> index_set;
0023     typedef std::vector<std::size_t> index_vector;
0024     // Not owner of nodes:
0025     typedef std::vector<node *> node_vector;
0026
0027     index_vector _index_vector;
0028     bool _greedy;
0029     std::size_t _id;
0030     node_vector _followpos;
0031
0032     equivset () :
0033         _greedy (true),
0034         _id (0)
0035     {
0036     }
0037
0038     equivset (const index_set &index_set_, const bool greedy_,
0039         const std::size_t id_, const node_vector &followpos_) :
0040         _greedy (greedy_),
0041         _id (id_),
0042         _followpos (followpos_)
0043     {
0044         index_set::const_iterator iter_ = index_set_.begin ();
0045         index_set::const_iterator end_ = index_set_.end ();
0046
0047         for (; iter_ != end_; ++iter_)
0048         {
0049             _index_vector.push_back (*iter_);
0050         }
0051     }
0052
0053     bool empty () const
0054     {
0055         return _index_vector.empty () && _followpos.empty ();
0056     }
0057
0058     void intersect (equivset &rhs_, equivset &overlap_)
0059     {
0060         intersect_indexes (rhs_._index_vector, overlap_._index_vector);
0061
0062         if (!overlap_._index_vector.empty ())
0063         {
0064             // Note that the LHS takes priority in order to
0065             // respect rule ordering priority in the lex spec.
0066             overlap_._id = _id;
0067             overlap_._greedy = _greedy;
0068             overlap_._followpos = _followpos;
0069
0070             node_vector::const_iterator overlap_begin_ =
0071                 overlap_._followpos.begin ();
0072             node_vector::const_iterator overlap_end_ =
0073                 overlap_._followpos.end ();
0074             node_vector::const_iterator rhs_iter_ =
0075                 rhs_._followpos.begin ();
0076             node_vector::const_iterator rhs_end_ =
0077                 rhs_._followpos.end ();
0078
0079             for (; rhs_iter_ != rhs_end_; ++rhs_iter_)
0080             {
0081                 node *node_ = *rhs_iter_;
0082
0083                 if (std::find (overlap_begin_, overlap_end_, node_) ==
0084                     overlap_end_)
0085                 {
0086                     overlap_._followpos.push_back (node_);
0087                     overlap_begin_ = overlap_._followpos.begin ();
0088                     overlap_end_ = overlap_._followpos.end ();
0089                 }
0090             }
0091
0092             if (_index_vector.empty ())
0093             {
0094                 _followpos.clear ();
0095             }
0096
0097             if (rhs_._index_vector.empty ())
0098             {
0099                 rhs_._followpos.clear ();
0100             }
0101         }
0102     }
0103
0104 private:
0105     void intersect_indexes (index_vector &rhs_, index_vector &overlap_)
0106     {
0107         index_vector::iterator iter_ = _index_vector.begin ();
0108         index_vector::iterator end_ = _index_vector.end ();
0109         index_vector::iterator rhs_iter_ = rhs_.begin ();
0110         index_vector::iterator rhs_end_ = rhs_.end ();
0111
0112         while (iter_ != end_ && rhs_iter_ != rhs_end_)
0113         {
0114             const std::size_t index_ = *iter_;
0115             const std::size_t rhs_index_ = *rhs_iter_;
0116
0117             if (index_ < rhs_index_)
0118             {
0119                 ++iter_;
0120             }
0121             else if (index_ > rhs_index_)
0122             {
0123                 ++rhs_iter_;
0124             }
0125             else
0126             {
0127                 overlap_.push_back (index_);
0128                 iter_ = _index_vector.erase (iter_);
0129                 end_ = _index_vector.end ();
0130                 rhs_iter_ = rhs_.erase (rhs_iter_);
0131                 rhs_end_ = rhs_.end ();
0132             }
0133         }
0134     }
0135 };
0136 }
0137 }
0138 }
0139
0140 #endif