counting.h

#ifndef BF_BLOOM_FILTER_COUNTING_H
#define BF_BLOOM_FILTER_COUNTING_H

#include <bf/counter_vector.h>
#include <bf/bloom_filter.h>
#include <bf/hash.h>

namespace bf {

class spectral_mi_bloom_filter;
class spectral_rm_bloom_filter;

class counting_bloom_filter : public bloom_filter
{
  friend spectral_mi_bloom_filter;
  friend spectral_rm_bloom_filter;

public:
  counting_bloom_filter(hasher h, size_t cells, size_t width);

  counting_bloom_filter(counting_bloom_filter&&) = default;

  using bloom_filter::add;
  using bloom_filter::lookup;

  virtual void add(object const& o) override;
  virtual size_t lookup(object const& o) const override;
  virtual void clear() override;

  void remove(object const& o);

  template <typename T>
  void remove(T const& x)
  {
    remove(wrap(x));
  }

protected:
  std::vector<size_t> find_indices(object const& o, bool part = false) const;

  size_t find_minimum(std::vector<size_t> const& indices) const;

  std::vector<size_t> find_minima(std::vector<size_t> const& indices) const;

  bool increment(std::vector<size_t> const& indices, size_t value = 1);

  bool decrement(std::vector<size_t> const& indices, size_t value = 1);

  size_t count(size_t index) const;

  hasher hasher_;
  counter_vector cells_;
};

class spectral_mi_bloom_filter : public counting_bloom_filter
{
public:
  spectral_mi_bloom_filter(hasher h, size_t cells, size_t width);

  using bloom_filter::add;
  using bloom_filter::lookup;
  using counting_bloom_filter::remove;
  virtual void add(object const& o) override;
};

class spectral_rm_bloom_filter : public bloom_filter
{
public:
  spectral_rm_bloom_filter(hasher h1, size_t cells1, size_t width1,
                           hasher h2, size_t cells2, size_t width2);

  using bloom_filter::add;
  using bloom_filter::lookup;
  virtual void add(object const& o) override;
  virtual size_t lookup(object const& o) const override;
  virtual void clear() override;

  void remove(object const& o);

private:
  counting_bloom_filter first_;
  counting_bloom_filter second_;
};

} // namespace bf

#endif