theta_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 THETA_SKETCH_HPP_
#define THETA_SKETCH_HPP_
 
#include "theta_update_sketch_base.hpp"
#include "compact_theta_sketch_parser.hpp"
 
namespace datasketches {
 
// forward declarations
template<typename A> class theta_sketch_alloc;
template<typename A> class update_theta_sketch_alloc;
template<typename A> class compact_theta_sketch_alloc;
template<typename A> class wrapped_compact_theta_sketch_alloc;

using theta_sketch = theta_sketch_alloc<std::allocator<uint64_t>>;
using update_theta_sketch = update_theta_sketch_alloc<std::allocator<uint64_t>>;
using compact_theta_sketch = compact_theta_sketch_alloc<std::allocator<uint64_t>>;
using wrapped_compact_theta_sketch = wrapped_compact_theta_sketch_alloc<std::allocator<uint64_t>>;

template<typename Allocator = std::allocator<uint64_t>>
class base_theta_sketch_alloc {
public:
 
  virtual ~base_theta_sketch_alloc() = default;

  virtual Allocator get_allocator() const = 0;

  virtual bool is_empty() const = 0;

  double get_estimate() const;

  double get_lower_bound(uint8_t num_std_devs) const;

  double get_upper_bound(uint8_t num_std_devs) const;

  bool is_estimation_mode() const;

  double get_theta() const;

  virtual uint64_t get_theta64() const = 0;

  virtual uint32_t get_num_retained() const = 0;

  virtual uint16_t get_seed_hash() const = 0;

  virtual bool is_ordered() const = 0;

  virtual string<Allocator> to_string(bool print_items = false) const;
 
protected:
  virtual void print_specifics(std::ostringstream& os) const = 0;
  virtual void print_items(std::ostringstream& os) const = 0;
};

template<typename Allocator = std::allocator<uint64_t>>
class theta_sketch_alloc: public base_theta_sketch_alloc<Allocator> {
public:
  using Entry = uint64_t;
  using ExtractKey = trivial_extract_key;
  using iterator = theta_iterator<Entry, ExtractKey>;
  using const_iterator = theta_const_iterator<Entry, ExtractKey>;
 
  virtual ~theta_sketch_alloc() = default;

  virtual iterator begin() = 0;

  virtual iterator end() = 0;

  virtual const_iterator begin() const = 0;

  virtual const_iterator end() const = 0;
 
protected:
  virtual void print_items(std::ostringstream& os) const;
};
 
// forward declaration
template<typename A> class compact_theta_sketch_alloc;

template<typename Allocator = std::allocator<uint64_t>>
class update_theta_sketch_alloc: public theta_sketch_alloc<Allocator> {
public:
  using Base = theta_sketch_alloc<Allocator>;
  using Entry = typename Base::Entry;
  using ExtractKey = typename Base::ExtractKey;
  using iterator = typename Base::iterator;
  using const_iterator = typename Base::const_iterator;
  using theta_table = theta_update_sketch_base<Entry, ExtractKey, Allocator>;
  using resize_factor = typename theta_table::resize_factor;
 
  // No constructor here. Use builder instead.
  class builder;

  update_theta_sketch_alloc(const update_theta_sketch_alloc& other) = default;

  update_theta_sketch_alloc(update_theta_sketch_alloc&& other) noexcept = default;
 
  virtual ~update_theta_sketch_alloc() = default;

  update_theta_sketch_alloc& operator=(const update_theta_sketch_alloc& other) = default;

  update_theta_sketch_alloc& operator=(update_theta_sketch_alloc&& other) = default;
 
  virtual Allocator get_allocator() const;
  virtual bool is_empty() const;
  virtual bool is_ordered() const;
  virtual uint16_t get_seed_hash() const;
  virtual uint64_t get_theta64() const;
  virtual uint32_t get_num_retained() const;

  uint8_t get_lg_k() const;

  resize_factor get_rf() 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* data, size_t length);

  void trim();

  void reset();

  compact_theta_sketch_alloc<Allocator> compact(bool ordered = true, bool trim = false) const;
 
  virtual iterator begin();
  virtual iterator end();
  virtual const_iterator begin() const;
  virtual const_iterator end() const;
 
private:
  theta_table table_;
 
  // for builder
  update_theta_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p,
      uint64_t theta, uint64_t seed, const Allocator& allocator);
 
  virtual void print_specifics(std::ostringstream& os) const;
};

template<typename Allocator = std::allocator<uint64_t>>
class compact_theta_sketch_alloc: public theta_sketch_alloc<Allocator> {
public:
  using Base = theta_sketch_alloc<Allocator>;
  using iterator = typename Base::iterator;
  using const_iterator = typename Base::const_iterator;
  using AllocBytes = typename std::allocator_traits<Allocator>::template rebind_alloc<uint8_t>;
  using vector_bytes = std::vector<uint8_t, AllocBytes>;
 
  static const uint8_t UNCOMPRESSED_SERIAL_VERSION = 3;
  static const uint8_t COMPRESSED_SERIAL_VERSION = 4;
  static const uint8_t SKETCH_TYPE = 3;
 
  // Instances of this type can be obtained:
  // - by compacting an update_theta_sketch_alloc
  // - as a result of a set operation
  // - by deserializing a previously serialized compact sketch

  template<typename Other>
  compact_theta_sketch_alloc(const Other& other, bool ordered);

  compact_theta_sketch_alloc(const compact_theta_sketch_alloc& other) = default;

