src/utils/CircularList.ts

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