MCPcopy Create free account
hub / github.com/ampproject/amphtml / binarySearch_

Method binarySearch_

src/core/data-structures/priority-queue.js:48–70  ·  view source on GitHub ↗

* Returns index at which item with `target` priority should be inserted. * @param {number} target * @return {number} * @private

(target)

Source from the content-addressed store, hash-verified

46 * @private
47 */
48 binarySearch_(target) {
49 let i = -1;
50 let lo = 0;
51 let hi = this.length;
52 while (lo <= hi) {
53 i = Math.floor((lo + hi) / 2);
54 // This means `target` is the new max priority in the queue.
55 if (i === this.length) {
56 break;
57 }
58 // Stop searching once p[i] >= target AND p[i-1] < target.
59 // This way, we'll return the index of the first occurrence of `target`
60 // priority (if any), which preserves FIFO order of same-priority items.
61 if (this.queue_[i].priority < target) {
62 lo = i + 1;
63 } else if (i > 0 && this.queue_[i - 1].priority >= target) {
64 hi = i - 1;
65 } else {
66 break;
67 }
68 }
69 return i;
70 }
71
72 /**
73 * @param {function(T):*} callback

Callers 1

enqueueMethod · 0.95

Calls

no outgoing calls

Tested by

no test coverage detected