/**

* @license

* Copyright 2018 Google LLC. All Rights Reserved.

* Licensed under the Apache License, Version 2.0 (the "License");

* you may not use this file except in compliance with the License.

* You may obtain a copy of the License at

*

* http://www.apache.org/licenses/LICENSE-2.0

*

* Unless required by applicable law or agreed to in writing, software

* distributed under the License is distributed on an "AS IS" BASIS,

* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

* See the License for the specific language governing permissions and

* limitations under the License.

*

* =============================================================================

*/

/**

* A ring buffer, providing O(1) FIFO, LIFO, and related operations.

*/

export class RingBuffer<T> {

// Note we store the indices in the range 0 <= index < 2*capacity.

// This allows us to distinguish the full from the empty case.

// See https://www.snellman.net/blog/archive/2016-12-13-ring-buffers/

protected begin = 0; // inclusive

protected end = 0; // exclusive

protected doubledCapacity: number;

protected data: T[];

/**

* Constructs a `RingBuffer`.

* @param capacity The number of items that the buffer can accomodate.

*/

constructor(public capacity: number) {

if (capacity == null) {

throw new RangeError('Can\'t create a ring buffer of unknown capacity.');

}

if (capacity < 1) {

throw new RangeError('Can\'t create ring buffer of capacity < 1.');

}

this.data = new Array<T>(capacity);

this.doubledCapacity = 2 * capacity;

}

/**

* Map any index into the range 0 <= index < 2*capacity.

*/

protected wrap(index: number) {

// don't trust % on negative numbers

while (index < 0) {

index += this.doubledCapacity;

}

return index % this.doubledCapacity;

}

protected get(index: number) {

if (index < 0) {

throw new RangeError('Can\'t get item at a negative index.');

}

return this.data[index % this.capacity];

}

protected set(index: number, value: T) {

if (index < 0) {

throw new RangeError('Can\'t set item at a negative index.');

}

this.data[index % this.capacity] = value;

}

/**

* Returns the current number of items in the buffer.

*/

length(): number {

let length = this.end - this.begin;

if (length < 0) {

length = this.doubledCapacity + length;

}

return length;

}

/**

* Reports whether the buffer is full.

* @returns true if the number of items in the buffer equals its capacity, and

* false otherwise.

*/

isFull() {

return this.length() === this.capacity;

}

/**

* Reports whether the buffer is empty.

* @returns true if the number of items in the buffer equals zero, and

* false otherwise.

*/

isEmpty() {

return this.length() === 0;

}

/**

* Adds an item to the end of the buffer.

*/

push(value: T) {

if (this.isFull()) {

throw new RangeError('Ring buffer is full.');

}

this.set(this.end, value);

this.end = this.wrap(this.end + 1);

}

/**

* Adds many items to the end of the buffer, in order.

*/

pushAll(values: T[]) {

for (const value of values) {

this.push(value);

}

}

/**

* Removes and returns the last item in the buffer.

*/

pop(): T {

if (this.isEmpty()) {

throw new RangeError('Ring buffer is empty.');

}

this.end = this.wrap(this.end - 1);

const result = this.get(this.end);

this.set(this.end, undefined);

return result;

}

/**

* Adds an item to the beginning of the buffer.

*/

unshift(value: T) {

if (this.isFull()) {

throw new RangeError('Ring buffer is full.');

}

this.begin = this.wrap(this.begin - 1);

this.set(this.begin, value);

}

/**

* Removes and returns the first item in the buffer.

*/

shift(): T {

if (this.isEmpty()) {

throw new RangeError('Ring buffer is empty.');

}

const result = this.get(this.begin);

this.set(this.begin, undefined);

this.begin = this.wrap(this.begin + 1);

return result;

}

/**

* Removes and returns a specific item in the buffer, and moves the last item

* to the vacated slot. This is useful for implementing a shuffling stream.

* Note that this operation necessarily scrambles the original order.

*

* @param relativeIndex: the index of the item to remove, relative to the

* first item in the buffer (e.g., hiding the ring nature of the underlying

* storage).

*/

shuffleExcise(relativeIndex: number): T {

if (this.isEmpty()) {

throw new RangeError('Ring buffer is empty.');

}

const index = this.wrap(this.begin + relativeIndex);

const result = this.get(index);

this.set(index, this.pop());

return result;

}

}