blob: 264851baf4b092797b1a6732a1d721eabffb58f8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
// Forked from https://github.com/stardazed/sd-streams/tree/8928cf04b035fd02fb1340b7eb541c76be37e546
// Copyright (c) 2018-Present by Arthur Langereis - @zenmumbler MIT
/**
* streams/queue - simple queue type with chunked array backing
* Part of Stardazed
* (c) 2018-Present by Arthur Langereis - @zenmumbler
* https://github.com/stardazed/sd-streams
*/
const CHUNK_SIZE = 16384;
export interface Queue<T> {
push(t: T): void;
shift(): T | undefined;
front(): T | undefined;
readonly length: number;
}
export class QueueImpl<T> implements Queue<T> {
private readonly chunks_: T[][];
private readChunk_: T[];
private writeChunk_: T[];
private length_: number;
constructor() {
this.chunks_ = [[]];
this.readChunk_ = this.writeChunk_ = this.chunks_[0];
this.length_ = 0;
}
push(t: T): void {
this.writeChunk_.push(t);
this.length_ += 1;
if (this.writeChunk_.length === CHUNK_SIZE) {
this.writeChunk_ = [];
this.chunks_.push(this.writeChunk_);
}
}
front(): T | undefined {
if (this.length_ === 0) {
return undefined;
}
return this.readChunk_[0];
}
shift(): T | undefined {
if (this.length_ === 0) {
return undefined;
}
const t = this.readChunk_.shift();
this.length_ -= 1;
if (this.readChunk_.length === 0 && this.readChunk_ !== this.writeChunk_) {
this.chunks_.shift();
this.readChunk_ = this.chunks_[0];
}
return t;
}
get length(): number {
return this.length_;
}
}
|
