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]

Reply via email to