/home/mhx/git/github/libmoost/include/moost/algorithm/inplace_set_intersection.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_ALGORITHM_INPLACE_SET_INTERSECTION_HPP__
#define MOOST_ALGORITHM_INPLACE_SET_INTERSECTION_HPP__

namespace moost { namespace algorithm {

// just like stl set_intersection, these two algorithms have the precondition
// that their input ranges are sorted
// i've looked through gcc's include and it seems like we shouldn't need our own in-place version,
// and that this would be safe:
// std::set_intersection(foo.begin(), foo.end(), bar.begin(), bar.end(), foo.begin());
// however, the preconditions of set_intersection (http://www.sgi.com/tech/stl/set_intersection.html)
// explicitly state that the output range and input ranges should not overlap
// so just to be safe, we'll write our own
template <class ForwardIterator, class InputIterator>
ForwardIterator inplace_set_intersection(ForwardIterator first1, ForwardIterator last1,
                                         InputIterator first2, InputIterator last2)
{
  ForwardIterator result = first1;
  while (   first1 != last1
         && first2 != last2)
  {
    if (*first1 < *first2)
      ++first1;
    else if (*first2 < *first1)
      ++first2;
    else
    {
      *result = *first1;
      ++first1;
      ++first2;
      ++result;
    }
  }
  return result;
}

template <class ForwardIterator, class InputIterator, class StrictWeakOrdering>
ForwardIterator inplace_set_intersection(ForwardIterator first1, ForwardIterator last1,
                                         InputIterator first2, InputIterator last2,
                                         StrictWeakOrdering comp)
{
  ForwardIterator result = first1;
  while (   first1 != last1
         && first2 != last2)
  {
    if (comp(*first1, *first2))
      ++first1;
    else if (comp(*first2, *first1))
      ++first2;
    else
    {
      *result = *first1;
      ++first1;
      ++first2;
      ++result;
    }
  }
  return result;
}

}} // moost::algorithm

#endif // MOOST_ALGORITHM_INPLACE_SET_INTERSECTION_HPP__