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

Go to the SVN repository for this file.

1 #ifndef RESIZE_ITER__HPP
2 #define RESIZE_ITER__HPP
3 
4 /* $Id: resize_iter.hpp 73469 2016-07-08 15:55:21Z ucko $
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 * Author: Aaron Ucko
30 *
31 * File Description:
32 * CConstResizingIterator: handles sequences represented as packed
33 * sequences of elements of a different size; for instance, a
34 * "vector<char>" might actually hold 2-bit nucleotides or 32-bit integers.
35 * Assumes a big-endian representation: the MSBs of the first elements of
36 * the input and output sequences line up.
37 */
38 
39 #include <corelib/ncbistd.hpp>
40 #include <iterator>
41 #include <limits.h>
42 
43 
44 /** @addtogroup ResizingIterator
45  *
46  * @{
47  */
48 
49 
51 
52 
53 template <class TSeq, class TOut = int>
55 {
56  // Acts like an STL input iterator, with two exceptions:
57  // 1. It does not support ->, but TOut should be scalar anyway.
58  // 2. It caches the last value read, so might not adequately
59  // reflect changes to the underlying sequence.
60  // Also has forward-iterator semantics iff TSeq::const_iterator does.
61 
62  typedef typename TSeq::const_iterator TRawIterator;
63  typedef typename TSeq::value_type TRawValue;
64 
65 public:
66  typedef input_iterator_tag iterator_category;
67  typedef TOut value_type;
68  typedef size_t difference_type;
69  // no pointer or reference.
70 
71  CConstResizingIterator(const TSeq& s, size_t new_size /* in bits */)
72  : m_RawIterator(s.begin()), m_End(s.end()), m_NewSize(new_size),
75  size_t new_size)
76  : m_RawIterator(it), m_End(end), m_NewSize(new_size), m_BitOffset(0),
80  TOut operator*();
81  // No operator->; see above.
82  bool AtEnd() const;
83 
84 private:
87  size_t m_NewSize;
88  size_t m_BitOffset;
89  TOut m_Value;
91  // If m_ValueKnown is true, we have already determined the value at
92  // the current position and stored it in m_Value, advancing
93  // m_RawIterator + m_BitOffset along the way. Otherwise, m_Value still
94  // holds the previously accessed value, and m_RawIterator + m_BitOffset
95  // points at the beginning of the current value. This system is
96  // necessary to handle multiple dereferences to a value spanning
97  // multiple elements of the original sequence.
98 };
99 
100 
101 template <class TSeq, class TVal = int>
103 {
104  typedef typename TSeq::iterator TRawIterator;
105  // must be a mutable forward iterator.
106  typedef typename TSeq::value_type TRawValue;
107 
108 public:
109  typedef forward_iterator_tag iterator_category;
110  typedef TVal value_type;
111  typedef size_t difference_type;
112  // no pointer or reference.
113 
114  CResizingIterator(TSeq& s, size_t new_size)
115  : m_RawIterator(s.begin()), m_End(s.end()), m_NewSize(new_size),
116  m_BitOffset(0) {}
117  CResizingIterator(const TRawIterator& start, const TRawIterator& end,
118  size_t new_size)
119  : m_RawIterator(start), m_End(end), m_NewSize(new_size), m_BitOffset(0)
120  {}
121 
125  { return *this; } // acts as its own proxy type
126  // Again, no operator->.
127 
128  void operator=(TVal value);
129  operator TVal();
130 
131  bool AtEnd() const;
132 
133 private:
136  size_t m_NewSize;
137  size_t m_BitOffset;
138 };
139 
140 
141 /* @} */
142 
143 
144 ///////////////////////////////////////////////////////////////////////////
145 //
146 // INLINE FUNCTIONS
147 //
148 // This code contains some heavy bit-fiddling; take care when modifying it.
149 
150 #ifndef CHAR_BIT
151 #define CHAR_BIT 8
152 #endif
153 
154 
155 template <class T>
156 size_t xx_BitsPerElement(const T*)
157 {
158  return CHAR_BIT * sizeof(T);
159 }
160 
161 template <class TIterator>
163 {
164  return CHAR_BIT * sizeof(typename iterator_traits<TIterator>::value_type);
165 }
166 
167 
168 template <class TIterator, class TOut>
169 TOut ExtractBits(TIterator& start, const TIterator& end,
170  size_t& bit_offset, size_t bit_count)
171 {
172  static const size_t kBitsPerElement = x_BitsPerElement(start);
173 
174  const TOut kMask = (1 << bit_count) - 1;
175  static const TOut kMask2 = (1 << kBitsPerElement) - 1;
176  TOut value;
177 
178  if (start == end) {
179  return 0;
180  } else if (bit_offset + bit_count <= kBitsPerElement) {
181  // the current element contains it all
182  bit_offset += bit_count;
183  value = (*start >> (kBitsPerElement - bit_offset)) & kMask;
184  if (bit_offset == kBitsPerElement) {
185  bit_offset = 0;
186  ++start;
187  }
188  } else {
189  // We have to deal with multiple elements.
190  value = *start & ((1 << (kBitsPerElement - bit_offset)) - 1);
191  ++start;
192  for (bit_offset += bit_count - kBitsPerElement;
193  bit_offset >= kBitsPerElement;
194  bit_offset -= kBitsPerElement) {
195  value <<= kBitsPerElement;
196  if (start != end) {
197  value |= *start & kMask2;
198  ++start;
199  }
200  }
201  if (bit_offset) {
202  value <<= bit_offset;
203  if (start != end) {
204  value |= ((*start >> (kBitsPerElement - bit_offset))
205  & ((1 << bit_offset) - 1));
206  }
207  }
208  }
209  return value;
210 }
211 
212 
213 template <class TIterator, class TVal, class TElement>
214 TElement StoreBits(TIterator& start, const TIterator& end,
215  size_t& bit_offset, size_t bit_count,
216  TElement partial, TVal data) // returns new partial
217 {
218  static const size_t kBitsPerElement = CHAR_BIT * sizeof(TElement);
219 
220  if (bit_offset) {
221  partial = (TElement)(partial &
222  (~(TElement)0) << (kBitsPerElement - bit_offset));
223  } else {
224  partial = 0;
225  }
226 
227  if (bit_offset + bit_count <= kBitsPerElement) {
228  // Everything fits in one element.
229  bit_offset += bit_count;
230  partial = (TElement)(partial |
231  (data << (kBitsPerElement - bit_offset)));
232  if (bit_count == kBitsPerElement) {
233  *(start++) = partial;
234  bit_count = 0;
235  partial = 0;
236  }
237  } else {
238  // We need to split it up.
239  *(start++) = (TElement)(partial |
240  ((data >> (bit_count + bit_offset - kBitsPerElement))
241  & ((1 << (kBitsPerElement - bit_offset)) - 1)) );
242  for (bit_offset += bit_count - kBitsPerElement;
243  bit_offset >= kBitsPerElement;
244  bit_offset -= kBitsPerElement) {
245  if (start != end) {
246  *(start++) = (TElement)(data >> (bit_offset - kBitsPerElement));
247  }
248  }
249  if (bit_offset) {
250  partial = (TElement)(data << (kBitsPerElement - bit_offset));
251  } else {
252  partial = 0;
253  }
254  }
255  return partial;
256 }
257 
258 
259 // CConstResizingIterator members.
260 
261 
262 template <class TSeq, class TOut>
265 {
266  static const size_t kBitsPerElement = CHAR_BIT * sizeof(TRawValue);
267 
268  // We advance the raw iterator past things we read, so only advance
269  // it now if we haven't read the current value.
270  if (!m_ValueKnown) {
271  for (m_BitOffset += m_NewSize;
272  m_BitOffset >= kBitsPerElement && m_RawIterator != m_End;
273  m_BitOffset -= kBitsPerElement) {
274  ++m_RawIterator;
275  }
276  }
277  m_ValueKnown = false;
278  return *this;
279 }
280 
281 
282 template <class TSeq, class TOut>
285 {
287  ++(*this);
288  return copy;
289 }
290 
291 
292 template <class TSeq, class TOut>
294 {
295  if (m_ValueKnown)
296  return m_Value;
297 
298  m_ValueKnown = true;
299  return m_Value = ExtractBits<TRawIterator, TOut>
300  (m_RawIterator, m_End, m_BitOffset, m_NewSize);
301 }
302 
303 
304 
305 template <class TSeq, class TOut>
307 {
308  size_t avail = 0, goal = m_BitOffset + m_NewSize;
309  for (TRawIterator it2 = m_RawIterator; it2 != m_End && avail < goal;
310  ++it2) {
311  avail += x_BitsPerElement(m_RawIterator);
312  }
313  return avail < goal;
314 }
315 
316 
317 // CResizingIterator members.
318 
319 
320 template <class TSeq, class TVal>
322  // prefix
323 {
324  static const size_t kBitsPerElement = CHAR_BIT * sizeof(TRawValue);
325 
326  for (m_BitOffset += m_NewSize;
327  m_BitOffset >= kBitsPerElement && m_RawIterator != m_End;
328  m_BitOffset -= kBitsPerElement) {
329  ++m_RawIterator;
330  }
331  return *this;
332 }
333 
334 
335 template <class TSeq, class TVal>
337  // postfix
338 {
340  ++(*this);
341  return copy;
342 }
343 
344 
345 template <class TSeq, class TVal>
347 {
348  // don't advance iterator in object.
349  TRawIterator it = m_RawIterator;
350  size_t offset = m_BitOffset;
351  TRawValue tmp;
352 
353  tmp = StoreBits<TRawIterator, TVal, TRawValue>
354  (it, m_End, offset, m_NewSize, *it, value);
355  if (offset > 0 && it != m_End) {
356  *it = tmp;
357  }
358 }
359 
360 
361 template <class TSeq, class TVal>
363 {
364  // don't advance iterator in object.
365  TRawIterator it = m_RawIterator;
366  size_t offset = m_BitOffset;
367 
368  return ExtractBits<TRawIterator, TVal>(it, m_End, offset, m_NewSize);
369 }
370 
371 
372 template <class TSeq, class TVal>
374 {
375  size_t avail = 0, goal = m_BitOffset + m_NewSize;
376  for (TRawIterator it2 = m_RawIterator; it2 != m_End && avail < goal;
377  ++it2) {
378  avail += x_BitsPerElement(m_RawIterator);
379  }
380  return avail < goal;
381 }
382 
383 
385 
386 #endif /* RESIZE_ITER__HPP */
#define false
Definition: bool.h:36
char value[7]
Definition: config.c:431
Include a standard set of the NCBI C++ Toolkit most basic headers.
#define T(s)
Definition: common.h:230
CResizingIterator(TSeq &s, size_t new_size)
TElement StoreBits(TIterator &start, const TIterator &end, size_t &bit_offset, size_t bit_count, TElement partial, TVal data)
size_t xx_BitsPerElement(const T *)
#define CHAR_BIT
TSeq::const_iterator TRawIterator
Definition: resize_iter.hpp:62
size_t x_BitsPerElement(const TIterator &)
TOut ExtractBits(TIterator &start, const TIterator &end, size_t &bit_offset, size_t bit_count)
forward_iterator_tag iterator_category
TRawIterator m_RawIterator
TSeq::value_type TRawValue
void operator=(TVal value)
CConstResizingIterator(const TSeq &s, size_t new_size)
Definition: resize_iter.hpp:71
CConstResizingIterator(const TRawIterator &it, const TRawIterator &end, size_t new_size)
Definition: resize_iter.hpp:74
TRawIterator m_RawIterator
Definition: resize_iter.hpp:85
TSeq::value_type TRawValue
Definition: resize_iter.hpp:63
CResizingIterator< TSeq, TVal > & operator++()
CResizingIterator(const TRawIterator &start, const TRawIterator &end, size_t new_size)
CConstResizingIterator< TSeq, TOut > & operator++()
bool AtEnd() const
TRawIterator m_End
input_iterator_tag iterator_category
Definition: resize_iter.hpp:66
TSeq::iterator TRawIterator
CResizingIterator< TSeq, TVal > operator*()
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
vector< CSeq_align const * >::const_iterator TIterator
double value_type
The numeric datatype used by the parser.
Definition: muParserDef.h:228
void copy(Njn::Matrix< S > *matrix_, const Njn::Matrix< T > &matrix0_)
Definition: njn_matrix.hpp:613
static char tmp[2048]
Definition: utf8.c:42
int offset
Definition: replacements.h:160
Modified on Wed Mar 27 11:27:06 2024 by modify_doxy.py rev. 669887