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