kenlm/util/multi_intersection.hh

#ifndef UTIL_MULTI_INTERSECTION_H
#define UTIL_MULTI_INTERSECTION_H

#include <boost/optional.hpp>
#include <boost/range/iterator_range.hpp>

#include <algorithm>
#include <functional>
#include <vector>

namespace util {

namespace detail {
template <class Range> struct RangeLessBySize : public std::binary_function<const Range &, const Range &, bool> {
  bool operator()(const Range &left, const Range &right) const {
    return left.size() < right.size();
  }
};

/* Takes sets specified by their iterators and a boost::optional containing
 * the lowest intersection if any.  Each set must be sorted in increasing
 * order.  sets is changed to truncate the beginning of each sequence to the
 * location of the match or an empty set.  Precondition: sets is not empty
 * since the intersection over null is the universe and this function does not
 * know the universe.
 */
template <class Iterator, class Less> boost::optional<typename std::iterator_traits<Iterator>::value_type> FirstIntersectionSorted(std::vector<boost::iterator_range<Iterator> > &sets, const Less &less = std::less<typename std::iterator_traits<Iterator>::value_type>()) {
  typedef std::vector<boost::iterator_range<Iterator> > Sets;
  typedef typename std::iterator_traits<Iterator>::value_type Value;

  assert(!sets.empty());

  if (sets.front().empty()) return boost::optional<Value>();
  // Possibly suboptimal to copy for general Value; makes unsigned int go slightly faster.
  Value highest(sets.front().front());
  for (typename Sets::iterator i(sets.begin()); i != sets.end(); ) {
    i->advance_begin(std::lower_bound(i->begin(), i->end(), highest, less) - i->begin());
    if (i->empty()) return boost::optional<Value>();
    if (less(highest, i->front())) {
      highest = i->front();
      // start over
      i = sets.begin();
    } else {
      ++i;
    }
  }
  return boost::optional<Value>(highest);
}

} // namespace detail

template <class Iterator, class Less> boost::optional<typename std::iterator_traits<Iterator>::value_type> FirstIntersection(std::vector<boost::iterator_range<Iterator> > &sets, const Less less) {
  assert(!sets.empty());

  std::sort(sets.begin(), sets.end(), detail::RangeLessBySize<boost::iterator_range<Iterator> >());
  return detail::FirstIntersectionSorted(sets, less);
}

template <class Iterator> boost::optional<typename std::iterator_traits<Iterator>::value_type> FirstIntersection(std::vector<boost::iterator_range<Iterator> > &sets) {
  return FirstIntersection(sets, std::less<typename std::iterator_traits<Iterator>::value_type>());
}

template <class Iterator, class Output, class Less> void AllIntersection(std::vector<boost::iterator_range<Iterator> > &sets, Output &out, const Less less) {
  typedef typename std::iterator_traits<Iterator>::value_type Value;
  assert(!sets.empty());

  std::sort(sets.begin(), sets.end(), detail::RangeLessBySize<boost::iterator_range<Iterator> >());
  boost::optional<Value> ret;
  for (boost::optional<Value> ret; (ret = detail::FirstIntersectionSorted(sets, less)); sets.front().advance_begin(1)) {
    out(*ret);
  }
}

template <class Iterator, class Output> void AllIntersection(std::vector<boost::iterator_range<Iterator> > &sets, Output &out) {
  AllIntersection(sets, out, std::less<typename std::iterator_traits<Iterator>::value_type>());
}

} // namespace util

#endif // UTIL_MULTI_INTERSECTION_H