BitMagic-C++
rscsample04.cpp
Go to the documentation of this file.
1 /*
2 Copyright(c) 2002-2020 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 rscsample04.cpp
20  Example of how to use bm::rsc_sparse_vector<> pre-defined set construction
21 
22  1. Lets assume we know which elements of the vector are not NULL
23  2. bm::rsc_sparse_vector<> can be constructed for this
24  3. call to bm::rsc_sparse_vector<>::sync will re-calculate Rank-Select index
25  to enable fast access to elements (usually read only mode)
26  4. In this example we modify not NULL vector elements so it would use
27  Rank-Select index without breaking its consistency
28 
29 
30  \sa bm::rsc_sparse_vector
31  \sa bm::rsc_sparse_vector::sync
32  \sa bm::rsc_sparse_vector::inc
33 
34 */
35 
36 /*! \file rscsample04.cpp
37  \brief Example: bm::rsc_sparse_vector<> known NULL elements access
38 
39  @sa rscsample02.cpp
40 */
41 
42 #include <iostream>
43 #include <vector>
44 #include <cassert>
45 
46 #include "bm.h"
47 #include "bmsparsevec.h"
48 #include "bmsparsevec_compr.h"
49 
50 using namespace std;
51 
52 /// Print sparse vector not NULL elements
53 template<typename SV> void PrintSV(const SV& sv)
54 {
55  typename SV::const_iterator it = sv.begin();
56  typename SV::const_iterator it_end = sv.end();
57 
58  for (size_t i = 0; it != it_end; ++it, ++i)
59  {
60  if (!it.is_null())
61  cout << i << ": " << *it << ", ";
62  }
63  cout << endl;
64 }
65 
68 
69 
70 int main(void)
71 {
72  try
73  {
74  // vector of not NULL elements
75  bm::bvector<> bv1 { 10, 20, 100, 200, 65536 };
76  rsc_sparse_vector_u32 csv1(bv1);
77 
78  csv1.sync(); // build Rank-Select index for faster access
79  bv1.clear(); // we don't need bv1 anymore
80 
81  // modify vector elements but only touch the not NULL elements
82  // for fast access
83  //
84  csv1.set(100, 1);
85  csv1.set(20, 1);
86  csv1.inc(10);
87  csv1.inc(65536, 1);
88 
89  assert(csv1.in_sync()); // make sure Rank-Select index is still alive
90 
91  PrintSV(csv1); // 10: 1, 20: 1, 100: 1, 200: 0, 65536: 1
92  }
93  catch(std::exception& ex)
94  {
95  std::cerr << ex.what() << std::endl;
96  return 1;
97  }
98 
99 
100 
101  return 0;
102 }
103 
PrintSV
void PrintSV(const SV &sv)
Print sparse vector not NULL elements.
Definition: rscsample04.cpp:53
bm::rsc_sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec_compr.h:1001
bm::sparse_vector
sparse vector with runtime compression using bit transposition method
Definition: bmsparsevec.h:81
bm::rsc_sparse_vector::in_sync
bool in_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
Definition: bmsparsevec_compr.h:664
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bmsparsevec_compr.h
Compressed sparse container rsc_sparse_vector<> for integer types.
bm::bvector<>
rsc_sparse_vector_u32
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 > rsc_sparse_vector_u32
Definition: rscsample04.cpp:67
sparse_vector_u32
bm::sparse_vector< unsigned, bm::bvector<> > sparse_vector_u32
Definition: rscsample04.cpp:66
bm::rsc_sparse_vector
Rank-Select compressed sparse vector.
Definition: bmsparsevec_compr.h:58
main
int main(void)
Definition: rscsample04.cpp:70
bm::rsc_sparse_vector::sync
void sync(bool force)
Re-calculate prefix sum table used for rank search.
Definition: bmsparsevec_compr.h:1121
bm::rsc_sparse_vector::inc
void inc(size_type idx)
increment specified element by one
Definition: bmsparsevec_compr.h:918
bm.h
Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators.