/
utils.ts
75 lines (63 loc) · 1.96 KB
/
utils.ts
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
export class SortedList<T> {
constructor(
private array: Array<T>,
private compare: (a: T, b: T) => number
) {
this.array.sort(compare);
}
public pop() {
return this.array.shift();
}
public insert(element: T) {
let high = this.array.length - 1;
let low = 0;
let mid;
let highElement, lowElement, midElement;
let compareHigh, compareLow, compareMid;
let targetIndex;
while (true) {
if (high < low) {
targetIndex = low;
break;
}
mid = Math.floor((low + high) / 2);
highElement = this.array[high];
lowElement = this.array[low];
midElement = this.array[mid];
compareHigh = this.compare(element, highElement);
compareLow = this.compare(element, lowElement);
compareMid = this.compare(element, midElement);
if (low === high) {
// Target index is either to the left or right of element at low
if (compareLow <= 0) targetIndex = low;
else targetIndex = low + 1;
break;
}
if (compareHigh >= 0) {
// Target index is to the right of high
low = high;
continue;
}
if (compareLow <= 0) {
// Target index is to the left of low
high = low;
continue;
}
if (compareMid <= 0) {
// Target index is to the left of mid
high = mid;
continue;
}
// Target index is to the right of mid
low = mid + 1;
}
this.array.splice(targetIndex, 0, element);
return targetIndex;
}
public length() {
return this.array.length;
}
public toArray() {
return this.array;
}
}