NCBI C++ ToolKit
id_mux.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef UTIL___ID_MUX__HPP
2 #define UTIL___ID_MUX__HPP
3 
4 /* $Id: id_mux.hpp 72570 2016-05-16 15:12:46Z ivanov $
5  * ===========================================================================
6  *
7  * PUBLIC DOMAIN NOTICE
8  * National Center for Biotechnology Information
9  *
10  * This software/database is a "United States Government Work" under the
11  * terms of the United States Copyright Act. It was written as part of
12  * the author's official duties as a United States Government employee and
13  * thus cannot be copyrighted. This software/database is freely available
14  * to the public for use. The National Library of Medicine and the U.S.
15  * Government have not placed any restriction on its use or reproduction.
16  *
17  * Although all reasonable efforts have been taken to ensure the accuracy
18  * and reliability of the software and data, the NLM and the U.S.
19  * Government do not and cannot warrant the performance or results that
20  * may be obtained by using this software or data. The NLM and the U.S.
21  * Government disclaim all warranties, express or implied, including
22  * warranties of performance, merchantability or fitness for any particular
23  * purpose.
24  *
25  * Please cite the author in any work or product based on this material.
26  *
27  * ===========================================================================
28  *
29  * Authors: Anatoliy Kuznetsov
30  *
31  * File Description: Id Multiplexer
32  *
33  */
34 
35 /// @file id_mux.hpp
36 /// Classes and interfaces to map integer ids into multi-dimension
37 /// coordinates.
38 
39 
40 #include <corelib/ncbistd.hpp>
41 #include <corelib/ncbimisc.hpp>
42 
43 #include <util/bitset/bmfwd.h>
44 #include <util/bitset/bmconst.h>
45 
46 #include <vector>
47 
49 
50 
51 /// Abstract object demultiplexer.
52 ///
53 /// This interface makes translation from an object (any C++ type) to
54 /// N-dimensional integer coordinate point describing the object.
55 /// In other words this interface is doing property extraction.
56 ///
57 template<class TObj>
58 struct IObjDeMux
59 {
60  typedef TObj TObject;
61 
62  /// Object to coordinates (properties) remap.
63  ///
64  /// @note Method made C-style for better performance
65  /// It is also intentinally made NOT virtual for
66  /// inlining (it is frequently called mathod).
67  /// All derived classes must be used by their types not as
68  /// references to the parent (IObjDeMux);
69  /// Inheritance is optional in this case.
70  void GetCoordinates(const TObj& obj, unsigned* coord)
71  {
72  _ASSERT(0); // use custom implementation of demux
73  }
74 };
75 
76 
77 
78 /// Bit-vector factory
79 template<class TBV>
81 {
82 public:
83  static TBV* Create() { return new TBV(bm::BM_GAP); }
84 };
85 
86 /// Id to coordinates demultiplexer
87 ///
88 /// This class converts single id into N-dimensional point
89 /// (vector of coordinates)
90 ///
91 /// <pre>
92 /// Example:
93 ///
94 /// Database of BLOBs of various sizes:
95 /// Dimension 1 - DB volumes (every volume holds up to 4GB of BLOBs)
96 /// Dimension 2 - Approximate size of the BLOB (small, medium, large)
97 ///
98 ///
99 /// 2D matrix:
100 ///
101 /// small(1) medium(2) large(3)
102 /// +-------------+-------------+-------------+
103 /// vol= 1 | 1,3,5 | 8 | 11, 9 |
104 /// vol= 2 | 6,10 | 15,16 | 2, 4 |
105 /// +-------------+-------------+-------------+
106 ///
107 /// Request to get coordinates of
108 /// BLOB 8 returns (1, 2)
109 /// 2 (2, 3)
110 /// 1 (1, 1)
111 /// </pre>
112 ///
113 /// This coordinate remapper stores lists of ids for every projection.
114 /// In the example above "vol= 1" projection is (1,3,5,8,9,11)
115 /// "small" projection is (1,3,5,6,10).
116 /// Coordinate search is implemented as scan in all available projections
117 /// until the id is found.
118 ///
119 template<class TBV, class TBVFact=CBvGapFactory<TBV> >
120 class CIdDeMux
121 {
122 public:
123  /// Point in N-dimensional space
124  typedef vector<unsigned> TDimensionalPoint;
125 
126  /// Bitvector describing members of dimension
127  typedef TBV TBitVector;
128 
129  typedef TBVFact TBVFactory;
130 
132 
133  /// Dimension vector
134  ///
135  /// Each element of the dimension vector is a bitset of elements
136  /// belonging to this projection.
137  typedef vector<TBitVectorPtr> TDimVector;
138 
139  /// Vector of space projections
140  typedef vector<TDimVector> TCoordinateSpace;
141 
142 public:
143 
144  /// @param N
145  /// Number of dimensions (order of demultiplexer)
146  ///
147  CIdDeMux(size_t N);
148 
149  /// Get order of Multiplexer
150  size_t GetN() const { return m_DimSpace.size(); }
151 
152  /// Find id in the coordinate space
153  ///
154  /// @param id
155  /// Input id
156  /// @param coords
157  /// Coordinates of the id (N-dim point)
158  ///
159  /// @return FALSE if id cannot be found
160  ///
161  bool GetCoordinates(unsigned id, TDimensionalPoint* coord) const;
162 
163  /// C-style version of coordinates mapping
164  ///
165  bool GetCoordinatesFast(unsigned id, unsigned* coord) const;
166 
167  /// Set/clear id using dimensional point
168  ///
169  /// Method does NOT check if the same id already been assigned
170  /// to some different coordinates. In other words this method
171  /// allows alternative projections.
172  void SetCoordinates(unsigned id,
173  const TDimensionalPoint& coord,
174  bool set_flag = true);
175 
176  /// Set/clear coordinates C-style
177  void SetCoordinatesFast(unsigned id,
178  const unsigned* coord,
179  bool set_flag = true);
180 
181  /// Get all ids registered in demux.
182  /// Method takes all dimention vectors and OR them into bv
183  ///
184  /// @param bv
185  /// Vector of IDs stored in demux
186  ///
187  void GetIdVector(TBitVector* bv) const;
188 
189  /// Get dimension vector
190  /// @param i
191  /// Dimension index
192  const TDimVector& GetDimVector(size_t i) const;
193 
194  /// Get modification access to dimension vector
195  TDimVector& PutDimVector(size_t i);
196 
197  /// Assign projection idx for dimension i.
198  /// Class takes ownership of bv
199  void SetProjection(size_t i, size_t idx, TBitVector* bv);
200 
201  /// Resize dimesion, create bitset content
202  void InitDim(size_t i, size_t dim_size);
203 
204  /// Reclaim unused memory
205  void FreeUnusedMem();
206 private:
207  // TO DO: implement copy semantics
210 private:
211  TCoordinateSpace m_DimSpace; ///< Dimensions
212 };
213 
214 
215 /////////////////////////////////////////////////////////////////////////////
216 // IMPLEMENTATION of INLINE functions
217 /////////////////////////////////////////////////////////////////////////////
218 
219 
220 
221 
222 template<class TBV, class TBVFact>
224 : m_DimSpace(N)
225 {
226 }
227 
228 template<class TBV, class TBVFact>
230  TDimensionalPoint* coord) const
231 {
232  _ASSERT(coord);
233  size_t N = m_DimSpace.size();
234  coord->resize(N);
235  return GetCoordinatesFast(id, &((*coord)[0]));
236 }
237 
238 
239 template<class TBV, class TBVFact>
241  unsigned* coord) const
242 {
243  size_t N = m_DimSpace.size();
244  for (size_t i = 0; i < N; ++i) {
245  bool dim_found = false;
246  const TDimVector& dv = GetDimVector(i);
247  size_t M = dv.size();
248  for (size_t j = 0; j < M; ++j) {
249  if (dv[j].get() == 0)
250  continue;
251  const TBitVector& bv = *(dv[j]);
252  dim_found = bv[id];
253  if (dim_found) {
254  coord[i] = (unsigned)j;
255  break;
256  }
257  } // for j
258  if (!dim_found)
259  return dim_found;
260  } // for i
261  return true;
262 }
263 
264 template<class TBV, class TBVFact>
266 {
267  _ASSERT(bv);
268 
269  bool first = true;
270 
271  // scan dimention 0 OR all vectors
272  const TDimVector& dv = GetDimVector(0);
273  size_t M = dv.size();
274  for (size_t j = 0; j < M; ++j) {
275  if (dv[j].get() == 0)
276  continue;
277  const TBitVector& dbv = *(dv[j]);
278  if (first) {
279  *bv = dbv;
280  first = false;
281  } else {
282  *bv |= dbv;
283  }
284  } // for j
285 }
286 
287 template<class TBV, class TBVFact>
289 {
290  size_t N = m_DimSpace.size();
291  for (size_t i = 0; i < N; ++i) {
292  const TDimVector& dv = GetDimVector(i);
293  size_t M = dv.size();
294  for (size_t j = 0; j < M; ++j) {
295  if (dv[j].get() == 0)
296  continue;
297  TBitVector& bv = *(dv[j]);
298  bv.optimize(0, TBitVector::opt_free_0);
299  } // for j
300  } // for i
301 }
302 
303 template<class TBV, class TBVFact>
304 void
306  const TDimensionalPoint& coord,
307  bool set_flag)
308 {
309  _ASSERT(coord.size() == GetN());
310  SetCoordinatesFast(id, &(coord[0]), set_flag);
311 }
312 
313 
314 template<class TBV, class TBVFact>
315 void
317  const unsigned* coord,
318  bool set_flag)
319 {
320  size_t N = GetN();
321  for (size_t i = 0; i < N; ++i) {
322  TDimVector& dv = PutDimVector(i);
323  unsigned c = coord[i];
324  if (dv.size() <= c) {
325  dv.resize(c+1);
326  }
327  TBitVector* bv = dv[c].get();
328  if (set_flag == false && bv == 0) {
329  continue; // nothing to do
330  }
331  if (!bv) {
332  dv[c] = bv = TBVFactory::Create();
333  }
334  bv->set(id, set_flag);
335  } // for i
336 }
337 
338 
339 
340 template<class TBV, class TBVFact>
341 const typename CIdDeMux<TBV, TBVFact>::TDimVector&
343 {
344  _ASSERT(i < m_DimSpace.size());
345  return m_DimSpace[i];
346 }
347 
348 template<class TBV, class TBVFact>
351 {
352  _ASSERT(i < m_DimSpace.size());
353  return m_DimSpace[i];
354 }
355 
356 template<class TBV, class TBVFact>
357 void
359 {
360  TDimVector& dv = this->PutDimVector(i);
361  if (dv.size() < idx + 1) {
362  dv.resize(idx + 1);
363  }
364  dv[idx] = bv;
365 }
366 
367 
368 template<class TBV, class TBVFact>
369 void CIdDeMux<TBV, TBVFact>::InitDim(size_t i, size_t dim_size)
370 {
371  TDimVector& dv = PutDimVector(i);
372 
373  size_t old_size = dv.size();
374  dv.resize(dim_size);
375  for (size_t j = old_size; j < dim_size; ++j) {
376  dv[j] = TBVFactory::Create();
377  }
378 }
379 
380 
382 
383 
384 #endif /* UTIL___ID_MUX__HPP */
Constants, lookup tables and typedefs.
Forward declarations.
AutoPtr –.
Definition: ncbimisc.hpp:401
Bit-vector factory.
Definition: id_mux.hpp:81
static TBV * Create()
Definition: id_mux.hpp:83
Id to coordinates demultiplexer.
Definition: id_mux.hpp:121
TBV TBitVector
Bitvector describing members of dimension.
Definition: id_mux.hpp:127
void SetCoordinates(unsigned id, const TDimensionalPoint &coord, bool set_flag=true)
Set/clear id using dimensional point.
Definition: id_mux.hpp:305
void SetCoordinatesFast(unsigned id, const unsigned *coord, bool set_flag=true)
Set/clear coordinates C-style.
Definition: id_mux.hpp:316
AutoPtr< TBitVector > TBitVectorPtr
Definition: id_mux.hpp:131
void InitDim(size_t i, size_t dim_size)
Resize dimesion, create bitset content.
Definition: id_mux.hpp:369
TCoordinateSpace m_DimSpace
Dimensions.
Definition: id_mux.hpp:211
bool GetCoordinates(unsigned id, TDimensionalPoint *coord) const
Find id in the coordinate space.
Definition: id_mux.hpp:229
CIdDeMux(const CIdDeMux &)
vector< unsigned > TDimensionalPoint
Point in N-dimensional space.
Definition: id_mux.hpp:124
TDimVector & PutDimVector(size_t i)
Get modification access to dimension vector.
Definition: id_mux.hpp:350
size_t GetN() const
Get order of Multiplexer.
Definition: id_mux.hpp:150
void FreeUnusedMem()
Reclaim unused memory.
Definition: id_mux.hpp:288
TBVFact TBVFactory
Definition: id_mux.hpp:129
const TDimVector & GetDimVector(size_t i) const
Get dimension vector.
Definition: id_mux.hpp:342
void SetProjection(size_t i, size_t idx, TBitVector *bv)
Assign projection idx for dimension i.
Definition: id_mux.hpp:358
CIdDeMux(size_t N)
Definition: id_mux.hpp:223
vector< TDimVector > TCoordinateSpace
Vector of space projections.
Definition: id_mux.hpp:140
bool GetCoordinatesFast(unsigned id, unsigned *coord) const
C-style version of coordinates mapping.
Definition: id_mux.hpp:240
vector< TBitVectorPtr > TDimVector
Dimension vector.
Definition: id_mux.hpp:137
void GetIdVector(TBitVector *bv) const
Get all ids registered in demux.
Definition: id_mux.hpp:265
CIdDeMux & operator=(const CIdDeMux &)
Include a standard set of the NCBI C++ Toolkit most basic headers.
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
@ BM_GAP
GAP compression is ON.
Definition: bmconst.h:148
int i
Miscellaneous common-use basic types and functionality.
Abstract object demultiplexer.
Definition: id_mux.hpp:59
void GetCoordinates(const TObj &obj, unsigned *coord)
Object to coordinates (properties) remap.
Definition: id_mux.hpp:70
TObj TObject
Definition: id_mux.hpp:60
#define _ASSERT
#define N
Definition: crc32.c:57
Modified on Wed Jul 24 17:19:11 2024 by modify_doxy.py rev. 669887