dvcompute_dist/simulation/
strategy.rs

1// Copyright (c) 2020-2022  David Sorokin <davsor@mail.ru>, based in Yoshkar-Ola, Russia
2//
3// This Source Code Form is subject to the terms of the Mozilla Public
4// License, v. 2.0. If a copy of the MPL was not distributed with this
5// file, You can obtain one at https://mozilla.org/MPL/2.0/.
6
7use std::rc::Rc;
8use std::ops::Deref;
9
10use crate::simulation::Point;
11use crate::simulation::ref_comp::*;
12
13use dvcompute_utils::collections::im::*;
14
15/// Represents a queue storage.
16///
17/// The queue storage either supports `push`, or `push_with_priority`, but
18/// it cannot support the both methods simulateneously.
19pub trait QueueStorage {
20
21    /// The type of priorities, if `push_with_priority` is supported.
22    /// Otherwise, it may define the `()` type.
23    type Priority;
24
25    /// The type of items.
26    type Item;
27
28    /// Test whether the storage is empty.
29    fn is_empty(&self, p: &Point) -> bool;
30
31    /// Pop the front item.
32    fn pop(&self, p: &Point) -> Option<Self::Item>;
33
34    /// Push an item, or panic if only `push_with_priority` is supported.
35    fn push(&self, item: Self::Item, p: &Point);
36
37    /// Push an item with the specified priority, or panic if only `push` is supported.
38    fn push_with_priority(&self, priority: Self::Priority, item: Self::Item, p: &Point);
39
40    /// Try to remove an item satisfying the specified predicate and return the item removed.
41    fn remove_by<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
42        where F: Fn(&Self::Item) -> bool + Clone;
43
44    /// Detect whether there is an element satisfying the specified predicate in the queue.
45    fn exists<F>(&self, predicate: F, p: &Point) -> bool
46        where F: Fn(&Self::Item) -> bool + Clone;
47
48    /// Find an element satisfying the specified predicate.
49    fn find<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
50        where F: Fn(&Self::Item) -> bool + Clone,
51              Self::Item: Clone;
52}
53
54/// The `QueueStorage` box.
55pub type QueueStorageBox<Item, Priority> = Box<dyn BoxableQueueStorage<Item = Item, Priority = Priority>>;
56
57/// Represents a `QueueStorage` that can be boxed.
58pub trait BoxableQueueStorage {
59
60    /// The type of priorities, if `push_with_priority` is supported.
61    /// Otherwise, it may define the `()` type.
62    type Priority;
63
64    /// The type of items.
65    type Item;
66
67    /// Test whether the storage is empty.
68    fn is_empty(&self, p: &Point) -> bool;
69
70    /// Pop the front item.
71    fn pop(&self, p: &Point) -> Option<Self::Item>;
72
73    /// Push an item, or panic if only `push_with_priority` is supported.
74    fn push(&self, item: Self::Item, p: &Point);
75
76    /// Push an item with the specified priority, or panic if only `push` is supported.
77    fn push_with_priority(&self, priority: Self::Priority, item: Self::Item, p: &Point);
78
79    /// Try to remove an item satisfying the specified predicate and return the item removed.
80    fn remove_boxed_by(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>;
81
82    /// Detect whether there is an element satisfying the specified predicate in the queue.
83    fn exists_boxed(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> bool;
84
85    /// Find an element satisfying the specified predicate.
86    fn find_boxed(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>
87        where Self::Item: Clone;
88}
89
90impl<S> BoxableQueueStorage for S
91    where S: QueueStorage
92{
93    type Priority = S::Priority;
94    type Item     = S::Item;
95
96    fn is_empty(&self, p: &Point) -> bool {
97        S::is_empty(self, p)
98    }
99
100    fn pop(&self, p: &Point) -> Option<Self::Item> {
101        S::pop(self, p)
102    }
103
104    fn push(&self, item: Self::Item, p: &Point) {
105        S::push(self, item, p)
106    }
107
108    fn push_with_priority(&self, priority: Self::Priority, item: Self::Item, p: &Point) {
109        S::push_with_priority(self, priority, item, p)
110    }
111
112    fn remove_boxed_by(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item> {
113        S::remove_by(self, move |x| { predicate(x) }, p)
114    }
115
116    fn exists_boxed(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> bool {
117        S::exists(self, move |x| { predicate(x) }, p)
118    }
119
120    fn find_boxed(&self, predicate: Rc<dyn Fn(&Self::Item) -> bool>, p: &Point) -> Option<Self::Item>
121        where Self::Item: Clone
122    {
123        S::find(self, move |x| { predicate(x) }, p)
124    }
125}
126
127/// Defines a queue strategy.
128pub trait QueueStrategy {
129
130    /// The associated priority type, or `()` if the priorities are not supported.
131    type Priority;
132
133    /// Create a new storage.
134    fn new_storage<T>(&self) -> QueueStorageBox<T, Self::Priority>
135        where T: Clone + 'static;
136}
137
138/// The FCFS queue storage.
139pub struct FCFSStorage<T> {
140
141    /// The underlying queue.
142    queue: RefComp<Queue<T>>
143}
144
145impl<T> FCFSStorage<T>
146    where T: Clone
147{
148    /// Create a new storage.
149    pub fn new() -> Self {
150        FCFSStorage { queue: RefComp::new(Queue::empty()) }
151    }
152}
153
154impl<T> QueueStorage for FCFSStorage<T>
155    where T: Clone + 'static
156{
157    type Priority = ();
158    type Item     = T;
159
160    #[inline]
161    fn is_empty(&self, p: &Point) -> bool {
162        let queue = self.queue.read_at(p);
163        queue.is_empty()
164    }
165
166    fn pop(&self, p: &Point) -> Option<Self::Item> {
167        let results = {
168            let queue = self.queue.read_at(p);
169            queue.pop_front()
170        };
171        match results {
172            None => None,
173            Some((item, queue)) => {
174                self.queue.write_at(queue, p);
175                Some(item)
176            }
177        }
178    }
179
180    fn push(&self, item: Self::Item, p: &Point) {
181        let results = {
182            let queue = self.queue.read_at(p);
183            queue.push_back(item)
184        };
185        self.queue.write_at(results, p);
186    }
187
188    fn push_with_priority(&self, _priority: Self::Priority, _item: Self::Item, _p: &Point) {
189        panic!("Not supported operation");
190    }
191
192    fn remove_by<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
193        where F: Fn(&Self::Item) -> bool + Clone
194    {
195        let results = {
196            let queue = self.queue.read_at(p);
197            queue.remove_by(predicate)
198        };
199        match results {
200            None => None,
201            Some((item, queue)) => {
202                self.queue.write_at(queue, p);
203                Some(item)
204            }
205        }
206    }
207
208    fn exists<F>(&self, predicate: F, p: &Point) -> bool
209        where F: Fn(&Self::Item) -> bool + Clone
210    {
211        let queue = self.queue.read_at(p);
212        queue.exists(predicate)
213    }
214
215    fn find<F>(&self, predicate: F, p: &Point) -> Option<T>
216        where F: Fn(&Self::Item) -> bool + Clone,
217              Self::Item: Clone
218    {
219        let queue = self.queue.read_at(p);
220        queue.find(predicate)
221    }
222}
223
224/// The LCFS queue storage.
225pub struct LCFSStorage<T> {
226
227    /// The underlying queue.
228    queue: RefComp<List<T>>
229}
230
231impl<T> LCFSStorage<T>
232    where T: Clone
233{
234    /// Create a new storage.
235    pub fn new() -> Self {
236        LCFSStorage { queue: RefComp::new(List::Nil) }
237    }
238}
239
240impl<T> QueueStorage for LCFSStorage<T>
241    where T: Clone + 'static
242{
243    type Priority = ();
244    type Item     = T;
245
246    #[inline]
247    fn is_empty(&self, p: &Point) -> bool {
248        let queue = self.queue.read_at(p);
249        queue.is_empty()
250    }
251
252    fn pop(&self, p: &Point) -> Option<Self::Item> {
253        match self.queue.read_at(p) {
254            List::Nil => None,
255            List::Cons(head, tail) => {
256                let tail = tail.deref();
257                self.queue.write_at(tail.clone(), p);
258                Some(head)
259            }
260        }
261    }
262
263    fn push(&self, item: Self::Item, p: &Point) {
264        let results = {
265            let queue = self.queue.read_at(p);
266            List::Cons(item, Rc::new(queue))
267        };
268        self.queue.write_at(results, p);
269    }
270
271    fn push_with_priority(&self, _priority: Self::Priority, _item: Self::Item, _p: &Point) {
272        panic!("Not supported operation");
273    }
274
275    fn remove_by<F>(&self, predicate: F, p: &Point) -> Option<Self::Item>
276        where F: Fn(&Self::Item) -> bool + Clone
277    {
278        let results = {
279            let queue = self.queue.read_at(p);
280            queue.remove_by(predicate)
281        };
282        match results {
283            None => None,
284            Some((item, queue)) => {
285                self.queue.write_at(queue, p);
286                Some(item)
287            }
288        }
289    }
290
291    fn exists<F>(&self, predicate: F, p: &Point) -> bool
292        where F: Fn(&Self::Item) -> bool + Clone
293    {
294        let queue = self.queue.read_at(p);
295        queue.exists(predicate)
296    }
297
298    fn find<F>(&self, predicate: F, p: &Point) -> Option<T>
299        where F: Fn(&Self::Item) -> bool + Clone,
300              Self::Item: Clone
301    {
302        let queue = self.queue.read_at(p);
303        queue.find(predicate)
304    }
305}
306
307/// A queue strategy based on the FCFS (a.k.a. FIFO) strategy. It means "First Come - First Served".
308#[derive(Clone)]
309pub enum FCFSStrategy {
310
311    /// A single instance of the queue strategy.
312    Instance
313}
314
315impl QueueStrategy for FCFSStrategy {
316
317    type Priority = ();
318
319    fn new_storage<T>(&self) -> QueueStorageBox<T, Self::Priority>
320        where T: Clone + 'static
321    {
322        Box::new(FCFSStorage::new())
323    }
324}
325
326/// A queue strategy based on the LCFS (a.k.a. LIFO) strategy. It means "Last Come - First Served".
327#[derive(Clone)]
328pub enum LCFSStrategy {
329
330    /// A single instance of the queue strategy.
331    Instance
332}
333
334impl QueueStrategy for LCFSStrategy {
335
336    type Priority = ();
337
338    fn new_storage<T>(&self) -> QueueStorageBox<T, Self::Priority>
339        where T: Clone + 'static
340    {
341        Box::new(LCFSStorage::new())
342    }
343}
dvcompute_dist/simulation/strategy.rs

dvcompute_dist/simulation/
strategy.rs
