1 /*==========================================================================
2 SeqAn - The Library for Sequence Analysis
4 ============================================================================
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 3 of the License, or (at your option) any later version.
12 This library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
17 ============================================================================
18 $Id: basic_aggregates.h,v 1.1 2008/08/25 16:20:01 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_BASIC_AGGREGATES_H
22 #define SEQAN_HEADER_BASIC_AGGREGATES_H
24 namespace SEQAN_NAMESPACE_MAIN
27 //____________________________________________________________________________
30 typedef Tag<_Compressed> Compressed;
32 // for Pairs with small i1-values
33 // store i1 and i2 in one word of type i2
34 // use the upper bits for i1 and the lower bits for i2
35 template <unsigned valueSizeI1 = 16>
36 struct CutCompressed {
37 enum { bitSizeI1 = Log2<valueSizeI1>::VALUE };
43 ..summary:Stores two arbitrary objects.
44 ..signature:Pair<T1, T2[, Compression]>
45 ..param.T1:The type of the first object.
46 ..param.T2:The type of the second object.
47 ..param.Compression:If $Compressed$, the pair is stored in a more space efficient way (useful for external storage).
48 ...note:When compression is enabled, referring to members is not allowed.
49 ...default:$void$, no compression (faster access).
53 ..signature:Pair<T1, T2> ()
54 ..signature:Pair<T1, T2> (pair)
55 ..signature:Pair<T1, T2> (i1, i2)
56 ..param.pair:Other Pair object. (copy constructor)
68 template <typename _T1, typename _T2 = _T1, typename TCompression = void>
75 inline Pair(Pair const &_p): i1(_p.i1), i2(_p.i2) {}
76 inline Pair(_T1 const &_i1, _T2 const &_i2): i1(_i1), i2(_i2) {}
78 template <typename __T1, typename __T2, typename __TCompression>
79 inline Pair(Pair<__T1, __T2, __TCompression> const &_p):
80 i1(getValueI1(_p)), i2(getValueI2(_p)) {}
85 // unaligned and unpadded storage (space efficient)
86 #ifdef PLATFORM_WINDOWS
89 template <typename _T1, typename _T2>
90 struct Pair<_T1, _T2, Compressed> {
96 inline Pair(Pair const &_p): i1(_p.i1), i2(_p.i2) {}
97 inline Pair(_T1 const &_i1, _T2 const &_i2): i1(_i1), i2(_i2) {}
99 template <typename __T1, typename __T2, typename __TCompression>
100 inline Pair(Pair<__T1, __T2, __TCompression> const &_p):
101 i1(getValueI1(_p)), i2(getValueI2(_p)) {}
103 #ifndef PLATFORM_WINDOWS
104 __attribute__((packed))
107 #ifdef PLATFORM_WINDOWS
113 #ifdef PLATFORM_WINDOWS
116 template <typename _T1, typename _T2, unsigned valueSizeI1>
117 struct Pair<_T1, _T2, CutCompressed<valueSizeI1> > {
125 enum { bitSizeI1 = CutCompressed<valueSizeI1>::bitSizeI1 };
126 enum { bitShiftI1 = BitsPerValue<T12>::VALUE - bitSizeI1 };
129 inline Pair(Pair const &_p): i12(_p.i12) {}
130 inline Pair(_T1 const &_i1, _T2 const &_i2):
131 i12(((T12)_i1 << bitShiftI1) + (T12)_i2) {}
133 template <typename __T1, typename __T2, typename __TCompression>
134 inline Pair(Pair<__T1, __T2, __TCompression> const &_p):
135 i12(((T12)getValueI1(_p) << bitShiftI1) + (T12)getValueI2(_p)) {}
137 #ifndef PLATFORM_WINDOWS
138 __attribute__((packed))
141 #ifdef PLATFORM_WINDOWS
147 template <typename _T1, typename _T2, typename TCompression>
148 std::ostream& operator<<(std::ostream &out, Pair<_T1,_T2,TCompression> const &p) {
149 out << "< " << getValueI1(p) << " , " << getValueI2(p) << " >";
153 template <typename T1, typename T2, typename TCompression>
154 struct Value< Pair<T1, T2, TCompression>, 1 > {
158 template <typename T1, typename T2, typename TCompression>
159 struct Value< Pair<T1, T2, TCompression>, 2 > {
163 template <typename T1, typename T2, typename TCompression>
164 struct Spec< Pair<T1, T2, TCompression> > {
165 typedef TCompression Type;
169 //____________________________________________________________________________
171 template <typename TKey, typename TObject, typename TSpec>
172 struct Key< Pair<TKey, TObject, TSpec> >
177 template <typename TKey, typename TCargo, typename TSpec>
178 struct Cargo< Pair<TKey, TCargo, TSpec> >
182 //____________________________________________________________________________
187 ..summary:Stores three arbitrary objects.
188 ..signature:Triple<T1, T2, T3[, Compression]>
189 ..param.T1:The type of the first object.
190 ..param.T2:The type of the second object.
191 ..param.T3:The type of the third object.
192 ..param.Compression:If $Compressed$, the triple is stored in a more space efficient way (useful for external storage).
193 ...note:When compression is enabled, referring to members is not allowed.
194 ...default:$void$, no compression (faster access).
195 .Memfunc.Triple#Triple:
197 ..summary:Constructor
198 ..signature:Triple<T1, T2, T3> ()
199 ..signature:Triple<T1, T2, T3> (triple)
200 ..signature:Triple<T1, T2, T3> (i1, i2, i3)
201 ..param.triple:Other Triple object. (copy constructor)
202 ..param.i1:T1 object.
203 ..param.i2:T2 object.
204 ..param.i3:T3 object.
217 template <typename _T1, typename _T2 = _T1, typename _T3 = _T1, typename TCompression = void>
226 inline Triple(Triple const &_p):
227 i1(_p.i1), i2(_p.i2), i3(_p.i3) {}
228 inline Triple(_T1 const &_i1, _T2 const &_i2, _T3 const &_i3):
229 i1(_i1), i2(_i2), i3(_i3) {}
231 template <typename __T1, typename __T2, typename __T3, typename __TCompression>
232 inline Triple(Triple<__T1, __T2, __T3, __TCompression> const &_p):
233 i1(getValueI1(_p)), i2(getValueI2(_p)), i3(getValueI3(_p)) {}
236 // unaligned and unpadded storage (space efficient)
237 #ifdef PLATFORM_WINDOWS
240 template <typename _T1, typename _T2, typename _T3>
241 struct Triple<_T1, _T2, _T3, Compressed> {
249 inline Triple(Triple const &_p):
250 i1(_p.i1), i2(_p.i2), i3(_p.i3) {}
251 inline Triple(_T1 const &_i1, _T2 const &_i2, _T3 const &_i3):
252 i1(_i1), i2(_i2), i3(_i3) {}
254 template <typename __T1, typename __T2, typename __T3, typename __TCompression>
255 inline Triple(Triple<__T1, __T2, __T3, __TCompression> const &_p):
256 i1(getValueI1(_p)), i2(getValueI2(_p)), i3(getValueI3(_p)) {}
258 #ifndef PLATFORM_WINDOWS
259 __attribute__((packed))
262 #ifdef PLATFORM_WINDOWS
266 template <typename _T1, typename _T2, typename _T3, typename TCompression>
267 std::ostream& operator<<(std::ostream &out, Triple<_T1,_T2,_T3,TCompression> const &t) {
268 out << "< " << getValueI1(t) << " , " << getValueI2(t) << " , " << getValueI3(t) << " >";
272 template <typename T1, typename T2, typename T3, typename TCompression>
273 struct Value< Triple<T1, T2, T3, TCompression>, 1 > {
277 template <typename T1, typename T2, typename T3, typename TCompression>
278 struct Value< Triple<T1, T2, T3, TCompression>, 2 > {
282 template <typename T1, typename T2, typename T3, typename TCompression>
283 struct Value< Triple<T1, T2, T3, TCompression>, 3 > {
287 template <typename T1, typename T2, typename T3, typename TCompression>
288 struct Spec< Triple<T1, T2, T3, TCompression> > {
289 typedef TCompression Type;
293 //____________________________________________________________________________
298 ..summary:A plain fixed-length string.
299 ..signature:Tuple<T, size[, compress]>
300 ..param.T:The value type, that is the type of characters stored in the tuple.
301 ..param.size:The size/length of the tuple.
302 ...remarks:In contrast to @Class.String@ the length of Tuple is fixed.
303 ..param.compress:Enable/Disable compression.
304 ..param.compress:If $void$, no compression is used.
305 ..param.compress:If $Compressed$, the characters are stored as a bit sequence in an ordinal type (char, ..., __int64)
306 ...remarks:Only useful for small alphabets and small tuple sizes (|Sigma|^size <= 2^64) as for DNA or protein m-grams)
312 template <typename _T, unsigned _size, typename TCompression = void>
315 enum { size = _size };
318 template <typename TPos>
319 inline _T& operator[](TPos k) {
320 SEQAN_ASSERT(k >= 0 && k < size);
323 template <typename TPos>
324 inline const _T& operator[](TPos k) const {
325 SEQAN_ASSERT(k >= 0 && k < size);
328 inline _T* operator&() { return i; }
329 inline const _T* operator&() const { return i; }
331 // has to be inline because elements (like this tuple) of packed structs can't be arguments
332 template <typename TPos, typename SSS>
333 inline SSS const assignValueAt(TPos k, SSS const source) {
334 return i[k] = source;
339 template < unsigned char _size >
341 typedef typename _BitVector<_size + 1>::Type Type;
344 template <> struct _BitVector<8> { typedef unsigned char Type; };
345 template <> struct _BitVector<16> { typedef unsigned short Type; };
346 template <> struct _BitVector<32> { typedef unsigned int Type; };
347 template <> struct _BitVector<64> { typedef __int64 Type; };
348 template <> struct _BitVector<255> { typedef __int64 Type; };
350 // bit-compressed storage (space efficient)
351 #ifdef PLATFORM_WINDOWS
354 template <typename _T, unsigned _size>
355 struct Tuple<_T, _size, Compressed> {
357 enum { size = _size };
358 enum { bitSize = BitsPerValue<_T>::VALUE };
359 enum { bitMask = (1 << bitSize) - 1 };
360 enum { mask = (1 << (size * bitSize)) - 1 };
361 typedef typename _BitVector< bitSize * size >::Type CT;
366 SEQAN_ASSERT(bitSize * size <= sizeof(CT) * 8);
369 template <typename TPos>
370 inline const _T operator[](TPos k) const {
371 SEQAN_ASSERT(k >= 0 && k < size);
372 return (i >> (size - 1 - k) * bitSize) & bitMask;
374 template <unsigned __size>
375 inline Tuple operator=(Tuple<_T, __size, Compressed> const &_right) {
379 template <typename TShiftSize>
380 inline CT operator<<=(TShiftSize shift) {
381 return i = (i << (shift * bitSize)) & mask;
383 template <typename TShiftSize>
384 inline CT operator<<(TShiftSize shift) const {
385 return (i << (shift * bitSize)) & mask;
387 template <typename TShiftSize>
388 inline CT operator>>=(TShiftSize shift) {
389 return i = (i >> (shift * bitSize));
391 template <typename TShiftSize>
392 inline CT operator>>(TShiftSize shift) const {
393 return i >> (shift * bitSize);
395 template <typename T>
396 inline void operator|=(T const &t) {
399 template <typename T, typename TSpec>
400 inline void operator|=(SimpleType<T, TSpec> const &t) {
403 inline CT* operator&() { return &i; }
404 inline const CT* operator&() const { return &i; }
406 // has to be inline because elements (like this tuple) of packed structs can't be arguments
407 template <typename TPos, typename SSS>
408 inline SSS const assignValueAt(TPos k, SSS const source) {
409 typedef Tuple<_T, _size, Compressed> Tup;
410 typename Tup::CT mask = Tup::bitMask << ((_size - 1 - k) * bitSize);
411 i = (i & ~mask) | ((CT)source << ((_size - 1 - k) * bitSize));
415 #ifndef PLATFORM_WINDOWS
416 __attribute__((packed))
419 #ifdef PLATFORM_WINDOWS
424 //////////////////////////////////////////////////////////////////////////////
427 template <typename _T, unsigned _size, typename TCompression>
428 inline unsigned length(Tuple<_T, _size, TCompression> const &) { return _size; }
430 ///.Metafunction.LENGTH.param.T.type:Class.Tuple
431 template <typename _T, unsigned _size, typename TCompression>
432 struct LENGTH< Tuple<_T, _size, TCompression> >
434 enum { VALUE = _size };
437 //////////////////////////////////////////////////////////////////////////////
440 template <typename TObject, typename TPos, typename TSource>
442 assignValueAt(TObject &me, TPos k, TSource &source) {
443 assign(value(me, k), source);
447 template <typename TObject, typename TPos, typename TSource>
448 inline TSource const &
449 assignValueAt(TObject &me, TPos k, TSource const &source) {
450 assign(value(me, k), source);
454 template <typename TTT, unsigned _size, typename SSS, typename TPos>
455 inline SSS const assignValueAt(Tuple<TTT, _size, void> &me, TPos k, SSS const source) {
456 return me.i[k] = source;
459 template <typename TTT, unsigned _size, typename SSS, typename TPos>
460 inline SSS const assignValueAt(Tuple<TTT, _size, Compressed> &me, TPos k, SSS const source) {
461 typedef Tuple<TTT, _size, Compressed> Tup;
462 typename Tup::CT mask = Tup::bitMask << ((_size - 1 - k) * me.bitSize);
463 me.i = (me.i & ~mask) | source << ((_size - 1 - k) * me.bitSize);
467 template <typename TTT, typename SSS, typename SSSpec, unsigned _size, typename TPos>
468 inline SimpleType<SSS, SSSpec> const & assignValueAt(Tuple<TTT, _size, Compressed> &me, TPos k, SimpleType<SSS, SSSpec> const &source) {
469 typedef Tuple<TTT, _size, Compressed> Tup;
470 typename Tup::CT mask = Tup::bitMask << ((_size - 1 - k) * me.bitSize);
471 me.i = (me.i & ~mask) | source.value << ((_size - 1 - k) * me.bitSize);
475 //////////////////////////////////////////////////////////////////////////////
478 template <typename TTT, unsigned _size, typename TCompression>
479 inline void clear(Tuple<TTT, _size, TCompression> &me) {
480 memset<sizeof(me.i), 0>(&(me.i));
482 template <typename TTT, unsigned _size>
483 inline void clear(Tuple<TTT, _size, Compressed> &me) {
487 //////////////////////////////////////////////////////////////////////////////
488 // optimized compares
490 template <typename TTT, unsigned _sizeL, unsigned _sizeR>
491 inline bool operator<(Tuple<TTT, _sizeL, Compressed> const &_left, Tuple<TTT, _sizeR, Compressed> const &_right) {
492 return _left.i < _right.i;
494 template <typename TTT, unsigned _sizeL, unsigned _sizeR>
495 inline bool operator>(Tuple<TTT, _sizeL, Compressed> const &_left, Tuple<TTT, _sizeR, Compressed> const &_right) {
496 return _left.i > _right.i;
498 template <typename TTT, unsigned _sizeL, unsigned _sizeR>
499 inline bool operator==(Tuple<TTT, _sizeL, Compressed> const &_left, Tuple<TTT, _sizeR, Compressed> const &_right) {
500 return _left.i == _right.i;
502 template <typename TTT, unsigned _sizeL, unsigned _sizeR>
503 inline bool operator!=(Tuple<TTT, _sizeL, Compressed> const &_left, Tuple<TTT, _sizeR, Compressed> const &_right) {
504 return _left.i != _right.i;
507 //////////////////////////////////////////////////////////////////////////////
510 struct _TupleShiftLeftWorker {
511 template <typename Arg>
512 static inline void body(Arg &arg, unsigned I) {
517 struct _TupleShiftRightWorker {
518 template <typename Arg>
519 static inline void body(Arg &arg, unsigned I) {
524 template <typename _T, unsigned _size, typename TCompression>
525 inline void shiftLeft(Tuple<_T, _size, TCompression> &me) {
526 LOOP<_TupleShiftLeftWorker, _size - 1>::run(me);
529 template <typename _T, unsigned _size, typename TCompression>
530 inline void shiftRight(Tuple<_T, _size, TCompression> &me) {
531 LOOP_REVERSE<_TupleShiftRightWorker, _size - 1>::run(me);
534 template <typename _T, unsigned _size>
535 inline void shiftLeft(Tuple<_T, _size, Compressed> &me) {
539 template <typename _T, unsigned _size>
540 inline void shiftRight(Tuple<_T, _size, Compressed> &me) {
544 //////////////////////////////////////////////////////////////////////////////
547 template <typename _T, unsigned _size, typename TCompression>
548 std::ostream& operator<<(std::ostream& out, Tuple<_T,_size,TCompression> const &a) {
552 for(unsigned j = 1; j < a.size; ++j)
558 template <typename _T, unsigned _size, typename TCompression>
559 struct Value< Tuple<_T, _size, TCompression> > {
563 template <typename _T, unsigned _size, typename TCompression>
564 struct Spec< Tuple<_T, _size, TCompression> > {
565 typedef TCompression Type;
568 //////////////////////////////////////////////////////////////////////////////
571 template <typename T1, typename T2, typename TCompression>
572 inline T1 getValueI1(Pair<T1, T2, TCompression> const &pair) {
576 template <typename T1, typename T2, typename TCompression>
577 inline T2 getValueI2(Pair<T1, T2, TCompression> const &pair) {
581 template <typename T1, typename T2, unsigned valueSizeI1>
582 inline T1 getValueI1(Pair<T1, T2, CutCompressed<valueSizeI1> > const &pair) {
583 typedef Pair<T1, T2, CutCompressed<valueSizeI1> > TPair;
584 return pair.i12 >> TPair::bitShiftI1;
587 template <typename T1, typename T2, unsigned valueSizeI1>
588 inline T2 getValueI2(Pair<T1, T2, CutCompressed<valueSizeI1> > const &pair) {
589 typedef Pair<T1, T2, CutCompressed<valueSizeI1> > TPair;
590 return pair.i12 & (((typename TPair::T12)1 << TPair::bitShiftI1) - 1);
592 //____________________________________________________________________________
594 template <typename T1, typename T2, typename T3, typename TCompression>
595 inline T1 getValueI1(Triple<T1, T2, T3, TCompression> const &triple) {
599 template <typename T1, typename T2, typename T3, typename TCompression>
600 inline T2 getValueI2(Triple<T1, T2, T3, TCompression> const &triple) {
604 template <typename T1, typename T2, typename T3, typename TCompression>
605 inline T3 getValueI3(Triple<T1, T2, T3, TCompression> const &triple) {
609 //////////////////////////////////////////////////////////////////////////////
612 template <typename T1, typename T2, typename TCompression, typename T>
613 inline void assignValueI1(Pair<T1, T2, TCompression> &pair, T const &_i) {
617 template <typename T1, typename T2, typename TCompression, typename T>
618 inline void assignValueI2(Pair<T1, T2, TCompression> &pair, T const &_i) {
622 template <typename T1, typename T2, unsigned valueSizeI1, typename T>
623 inline void assignValueI1(Pair<T1, T2, CutCompressed<valueSizeI1> > &pair, T const &_i)
625 typedef Pair<T1, T2, CutCompressed<valueSizeI1> > TPair;
626 pair.i12 = ((typename TPair::T12)_i << TPair::bitShiftI1) |
627 (pair.i12 & (((typename TPair::T12)1 << TPair::bitShiftI1) - 1));
630 template <typename T1, typename T2, unsigned valueSizeI1, typename T>
631 inline void assignValueI2(Pair<T1, T2, CutCompressed<valueSizeI1> > &pair, T const &_i) {
632 typedef Pair<T1, T2, CutCompressed<valueSizeI1> > TPair;
633 pair.i12 = (pair.i12 & ~(((typename TPair::T12)1 << TPair::bitShiftI1) - 1)) | _i;
635 //____________________________________________________________________________
637 template <typename T1, typename T2, typename T3, typename TCompression, typename T>
638 inline T const assignValueI1(Triple<T1, T2, T3, TCompression> &triple, T const &_i) {
639 return triple.i1 = _i;
642 template <typename T1, typename T2, typename T3, typename TCompression, typename T>
643 inline T const assignValueI2(Triple<T1, T2, T3, TCompression> &triple, T const &_i) {
644 return triple.i2 = _i;
647 template <typename T1, typename T2, typename T3, typename TCompression, typename T>
648 inline T const assignValueI3(Triple<T1, T2, T3, TCompression> &triple, T const &_i) {
649 return triple.i3 = _i;
652 //////////////////////////////////////////////////////////////////////////////
653 // operator ==/!= for pairs and triples
655 template <typename L1, typename L2, typename LCompression, typename R1, typename R2, typename RCompression>
656 inline bool operator==(Pair<L1, L2, LCompression> const &_left, Pair<R1, R2, RCompression> const &_right) {
657 return _left.i1 == _right.i1 && _left.i2 == _right.i2;
659 template <typename L1, typename L2, typename LCompression, typename R1, typename R2, typename RCompression>
660 inline bool operator!=(Pair<L1, L2, LCompression> const &_left, Pair<R1, R2, RCompression> const &_right) {
661 return _left.i1 != _right.i1 || _left.i2 != _right.i2;
664 template <typename L1, typename L2, unsigned LSizeI1, typename R1, typename R2, unsigned RSizeI1>
665 inline bool operator==(Pair<L1, L2, CutCompressed<LSizeI1> > const &_left, Pair<R1, R2, CutCompressed<RSizeI1> > const &_right) {
666 return _left.i12 == _right.i12;
668 template <typename L1, typename L2, unsigned LSizeI1, typename R1, typename R2, unsigned RSizeI1>
669 inline bool operator!=(Pair<L1, L2, CutCompressed<LSizeI1> > const &_left, Pair<R1, R2, CutCompressed<RSizeI1> > const &_right) {
670 return _left.i12 != _right.i12;
672 //____________________________________________________________________________
675 typename L1, typename L2, typename L3, typename LCompression,
676 typename R1, typename R2, typename R3, typename RCompression>
677 inline bool operator==(Triple<L1, L2, L3, LCompression> const &_left, Triple<R1, R2, R3, RCompression> const &_right) {
678 return _left.i1 == _right.i1 && _left.i2 == _right.i2 && _left.i3 == _right.i3;
681 typename L1, typename L2, typename L3, typename LCompression,
682 typename R1, typename R2, typename R3, typename RCompression>
683 inline bool operator!=(Triple<L1, L2, L3, LCompression> const &_left, Triple<R1, R2, R3, RCompression> const &_right) {
684 return _left.i1 != _right.i1 || _left.i2 != _right.i2 || _left.i3 != _right.i3;
687 }// namespace SEQAN_NAMESPACE_MAIN
689 #endif //#ifndef SEQAN_HEADER_...