Skip to content

web search done right

3.6 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

use std::cmp::Ordering;

pub trait IteratorExt: Iterator {
    fn peekable_non_lazy(self) -> Peekable<Self>
    where
        Self: Sized,
    {
        Peekable::new(self)
    }
}

pub trait VectorExt {
    type Iter: Iterator;
    fn sort_sorted_by<F>(self, f: F) -> SortSortedBy<Self::Iter, F>
    where
        Self: Sized,
        F: FnMut(&<Self::Iter as Iterator>::Item, &<Self::Iter as Iterator>::Item) -> Ordering;
}

impl<I> VectorExt for Vec<I>
where
    I: Iterator,
{
    type Iter = I;

    fn sort_sorted_by<F>(self, f: F) -> SortSortedBy<Self::Iter, F>
    where
        Self: Sized,
        F: FnMut(&<Self::Iter as Iterator>::Item, &<Self::Iter as Iterator>::Item) -> Ordering,
    {
        SortSortedBy::new(self, f)
    }
}

impl<I: Iterator> IteratorExt for I {}

pub struct Peekable<I>
where
    I: Iterator,
{
    iter: I,
    peeked: Option<I::Item>,
}

impl<I: Iterator> Peekable<I> {
    pub fn new(iter: I) -> Self {
        let mut iter = iter;
        let peeked = iter.next();
        Self { iter, peeked }
    }

    pub fn peek(&self) -> Option<&I::Item> {
        self.peeked.as_ref()
    }
}

impl<I: Iterator> Iterator for Peekable<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        let peeked = self.peeked.take();
        if peeked.is_some() {
            self.peeked = self.iter.next();
        }

        peeked
    }
}

/// Iterator that produces a sorted sequence of items from an a set of
/// iterators where each iterator is sorted.
///
/// This iterator does not verify that the input iterators are sorted.
pub struct SortSortedBy<I, F>
where
    I: Iterator,
{
    iters: Vec<Peekable<I>>,
    f: F,
}

impl<I, F> SortSortedBy<I, F>
where
    I: Iterator,
{
    pub fn new(iters: Vec<I>, f: F) -> Self
    where
        I: Iterator,
    {
        let iters = iters.into_iter().map(Peekable::new).collect();
        Self { iters, f }
    }
}

impl<I, F> Iterator for SortSortedBy<I, F>
where
    I: Iterator,
    F: FnMut(&<I as Iterator>::Item, &<I as Iterator>::Item) -> Ordering,
{
    type Item = <I as Iterator>::Item;

    fn next(&mut self) -> Option<Self::Item> {
        let mut min = self
            .iters
            .iter_mut()
            .min_by(|a, b| match (a.peek(), b.peek()) {
                (Some(a), Some(b)) => (self.f)(a, b),
                (Some(_), None) => Ordering::Less,
                (None, Some(_)) => Ordering::Greater,
                (None, None) => Ordering::Equal,
            });

        min.as_mut()?.next()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_flat_sorted_by() {
        let iters = vec![
            vec![1, 2, 3].into_iter(),
            vec![4, 5, 6].into_iter(),
            vec![7, 8, 9].into_iter(),
        ];
        let sorted: Vec<_> = iters.sort_sorted_by(|a, b| a.cmp(b)).collect();
        assert_eq!(sorted, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    }
}