svsample07a.cpp
Go to the documentation of this file.
/*
Copyright(c) 2002-2019 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 svsample07a.cpp
Example of how to search bm::sparse_vector_scanner<> with sparse vector scanner
and inspect search results using bm::interval_enumerator<>
to find special values: unique, co-locvated together in the results or dispersed.
\sa bm::sparse_vector
\sa bm::sparse_vector_scanner
\sa bm::interval_enumerator
\sa bvintervals
\sa sample23
*/
/*! \file svsample07a.cpp
\brief Example: sparse_vector<> search
*/
#include <assert.h>
#include <iostream>
#include <vector>
#include <chrono>
#include <algorithm>
#include <random>
#include <algorithm>
#include <stdexcept>
#include "bm.h"
#include "bmsparsevec.h"
#include "bmsparsevec_algo.h"
#include "bmintervals.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
using namespace std;
typedef bm::bvector<> bvector_type;
typedef bm::sparse_vector<unsigned, bvector_type > sparse_vector_u32;
typedef bm::interval_enumerator<bvector_type > interval_enumerator_type;
int main(void)
{
try
{
sparse_vector_u32 sv;
// use back inserter to add values to the vector
{
sparse_vector_u32::back_insert_iterator bit(&sv);
bit = 0;
bit = bm::id_max;
bit = 17;
bit = 17;
bit = 5;
bit = 18;
bit = 178;
bit = 178;
bit = 17;
bit = 0;
bit = bm::id_max;
bit.flush();
}
sv.optimize(); // mmemory optimization after active editing
// just a print-out
{
cout << "Sparse vector:" << endl;
std::for_each(sv.begin(), sv.end(), [](unsigned v) {
cout << v << ",";
});
cout << endl << endl;
}
bm::sparse_vector_scanner<sparse_vector_u32> scanner;
scanner.bind(sv, false);
bvector_type bv_res;
// connect bv_res with allocation pool scanner for better
// this is optional but known to improve performance on repeated searches
typename bvector_type::mem_pool_guard mp_guard;
mp_guard.assign_if_not_set(scanner.get_bvector_alloc_pool(), bv_res);
sparse_vector_u32::const_iterator it = sv.begin();
sparse_vector_u32::const_iterator it_end = sv.end();
// setup two bit-vectors for positive and negative values we seen
// if values are signed - maintain two separatevectors
// for positives and negatives
bvector_type bv_seen_values(bm::BM_GAP);
bool id_max_seen(false); // bit-vector cannot take bm::id_max value
for (;it != it_end; ++it)
{
auto v = *it;
if (bvector_type::size_type(v) == bm::id_max)
{
if (id_max_seen)
continue;
id_max_seen = true;
}
else
{
// scanner search is an expensive operation do avoid duplicate lookups
// maintain bit-vectors of already seen values
//
if (bv_seen_values.test(bvector_type::size_type(v)))
continue;
bv_seen_values.set(bvector_type::size_type(v));
}
scanner.find_eq(sv, v, bv_res);
// we have our results, we can now inspect the result bit-vector
// using interval enumerator to find which values are co-located
// in one bunch as 000011000...0000
// or unique as 000010000...00
// or form non-unique, multi-occurence patterns as 000111000..011..
//
interval_enumerator_type ien(bv_res);
assert(ien.valid()); // as we took value from the search vector
bvector_type::size_type range_cnt = ien.end() - ien.start() + 1;
// try to advance
if (!ien.advance()) // only one interval, cannot advance more
{
if (range_cnt == 1)
{
cout << "Value = " << v << " is unique" << endl;
continue;
}
cout << "Value = " << v << " is colocated" << endl;
continue;
}
cout << "Value = " << v << " is not colocated" << endl;
} // for it
}
catch(std::exception& ex)
{
std::cerr << ex.what() << std::endl;
return 1;
}
return 0;
}
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bmintervals.h
Algorithms for bit ranges and intervals.
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bmsparsevec_algo.h
Algorithms for bm::sparse_vector.
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition bm.h:115
bm::bvector::test
bool test(size_type n) const BMNOEXCEPT
returns true if bit n is set and false is bit n is 0.
Definition bm.h:1502
bm::bvector::set
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition bm.h:4188
bm::bvector::size_type
bvector_size_type size_type
Definition bm.h:121
bm::interval_enumerator
forward iterator class to traverse bit-vector as ranges
Definition bmintervals.h:53
bm::interval_enumerator::end
size_type end() const BMNOEXCEPT
Return interval end/right as bit-vector coordinate 011110 [left..right].
Definition bmintervals.h:560
bm::interval_enumerator::valid
bool valid() const BMNOEXCEPT
Returns true if enumerator is valid (false if traversal is done).
Definition bmintervals.h:568
bm::interval_enumerator::advance
bool advance()
Definition bmintervals.h:717
bm::interval_enumerator::start
size_type start() const BMNOEXCEPT
Return interval start/left as bit-vector coordinate 011110 [left..right].
Definition bmintervals.h:551
bm::sparse_vector_scanner
algorithms for sparse_vector scan/search
Definition bmsparsevec_algo.h:582
bm::sparse_vector_scanner::get_bvector_alloc_pool
allocator_pool_type & get_bvector_alloc_pool() BMNOEXCEPT
Return allocator pool for blocks (Can be used to improve performance of repeated searches with the sa...
Definition bmsparsevec_algo.h:1042
bm::sparse_vector_scanner::find_eq
void find_eq(const SV &sv, value_type value, bvector_type &bv_out)
find all sparse vector elements EQ to search value
Definition bmsparsevec_algo.h:3071
bm::sparse_vector_scanner::bind
void bind(const SV &sv, bool sorted)
bind sparse vector for all searches
Definition bmsparsevec_algo.h:1594
bm::sparse_vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition bmsparsevec.h:87
bm::sparse_vector::end
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end.
Definition bmsparsevec.h:575
bm::sparse_vector::begin
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content.
Definition bmsparsevec.h:2310
bm::sparse_vector::optimize
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector planes
Definition bmsparsevec.h:2148
bm::bvector::mem_pool_guard
bm::alloc_pool_guard< allocator_pool_type, bvector< Alloc > > mem_pool_guard
Definition bm.h:790
bm::BM_GAP
@ BM_GAP
GAP compression is ON.
Definition bmconst.h:148
bm::id_max
const unsigned id_max
Definition bmconst.h:109
interval_enumerator_type
bm::interval_enumerator< bm::bvector<> > interval_enumerator_type
Definition sample23.cpp:52
main
int main(void)
Definition svsample07a.cpp:59
sparse_vector_u32
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition xsample02.cpp:68
bvector_type
bm::bvector bvector_type
Definition xsample07a.cpp:94