#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