-
Notifications
You must be signed in to change notification settings - Fork 3.5k
/
Queue.js
134 lines (118 loc) · 3.22 KB
/
Queue.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
define([
'./defineProperties'
], function(
defineProperties) {
'use strict';
/**
* A queue that can enqueue items at the end, and dequeue items from the front.
*
* @alias Queue
* @constructor
*/
function Queue() {
this._array = [];
this._offset = 0;
this._length = 0;
}
defineProperties(Queue.prototype, {
/**
* The length of the queue.
*
* @memberof Queue.prototype
*
* @type {Number}
* @readonly
*/
length : {
get : function() {
return this._length;
}
}
});
/**
* Enqueues the specified item.
*
* @param {*} item The item to enqueue.
*/
Queue.prototype.enqueue = function(item) {
this._array.push(item);
this._length++;
};
/**
* Dequeues an item. Returns undefined if the queue is empty.
*
* @returns {*} The the dequeued item.
*/
Queue.prototype.dequeue = function() {
if (this._length === 0) {
return undefined;
}
var array = this._array;
var offset = this._offset;
var item = array[offset];
array[offset] = undefined;
offset++;
if ((offset > 10) && (offset * 2 > array.length)) {
//compact array
this._array = array.slice(offset);
offset = 0;
}
this._offset = offset;
this._length--;
return item;
};
/**
* Returns the item at the front of the queue. Returns undefined if the queue is empty.
*
* @returns {*} The item at the front of the queue.
*/
Queue.prototype.peek = function() {
if (this._length === 0) {
return undefined;
}
return this._array[this._offset];
};
/**
* Check whether this queue contains the specified item.
*
* @param {*} item The item to search for.
*/
Queue.prototype.contains = function(item) {
return this._array.indexOf(item) !== -1;
};
/**
* Remove all items from the queue.
*/
Queue.prototype.clear = function() {
this._array.length = this._offset = this._length = 0;
};
/**
* Sort the items in the queue in-place.
*
* @param {Queue~Comparator} compareFunction A function that defines the sort order.
*/
Queue.prototype.sort = function(compareFunction) {
if (this._offset > 0) {
//compact array
this._array = this._array.slice(this._offset);
this._offset = 0;
}
this._array.sort(compareFunction);
};
/**
* A function used to compare two items while sorting a queue.
* @callback Queue~Comparator
*
* @param {*} a An item in the array.
* @param {*} b An item in the array.
* @returns {Number} Returns a negative value if <code>a</code> is less than <code>b</code>,
* a positive value if <code>a</code> is greater than <code>b</code>, or
* 0 if <code>a</code> is equal to <code>b</code>.
*
* @example
* function compareNumbers(a, b) {
* return a - b;
* }
*/
return Queue;
});