diff options
author | Kenneth Heafield <github@kheafield.com> | 2013-01-18 19:58:54 +0400 |
---|---|---|
committer | Kenneth Heafield <github@kheafield.com> | 2013-01-18 19:59:51 +0400 |
commit | fc5868d0fff647c3879668af4bfe6e1bab9e83ab (patch) | |
tree | d9b5026f32cc5ae603e6f42b1fc7128aeee4ba55 /util/multi_intersection.hh | |
parent | 5f7b91e702f809577d82a7570778d254d985ba93 (diff) |
KenLM df5be22 lmplz for estimation
Diffstat (limited to 'util/multi_intersection.hh')
-rw-r--r-- | util/multi_intersection.hh | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/util/multi_intersection.hh b/util/multi_intersection.hh new file mode 100644 index 000000000..8334d39df --- /dev/null +++ b/util/multi_intersection.hh @@ -0,0 +1,80 @@ +#ifndef UTIL_MULTI_INTERSECTION__ +#define UTIL_MULTI_INTERSECTION__ + +#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__ |