forked from playcanvas/engine
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsorted-loop-array.js
More file actions
145 lines (132 loc) · 4.97 KB
/
sorted-loop-array.js
File metadata and controls
145 lines (132 loc) · 4.97 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
Object.assign(pc, function () {
'use strict';
/**
* @private
* @class
* @name pc.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
* }
*/
var SortedLoopArray = function (args) {
this._sortBy = args.sortBy;
this.items = [];
this.length = 0;
this.loopIndex = -1;
this._sortHandler = this._doSort.bind(this);
};
/**
* @private
* @function
* @name pc.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.
*/
SortedLoopArray.prototype._binarySearch = function (item) {
var left = 0;
var right = this.items.length - 1;
var search = item[this._sortBy];
var middle;
var 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;
};
SortedLoopArray.prototype._doSort = function (a, b) {
var sortBy = this._sortBy;
return a[sortBy] - b[sortBy];
};
/**
* @private
* @function
* @name pc.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.
*/
SortedLoopArray.prototype.insert = function (item) {
var index = this._binarySearch(item);
this.items.splice(index, 0, item);
this.length++;
if (this.loopIndex >= index) {
this.loopIndex++;
}
};
/**
* @private
* @function
* @name pc.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.
*/
SortedLoopArray.prototype.append = function (item) {
this.items.push(item);
this.length++;
};
/**
* @private
* @function
* @name pc.SortedLoopArray#remove
* @description Removes the specified item from the array.
* @param {object} item - The item to remove.
*/
SortedLoopArray.prototype.remove = function (item) {
var 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 pc.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!
*/
SortedLoopArray.prototype.sort = function () {
// get current item pointed to by loopIndex
var 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);
}
};
return {
SortedLoopArray: SortedLoopArray
};
}());