Debian Codegraph @

closure-library/closure/goog/structs/circularbuffer.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 /**
17 * @fileoverview Datastructure: Circular Buffer.
18 *
19 * Implements a buffer with a maximum size. New entries override the oldest
20 * entries when the maximum size has been reached.
21 *
22 */
23
24
25 goog.provide('goog.structs.CircularBuffer');
26
27
28
29 /**
30 * Class for CircularBuffer.
31 * @param {number=} opt_maxSize The maximum size of the buffer.
32 * @constructor
33 * @template T
34 */
35 goog.structs.CircularBuffer = function(opt_maxSize) {
36 /**
37 * Index of the next element in the circular array structure.
38 * @private {number}
39 */
40 this.nextPtr_ = 0;
41
42 /**
43 * Maximum size of the the circular array structure.
44 * @private {number}
45 */
46 this.maxSize_ = opt_maxSize || 100;
47
48 /**
49 * Underlying array for the CircularBuffer.
50 * @private {!Array<T>}
51 */
52 this.buff_ = [];
53 };
54
55
56 /**
57 * Adds an item to the buffer. May remove the oldest item if the buffer is at
58 * max size.
59 * @param {T} item The item to add.
60 * @return {T|undefined} The removed old item, if the buffer is at max size.
61 * Return undefined, otherwise.
62 */
63 goog.structs.CircularBuffer.prototype.add = function(item) {
64 var previousItem = this.buff_[this.nextPtr_];
65 this.buff_[this.nextPtr_] = item;
66 this.nextPtr_ = (this.nextPtr_ + 1) % this.maxSize_;
67 return previousItem;
68 };
69
70
71 /**
72 * Returns the item at the specified index.
73 * @param {number} index The index of the item. The index of an item can change
74 * after calls to {@code add()} if the buffer is at maximum size.
75 * @return {T} The item at the specified index.
76 */
77 goog.structs.CircularBuffer.prototype.get = function(index) {
78 index = this.normalizeIndex_(index);
79 return this.buff_[index];
80 };
81
82
83 /**
84 * Sets the item at the specified index.
85 * @param {number} index The index of the item. The index of an item can change
86 * after calls to {@code add()} if the buffer is at maximum size.
87 * @param {T} item The item to add.
88 */
89 goog.structs.CircularBuffer.prototype.set = function(index, item) {
90 index = this.normalizeIndex_(index);
91 this.buff_[index] = item;
92 };
93
94
95 /**
96 * Returns the current number of items in the buffer.
97 * @return {number} The current number of items in the buffer.
98 */
99 goog.structs.CircularBuffer.prototype.getCount = function() {
100 return this.buff_.length;
101 };
102
103
104 /**
105 * @return {boolean} Whether the buffer is empty.
106 */
107 goog.structs.CircularBuffer.prototype.isEmpty = function() {
108 return this.buff_.length == 0;
109 };
110
111
112 /**
113 * Empties the current buffer.
114 */
115 goog.structs.CircularBuffer.prototype.clear = function() {
116 this.buff_.length = 0;
117 this.nextPtr_ = 0;
118 };
119
120
121 /**
122 * @return {!Array<T>} The values in the buffer ordered from oldest to newest.
123 */
124 goog.structs.CircularBuffer.prototype.getValues = function() {
125 // getNewestValues returns all the values if the maxCount parameter is the
126 // count
127 return this.getNewestValues(this.getCount());
128 };
129
130
131 /**
132 * Returns the newest values in the buffer up to {@code count}.
133 * @param {number} maxCount The maximum number of values to get. Should be a
134 * positive number.
135 * @return {!Array<T>} The newest values in the buffer up to {@code count}. The
136 * values are ordered from oldest to newest.
137 */
138 goog.structs.CircularBuffer.prototype.getNewestValues = function(maxCount) {
139 var l = this.getCount();
140 var start = this.getCount() - maxCount;
141 var rv = [];
142 for (var i = start; i < l; i++) {
143 rv.push(this.get(i));
144 }
145 return rv;
146 };
147
148
149 /** @return {!Array<number>} The indexes in the buffer. */
150 goog.structs.CircularBuffer.prototype.getKeys = function() {
151 var rv = [];
152 var l = this.getCount();
153 for (var i = 0; i < l; i++) {
154 rv[i] = i;
155 }
156 return rv;
157 };
158
159
160 /**
161 * Whether the buffer contains the key/index.
162 * @param {number} key The key/index to check for.
163 * @return {boolean} Whether the buffer contains the key/index.
164 */
165 goog.structs.CircularBuffer.prototype.containsKey = function(key) {
166 return key < this.getCount();
167 };
168
169
170 /**
171 * Whether the buffer contains the given value.
172 * @param {T} value The value to check for.
173 * @return {boolean} Whether the buffer contains the given value.
174 */
175 goog.structs.CircularBuffer.prototype.containsValue = function(value) {
176 var l = this.getCount();
177 for (var i = 0; i < l; i++) {
178 if (this.get(i) == value) {
179 return true;
180 }
181 }
182 return false;
183 };
184
185
186 /**
187 * Returns the last item inserted into the buffer.
188 * @return {T|null} The last item inserted into the buffer,
189 * or null if the buffer is empty.
190 */
191 goog.structs.CircularBuffer.prototype.getLast = function() {
192 if (this.getCount() == 0) {
193 return null;
194 }
195 return this.get(this.getCount() - 1);
196 };
197
198
199 /**
200 * Helper function to convert an index in the number space of oldest to
201 * newest items in the array to the position that the element will be at in the
202 * underlying array.
203 * @param {number} index The index of the item in a list ordered from oldest to
204 * newest.
205 * @return {number} The index of the item in the CircularBuffer's underlying
206 * array.
207 * @private
208 */
209 goog.structs.CircularBuffer.prototype.normalizeIndex_ = function(index) {
210 if (index >= this.buff_.length) {
211 throw new Error('Out of bounds exception');
212 }
213
214 if (this.buff_.length < this.maxSize_) {
215 return index;
216 }
217
218 return (this.nextPtr_ + Number(index)) % this.maxSize_;
219 };