ebpps_sketch.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 _EBPPS_SKETCH_HPP_
#define _EBPPS_SKETCH_HPP_
 
#include "common_defs.hpp"
#include "ebpps_sample.hpp"
#include "optional.hpp"
#include "serde.hpp"
 
#include <random>
#include <string>
#include <vector>
 
namespace datasketches {
 
namespace ebpps_constants {
  const uint32_t MAX_K = ((uint32_t) 1 << 31) - 2;
}
 
template<
  typename T,
  typename A = std::allocator<T>
>
class ebpps_sketch {
 
  public:
    static const uint32_t MAX_K = ebpps_constants::MAX_K;
 
    explicit ebpps_sketch(uint32_t k, const A& allocator = A());
 
    void update(const T& item, double weight = 1.0);
 
    void update(T&& item, double weight = 1.0);
 
    void merge(const ebpps_sketch<T, A>& sketch);
 
    void merge(ebpps_sketch<T, A>&& sketch);
 
    using result_type = typename ebpps_sample<T,A>::result_type;
 
    result_type get_result() const;
 
    inline uint32_t get_k() const;
 
    inline uint64_t get_n() const;
 
    inline double get_cumulative_weight() const;
 
    inline double get_c() const;
    
    inline bool is_empty() const;
    
    A get_allocator() const;
 
    void reset();
 
    template<typename SerDe = serde<T>>
    inline size_t get_serialized_size_bytes(const SerDe& sd = SerDe()) const;
 
    // 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>>;
 
    template<typename SerDe = serde<T>>
    vector_bytes serialize(unsigned header_size_bytes = 0, const SerDe& sd = SerDe()) const;
 
    template<typename SerDe = serde<T>>
    void serialize(std::ostream& os, const SerDe& sd = SerDe()) const;
 
    template<typename SerDe = serde<T>>
    static ebpps_sketch deserialize(const void* bytes, size_t size, const SerDe& sd = SerDe(), const A& allocator = A());
 
    template<typename SerDe = serde<T>>
    static ebpps_sketch deserialize(std::istream& is, const SerDe& sd = SerDe(), const A& allocator = A());
 
    string<A> to_string() const;
 
    string<A> items_to_string() const;
 
    typename ebpps_sample<T,A>::const_iterator begin() const;
 
    typename ebpps_sample<T,A>::const_iterator end() const;
 
  private:
    static const uint8_t PREAMBLE_LONGS_EMPTY  = 1;
    static const uint8_t PREAMBLE_LONGS_FULL   = 5; // C is part of sample_
    static const uint8_t SER_VER = 1;
    static const uint8_t FAMILY_ID  = 19;
    static const uint8_t EMPTY_FLAG_MASK  = 4;
    static const uint8_t HAS_PARTIAL_ITEM_MASK = 8;
 
    A allocator_;
    uint32_t k_;                    // max size of sketch, in items
    uint64_t n_;                    // total number of items processed by the sketch
 
    double cumulative_wt_;          // total weight of items processed by the sketch
    double wt_max_;                 // maximum weight seen so far
    double rho_;                    // latest scaling parameter for downsampling
 
    ebpps_sample<T,A> sample_;      // Object holding the current state of the sample
 
    ebpps_sample<T,A> tmp_;         // Temporary sample of size 1 used in updates
 
    // handles merge after ensuring other.cumulative_wt_ <= this->cumulative_wt_
    // so we can send items in individually
    template<typename O>
    void internal_merge(O&& other);
 
    ebpps_sketch(uint32_t k, uint64_t n, double cumulative_wt, double wt_max, double rho,
                 ebpps_sample<T,A>&& sample, const A& allocator = A());
 
    template<typename FwdItem>
    inline void internal_update(FwdItem&& item, double weight);
 
    // validation
    static uint32_t check_k(uint32_t k);
    static void check_preamble_longs(uint8_t preamble_longs, uint8_t flags);
    static void check_family_and_serialization_version(uint8_t family_id, uint8_t ser_ver);
    static uint32_t validate_and_get_target_size(uint32_t preamble_longs, uint32_t k, uint64_t n);
};
 
} // namespace datasketches
 
#include "ebpps_sketch_impl.hpp"
 
#endif // _EBPPS_SKETCH_HPP_