| 76 | // suboptimal for tiny or large n, possibly okay as we're not in hot path |
| 77 | template <typename InType, typename Generator> |
| 78 | Status Finalize(KernelContext* ctx, const DataType& type, ExecResult* out, |
| 79 | Generator&& gen) { |
| 80 | using CType = typename TypeTraits<InType>::CType; |
| 81 | |
| 82 | using ValueCountPair = std::pair<CType, uint64_t>; |
| 83 | auto gt = [](const ValueCountPair& lhs, const ValueCountPair& rhs) { |
| 84 | const bool rhs_is_nan = rhs.first != rhs.first; // nan as largest value |
| 85 | return lhs.second > rhs.second || |
| 86 | (lhs.second == rhs.second && (lhs.first < rhs.first || rhs_is_nan)); |
| 87 | }; |
| 88 | |
| 89 | std::priority_queue<ValueCountPair, std::vector<ValueCountPair>, decltype(gt)> min_heap( |
| 90 | std::move(gt)); |
| 91 | |
| 92 | const ModeOptions& options = ModeState::Get(ctx); |
| 93 | while (true) { |
| 94 | const ValueCountPair& value_count = gen(); |
| 95 | DCHECK_NE(value_count.second, 0); |
| 96 | if (value_count.second == kCountEOF) break; |
| 97 | if (static_cast<int64_t>(min_heap.size()) < options.n) { |
| 98 | min_heap.push(value_count); |
| 99 | } else if (gt(value_count, min_heap.top())) { |
| 100 | min_heap.pop(); |
| 101 | min_heap.push(value_count); |
| 102 | } |
| 103 | } |
| 104 | const int64_t n = min_heap.size(); |
| 105 | |
| 106 | CType* mode_buffer; |
| 107 | int64_t* count_buffer; |
| 108 | ARROW_ASSIGN_OR_RAISE(std::tie(mode_buffer, count_buffer), |
| 109 | PrepareOutput<InType>(n, ctx, type, out)); |
| 110 | |
| 111 | for (int64_t i = n - 1; i >= 0; --i) { |
| 112 | std::tie(mode_buffer[i], count_buffer[i]) = min_heap.top(); |
| 113 | min_heap.pop(); |
| 114 | } |
| 115 | |
| 116 | return Status::OK(); |
| 117 | } |
| 118 | |
| 119 | // count value occurrences for integers with narrow value range |
| 120 | // O(1) space, O(n) time |