src/third_party/closure_library/closure/goog/structs/heap.js

// Copyright 2006 The Closure Library Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @fileoverview Datastructure: Heap.
 *
 *
 * This file provides the implementation of a Heap datastructure. Smaller keys
 * rise to the top.
 *
 * The big-O notation for all operations are below:
 * <pre>
 *  Method          big-O
 * ----------------------------------------------------------------------------
 * - insert         O(logn)
 * - remove         O(logn)
 * - peek           O(1)
 * - contains       O(n)
 * </pre>
 */
// TODO(user): Should this rely on natural ordering via some Comparable
//     interface?


goog.provide('goog.structs.Heap');

goog.require('goog.array');
goog.require('goog.object');
goog.require('goog.structs.Node');



/**
 * Class for a Heap datastructure.
 *
 * @param {goog.structs.Heap|Object=} opt_heap Optional goog.structs.Heap or
 *     Object to initialize heap with.
 * @constructor
 * @template K, V
 */
goog.structs.Heap = function(opt_heap) {
  /**
   * The nodes of the heap.
   * @private
   * @type {Array<goog.structs.Node>}
   */
  this.nodes_ = [];

  if (opt_heap) {
    this.insertAll(opt_heap);
  }
};


/**
 * Insert the given value into the heap with the given key.
 * @param {K} key The key.
 * @param {V} value The value.
 */
goog.structs.Heap.prototype.insert = function(key, value) {
  var node = new goog.structs.Node(key, value);
  var nodes = this.nodes_;
  nodes.push(node);
  this.moveUp_(nodes.length - 1);
};


/**
 * Adds multiple key-value pairs from another goog.structs.Heap or Object
 * @param {goog.structs.Heap|Object} heap Object containing the data to add.
 */
goog.structs.Heap.prototype.insertAll = function(heap) {
  var keys, values;
  if (heap instanceof goog.structs.Heap) {
    keys = heap.getKeys();
    values = heap.getValues();

    // If it is a heap and the current heap is empty, I can rely on the fact
    // that the keys/values are in the correct order to put in the underlying
    // structure.
    if (heap.getCount() <= 0) {
      var nodes = this.nodes_;
      for (var i = 0; i < keys.length; i++) {
        nodes.push(new goog.structs.Node(keys[i], values[i]));
      }
      return;
    }
  } else {
    keys = goog.object.getKeys(heap);
    values = goog.object.getValues(heap);
  }

  for (var i = 0; i < keys.length; i++) {
    this.insert(keys[i], values[i]);
  }
};


/**
 * Retrieves and removes the root value of this heap.
 * @return {V} The value removed from the root of the heap.  Returns
 *     undefined if the heap is empty.
 */
goog.structs.Heap.prototype.remove = function() {
  var nodes = this.nodes_;
  var count = nodes.length;
  var rootNode = nodes[0];
  if (count <= 0) {
    return undefined;
  } else if (count == 1) {
    goog.array.clear(nodes);
  } else {
    nodes[0] = nodes.pop();
    this.moveDown_(0);
  }
  return rootNode.getValue();
};


/**
 * Retrieves but does not remove the root value of this heap.
 * @return {V} The value at the root of the heap. Returns
 *     undefined if the heap is empty.
 */
goog.structs.Heap.prototype.peek = function() {
  var nodes = this.nodes_;
  if (nodes.length == 0) {
    return undefined;
  }
  return nodes[0].getValue();
};


/**
 * Retrieves but does not remove the key of the root node of this heap.
 * @return {K} The key at the root of the heap. Returns undefined if the
 *     heap is empty.
 */
goog.structs.Heap.prototype.peekKey = function() {
  return this.nodes_[0] && this.nodes_[0].getKey();
};


/**
 * Moves the node at the given index down to its proper place in the heap.
 * @param {number} index The index of the node to move down.
 * @private
 */
