| 400 | /// Find the insertion point into a dense array |
| 401 | template <typename ArrowType, typename Accessor> |
| 402 | int64_t FindInsertionDense(const Accessor& array, const SearchValue<ArrowType>& needle, |
| 403 | SearchSortedOptions::Side side, NullPlacement null_placement) { |
| 404 | // When looking for the Left side, we want equal values to be considered greater |
| 405 | // than the needle (1), otherwise smaller (-1). |
| 406 | const int on_equality = (side == SearchSortedOptions::Left) ? 1 : -1; |
| 407 | int64_t first = 0; |
| 408 | int64_t count = array.length(); |
| 409 | |
| 410 | auto compare = [&](auto left, auto right) { |
| 411 | // The same comparison function as used for sorting, taking account null_placement |
| 412 | // when NaNs are involved. |
| 413 | // XXX Instead of detecting NaN-ness during each comparison, we could |
| 414 | // take advantage of null_placement to single out the range of NaNs that's at |
| 415 | // the beginning or end of the array. |
| 416 | return CompareTypeValues<ArrowType>(left, right, SortOrder::Ascending, null_placement, |
| 417 | /*on_equality=*/on_equality); |
| 418 | }; |
| 419 | |
| 420 | while (count > 0) { |
| 421 | const int64_t step = count / 2; |
| 422 | const int64_t it = first + step; |
| 423 | const bool advance = compare(array.Value(it), needle) < 0; |
| 424 | if (advance) { |
| 425 | first = it + 1; |
| 426 | count -= step + 1; |
| 427 | } else { |
| 428 | count = step; |
| 429 | } |
| 430 | } |
| 431 | return first; |
| 432 | } |
| 433 | |
| 434 | /// Find the insertion chunk in an array of vector chunks. The chunk index is returned. |
| 435 | template <typename ArrowType, typename Accessor> |