rs_graph/collections/
priqueue.rs

1/*
2 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
3 *
4 * This program is free software: you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation, either version 3 of the
7 * License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
16 */
17
18mod binheap;
19pub use self::binheap::BinHeap;
20
21pub trait ItemPriQueue<K, V> {
22    /// Handle for an item in the queue.
23    type Item;
24
25    /// Return `true` iff the queue contains no element.
26    fn is_empty(&self) -> bool;
27
28    /// Remove all elements from the queue.
29    fn clear(&mut self);
30
31    /// Push the element with given `key` and `value` onto the queue.
32    ///
33    /// Return a handle referencing the element. That handle can be used in a
34    /// subsequent call to `decrease_key`.
35    fn push(&mut self, key: K, value: V) -> Self::Item;
36
37    /// Decrease the value of some item in the queue.
38    ///
39    /// Returns `true` if the new value is smaller than the old one.
40    fn decrease_key(&mut self, item: &mut Self::Item, value: V) -> bool;
41
42    /// Remove and return the element with the smallest value from the queue or `None` if
43    /// the queue is empty.
44    fn pop_min(&mut self) -> Option<(K, V)>;
45
46    /// Return the current value associated with some item in the queue.
47    fn value(&self, item: &Self::Item) -> &V;
48}
49
50impl<'a, P, K, V> ItemPriQueue<K, V> for &'a mut P
51where
52    P: ItemPriQueue<K, V>,
53{
54    type Item = P::Item;
55
56    fn is_empty(&self) -> bool {
57        (**self).is_empty()
58    }
59
60    fn clear(&mut self) {
61        (**self).clear()
62    }
63
64    fn push(&mut self, key: K, value: V) -> Self::Item {
65        (**self).push(key, value)
66    }
67
68    fn decrease_key(&mut self, item: &mut Self::Item, value: V) -> bool {
69        (**self).decrease_key(item, value)
70    }
71
72    fn pop_min(&mut self) -> Option<(K, V)> {
73        (**self).pop_min()
74    }
75
76    fn value(&self, item: &Self::Item) -> &V {
77        (**self).value(item)
78    }
79}
rs_graph/collections/priqueue.rs

rs_graph/collections/
priqueue.rs
