1/** 2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16package std.core; 17 18// NOTE: autogenerated file 19 20export const KEY_NOT_FOUND = -1; 21 22// C++ semantics 23// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 24// ^ ^ 25// | | 26// | upper bound 27// lower bound 28 29/** 30 * tries to find a lower bound of a key in sorted arr. 31 * The array has to be sorted before calling this function. 32 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 33 * 34 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 35 * 36 * @param key a value to find lower bound of. It may be not in arr, lower bound will present anyway 37 * 38 * @param startIndex an index of arr to begin search with 39 * 40 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 41 * 42 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 43 */ 44export function lowerBoundSearch(arr: boolean[], key: boolean, startIndex: int, endIndex: int): int { 45 if (!checkRange(arr.length, startIndex, endIndex)){ 46 throw new RangeError("lowerBoundSearch: bounds verification failed") 47 } 48 49 let left: int = startIndex; 50 let len: int = endIndex - startIndex; 51 52 while (len > 0) { 53 let half: int = len >>> 1; 54 let middle: int = left + half; 55 56 if (arr[middle] == false && key == true) { 57 left = middle + 1; 58 len -= half + 1; 59 } else { 60 len = half; 61 } 62 } 63 64 return left; 65} 66 67/** 68 * tries to find a lower bound of a key in sorted arr. 69 * The array has to be sorted before calling this function. 70 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 71 * 72 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 73 * 74 * @param key a value to find lower bound of. It may be not in arr, lower bound will present anyway 75 * 76 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 77 */ 78export function lowerBoundSearch(arr: boolean[], key: boolean): int { 79 return lowerBoundSearch(arr, key, 0, arr.length); 80} 81 82/** 83 * tries to find an upper bound of a key in sorted arr. 84 * The array has to be sorted before calling this function. 85 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 86 * 87 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 88 * 89 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 90 * 91 * @param startIndex an index of arr to begin search with 92 * 93 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 94 * 95 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 96 */ 97export function upperBoundSearch(arr: boolean[], key: boolean, startIndex: int, endIndex: int): int { 98 if (!checkRange(arr.length, startIndex, endIndex)) { 99 throw new RangeError("upperBoundSearch: bounds verification failed") 100 } 101 102 let left: int = startIndex; 103 let len: int = endIndex - startIndex; 104 105 while (len > 0) { 106 let half: int = len >>> 1; 107 let middle: int = left + half; 108 109 if (arr[middle] == false && key == true || arr[middle] == key) { 110 left = middle + 1; 111 len -= half + 1; 112 } else { 113 len = half; 114 } 115 } 116 117 return left; 118} 119 120/** 121 * tries to find an upper bound of a key in sorted arr. 122 * The array has to be sorted before calling this function. 123 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 124 * 125 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 126 * 127 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 128 * 129 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 130 */ 131export function upperBoundSearch(arr: boolean[], key: boolean): int { 132 return upperBoundSearch(arr, key, 0, arr.length); 133} 134 135/** 136 * Makes an array shallow copy 137 * 138 * @param src source array to be copied 139 * @returns copy of `src` 140 */ 141export function copyOf(src: boolean[]): boolean[] { 142 const r = new boolean[src.length]; 143 try { 144 copyTo(src, r, 0, 0, src.length); 145 } catch (e) { 146 // ignore 147 } 148 return r; 149} 150 151/** 152 * copies src array into dst with respect to passed indexes. 153 * dst must have enough space, otherwise out-of-bounds might occur 154 * 155 * @param src source array to be copied 156 * 157 * @param dst destination array 158 * 159 * @param dstStart index of dst to start from 160 * 161 * @param srcStart index of src to start from 162 * 163 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 164 * 165 * @example: copy src to dst 166 * ``` 167 * copyTo(src, dst, 0, 0, src.length) 168 * ``` 169 */ 170export function copyTo(src: boolean[], dst: boolean[], dstStart: int, srcStart: int, srcEnd: int): void { 171 if (!checkRange(src.length, srcStart, srcEnd)) { 172 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 173 } 174 if (!checkRange(dst.length, dstStart, dst.length)) { 175 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 176 } 177 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 178 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 179 } 180 181 let j: int = dstStart; 182 for (let i: int = srcStart; i < srcEnd; i++) { 183 dst[j] = src[i]; 184 j++; 185 } 186} 187 188// C++ semantics 189// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 190// ^ ^ 191// | | 192// | upper bound 193// lower bound 194 195/** 196 * tries to find a lower bound of a key in sorted arr. 197 * The array has to be sorted before calling this function. 198 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 199 * 200 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 201 * 202 * @param key a value to find lower bound of 203 * 204 * @param startIndex an index of arr to begin search with 205 * 206 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 207 * 208 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 209 */ 210export function lowerBoundSearch(arr: byte[], key: byte, startIndex: int, endIndex: int): int { 211 if (!checkRange(arr.length, startIndex, endIndex)){ 212 throw new RangeError("lowerBoundSearch: bounds verification failed") 213 } 214 215 let left: int = startIndex; 216 let len: int = endIndex - startIndex; 217 218 while (len > 0) { 219 let half: int = len >>> 1; 220 let middle: int = left + half; 221 222 if (arr[middle] < key) { 223 left = middle + 1; 224 len -= half + 1; 225 } else { 226 len = half; 227 } 228 } 229 230 return left; 231} 232 233/** 234 * tries to find a lower bound of a key in sorted arr. 235 * The array has to be sorted before calling this function. 236 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 237 * 238 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 239 * 240 * @param key a value to find lower bound of 241 * 242 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 243 */ 244export function lowerBoundSearch(arr: byte[], key: byte): int { 245 return lowerBoundSearch(arr, key, 0, arr.length); 246} 247 248/** 249 * tries to find an upper bound of a key in sorted arr. 250 * The array has to be sorted before calling this function. 251 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 252 * 253 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 254 * 255 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 256 * 257 * @param startIndex an index of arr to begin search with 258 * 259 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 260 * 261 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 262 */ 263export function upperBoundSearch(arr: byte[], key: byte, startIndex: int, endIndex: int): int { 264 if (!checkRange(arr.length, startIndex, endIndex)) { 265 throw new RangeError("upperBoundSearch: bounds verification failed") 266 } 267 268 let left: int = startIndex; 269 let len: int = endIndex - startIndex; 270 271 while (len > 0) { 272 let half: int = len >>> 1; 273 let middle: int = left + half; 274 275 if (arr[middle] <= key) { 276 left = middle + 1; 277 len -= half + 1; 278 } else { 279 len = half; 280 } 281 } 282 283 return left; 284} 285 286/** 287 * tries to find an upper bound of a key in sorted arr. 288 * The array has to be sorted before calling this function. 289 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 290 * 291 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 292 * 293 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 294 * 295 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 296 */ 297export function upperBoundSearch(arr: byte[], key: byte): int { 298 return upperBoundSearch(arr, key, 0, arr.length); 299} 300 301/** 302 * Makes an array shallow copy 303 * 304 * @param src source array to be copied 305 * @returns copy of `src` 306 */ 307export function copyOf(src: byte[]): byte[] { 308 const r = new byte[src.length]; 309 try { 310 copyTo(src, r, 0, 0, src.length); 311 } catch (e) { 312 // ignore 313 } 314 return r; 315} 316 317/** 318 * copies src array into dst with respect to passed indexes. 319 * dst must have enough space, otherwise out-of-bounds might occur 320 * 321 * @param src source array to be copied 322 * 323 * @param dst destination array 324 * 325 * @param dstStart index of dst to start from 326 * 327 * @param srcStart index of src to start from 328 * 329 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 330 * 331 * @example: copy src to dst 332 * ``` 333 * copyTo(src, dst, 0, 0, src.length) 334 * ``` 335 */ 336export function copyTo(src: byte[], dst: byte[], dstStart: int, srcStart: int, srcEnd: int): void { 337 if (!checkRange(src.length, srcStart, srcEnd)) { 338 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 339 } 340 if (!checkRange(dst.length, dstStart, dst.length)) { 341 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 342 } 343 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 344 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 345 } 346 347 let j: int = dstStart; 348 for (let i: int = srcStart; i < srcEnd; i++) { 349 dst[j] = src[i]; 350 j++; 351 } 352} 353 354// C++ semantics 355// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 356// ^ ^ 357// | | 358// | upper bound 359// lower bound 360 361/** 362 * tries to find a lower bound of a key in sorted arr. 363 * The array has to be sorted before calling this function. 364 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 365 * 366 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 367 * 368 * @param key a value to find lower bound of 369 * 370 * @param startIndex an index of arr to begin search with 371 * 372 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 373 * 374 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 375 */ 376export function lowerBoundSearch(arr: short[], key: short, startIndex: int, endIndex: int): int { 377 if (!checkRange(arr.length, startIndex, endIndex)){ 378 throw new RangeError("lowerBoundSearch: bounds verification failed") 379 } 380 381 let left: int = startIndex; 382 let len: int = endIndex - startIndex; 383 384 while (len > 0) { 385 let half: int = len >>> 1; 386 let middle: int = left + half; 387 388 if (arr[middle] < key) { 389 left = middle + 1; 390 len -= half + 1; 391 } else { 392 len = half; 393 } 394 } 395 396 return left; 397} 398 399/** 400 * tries to find a lower bound of a key in sorted arr. 401 * The array has to be sorted before calling this function. 402 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 403 * 404 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 405 * 406 * @param key a value to find lower bound of 407 * 408 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 409 */ 410export function lowerBoundSearch(arr: short[], key: short): int { 411 return lowerBoundSearch(arr, key, 0, arr.length); 412} 413 414/** 415 * tries to find an upper bound of a key in sorted arr. 416 * The array has to be sorted before calling this function. 417 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 418 * 419 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 420 * 421 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 422 * 423 * @param startIndex an index of arr to begin search with 424 * 425 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 426 * 427 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 428 */ 429export function upperBoundSearch(arr: short[], key: short, startIndex: int, endIndex: int): int { 430 if (!checkRange(arr.length, startIndex, endIndex)) { 431 throw new RangeError("upperBoundSearch: bounds verification failed") 432 } 433 434 let left: int = startIndex; 435 let len: int = endIndex - startIndex; 436 437 while (len > 0) { 438 let half: int = len >>> 1; 439 let middle: int = left + half; 440 441 if (arr[middle] <= key) { 442 left = middle + 1; 443 len -= half + 1; 444 } else { 445 len = half; 446 } 447 } 448 449 return left; 450} 451 452/** 453 * tries to find an upper bound of a key in sorted arr. 454 * The array has to be sorted before calling this function. 455 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 456 * 457 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 458 * 459 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 460 * 461 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 462 */ 463export function upperBoundSearch(arr: short[], key: short): int { 464 return upperBoundSearch(arr, key, 0, arr.length); 465} 466 467/** 468 * Makes an array shallow copy 469 * 470 * @param src source array to be copied 471 * @returns copy of `src` 472 */ 473export function copyOf(src: short[]): short[] { 474 const r = new short[src.length]; 475 try { 476 copyTo(src, r, 0, 0, src.length); 477 } catch (e) { 478 // ignore 479 } 480 return r; 481} 482 483/** 484 * copies src array into dst with respect to passed indexes. 485 * dst must have enough space, otherwise out-of-bounds might occur 486 * 487 * @param src source array to be copied 488 * 489 * @param dst destination array 490 * 491 * @param dstStart index of dst to start from 492 * 493 * @param srcStart index of src to start from 494 * 495 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 496 * 497 * @example: copy src to dst 498 * ``` 499 * copyTo(src, dst, 0, 0, src.length) 500 * ``` 501 */ 502export function copyTo(src: short[], dst: short[], dstStart: int, srcStart: int, srcEnd: int): void { 503 if (!checkRange(src.length, srcStart, srcEnd)) { 504 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 505 } 506 if (!checkRange(dst.length, dstStart, dst.length)) { 507 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 508 } 509 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 510 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 511 } 512 513 let j: int = dstStart; 514 for (let i: int = srcStart; i < srcEnd; i++) { 515 dst[j] = src[i]; 516 j++; 517 } 518} 519 520// C++ semantics 521// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 522// ^ ^ 523// | | 524// | upper bound 525// lower bound 526 527/** 528 * tries to find a lower bound of a key in sorted arr. 529 * The array has to be sorted before calling this function. 530 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 531 * 532 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 533 * 534 * @param key a value to find lower bound of 535 * 536 * @param startIndex an index of arr to begin search with 537 * 538 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 539 * 540 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 541 */ 542export function lowerBoundSearch(arr: int[], key: int, startIndex: int, endIndex: int): int { 543 if (!checkRange(arr.length, startIndex, endIndex)){ 544 throw new RangeError("lowerBoundSearch: bounds verification failed") 545 } 546 547 let left: int = startIndex; 548 let len: int = endIndex - startIndex; 549 550 while (len > 0) { 551 let half: int = len >>> 1; 552 let middle: int = left + half; 553 554 if (arr[middle] < key) { 555 left = middle + 1; 556 len -= half + 1; 557 } else { 558 len = half; 559 } 560 } 561 562 return left; 563} 564 565/** 566 * tries to find a lower bound of a key in sorted arr. 567 * The array has to be sorted before calling this function. 568 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 569 * 570 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 571 * 572 * @param key a value to find lower bound of 573 * 574 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 575 */ 576export function lowerBoundSearch(arr: int[], key: int): int { 577 return lowerBoundSearch(arr, key, 0, arr.length); 578} 579 580/** 581 * tries to find an upper bound of a key in sorted arr. 582 * The array has to be sorted before calling this function. 583 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 584 * 585 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 586 * 587 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 588 * 589 * @param startIndex an index of arr to begin search with 590 * 591 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 592 * 593 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 594 */ 595export function upperBoundSearch(arr: int[], key: int, startIndex: int, endIndex: int): int { 596 if (!checkRange(arr.length, startIndex, endIndex)) { 597 throw new RangeError("upperBoundSearch: bounds verification failed") 598 } 599 600 let left: int = startIndex; 601 let len: int = endIndex - startIndex; 602 603 while (len > 0) { 604 let half: int = len >>> 1; 605 let middle: int = left + half; 606 607 if (arr[middle] <= key) { 608 left = middle + 1; 609 len -= half + 1; 610 } else { 611 len = half; 612 } 613 } 614 615 return left; 616} 617 618/** 619 * tries to find an upper bound of a key in sorted arr. 620 * The array has to be sorted before calling this function. 621 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 622 * 623 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 624 * 625 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 626 * 627 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 628 */ 629export function upperBoundSearch(arr: int[], key: int): int { 630 return upperBoundSearch(arr, key, 0, arr.length); 631} 632 633/** 634 * Makes an array shallow copy 635 * 636 * @param src source array to be copied 637 * @returns copy of `src` 638 */ 639export function copyOf(src: int[]): int[] { 640 const r = new int[src.length]; 641 try { 642 copyTo(src, r, 0, 0, src.length); 643 } catch (e) { 644 // ignore 645 } 646 return r; 647} 648 649/** 650 * copies src array into dst with respect to passed indexes. 651 * dst must have enough space, otherwise out-of-bounds might occur 652 * 653 * @param src source array to be copied 654 * 655 * @param dst destination array 656 * 657 * @param dstStart index of dst to start from 658 * 659 * @param srcStart index of src to start from 660 * 661 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 662 * 663 * @example: copy src to dst 664 * ``` 665 * copyTo(src, dst, 0, 0, src.length) 666 * ``` 667 */ 668export function copyTo(src: int[], dst: int[], dstStart: int, srcStart: int, srcEnd: int): void { 669 if (!checkRange(src.length, srcStart, srcEnd)) { 670 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 671 } 672 if (!checkRange(dst.length, dstStart, dst.length)) { 673 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 674 } 675 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 676 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 677 } 678 679 let j: int = dstStart; 680 for (let i: int = srcStart; i < srcEnd; i++) { 681 dst[j] = src[i]; 682 j++; 683 } 684} 685 686// C++ semantics 687// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 688// ^ ^ 689// | | 690// | upper bound 691// lower bound 692 693/** 694 * tries to find a lower bound of a key in sorted arr. 695 * The array has to be sorted before calling this function. 696 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 697 * 698 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 699 * 700 * @param key a value to find lower bound of 701 * 702 * @param startIndex an index of arr to begin search with 703 * 704 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 705 * 706 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 707 */ 708export function lowerBoundSearch(arr: long[], key: long, startIndex: int, endIndex: int): int { 709 if (!checkRange(arr.length, startIndex, endIndex)){ 710 throw new RangeError("lowerBoundSearch: bounds verification failed") 711 } 712 713 let left: int = startIndex; 714 let len: int = endIndex - startIndex; 715 716 while (len > 0) { 717 let half: int = len >>> 1; 718 let middle: int = left + half; 719 720 if (arr[middle] < key) { 721 left = middle + 1; 722 len -= half + 1; 723 } else { 724 len = half; 725 } 726 } 727 728 return left; 729} 730 731/** 732 * tries to find a lower bound of a key in sorted arr. 733 * The array has to be sorted before calling this function. 734 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 735 * 736 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 737 * 738 * @param key a value to find lower bound of 739 * 740 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 741 */ 742export function lowerBoundSearch(arr: long[], key: long): int { 743 return lowerBoundSearch(arr, key, 0, arr.length); 744} 745 746/** 747 * tries to find an upper bound of a key in sorted arr. 748 * The array has to be sorted before calling this function. 749 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 750 * 751 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 752 * 753 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 754 * 755 * @param startIndex an index of arr to begin search with 756 * 757 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 758 * 759 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 760 */ 761export function upperBoundSearch(arr: long[], key: long, startIndex: int, endIndex: int): int { 762 if (!checkRange(arr.length, startIndex, endIndex)) { 763 throw new RangeError("upperBoundSearch: bounds verification failed") 764 } 765 766 let left: int = startIndex; 767 let len: int = endIndex - startIndex; 768 769 while (len > 0) { 770 let half: int = len >>> 1; 771 let middle: int = left + half; 772 773 if (arr[middle] <= key) { 774 left = middle + 1; 775 len -= half + 1; 776 } else { 777 len = half; 778 } 779 } 780 781 return left; 782} 783 784/** 785 * tries to find an upper bound of a key in sorted arr. 786 * The array has to be sorted before calling this function. 787 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 788 * 789 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 790 * 791 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 792 * 793 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 794 */ 795export function upperBoundSearch(arr: long[], key: long): int { 796 return upperBoundSearch(arr, key, 0, arr.length); 797} 798 799/** 800 * Makes an array shallow copy 801 * 802 * @param src source array to be copied 803 * @returns copy of `src` 804 */ 805export function copyOf(src: long[]): long[] { 806 const r = new long[src.length]; 807 try { 808 copyTo(src, r, 0, 0, src.length); 809 } catch (e) { 810 // ignore 811 } 812 return r; 813} 814 815/** 816 * copies src array into dst with respect to passed indexes. 817 * dst must have enough space, otherwise out-of-bounds might occur 818 * 819 * @param src source array to be copied 820 * 821 * @param dst destination array 822 * 823 * @param dstStart index of dst to start from 824 * 825 * @param srcStart index of src to start from 826 * 827 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 828 * 829 * @example: copy src to dst 830 * ``` 831 * copyTo(src, dst, 0, 0, src.length) 832 * ``` 833 */ 834export function copyTo(src: long[], dst: long[], dstStart: int, srcStart: int, srcEnd: int): void { 835 if (!checkRange(src.length, srcStart, srcEnd)) { 836 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 837 } 838 if (!checkRange(dst.length, dstStart, dst.length)) { 839 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 840 } 841 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 842 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 843 } 844 845 let j: int = dstStart; 846 for (let i: int = srcStart; i < srcEnd; i++) { 847 dst[j] = src[i]; 848 j++; 849 } 850} 851 852// C++ semantics 853// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 854// ^ ^ 855// | | 856// | upper bound 857// lower bound 858 859/** 860 * tries to find a lower bound of a key in sorted arr. 861 * The array has to be sorted before calling this function. 862 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 863 * 864 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 865 * 866 * @param key a value to find lower bound of 867 * 868 * @param startIndex an index of arr to begin search with 869 * 870 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 871 * 872 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 873 */ 874export function lowerBoundSearch(arr: float[], key: float, startIndex: int, endIndex: int): int { 875 if (!checkRange(arr.length, startIndex, endIndex)){ 876 throw new RangeError("lowerBoundSearch: bounds verification failed") 877 } 878 879 let left: int = startIndex; 880 let len: int = endIndex - startIndex; 881 882 while (len > 0) { 883 let half: int = len >>> 1; 884 let middle: int = left + half; 885 886 if (arr[middle] < key) { 887 left = middle + 1; 888 len -= half + 1; 889 } else { 890 len = half; 891 } 892 } 893 894 return left; 895} 896 897/** 898 * tries to find a lower bound of a key in sorted arr. 899 * The array has to be sorted before calling this function. 900 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 901 * 902 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 903 * 904 * @param key a value to find lower bound of 905 * 906 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 907 */ 908export function lowerBoundSearch(arr: float[], key: float): int { 909 return lowerBoundSearch(arr, key, 0, arr.length); 910} 911 912/** 913 * tries to find an upper bound of a key in sorted arr. 914 * The array has to be sorted before calling this function. 915 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 916 * 917 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 918 * 919 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 920 * 921 * @param startIndex an index of arr to begin search with 922 * 923 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 924 * 925 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 926 */ 927export function upperBoundSearch(arr: float[], key: float, startIndex: int, endIndex: int): int { 928 if (!checkRange(arr.length, startIndex, endIndex)) { 929 throw new RangeError("upperBoundSearch: bounds verification failed") 930 } 931 932 let left: int = startIndex; 933 let len: int = endIndex - startIndex; 934 935 while (len > 0) { 936 let half: int = len >>> 1; 937 let middle: int = left + half; 938 939 if (arr[middle] <= key) { 940 left = middle + 1; 941 len -= half + 1; 942 } else { 943 len = half; 944 } 945 } 946 947 return left; 948} 949 950/** 951 * tries to find an upper bound of a key in sorted arr. 952 * The array has to be sorted before calling this function. 953 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 954 * 955 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 956 * 957 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 958 * 959 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 960 */ 961export function upperBoundSearch(arr: float[], key: float): int { 962 return upperBoundSearch(arr, key, 0, arr.length); 963} 964 965/** 966 * Makes an array shallow copy 967 * 968 * @param src source array to be copied 969 * @returns copy of `src` 970 */ 971export function copyOf(src: float[]): float[] { 972 const r = new float[src.length]; 973 try { 974 copyTo(src, r, 0, 0, src.length); 975 } catch (e) { 976 // ignore 977 } 978 return r; 979} 980 981/** 982 * copies src array into dst with respect to passed indexes. 983 * dst must have enough space, otherwise out-of-bounds might occur 984 * 985 * @param src source array to be copied 986 * 987 * @param dst destination array 988 * 989 * @param dstStart index of dst to start from 990 * 991 * @param srcStart index of src to start from 992 * 993 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 994 * 995 * @example: copy src to dst 996 * ``` 997 * copyTo(src, dst, 0, 0, src.length) 998 * ``` 999 */ 1000export function copyTo(src: float[], dst: float[], dstStart: int, srcStart: int, srcEnd: int): void { 1001 if (!checkRange(src.length, srcStart, srcEnd)) { 1002 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 1003 } 1004 if (!checkRange(dst.length, dstStart, dst.length)) { 1005 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 1006 } 1007 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 1008 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 1009 } 1010 1011 let j: int = dstStart; 1012 for (let i: int = srcStart; i < srcEnd; i++) { 1013 dst[j] = src[i]; 1014 j++; 1015 } 1016} 1017 1018// C++ semantics 1019// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 1020// ^ ^ 1021// | | 1022// | upper bound 1023// lower bound 1024 1025/** 1026 * tries to find a lower bound of a key in sorted arr. 1027 * The array has to be sorted before calling this function. 1028 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 1029 * 1030 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1031 * 1032 * @param key a value to find lower bound of 1033 * 1034 * @param startIndex an index of arr to begin search with 1035 * 1036 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 1037 * 1038 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 1039 */ 1040export function lowerBoundSearch(arr: double[], key: double, startIndex: int, endIndex: int): int { 1041 if (!checkRange(arr.length, startIndex, endIndex)){ 1042 throw new RangeError("lowerBoundSearch: bounds verification failed") 1043 } 1044 1045 let left: int = startIndex; 1046 let len: int = endIndex - startIndex; 1047 1048 while (len > 0) { 1049 let half: int = len >>> 1; 1050 let middle: int = left + half; 1051 1052 if (arr[middle] < key) { 1053 left = middle + 1; 1054 len -= half + 1; 1055 } else { 1056 len = half; 1057 } 1058 } 1059 1060 return left; 1061} 1062 1063/** 1064 * tries to find a lower bound of a key in sorted arr. 1065 * The array has to be sorted before calling this function. 1066 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 1067 * 1068 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1069 * 1070 * @param key a value to find lower bound of 1071 * 1072 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 1073 */ 1074export function lowerBoundSearch(arr: double[], key: double): int { 1075 return lowerBoundSearch(arr, key, 0, arr.length); 1076} 1077 1078/** 1079 * tries to find an upper bound of a key in sorted arr. 1080 * The array has to be sorted before calling this function. 1081 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 1082 * 1083 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1084 * 1085 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 1086 * 1087 * @param startIndex an index of arr to begin search with 1088 * 1089 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 1090 * 1091 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 1092 */ 1093export function upperBoundSearch(arr: double[], key: double, startIndex: int, endIndex: int): int { 1094 if (!checkRange(arr.length, startIndex, endIndex)) { 1095 throw new RangeError("upperBoundSearch: bounds verification failed") 1096 } 1097 1098 let left: int = startIndex; 1099 let len: int = endIndex - startIndex; 1100 1101 while (len > 0) { 1102 let half: int = len >>> 1; 1103 let middle: int = left + half; 1104 1105 if (arr[middle] <= key) { 1106 left = middle + 1; 1107 len -= half + 1; 1108 } else { 1109 len = half; 1110 } 1111 } 1112 1113 return left; 1114} 1115 1116/** 1117 * tries to find an upper bound of a key in sorted arr. 1118 * The array has to be sorted before calling this function. 1119 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 1120 * 1121 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1122 * 1123 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 1124 * 1125 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 1126 */ 1127export function upperBoundSearch(arr: double[], key: double): int { 1128 return upperBoundSearch(arr, key, 0, arr.length); 1129} 1130 1131/** 1132 * Makes an array shallow copy 1133 * 1134 * @param src source array to be copied 1135 * @returns copy of `src` 1136 */ 1137export function copyOf(src: double[]): double[] { 1138 const r = new double[src.length]; 1139 try { 1140 copyTo(src, r, 0, 0, src.length); 1141 } catch (e) { 1142 // ignore 1143 } 1144 return r; 1145} 1146 1147/** 1148 * copies src array into dst with respect to passed indexes. 1149 * dst must have enough space, otherwise out-of-bounds might occur 1150 * 1151 * @param src source array to be copied 1152 * 1153 * @param dst destination array 1154 * 1155 * @param dstStart index of dst to start from 1156 * 1157 * @param srcStart index of src to start from 1158 * 1159 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 1160 * 1161 * @example: copy src to dst 1162 * ``` 1163 * copyTo(src, dst, 0, 0, src.length) 1164 * ``` 1165 */ 1166export function copyTo(src: double[], dst: double[], dstStart: int, srcStart: int, srcEnd: int): void { 1167 if (!checkRange(src.length, srcStart, srcEnd)) { 1168 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 1169 } 1170 if (!checkRange(dst.length, dstStart, dst.length)) { 1171 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 1172 } 1173 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 1174 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 1175 } 1176 1177 let j: int = dstStart; 1178 for (let i: int = srcStart; i < srcEnd; i++) { 1179 dst[j] = src[i]; 1180 j++; 1181 } 1182} 1183 1184// C++ semantics 1185// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7) 1186// ^ ^ 1187// | | 1188// | upper bound 1189// lower bound 1190 1191/** 1192 * tries to find a lower bound of a key in sorted arr. 1193 * The array has to be sorted before calling this function. 1194 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex 1195 * 1196 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1197 * 1198 * @param key a value to find lower bound of 1199 * 1200 * @param startIndex an index of arr to begin search with 1201 * 1202 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 1203 * 1204 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex 1205 */ 1206export function lowerBoundSearch(arr: char[], key: char, startIndex: int, endIndex: int): int { 1207 if (!checkRange(arr.length, startIndex, endIndex)){ 1208 throw new RangeError("lowerBoundSearch: bounds verification failed") 1209 } 1210 1211 let left: int = startIndex; 1212 let len: int = endIndex - startIndex; 1213 1214 while (len > 0) { 1215 let half: int = len >>> 1; 1216 let middle: int = left + half; 1217 1218 if (arr[middle] < key) { 1219 left = middle + 1; 1220 len -= half + 1; 1221 } else { 1222 len = half; 1223 } 1224 } 1225 1226 return left; 1227} 1228 1229/** 1230 * tries to find a lower bound of a key in sorted arr. 1231 * The array has to be sorted before calling this function. 1232 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length 1233 * 1234 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1235 * 1236 * @param key a value to find lower bound of 1237 * 1238 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length 1239 */ 1240export function lowerBoundSearch(arr: char[], key: char): int { 1241 return lowerBoundSearch(arr, key, 0, arr.length); 1242} 1243 1244/** 1245 * tries to find an upper bound of a key in sorted arr. 1246 * The array has to be sorted before calling this function. 1247 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 1248 * 1249 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1250 * 1251 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 1252 * 1253 * @param startIndex an index of arr to begin search with 1254 * 1255 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked 1256 * 1257 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex 1258 */ 1259export function upperBoundSearch(arr: char[], key: char, startIndex: int, endIndex: int): int { 1260 if (!checkRange(arr.length, startIndex, endIndex)) { 1261 throw new RangeError("upperBoundSearch: bounds verification failed") 1262 } 1263 1264 let left: int = startIndex; 1265 let len: int = endIndex - startIndex; 1266 1267 while (len > 0) { 1268 let half: int = len >>> 1; 1269 let middle: int = left + half; 1270 1271 if (arr[middle] <= key) { 1272 left = middle + 1; 1273 len -= half + 1; 1274 } else { 1275 len = half; 1276 } 1277 } 1278 1279 return left; 1280} 1281 1282/** 1283 * tries to find an upper bound of a key in sorted arr. 1284 * The array has to be sorted before calling this function. 1285 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex 1286 * 1287 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect 1288 * 1289 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway 1290 * 1291 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length 1292 */ 1293export function upperBoundSearch(arr: char[], key: char): int { 1294 return upperBoundSearch(arr, key, 0, arr.length); 1295} 1296 1297/** 1298 * Makes an array shallow copy 1299 * 1300 * @param src source array to be copied 1301 * @returns copy of `src` 1302 */ 1303export function copyOf(src: char[]): char[] { 1304 const r = new char[src.length]; 1305 try { 1306 copyTo(src, r, 0, 0, src.length); 1307 } catch (e) { 1308 // ignore 1309 } 1310 return r; 1311} 1312 1313/** 1314 * copies src array into dst with respect to passed indexes. 1315 * dst must have enough space, otherwise out-of-bounds might occur 1316 * 1317 * @param src source array to be copied 1318 * 1319 * @param dst destination array 1320 * 1321 * @param dstStart index of dst to start from 1322 * 1323 * @param srcStart index of src to start from 1324 * 1325 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 1326 * 1327 * @example: copy src to dst 1328 * ``` 1329 * copyTo(src, dst, 0, 0, src.length) 1330 * ``` 1331 */ 1332export function copyTo(src: char[], dst: char[], dstStart: int, srcStart: int, srcEnd: int): void { 1333 if (!checkRange(src.length, srcStart, srcEnd)) { 1334 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 1335 } 1336 if (!checkRange(dst.length, dstStart, dst.length)) { 1337 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 1338 } 1339 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 1340 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 1341 } 1342 1343 let j: int = dstStart; 1344 for (let i: int = srcStart; i < srcEnd; i++) { 1345 dst[j] = src[i]; 1346 j++; 1347 } 1348} 1349 1350/** 1351 * Makes an array shallow copy 1352 * 1353 * @param src source array to be copied 1354 * @returns copy of `src` 1355 */ 1356export function copyOf(src: NullishType[]): NullishType[] { 1357 const r = new NullishType[src.length]; 1358 try { 1359 copyTo(src, r, 0, 0, src.length); 1360 } catch (e) { 1361 // ignore 1362 } 1363 return r; 1364} 1365 1366/** 1367 * copies src array into dst with respect to passed indexes. 1368 * dst must have enough space, otherwise out-of-bounds might occur 1369 * 1370 * @param src source array to be copied 1371 * 1372 * @param dst destination array 1373 * 1374 * @param dstStart index of dst to start from 1375 * 1376 * @param srcStart index of src to start from 1377 * 1378 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied 1379 * 1380 * @example: copy src to dst 1381 * ``` 1382 * copyTo(src, dst, 0, 0, src.length) 1383 * ``` 1384 */ 1385export function copyTo(src: NullishType[], dst: NullishType[], dstStart: int, srcStart: int, srcEnd: int): void { 1386 if (!checkRange(src.length, srcStart, srcEnd)) { 1387 throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed") 1388 } 1389 if (!checkRange(dst.length, dstStart, dst.length)) { 1390 throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed") 1391 } 1392 if (!((srcEnd - srcStart) <= (dst.length - dstStart))) { 1393 throw new ArrayIndexOutOfBoundsError("Destination array must have enough space") 1394 } 1395 1396 let j: int = dstStart; 1397 for (let i: int = srcStart; i < srcEnd; i++) { 1398 dst[j] = src[i]; 1399 j++; 1400 } 1401} 1402