| 434 | /// Find the insertion chunk in an array of vector chunks. The chunk index is returned. |
| 435 | template <typename ArrowType, typename Accessor> |
| 436 | int64_t FindInsertionChunk(const std::vector<Accessor>& chunks, |
| 437 | const SearchValue<ArrowType>& needle, |
| 438 | SearchSortedOptions::Side side, NullPlacement null_placement) { |
| 439 | // When looking for the Left side, we want equal values to be considered greater |
| 440 | // than the needle (1), otherwise smaller (-1). |
| 441 | const int on_equality = (side == SearchSortedOptions::Left) ? 1 : -1; |
| 442 | int64_t first = 0; |
| 443 | int64_t count = static_cast<int64_t>(chunks.size()); |
| 444 | |
| 445 | auto compare = [&](auto left, auto right) { |
| 446 | // The same comparison function as used for sorting, taking account null_placement |
| 447 | // when NaNs are involved. |
| 448 | // XXX Instead of detecting NaN-ness during each comparison, we could |
| 449 | // take advantage of null_placement to single out the range of NaNs that's at |
| 450 | // the beginning or end of the sorted_values. |
| 451 | return CompareTypeValues<ArrowType>(left, right, SortOrder::Ascending, null_placement, |
| 452 | on_equality); |
| 453 | }; |
| 454 | |
| 455 | while (count > 0) { |
| 456 | const int64_t step = count / 2; |
| 457 | const int64_t it = first + step; |
| 458 | bool advance; |
| 459 | const auto& chunk = chunks[it]; |
| 460 | if (chunk.length() == 0) { |
| 461 | // If nulls are clustered at the start, advance towards the end. |
| 462 | advance = (null_placement == NullPlacement::AtStart); |
| 463 | } else { |
| 464 | auto chunk_first = chunk.Value(0); |
| 465 | auto chunk_last = chunk.Value(chunk.length() - 1); |
| 466 | if (compare(chunk_first, needle) > 0) { |
| 467 | // First chunk value too large => go left |
| 468 | advance = false; |
| 469 | } else if (compare(chunk_last, needle) < 0) { |
| 470 | // Last chunk value too small => go right |
| 471 | advance = true; |
| 472 | } else { |
| 473 | // Insertion point is in this chunk |
| 474 | first = it; |
| 475 | break; |
| 476 | } |
| 477 | } |
| 478 | if (advance) { |
| 479 | first = it + 1; |
| 480 | count -= step + 1; |
| 481 | } else { |
| 482 | count = step; |
| 483 | } |
| 484 | } |
| 485 | return first; |
| 486 | } |
| 487 | |
| 488 | /// Find the insertion point into a chunked array. |
| 489 | template <typename ArrowType, typename Accessor> |