src/utils/CircularList.ts

   1 /**
   2  * xterm.js: xterm, in the browser
   3  * Copyright (c) 2016, SourceLair Private Company <www.sourcelair.com> (MIT License)
   4  */
   5
   6 /**
   7  * Represents a circular list; a list with a maximum size that wraps around when push is called,
   8  * overriding values at the start of the list.
   9  */
  10 export class CircularList<T> {
  11   private _array: T[];
  12   private _startIndex: number;
  13   private _length: number;
  14
  15   constructor(maxLength: number) {
  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     // TODO: Is this auto fill is needed or can it be
  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, array: T[]) => void) => void {
  51     return this._array.forEach;
  52   }
  53
  54   /**
  55    * Gets the value at an index.
  56    *
  57    * Note that for performance reasons there is no bounds checking here, the index reference is
  58    * circular so this should always return a value and never throw.
  59    * @param index The index of the value to get.
  60    * @return The value corresponding to the index.
  61    */
  62   public get(index: number): T {
  63     return this._array[this._getCyclicIndex(index)];
  64   }
  65
  66   /**
  67    * Sets the value at an index.
  68    *
  69    * Note that for performance reasons there is no bounds checking here, the index reference is
  70    * circular so this should always return a value and never throw.
  71    * @param index The index to set.
  72    * @param value The value to set.
  73    */
  74   public set(index: number, value: T): void {
  75     this._array[this._getCyclicIndex(index)] = value;
  76   }
  77
  78   /**
  79    * Pushes a new value onto the list, wrapping around to the start of the array, overriding index 0
  80    * if the maximum length is reached.
  81    * @param value The value to push onto the list.
  82    */
  83   public push(value: T): void {
  84     this._array[this._getCyclicIndex(this._length)] = value;
  85     if (this._length === this.maxLength) {
  86       this._startIndex++;
  87     } else {
  88       this._length++;
  89     }
  90   }
  91
  92   public pop(): T {
  93     return this._array[this._getCyclicIndex(this._length-- - 1)];
  94   }
  95
  96   // TODO: Warn there's no error handling and that this is a slow operation
  97   public splice(start: number, deleteCount: number, ...items: T[]) {
  98     if (deleteCount) {
  99       for (let i = start; i < this._length - deleteCount; i++) {
 100         this._array[this._getCyclicIndex(i)] = this._array[this._getCyclicIndex(i + deleteCount)];
 101       }
 102       this._length -= deleteCount;
 103     }
 104     if (items && items.length) {
 105       for (let i = this._length - 1; i >= start; i--) {
 106         this._array[this._getCyclicIndex(i + items.length)] = this._array[this._getCyclicIndex(i)];
 107       }
 108       for (let i = 0; i < items.length; i++) {
 109         this._array[this._getCyclicIndex(start + i)] = items[i];
 110       }
 111
 112       if (this._length + items.length > this.maxLength) {
 113         this._startIndex += (this._length + items.length) - this.maxLength;
 114         this._length = this.maxLength;
 115       } else {
 116         this._length += items.length;
 117       }
 118     }
 119   }
 120
 121   private _getCyclicIndex(index: number): number {
 122     return (this._startIndex + index) % this.maxLength;
 123   }
 124 }