l4/pkg/boost-lite/include/boost/spirit/home/support/detail/lexer/partition/equivset.hpp

   1 // equivset.hpp
   2 // Copyright (c) 2007-2008 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_LEXER_EQUIVSET_HPP
   7 #define BOOST_LEXER_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
  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 (*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_._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:
 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 (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