MCPcopy Create free account
hub / github.com/apache/arrow / FindInsertionChunk

Function FindInsertionChunk

cpp/src/arrow/compute/kernels/vector_search_sorted.cc:436–486  ·  view source on GitHub ↗

Source from the content-addressed store, hash-verified

434/// Find the insertion chunk in an array of vector chunks. The chunk index is returned.
435template <typename ArrowType, typename Accessor>
436int64_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.
489template <typename ArrowType, typename Accessor>

Callers

nothing calls this directly

Calls 3

sizeMethod · 0.45
lengthMethod · 0.45
ValueMethod · 0.45

Tested by

no test coverage detected