dvcompute 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::collections::VecDeque;
use std::cell::RefCell;

use crate::simulation::Point;

/// Represents a queue storage.
///
/// The queue storage either supports `push`, or `push_with_priority`, but
/// it cannot support the both methods simulateneously.
pub trait QueueStorage {

    /// The type of priorities, if `push_with_priority` is supported.
    /// Otherwise, it may define the `()` type.
    type Priority;

    /// The type of items.
    type Item;

    /// Test whether the storage is empty.
    fn is_empty(&self, p: &Point) -> bool;

    /// Pop the front item.
    fn pop(&self, p: &Point) -> Option<Self::Item>;

    /// Push an item, or panic if only `push_with_priority` is supported.
    fn push(&self, item: Self::Item, p: &Point);

    /// Push an item with the specified priority, or panic if only `push` is supported.
    fn push_with_priority(&self, priority: Self::Priority, item: Self::Item, p: &Point);

    /// Try to remove an item satisfying the specified predicate and return the item removed.
    fn remove_by<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool;

    /// Detect whether there is an element satisfying the specified predicate in the queue.
    fn exists<F>(&self, predicate: F, p: &Point) -> bool
        where F: Fn(&Self::Item) -> bool;

    /// Find an element satisfying the specified predicate.
    fn find<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool,
              Self::Item: Clone;
}

/// The `QueueStorage` box.
pub type QueueStorageBox<Item, Priority> = Box<dyn BoxableQueueStorage<Item = Item, Priority = Priority>>;

/// Represents a `QueueStorage` that can be boxed.
pub trait BoxableQueueStorage {

    /// The type of priorities, if `push_with_priority` is supported.
    /// Otherwise, it may define the `()` type.
    type Priority;

    /// The type of items.
    type Item;

    /// Test whether the storage is empty.
    fn is_empty(&self, p: &Point) -> bool;

    /// Pop the front item.
    fn pop(&self, p: &Point) -> Option<Self::Item>;

    /// Push an item, or panic if only `push_with_priority` is supported.
    fn push(&self, item: Self::Item, p: &Point);

    /// Push an item with the specified priority, or panic if only `push` is supported.
    fn push_with_priority(&self, priority: Self::Priority, item: Self::Item, p: &Point);

