dvcompute_branch/simulation/utils/
priority_queue.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;
8
9/// An immutable priority queue as described in book
10/// "Algorithms: a functional programming approach" by
11/// Fethi Rabhi and Guy Lapalme.
12#[derive(Clone)]
13pub enum PriorityQueue<K, V> {
14
15    /// The queue item.
16    QueueItem(Rc<PriorityQueueItem<K, V>>),
17
18    /// The empty queue.
19    EmptyQueue
20}
21
22/// An immutable queue item.
23#[derive(Clone)]
24pub struct PriorityQueueItem<K, V> {
25
26    /// The queue size.
27    len: usize,
28
29    /// The item key.
30    key: K,
31
32    /// The item value.
33    val: V,
34
35    /// The item rank.
36    rank: usize,
37
38    /// The left branch.
39    left: PriorityQueue<K, V>,
40
41    /// The right branch.
42    right: PriorityQueue<K, V>,
43}
44
45impl<K, V> PriorityQueue<K, V> where K: PartialOrd + Copy, V: Clone {
46
47    /// Create a new priority queue.
48    #[inline]
49    pub fn new() -> Self {
50        PriorityQueue::EmptyQueue
51    }
52
53    /// The size of the queue.
54    #[inline]
55    pub fn len(&self) -> usize {
56        match self {
57            PriorityQueue::QueueItem(ref item) => item.len,
58            PriorityQueue::EmptyQueue => 0
59        }
60    }
61
62    /// Test whether the queue is empty.
63    #[inline]
64    pub fn is_empty(&self) -> bool {
65        match self {
66            PriorityQueue::QueueItem(_) => false,
67            PriorityQueue::EmptyQueue => true
68        }
69    }
70
71    /// Enqueue a new item with the specified key and value.
72    #[inline]
73    pub fn enqueue(&self, key: K, val: V) -> Self {
74        let item = PriorityQueueItem {
75            len: 1,
76            key: key,
77            val: val,
78            rank: 1,
79            left: PriorityQueue::EmptyQueue,
80            right: PriorityQueue::EmptyQueue
81        };
82        let queue = PriorityQueue::QueueItem(Rc::new(item));
83        self.merge(&queue)
84    }
85
86    /// Dequeue the top element with minimal key.
87    #[inline]
88    pub fn dequeue(&self) -> Self {
89        match self {
90            PriorityQueue::QueueItem(ref item) => {
91                item.left.merge(&item.right)
92            },
93            PriorityQueue::EmptyQueue => {
94                panic!("The queue is empty!")
95            }
96        }
97    }
98
99    /// Return the minimal key if the priority queue is not empty.
100    #[inline]
101    pub fn front_key(&self) -> Option<&K> {
102        match self {
103            PriorityQueue::QueueItem(ref item) => Some(&item.key),
104            PriorityQueue::EmptyQueue => None
105        }
106    }
107
108    /// Return the front value if the priority queue is not empty.
109    #[inline]
110    pub fn front_val(&self) -> Option<&V> {
111        match self {
112            PriorityQueue::QueueItem(ref item) => Some(&item.val),
113            PriorityQueue::EmptyQueue => None
114        }
115    }
116
117    /// Return the front key and value if the priority queue is not empty.
118    #[inline]
119    pub fn front(&self) -> Option<(&K, &V)> {
120        match self {
121            PriorityQueue::QueueItem(ref item) => Some((&item.key, &item.val)),
122            PriorityQueue::EmptyQueue => None
123        }
124    }
125
126    /// Return the queue rank.
127    #[inline]
128    fn rank(&self) -> usize {
129        match self {
130            PriorityQueue::QueueItem(ref item) => item.rank,
131            PriorityQueue::EmptyQueue => 0
132        }
133    }
134
135    /// Construct a new priority queue.
136    fn make(key: K, val: V, left: Self, right: Self) -> Self {
137        let len = left.len() + right.len() + 1;
138        if left.rank() >= right.rank() {
139            let item = PriorityQueueItem {
140                len: len,
141                key: key,
142                val: val,
143                rank: right.rank() + 1,
144                left: left,
145                right: right
146            };
147            PriorityQueue::QueueItem(Rc::new(item))
148        } else {
149            let item = PriorityQueueItem {
150                len: len,
151                key: key,
152                val: val,
153                rank: left.rank() + 1,
154                left: right,
155                right: left
156            };
157            PriorityQueue::QueueItem(Rc::new(item))
158        }
159    }
160
161    /// Merge two queues.
162    fn merge(&self, other: &Self) -> Self {
163        match (self, other) {
164            (PriorityQueue::QueueItem(ref r1), PriorityQueue::QueueItem(ref r2)) => {
165                if r1.key <= r2.key {
166                    let left  = r1.left.clone();
167                    let right = r1.right.merge(other);
168                    PriorityQueue::make(r1.key, r1.val.clone(), left, right)
169                } else {
170                    let left  = r2.left.clone();
171                    let right = self.merge(&r2.right);
172                    PriorityQueue::make(r2.key, r2.val.clone(), left, right)
173                }
174            },
175            (PriorityQueue::QueueItem(ref r1), PriorityQueue::EmptyQueue) => {
176                PriorityQueue::QueueItem(r1.clone())
177            },
178            (PriorityQueue::EmptyQueue, PriorityQueue::QueueItem(ref r2)) => {
179                PriorityQueue::QueueItem(r2.clone())
180            },
181            (PriorityQueue::EmptyQueue, PriorityQueue::EmptyQueue) => {
182                PriorityQueue::EmptyQueue
183            }
184        }
185    }
186}
dvcompute_branch/simulation/utils/priority_queue.rs

dvcompute_branch/simulation/utils/
priority_queue.rs
