Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(920)

Side by Side Diff: Source/devtools/front_end/utilities.js

Issue 18828002: DevTools: Replace binarySearch with lowerBound and upperBound functions (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Rebaseline Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « Source/devtools/front_end/externs.js ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « Source/devtools/front_end/externs.js ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698