Created
October 11, 2019 09:55
-
-
Save jaycosaur/d492b1794013ba7a26ca32a4a61fc043 to your computer and use it in GitHub Desktop.
Typescript implementation of overwriting ring buffer with memory of insertion position for gets. Useful for a rolling video frame / audio frame cache requiring lookups.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// extension of classical overwriting ring buffer that holds an incremental counter that can be indexed | |
// this should not be used for read heavy write infrequent streams (as a map would be a much mor effective implementation) | |
// this could be used for write heavy read infrequent streams | |
export class OverwritingRingBuffer<T> { | |
private buffer: T[]; | |
private bufferLength: number; | |
private pointer: number; | |
private counter: number; | |
constructor(bufferLength: number) { | |
if (bufferLength <= 0) { | |
throw new Error( | |
'a ring buffer is pretty useless unless it has a length > 0' | |
); | |
} | |
this.buffer = []; | |
this.pointer = 0; | |
this.bufferLength = bufferLength; | |
this.counter = 0; | |
} | |
public push(element: T): void { | |
// increment counter | |
this.counter++; | |
if (this.buffer.length === this.bufferLength) { | |
this.buffer[this.pointer] = element; | |
} else { | |
this.buffer.push(element); | |
} | |
// advance pointer | |
this.pointer = (this.pointer + 1) % this.bufferLength; | |
} | |
// indexes start from 0 ie first element added is at index 0 | |
public get(index: number): T | null { | |
// index has not happened yet | |
if (index >= this.counter) { | |
return null; | |
} | |
// index has already been overwritten | |
if (this.counter - index > this.bufferLength) { | |
return null; | |
} | |
return this.buffer[ | |
(this.bufferLength + this.pointer - (this.counter - index)) % | |
this.bufferLength | |
]; | |
} | |
// Gets the last element added to the buffer | |
public getLast(): T | null { | |
if (this.counter > 0) { | |
return this.buffer[ | |
(this.pointer + this.bufferLength - 1) % this.bufferLength | |
]; | |
} | |
return null; | |
} | |
// reset buffer | |
public reset(): void { | |
this.buffer = []; | |
this.pointer = 0; | |
this.counter = 0; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment