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::bvector::find_reverse()
38 \sa bm::is_interval
39 \sa bm::find_interval_end
40 \sa bm::find_interval_start
41 \sa bm::deserialize_range
42
43 \sa sample23.cpp
44 \sa bvintervals
45*/
46
47/*! \file sample22.cpp
48 \brief Example: bvector<> - ranges and intervals functions
49*/
50
51#include <iostream>
52#include <assert.h>
53
54#include "bm.h"
55#include "bmserial.h"
56#include "bmintervals.h"
57#include "bmundef.h" /* clear the pre-proc defines from BM */
58
59using namespace std;
60
61// Utility template function used to print container
62template<class T> void PrintContainer(T first, T last)
63{
64 if (first == last)
65 cout << "<EMPTY SET>";
66 else
67 for(;first != last; ++first)
68 cout << *first << ", ";
69 cout << endl;
70}
71
72int main(void)
73{
74 try
75 {
76 bm::bvector<> bv(bm::BM_GAP); // use RLE compressed vector from the start
77
78 bv.set_range(100, 110); // sets a range of 1s [100, 110] .....11111....
79
80 bv.optimize(); // RLE memory compression
81
82 cout << "Source set:";
83 PrintContainer(bv.first(), bv.end());
84
85 cout << "bvector<>::is_all_one_range() demo" << endl;
86 // check is range has no 0s in it "....1111...."
87 bool all_one = bv.is_all_one_range(100, 110); // true
88 cout << all_one << endl;
89 all_one = bv.is_all_one_range(100, 111); // false (last bit is 0)
90 cout << all_one << endl;
91
92 cout << "bvector<>::is_interval() demo" << endl;
93 // verify if the range is all 1s AND flanked by 0s "...011110..."
94 bool is_int = bm::is_interval(bv, 100, 110); // true
95 cout << is_int << endl;
96 is_int = bm::is_interval(bv, 99, 110); // false (internal range is not all 1s)
97 cout << is_int << endl;
98
99 cout << "bvector<>::any_range() demo" << endl;
100 // Check is specified interval contains at least one 1
101 bool any_one = bv.any_range(0, 99); // false
102 cout << any_one << endl;
103 any_one = bv.any_range(0, 100); // true
104 cout << any_one << endl;
105
106 cout << "bvector<>::find_reverse() demo" << endl;
108
109 bool found = bv.find_reverse(256, pos);
110 assert(found);
111 cout << pos << endl; // 110
112
113
114 // interval boundaries detection
115 //
116 //
117 cout << "bvector<>::find_interval demo" << endl;
118
119 // interval end search from interval start
120 found = bm::find_interval_end(bv, 100, pos);
121 if (found)
122 cout << pos << endl; // 110
123 else
124 cout << "Not found." << endl;
125
126 // interval end start from a non-interval location
127 // - it will not find anything
128 found = bm::find_interval_end(bv, 99, pos);
129 if (found)
130 cout << pos << endl;
131 else
132 cout << "Not found." << endl; // This !
133
134 // start search from a position within the interval
135 found = bm::find_interval_start(bv, 105, pos);
136 if (found)
137 cout << pos << endl; // 100
138 else
139 cout << "Not found." << endl;
140
141 bm::bvector<> bv3(bv);
142
143
144 // range editing
145 //
146 cout << endl;
147
148 bm::bvector<> bv2;
149 bv2.copy_range(bv, 101, 105); // make a copy of [101..105]
150
151 bv.clear_range(99, 100); // clear bits in [99..100]
152 PrintContainer(bv.first(), bv.end());
153
154 bv.keep_range(99, 105); // clear everything outside [99..105]
155 PrintContainer(bv.first(), bv.end()); // print edited vector
156
157 PrintContainer(bv2.first(), bv2.end()); // print range copy vector
158
159 bool eq = bv.equal(bv2); // make sure both vectors are the same
160 cout << eq << endl; // true
161
162 // demo (de)serialization range
163 // BM can serialize a bit-vector and selectively restore only
164 // part of it (range). Adding block bookmarks makes target range
165 // extraction faster.
166 //
167 {
168 // configure serializer to use bookmarks every 64 blocks
169 // for faster extraction. Higher number gives you smaller BLOB
170 // but slower speed. Tweak it as needed.
171 //
172 // (range deserialization would work even without bookmarks)
173 //
175 ser.set_bookmarks(true, 64);
176
177 bm::serializer<bm::bvector<> >::buffer buf;
178 ser.serialize(bv3, buf);
179 cout << "BLOB size=" << buf.size() << endl;
180
181 // equivalent of a copy_range right from a compressed BLOB
182 bm::bvector<> bv4;
183 bm::deserialize_range(bv4, buf.data(), 101, 105);
184
185 PrintContainer(bv4.first(), bv4.end()); // print deserialized range vector
186
187 eq = bv4.equal(bv2); // make sure both vectors are the same
188 cout << eq << endl; // true
189 }
190
191 }
192 catch(std::exception& ex)
193 {
194 std::cerr << ex.what() << std::endl;
195 return 1;
196 }
197
198 return 0;
199}
200
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.
pre-processor un-defines to avoid global space pollution (internal)
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:115
bool equal(const bvector< Alloc > &bvect) const BMNOEXCEPT
Equal comparison with an agr bit-vector.
Definition: bm.h:1995
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:3387
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:3600
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:2318
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:3303
bvector_size_type size_type
Definition: bm.h:121
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:1194
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1849
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1855
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:2333
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:7743
bool find_reverse(size_type &pos) const BMNOEXCEPT
Finds last index of 1 bit.
Definition: bm.h:4673
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:1287
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
Definition: bmserial.h:2706
@ BM_GAP
GAP compression is ON.
Definition: bmconst.h:147
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
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
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
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:3203
void PrintContainer(T first, T last)
Definition: sample22.cpp:62
int main(void)
Definition: sample22.cpp:72