]>
Commit | Line | Data |
---|---|---|
49b76baf DI |
1 | /** |
2 | * Represents a circular list; a list with a maximum size that wraps around when push is called, | |
3 | * overriding values at the start of the list. | |
50cfe2b2 DI |
4 | * @module xterm/utils/CircularList |
5 | * @license MIT | |
49b76baf | 6 | */ |
70fda994 DI |
7 | import { EventEmitter } from '../EventEmitter'; |
8 | ||
9 | export class CircularList<T> extends EventEmitter { | |
71477874 | 10 | private _array: T[]; |
49b76baf DI |
11 | private _startIndex: number; |
12 | private _length: number; | |
13 | ||
14 | constructor(maxLength: number) { | |
70fda994 | 15 | super(); |
71477874 | 16 | this._array = new Array<T>(maxLength); |
49b76baf DI |
17 | this._startIndex = 0; |
18 | this._length = 0; | |
19 | } | |
20 | ||
21 | public get maxLength(): number { | |
22 | return this._array.length; | |
23 | } | |
24 | ||
25 | public set maxLength(newMaxLength: number) { | |
26 | // Reconstruct array, starting at index 0. Only transfer values from the | |
27 | // indexes 0 to length. | |
71477874 | 28 | let newArray = new Array<T>(newMaxLength); |
49b76baf | 29 | for (let i = 0; i < Math.min(newMaxLength, this.length); i++) { |
71477874 | 30 | newArray[i] = this._array[this._getCyclicIndex(i)]; |
49b76baf DI |
31 | } |
32 | this._array = newArray; | |
33 | this._startIndex = 0; | |
34 | } | |
35 | ||
36 | public get length(): number { | |
37 | return this._length; | |
38 | } | |
39 | ||
40 | public set length(newLength: number) { | |
49b76baf DI |
41 | if (newLength > this._length) { |
42 | for (let i = this._length; i < newLength; i++) { | |
43 | this._array[i] = undefined; | |
44 | } | |
45 | } | |
46 | this._length = newLength; | |
47 | } | |
48 | ||
65256c87 DI |
49 | public get forEach(): (callbackfn: (value: T, index: number) => void) => void { |
50 | return (callbackfn: (value: T, index: number) => void) => { | |
51 | let i = 0; | |
52 | let length = this.length; | |
53 | for (let i = 0; i < length; i++) { | |
54 | callbackfn(this.get(i), i); | |
55 | } | |
56 | }; | |
49b76baf DI |
57 | } |
58 | ||
59 | /** | |
60 | * Gets the value at an index. | |
61 | * | |
62 | * Note that for performance reasons there is no bounds checking here, the index reference is | |
63 | * circular so this should always return a value and never throw. | |
64 | * @param index The index of the value to get. | |
65 | * @return The value corresponding to the index. | |
66 | */ | |
67 | public get(index: number): T { | |
68 | return this._array[this._getCyclicIndex(index)]; | |
69 | } | |
70 | ||
71 | /** | |
72 | * Sets the value at an index. | |
73 | * | |
74 | * Note that for performance reasons there is no bounds checking here, the index reference is | |
75 | * circular so this should always return a value and never throw. | |
76 | * @param index The index to set. | |
77 | * @param value The value to set. | |
78 | */ | |
79 | public set(index: number, value: T): void { | |
71477874 | 80 | this._array[this._getCyclicIndex(index)] = value; |
49b76baf DI |
81 | } |
82 | ||
83 | /** | |
84 | * Pushes a new value onto the list, wrapping around to the start of the array, overriding index 0 | |
85 | * if the maximum length is reached. | |
86 | * @param value The value to push onto the list. | |
87 | */ | |
88 | public push(value: T): void { | |
71477874 | 89 | this._array[this._getCyclicIndex(this._length)] = value; |
49b76baf DI |
90 | if (this._length === this.maxLength) { |
91 | this._startIndex++; | |
3b35d12e DI |
92 | if (this._startIndex === this.maxLength) { |
93 | this._startIndex = 0; | |
94 | } | |
70fda994 | 95 | this.emit('trim', 1); |
49b76baf DI |
96 | } else { |
97 | this._length++; | |
98 | } | |
99 | } | |
100 | ||
bfaf9cd6 DI |
101 | /** |
102 | * Removes and returns the last value on the list. | |
103 | * @return The popped value. | |
104 | */ | |
61fbbb00 | 105 | public pop(): T { |
71477874 | 106 | return this._array[this._getCyclicIndex(this._length-- - 1)]; |
61fbbb00 DI |
107 | } |
108 | ||
bfaf9cd6 DI |
109 | /** |
110 | * Deletes and/or inserts items at a particular index (in that order). Unlike | |
111 | * Array.prototype.splice, this operation does not return the deleted items as a new array in | |
112 | * order to save creating a new array. Note that this operation may shift all values in the list | |
113 | * in the worst case. | |
114 | * @param start The index to delete and/or insert. | |
115 | * @param deleteCount The number of elements to delete. | |
116 | * @param items The items to insert. | |
117 | */ | |
be2e4b5d | 118 | public splice(start: number, deleteCount: number, ...items: T[]): void { |
65256c87 | 119 | // Delete items |
61fbbb00 DI |
120 | if (deleteCount) { |
121 | for (let i = start; i < this._length - deleteCount; i++) { | |
122 | this._array[this._getCyclicIndex(i)] = this._array[this._getCyclicIndex(i + deleteCount)]; | |
123 | } | |
124 | this._length -= deleteCount; | |
125 | } | |
65256c87 | 126 | |
61fbbb00 | 127 | if (items && items.length) { |
65256c87 | 128 | // Add items |
61fbbb00 DI |
129 | for (let i = this._length - 1; i >= start; i--) { |
130 | this._array[this._getCyclicIndex(i + items.length)] = this._array[this._getCyclicIndex(i)]; | |
131 | } | |
132 | for (let i = 0; i < items.length; i++) { | |
71477874 | 133 | this._array[this._getCyclicIndex(start + i)] = items[i]; |
61fbbb00 DI |
134 | } |
135 | ||
65256c87 | 136 | // Adjust length as needed |
61fbbb00 | 137 | if (this._length + items.length > this.maxLength) { |
70fda994 DI |
138 | const countToTrim = (this._length + items.length) - this.maxLength; |
139 | this._startIndex += countToTrim; | |
61fbbb00 | 140 | this._length = this.maxLength; |
70fda994 | 141 | this.emit('trim', countToTrim); |
61fbbb00 DI |
142 | } else { |
143 | this._length += items.length; | |
144 | } | |
145 | } | |
146 | } | |
147 | ||
bfaf9cd6 DI |
148 | /** |
149 | * Trims a number of items from the start of the list. | |
150 | * @param count The number of items to remove. | |
151 | */ | |
3b35d12e | 152 | public trimStart(count: number): void { |
bfaf9cd6 DI |
153 | if (count > this._length) { |
154 | count = this._length; | |
155 | } | |
3b35d12e | 156 | this._startIndex += count; |
bfaf9cd6 | 157 | this._length -= count; |
70fda994 | 158 | this.emit('trim', count); |
3b35d12e DI |
159 | } |
160 | ||
969a2e95 DI |
161 | public shiftElements(start: number, count: number, offset: number): void { |
162 | if (count <= 0) { | |
163 | return; | |
164 | } | |
165 | if (start < 0 || start >= this._length) { | |
166 | throw new Error('start argument out of range'); | |
167 | } | |
168 | if (start + offset < 0) { | |
169 | throw new Error('Cannot shift elements in list beyond index 0'); | |
170 | } | |
171 | ||
172 | if (offset > 0) { | |
173 | for (let i = count - 1; i >= 0; i--) { | |
71477874 | 174 | this.set(start + i + offset, this.get(start + i)); |
969a2e95 DI |
175 | } |
176 | const expandListBy = (start + count + offset) - this._length; | |
177 | if (expandListBy > 0) { | |
178 | this._length += expandListBy; | |
179 | while (this._length > this.maxLength) { | |
180 | this._length--; | |
181 | this._startIndex++; | |
70fda994 | 182 | this.emit('trim', 1); |
969a2e95 DI |
183 | } |
184 | } | |
185 | } else { | |
186 | for (let i = 0; i < count; i++) { | |
187 | this.set(start + i + offset, this.get(start + i)); | |
188 | } | |
189 | } | |
190 | } | |
191 | ||
bfaf9cd6 DI |
192 | /** |
193 | * Gets the cyclic index for the specified regular index. The cyclic index can then be used on the | |
194 | * backing array to get the element associated with the regular index. | |
195 | * @param index The regular index. | |
196 | * @returns The cyclic index. | |
197 | */ | |
49b76baf DI |
198 | private _getCyclicIndex(index: number): number { |
199 | return (this._startIndex + index) % this.maxLength; | |
200 | } | |
201 | } |