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: shape_gapped.h,v 1.1 2008/08/25 16:20:05 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_SHAPE_GAPPED_H
22 #define SEQAN_HEADER_SHAPE_GAPPED_H
24 namespace SEQAN_NAMESPACE_MAIN
27 //////////////////////////////////////////////////////////////////////////////
28 // HardwiredShape allows compiler-time defined gapped shape
31 .Class.HardwiredShape:
33 ..summary:A structure to define a fixed gapped shape.
34 ..signature:HardwiredShape<P1, P2, ..., Pn>
35 ..param.P1, P2, ..., Pn:Px is the distance of the x'th '1' to the next '1' in the shape.
36 ...remarks:At most 20 parameters are allowed, so the maximal shape weight is 21.
37 ..remarks:You can use this structure to define your one gapped shapes in conjunction with @Spec.FixedGappedShape@.
38 ..note:The shape $1100101$ corresponds to $HardwiredShape<1,3,2>$.
39 ..note:The following predefined shapes are already available in $seqan/index/shape_predefined.h$:
40 ..file:../projects/library/seqan/index/shape_predefined.h
43 // Pxx = spaces between '1's
45 int P00 = 0, int P01 = 0, int P02 = 0, int P03 = 0, int P04 = 0,
46 int P05 = 0, int P06 = 0, int P07 = 0, int P08 = 0, int P09 = 0,
47 int P10 = 0, int P11 = 0, int P12 = 0, int P13 = 0, int P14 = 0,
48 int P15 = 0, int P16 = 0, int P17 = 0, int P18 = 0, int P19 = 0
50 struct HardwiredShape {
51 static const int DIFFS[];
55 int P00, int P01, int P02, int P03, int P04,
56 int P05, int P06, int P07, int P08, int P09,
57 int P10, int P11, int P12, int P13, int P14,
58 int P15, int P16, int P17, int P18, int P19
60 const int HardwiredShape<
69 P15,P16,P17,P18,P19, 0
73 //////////////////////////////////////////////////////////////////////////////
74 // LENGTH meta-function for fixed gapped shapes
77 struct LENGTH< HardwiredShape<
87 int P00, int P01, int P02, int P03, int P04,
88 int P05, int P06, int P07, int P08, int P09,
89 int P10, int P11, int P12, int P13, int P14,
90 int P15, int P16, int P17, int P18, int P19
92 struct LENGTH< HardwiredShape<
96 P15,P16,P17,P18,P19> >
98 enum { VALUE = LENGTH< HardwiredShape<
102 P16,P17,P18,P19, 0 > >::VALUE + P00 };
107 int P00, int P01, int P02, int P03, int P04,
108 int P05, int P06, int P07, int P08, int P09,
109 int P10, int P11, int P12, int P13, int P14,
110 int P15, int P16, int P17, int P18, int P19
112 struct LENGTH< Shape<TValue, FixedGappedShape< HardwiredShape<
118 LENGTH< HardwiredShape<
126 //////////////////////////////////////////////////////////////////////////////
127 // WEIGHT meta-function for fixed gapped shapes
130 struct WEIGHT< HardwiredShape<
140 int P00, int P01, int P02, int P03, int P04,
141 int P05, int P06, int P07, int P08, int P09,
142 int P10, int P11, int P12, int P13, int P14,
143 int P15, int P16, int P17, int P18, int P19
145 struct WEIGHT< HardwiredShape<
149 P15,P16,P17,P18,P19> >
151 enum { VALUE = WEIGHT< HardwiredShape<
155 P16,P17,P18,P19, 0 > >::VALUE + 1 };
160 int P00, int P01, int P02, int P03, int P04,
161 int P05, int P06, int P07, int P08, int P09,
162 int P10, int P11, int P12, int P13, int P14,
163 int P15, int P16, int P17, int P18, int P19
165 struct WEIGHT< Shape<TValue, FixedGappedShape< HardwiredShape<
171 WEIGHT< HardwiredShape<
179 //////////////////////////////////////////////////////////////////////////////
184 ..summary:A variable gapped shape.
185 ..general:Class.Shape
186 ..signature:Shape<TValue, GappedShape>
187 ..param.TValue:The @Metafunction.Value@ type of the string the shape is applied to (e.g. $Dna$).
188 ..remarks:A GappedShape must be initialized first with a valid shape. To do so, call @Function.stringToShape@.
189 ..see:Spec.FixedGappedShape
192 //////////////////////////////////////////////////////////////////////////////
193 // variable gapped shape
194 //////////////////////////////////////////////////////////////////////////////
196 template <typename TValue>
197 class Shape<TValue, GappedShape>
200 //____________________________________________________________________________
206 typename Value<Shape>::Type hValue; // current hash value
207 //____________________________________________________________________________
210 .Memfunc.GappedShape#Shape:
211 ..class:Spec.GappedShape
212 ..summary:Constructor
213 ..signature:Shape<TValue, GappedShape> ()
214 ..signature:Shape<TValue, GappedShape> (q)
215 ..signature:Shape<TValue, GappedShape> (shape)
216 ..signature:Shape<TValue, GappedShape> (predefined)
217 ..param.q:Creates an ungapped q-gram.
218 ..param.shape:Any other gapped/ungapped shape.
219 ..param.predefined:Any instance of a predefined shape spec (e.g. $ShapePatternHunter$).
220 ..see:Class.HardwiredShape
224 // c'tor for ungapped shapes
225 Shape(unsigned _span):
230 resize(diffs, _span);
231 for(unsigned i = 0; i < _span; ++i)
235 Shape(Shape const &other):
237 weight(other.weight),
239 hValue(other.hValue) {}
241 template <typename TSpec>
242 Shape(Shape<TValue, TSpec> const &other)
247 template <typename TSpec>
248 Shape(FixedGappedShape<TSpec> const &other)
253 template <typename TStringValue, typename TSpec>
254 Shape(String<TStringValue, TSpec> const &bitmap)
259 //____________________________________________________________________________
261 template <unsigned q>
263 operator=(Shape<TValue, FixedShape<q> > const &other)
265 span = length(other);
266 weight = weight(other);
267 resize(diffs, weight);
268 for(unsigned i = 1; i < weight; ++i)
270 hValue = other.hValue;
274 template <typename TSpec>
276 operator=(Shape<TValue, FixedGappedShape<TSpec> > const &other)
279 weight = other.weight;
281 hValue = other.hValue;
285 template <typename TSpec>
287 operator=(FixedGappedShape<TSpec> const)
289 typedef Shape<TValue, FixedGappedShape<TSpec> > TShape;
290 return *this = TShape();
293 template <typename TStringValue, typename TSpec>
295 operator=(String<TStringValue, TSpec> const &bitmap)
297 stringToShape(*this, bitmap);
303 //////////////////////////////////////////////////////////////////////////////
306 .Spec.FixedGappedShape:
308 ..summary:A fixed gapped shape.
309 ..general:Class.Shape
310 ..signature:Shape<TValue, FixedGappedShape<TSpec> >
311 ..param.TValue:The @Metafunction.Value@ type of the string the shape is applied to (e.g. $Dna$).
312 ..param.TSpec:A structure to store the shape at compile-time.
313 ...type:Class.HardwiredShape
314 ..remarks:There are predefined shapes in $index/shape_predefined.h$.
315 You can simply use them with $Shape<TValue, ShapePatternHunter>$ for example.
316 ..see:Class.HardwiredShape
319 //////////////////////////////////////////////////////////////////////////////
320 // fixed gapped shape
321 //////////////////////////////////////////////////////////////////////////////
323 template <typename TValue, typename TSpec>
324 class Shape<TValue, FixedGappedShape<TSpec> >
327 //____________________________________________________________________________
329 typedef FixedGappedShape<TSpec> TShapeSpec;
331 enum { span = LENGTH<Shape>::VALUE };
332 enum { weight = WEIGHT<Shape>::VALUE };
335 typename Value<Shape>::Type hValue; // current hash value
336 //____________________________________________________________________________
339 diffs(TSpec::DIFFS) {}
341 Shape(Shape const &other):
343 hValue(other.hValue) {}
344 //____________________________________________________________________________
347 operator=(Shape const &other)
349 hValue = other.hValue;
353 //////////////////////////////////////////////////////////////////////////////
355 template <typename TValue, typename TSpec>
356 inline typename Size< Shape<TValue, FixedGappedShape<TSpec> > >::Type
357 weight(Shape<TValue, FixedGappedShape<TSpec> > const & me)
363 //____________________________________________________________________________
365 template <typename TValue, typename TIter>
366 inline typename Value< Shape<TValue, GappedShape> >::Type
367 hash(Shape<TValue, GappedShape> &me, TIter it)
370 typedef typename Value< Shape<TValue, GappedShape> >::Type THValue;
371 typedef typename Size< Shape<TValue, GappedShape> >::Type TSize;
373 me.hValue = ordValue((TValue)*it);
374 TSize iEnd = me.weight - 1;
375 for(TSize i = 0; i < iEnd; ++i) {
376 goFurther(it, me.diffs[i]);
377 me.hValue = me.hValue * ValueSize<TValue>::VALUE + ordValue((TValue)*it);
382 template <typename TValue, typename TSpec, typename TIter, typename TSize>
383 inline typename Value< Shape<TValue, FixedGappedShape<TSpec> > >::Type
384 hash(Shape<TValue, FixedGappedShape<TSpec> > &me, TIter it, TSize charsLeft)
387 typedef typename Value< Shape<TValue, FixedGappedShape<TSpec> > >::Type THValue;
389 TSize iEnd = me.weight;
390 if (iEnd > charsLeft) iEnd = charsLeft;
394 me.hValue = ordValue((TValue)*it);
396 for(; i < iEnd; ++i) {
397 goFurther(it, me.diffs[i]);
398 me.hValue = me.hValue * ValueSize<TValue>::VALUE + ordValue((TValue)*it);
402 return me.hValue = 0;
404 // fill shape with zeros
405 for(; i < (TSize)me.weight; ++i)
406 me.hValue *= ValueSize<TValue>::VALUE;
410 template <typename TValue, typename TSpec, typename TIter, typename TSize>
411 inline typename Value< Shape<TValue, FixedGappedShape<TSpec> > >::Type
412 hashUpper(Shape<TValue, FixedGappedShape<TSpec> > &me, TIter it, TSize charsLeft)
415 typedef typename Value< Shape<TValue, FixedGappedShape<TSpec> > >::Type THValue;
417 TSize iEnd = me.weight;
418 if (iEnd > charsLeft) iEnd = charsLeft;
422 me.hValue = ordValue((TValue)*it);
424 for(; i < iEnd; ++i) {
425 goFurther(it, me.diffs[i]);
426 me.hValue = me.hValue * ValueSize<TValue>::VALUE + ordValue((TValue)*it);
431 return me.hValue = 1;
433 // fill shape with zeros
434 for(; i < (TSize)me.weight; ++i)
435 me.hValue *= ValueSize<TValue>::VALUE;
439 //____________________________________________________________________________
441 template <typename THValue, typename TValue, typename TIter>
443 _hashHardwiredShape(THValue hash, TIter &, TValue const, HardwiredShape<
453 int P01, int P02, int P03, int P04,
454 int P05, int P06, int P07, int P08, int P09,
455 int P10, int P11, int P12, int P13, int P14,
456 int P15, int P16, int P17, int P18, int P19,
457 typename THValue, typename TValue, typename TIter
460 _hashHardwiredShape(THValue hash, TIter &it, TValue const, HardwiredShape<
464 P15,P16,P17,P18,P19 > const)
467 return _hashHardwiredShape(hash * ValueSize<TValue>::VALUE + ordValue((TValue)*it),
468 it, TValue(), HardwiredShape<
472 P16,P17,P18,P19, 0 >());
476 int P00, int P01, int P02, int P03, int P04,
477 int P05, int P06, int P07, int P08, int P09,
478 int P10, int P11, int P12, int P13, int P14,
479 int P15, int P16, int P17, int P18, int P19,
480 typename THValue, typename TValue, typename TIter
483 _hashHardwiredShape(THValue hash, TIter &it, TValue const, HardwiredShape<
487 P15,P16,P17,P18,P19 > const)
490 return _hashHardwiredShape(hash * ValueSize<TValue>::VALUE + ordValue((TValue)*it),
491 it, TValue(), HardwiredShape<
495 P16,P17,P18,P19, 0 >());
499 int P00, int P01, int P02, int P03, int P04,
500 int P05, int P06, int P07, int P08, int P09,
501 int P10, int P11, int P12, int P13, int P14,
502 int P15, int P16, int P17, int P18, int P19,
503 typename TValue, typename TIter
505 inline typename Value< Shape<TValue, FixedGappedShape< HardwiredShape<
511 hash(Shape<TValue, FixedGappedShape< HardwiredShape<
519 typedef HardwiredShape<
523 P15,P16,P17,P18,P19 > TSpec;
524 typedef FixedGappedShape<TSpec> TShape;
525 typedef typename Value< Shape<TValue, TShape> >::Type THValue;
527 me.hValue = (THValue)ordValue((TValue)*it);
528 return me.hValue = _hashHardwiredShape(me.hValue, it, TValue(), TSpec());
531 //____________________________________________________________________________
533 template <typename TValue, typename TSpec, typename TIter>
534 inline typename Value< Shape<TValue, FixedGappedShape<TSpec> > >::Type
535 hashNext(Shape<TValue, FixedGappedShape<TSpec> > &me, TIter it)
542 //____________________________________________________________________________
544 /**.Function.stringToShape:
546 ..summary:Takes a shape given as a string of '1' (relevant position) and '0'
547 (irrelevant position) and converts it into a Shape object.
548 ..signature:stringToShape(shape, bitmap)
549 ..param.shape:Shape object that is manipulated.
550 ...type:Spec.GappedShape
551 ..param.bitmap:A character string of '1' and '0' representing relevant and irrelevant positions (blanks) respectively.
552 ...remarks:This string must begin with a '1'.
556 template <typename TValue, typename TSpec, typename TShapeString>
559 Shape<TValue, FixedGappedShape<TSpec> > &me,
560 TShapeString const &bitmap)
563 typedef typename Iterator<TShapeString const>::Type TIter;
564 typedef typename Iterator<String<int> >::Type TShapeIter;
566 me.span = length(bitmap);
568 unsigned oneCount = 0;
569 TIter it = begin(bitmap, Standard());
570 TIter itEnd = end(bitmap, Standard());
571 for(; it != itEnd; ++it)
575 me.weight = oneCount;
576 resize(me.diffs, oneCount);
579 it = begin(bitmap, Standard());
580 TShapeIter itS = begin(me.diffs, Standard());
581 for(; it != itEnd; ++it) {