BitMagic-C++
svsample05.cpp
Go to the documentation of this file.
1/*
2Copyright(c) 2002-2017 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 svsample05.cpp
20 Example how to use for bvector re-mapping / transformation
21 based on sparse_vector as a translation table.
22
23 Example discusses how use of NULL (unassigned) sparse_vector<> semantics affects
24 behavior of image transformation algorithm.
25
26 \sa bm::sparse_vector<>
27 \sa bm::set2set_11_transform
28*/
29
30/*! \file svsample05.cpp
31 \brief Example: sparse_vector<> used for set 2 set remapping (theory of groups Image)
32*/
33
34
35#include <iostream>
36#include <vector>
37
38#include "bm.h"
39#include "bmsparsevec.h"
40#include "bmsparsevec_algo.h"
41#include "bmundef.h" /* clear the pre-proc defines from BM */
42
43using namespace std;
44
46
47static
49{
50 if (sv.size() == 0)
51 {
52 cout << sv.size() << ": [ EMPTY ]" << endl;
53 return;
54 }
55 cout << sv.size() << ": [ ";
56 for (unsigned i = 0; i < sv.size(); ++i)
57 {
58 unsigned v = sv.at(i);
59 bool is_null = sv.is_null(i);
60
61 if (is_null)
62 cout << "NULL";
63 else
64 cout << v << "";
65
66 if (i == sv.size()-1)
67 cout << " ]";
68 else
69 cout << ", ";
70 }
71 cout << endl;
72}
73
74inline
76{
77 cout << "( count = " << bv.count() << ")" << ": [";
79 for (; en.valid(); ++en)
80 {
81 cout << *en << ", ";
82 }
83 cout << "]" << endl;
84}
85
86
87int main(void)
88{
89 try
90 {
91 // initialize sparse_vector as a binary relation (transform function)
92 // to translate from one set to another (please note it uses NULL values)
93 //
94 sparse_vector_u32 sv_transform(bm::use_null);
95
96 // transformation function defined as a table:
97 // 2 -> 25
98 // 3 -> 35
99 // 7 -> 75
100 // 1000 -> 2000
101 // 256 -> 2001
102
103 sv_transform.set(2, 25);
104 sv_transform.set(3, 35);
105 sv_transform.set(7, 75);
106 sv_transform.set(1000, 2000);
107 sv_transform.set(256, 2001);
108
109 print_svector(sv_transform);
110
111 // initialize input bit-vector
112 //
113 bm::bvector<> bv_in { 1, 2, 3, 1000, 256 };
114
115 bm::bvector<> bv_out;
116
118 func.run(bv_in, sv_transform, bv_out);
119
120 std::cout << "re-mapped vector:" << endl;
121 print_bvector(bv_out); // ( count = 4): [25, 35, 2000, 2001, ]
122
123 // Please note, that remapping request for "1" cannot be satisfied
124 // as sv_transform vector did not assign this element so it has
125 // special unassigned, NULL value
126
127 bm::id_t from = 1;
128 bm::id_t to;
129 bool found = func.remap(1, sv_transform, to);
130 if (!found)
131 std::cout << from << " not mapped" << std::endl; // THIS works!
132 else
133 std::cout << from << " mapped to " << to << std::endl;
134
135
136 // now lets try another experiment here, construct image transform
137 // function as default NOT using NULL values
138
139 sparse_vector_u32 sv_transform2;
140
141 sv_transform2.set(2, 25);
142 sv_transform2.set(3, 35);
143 sv_transform2.set(7, 75);
144 sv_transform2.set(1000, 2000);
145 sv_transform2.set(256, 2001);
146
147 found = func.remap(1, sv_transform2, to);
148 if (!found)
149 std::cout << from << " not mapped" << std::endl;
150 else
151 std::cout << from << " mapped to " << to << std::endl; // Now THIS works!
152
153 // Please note that remapping for unassigned value - works and maps to 0
154 // because transformation sparse vector does not keep information about
155 // unassigned values, all unassigned are now implicitly assumed to be "0"
156
157 func.run(bv_in, sv_transform2, bv_out);
158
159 std::cout << "re-mapped vector2:" << endl;
160 print_bvector(bv_out); // ( count = 5): [0, 25, 35, 2000, 2001, ]
161
162 }
163 catch(std::exception& ex)
164 {
165 std::cerr << ex.what() << std::endl;
166 return 1;
167 }
168
169 return 0;
170}
171
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.
pre-processor un-defines to avoid global space pollution (internal)
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
Definition: bmbmatrix.h:1709
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:603
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition: bm.h:283
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:115
size_type count() const BMNOEXCEPT
population count (count of ON bits)
Definition: bm.h:2366
enumerator first() const
Returns enumerator pointing on the first non-zero bit.
Definition: bm.h:1849
Integer set to set transformation (functional image in groups theory) https://en.wikipedia....
void remap(const bvector_type &bv_in, bvector_type &bv_out)
Perform remapping (Image function) (based on attached translation table)
void run(const bvector_type &bv_in, const SV &sv_brel, bvector_type &bv_out)
Run remap transformation.
succinct sparse vector with runtime compression using bit-slicing / transposition method
Definition: bmsparsevec.h:87
value_type at(size_type idx) const
access specified element with bounds checking
Definition: bmsparsevec.h:1730
size_type size() const BMNOEXCEPT
return size of the vector
Definition: bmsparsevec.h:711
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec.h:1804
@ use_null
support "non-assigned" or "NULL" logic
Definition: bmconst.h:229
unsigned int id_t
Definition: bmconst.h:38
bm::sparse_vector< bm::id_t, bm::bvector<> > sparse_vector_u32
Definition: svsample05.cpp:45
int main(void)
Definition: svsample05.cpp:87
void print_bvector(const bm::bvector<> &bv)
Definition: svsample05.cpp:75
static void print_svector(const sparse_vector_u32 &sv)
Definition: svsample05.cpp:48