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