req_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 REQ_SKETCH_HPP_
#define REQ_SKETCH_HPP_
 
#include <iterator>
 
#include "req_common.hpp"
#include "req_compactor.hpp"
#include "quantiles_sorted_view.hpp"
#include "optional.hpp"
 
namespace datasketches {

template<
  typename T,
  typename Comparator = std::less<T>, // strict weak ordering function (see C++ named requirements: Compare)
  typename Allocator = std::allocator<T>
>
class req_sketch {
public:
  using value_type = T;
  using comparator = Comparator;
  using allocator_type = Allocator;
  using Compactor = req_compactor<T, Comparator, Allocator>;
  using AllocCompactor = typename std::allocator_traits<Allocator>::template rebind_alloc<Compactor>;
  using vector_double = typename quantiles_sorted_view<T, Comparator, Allocator>::vector_double;

  using quantile_return_type = typename quantiles_sorted_view<T, Comparator, Allocator>::quantile_return_type;

  explicit req_sketch(uint16_t k, bool hra = true, const Comparator& comparator = Comparator(),
      const Allocator& allocator = Allocator());

  req_sketch(const req_sketch& other);

  req_sketch(req_sketch&& other) noexcept;
 
  ~req_sketch();

  req_sketch& operator=(const req_sketch& other);

  req_sketch& operator=(req_sketch&& other);

  template<typename TT, typename CC, typename AA>
  explicit req_sketch(const req_sketch<TT, CC, AA>& other, const Comparator& comparator = Comparator(),
      const Allocator& allocator = Allocator());

  uint16_t get_k() const;

  bool is_HRA() const;

  bool is_empty() const;

  uint64_t get_n() const;

  uint32_t get_num_retained() const;

  bool is_estimation_mode() const;

  template<typename FwdT>
  void update(FwdT&& item);

  template<typename FwdSk>
  void merge(FwdSk&& other);

  const T& get_min_item() const;

  const T& get_max_item() const;

  Comparator get_comparator() const;

  Allocator get_allocator() const;

  double get_rank(const T& item, bool inclusive = true) const;

  vector_double get_PMF(const T* split_points, uint32_t size, bool inclusive = true) const;

  vector_double get_CDF(const T* split_points, uint32_t size, bool inclusive = true) const;

  quantile_return_type get_quantile(double rank, bool inclusive = true) const;

  double get_rank_lower_bound(double rank, uint8_t num_std_dev) const;

  double get_rank_upper_bound(double rank, uint8_t num_std_dev) const;

  static double get_RSE(uint16_t k, double rank, bool hra, uint64_t n);

  template<typename TT = T, typename SerDe = serde<T>, typename std::enable_if<std::is_arithmetic<TT>::value, int>::type = 0>
  size_t get_serialized_size_bytes(const SerDe& sd = SerDe()) const;

  template<typename TT = T, typename SerDe = serde<T>, typename std::enable_if<!std::is_arithmetic<TT>::value, int>::type = 0>
  size_t get_serialized_size_bytes(const SerDe& sd = SerDe()) const;

  template<typename SerDe = serde<T>>
  void serialize(std::ostream& os, 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<Allocator>::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>>
  static req_sketch deserialize(std::istream& is, const SerDe& sd = SerDe(),
      const Comparator& comparator = Comparator(), const Allocator& allocator = Allocator());

  template<typename SerDe = serde<T>>
  static req_sketch deserialize(const void* bytes, size_t size, const SerDe& sd = SerDe(),
      const Comparator& comparator = Comparator(), const Allocator& allocator = Allocator());

  string<Allocator> to_string(bool print_levels = false, bool print_items = false) const;
 
  class const_iterator;

  const_iterator begin() const;

  const_iterator end() const;

  quantiles_sorted_view<T, Comparator, Allocator> get_sorted_view() const;
 
private:
  Comparator comparator_;
  Allocator allocator_;
  uint16_t k_;
  bool hra_;
  uint32_t max_nom_size_;
  uint32_t num_retained_;
  uint64_t n_;
  std::vector<Compactor, AllocCompactor> compactors_;
  optional<T> min_item_;
  optional<T> max_item_;
  mutable quantiles_sorted_view<T, Comparator, Allocator>* sorted_view_;
 
  void setup_sorted_view() const; // modifies mutable state
  void reset_sorted_view();
 
  static const bool LAZY_COMPRESSION = false;
 
  static const uint8_t SERIAL_VERSION = 1;
  static const uint8_t FAMILY = 17;
  static const size_t PREAMBLE_SIZE_BYTES = 8;
  enum flags { RESERVED1, RESERVED2, IS_EMPTY, IS_HIGH_RANK, RAW_ITEMS, IS_LEVEL_ZERO_SORTED };
 
  static constexpr double FIXED_RSE_FACTOR = 0.084;
  static double relative_rse_factor();
 
  uint8_t get_num_levels() const;
  void grow();
  void update_max_nom_size();
  void update_num_retained();
  void compress();
 
  static double get_rank_lb(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n, bool hra);
  static double get_rank_ub(uint16_t k, uint8_t num_levels, double rank, uint8_t num_std_dev, uint64_t n, bool hra);
  static bool is_exact_rank(uint16_t k, uint8_t num_levels, double rank, uint64_t n, bool hra);
 
  // for deserialization
  req_sketch(uint16_t k, bool hra, uint64_t n,
      optional<T>&& min_item, optional<T>&& max_item,
      std::vector<Compactor, AllocCompactor>&& compactors, const Comparator& comparator);
 
  static void check_k(uint16_t k);
  static void check_preamble_ints(uint8_t preamble_ints, uint8_t num_levels);
  static void check_num_levels(uint8_t num_levels, bool raw_items);
  static void check_serial_version(uint8_t serial_version);
  static void check_family_id(uint8_t family_id);
 
  template<typename TT = T, typename std::enable_if<std::is_floating_point<TT>::value, int>::type = 0>
  static inline bool check_update_item(const TT& item) {
    return !std::isnan(item);
  }
 
  template<typename TT = T, typename std::enable_if<!std::is_floating_point<TT>::value, int>::type = 0>
  static inline bool check_update_item(const TT&) {
    return true;
  }
 
  // for type converting constructor
  template<typename TT, typename CC, typename AA> friend class req_sketch;
};
 
template<typename T, typename C, typename A>
class req_sketch<T, C, A>::const_iterator {
public:
  using iterator_category = std::input_iterator_tag;
  using value_type = std::pair<const T&, const uint64_t>;
  using difference_type = void;
  using pointer = const return_value_holder<value_type>;
  using reference = const value_type;
 
  const_iterator& operator++();
  const_iterator& operator++(int);
  bool operator==(const const_iterator& other) const;
  bool operator!=(const const_iterator& other) const;
  reference operator*() const;
  pointer operator->() const;
private:
  using LevelsIterator = typename std::vector<Compactor, AllocCompactor>::const_iterator;
  LevelsIterator levels_it_;
  LevelsIterator levels_end_;
  const T* compactor_it_;
  friend class req_sketch<T, C, A>;
  const_iterator(LevelsIterator begin, LevelsIterator end);
};
 
} /* namespace datasketches */
 
#include "req_sketch_impl.hpp"
 
#endif