BitMagic-C++
sample16.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 sample16.cpp
20Example for finding first and last bits in bit-vector (dynamic range).
21
22Ranges of bit-vectors can be used to find probability of intersection.
23For instance, in some corner cases AND product can be predicted empty if vectors
24belong 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
47template<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
58const unsigned max_vectors = 10;
59
60int 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
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
Algorithms for fast aggregation of N bvectors.
Algorithms for fast aggregation of a group of bit-vectors.
void reset() BMNOEXCEPT
Reset aggregate groups, forget all attached vectors.
unsigned add(const bvector_type *bv, unsigned agr_group=0) BMNOEXCEPT
Attach source bit-vector to a argument group (0 or 1).
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...
void combine_or(bvector_type &bv_target)
Aggregate added group of vectors using logical OR Operation does NOT perform an explicit reset of arg...
void combine_and(bvector_type &bv_target)
Aggregate added group of vectors using logical AND Operation does NOT perform an explicit reset of ar...
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:108
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition bm.h:1770
enumerator end() const
Returns enumerator pointing on the next bit after the last.
Definition bm.h:1776
const unsigned max_vectors
Definition sample16.cpp:58
int main(void)
Definition sample1.cpp:38
void PrintContainer(T first, T last)
Definition sample7.cpp:61