  compact_theta_sketch_alloc(compact_theta_sketch_alloc&& other) noexcept = default;
 
  virtual ~compact_theta_sketch_alloc() = default;

  compact_theta_sketch_alloc& operator=(const compact_theta_sketch_alloc& other) = default;

  compact_theta_sketch_alloc& operator=(compact_theta_sketch_alloc&& other) = default;
 
  virtual Allocator get_allocator() const;
  virtual bool is_empty() const;
  virtual bool is_ordered() const;
  virtual uint64_t get_theta64() const;
  virtual uint32_t get_num_retained() const;
  virtual uint16_t get_seed_hash() const;

  static size_t get_max_serialized_size_bytes(uint8_t lg_k);

  size_t get_serialized_size_bytes(bool compressed = false) const;

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

  vector_bytes serialize(unsigned header_size_bytes = 0) const;

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

  vector_bytes serialize_compressed(unsigned header_size_bytes = 0) const;
 
  virtual iterator begin();
  virtual iterator end();
  virtual const_iterator begin() const;
  virtual const_iterator end() const;

  static compact_theta_sketch_alloc deserialize(std::istream& is,
      uint64_t seed = DEFAULT_SEED, const Allocator& allocator = Allocator());

  static compact_theta_sketch_alloc deserialize(const void* bytes, size_t size,
      uint64_t seed = DEFAULT_SEED, const Allocator& allocator = Allocator());
 
private:
  enum flags { IS_BIG_ENDIAN, IS_READ_ONLY, IS_EMPTY, IS_COMPACT, IS_ORDERED, IS_SINGLE_ITEM };
 
  bool is_empty_;
  bool is_ordered_;
  uint16_t seed_hash_;
  uint64_t theta_;
  std::vector<uint64_t, Allocator> entries_;
 
  uint8_t get_preamble_longs(bool compressed) const;
  bool is_single_item() const;
  bool is_suitable_for_compression() const;
  uint8_t compute_entry_bits() const;
  uint8_t get_num_entries_bytes() const;
  size_t get_compressed_serialized_size_bytes(uint8_t entry_bits, uint8_t num_entries_bytes) const;
  void serialize_version_4(std::ostream& os) const;
  vector_bytes serialize_version_4(unsigned header_size_bytes = 0) const;
 
  static compact_theta_sketch_alloc deserialize_v1(uint8_t preamble_longs, std::istream& is, uint64_t seed, const Allocator& allocator);
  static compact_theta_sketch_alloc deserialize_v2(uint8_t preamble_longs, std::istream& is, uint64_t seed, const Allocator& allocator);
  static compact_theta_sketch_alloc deserialize_v3(uint8_t preamble_longs, std::istream& is, uint64_t seed, const Allocator& allocator);
  static compact_theta_sketch_alloc deserialize_v4(uint8_t preamble_longs, std::istream& is, uint64_t seed, const Allocator& allocator);
 
  virtual void print_specifics(std::ostringstream& os) const;
 
  template<typename E, typename EK, typename P, typename S, typename CS, typename A> friend class theta_union_base;
  template<typename E, typename EK, typename P, typename S, typename CS, typename A> friend class theta_intersection_base;
  template<typename E, typename EK, typename CS, typename A> friend class theta_set_difference_base;
  template<typename A> friend class update_theta_sketch_alloc;
  compact_theta_sketch_alloc(bool is_empty, bool is_ordered, uint16_t seed_hash, uint64_t theta, std::vector<uint64_t, Allocator>&& entries);
};

template<typename Allocator>
class update_theta_sketch_alloc<Allocator>::builder: public theta_base_builder<builder, Allocator> {
public:
    builder(const Allocator& allocator = Allocator());
    update_theta_sketch_alloc build() const;
};

template<typename Allocator = std::allocator<uint64_t>>
class wrapped_compact_theta_sketch_alloc: public base_theta_sketch_alloc<Allocator> {
public:
  class const_iterator;
 
  Allocator get_allocator() const;
  bool is_empty() const;
  bool is_ordered() const;
  uint64_t get_theta64() const;
  uint32_t get_num_retained() const;
  uint16_t get_seed_hash() const;

  const_iterator begin() const;

  const_iterator end() const;

  static const wrapped_compact_theta_sketch_alloc wrap(const void* bytes, size_t size, uint64_t seed = DEFAULT_SEED, bool dump_on_error = false);
 
protected:
  virtual void print_specifics(std::ostringstream& os) const;
  virtual void print_items(std::ostringstream& os) const;
 
private:
  using data_type = compact_theta_sketch_parser<true>::compact_theta_sketch_data;
  data_type data_;
 
  wrapped_compact_theta_sketch_alloc(const data_type& data);
};
 
template<typename Allocator>
class wrapped_compact_theta_sketch_alloc<Allocator>::const_iterator {
public:
  using iterator_category = std::input_iterator_tag;
  using value_type = const uint64_t;
  using difference_type = void;
  using pointer = value_type*;
  using reference = uint64_t;
 
  const_iterator(const void* ptr, uint8_t entry_bits, uint32_t num_entries, uint32_t index);
  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:
  const void* ptr_;
  uint8_t entry_bits_;
  uint32_t num_entries_;
  uint32_t index_;
  uint64_t previous_;
  bool is_block_mode_;
  uint8_t offset_;
  uint64_t buffer_[8];
 
  inline void unpack1();
  inline void unpack8();
};
 
} /* namespace datasketches */
 
#include "theta_sketch_impl.hpp"
 
#endif