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