dvcompute 2.0.0

Discrete event simulation library (sequential simulation)
Documentation 
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

// 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/.

/// The heap-based imperative priority queue.
pub struct PriorityQueue<K, V> {

    /// The keys.
    keys: Vec<K>,

    /// The values.
    vals: Vec<V>,

    /// The queue size.
    size: usize
}

impl<K, V> PriorityQueue<K, V> where K: PartialOrd + Copy {

    /// Create a new priority queue.
    pub fn new() -> PriorityQueue<K, V> {
        let keys = Vec::with_capacity(11);
        let vals = Vec::with_capacity(11);
        let size = 0;
        PriorityQueue { keys: keys, vals: vals, size: size }
    }

    /// Return the queue size.
    pub fn len(&self) -> usize {
        self.keys.len()
    }

    /// Enqueue a new item with the specified key and value.
    pub fn enqueue(&mut self, key: K, val: V) {
        self.keys.push(key);
        self.vals.push(val);
        self.size += 1;
        let mut i = self.size - 1;
        let k = key;
        loop {
            if i == 0 {
                break;
            } else {
                let n = (i - 1) >> 1;
                if k >= self.keys[n] {
                    break;
                } else {
                    self.keys.swap(i, n);
                    self.vals.swap(i, n);
                    i = n;
                }
            }
        }
    }

    /// Dequeue the top element with minimal key.
    pub fn dequeue(&mut self) -> (K, V) {
        assert!(self.size > 0, "The priority queue cannot be empty when dequeueing");
        let k0 = self.keys.swap_remove(0);
        let v0 = self.vals.swap_remove(0);
        self.size -= 1;
        if self.size > 0 {
            let mut i = 0;
            let k = self.keys[0];
            loop {
                if i >= self.size >> 1 {
                    break;
                } else {
                    let n  = (i << 1) + 1;
                    let n2 = n + 1;
                    let n  =
                        if n2 < self.size && self.keys[n] > self.keys[n2] {
                            n2
                        } else {
                            n
                        };
                    if k <= self.keys[n] {
                        break;
                    } else {
                        self.keys.swap(i, n);
                        self.vals.swap(i, n);
                        i = n;
                    }
                }
            }
        }
        (k0, v0)
    }

    /// Return the minimal key if the priority queue is not empty.
    pub fn minimal_key(&self) -> Option<&K> {
        self.keys.get(0)
    }

    /// Test whether the priority queue is empty.
    pub fn is_empty(&self) -> bool {
        self.size == 0
    }
}