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::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 
56 using namespace std;
57 
58 // Utility template function used to print container
59 template<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 
69 int 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 
bm::bvector::set_range
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
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::bvector::keep_range
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
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:6653
bm::bvector::equal
bool equal(const bvector< Alloc > &bvect) const BMNOEXCEPT
Equal comparison with an agr bit-vector.
Definition: bm.h:1883
bm::BM_GAP
GAP compression is ON.
Definition: bmconst.h:144
bm::bvector::any_range
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
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
bm::bvector::clear_range
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
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:1776
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:1770
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::bvector::optimize
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
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
bm::bvector::is_all_one_range
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