BitMagic-C++
svsample09.cpp
Go to the documentation of this file.
1 /*
2 Copyright(c) 2002-2019 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3 
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 
16 For 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 
47 using namespace std;
48 
49 
51 
52 
53 int 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 
bmsparsevec_algo.h
Algorithms for bm::sparse_vector.
bm::sparse_vector
sparse vector with runtime compression using bit transposition method
Definition: bmsparsevec.h:81
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bm::use_null
support "non-assigned" or "NULL" logic
Definition: bmconst.h:215
bm::sparse_vector::set_null
void set_null(size_type idx)
set specified element to unassigned value (NULL)
Definition: bmsparsevec.h:986
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
bm::sparse_vector::push_back
void push_back(value_type v)
push value back into vector
Definition: bmsparsevec.h:1498
main
int main(void)
Definition: svsample09.cpp:53
svector_u32
bm::sparse_vector< unsigned, bm::bvector<> > svector_u32
Definition: svsample09.cpp:50
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.
bm::sparse_vector< unsigned, bm::bvector<> >::size_type
bvector_type::size_type size_type
Definition: bmsparsevec.h:87