node_modules/xterm/src/common/CircularList.ts

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