This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch kll-weighted-update in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit b81cdf58f27193be9771d09215abd34bbe222ab6 Author: Lee Rhodes <[email protected]> AuthorDate: Sun Nov 15 10:57:01 2026 -0800 KLL: iterator starts at the first non-empty level The const_iterator started at level 0 without skipping empty levels. When level 0 is empty, which a merge can leave, every item was reported with weight 1 instead of the weight of its level. Quantile queries were not affected: the sorted view reads the levels directly. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- kll/include/kll_sketch_impl.hpp | 8 +++++++- kll/test/kll_sketch_test.cpp | 18 ++++++++++++++++++ 2 files changed, 25 insertions(+), 1 deletion(-) diff --git a/kll/include/kll_sketch_impl.hpp b/kll/include/kll_sketch_impl.hpp index d97c43ba..b51da6bd 100644 --- a/kll/include/kll_sketch_impl.hpp +++ b/kll/include/kll_sketch_impl.hpp @@ -1142,7 +1142,13 @@ void kll_sketch<T, C, A>::reset_sorted_view() { template<typename T, typename C, typename A> kll_sketch<T, C, A>::const_iterator::const_iterator(const T* items, const uint32_t* levels, const uint8_t num_levels): items(items), levels(levels), num_levels(num_levels), index(items == nullptr ? levels[num_levels] : levels[0]), level(items == nullptr ? num_levels : 0), weight(1) -{} +{ + // start at the first non-empty level: level zero can be empty after a merge + while (level < num_levels && levels[level] == levels[level + 1]) { + ++level; + weight *= 2; + } +} template<typename T, typename C, typename A> typename kll_sketch<T, C, A>::const_iterator& kll_sketch<T, C, A>::const_iterator::operator++() { diff --git a/kll/test/kll_sketch_test.cpp b/kll/test/kll_sketch_test.cpp index cd49087a..fc09505c 100644 --- a/kll/test/kll_sketch_test.cpp +++ b/kll/test/kll_sketch_test.cpp @@ -970,6 +970,24 @@ TEST_CASE("kll sketch", "[kll_sketch]") { } +TEST_CASE("kll sketch: iterator weights when level zero is empty", "[kll_sketch]") { + // merges can leave level zero empty; the iterator must still give each item the weight of its level + bool found_empty_level_zero = false; + for (int trial = 0; trial < 50; ++trial) { + kll_float_sketch target(8, std::less<float>(), 0); + for (int j = 0; j < 1 + trial % 5; ++j) { + kll_float_sketch sketch(8, std::less<float>(), 0); + for (int i = 0; i < 10 + (trial * 37 + j * 11) % 300; ++i) sketch.update(static_cast<float>(i)); + target.merge(sketch); + } + uint64_t total_weight = 0; + for (const auto pair: target) total_weight += pair.second; + REQUIRE(total_weight == target.get_n()); + if (target.to_string(true, false).find(" 0: 8, 0\n") != std::string::npos) found_empty_level_zero = true; + } + REQUIRE(found_empty_level_zero); +} + TEST_CASE("kll sketch: deserialize rejects inconsistent levels", "[kll_sketch]") { using vector_bytes = kll_sketch<int>::vector_bytes; const size_t k_offset = 4; --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
