density_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 DENSITY_SKETCH_HPP_
#define DENSITY_SKETCH_HPP_
 
#include <type_traits>
#include <vector>
#include <functional>
#include <numeric>
#include <cmath>
 
#include "common_defs.hpp"
 
namespace datasketches {
 
template<typename T>
struct gaussian_kernel {
  // any two vectors of T, so the sketch's points can use its allocator
  template<typename V1, typename V2>
  T operator()(const V1& v1, const V2& v2) const {
    return exp(-std::inner_product(v1.begin(), v1.end(), v2.begin(), 0.0, std::plus<T>(), [](T a, T b){return (a-b)*(a-b);}));
  }
};

template<
  typename T,
  typename Kernel = gaussian_kernel<T>,
  typename Allocator = std::allocator<T>
>
class density_sketch {
  static_assert(std::is_floating_point<T>::value, "Floating point type expected");
 
public:
  using Vector = std::vector<T, Allocator>;
  using Level = std::vector<Vector, typename std::allocator_traits<Allocator>::template rebind_alloc<Vector>>;
  using Levels = std::vector<Level, typename std::allocator_traits<Allocator>::template rebind_alloc<Level>>;

  density_sketch(uint16_t k, uint32_t dim, const Kernel& kernel = Kernel(), const Allocator& allocator = Allocator());

  uint16_t get_k() const;

  uint32_t get_dim() const;

  bool is_empty() const;

  uint64_t get_n() const;

  uint32_t get_num_retained() const;

  bool is_estimation_mode() const;

  template<typename FwdVector>
  void update(FwdVector&& point);

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

  T get_estimate(const std::vector<T>& point) const;

  Allocator get_allocator() const;

  void serialize(std::ostream& os) const;
 
  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 density_sketch deserialize(std::istream& is,
      const Kernel& kernel=Kernel(), const Allocator& allocator = Allocator());

  static density_sketch deserialize(const void* bytes, size_t size,
      const Kernel& kernel=Kernel(), 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;
 
private:
  enum flags { RESERVED0, RESERVED1, IS_EMPTY };
  static const uint8_t PREAMBLE_INTS_SHORT = 3;
  static const uint8_t PREAMBLE_INTS_LONG = 6;
  static const uint8_t FAMILY_ID = 19;
  static const uint8_t SERIAL_VERSION = 1;
  static const size_t LEVELS_ARRAY_START = 5;
 
  Kernel kernel_;
  uint16_t k_;
  uint32_t dim_;
  uint32_t num_retained_;
  uint64_t n_;
  Levels levels_;
 
  void compact();
  void compact_level(unsigned height);
 
  static void check_k(uint16_t k);
  static void check_serial_version(uint8_t serial_version);
  static void check_family_id(uint8_t family_id);
  static void check_header_validity(uint8_t preamble_ints, uint8_t flags_byte, uint8_t serial_version);
 
  density_sketch(uint16_t k, uint32_t dim, uint32_t num_retained, uint64_t n, Levels&& levels,
                 const Kernel& kernel = Kernel());
};
 
template<typename T, typename K, typename A>
class density_sketch<T, K, A>::const_iterator {
public:
  using Vector = density_sketch<T, K, A>::Vector;
  using iterator_category = std::input_iterator_tag;
  using value_type = std::pair<const Vector&, const uint64_t>;
  using difference_type = void;
  using pointer = 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;
  const value_type operator*() const;
  const return_value_holder<value_type> operator->() const;
private:
  using LevelsIterator = typename density_sketch<T, K, A>::Levels::const_iterator;
  using LevelIterator = typename density_sketch<T, K, A>::Level::const_iterator;
  LevelsIterator levels_it_;
  LevelsIterator levels_end_;
  LevelIterator level_it_;
  unsigned height_;
  friend class density_sketch<T, K, A>;
  const_iterator(LevelsIterator begin, LevelsIterator end);
};
 
} /* namespace datasketches */
 
#include "density_sketch_impl.hpp"
 
#endif