* Returns index at which item with `target` priority should be inserted. * @param {number} target * @return {number} * @private
(target)
| 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 |