123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156 |
- goog.provide('goog.structs.InversionMap');
- goog.require('goog.array');
- goog.require('goog.asserts');
- goog.structs.InversionMap = function(rangeArray, valueArray, opt_delta) {
-
- this.rangeArray = null;
- goog.asserts.assert(
- rangeArray.length == valueArray.length,
- 'rangeArray and valueArray must have the same length.');
- this.storeInversion_(rangeArray, opt_delta);
-
- this.values = valueArray;
- };
- 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];
- }
- }
- };
- 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);
- var endSplice = this.getLeast(endRange);
-
- if (startRange != this.rangeArray[startSplice]) {
-
-
- startSplice++;
- }
- this.rangeArray = this.rangeArray.slice(0, startSplice)
- .concat(otherMap.rangeArray)
- .concat(this.rangeArray.slice(endSplice + 1));
- this.values = this.values.slice(0, startSplice)
- .concat(otherMap.values)
- .concat(this.values.slice(endSplice + 1));
- };
- goog.structs.InversionMap.prototype.at = function(intKey) {
- var index = this.getLeast(intKey);
- if (index < 0) {
- return null;
- }
- return this.values[index];
- };
- 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;
- };
|