Debian Codegraph @

closure-library/closure/goog/structs/queue.js

raw
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 };