hll.hpp

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
 
#ifndef _HLL_HPP_
#define _HLL_HPP_
 
#include "common_defs.hpp"
#include "HllUtil.hpp"
 
#include <iostream>
#include <memory>
#include <string>
#include <vector>
 
namespace datasketches {
 
// forward declarations
template<typename A> class hll_sketch_alloc;
template<typename A> class hll_union_alloc;

using hll_sketch = hll_sketch_alloc<std::allocator<uint8_t>>;
using hll_union = hll_union_alloc<std::allocator<uint8_t>>;

enum target_hll_type {
    HLL_4, 
    HLL_6, 
    HLL_8  
};

 
// forward declaration
template<typename A> class HllSketchImpl;
 
template<typename A = std::allocator<uint8_t> >
class hll_sketch_alloc final {
  public:
    explicit hll_sketch_alloc(uint8_t lg_config_k, target_hll_type tgt_type = HLL_4, bool start_full_size = false, const A& allocator = A());

    hll_sketch_alloc(const hll_sketch_alloc<A>& that);

    hll_sketch_alloc(const hll_sketch_alloc<A>& that, target_hll_type tgt_type);

    hll_sketch_alloc(hll_sketch_alloc<A>&& that) noexcept;

    static hll_sketch_alloc deserialize(std::istream& is, const A& allocator = A());

    static hll_sketch_alloc deserialize(const void* bytes, size_t len, const A& allocator = A());

    ~hll_sketch_alloc();

    hll_sketch_alloc& operator=(const hll_sketch_alloc<A>& other);

    hll_sketch_alloc& operator=(hll_sketch_alloc<A>&& other);

    void reset(bool full_size = false);
 
    // This is a convenience alias for users
    // The type returned by the following serialize method
    using vector_bytes = std::vector<uint8_t, typename std::allocator_traits<A>::template rebind_alloc<uint8_t>>;

    vector_bytes serialize_compact(unsigned header_size_bytes = 0) const;

    vector_bytes serialize_updatable() const;

    void serialize_compact(std::ostream& os) const;

    void serialize_updatable(std::ostream& os) const;

    string<A> to_string(bool summary = true,
                        bool detail = false,
                        bool aux_detail = false,
                        bool all = false) const;

    void update(const std::string& datum);

    void update(uint64_t datum);

    void update(uint32_t datum);

    void update(uint16_t datum);

    void update(uint8_t datum);

    void update(int64_t datum);

    void update(int32_t datum);

    void update(int16_t datum);

    void update(int8_t datum);

    void update(double datum);

    void update(float datum);

    void update(const void* data, size_t length_bytes);

    double get_estimate() const;

    double get_composite_estimate() const;

    double get_lower_bound(uint8_t num_std_dev) const;

    double get_upper_bound(uint8_t num_std_dev) const;

    uint8_t get_lg_config_k() const;

    target_hll_type get_target_type() const;

    bool is_compact() const;

    bool is_empty() const;

    uint32_t get_compact_serialization_bytes() const;

    uint32_t get_updatable_serialization_bytes() const;

    static uint32_t get_max_updatable_serialization_bytes(uint8_t lg_k, target_hll_type tgt_type);
  
    static double get_rel_err(bool upper_bound, bool unioned,
                              uint8_t lg_config_k, uint8_t num_std_dev);
 
  private:
    explicit hll_sketch_alloc(HllSketchImpl<A>* that);
 
    void coupon_update(uint32_t coupon);
 
    std::string type_as_string() const;
    std::string mode_as_string() const;
 
    hll_mode get_current_mode() const;
    uint8_t get_serialization_version() const;
    bool is_out_of_order_flag() const;
    bool is_estimation_mode() const;
 
    HllSketchImpl<A>* sketch_impl;
    friend hll_union_alloc<A>;
};

template<typename A = std::allocator<uint8_t> >
class hll_union_alloc {
  public:
    explicit hll_union_alloc(uint8_t lg_max_k, const A& allocator = A());

    double get_estimate() const;

    double get_composite_estimate() const;

    double get_lower_bound(uint8_t num_std_dev) const;

    double get_upper_bound(uint8_t num_std_dev) const;

    uint8_t get_lg_config_k() const;

    target_hll_type get_target_type() const;

    bool is_empty() const;

    void reset();

    hll_sketch_alloc<A> get_result(target_hll_type tgt_type = HLL_4) const;

    void update(const hll_sketch_alloc<A>& sketch);

    void update(hll_sketch_alloc<A>&& sketch);
  
    void update(const std::string& datum);

    void update(uint64_t datum);

    void update(uint32_t datum);

    void update(uint16_t datum);

    void update(uint8_t datum);

    void update(int64_t datum);

    void update(int32_t datum);

    void update(int16_t datum);

    void update(int8_t datum);

    void update(double datum);

    void update(float datum);

    void update(const void* data, size_t length_bytes);

    static double get_rel_err(bool upper_bound, bool unioned,
                              uint8_t lg_config_k, uint8_t num_std_dev);
 
  private:

    inline void union_impl(const hll_sketch_alloc<A>& sketch, uint8_t lg_max_k);
 
    static HllSketchImpl<A>* copy_or_downsample(const HllSketchImpl<A>* src_impl, uint8_t tgt_lg_k);
 
    void coupon_update(uint32_t coupon);
 
    hll_mode get_current_mode() const;
    bool is_out_of_order_flag() const;
    bool is_estimation_mode() const;
 
    // calls couponUpdate on sketch, freeing the old sketch upon changes in hll_mode
    static HllSketchImpl<A>* leak_free_coupon_update(HllSketchImpl<A>* impl, uint32_t coupon);
 
    uint8_t lg_max_k_;
    hll_sketch_alloc<A> gadget_;
};
 
} // namespace datasketches
 
#include "hll.private.hpp"
 
#endif // _HLL_HPP_