frequent_items_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 FREQUENT_ITEMS_SKETCH_HPP_
#define FREQUENT_ITEMS_SKETCH_HPP_
 
#include <memory>
#include <vector>
#include <iostream>
#include <functional>
#include <type_traits>
 
#include "reverse_purge_hash_map.hpp"
#include "common_defs.hpp"
#include "serde.hpp"
 
namespace datasketches {

enum frequent_items_error_type {
  NO_FALSE_POSITIVES, 
  NO_FALSE_NEGATIVES 
};

template<
  typename T,
  typename W = uint64_t,
  typename H = std::hash<T>,
  typename E = std::equal_to<T>,
  typename A = std::allocator<T>
>
class frequent_items_sketch {
  static_assert(std::is_arithmetic<W>::value, "Arithmetic type expected");
public:
 
  static const uint8_t LG_MIN_MAP_SIZE = 3;

  explicit frequent_items_sketch(uint8_t lg_max_map_size, uint8_t lg_start_map_size = LG_MIN_MAP_SIZE,
      const E& equal = E(), const A& allocator = A());

  void update(const T& item, W weight = 1);

  void update(T&& item, W weight = 1);

  void merge(const frequent_items_sketch& other);

  void merge(frequent_items_sketch&& other);

  void reset();

  bool is_empty() const;

  uint32_t get_num_active_items() const;

  W get_total_weight() const;

  W get_estimate(const T& item) const;

  W get_lower_bound(const T& item) const;

  W get_upper_bound(const T& item) const;

  W get_maximum_error() const;

  double get_epsilon() const;

  static double get_epsilon(uint8_t lg_max_map_size);

  static double get_apriori_error(uint8_t lg_max_map_size, W estimated_total_weight);
 
  class row;
  using vector_row = typename std::vector<row, typename std::allocator_traits<A>::template rebind_alloc<row>>;

  vector_row get_frequent_items(frequent_items_error_type err_type) const;

  vector_row get_frequent_items(frequent_items_error_type err_type, W threshold) const;

  template<typename SerDe = serde<T>>
  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<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>>
  static frequent_items_sketch deserialize(std::istream& is, const SerDe& sd = SerDe(),
      const E& equal = E(), const A& allocator = A());

  template<typename SerDe = serde<T>>
  static frequent_items_sketch deserialize(const void* bytes, size_t size, const SerDe& sd = SerDe(),
      const E& equal = E(), const A& allocator = A());

  string<A> to_string(bool print_items = false) const;
 
private:
  static const uint8_t SERIAL_VERSION = 1;
  static const uint8_t FAMILY_ID = 10;
  static const uint8_t PREAMBLE_LONGS_EMPTY = 1;
  static const uint8_t PREAMBLE_LONGS_NONEMPTY = 4;
  static constexpr double EPSILON_FACTOR = 3.5;
  // Emptiness of a serialized image is determined by preamble longs (1 for empty, 4 otherwise).
  // The flags byte is only cross-checked against it. Due to a mistake different bits were used
  // in C++ and Java to indicate an empty sketch, therefore both are set for compatibility with
  // the historical binary format, and either one is accepted on read. No other flag bits are defined.
  enum flags { IS_EMPTY_1 = 0, IS_EMPTY_2 = 2 };
  W total_weight;
  W offset;
  reverse_purge_hash_map<T, W, H, E, A> map;
  static void check_preamble_longs(uint8_t preamble_longs, uint8_t flags_byte);
  static void check_total_weight(W total_weight);
  static void check_serial_version(uint8_t serial_version);
  static void check_family_id(uint8_t family_id);
  static void check_size(uint8_t lg_cur_size, uint8_t lg_max_size);
 
  // version for integral signed type
  template<typename WW = W, typename std::enable_if<std::is_integral<WW>::value && std::is_signed<WW>::value, int>::type = 0>
  static inline void check_weight(WW weight);
 
  // version for integral unsigned type
  template<typename WW = W, typename std::enable_if<std::is_integral<WW>::value && std::is_unsigned<WW>::value, int>::type = 0>
  static inline void check_weight(WW weight);
 
  // version for floating point type
  template<typename WW = W, typename std::enable_if<std::is_floating_point<WW>::value, int>::type = 0>
  static inline void check_weight(WW weight);
 
  // for deserialize
  class items_deleter;
};

template<typename T, typename W, typename H, typename E, typename A>
class frequent_items_sketch<T, W, H, E, A>::row {
public:
  row(const T* item, W weight, W offset):
    item(item), weight(weight), offset(offset) {}
  const T& get_item() const { return *item; }
  W get_estimate() const { return weight + offset; }
  W get_lower_bound() const { return weight; }
  W get_upper_bound() const { return weight + offset; }
private:
  const T* item;
  W weight;
  W offset;
};
 
}
 
#include "frequent_items_sketch_impl.hpp"
 
# endif