nxt.priority_queue source code

1 module nxt.priority_queue;
2 
3 /** Priority Queue.
4     `P` is Priority Type. Lower priority means higher precedence in queue.
5     `V` is Value Type.
6  */
7 struct PriorityQueue(P, V, alias pred = "a > b")
8 {
9     import std.container: Array, BinaryHeap;
10     import std.typecons: Tuple;
11 
12     alias E = Tuple!(P, V);     // ElementType
13     alias A = Array!E;          // underlying array storage
14 
15     this(this)
16     {
17         _q = _q.dup;            // needed or prevent foreach from having side-effects
18     }
19 
20     @property bool empty()
21     {
22         return _q.empty;
23     }
24 
25     @property auto ref front()
26     {
27         return _q.front;
28     }
29 
30     @property auto length()
31     {
32         return _q.length;
33     }
34 
35     void insert(E ins)
36     {
37         _q.insert(ins);
38     }
39 
40     void insert(P priority, V value)
41     {
42         insert(E(priority, value));
43     }
44 
45     void popFront()
46     {
47         _q.removeFront();
48     }
49 
50 private:
51     BinaryHeap!(A, pred) _q;
52 }
53 
54 alias PrioQ = PriorityQueue;
55 
56 ///
57 unittest
58 {
59     alias P = int;
60     alias V = string;
61     alias PQ = PriorityQueue!(P, V);
62     PQ pq;
63 
64     import std.typecons: tuple;
65 
66     pq.insert(10, `10`);
67     pq.insert(11, `11`);
68     pq.insert(tuple(3, `3`));
69 
70     foreach (const e; pq) {}    // iteration
71     assert(!pq.empty);          // shouldn't consume queue
72 
73     assert(pq.front == tuple(3, `3`));
74     pq.popFront();
75     assert(pq.front == tuple(10, `10`));
76     pq.popFront();
77     assert(pq.front == tuple(11, `11`));
78     pq.popFront();
79 
80     assert(pq.empty);
81 }