IntegerBufferSet.js.flow

/**
 * Copyright (c) 2013-present, Facebook, Inc.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 *
 * @providesModule IntegerBufferSet
 * @typechecks
 */
'use strict';

const Heap = require("./Heap");

const invariant = require("./invariant"); // Data structure that allows to store values and assign positions to them
// in a way to minimize changing positions of stored values when new ones are
// added or when some values are replaced. Stored elements are alwasy assigned
// a consecutive set of positoins startin from 0 up to count of elements less 1
// Following actions can be executed
// * get position assigned to given value (null if value is not stored)
// * create new entry for new value and get assigned position back
// * replace value that is furthest from specified value range with new value
//   and get it's position back
// All operations take amortized log(n) time where n is number of elements in
// the set.


class IntegerBufferSet {
  constructor() {
    this._valueToPositionMap = {};
    this._size = 0;
    this._smallValues = new Heap([], // Initial data in the heap
    this._smallerComparator);
    this._largeValues = new Heap([], // Initial data in the heap
    this._greaterComparator);
    this.getNewPositionForValue = this.getNewPositionForValue.bind(this);
    this.getValuePosition = this.getValuePosition.bind(this);
    this.getSize = this.getSize.bind(this);
    this.replaceFurthestValuePosition = this.replaceFurthestValuePosition.bind(this);
  }

  getSize()
  /*number*/
  {
    return this._size;
  }

  getValuePosition(
  /*number*/
  value)
  /*?number*/
  {
    if (this._valueToPositionMap[value] === undefined) {
      return null;
    }

    return this._valueToPositionMap[value];
  }

  getNewPositionForValue(
  /*number*/
  value)
  /*number*/
  {
    invariant(this._valueToPositionMap[value] === undefined, "Shouldn't try to find new position for value already stored in BufferSet");
    const newPosition = this._size;
    this._size++;

    this._pushToHeaps(newPosition, value);

    this._valueToPositionMap[value] = newPosition;
    return newPosition;
  }

  replaceFurthestValuePosition(
  /*number*/
  lowValue,
  /*number*/
  highValue,
  /*number*/
  newValue)
  /*?number*/
  {
    invariant(this._valueToPositionMap[newValue] === undefined, "Shouldn't try to replace values with value already stored value in " + "BufferSet");

    this._cleanHeaps();

    if (this._smallValues.empty() || this._largeValues.empty()) {
      // Threre are currently no values stored. We will have to create new
      // position for this value.
      return null;
    }

    const minValue = this._smallValues.peek().value;

    const maxValue = this._largeValues.peek().value;

    if (minValue >= lowValue && maxValue <= highValue) {
      // All values currently stored are necessary, we can't reuse any of them.
      return null;
    }

    let valueToReplace;

    if (lowValue - minValue > maxValue - highValue) {
      // minValue is further from provided range. We will reuse it's position.
      valueToReplace = minValue;

      this._smallValues.pop();
    } else {
      valueToReplace = maxValue;

      this._largeValues.pop();
    }

    const position = this._valueToPositionMap[valueToReplace];
    delete this._valueToPositionMap[valueToReplace];
    this._valueToPositionMap[newValue] = position;

    this._pushToHeaps(position, newValue);

    return position;
  }

  _pushToHeaps(
  /*number*/
  position,
  /*number*/
  value) {
    const element = {
      position,
      value
    }; // We can reuse the same object in both heaps, because we don't mutate them

    this._smallValues.push(element);

    this._largeValues.push(element);
  }

  _cleanHeaps() {
    // We not usually only remove object from one heap while moving value.
    // Here we make sure that there is no stale data on top of heaps.
    this._cleanHeap(this._smallValues);

    this._cleanHeap(this._largeValues);

    const minHeapSize = Math.min(this._smallValues.size(), this._largeValues.size());
    const maxHeapSize = Math.max(this._smallValues.size(), this._largeValues.size());

    if (maxHeapSize > 10 * minHeapSize) {
      // There are many old values in one of heaps. We nned to get rid of them
      // to not use too avoid memory leaks
      this._recreateHeaps();
    }
  }

  _recreateHeaps() {
    const sourceHeap = this._smallValues.size() < this._largeValues.size() ? this._smallValues : this._largeValues;
    const newSmallValues = new Heap([], // Initial data in the heap
    this._smallerComparator);
    const newLargeValues = new Heap([], // Initial datat in the heap
    this._greaterComparator);

    while (!sourceHeap.empty()) {
      const element = sourceHeap.pop(); // Push all stil valid elements to new heaps

      if (this._valueToPositionMap[element.value] !== undefined) {
        newSmallValues.push(element);
        newLargeValues.push(element);
      }
    }

    this._smallValues = newSmallValues;
    this._largeValues = newLargeValues;
  }

  _cleanHeap(
  /*object*/
  heap) {
    while (!heap.empty() && this._valueToPositionMap[heap.peek().value] === undefined) {
      heap.pop();
    }
  }

  _smallerComparator(
  /*object*/
  lhs,
  /*object*/
  rhs)
  /*boolean*/
  {
    return lhs.value < rhs.value;
  }

  _greaterComparator(
  /*object*/
  lhs,
  /*object*/
  rhs)
  /*boolean*/
  {
    return lhs.value > rhs.value;
  }

}

module.exports = IntegerBufferSet;