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 export class CircularList<T> extends EventEmitter {
  10   private _array: T[];
  11   private _startIndex: number;
  12   private _length: number;
  13
  14   constructor(maxLength: number) {
  15     super();
  16     this._array = new Array<T>(maxLength);
  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.
  28     let newArray = new Array<T>(newMaxLength);
  29     for (let i = 0; i < Math.min(newMaxLength, this.length); i++) {
  30       newArray[i] = this._array[this._getCyclicIndex(i)];
  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) {
  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
  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     };
  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 {
  80     this._array[this._getCyclicIndex(index)] = value;
  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 {
  89     this._array[this._getCyclicIndex(this._length)] = value;
  90     if (this._length === this.maxLength) {
  91       this._startIndex++;
  92       if (this._startIndex === this.maxLength) {
  93         this._startIndex = 0;
  94       }
  95       this.emit('trim', 1);
  96     } else {
  97       this._length++;
  98     }
  99   }
 100
 101   /**
 102    * Removes and returns the last value on the list.
 103    * @return The popped value.
 104    */
 105   public pop(): T {
 106     return this._array[this._getCyclicIndex(this._length-- - 1)];
 107   }
 108
 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    */
 118   public splice(start: number, deleteCount: number, ...items: T[]): void {
 119     // Delete items
 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     }
 126
 127     if (items && items.length) {
 128       // Add items
 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++) {
 133         this._array[this._getCyclicIndex(start + i)] = items[i];
 134       }
 135
 136       // Adjust length as needed
 137       if (this._length + items.length > this.maxLength) {
 138         const countToTrim = (this._length + items.length) - this.maxLength;
 139         this._startIndex += countToTrim;
 140         this._length = this.maxLength;
 141         this.emit('trim', countToTrim);
 142       } else {
 143         this._length += items.length;
 144       }
 145     }
 146   }
 147
 148   /**
 149    * Trims a number of items from the start of the list.
 150    * @param count The number of items to remove.
 151    */
 152   public trimStart(count: number): void {
 153     if (count > this._length) {
 154       count = this._length;
 155     }
 156     this._startIndex += count;
 157     this._length -= count;
 158     this.emit('trim', count);
 159   }
 160
 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--) {
 174         this.set(start + i + offset, this.get(start + i));
 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++;
 182           this.emit('trim', 1);
 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
 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    */
 198   private _getCyclicIndex(index: number): number {
 199     return (this._startIndex + index) % this.maxLength;
 200   }
 201 }