Repository navigation
Expand file tree
/
Copy pathsorted-loop-array.js
More file actions
149 lines (134 loc) · 4.32 KB
/
Copy pathsorted-loop-array.js
File metadata and controls
149 lines (134 loc) · 4.32 KB
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
138
139
140
141
142
143
144
145
146
147
148
149
/**
* Helper class used to hold an array of items in a specific order. This array is safe to modify
* while we loop through it. The class assumes that it holds objects that need to be sorted based
* on one of their fields.
*
* @ignore
*/
class SortedLoopArray {
/**
* The internal array that holds the actual array elements.
*
* @type {object[]}
*/
items = [];
/**
* The number of elements in the array.
*/
length = 0;
/**
* The current index used to loop through the array. This gets modified if we add or remove
* elements from the array while looping. See the example to see how to loop through this
* array.
*/
loopIndex = -1;
/** @private */
_sortBy;
/** @private */
_sortHandler;
/**
* Create a new SortedLoopArray instance.
*
* @param {object} args - Arguments.
* @param {string} args.sortBy - The name of the field that each element in the array is going
* to be sorted by.
* @example
* const array = new SortedLoopArray({ sortBy: 'priority' });
* array.insert(item); // adds item to the right slot based on item.priority
* array.append(item); // adds item to the end of the array
* array.remove(item); // removes item from array
* for (array.loopIndex = 0; array.loopIndex < array.length; array.loopIndex++) {
* // do things with array elements
* // safe to remove and add elements into the array while looping
* }
*/
constructor(args) {
this._sortBy = args.sortBy;
this._sortHandler = this._doSort.bind(this);
}
/**
* Searches for the right spot to insert the specified item.
*
* @param {object} item - The item.
* @returns {number} The index where to insert the item.
* @private
*/
_binarySearch(item) {
let left = 0;
let right = this.items.length - 1;
const search = item[this._sortBy];
let middle;
let current;
while (left <= right) {
middle = Math.floor((left + right) / 2);
current = this.items[middle][this._sortBy];
if (current <= search) {
left = middle + 1;
} else if (current > search) {
right = middle - 1;
}
}
return left;
}
_doSort(a, b) {
const sortBy = this._sortBy;
return a[sortBy] - b[sortBy];
}
/**
* Inserts the specified item into the array at the right index based on the 'sortBy' field
* passed into the constructor. This also adjusts the loopIndex accordingly.
*
* @param {object} item - The item to insert.
*/
insert(item) {
const index = this._binarySearch(item);
this.items.splice(index, 0, item);
this.length++;
if (this.loopIndex >= index) {
this.loopIndex++;
}
}
/**
* Appends the specified item to the end of the array. Faster than insert() as it does not
* binary search for the right index. This also adjusts the loopIndex accordingly.
*
* @param {object} item - The item to append.
*/
append(item) {
this.items.push(item);
this.length++;
}
/**
* Removes the specified item from the array.
*
* @param {object} item - The item to remove.
*/
remove(item) {
const idx = this.items.indexOf(item);
if (idx < 0) return;
this.items.splice(idx, 1);
this.length--;
if (this.loopIndex >= idx) {
this.loopIndex--;
}
}
/**
* Sorts elements in the array based on the 'sortBy' field passed into the constructor. This
* also updates the loopIndex if we are currently looping.
*
* WARNING: Be careful if you are sorting while iterating because if after sorting the array
* element that you are currently processing is moved behind other elements then you might end
* up iterating over elements more than once!
*/
sort() {
// get current item pointed to by loopIndex
const current = (this.loopIndex >= 0 ? this.items[this.loopIndex] : null);
// sort
this.items.sort(this._sortHandler);
// find new loopIndex
if (current !== null) {
this.loopIndex = this.items.indexOf(current);
}
}
}
export { SortedLoopArray };