【逐次更新】Heap や stack を filter して pop する実装を要求する問題リスト

逐次更新です。該当する問題を見つけたら @ngtkana_kyopro までお知らせいただけると幸いです。

問題リスト

問題	container	description
ARC 181 D - Prefix Bubble Sort	heap	pop_while
ARC 001 D - レースゲーム	stack	これも pop_while 系ですがライブラリで対応するのはキビシそうです

ライブラリ

use std::collections::BinaryHeap;
use std::iter::FusedIterator;

pub trait Popmore: Sized {
    type Item;

    fn pop(&mut self) -> Option<Self::Item>;

    fn peek(&self) -> Option<&Self::Item>;

    fn pop_if(&mut self, f: impl FnMut(&Self::Item) -> bool) -> Option<Self::Item> {
        if self.peek().map_or(false, f) {
            Some(self.pop().unwrap())
        } else {
            None
        }
    }

    fn pop_while<F>(&mut self, mut f: F)
    where
        F: FnMut(&Self::Item) -> bool,
    {
        while self.peek().map_or(false, &mut f) {
            self.pop().unwrap();
        }
    }

    fn drain_while<F>(&mut self, f: F) -> DrainWhile<'_, Self, Self::Item, F>
    where
        F: FnMut(&Self::Item) -> bool,
    {
        DrainWhile { container: self, f }
    }
}

impl<T: Ord> Popmore for BinaryHeap<T> {
    type Item = T;

    fn pop(&mut self) -> Option<Self::Item> {
        self.pop()
    }

    fn peek(&self) -> Option<&Self::Item> {
        self.peek()
    }
}

impl<T> Popmore for Vec<T> {
    type Item = T;

    fn pop(&mut self) -> Option<Self::Item> {
        self.pop()
    }

    fn peek(&self) -> Option<&Self::Item> {
        self.last()
    }
}

pub struct DrainWhile<'a, C, T, F>
where
    C: Popmore<Item = T>,
    F: FnMut(&T) -> bool,
{
    container: &'a mut C,
    f: F,
}

impl<'a, C, T, F> Iterator for DrainWhile<'a, C, T, F>
where
    T: Ord,
    C: Popmore<Item = T>,
    F: FnMut(&T) -> bool,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.container.peek().map_or(false, &mut self.f) {
            self.container.pop()
        } else {
            None
        }
    }
}

impl<'a, C, T, F> FusedIterator for DrainWhile<'a, C, T, F>
where
    T: Ord,
    C: Popmore<Item = T>,
    F: FnMut(&T) -> bool,
{
}