dvcompute_utils 2.0.0

// Copyright (c) 2020-2022  David Sorokin <davsor@mail.ru>, based in Yoshkar-Ola, Russia
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.

use std::rc::Rc;
use std::ops::Deref;
use std::iter::*;

use super::list::*;

/// An immutable queue as described in book
/// "Algorithms: a functional programming approach" by
/// Fethi Rabhi and Guy Lapalme.
pub struct Queue<T> {

    /// The first items.
    first: List<T>,

    /// The rest items.
    rest: List<T>
}

impl<T: Clone> Clone for Queue<T> {

    fn clone(&self) -> Self {
        let Queue { first, rest } = self;
        Queue {
            first: first.clone(),
            rest: rest.clone()
        }
    }
}

impl<T> Queue<T> {

    /// Test whether the queue is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.first.is_empty()
    }

    /// Create an empty queue.
    #[inline]
    pub fn empty() -> Self {
        Queue { first: List::Nil, rest: List::Nil }
    }

    /// Iterate the items of the list.
    pub fn iter(&self) -> Chain<ListIterator<T>, ListIterator<T>> where T: Clone {
        let it1 = self.first.iter();
        let it2 = self.rest.reversed().iter();
        it1.chain(it2)
    }

    /// Push a new item to the queue.
    pub fn push_back(&self, item: T) -> Self where T: Clone {
        let first = self.first.clone();
        let rest  = List::Cons(item, Rc::new(self.rest.clone()));
        let queue = Queue { first: first, rest: rest };
        queue.into_queue()
    }

    /// Try to pop the first item from the queue.
    pub fn pop_front(&self) -> Option<(T, Self)> where T: Clone {
        match &self.first {
            &List::Nil => None,
            &List::Cons(ref head, ref tail) => {
                let item  = head.clone();
                let tail  = tail.deref();
                let first = tail.clone();
                let rest  = self.rest.clone();
                let queue = Queue { first: first, rest: rest };
                let queue = queue.into_queue();
                Some((item, queue))
            }
        }
    }

    /// Try to return the first element.
    pub fn front(&self) -> Option<T> where T: Clone {
        match &self.first {
            &List::Nil => None,
            &List::Cons(ref head, _) => {
                let item = head.clone();
                Some(item)
            }
        }
    }

    /// Remove the specified item from the queue.
    pub fn remove(&self, item: T) -> Option<(T, Self)> where T: Clone + Eq {
        let first = self.first.append(Rc::new(self.rest.reversed()));
        match first.remove(item) {
            None => None,
            Some((item, first)) => {
                let rest  = List::Nil;
                let queue = Queue { first: first, rest: rest };
                Some((item, queue.into_queue()))
            }
        }
    }

    /// Remove an item satisfying the specified predicate.
    pub fn remove_by<F>(&self, predicate: F) -> Option<(T, Self)>
        where T: Clone,
              F: Fn(&T) -> bool
    {
        let first = self.first.append(Rc::new(self.rest.reversed()));
        match first.remove_by(predicate) {
            None => None,
            Some((item, first)) => {
                let rest  = List::Nil;
                let queue = Queue { first: first, rest: rest };
                Some((item, queue.into_queue()))
            }
        }
    }

    /// Test whether there is an item satisfying the specified predicate.
    pub fn exists<F>(&self, predicate: F) -> bool
        where T: Clone,
              F: Fn(&T) -> bool + Clone
    {
        match self.first.exists(predicate.clone()) {
            true => true,
            false => self.rest.reversed().exists(predicate)
        }
    }

    /// Find an item satisfying the specified predicate.
    pub fn find<F>(&self, predicate: F) -> Option<T>
        where T: Clone,
              F: Fn(&T) -> bool + Clone
    {
        match self.first.find(predicate.clone()) {
            y@Some(_) => y,
            None => self.rest.reversed().find(predicate)
        }
    }

    /// Post-process the queue.
    #[inline]
    fn into_queue(self) -> Self where T: Clone {
        if self.first.is_empty() {
            Queue { first: self.rest.reversed(), rest: List::Nil }
        } else {
            self
        }
    }
}

impl<T: Clone> IntoIterator for Queue<T> {

    type Item = T;
    type IntoIter = Chain<ListIterator<T>, ListIterator<T>>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        let Queue { first, rest } = self;
        let it1 = first.into_iter();
        let it2 = rest.reversed().into_iter();
        it1.chain(it2)
    }
}