BitMagic-C++
sample22.cpp
Go to the documentation of this file.
1/*
2Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15
16For more information please visit: http://bitmagic.io
17*/
18
19/** \example sample22.cpp
20
21 Example on ranges and intervals.
22
23 BitMagic bvector<> implements high performance operation on RLE
24 coded bit-vectors, transparently supporting all logical operations
25 like intersections. Serialization uses compressive encoding
26 (binary interpolative codes) to efficiently store collections
27 of intervals.
28
29 This creates a use case to use compressed bit-vector as an engine
30 for ranges and intervals.
31
32 \sa bm::bvector::set_range
33 \sa bm::bvector::clear_range
34 \sa bm::bvector::keep_range
35 \sa bm::bvector::is_all_one_range
36 \sa bm::bvector::any_range
37 \sa bm::is_interval
38 \sa bm::find_interval_end
39 \sa bm::find_interval_start
40 \sa bm::deserialize_range
41
42 \sa sample23.cpp
43 \sa bvintervals
44*/
45
46/*! \file sample22.cpp
47 \brief Example: bvector<> - ranges and intervals functions
48*/
49
50#include <iostream>
51
52#include "bm.h"
53#include "bmserial.h"
54#include "bmintervals.h"
55
56using namespace std;
57
58// Utility template function used to print container
59template<class T> void PrintContainer(T first, T last)
60{
61 if (first == last)
62 cout << "<EMPTY SET>";
63 else
64 for(;first != last; ++first)
65 cout << *first << ", ";
66 cout << endl;
67}
68
69int main(void)
70{
71 try
72 {
73 bm::bvector<> bv(bm::BM_GAP); // use RLE compressed vector from the start
74
75 bv.set_range(100, 110); // sets a range of 1s [100, 110] .....11111....
76
77 bv.optimize(); // RLE memory compression
78
79 cout << "Source set:";
80 PrintContainer(bv.first(), bv.end());
81
82 cout << "bvector<>::is_all_one_range() demo" << endl;
83 // check is range has no 0s in it "....1111...."
84 bool all_one = bv.is_all_one_range(100, 110); // true
85 cout << all_one << endl;
86 all_one = bv.is_all_one_range(100, 111); // false (last bit is 0)
87 cout << all_one << endl;
88
89 cout << "bvector<>::is_interval() demo" << endl;
90 // verify if the range is all 1s AND flanked by 0s "...011110..."
91 bool is_int = bm::is_interval(bv, 100, 110); // true
92 cout << is_int << endl;
93 is_int = bm::is_interval(bv, 99, 110); // false (internal range is not all 1s)
94 cout << is_int << endl;
95
96 cout << "bvector<>::any_range() demo" << endl;
97 // Check is specified inetrval contains at least one 1
98 bool any_one = bv.any_range(0, 99); // false
99 cout << any_one << endl;
100 any_one = bv.any_range(0, 100); // true
101 cout << any_one << endl;
102
103 // interval boundaries detection
104 //
105 //
106 cout << "bvector<>::find_interval demo" << endl;
108
109 // interval end search from interval start
110 bool found = bm::find_interval_end(bv, 100, pos);
111 if (found)
112 cout << pos << endl; // 110
113 else
114 cout << "Not found." << endl;
115
116 // interval end start from a non-interval location
117 // - it will not find anything
118 found = bm::find_interval_end(bv, 99, pos);
119 if (found)
120 cout << pos << endl;
121 else
122 cout << "Not found." << endl; // This !
123
124 // start search from a position within the interval
125 found = bm::find_interval_start(bv, 105, pos);
126 if (found)
127 cout << pos << endl; // 100
128 else
129 cout << "Not found." << endl;
130
131 bm::bvector<> bv3(bv);
132
133
134 // range editing
135 //
136 cout << endl;
137
138 bm::bvector<> bv2;
139 bv2.copy_range(bv, 101, 105); // make a copy of [101..105]
140
141 bv.clear_range(99, 100); // clear bits in [99..100]
142 PrintContainer(bv.first(), bv.end());
143
144 bv.keep_range(99, 105); // clear everything outside [99..105]
145 PrintContainer(bv.first(), bv.end()); // print edited vector
146
147 PrintContainer(bv2.first(), bv2.end()); // print range copy vector
148
149 bool eq = bv.equal(bv2); // make sure both vectors are the same
150 cout << eq << endl; // true
151
152 // demo (de)serialization range
153 // BM can serialize a bit-vector and selectively restore only
154 // part of it (range). Adding block bookmarks makes target range
155 // extraction faster.
156 //
157 {
158 // configure serializer to use bookmarks every 64 blocks
159 // for faster extraction. Higher number gives you smaller BLOB
160 // but slower speed. Tweak it as needed.
161 //
162 // (range deserialization would work even without bookmarks)
163 //
165 ser.set_bookmarks(true, 64);
166
167 bm::serializer<bm::bvector<> >::buffer buf;
168 ser.serialize(bv3, buf);
169 cout << "BLOB size=" << buf.size() << endl;
170
171 // equivalent of a copy_range right from a compressed BLOB
172 bm::bvector<> bv4;
173 bm::deserialize_range(bv4, buf.data(), 101, 105);
174
175 PrintContainer(bv4.first(), bv4.end()); // print deserialized range vector
176
177 eq = bv4.equal(bv2); // make sure both vectors are the same
178 cout << eq << endl; // true
179 }
180
181 }
182 catch(std::exception& ex)
183 {
184 std::cerr << ex.what() << std::endl;
185 return 1;
186 }
187
188 return 0;
189}
190
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
Algorithms for bit ranges and intervals.
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs.
bool equal(const bvector< Alloc > &bvect) const BMNOEXCEPT
Equal comparison with an agr bit-vector.
Definition bm.h:1883
bool any_range(size_type left, size_type right) const BMNOEXCEPT
Returns true if any bits in the range are 1s (non-empty interval) Function uses closed interval [left...
Definition bm.h:2865
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector's memory allocation.
Definition bm.h:3071
void keep_range(size_type left, size_type right)
Sets all bits to zero outside of the closed interval [left,right] Expected result: 00000....
Definition bm.h:2145
bool is_all_one_range(size_type left, size_type right) const BMNOEXCEPT
Returns true if all bits in the range are 1s (saturated interval) Function uses closed interval [left...
Definition bm.h:2781
void clear_range(size_type left, size_type right)
Sets all bits to zero in the specified closed interval [left,right] Interval must be inside the bvect...
Definition bm.h:1174
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1770
bvector< Alloc > & set_range(size_type left, size_type right, bool value=true)
Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector's siz...
Definition bm.h:2158
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:6653
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition bm.h:1776
Bit-vector serialization class.
Definition bmserial.h:76
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
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
Definition bmserial.h:2264
@ BM_GAP
GAP compression is ON.
Definition bmconst.h:144
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 ...
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 ...
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,...
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
void PrintContainer(T first, T last)
Definition sample22.cpp:59
int main(void)
Definition sample22.cpp:69