BitMagic-C++
sample22.cpp
Go to the documentation of this file.
1 /*
2 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 For 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 
59 using namespace std;
60 
61 // Utility template function used to print container
62 template<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 
72 int 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.
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
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:2171
bm::id_t size_type
Definition: bm.h:117
void optimize(bm::word_t *temp_block=0, optmode opt_mode=opt_compress, statistics *stat=0)
Optimize memory bitvector&#39;s memory allocation.
Definition: bm.h:3095
bool find_reverse(size_type &pos) const BMNOEXCEPT
Finds last index of 1 bit.
Definition: bm.h:4002
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:2889
pre-processor un-defines to avoid global space pollution (internal)
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:2805
Bit-vector serialization class.
Definition: bmserial.h:75
GAP compression is ON.
Definition: bmconst.h:144
void PrintContainer(T first, T last)
Definition: sample22.cpp:62
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1796
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:6807
size_type serialize(const BV &bv, unsigned char *buf, size_t buf_size)
Bitvector serialization into memory block.
Definition: bmserial.h:2484
Algorithms for bit ranges and intervals.
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&#39;s siz...
Definition: bm.h:2184
bool equal(const bvector< Alloc > &bvect) const BMNOEXCEPT
Equal comparison with an agr bit-vector.
Definition: bm.h:1909
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1802
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:2989
int main(void)
Definition: sample22.cpp:72
Serialization / compression of bvector<>. Set theoretical operations on compressed BLOBs...
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
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:1225
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:1188
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