OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2007 Apple Inc. All rights reserved. | 2 * Copyright (C) 2007 Apple Inc. All rights reserved. |
3 * Copyright (C) 2012 Google Inc. All rights reserved. | 3 * Copyright (C) 2012 Google Inc. All rights reserved. |
4 * | 4 * |
5 * Redistribution and use in source and binary forms, with or without | 5 * Redistribution and use in source and binary forms, with or without |
6 * modification, are permitted provided that the following conditions | 6 * modification, are permitted provided that the following conditions |
7 * are met: | 7 * are met: |
8 * | 8 * |
9 * 1. Redistributions of source code must retain the above copyright | 9 * 1. Redistributions of source code must retain the above copyright |
10 * notice, this list of conditions and the following disclaimer. | 10 * notice, this list of conditions and the following disclaimer. |
(...skipping 312 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
323 */ | 323 */ |
324 value: function() | 324 value: function() |
325 { | 325 { |
326 var keys = {}; | 326 var keys = {}; |
327 for (var i = 0; i < this.length; ++i) | 327 for (var i = 0; i < this.length; ++i) |
328 keys[this[i]] = true; | 328 keys[this[i]] = true; |
329 return keys; | 329 return keys; |
330 } | 330 } |
331 }); | 331 }); |
332 | 332 |
333 Object.defineProperty(Array.prototype, "upperBound", | |
334 { | |
335 /** | |
336 * @param {number} value | |
337 * @return {number} | |
338 * @this {Array.<number>} | |
339 */ | |
340 value: function(value) | |
341 { | |
342 var first = 0; | |
343 var count = this.length; | |
344 while (count > 0) { | |
345 var step = count >> 1; | |
346 var middle = first + step; | |
347 if (value >= this[middle]) { | |
348 first = middle + 1; | |
349 count -= step + 1; | |
350 } else | |
351 count = step; | |
352 } | |
353 return first; | |
354 } | |
355 }); | |
356 | |
357 Object.defineProperty(Array.prototype, "rotate", | 333 Object.defineProperty(Array.prototype, "rotate", |
358 { | 334 { |
359 /** | 335 /** |
360 * @param {number} index | 336 * @param {number} index |
361 * @return {Array.<*>} | 337 * @return {Array.<*>} |
362 * @this {Array.<*>} | 338 * @this {Array.<*>} |
363 */ | 339 */ |
364 value: function(index) | 340 value: function(index) |
365 { | 341 { |
366 var result = []; | 342 var result = []; |
(...skipping 96 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
463 if (pivotPosition === k) | 439 if (pivotPosition === k) |
464 return this[k]; | 440 return this[k]; |
465 else if (pivotPosition > k) | 441 else if (pivotPosition > k) |
466 high = pivotPosition - 1; | 442 high = pivotPosition - 1; |
467 else | 443 else |
468 low = pivotPosition + 1; | 444 low = pivotPosition + 1; |
469 } | 445 } |
470 } | 446 } |
471 }); | 447 }); |
472 | 448 |
473 /** | 449 Object.defineProperty(Array.prototype, "lowerBound", |
474 * @param {*} object | |
475 * @param {Array.<*>} array | |
476 * @param {function(*, *): number} comparator | |
477 * @return {number} | |
478 */ | |
479 function binarySearch(object, array, comparator) | |
480 { | 450 { |
481 var first = 0; | 451 /** |
482 var last = array.length - 1; | 452 * Return index of the leftmost element that is equal or greater |
| 453 * than the specimen object. If there's no such element (i.e. all |
| 454 * elements are smaller than the specimen) returns array.length. |
| 455 * The function works for sorted array. |
| 456 * |
| 457 * @this {Array.<*>} |
| 458 * @param {*} object |
| 459 * @param {function(*,*):number=} comparator |
| 460 * @return {number} |
| 461 */ |
| 462 value: function(object, comparator) |
| 463 { |
| 464 function defaultComparator(a, b) |
| 465 { |
| 466 return a - b; |
| 467 } |
| 468 comparator = comparator || defaultComparator; |
| 469 var l = 0; |
| 470 var r = this.length; |
| 471 while (l < r) { |
| 472 var m = (l + r) >> 1; |
| 473 if (comparator(object, this[m]) > 0) |
| 474 l = m + 1; |
| 475 else |
| 476 r = m; |
| 477 } |
| 478 return r; |
| 479 } |
| 480 }); |
483 | 481 |
484 while (first <= last) { | 482 Object.defineProperty(Array.prototype, "upperBound", |
485 var mid = (first + last) >> 1; | 483 { |
486 var c = comparator(object, array[mid]); | 484 /** |
487 if (c > 0) | 485 * Return index of the leftmost element that is greater |
488 first = mid + 1; | 486 * than the specimen object. If there's no such element (i.e. all |
489 else if (c < 0) | 487 * elements are smaller than the specimen) returns array.length. |
490 last = mid - 1; | 488 * The function works for sorted array. |
491 else | 489 * |
492 return mid; | 490 * @this {Array.<*>} |
| 491 * @param {*} object |
| 492 * @param {function(*,*):number=} comparator |
| 493 * @return {number} |
| 494 */ |
| 495 value: function(object, comparator) |
| 496 { |
| 497 function defaultComparator(a, b) |
| 498 { |
| 499 return a - b; |
| 500 } |
| 501 comparator = comparator || defaultComparator; |
| 502 var l = 0; |
| 503 var r = this.length; |
| 504 while (l < r) { |
| 505 var m = (l + r) >> 1; |
| 506 if (comparator(object, this[m]) >= 0) |
| 507 l = m + 1; |
| 508 else |
| 509 r = m; |
| 510 } |
| 511 return r; |
493 } | 512 } |
494 | 513 }); |
495 // Return the nearest lesser index negated minus 2, i.e.: | |
496 // "-1" means "-1", "-2" means "0, "-3" means "1", etc. | |
497 return -(first + 1); | |
498 } | |
499 | 514 |
500 Object.defineProperty(Array.prototype, "binaryIndexOf", | 515 Object.defineProperty(Array.prototype, "binaryIndexOf", |
501 { | 516 { |
502 /** | 517 /** |
| 518 * @this {Array.<*>} |
503 * @param {*} value | 519 * @param {*} value |
504 * @param {function(*, *): number} comparator | 520 * @param {function(*,*):number} comparator |
505 * @return {number} | 521 * @return {number} |
506 * @this {Array.<*>} | |
507 */ | 522 */ |
508 value: function(value, comparator) | 523 value: function(value, comparator) |
509 { | 524 { |
510 var result = binarySearch(value, this, comparator); | 525 var index = this.lowerBound(value, comparator); |
511 return result >= 0 ? result : -1; | 526 return index < this.length && comparator(value, this[index]) === 0 ? ind
ex : -1; |
512 } | 527 } |
513 }); | 528 }); |
514 | 529 |
515 Object.defineProperty(Array.prototype, "select", | 530 Object.defineProperty(Array.prototype, "select", |
516 { | 531 { |
517 /** | 532 /** |
518 * @param {string} field | 533 * @param {string} field |
519 * @return {!Array.<*>} | 534 * @return {!Array.<*>} |
520 * @this {Array.<*>} | 535 * @this {Array.<*>} |
521 */ | 536 */ |
(...skipping 12 matching lines...) Expand all Loading... |
534 * @return {*} | 549 * @return {*} |
535 * @this {Array.<*>} | 550 * @this {Array.<*>} |
536 */ | 551 */ |
537 value: function() | 552 value: function() |
538 { | 553 { |
539 return this[this.length - 1]; | 554 return this[this.length - 1]; |
540 } | 555 } |
541 }); | 556 }); |
542 | 557 |
543 /** | 558 /** |
544 * @param {*} anObject | 559 * @param {*} object |
545 * @param {Array.<*>} aList | 560 * @param {Array.<*>} list |
546 * @param {function(*, *)} aFunction | 561 * @param {function(*,*):number=} comparator |
547 * @param {boolean=} insertionIndexAfter | 562 * @param {boolean=} insertionIndexAfter |
548 * @return {number} | 563 * @return {number} |
549 */ | 564 */ |
550 function insertionIndexForObjectInListSortedByFunction(anObject, aList, aFunctio
n, insertionIndexAfter) | 565 function insertionIndexForObjectInListSortedByFunction(object, list, comparator,
insertionIndexAfter) |
551 { | 566 { |
552 var index = binarySearch(anObject, aList, aFunction); | 567 if (insertionIndexAfter) |
553 if (index < 0) { | 568 return list.upperBound(object, comparator); |
554 // See binarySearch implementation. | 569 else |
555 return -index - 1; | 570 return list.lowerBound(object, comparator); |
556 } | |
557 | |
558 if (!insertionIndexAfter) { | |
559 // Return the first occurence of an item in the list. | |
560 while (index > 0 && aFunction(anObject, aList[index - 1]) === 0) | |
561 index--; | |
562 return index; | |
563 } | |
564 // Return the last occurence of an item in the list. | |
565 while (index < aList.length && aFunction(anObject, aList[index]) === 0) | |
566 index++; | |
567 return index; | |
568 } | 571 } |
569 | 572 |
570 /** | 573 /** |
571 * @param {string} format | 574 * @param {string} format |
572 * @param {...*} var_arg | 575 * @param {...*} var_arg |
573 * @return {string} | 576 * @return {string} |
574 */ | 577 */ |
575 String.sprintf = function(format, var_arg) | 578 String.sprintf = function(format, var_arg) |
576 { | 579 { |
577 return String.vsprintf(format, Array.prototype.slice.call(arguments, 1)); | 580 return String.vsprintf(format, Array.prototype.slice.call(arguments, 1)); |
(...skipping 703 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1281 { | 1284 { |
1282 console.assert(this._pendingIncomingCallbacksCount > 0); | 1285 console.assert(this._pendingIncomingCallbacksCount > 0); |
1283 if (userCallback) { | 1286 if (userCallback) { |
1284 var args = Array.prototype.slice.call(arguments, 1); | 1287 var args = Array.prototype.slice.call(arguments, 1); |
1285 userCallback.apply(null, args); | 1288 userCallback.apply(null, args); |
1286 } | 1289 } |
1287 if (!--this._pendingIncomingCallbacksCount && this._outgoingCallback) | 1290 if (!--this._pendingIncomingCallbacksCount && this._outgoingCallback) |
1288 this._outgoingCallback(); | 1291 this._outgoingCallback(); |
1289 } | 1292 } |
1290 } | 1293 } |
OLD | NEW |