// Copyright 2008 Google Inc.
// All Rights Reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// 
//  * Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
//  * Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in
//    the documentation and/or other materials provided with the
//    distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE. 

/**
 * @fileoverview Provides inversion and inversion map functionality for storing
 * integer ranges and corresponding values.
 *
 */

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

goog.require('goog.array');


/**
 * Maps ranges to values using goog.structs.Inversion.
 * @param {Array.<number>} rangeArray An array of monotonically
 *     increasing integer values, with at least one instance.
 * @param {Array.<*>} valueArray An array of corresponding values.
 *     Length must be the same as rangeArray.
 * @param {boolean} opt_delta If true, saves only delta from previous value.
 * @constructor
 */
goog.structs.InversionMap = function(rangeArray, valueArray, opt_delta) {
  if (rangeArray.length != valueArray.length) {
    // rangeArray and valueArray has to match in number of entries.
    return null;
  }
  this.storeInversion_(rangeArray, opt_delta);

  /**
   * @type {Array}
   * @protected
   */
  this.values = valueArray;
};


/**
 * @type {Array}
 * @protected
 */
goog.structs.InversionMap.prototype.rangeArray;


/**
 * Stores the integers as ranges (half-open).
 * If delta is true, the integers are delta from the previous value and
 * will be restored to the absolute value.
 * When used as a set, even indices are IN, and odd are OUT.
 * @param {Array.<number?>} rangeArray An array of monotonically
 *     increasing integer values, with at least one instance.
 * @param {boolean} opt_delta If true, saves only delta from previous value.
 * @private
 */
goog.structs.InversionMap.prototype.storeInversion_ = function(rangeArray,
    opt_delta) {
  this.rangeArray = rangeArray;

  for (var i = 1; i < rangeArray.length; i++) {
    if (rangeArray[i] == null) {
      rangeArray[i] = rangeArray[i - 1] + 1;
    } else if (opt_delta) {
      rangeArray[i] += rangeArray[i - 1];
    }
  }
};


/**
 * Splices a range -> value map into this inversion map.
 * @param {Array.<number>} rangeArray An array of monotonically
 *     increasing integer values, with at least one instance.
 * @param {Array.<*>} valueArray An array of corresponding values.
 *     Length must be the same as rangeArray.
 * @param {boolean} opt_delta If true, saves only delta from previous value.
 */
goog.structs.InversionMap.prototype.spliceInversion = function(
    rangeArray, valueArray, opt_delta) {
  var otherMap = new goog.structs.InversionMap(
      rangeArray, valueArray, opt_delta);
  var startRange = otherMap.rangeArray[0];
  var endRange = goog.array.peek(otherMap.rangeArray);
  var startSplice = this.getLeast(startRange);
  if (startRange != startSplice) {
    startSplice++;
  }

  var spliceLength = this.getLeast(endRange) - startSplice + 1;
  goog.partial(goog.array.splice, this.rangeArray, startSplice,
      spliceLength).apply(null, otherMap.rangeArray);
  goog.partial(goog.array.splice, this.values, startSplice,
      spliceLength).apply(null, otherMap.values);
};


/**
 * Gets the value corresponding to a number from the inversion map.
 * @param {number} intKey The number for which value needs to be retrieved
 *     from inversion map.
 * @return {*} Value retrieved from inversion map; null if not found.
 */
goog.structs.InversionMap.prototype.at = function(intKey) {
  var index = this.getLeast(intKey);
  if (index < 0) {
    return null;
  }
  return this.values[index];
};


/**
 * Gets the largest index such that rangeArray[index] <= intKey from the
 * inversion map.
 * @param {number} intKey The probe for which rangeArray is searched.
 * @return {number} Largest index such that rangeArray[index] <= intKey.
 * @protected
 */
goog.structs.InversionMap.prototype.getLeast = function(intKey) {
  var arr = this.rangeArray;
  var low = 0;
  var high = arr.length;
  while (high - low > 8) {
    var mid = (high + low) >> 1;
    if (arr[mid] <= intKey) {
      low = mid;
    } else {
      high = mid;
    }
  }
  for (; low < high; ++low) {
    if (intKey < arr[low]) {
      break;
    }
  }
  return low - 1;
};