text: // equivset.hpp
  // Copyright (c) 2007 Ben Hanson (http://www.benhanson.net/)
  //
  // Distributed under the Boost Software License, Version 1.0. (See accompanying
  // file licence_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  #ifndef BOOST_LEXER_EQUIVSET_HPP
  #define BOOST_LEXER_EQUIVSET_HPP
  
  #include <algorithm>
  #include "../parser/tree/node.hpp"
  #include <set>
  #include "../size_t.hpp"
  
  namespace boost
  {
  namespace lexer
  {
  namespace detail
  {
  struct equivset
  {
      typedef std::set<std::size_t> index_set;
      typedef std::vector<std::size_t> index_vector;
      // Not owner of nodes:
      typedef std::vector<node *> node_vector;
  
      index_vector _index_vector;
      bool _greedy;
      std::size_t _id;
      node_vector _followpos;
  
      equivset () :
          _greedy (true),
          _id (0)
      {
      }
  
      equivset (const index_set &index_set_, const bool greedy_,
          const std::size_t id_, const node_vector &followpos_) :
          _greedy (greedy_),
          _id (id_),
          _followpos (followpos_)
      {
          index_set::const_iterator iter_ = index_set_.begin ();
          index_set::const_iterator end_ = index_set_.end ();
  
          for (; iter_ != end_; ++iter_)
          {
              _index_vector.push_back (*iter_);
          }
      }
  
      bool empty () const
      {
          return _index_vector.empty () && _followpos.empty ();
      }
  
      void intersect (equivset &rhs_, equivset &overlap_)
      {
          intersect_indexes (rhs_._index_vector, overlap_._index_vector);
  
          if (!overlap_._index_vector.empty ())
          {
              overlap_._id = _id;
  
              // LHS abstemious transitions have priority.
              if (_greedy < rhs_._greedy)
              {
                  overlap_._greedy = _greedy;
              }
              else
              {
                  overlap_._greedy = _greedy;
              }
  
              // Note that the LHS takes priority in order to
              // respect rule ordering priority in the lex spec.
              overlap_._followpos = _followpos;
  
              node_vector::const_iterator overlap_begin_ =
                  overlap_._followpos.begin ();
              node_vector::const_iterator overlap_end_ =
                  overlap_._followpos.end ();
              node_vector::const_iterator rhs_iter_ =
                  rhs_._followpos.begin ();
              node_vector::const_iterator rhs_end_ =
                  rhs_._followpos.end ();
  
              for (; rhs_iter_ != rhs_end_; ++rhs_iter_)
              {
                  node *node_ = *rhs_iter_;
  
                  if (std::find (overlap_begin_, overlap_end_, node_) ==
                      overlap_end_)
                  {
                      overlap_._followpos.push_back (node_);
                      overlap_begin_ = overlap_._followpos.begin ();
                      overlap_end_ = overlap_._followpos.end ();
                  }
              }
  
              if (_index_vector.empty ())
              {
                  _followpos.clear ();
              }
  
              if (rhs_._index_vector.empty ())
              {
                  rhs_._followpos.clear ();
              }
          }
      }
  
  private:
      void intersect_indexes (index_vector &rhs_, index_vector &overlap_)
      {
          index_vector::iterator iter_ = _index_vector.begin ();
          index_vector::iterator end_ = _index_vector.end ();
          index_vector::iterator rhs_iter_ = rhs_.begin ();
          index_vector::iterator rhs_end_ = rhs_.end ();
  
          while (iter_ != end_ && rhs_iter_ != rhs_end_)
          {
              const std::size_t index_ = *iter_;
              const std::size_t rhs_index_ = *rhs_iter_;
  
              if (index_ < rhs_index_)
              {
                  ++iter_;
              }
              else if (index_ > rhs_index_)
              {
                  ++rhs_iter_;
              }
              else
              {
                  overlap_.push_back (index_);
                  iter_ = _index_vector.erase (iter_);
                  end_ = _index_vector.end ();
                  rhs_iter_ = rhs_.erase (rhs_iter_);
                  rhs_end_ = rhs_.end ();
              }
          }
      }
  };
  }
  }
  }
  
  #endif
  