Repository navigation
Expand file tree
/
Copy pathsorted-loop-array.js
More file actions
139 lines (129 loc) · 4.56 KB
/
Copy pathsorted-loop-array.js
File metadata and controls
139 lines (129 loc) · 4.56 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
/**
* @private
* @class
* @name SortedLoopArray
* @classdesc 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.
* @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.
* @property {number} loopIndex 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.
* @property {number} length The number of elements in the array.
* @property {object[]} items The internal array that holds the actual array elements.
* @example
* var array = new pc.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
* }
*/
class SortedLoopArray {
constructor(args) {
this._sortBy = args.sortBy;
this.items = [];
this.length = 0;
this.loopIndex = -1;
this._sortHandler = this._doSort.bind(this);
}
/**
* @private
* @function
* @name SortedLoopArray#_binarySearch
* @description Searches for the right spot to insert the specified item.
* @param {object} item - The item.
* @returns {number} The index where to insert the item.
*/
_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];
}
/**
* @private
* @function
* @name SortedLoopArray#insert
* @description 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++;
}
}
/**
* @private
* @function
* @name SortedLoopArray#append
* @description 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++;
}
/**
* @private
* @function
* @name SortedLoopArray#remove
* @description 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--;
}
}
/**
* @private
* @function
* @name SortedLoopArray#sort
* @description 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 };