cpc_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 CPC_SKETCH_HPP_
#define CPC_SKETCH_HPP_
 
#include <iostream>
#include <functional>
#include <string>
#include <vector>
 
#include "u32_table.hpp"
#include "cpc_common.hpp"
#include "cpc_compressor.hpp"
#include "cpc_confidence.hpp"
#include "common_defs.hpp"
 
namespace datasketches {
 
// forward declarations
template<typename A> class cpc_sketch_alloc;
template<typename A> class cpc_union_alloc;

using cpc_sketch = cpc_sketch_alloc<std::allocator<uint8_t>>;

template<typename A> void cpc_init();

template<typename A>
class cpc_sketch_alloc {
public:
  using allocator_type = A;
  using vector_bytes = std::vector<uint8_t, typename std::allocator_traits<A>::template rebind_alloc<uint8_t>>;
  using vector_u64 = std::vector<uint64_t, typename std::allocator_traits<A>::template rebind_alloc<uint64_t>>;

  explicit cpc_sketch_alloc(uint8_t lg_k = cpc_constants::DEFAULT_LG_K, uint64_t seed = DEFAULT_SEED, const A& allocator = A());

  A get_allocator() const;

  uint8_t get_lg_k() const;

  bool is_empty() const;

  double get_estimate() const;

  double get_lower_bound(unsigned kappa) const;

  double get_upper_bound(unsigned kappa) const;

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

  void update(uint64_t value);

  void update(int64_t value);

  void update(uint32_t value);

  void update(int32_t value);

  void update(uint16_t value);

  void update(int16_t value);

  void update(uint8_t value);

  void update(int8_t value);

  void update(double value);

  void update(float value);

  void update(const void* value, size_t size);

  string<A> to_string() const;

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

  vector_bytes serialize(unsigned header_size_bytes = 0) const;

  static cpc_sketch_alloc<A> deserialize(std::istream& is, uint64_t seed = DEFAULT_SEED, const A& allocator = A());

  static cpc_sketch_alloc<A> deserialize(const void* bytes, size_t size, uint64_t seed = DEFAULT_SEED, const A& allocator = A());

  static size_t get_max_serialized_size_bytes(uint8_t lg_k);

  uint32_t get_num_coupons() const;

  // this should catch some forms of corruption during serialization-deserialization
  bool validate() const;
 
private:
  static const uint8_t SERIAL_VERSION = 1;
  static const uint8_t FAMILY = 16;
 
  enum flags { IS_BIG_ENDIAN, IS_COMPRESSED, HAS_HIP, HAS_TABLE, HAS_WINDOW };
 
  // Note: except for brief transitional moments, these sketches always obey
  // the following strict mapping between the flavor of a sketch and the
  // number of coupons that it has collected
  enum flavor {
    EMPTY,   //     0 == C <     1
    SPARSE,  //     1 <= C < 3K/32
    HYBRID,  // 3K/32 <= C <   K/2
    PINNED,  //   K/2 <= C < 27K/8  [NB: 27/8 = 3 + 3/8]
    SLIDING  // 27K/8 <= C
  };
 
  uint8_t lg_k;
  uint64_t seed;
  bool was_merged; // is the sketch the result of merging?
  uint32_t num_coupons; // the number of coupons collected so far
 
  u32_table<A> surprising_value_table;
  vector_bytes sliding_window;
  uint8_t window_offset; // derivable from num_coupons, but made explicit for speed
  uint8_t first_interesting_column; // This is part of a speed optimization
 
  double kxp;
  double hip_est_accum;
 
  // for deserialization and cpc_union::get_result()
  cpc_sketch_alloc(uint8_t lg_k, uint32_t num_coupons, uint8_t first_interesting_column, u32_table<A>&& table,
      vector_bytes&& window, bool has_hip, double kxp, double hip_est_accum, uint64_t seed);
 
  inline void row_col_update(uint32_t row_col);
  inline void update_sparse(uint32_t row_col);
  inline void update_windowed(uint32_t row_col);
  inline void update_hip(uint32_t row_col);
  void promote_sparse_to_windowed();
  void move_window();
  void refresh_kxp(const uint64_t* bit_matrix);
 
  friend double get_hip_confidence_lb<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
  friend double get_hip_confidence_ub<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
  friend double get_icon_confidence_lb<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
  friend double get_icon_confidence_ub<A>(const cpc_sketch_alloc<A>& sketch, int kappa);
  double get_hip_estimate() const;
  double get_icon_estimate() const;
 
  inline flavor determine_flavor() const;
  static inline flavor determine_flavor(uint8_t lg_k, uint64_t c);
 
  static inline uint8_t determine_correct_offset(uint8_t lg_k, uint64_t c);
 
  // this produces a full-size k-by-64 bit matrix
  vector_u64 build_bit_matrix() const;
 
  static uint8_t get_preamble_ints(uint32_t num_coupons, bool has_hip, bool has_table, bool has_window);
  inline void write_hip(std::ostream& os) const;
  inline size_t copy_hip_to_mem(void* dst) const;
 
  static void check_lg_k(uint8_t lg_k);
  static void check_num_coupons(uint8_t lg_k, uint32_t num_coupons, uint32_t num_pairs);
 
  friend cpc_compressor<A>;
  friend cpc_union_alloc<A>;
};
 
} /* namespace datasketches */
 
#include "cpc_sketch_impl.hpp"
 
#endif