sample22.cpp

Example on ranges and intervals.

Example on ranges and intervals.BitMagic bvector<> implements high performance operation on RLE coded bit-vectors, transparently supporting all logical operations like intersections. Serialization uses compressive encoding (binary interpolative codes) to efficiently store collections of intervals.

This creates a use case to use compressed bit-vector as an engine for ranges and intervals.

See also
  bm::bvector::set_range
  bm::bvector::clear_range
  bm::bvector::keep_range
  bm::bvector::is_all_one_range
  bm::bvector::any_range
  bm::bvector::find_reverse()
  bm::is_interval
  bm::find_interval_end
  bm::find_interval_start
  bm::deserialize_range
  sample23.cpp
  Algorithms for bit intervals

/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed 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.
For more information please visit: http://bitmagic.io
*/
/** \example sample22.cpp
Example on ranges and intervals.
BitMagic bvector<> implements high performance operation on RLE
coded bit-vectors, transparently supporting all logical operations
like intersections. Serialization uses compressive encoding
(binary interpolative codes) to efficiently store collections
of intervals.
This creates a use case to use compressed bit-vector as an engine
for ranges and intervals.
\sa bm::bvector::set_range
\sa bm::bvector::clear_range
\sa bm::bvector::keep_range
\sa bm::bvector::is_all_one_range
\sa bm::bvector::any_range
\sa bm::bvector::find_reverse()
\sa bm::is_interval
\sa bm::find_interval_end
\sa bm::find_interval_start
\sa bm::deserialize_range
\sa sample23.cpp
\sa bvintervals
*/
/*! \file sample22.cpp
\brief Example: bvector<> - ranges and intervals functions
*/
#include <iostream>
#include <assert.h>
#include "bm.h"
#include "bmserial.h"
#include "bmintervals.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
using namespace std;
// Utility template function used to print container
template<class T> void PrintContainer(T first, T last)
{
if (first == last)
cout << "<EMPTY SET>";
else
for(;first != last; ++first)
cout << *first << ", ";
cout << endl;
}
int main(void)
{
try
{
bm::bvector<> bv(bm::BM_GAP); // use RLE compressed vector from the start
bv.set_range(100, 110); // sets a range of 1s [100, 110] .....11111....
bv.optimize(); // RLE memory compression
cout << "Source set:";
PrintContainer(bv.first(), bv.end());
cout << "bvector<>::is_all_one_range() demo" << endl;
// check is range has no 0s in it "....1111...."
bool all_one = bv.is_all_one_range(100, 110); // true
cout << all_one << endl;
all_one = bv.is_all_one_range(100, 111); // false (last bit is 0)
cout << all_one << endl;
cout << "bvector<>::is_interval() demo" << endl;
// verify if the range is all 1s AND flanked by 0s "...011110..."
bool is_int = bm::is_interval(bv, 100, 110); // true
cout << is_int << endl;
is_int = bm::is_interval(bv, 99, 110); // false (internal range is not all 1s)
cout << is_int << endl;
cout << "bvector<>::any_range() demo" << endl;
// Check is specified interval contains at least one 1
bool any_one = bv.any_range(0, 99); // false
cout << any_one << endl;
any_one = bv.any_range(0, 100); // true
cout << any_one << endl;
cout << "bvector<>::find_reverse() demo" << endl;
bm::bvector<>::size_type pos;
bool found = bv.find_reverse(256, pos);
assert(found);
cout << pos << endl; // 110
// interval boundaries detection
//
//
cout << "bvector<>::find_interval demo" << endl;
// interval end search from interval start
found = bm::find_interval_end(bv, 100, pos);
if (found)
cout << pos << endl; // 110
else
cout << "Not found." << endl;
// interval end start from a non-interval location
// - it will not find anything
found = bm::find_interval_end(bv, 99, pos);
if (found)
cout << pos << endl;
else
cout << "Not found." << endl; // This !
// start search from a position within the interval
found = bm::find_interval_start(bv, 105, pos);
if (found)
cout << pos << endl; // 100
else
cout << "Not found." << endl;
bm::bvector<> bv3(bv);
// range editing
//
cout << endl;
bm::bvector<> bv2;
bv2.copy_range(bv, 101, 105); // make a copy of [101..105]
bv.clear_range(99, 100); // clear bits in [99..100]
PrintContainer(bv.first(), bv.end());
bv.keep_range(99, 105); // clear everything outside [99..105]
PrintContainer(bv.first(), bv.end()); // print edited vector
PrintContainer(bv2.first(), bv2.end()); // print range copy vector
bool eq = bv.equal(bv2); // make sure both vectors are the same
cout << eq << endl; // true
// demo (de)serialization range
// BM can serialize a bit-vector and selectively restore only
// part of it (range). Adding block bookmarks makes target range
// extraction faster.
//
{
// configure serializer to use bookmarks every 64 blocks
// for faster extraction. Higher number gives you smaller BLOB
// but slower speed. Tweak it as needed.
//
// (range deserialization would work even without bookmarks)
//
bm::serializer<bm::bvector<> > ser;
ser.set_bookmarks(true, 64);
bm::serializer<bm::bvector<> >::buffer buf;
ser.serialize(bv3, buf);
cout << "BLOB size=" << buf.size() << endl;
// equivalent of a copy_range right from a compressed BLOB
bm::bvector<> bv4;
bm::deserialize_range(bv4, buf.data(), 101, 105);
PrintContainer(bv4.first(), bv4.end()); // print deserialized range vector
eq = bv4.equal(bv2); // make sure both vectors are the same
cout << eq << endl; // true
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bmintervals.h
Algorithms for bit ranges and intervals.
bmserial.h
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::bvector::equal
bool equal(const bvector< Alloc > &bvect) const BMNOEXCEPT
Equal comparison with an agr bit-vector.
Definition bm.h:2017
bm::bvector::size_type
bvector_size_type size_type
Definition bm.h:121
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1871
bm::bvector::copy_range
void copy_range(const bvector< Alloc > &bvect, size_type left, size_type right)
Copy all bits in the specified closed interval [left,right].
Definition bm.h:7981
bm::bvector::end
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition bm.h:1877
bm::serializer
Bit-vector serialization class.
Definition bmserial.h:76
bm::serializer::set_bookmarks
void set_bookmarks(bool enable, unsigned bm_interval=256) BMNOEXCEPT
Add skip-markers to serialization BLOB for faster range decode at the expense of some BLOB size incre...
Definition bmserial.h:1284
bm::serializer::serialize
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
Definition bmserial.h:2703
bm::BM_GAP
@ BM_GAP
GAP compression is ON.
Definition bmconst.h:148
bm::find_interval_end
bool find_interval_end(const BV &bv, typename BV::size_type from, typename BV::size_type &pos) BMNOEXCEPT
Reverse find index of first 1 bit gap (01110) starting from position Reverse scan for the first 1 in ...
Definition bmintervals.h:438
bm::find_interval_start
bool find_interval_start(const BV &bv, typename BV::size_type from, typename BV::size_type &pos) BMNOEXCEPT
Reverse find index of first 1 bit gap (01110) starting from position Reverse scan for the first 1 in ...
Definition bmintervals.h:315
bm::is_interval
bool is_interval(const BV &bv, typename BV::size_type left, typename BV::size_type right) BMNOEXCEPT
Returns true if range is all 1s flanked with 0s Function performs the test on a closed range [left,...
Definition bmintervals.h:248
bm::deserialize_range
void deserialize_range(BV &bv, const unsigned char *buf, typename BV::size_type from, typename BV::size_type to, const bm::bv_ref_vector< BV > *ref_vect=0)
Bitvector range deserialization from a memory BLOB.
Definition bmserial.h:3200
main
int main(void)
Definition sample1.cpp:43
PrintContainer
void PrintContainer(T first, T last)
Definition sample7.cpp:62