    /// Try to remove an item satisfying the specified predicate and return the item removed.
    fn remove_boxed_by(&self, predicate: Box<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>;

    /// Detect whether there is an element satisfying the specified predicate in the queue.
    fn exists_boxed(&self, predicate: Box<dyn Fn(&Self::Item) -> bool>, p: &Point) -> bool;

    /// Find an element satisfying the specified predicate.
    fn find_boxed(&self, predicate: Box<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>
        where Self::Item: Clone;
}

impl<S> BoxableQueueStorage for S
    where S: QueueStorage
{
    type Priority = S::Priority;
    type Item     = S::Item;

    fn is_empty(&self, p: &Point) -> bool {
        S::is_empty(self, p)
    }

    fn pop(&self, p: &Point) -> Option<Self::Item> {
        S::pop(self, p)
    }

    fn push(&self, item: Self::Item, p: &Point) {
        S::push(self, item, p)
    }

    fn push_with_priority(&self, priority: Self::Priority, item: Self::Item, p: &Point) {
        S::push_with_priority(self, priority, item, p)
    }

    fn remove_boxed_by(&self, predicate: Box<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item> {
        S::remove_by(self, predicate, p)
    }

    fn exists_boxed(&self, predicate: Box<dyn Fn(&Self::Item) -> bool>, p: &Point) -> bool {
        S::exists(self, predicate, p)
    }

    fn find_boxed(&self, predicate: Box<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>
        where Self::Item: Clone
    {
        S::find(self, predicate, p)
    }
}

/// Defines a queue strategy.
pub trait QueueStrategy {

    /// The associated priority type, or `()` if the priorities are not supported.
    type Priority;

    /// Create a new storage.
    fn new_storage<T>(&self) -> QueueStorageBox<T, Self::Priority>
        where T: 'static;
}

/// A queue storage based on the FCFS strategy.
pub struct FCFSStorage<T> {

    /// The underlying queue.
    queue: RefCell<VecDeque<T>>
}

impl<T> FCFSStorage<T> {

    /// Create a new storage.
    pub fn new() -> Self {
        FCFSStorage {
            queue: RefCell::new(VecDeque::new())
        }
    }
}

impl<T> QueueStorage for FCFSStorage<T> {

    type Priority = ();
    type Item     = T;

    fn is_empty(&self, _p: &Point) -> bool {
        let queue = self.queue.borrow();
        queue.is_empty()
    }

    fn pop(&self, _p: &Point) -> Option<Self::Item> {
        let mut queue = self.queue.borrow_mut();
        queue.pop_front()
    }

    fn push(&self, item: Self::Item, _p: &Point) {
        let mut queue = self.queue.borrow_mut();
        queue.push_back(item);
    }

    fn push_with_priority(&self, _priority: Self::Priority, _item: Self::Item, _p: &Point) {
        panic!("Not supported operation");
    }

    fn remove_by<F>(&self, predicate: F, _p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool
    {
        let mut queue = self.queue.borrow_mut();
        let n = queue.len();
        for i in 0 .. n {
            if predicate(&queue[i]) {
                return queue.remove(i);
            }
        }
        None
    }

    fn exists<F>(&self, predicate: F, _p: &Point) -> bool
        where F: Fn(&Self::Item) -> bool
    {
        let queue = self.queue.borrow();
        let n = queue.len();
        for i in 0 .. n {
            if predicate(&queue[i]) {
                return true;
            }
        }
        false
    }

    fn find<F>(&self, predicate: F, _p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool,
              Self::Item: Clone
    {
        let queue = self.queue.borrow();
        let n = queue.len();
        for i in 0 .. n {
            let e = &queue[i];
            if predicate(e) {
                return Some(e.clone());
            }
        }
        None
    }
}

/// A queue storage based on the LCFS strategy.
pub struct LCFSStorage<T> {

    /// The underlying queue.
    queue: RefCell<VecDeque<T>>
}

impl<T> LCFSStorage<T> {

    /// Create a new storage.
    pub fn new() -> Self {
        LCFSStorage {
            queue: RefCell::new(VecDeque::new())
        }
    }
}

impl<T> QueueStorage for LCFSStorage<T> {

    type Priority = ();
    type Item     = T;

    fn is_empty(&self, _p: &Point) -> bool {
        let queue = self.queue.borrow();
        queue.is_empty()
    }

    fn pop(&self, _p: &Point) -> Option<Self::Item> {
        let mut queue = self.queue.borrow_mut();
        queue.pop_back()
    }

    fn push(&self, item: Self::Item, _p: &Point) {
        let mut queue = self.queue.borrow_mut();
        queue.push_back(item);
    }

    fn push_with_priority(&self, _priority: Self::Priority, _item: Self::Item, _p: &Point) {
        panic!("Not supported operation");
    }

    fn remove_by<F>(&self, predicate: F, _p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool
    {
        let mut queue = self.queue.borrow_mut();
        let n = queue.len();
        for i in 0 .. n {
            if predicate(&queue[n - i]) {
                return queue.remove(i);
            }
        }
        None
    }

    fn exists<F>(&self, predicate: F, _p: &Point) -> bool
        where F: Fn(&Self::Item) -> bool
    {
        let queue = self.queue.borrow();
        let n = queue.len();
        for i in 0 .. n {
            if predicate(&queue[n - i]) {
                return true;
            }
        }
        false
    }

    fn find<F>(&self, predicate: F, _p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool,
              Self::Item: Clone
    {
        let queue = self.queue.borrow();
        let n = queue.len();
        for i in 0 .. n {
            let e = &queue[n - i];
            if predicate(e) {
                return Some(e.clone());
            }
        }
        None
    }
}

/// A queue strategy based on the FCFS (a.k.a. FIFO) strategy. It means "First Come - First Served".
#[derive(Clone)]
pub enum FCFSStrategy {

    /// A single instance of the queue strategy.
    Instance
}

impl QueueStrategy for FCFSStrategy {

    type Priority = ();

    fn new_storage<T>(&self) -> QueueStorageBox<T, Self::Priority>
        where T: 'static
    {
        Box::new(FCFSStorage::new())
    }
}

/// A queue strategy based on the LCFS (a.k.a. LIFO) strategy. It means "Last Come - First Served".
#[derive(Clone)]
pub enum LCFSStrategy {

    /// A single instance of the queue strategy.
    Instance
}

impl QueueStrategy for LCFSStrategy {

    type Priority = ();

    fn new_storage<T>(&self) -> QueueStorageBox<T, Self::Priority>
        where T: 'static
    {
        Box::new(LCFSStorage::new())
    }
}