| 1 |
// Copyright 2006 The Closure Library Authors. All Rights Reserved. |
| 2 |
// |
| 3 |
// Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 |
// you may not use this file except in compliance with the License. |
| 5 |
// You may obtain a copy of the License at |
| 6 |
// |
| 7 |
// http://www.apache.org/licenses/LICENSE-2.0 |
| 8 |
// |
| 9 |
// Unless required by applicable law or agreed to in writing, software |
| 10 |
// distributed under the License is distributed on an "AS-IS" BASIS, |
| 11 |
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 |
// See the License for the specific language governing permissions and |
| 13 |
// limitations under the License. |
| 14 |
|
| 15 |
/** |
| 16 |
* @fileoverview Datastructure: Queue. |
| 17 |
* |
| 18 |
* |
| 19 |
* This file provides the implementation of a FIFO Queue structure. |
| 20 |
* API is similar to that of com.google.common.collect.IntQueue |
| 21 |
* |
| 22 |
* The implementation is a classic 2-stack queue. |
| 23 |
* There's a "front" stack and a "back" stack. |
| 24 |
* Items are pushed onto "back" and popped from "front". |
| 25 |
* When "front" is empty, we replace "front" with reverse(back). |
| 26 |
* |
| 27 |
* Example: |
| 28 |
* front back op |
| 29 |
* [] [] enqueue 1 |
| 30 |
* [] [1] enqueue 2 |
| 31 |
* [] [1,2] enqueue 3 |
| 32 |
* [] [1,2,3] dequeue -> ... |
| 33 |
* [3,2,1] [] ... -> 1 |
| 34 |
* [3,2] [] enqueue 4 |
| 35 |
* [3,2] [4] dequeue -> 2 |
| 36 |
* [3] [4] |
| 37 |
* |
| 38 |
* Front and back are simple javascript arrays. We rely on |
| 39 |
* Array.push and Array.pop being O(1) amortized. |
| 40 |
* |
| 41 |
* Note: In V8, queues, up to a certain size, can be implemented |
| 42 |
* just fine using Array.push and Array.shift, but other JavaScript |
| 43 |
* engines do not have the optimization of Array.shift. |
| 44 |
* |
| 45 |
*/ |
| 46 |
|
| 47 |
goog.provide('goog.structs.Queue'); |
| 48 |
|
| 49 |
goog.require('goog.array'); |
| 50 |
|
| 51 |
|
| 52 |
|
| 53 |
/** |
| 54 |
* Class for FIFO Queue data structure. |
| 55 |
* |
| 56 |
* @constructor |
| 57 |
* @template T |
| 58 |
*/ |
| 59 |
goog.structs.Queue = function() { |
| 60 |
/** |
| 61 |
* @private {!Array<T>} Front stack. Items are pop()'ed from here. |
| 62 |
*/ |
| 63 |
this.front_ = []; |
| 64 |
/** |
| 65 |
* @private {!Array<T>} Back stack. Items are push()'ed here. |
| 66 |
*/ |
| 67 |
this.back_ = []; |
| 68 |
}; |
| 69 |
|
| 70 |
|
| 71 |
/** |
| 72 |
* Flips the back stack onto the front stack if front is empty, |
| 73 |
* to prepare for peek() or dequeue(). |
| 74 |
* |
| 75 |
* @private |
| 76 |
*/ |
| 77 |
goog.structs.Queue.prototype.maybeFlip_ = function() { |
| 78 |
if (goog.array.isEmpty(this.front_)) { |
| 79 |
this.front_ = this.back_; |
| 80 |
this.front_.reverse(); |
| 81 |
this.back_ = []; |
| 82 |
} |
| 83 |
}; |
| 84 |
|
| 85 |
|
| 86 |
/** |
| 87 |
* Puts the specified element on this queue. |
| 88 |
* @param {T} element The element to be added to the queue. |
| 89 |
*/ |
| 90 |
goog.structs.Queue.prototype.enqueue = function(element) { |
| 91 |
this.back_.push(element); |
| 92 |
}; |
| 93 |
|
| 94 |
|
| 95 |
/** |
| 96 |
* Retrieves and removes the head of this queue. |
| 97 |
* @return {T} The element at the head of this queue. Returns undefined if the |
| 98 |
* queue is empty. |
| 99 |
*/ |
| 100 |
goog.structs.Queue.prototype.dequeue = function() { |
| 101 |
this.maybeFlip_(); |
| 102 |
return this.front_.pop(); |
| 103 |
}; |
| 104 |
|
| 105 |
|
| 106 |
/** |
| 107 |
* Retrieves but does not remove the head of this queue. |
| 108 |
* @return {T} The element at the head of this queue. Returns undefined if the |
| 109 |
* queue is empty. |
| 110 |
*/ |
| 111 |
goog.structs.Queue.prototype.peek = function() { |
| 112 |
this.maybeFlip_(); |
| 113 |
return goog.array.peek(this.front_); |
| 114 |
}; |
| 115 |
|
| 116 |
|
| 117 |
/** |
| 118 |
* Returns the number of elements in this queue. |
| 119 |
* @return {number} The number of elements in this queue. |
| 120 |
*/ |
| 121 |
goog.structs.Queue.prototype.getCount = function() { |
| 122 |
return this.front_.length + this.back_.length; |
| 123 |
}; |
| 124 |
|
| 125 |
|
| 126 |
/** |
| 127 |
* Returns true if this queue contains no elements. |
| 128 |
* @return {boolean} true if this queue contains no elements. |
| 129 |
*/ |
| 130 |
goog.structs.Queue.prototype.isEmpty = function() { |
| 131 |
return goog.array.isEmpty(this.front_) && goog.array.isEmpty(this.back_); |
| 132 |
}; |
| 133 |
|
| 134 |
|
| 135 |
/** |
| 136 |
* Removes all elements from the queue. |
| 137 |
*/ |
| 138 |
goog.structs.Queue.prototype.clear = function() { |
| 139 |
this.front_ = []; |
| 140 |
this.back_ = []; |
| 141 |
}; |
| 142 |
|
| 143 |
|
| 144 |
/** |
| 145 |
* Returns true if the given value is in the queue. |
| 146 |
* @param {T} obj The value to look for. |
| 147 |
* @return {boolean} Whether the object is in the queue. |
| 148 |
*/ |
| 149 |
goog.structs.Queue.prototype.contains = function(obj) { |
| 150 |
return goog.array.contains(this.front_, obj) || |
| 151 |
goog.array.contains(this.back_, obj); |
| 152 |
}; |
| 153 |
|
| 154 |
|
| 155 |
/** |
| 156 |
* Removes the first occurrence of a particular value from the queue. |
| 157 |
* @param {T} obj Object to remove. |
| 158 |
* @return {boolean} True if an element was removed. |
| 159 |
*/ |
| 160 |
goog.structs.Queue.prototype.remove = function(obj) { |
| 161 |
return goog.array.removeLast(this.front_, obj) || |
| 162 |
goog.array.remove(this.back_, obj); |
| 163 |
}; |
| 164 |
|
| 165 |
|
| 166 |
/** |
| 167 |
* Returns all the values in the queue. |
| 168 |
* @return {!Array<T>} An array of the values in the queue. |
| 169 |
*/ |
| 170 |
goog.structs.Queue.prototype.getValues = function() { |
| 171 |
var res = []; |
| 172 |
// Add the front array in reverse, then the back array. |
| 173 |
for (var i = this.front_.length - 1; i >= 0; --i) { |
| 174 |
res.push(this.front_[i]); |
| 175 |
} |
| 176 |
var len = this.back_.length; |
| 177 |
for (var i = 0; i < len; ++i) { |
| 178 |
res.push(this.back_[i]); |
| 179 |
} |
| 180 |
return res; |
| 181 |
}; |