BitMagic-C++
svsample09.cpp
Go to the documentation of this file.
1/*
2Copyright(c) 2002-2019 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 svsample09.cpp
20 Use of sparse vector for compressed DNA strings (2 bits per bp)
21 Construction of comparison functions on bit-transposed compressed
22 containers, benchmarking.
23
24 \sa bm::sparse_vector
25 \sa bm::sparse_vector_find_first_mismatch
26
27 \sa bm::bvector<>::find_first_mismatch()
28
29*/
30
31/*! \file svsample09.cpp
32 \brief Example: Use of sparse vector mismatch search
33*/
34
35#include <assert.h>
36#include <stdlib.h>
37
38#include <iostream>
39#include <vector>
40#include <utility>
41
42#include "bm.h"
43#include "bmsparsevec.h"
44#include "bmsparsevec_algo.h"
45
46
47using namespace std;
48
49
51
52
53int main(void)
54{
55 try
56 {
58
59 cout << "sparse vectors without NULL:" << endl;
60 {
61 svector_u32 sv1, sv2;
62
63 sv1.push_back(1);
64 sv1.push_back(2);
65 sv1.push_back(2);
66 sv1.push_back(3);
67
68 sv2 = sv1;
69
70 bool found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
71 if (found)
72 std::cout << "Mismatch found." << endl; // this would be an error
73 else
74 std::cout << "Mismatch not found" << endl; // identical vectors
75
76 // modify sv2 to introduce a mismatch
77
78 sv2[2] = 0;
79 found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
80 if (found)
81 {
82 std::cout << "Mismatch found at: " << pos << endl; // at 2
83 }
84 }
85
86 // bm::sparse_vector_find_first_mismatch works with NULL-able vectors
87 // first NULL (unsassigned) between vectors is a mimatch
88 //
89 cout << endl << "sparse vectors with NULL:" << endl;
90 {
93
94 sv1[1] = 1;
95 sv1[2] = 2;
96 sv1.set_null(3); // set element 3 to NULL
97 sv1[4] = 0;
98
99 sv2 = sv1;
100
101 bool found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
102 if (found)
103 std::cout << "Mismatch found." << endl; // this would be an error
104 else
105 std::cout << "Mismatch not found" << endl; // identical vectors
106
107 sv2[4] = 10;
108 found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
109 if (found)
110 {
111 std::cout << "Mismatch found at: " << pos << endl; // at 4
112 }
113
114
115 // set element 3 to 0, now we have a situation when element 3 in both
116 // vectors has value 0, except it is NULL value in vector 1
117 // mismatch search should detect it
118 //
119 sv2[3] = 0;
120 found = bm::sparse_vector_find_first_mismatch(sv1, sv2, pos);
121 if (found)
122 {
123 std::cout << "Mismatch found at: " << pos << endl; // at 3
124 }
125 }
126
127 }
128 catch(std::exception& ex)
129 {
130 std::cerr << ex.what() << std::endl;
131 return 1;
132 }
133
134
135
136 return 0;
137}
138
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Algorithms for bm::sparse_vector.
sparse vector with runtime compression using bit transposition method
Definition bmsparsevec.h:82
void set_null(size_type idx)
set specified element to unassigned value (NULL)
void push_back(value_type v)
push value back into vector
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:215
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-...
bm::sparse_vector< unsigned, bm::bvector<> > svector_u32
int main(void)