apache/datasketches-rust

Context BloomFilter::invert() flips every bit in the backing array. #194 raised the resulting contract questions and #202 documented the altered guarantees, but left the API-shape decision open: after inversion the type signature is unchanged and still permits every update operation. The semantics after inversion are worth pinning down precisely. Let B be the bit array before inversion and S(x) the k hash positions of an item x: contains(x) == true after inversion means every position of S(x) was 0 in B, so x was definitely not inserted before the inversion. This direction is certain; it has no error probability. contains(x) == false means at least one position of S(x) was 1 in B. All inserted items land here, but so does any absent item with at least one colliding position — with probability roughly 1 - (1 - load_factor)^k, which is close to 1 for typical configurations. So false carries little information. Inversion is therefore not the exact logical complement of the pre-inversio

Aggregation pipelines often own multiple partial TDigestMut states. Repeated borrowed merge calls recompress intermediate results, so consuming an iterator of digests should combine them with one compression pass while retaining the existing borrowed API. PR #261 explored FromIterator<TDigestMut>. A first implementation collected sorted slices into a BinaryHeap and then collected all centroids again, which added allocations and obscured the data flow. The revised approach lazily k-way merges fully compressed sorted buffers directly into compression; inputs with unsorted update tails are materialized and stably sorted once because sorting every tail separately was slower. A focused PR should cover empty and single inputs, mixed k values, stable tie ordering, compressed and uncompressed inputs, allocation-aware benchmarks, and the clone tradeoff between borrowed merge and consuming collection.

Repeated quantile calls scan the same centroid sequence independently. T-Digest should expose batch queries on TDigest and TDigestMut so ranks in nondecreasing order share one traversal while arbitrary input order is preserved. PR #261 explored this with a small cursor over the centroid sequence: sorted ranks use it directly, while unsorted ranks sort indices and scatter answers back into caller order. A focused PR should carry over the API, validation, tests, benchmark, and changelog entry without the merge changes from #261.

Context The Rust implementations currently use different error models for distribution queries: T-Digest returns Option when querying an empty sketch and panics for invalid ranks, NaN rank inputs, or invalid split points. KLL and REQ return Result, but currently classify an empty sketch as InvalidArgument alongside malformed query arguments. Deserializers separately report malformed serialized state as InvalidData. An empty sketch is a valid object state: it can be created, serialized, merged, and updated. However, quantile, rank, CDF, and PMF values are undefined until the sketch has observed data. That condition is distinct from an invalid query argument and from corrupted serialized data. The C++ and Java implementations preserve this distinction with exception categories: DataSketches C++ T-Digest and KLL throw std::runtime_error for queries on empty sketches and std::invalid_argument for invalid query parameters. DataSketches Java T-Digest throws SketchesStateException for quer

Description REQ deserialization currently accepts compactor states that cannot be produced by a valid sketch. Those states can later panic in safe public APIs or violate documented return-value contracts. Two concrete examples on current main: A single-level image with num_sections = 0 deserializes successfully. A subsequent ReqSketch::merge panics at 1u64 << (self.num_sections - 1) because the subtraction underflows. A single-level image whose level-0 compactor declares lg_weight = 63 and contains one item deserializes successfully. Its inclusive rank for that item is approximately 9.22e18, even though ReqSketch::rank promises a result in [0.0, 1.0]. Relevant code: Compactor::deserialize validates only broad section_size_raw and lg_weight bounds ensure_enough_sections assumes num_sections is nonzero ReqSketch::deserialize accepts the reconstructed compactors without validating cross-field invariants Expected fix Validate wire-controlled compactor state before constructing a ReqSke