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

Function FindInsertionDense

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

Source from the content-addressed store, hash-verified

400/// Find the insertion point into a dense array
401template <typename ArrowType, typename Accessor>
402int64_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.
435template <typename ArrowType, typename Accessor>

Callers

nothing calls this directly

Calls 2

lengthMethod · 0.45
ValueMethod · 0.45

Tested by

no test coverage detected