svsample09.cpp

Mismatch search.

Mismatch search. bm::sparse_vector_find_first_mismatch

See also
  bm::sparse_vector
  bm::sparse_vector_find_first_mismatch
  bm::bvector<>::find_first_mismatch()

/*
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 svsample09.cpp
Mismatch search. bm::sparse_vector_find_first_mismatch
\sa bm::sparse_vector
\sa bm::sparse_vector_find_first_mismatch
\sa bm::bvector<>::find_first_mismatch()
*/
/*! \file svsample09.cpp
\brief Example: Use of sparse vector mismatch search
*/
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <utility>
#include "bm.h"
#include "bmsparsevec.h"
#include "bmsparsevec_algo.h"
#include "bmundef.h" /* clear the pre-proc defines from BM */
using namespace std;
typedef bm::sparse_vector<unsigned, bm::bvector<> > svector_u32;
int main(void)
{
try
{
svector_u32::size_type pos;
cout << "sparse vectors without NULL:" << endl;
{
svector_u32 sv1, sv2;
sv1.push_back(1);
sv1.push_back(2);
sv1.push_back(2);
sv1.push_back(3);
sv2 = sv1;
bool found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
if (found)
std::cout << "Mismatch found." << endl; // this would be an error
else
std::cout << "Mismatch not found" << endl; // identical vectors
// modify sv2 to introduce a mismatch
sv2[2] = 0;
found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
if (found)
{
std::cout << "Mismatch found at: " << pos << endl; // at 2
}
}
// bm::sparse_vector_find_first_mismatch works with NULL-able vectors
// first NULL (unsassigned) between vectors is a mimatch
//
cout << endl << "sparse vectors with NULL:" << endl;
{
svector_u32 sv1(bm::use_null);
svector_u32 sv2(bm::use_null);
sv1[1] = 1;
sv1[2] = 2;
sv1.set_null(3); // set element 3 to NULL
sv1[4] = 0;
sv2 = sv1;
bool found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
if (found)
std::cout << "Mismatch found." << endl; // this would be an error
else
std::cout << "Mismatch not found" << endl; // identical vectors
sv2[4] = 10;
found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
if (found)
{
std::cout << "Mismatch found at: " << pos << endl; // at 4
}
// set element 3 to 0, now we have a situation when element 3 in both
// vectors has value 0, except it is NULL value in vector 1
// mismatch search should detect it
//
sv2[3] = 0;
found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
if (found)
{
std::cout << "Mismatch found at: " << pos << endl; // at 3
}
}
}
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.
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::sparse_vector
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition bmsparsevec.h:87
bm::sparse_vector< unsigned, bm::bvector<> >::size_type
bvector_type::size_type size_type
Definition bmsparsevec.h:92
bm::sparse_vector::set_null
void set_null(size_type idx)
set specified element to unassigned value (NULL)
Definition bmsparsevec.h:1164
bm::sparse_vector::push_back
void push_back(value_type v)
push value back into vector
Definition bmsparsevec.h:1883
bm::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:230
bm::sparse_vector_find_first_mismatch
bool sparse_vector_find_first_mismatch(const SV &sv1, const SV &sv2, typename SV::size_type &midx, bm::null_support null_proc=bm::use_null)
Find first mismatch (element which is different) between two sparse vectors (uses linear scan in bit-...
Definition bmsparsevec_algo.h:170
main
int main(void)
Definition sample1.cpp:43
svector_u32
bm::sparse_vector< unsigned, bm::bvector<> > svector_u32
Definition xsample06.cpp:132