BitMagic-C++
sample16.cpp

Example for finding first and last bits in bit-vector (dynamic range).Ranges of bit-vectors can be used to find probability of intersection. For instance, in some corner cases AND product can be predicted empty if vectors belong to different ranges.

@sa bm::aggregator
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/** \example sample16.cpp
Example for finding first and last bits in bit-vector (dynamic range).
Ranges of bit-vectors can be used to find probability of intersection.
For instance, in some corner cases AND product can be predicted empty if vectors
belong to different ranges.
@sa bm::aggregator
*/
/*! \file sample16.cpp
\brief Example: how to use bm::aggregator<> for logical operations
bm::aggregator<> uses cache blocking techniques and bandwidth optimizations
to do logical operations (OR, AND, AND-SUB) faster, than if we do it by
combining bit-vectors one by one, sequentially.
*/
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <memory>
#include "bm.h"
#include "bmaggregator.h"
// Utility template function used to print container
template<class T> void PrintContainer(T first, T last)
{
if (first == last)
std::cout << "<EMPTY SET>";
else
for (; first != last; ++first)
std::cout << *first << ";";
std::cout << std::endl;
}
const unsigned max_vectors = 10;
int main(void)
{
try
{
// declare standalone aggregator for logical operations
// current version of aggregator is capped at 256 processing limit
{
std::cerr << "Too many bit-vectors!" << std::endl;
return 1;
}
std::cout << "AGRUMENT (GROUP 0) SETS:" << std::endl;
// make vector of bit-vectors, set some bits
std::vector<std::unique_ptr<bm::bvector<> > > vect;
for (unsigned i = 0; i < max_vectors; ++i)
{
std::unique_ptr<bm::bvector<>> bv(new bm::bvector<>());
bv->set(i);
bv->set(i+1);
bv->set(10000);
bv->set(20000);
PrintContainer(bv->first(), bv->end());
bv->optimize();
vect.push_back(std::move(bv));
}
std::cout << std::endl;
try
{
// in a loop we add all agruments to the aggregator
// (aggregator does not take ownership of pointers it receives)
//
for (unsigned i = 0; i < vect.size(); ++i)
{
agg.add(vect[i].get());
}
bm::bvector<> bv_res; // target vector for aggregation
agg.combine_or(bv_res); // perform logical OR on a vector group
std::cout << "OR:" << std::endl;
PrintContainer(bv_res.first(), bv_res.end()); // 0, 1, 2, 3, 4... 10000, 20000
// since we did not call bm::aggregator::reset() the vector group
// still remains attached
std::cout << "AND:" << std::endl;
agg.combine_and(bv_res); // AND on the same vector group
PrintContainer(bv_res.first(), bv_res.end()); // 10000, 20000
agg.reset(); // reset the aggregator
// fused logical AND MINUS example
// AND(vector-group-0) SUBstract (AND NOT) vector-group-1
for (unsigned i = 0; i < vect.size(); ++i)
{
const unsigned group0 = 0; // vector group 0
agg.add(vect[i].get(), group0);
}
// Note that we do not set vector group 1 yet, so operation just
// runs as a regular AND MINUS an empty-set
agg.combine_and_sub(bv_res); // AND-SUB vector group1 and group2
std::cout << "AND-SUB(empty):" << std::endl;
PrintContainer(bv_res.first(), bv_res.end()); // 10000, 20000
bm::bvector<> bv_not { 10, 10000 };
agg.add(&bv_not, 1); // add to vector-group-1
agg.combine_and_sub(bv_res); // AND-SUB vector group0 minus group1
std::cout << "AND-SUB:" << std::endl;
PrintContainer(bv_res.first(), bv_res.end()); // 20000
agg.reset();
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
agg.reset(); // reset
throw;
}
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
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:622
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:630
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:638
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:589
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:1790
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:554
bm::bvector::first
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1784
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bm::aggregator::max_aggregator_cap
@ max_aggregator_cap
Definition: bmaggregator.h:71