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::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::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 "bm.h"
#include "bmserial.h"
#include "bmintervals.h"
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 inetrval 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;
// interval boundaries detection
//
//
cout << "bvector<>::find_interval demo" << endl;
// interval end search from interval start
bool 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;
}
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::serializer::serialize
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
Definition: bmserial.h:2264
main
int main(void)
Definition: sample22.cpp:69
bm::bvector<>
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:6667
bm::bvector::equal
bool equal(const bvector< Alloc > &bvect) const BMNOEXCEPT
Equal comparison with an agr bit-vector.
Definition: bm.h:1897
bm::BM_GAP
@ BM_GAP
GAP compression is ON.
Definition: bmconst.h:144
bmintervals.h
Algorithms for bit ranges and intervals.
PrintContainer
void PrintContainer(T first, T last)
Definition: sample22.cpp:59
bm::serializer
Bit-vector serialization class.
Definition: bmserial.h:75
bmserial.h
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
bm::bvector::end
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1790
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:2751
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1784
bm::bvector::size_type
bm::id_t size_type
Definition: bm.h:117
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:1138
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
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::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