/home/mhx/git/github/libmoost/include/moost/container/bit_filter.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_CONTAINER_BIT_FILTER_HPP_
#define MOOST_CONTAINER_BIT_FILTER_HPP_

#include <vector>
#include <iostream>

#include <bm/bm.h>
#include <bm/bmserial.h>

namespace moost { namespace container {

namespace bit_filter_types
{

struct default_hash
{
   template <typename itemT>
   size_t operator()(itemT const & t) const
   {
      return t;
   }
};

typedef std::vector<unsigned char> serial_buffer_t;

}

template <typename itemT, typename hashT = bit_filter_types::default_hash>
class bit_filter
{
public:
   typedef itemT item_type;
   typedef hashT hash_type;
   typedef bit_filter<item_type, hash_type> this_type;
   typedef bit_filter_types::serial_buffer_t serial_buffer_t;

   bit_filter(
      size_t const size,
      hash_type const & ht = hash_type()
      ) : size_(size), ht_(ht)
   {
   }

   template <typename inputIteratorT>
   bit_filter(
      size_t const size,
      inputIteratorT beg,
      inputIteratorT end,
      bool boptimise = false,
      hash_type const & ht = hash_type()
      ) : size_(size), ht_(ht)
   {
      insert(beg, end, boptimise);
   }

   bit_filter(bit_filter const & rhs)
       : size_(rhs.size_), bv_(rhs.bv_), ht_(rhs.ht_)
   {
   }

   bit_filter & operator = (bit_filter const & rhs)
   {
      if(this != &rhs)
      {
         size_ = rhs.size_;
         bv_ = rhs.bv_;
         ht_ = rhs.ht_;
      }

      return *this;
   }

   void insert(item_type const & t, bool boptimise = false)
   {
      if(!find(t))
      {
         bv_.set(ht_(t) % size_);
      }

      if(boptimise) { optimize(); }
   }

   template <typename inputIteratorT>
   void insert(inputIteratorT beg, inputIteratorT end, bool boptimise = false)
   {
      while(beg != end)
      {
         insert(*beg);
         ++beg;
      }

      if(boptimise) { optimize(); }
   }

   template <typename inputIteratorT>
   void replace(inputIteratorT beg, inputIteratorT end)
   {
      clear();
      insert(beg, end);
   }

   void clear()
   {
      bv_.clear();
   }

   size_t size() const
   {
      return size_;
   }

   bool find(item_type const & t) const
   {
      return bv_.test(ht_(t) % size_);
   }

   template <typename inputIteratorT>
   size_t find(inputIteratorT beg, inputIteratorT end) const
   {
      size_t cnt = 0;
      while(beg != end)
      {
         if(find(*beg))
         {
            ++cnt;
         }

         ++beg;
      }

      return cnt;
   }

   template <typename inputIteratorT, typename outputIteratorT>
   size_t find(inputIteratorT beg, inputIteratorT end, outputIteratorT out) const
   {
      size_t cnt = 0;
      while(beg != end)
      {
         if(find(*beg))
         {
            ++cnt;
            *out = *beg;
            ++out;
         }

         ++beg;
      }

      return cnt;
   }

   bool find(this_type const & rhs) const
   {
      return (this == &rhs) ? true : (bm::any_and(bv_, rhs.bv_) != 0);
   }

   void optimize()
   {
      bv_.optimize();
   }

   size_t serialize(serial_buffer_t & buf, bool boptimise = true)
   {
      // Since we can't deallocate vector memory and since we initially
      // allocate far more than we'll need we use a temporary that can be
      // thrown away after, so we only used as much memory as needed.

      if(boptimise) { optimize(); }

      bm::bvector<>::statistics st;
      bm::serializer<bm::bvector<> > bvs;

      // Optimize things
      bvs.byte_order_serialization(false); // We don't care about supporting different endianess
      bvs.gap_length_serialization(false); // We don't care about GAP levels
      bvs.set_compression_level(4);         // We want maximum compression

      bv_.calc_stat(&st);

      serial_buffer_t tmp_buf(st.max_serialize_mem);
      size_t const used = bvs.serialize(bv_, &tmp_buf[0], tmp_buf.size());
      buf.resize(used);
      buf.insert(buf.begin(), tmp_buf.begin(), tmp_buf.begin() + used);

      return used;
   }

   void deserialize(serial_buffer_t const & buf, bool bclear = true)
   {
      if(bclear) { bv_.clear(); }
      if(!buf.empty())
      {
         bm::deserialize(bv_, &buf[0]);
      }
   }

   bool operator == (this_type const & rhs) const
   {
      return bv_ == rhs.bv_;
   }

   bool operator != (this_type const & rhs) const
   {
      return bv_ != rhs.bv_;
   }

   size_t memory() const
   {
      bm::bvector<>::statistics st;
      bv_.calc_stat(&st);
      return st.memory_used;
   }

   size_t count () const
   {
      return bv_.count();
   }

private:
   size_t size_;
   bm::bvector<> bv_;
   hash_type ht_;
};

template <typename itemT, typename hashT>
bit_filter<itemT, hashT> &  operator >> (
   bit_filter<itemT, hashT> & bf,
   typename bit_filter<itemT, hashT>::serial_buffer_t & buf
   )
{
   bf.serialize(buf);
   return bf;
}

template <typename itemT, typename hashT>
bit_filter<itemT, hashT> & operator << (
   bit_filter<itemT, hashT> & bf,
   typename bit_filter<itemT, hashT>::serial_buffer_t const & buf
   )
{
   bf.deserialize(buf);
   return bf;
}

}}

#endif