(key: K, failXor: number, cmp: (a: K, b: K) => number)
| 441 | // If key not found, returns i^failXor where i is the insertion index. |
| 442 | // Callers that don't care whether there was a match will set failXor=0. |
| 443 | indexOf(key: K, failXor: number, cmp: (a: K, b: K) => number): index { |
| 444 | const keys = this.keys |
| 445 | let lo = 0, |
| 446 | hi = keys.length, |
| 447 | mid = hi >> 1 |
| 448 | while (lo < hi) { |
| 449 | const c = cmp(keys[mid]!, key) |
| 450 | if (c < 0) lo = mid + 1 |
| 451 | else if (c > 0) |
| 452 | // key < keys[mid] |
| 453 | hi = mid |
| 454 | else if (c === 0) return mid |
| 455 | else { |
| 456 | // c is NaN or otherwise invalid |
| 457 | if (key === key) |
| 458 | // at least the search key is not NaN |
| 459 | return keys.length |
| 460 | else throw new Error(`BTree: NaN was used as a key`) |
| 461 | } |
| 462 | mid = (lo + hi) >> 1 |
| 463 | } |
| 464 | return mid ^ failXor |
| 465 | } |
| 466 | |
| 467 | // /////////////////////////////////////////////////////////////////////////// |
| 468 | // Leaf Node: misc ////////////////////////////////////////////////////////// |
no outgoing calls