<commit_before>/**
 * @license
 * js-data-structures <http://github.com/Tyriar/js-data-structures>
 * Copyright 2014 <NAME> <http://www.growingwiththeweb.com>
 * Released under the MIT license <http://github.com/Tyriar/js-data-structures/blob/master/LICENSE>
 */
'use strict';

if (typeof exports === 'object' && typeof define !== 'function') {
    var define = function (factory) {
        factory(require, exports, module);
    };
}

define(function (require, exports, module) {
  /**
   * Creates a binary heap.
   *
   * @constructor
   * @param {function} customCompare An optional custom node comparison
   * function.
   */
  var BinaryHeap = function (customCompare) {
    this.list = [];

    if (customCompare) {
      this.compare = customCompare;
    }
  };

  /**
   * Builds a heap with the provided keys and values, this will discard the
   * heap's current data.
   *
   * @param {Array} keys An array of keys.
   * @param {Array} values An array of values. This must be the same size as the
   * key array.
   */
  BinaryHeap.prototype.buildHeap = function (keys, values) {
    if (keys.length !== values.length) {
      throw 'Key array must be the same length as value array';
    }

    var nodeArray = [];

    for (var i = 0; i < keys.length; i++) {
      nodeArray.push(new Node(keys[i], values[i], i));
    }

    buildHeapFromNodeArray(this, nodeArray);
  };

  /**
   * Clears the heap's data, making it an empty heap.
   */
  BinaryHeap.prototype.clear = function () {
    this.list.length = 0;
  };

  /**
   * Decreases the key of a node.
   *
   * @param {Node} node The node to decrease.
   * @param {Object} newKey The new key.
   */
  BinaryHeap.prototype.decreaseKey = function (node, newKey) {
    if (typeof node === 'undefined') {
      throw 'Cannot decrease key of non-existent node';
    }
    // Create a temp node for comparison
    if (this.compare({ key: newKey }, { key: node.key }) > 0) {
      throw 'New key is larger than old key';
    }

    node.key = newKey;
    var parent = getParent(node.i);
    while (this.compare(node, this.list[parent]) < 0) {
      swap(this.list, node.i, parent);
      parent = getParent(node.i);
    }
  };

  /**
   * Removes a node from the heap.
   *
   * @param {Node} node The node to remove.
   */
  BinaryHeap.prototype.delete = function (node) {
    // Bubble up to the root and extract
    while (node.i > 0) {
      var parent = getParent(node.i);
      swap(this.list, node.i, parent);
    }
    this.extractMinimum();
  };

  /**
   * Extracts and returns the minimum node from the heap.
   *
   * @return {Node} node The heap's minimum node or undefined if the heap is
   * empty.
   */
  BinaryHeap.prototype.extractMinimum = function () {
    if (!this.list.length) {
      return undefined;
    }
    if (this.list.length === 1) {
      return this.list.shift();
    }
    var min = this.list[0];
    this.list[0] = this.list.pop();
    this.list[0].i = 0;
    heapify(this, 0);
    return min;
  };

  /**
   * Returns the minimum node from the heap.
   *
   * @return {Node} node The heap's minimum node or undefined if the heap is
   * empty.
   */
  BinaryHeap.prototype.findMinimum = function () {
    return this.isEmpty() ? undefined : this.list[0];
  };

  BinaryHeap.prototype.insert = function (key, value) {
    var i = this.list.length;
    var node = new Node(key, value, i);
    this.list.push(node);
    var parent = getParent(i);
    while (parent !== i && this.compare(this.list[i], this.list[parent]) < 0) {
      swap(this.list, i, parent);
      i = parent;
      parent = getParent(i);
    }
    return node;
  };

  BinaryHeap.prototype.isEmpty = function () {
    return !this.list.length;
  };

  BinaryHeap.prototype.size = function () {
    return this.list.length;
  };

  BinaryHeap.prototype.union = function (otherHeap) {
    var array = this.list.concat(otherHeap.list);
    buildHeapFromNodeArray(this, array);
  };

  BinaryHeap.prototype.compare = function (a, b) {
    if (a.key > b.key) {
      return 1;
    }
    if (a.key < b.key) {<commit_msg>jsdoc<commit_after>/**
 * @license
 * js-data-structures <http://github.com/Tyriar/js-data-structures>
 * Copyright 2014 <NAME> <http://www.growingwiththeweb.com>
 * Released under the MIT license <http://github.com/Tyriar/js-data-structures/blob/master/LICENSE>
 */
'use strict';

if (typeof exports === 'object' && typeof define !== 'function') {
    var define = function (factory) {
        factory(require, exports, module);
    };
}

define(function (require, exports, module) {
  /**
   * Creates a binary heap.
   *
   * @constructor
   * @param {function} customCompare An optional custom node comparison
   * function.
   */
  var BinaryHeap = function (customCompare) {
    this.list = [];

    if (customCompare) {
      this.compare = customCompare;
    }
  };

  /**
   * Builds a heap with the provided keys and values, this will discard the
   * heap's current data.
   *
   * @param {Array} keys An array of keys.
   * @param {Array} values An array of values. This must be the same size as the
   * key array.
   */
  BinaryHeap.prototype.buildHeap = function (keys, values) {
    if (keys.length !== values.length) {
      throw 'Key array must be the same length as value array';
    }

    var nodeArray = [];

    for (var i = 0; i < keys.length; i++) {
      nodeArray.push(new Node(keys[i], values[i], i));
    }

    buildHeapFromNodeArray(this, nodeArray);
  };

  /**
   * Clears the heap's data, making it an empty heap.
   */
  BinaryHeap.prototype.clear = function () {
    this.list.length = 0;
  };

  /**
   * Decreases the key of a node.
   *
   * @param {Node} node The node to decrease.
   * @param {Object} newKey The new key.
   */
  BinaryHeap.prototype.decreaseKey = function (node, newKey) {
    if (typeof node === 'undefined') {
      throw 'Cannot decrease key of non-existent node';
    }
    // Create a temp node for comparison
    if (this.compare({ key: newKey }, { key: node.key }) > 0) {
      throw 'New key is larger than old key';
    }

    node.key = newKey;
    var parent = getParent(node.i);
    while (this.compare(node, this.list[parent]) < 0) {
      swap(this.list, node.i, parent);
      parent = getParent(node.i);
    }
  };

  /**
   * Removes a node from the heap.
   *
   * @param {Node} node The node to remove.
   */
  BinaryHeap.prototype.delete = function (node) {
    // Bubble up to the root and extract
    while (node.i > 0) {
      var parent = getParent(node.i);
      swap(this.list, node.i, parent);
    }
    this.extractMinimum();
  };

  /**
   * Extracts and returns the minimum node from the heap.
   *
   * @return {Node} node The heap's minimum node or undefined if the heap is
   * empty.
   */
  BinaryHeap.prototype.extractMinimum = function () {
    if (!this.list.length) {
      return undefined;
    }
    if (this.list.length === 1) {
      return this.list.shift();
    }
    var min = this.list[0];
    this.list[0] = this.list.pop();
    this.list[0].i = 0;
    heapify(this, 0);
    return min;
  };

  /**
   * Returns the minimum node from the heap.
   *
   * @return {Node} node The heap's minimum node or undefined if the heap is
   * empty.
   */
  BinaryHeap.prototype.findMinimum = function () {
    return this.isEmpty() ? undefined : this.list[0];
  };

  /**
   * Inserts a new key-value pair into the heap.
   *
   * @param {Object} key The key to insert.
   * @param {Object} value The value to insert.
   * @return {Node} node The inserted node.
   */
  BinaryHeap.prototype.insert = function (key, value) {
    var i = this.list.length;
    var node = new Node(key, value, i);
    this.list.push(node);
    var parent = getParent(i);
    while (parent !== i && this.compare(this.list[i], this.list[parent]) < 0) {
      swap(this.list, i, parent);
      i = parent;
      parent = getParent(i);
    }
    return node;
  };

  /**
   * @return {boolean} Whether the heap is empty.
   */
  BinaryHeap.prototype.isEmpty = function () {
    return !this.list.length;
  };

  /**
   * @return {number} The size of the heap.
   */
  BinaryHeap.prototype.size = function () {
    return this.list.length;
  };

  BinaryHeap.prototype.union = function (otherHeap) {
    var array = this.list.concat(otherHeap.list);
    buildHeapFromNodeArray(this, array);
  };

  BinaryHeap.prototype.compare = function (a, b) {
    if (a.key > b.key) {
      return 1;
    }
    if (a.key < b.key) {
{'fraction_non_alphanumeric': 0.14144037780401417, 'fraction_numerical': 0.004250295159386069, 'mean_word_length': 2.5251768622555137, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2712343', 'n_tokens_mistral': 2827, 'n_tokens_neox': 2744, 'n_words': 798}