1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/*
 * Copyright (c) 2018 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

mod binheap;
pub use self::binheap::BinHeap;

pub trait ItemPriQueue<K, V> {
    /// Handle for an item in the queue.
    type Item;

    /// Return `true` iff the queue contains no element.
    fn is_empty(&self) -> bool;

    /// Remove all elements from the queue.
    fn clear(&mut self);

    /// Push the element with given `key` and `value` onto the queue.
    ///
    /// Return a handle referencing the element. That handle can be used in a
    /// subsequent call to `decrease_key`.
    fn push(&mut self, key: K, value: V) -> Self::Item;

    /// Decrease the value of some item in the queue.
    ///
    /// Returns `true` if the new value is smaller than the old one.
    fn decrease_key(&mut self, item: &mut Self::Item, value: V) -> bool;

    /// Remove and return the element with the smallest value from the queue or `None` if
    /// the queue is empty.
    fn pop_min(&mut self) -> Option<(K, V)>;

    /// Return the current value associated with some item in the queue.
    fn value(&self, item: &Self::Item) -> &V;
}

impl<'a, P, K, V> ItemPriQueue<K, V> for &'a mut P
where
    P: ItemPriQueue<K, V>,
{
    type Item = P::Item;

    fn is_empty(&self) -> bool {
        (**self).is_empty()
    }

    fn clear(&mut self) {
        (**self).clear()
    }

    fn push(&mut self, key: K, value: V) -> Self::Item {
        (**self).push(key, value)
    }

    fn decrease_key(&mut self, item: &mut Self::Item, value: V) -> bool {
        (**self).decrease_key(item, value)
    }

    fn pop_min(&mut self) -> Option<(K, V)> {
        (**self).pop_min()
    }

    fn value(&self, item: &Self::Item) -> &V {
        (**self).value(item)
    }
}