count_min.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 COUNT_MIN_HPP_
#define COUNT_MIN_HPP_
 
#include <iterator>
#include <type_traits>
#include <vector>
#include "common_defs.hpp"
 
namespace datasketches {

template <typename W,
          typename Allocator = std::allocator<W>>
class count_min_sketch{
  static_assert(std::is_arithmetic<W>::value, "Arithmetic type expected");
  static_assert(!std::is_same<W, bool>::value, "Boolean weight type is not supported");
public:
  using allocator_type = Allocator;
  using const_iterator = typename std::vector<W, Allocator>::const_iterator;

  count_min_sketch(uint8_t num_hashes, uint32_t num_buckets, uint64_t seed = DEFAULT_SEED, const Allocator& allocator = Allocator());

  uint8_t get_num_hashes() const;

  uint32_t get_num_buckets() const;

  uint64_t get_seed()  const;

   double get_relative_error() const;

  W get_total_weight() const;

  static uint32_t suggest_num_buckets(double relative_error);

  static uint8_t suggest_num_hashes(double confidence);

  W get_estimate(uint64_t item) const;

  W get_estimate(int64_t item) const;

  W get_estimate(const std::string& item) const;

  W get_estimate(const void* item, size_t size) const;

  W get_upper_bound(const void* item, size_t size) const;

  W get_upper_bound(int64_t item) const;

  W get_upper_bound(uint64_t item) const;

  W get_upper_bound(const std::string& item) const;

  W get_lower_bound(const void* item, size_t size) const;

  W get_lower_bound(int64_t item) const;

  W get_lower_bound(uint64_t item) const;

  W get_lower_bound(const std::string& item) const;

  void update(const void* item, size_t size, W weight);

  void update(uint64_t item, W weight = 1);

  void update(int64_t item, W weight = 1);

  void update(const std::string& item, W weight = 1);

  void merge(const count_min_sketch& other_sketch);

  bool is_empty() const;

  string<Allocator> to_string() const;

  const_iterator begin() const;

  const_iterator end() const;
 
  /*
   * The serialized sketch binary form has the following structure
   * Byte 0:
   * 1 - if and only if the sketch is empty
   * 0 - otherwise
   *
   * Byte 1 (serial version), byte 2 (family id), byte 3 (flags):
   * 00000001 - default for now.
   *
   * Bytes 4 - 7:
   * uint8_t zero corresponding to ``empty''
   *
   * Byte 8:
   * uint_8 for number of hash functions
   *
   * Bytes 9, 13
   * 4 bytes : uint32 for number of buckets.
   *
   * Bytes 14, 15:
   * seed_hash
   *
   * Byte 16:
   * uint8_t zero corresponding to ``empty''
   *
   * All remaining bytes from 17-24 follow the pattern of
   * Bytes 17-24:
   * Sketch array entry
   *
 
  0   ||    0   |    1   |    2   |    3   |    4   |    5   |    6   |    7   |
      ||is_empty|ser__ver|familyId| flags  |xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|
 
  1   ||    0   |    1   |    2   |    3   |    4   |    5   |    6   |    7   |
      ||---------- _num_buckets -----------|num_hash|__seed__ __hash__|xxxxxxxx|
 
  2   ||    0   |    1   |    2   |    3   |    4   |    5   |    6   |    7   |
      ||---------------------------- total  weight ----------------------------|
 
  3   ||    0   |    1   |    2   |    3   |    4   |    5   |    6   |    7   |
      ||---------------------------- sketch entries ---------------------------|
 ...
 
   */
 
  
  size_t get_serialized_size_bytes() const;

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

  template<typename Sink>
  size_t serialize_to(Sink&& sink) 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>>;

  vector_bytes serialize(unsigned header_size_bytes = 0) const;

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

  static count_min_sketch deserialize(const void* bytes, size_t size, uint64_t seed=DEFAULT_SEED, const Allocator& allocator = Allocator());

  allocator_type get_allocator() const;
 
private:
  Allocator _allocator;
  uint8_t _num_hashes;
  uint32_t _num_buckets;
  std::vector<W, Allocator> _sketch_array; // the array stored by the sketch
  uint64_t _seed;
  W _total_weight;
  std::vector<uint64_t> hash_seeds;
 
  enum flags {IS_EMPTY};
  static const uint8_t PREAMBLE_LONGS_SHORT = 2; // Empty -> need second byte for sketch parameters
  static const uint8_t PREAMBLE_LONGS_FULL = 3; // Not empty -> need (at least) third byte for total weight.
  static const uint8_t SERIAL_VERSION_1 = 1;
  static const uint8_t FAMILY_ID = 18;
  static const uint8_t NULL_8 = 0;
  static const uint32_t NULL_32 = 0;

  static void check_header_validity(uint8_t preamble_longs, uint8_t serial_version, uint8_t family_id, uint8_t flags_byte);
 
  /*
   * Compute the hash locations for an input item
   * @param item pointer to the data item to be inserted into or queried from the sketch.
   * @param size of the data in bytes
   * @param callback function to invoke for each sketch array location
   */
  template<typename F>
  void foreach_hash_location(const void* item, size_t size, F callback) const;
 
};
 
} /* namespace datasketches */
 
#include "count_min_impl.hpp"
 
#endif