BitMagic-C++
sample16.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 sample16.cpp
20 Example for finding first and last bits in bit-vector (dynamic range).
21 
22 Ranges of bit-vectors can be used to find probability of intersection.
23 For instance, in some corner cases AND product can be predicted empty if vectors
24 belong to different ranges.
25 
26  @sa bm::aggregator
27 */
28 
29 /*! \file sample16.cpp
30  \brief Example: how to use bm::aggregator<> for logical operations
31 
32  bm::aggregator<> uses cache blocking techniques and bandwidth optimizations
33  to do logical operations (OR, AND, AND-SUB) faster, than if we do it by
34  combining bit-vectors one by one, sequentially.
35 */
36 
37 #include <stdlib.h>
38 #include <iostream>
39 #include <vector>
40 #include <memory>
41 
42 #include "bm.h"
43 #include "bmaggregator.h"
44 
45 
46 // Utility template function used to print container
47 template<class T> void PrintContainer(T first, T last)
48 {
49  if (first == last)
50  std::cout << "<EMPTY SET>";
51  else
52  for (; first != last; ++first)
53  std::cout << *first << ";";
54  std::cout << std::endl;
55 }
56 
57 
58 const unsigned max_vectors = 10;
59 
60 int main(void)
61 {
62  try
63  {
64  // declare standalone aggregator for logical operations
66 
67  // current version of aggregator is capped at 256 processing limit
69  {
70  std::cerr << "Too many bit-vectors!" << std::endl;
71  return 1;
72  }
73 
74  std::cout << "AGRUMENT (GROUP 0) SETS:" << std::endl;
75  // make vector of bit-vectors, set some bits
76  std::vector<std::unique_ptr<bm::bvector<> > > vect;
77  for (unsigned i = 0; i < max_vectors; ++i)
78  {
79  std::unique_ptr<bm::bvector<>> bv(new bm::bvector<>());
80  bv->set(i);
81  bv->set(i+1);
82  bv->set(10000);
83  bv->set(20000);
84  PrintContainer(bv->first(), bv->end());
85  bv->optimize();
86  vect.push_back(std::move(bv));
87  }
88  std::cout << std::endl;
89 
90  try
91  {
92  // in a loop we add all agruments to the aggregator
93  // (aggregator does not take ownership of pointers it receives)
94  //
95  for (unsigned i = 0; i < vect.size(); ++i)
96  {
97  agg.add(vect[i].get());
98  }
99 
100  bm::bvector<> bv_res; // target vector for aggregation
101 
102  agg.combine_or(bv_res); // perform logical OR on a vector group
103 
104  std::cout << "OR:" << std::endl;
105  PrintContainer(bv_res.first(), bv_res.end()); // 0, 1, 2, 3, 4... 10000, 20000
106 
107  // since we did not call bm::aggregator::reset() the vector group
108  // still remains attached
109 
110  std::cout << "AND:" << std::endl;
111  agg.combine_and(bv_res); // AND on the same vector group
112  PrintContainer(bv_res.first(), bv_res.end()); // 10000, 20000
113 
114  agg.reset(); // reset the aggregator
115 
116  // fused logical AND MINUS example
117  // AND(vector-group-0) SUBstract (AND NOT) vector-group-1
118  for (unsigned i = 0; i < vect.size(); ++i)
119  {
120  const unsigned group0 = 0; // vector group 0
121  agg.add(vect[i].get(), group0);
122  }
123  // Note that we do not set vector group 1 yet, so operation just
124  // runs as a regular AND MINUS an empty-set
125 
126  agg.combine_and_sub(bv_res); // AND-SUB vector group1 and group2
127 
128  std::cout << "AND-SUB(empty):" << std::endl;
129  PrintContainer(bv_res.first(), bv_res.end()); // 10000, 20000
130 
131  bm::bvector<> bv_not { 10, 10000 };
132  agg.add(&bv_not, 1); // add to vector-group-1
133 
134  agg.combine_and_sub(bv_res); // AND-SUB vector group0 minus group1
135 
136  std::cout << "AND-SUB:" << std::endl;
137  PrintContainer(bv_res.first(), bv_res.end()); // 20000
138 
139  agg.reset();
140 
141  }
142  catch(std::exception& ex)
143  {
144  std::cerr << ex.what() << std::endl;
145  agg.reset(); // reset
146  throw;
147  }
148 
149  }
150  catch(std::exception& ex)
151  {
152  std::cerr << ex.what() << std::endl;
153  return 1;
154  }
155 
156 
157  return 0;
158 }
159 
160 
bmaggregator.h
Algorithms for fast aggregation of N bvectors.
bm::aggregator::combine_or
void combine_or(bvector_type &bv_target)
Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg...
Definition: bmaggregator.h:609
bm::aggregator::combine_and
void combine_and(bvector_type &bv_target)
Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of ar...
Definition: bmaggregator.h:617
bm::aggregator
Algorithms for fast aggregation of a group of bit-vectors.
Definition: bmaggregator.h:58
bm::aggregator::combine_and_sub
bool combine_and_sub(bvector_type &bv_target)
Aggregate added group of vectors using fused logical AND-SUB Operation does NOT perform an explicit r...
Definition: bmaggregator.h:625
bm::bvector<>
main
int main(void)
Definition: sample16.cpp:60
bm::aggregator::add
unsigned add(const bvector_type *bv, unsigned agr_group=0) BMNOEXCEPT
Attach source bit-vector to a argument group (0 or 1).
Definition: bmaggregator.h:576
max_vectors
const unsigned max_vectors
Definition: sample16.cpp:58
bm::bvector::end
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition: bm.h:1776
PrintContainer
void PrintContainer(T first, T last)
Definition: sample16.cpp:47
bm::aggregator::reset
void reset() BMNOEXCEPT
Reset aggregate groups, forget all attached vectors.
Definition: bmaggregator.h:542
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1770
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bm::aggregator::max_aggregator_cap
@ max_aggregator_cap
Definition: bmaggregator.h:71