forked from mberktas/javascript-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
PriorityQueue.js
98 lines (88 loc) · 2.43 KB
/
PriorityQueue.js
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
import MinHeap from '../heap/MinHeap';
import Comparator from '../../utils/comparator/Comparator';
// It is the same as min heap except that when comparing two elements
// we take into account its priority instead of the element's value.
export default class PriorityQueue extends MinHeap {
constructor() {
// Call MinHip constructor first.
super();
// Setup priorities map.
this.priorities = new Map();
// Use custom comparator for heap elements that will take element priority
// instead of element value into account.
this.compare = new Comparator(this.comparePriority.bind(this));
}
/**
* Add item to the priority queue.
* @param {*} item - item we're going to add to the queue.
* @param {number} [priority] - items priority.
* @return {PriorityQueue}
*/
add(item, priority = 0) {
this.priorities.set(item, priority);
super.add(item);
return this;
}
/**
* Remove item from priority queue.
* @param {*} item - item we're going to remove.
* @param {Comparator} [customFindingComparator] - custom function for finding the item to remove
* @return {PriorityQueue}
*/
remove(item, customFindingComparator) {
super.remove(item, customFindingComparator);
this.priorities.delete(item);
return this;
}
/**
* Change priority of the item in a queue.
* @param {*} item - item we're going to re-prioritize.
* @param {number} priority - new item's priority.
* @return {PriorityQueue}
*/
changePriority(item, priority) {
this.remove(item, new Comparator(this.compareValue));
this.add(item, priority);
return this;
}
/**
* Find item by ite value.
* @param {*} item
* @return {Number[]}
*/
findByValue(item) {
return this.find(item, new Comparator(this.compareValue));
}
/**
* Check if item already exists in a queue.
* @param {*} item
* @return {boolean}
*/
hasValue(item) {
return this.findByValue(item).length > 0;
}
/**
* Compares priorities of two items.
* @param {*} a
* @param {*} b
* @return {number}
*/
comparePriority(a, b) {
if (this.priorities.get(a) === this.priorities.get(b)) {
return 0;
}
return this.priorities.get(a) < this.priorities.get(b) ? -1 : 1;
}
/**
* Compares values of two items.
* @param {*} a
* @param {*} b
* @return {number}
*/
compareValue(a, b) {
if (a === b) {
return 0;
}
return a < b ? -1 : 1;
}
}