goog.structs.Heap.prototype.moveDown_ = function(index) {
  var nodes = this.nodes_;
  var count = nodes.length;

  // Save the node being moved down.
  var node = nodes[index];
  // While the current node has a child.
  while (index < (count >> 1)) {
    var leftChildIndex = this.getLeftChildIndex_(index);
    var rightChildIndex = this.getRightChildIndex_(index);

    // Determine the index of the smaller child.
    var smallerChildIndex = rightChildIndex < count &&
        nodes[rightChildIndex].getKey() < nodes[leftChildIndex].getKey() ?
        rightChildIndex : leftChildIndex;

    // If the node being moved down is smaller than its children, the node
    // has found the correct index it should be at.
    if (nodes[smallerChildIndex].getKey() > node.getKey()) {
      break;
    }

    // If not, then take the smaller child as the current node.
    nodes[index] = nodes[smallerChildIndex];
    index = smallerChildIndex;
  }
  nodes[index] = node;
};


/**
 * Moves the node at the given index up to its proper place in the heap.
 * @param {number} index The index of the node to move up.
 * @private
 */
goog.structs.Heap.prototype.moveUp_ = function(index) {
  var nodes = this.nodes_;
  var node = nodes[index];

  // While the node being moved up is not at the root.
  while (index > 0) {
    // If the parent is less than the node being moved up, move the parent down.
    var parentIndex = this.getParentIndex_(index);
    if (nodes[parentIndex].getKey() > node.getKey()) {
      nodes[index] = nodes[parentIndex];
      index = parentIndex;
    } else {
      break;
    }
  }
  nodes[index] = node;
};


/**
 * Gets the index of the left child of the node at the given index.
 * @param {number} index The index of the node to get the left child for.
 * @return {number} The index of the left child.
 * @private
 */
goog.structs.Heap.prototype.getLeftChildIndex_ = function(index) {
  return index * 2 + 1;
};


/**
 * Gets the index of the right child of the node at the given index.
 * @param {number} index The index of the node to get the right child for.
 * @return {number} The index of the right child.
 * @private
 */
goog.structs.Heap.prototype.getRightChildIndex_ = function(index) {
  return index * 2 + 2;
};


/**
 * Gets the index of the parent of the node at the given index.
 * @param {number} index The index of the node to get the parent for.
 * @return {number} The index of the parent.
 * @private
 */
goog.structs.Heap.prototype.getParentIndex_ = function(index) {
  return (index - 1) >> 1;
};


/**
 * Gets the values of the heap.
 * @return {!Array<V>} The values in the heap.
 */
goog.structs.Heap.prototype.getValues = function() {
  var nodes = this.nodes_;
  var rv = [];
  var l = nodes.length;
  for (var i = 0; i < l; i++) {
    rv.push(nodes[i].getValue());
  }
  return rv;
};


/**
 * Gets the keys of the heap.
 * @return {!Array<K>} The keys in the heap.
 */
goog.structs.Heap.prototype.getKeys = function() {
  var nodes = this.nodes_;
  var rv = [];
  var l = nodes.length;
  for (var i = 0; i < l; i++) {
    rv.push(nodes[i].getKey());
  }
  return rv;
};


/**
 * Whether the heap contains the given value.
 * @param {V} val The value to check for.
 * @return {boolean} Whether the heap contains the value.
 */
goog.structs.Heap.prototype.containsValue = function(val) {
  return goog.array.some(this.nodes_, function(node) {
    return node.getValue() == val;
  });
};


/**
 * Whether the heap contains the given key.
 * @param {K} key The key to check for.
 * @return {boolean} Whether the heap contains the key.
 */
goog.structs.Heap.prototype.containsKey = function(key) {
  return goog.array.some(this.nodes_, function(node) {
    return node.getKey() == key;
  });
};


/**
 * Clones a heap and returns a new heap
 * @return {!goog.structs.Heap} A new goog.structs.Heap with the same key-value
 *     pairs.
 */
goog.structs.Heap.prototype.clone = function() {
  return new goog.structs.Heap(this);
};


/**
 * The number of key-value pairs in the map
 * @return {number} The number of pairs.
 */
goog.structs.Heap.prototype.getCount = function() {
  return this.nodes_.length;
};


/**
 * Returns true if this heap contains no elements.
 * @return {boolean} Whether this heap contains no elements.
 */
goog.structs.Heap.prototype.isEmpty = function() {
  return goog.array.isEmpty(this.nodes_);
};


/**
 * Removes all elements from the heap.
 */
goog.structs.Heap.prototype.clear = function() {
  goog.array.clear(this.nodes_);
};