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