-
Notifications
You must be signed in to change notification settings - Fork 0
/
utils.js
137 lines (116 loc) · 2.76 KB
/
utils.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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
function topp(a, b) {
if (a - 1 >= 0) {
return createVector(a - 1, b);
}
}
function right(a, b) {
if (b + 1 <= rows - 1) {
return createVector(a, b + 1);
}
}
function bottom(a, b) {
if (a + 1 <= cols - 1) {
return createVector(a + 1, b);
}
}
function left(a, b) {
if (b - 1 >= 0) {
return createVector(a, b - 1);
}
}
// extending elements of a second array to the main array
function extend(mainArr, arr) {
for (var element of arr) {
mainArr.push(element);
}
return mainArr;
}
// Priority Queue
// push element in the heap
function heapPush(arr, item) {
arr.push(item);
}
function heapPop(arr) {
// create a temporary array for storing the priorities
let temp = [];
for (let element of arr) {
temp.push(element.priority);
}
// find the most prior element's index from the list
let c = temp.findIndex((x) => Math.min.apply(Math, temp) === x);
return arr.splice(c, 1)[0].value; // delete the most prior element and return it
}
function delete_(arr, key) {
let temp = [];
for (let element of arr) {
temp.push(element.value);
}
// find the most prior element's index from the list
let c = temp.findIndex((x) => key === x);
if (c >= 0) {
return arr.splice(c, 1); // delete the element from the heap
}
}
function contains(arr, key) {
let isPresent = false;
for (let element of arr) {
if (key.state.x === element.value.state.x && key.state.y === element.value.state.y) {
isPresent = true;
}
}
return isPresent;
}
// Item Class
class Item {
constructor(priority, value) {
this.priority = priority;
this.value = value;
}
}
class PriorityQueue {
constructor(order = "min", f = (x) => x) {
this.heap = [];
if (order === "min") {
this.f = f;
} else if (order === "max") {
this.f = (x) => -f(x);
} else {
console.log("Order must be min or max");
}
}
append(val) {
// Insert element in the priority queue
let item = new Item(this.f(val), val);
heapPush(this.heap, item);
}
pop() {
// Returns the most prior item and remove it from the heap
if (this.heap.length > 0) {
return heapPop(this.heap);
} else {
console.log("Trying to pop from empty PriorityQueue.");
}
}
extend(items) {
for (let item of items) {
this.append(item);
}
}
length() {
return this.heap.length;
}
include(key) {
let isPresent = contains(this.heap, key);
return isPresent;
}
getItem(key) {
for (let element of this.heap) {
if (element.value === key) {
return element.priority;
}
}
}
deleteItem(key) {
delete_(this.heap, key);
}
}