1 | /**
|
2 | * This very basic implementation of a priority queue is used to select the
|
3 | * next node of the graph to walk to.
|
4 | *
|
5 | * The queue is always sorted to have the least expensive node on top. Some
|
6 | * comodoty methods are also implemented.
|
7 | *
|
8 | * You should **never** modify the queue directly, but only using the methods
|
9 | * provided by the class.
|
10 | */
|
11 | class PriorityQueue {
|
12 |
|
13 | /**
|
14 | * Creates a new empty priority queue
|
15 | */
|
16 | constructor() {
|
17 | // The `keys` set is used to greately improve the speed at which we can
|
18 | // check the presence of a value in the queue
|
19 | this.keys = new Set();
|
20 | this.queue = [];
|
21 | }
|
22 |
|
23 | /**
|
24 | * Sort the queue to have the least expensive node to visit on top
|
25 | *
|
26 | * @private
|
27 | */
|
28 | sort() {
|
29 | this.queue.sort((a, b) => a.priority - b.priority);
|
30 | }
|
31 |
|
32 | /**
|
33 | * Sets a priority for a key in the queue.
|
34 | * Inserts it in the queue if it does not already exists.
|
35 | *
|
36 | * @param {any} key Key to update or insert
|
37 | * @param {number} value Priority of the key
|
38 | * @return {number} Size of the queue
|
39 | */
|
40 | set(key, value) {
|
41 | const priority = Number(value);
|
42 | if (isNaN(priority)) throw new TypeError('"priority" must be a number');
|
43 |
|
44 | if (!this.keys.has(key)) {
|
45 | // Insert a new entry if the key is not already in the queue
|
46 | this.keys.add(key);
|
47 | this.queue.push({ key, priority });
|
48 | } else {
|
49 | // Update the priority of an existing key
|
50 | this.queue.map((element) => {
|
51 | if (element.key === key) {
|
52 | Object.assign(element, { priority });
|
53 | }
|
54 |
|
55 | return element;
|
56 | });
|
57 | }
|
58 |
|
59 | this.sort();
|
60 | return this.queue.length;
|
61 | }
|
62 |
|
63 | /**
|
64 | * The next method is used to dequeue a key:
|
65 | * It removes the first element from the queue and returns it
|
66 | *
|
67 | * @return {object} First priority queue entry
|
68 | */
|
69 | next() {
|
70 | const element = this.queue.shift();
|
71 |
|
72 | // Remove the key from the `_keys` set
|
73 | this.keys.delete(element.key);
|
74 |
|
75 | return element;
|
76 | }
|
77 |
|
78 | /**
|
79 | * @return {boolean} `true` when the queue is empty
|
80 | */
|
81 | isEmpty() {
|
82 | return Boolean(this.queue.length === 0);
|
83 | }
|
84 |
|
85 | /**
|
86 | * Check if the queue has a key in it
|
87 | *
|
88 | * @param {any} key Key to lookup
|
89 | * @return {boolean}
|
90 | */
|
91 | has(key) {
|
92 | return this.keys.has(key);
|
93 | }
|
94 |
|
95 | /**
|
96 | * Get the element in the queue with the specified key
|
97 | *
|
98 | * @param {any} key Key to lookup
|
99 | * @return {object}
|
100 | */
|
101 | get(key) {
|
102 | return this.queue.find(element => element.key === key);
|
103 | }
|
104 |
|
105 | }
|
106 |
|
107 | module.exports = PriorityQueue;
|