BitMagic-C++
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.

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;
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;
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)
//
ser.set_bookmarks(true, 64);
ser.serialize(bv3, buf);
cout << "BLOB size=" << buf.size() << endl;
// equivalent of a copy_range right from a compressed BLOB
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;
}