dvcompute_branch 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 crate::simulation::Point;
use crate::simulation::ref_comp::*;

use dvcompute_utils::collections::im::*;

/// 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 + Clone;

    /// 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 + Clone;

    /// Find an element satisfying the specified predicate.
    fn find<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
        where F: Fn(&Self::Item) -> bool + Clone,
              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: Rc<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: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> bool;

    /// Find an element satisfying the specified predicate.
    fn find_boxed(&self, predicate: Rc<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: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item> {
        S::remove_by(self, move |x| { predicate(x) }, p)
    }

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

    fn find_boxed(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>
        where Self::Item: Clone
    {
        S::find(self, move |x| { predicate(x) }, 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: Clone + 'static;
}

/// The FCFS queue storage.
pub struct FCFSStorage<T> {

    /// The underlying queue.
    queue: RefComp<Queue<T>>
}

impl<T> FCFSStorage<T>
    where T: Clone
{
    /// Create a new storage.
    pub fn new() -> Self {
        FCFSStorage { queue: RefComp::new(Queue::empty()) }
    }
}

impl<T> QueueStorage for FCFSStorage<T>
    where T: Clone + 'static
{
    type Priority = ();
    type Item     = T;

    #[inline]
    fn is_empty(&self, p: &Point) -> bool {
        let queue = self.queue.read_at(p);
        queue.is_empty()
    }

    fn pop(&self, p: &Point) -> Option<Self::Item> {
        let results = {
            let queue = self.queue.read_at(p);
            queue.pop_front()
        };
        match results {
            None => None,
            Some((item, queue)) => {
                self.queue.write_at(queue, p);
                Some(item)
            }
        }
    }

    fn push(&self, item: Self::Item, p: &Point) {
        let results = {
            let queue = self.queue.read_at(p);
            queue.push_back(item)
        };
        self.queue.write_at(results, p);
    }

    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 + Clone
    {
        let results = {
            let queue = self.queue.read_at(p);
            queue.remove_by(predicate)
        };
        match results {
            None => None,
            Some((item, queue)) => {
                self.queue.write_at(queue, p);
                Some(item)
            }
        }
    }

    fn exists<F>(&self, predicate: F, p: &Point) -> bool
        where F: Fn(&Self::Item) -> bool + Clone
    {
        let queue = self.queue.read_at(p);
        queue.exists(predicate)
    }

    fn find<F>(&self, predicate: F, p: &Point) -> Option<T>
        where F: Fn(&Self::Item) -> bool + Clone,
              Self::Item: Clone
    {
        let queue = self.queue.read_at(p);
        queue.find(predicate)
    }
}

/// The LCFS queue storage.
pub struct LCFSStorage<T> {

    /// The underlying queue.
    queue: RefComp<List<T>>
}

impl<T> LCFSStorage<T>
    where T: Clone
{
    /// Create a new storage.
    pub fn new() -> Self {
        LCFSStorage { queue: RefComp::new(List::Nil) }
    }
}

impl<T> QueueStorage for LCFSStorage<T>
    where T: Clone + 'static
{
    type Priority = ();
    type Item     = T;

    #[inline]
    fn is_empty(&self, p: &Point) -> bool {
        let queue = self.queue.read_at(p);
        queue.is_empty()
    }

    fn pop(&self, p: &Point) -> Option<Self::Item> {
        match self.queue.read_at(p) {
            List::Nil => None,
            List::Cons(head, tail) => {
                let tail = tail.deref();
                self.queue.write_at(tail.clone(), p);
                Some(head)
            }
        }
    }

    fn push(&self, item: Self::Item, p: &Point) {
        let results = {
            let queue = self.queue.read_at(p);
            List::Cons(item, Rc::new(queue))
        };
        self.queue.write_at(results, p);
    }

    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 + Clone
    {
        let results = {
            let queue = self.queue.read_at(p);
            queue.remove_by(predicate)
        };
        match results {
            None => None,
            Some((item, queue)) => {
                self.queue.write_at(queue, p);
                Some(item)
            }
        }
    }

    fn exists<F>(&self, predicate: F, p: &Point) -> bool
        where F: Fn(&Self::Item) -> bool + Clone
    {
        let queue = self.queue.read_at(p);
        queue.exists(predicate)
    }

    fn find<F>(&self, predicate: F, p: &Point) -> Option<T>
        where F: Fn(&Self::Item) -> bool + Clone,
              Self::Item: Clone
    {
        let queue = self.queue.read_at(p);
        queue.find(predicate)
    }
}

/// 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: Clone + '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: Clone + 'static
    {
        Box::new(LCFSStorage::new())
    }
}