1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2015, Knut Reinert, FU Berlin 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above copyright 13 // notice, this list of conditions and the following disclaimer in the 14 // documentation and/or other materials provided with the distribution. 15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of 16 // its contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE 23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 // DAMAGE. 30 // 31 // ========================================================================== 32 // Author: Andreas Gogol-Doering <andreas.doering@mdc-berlin.de> 33 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de> 34 // ========================================================================== 35 36 // TODO(holtgrew): Switch to Host interface. 37 38 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_BASE_H_ 39 #define SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_BASE_H_ 40 41 namespace seqan { 42 43 // ============================================================================ 44 // Forwards 45 // ============================================================================ 46 47 // Internally used tag for creating iterators at the begin of containers. 48 struct Begin__; 49 typedef Tag<Begin__> Begin_; 50 51 // Internally used tag for creating iterators at the end of containers. 52 struct End__; 53 typedef Tag<End__> End_; 54 55 // Internally used tag for creating iterators inside of containers. 56 struct Position__; 57 typedef Tag<Position__> Position_; 58 59 // ============================================================================ 60 // Tags, Classes, Enums 61 // ============================================================================ 62 63 /*! 64 * @class GapsIterator 65 * @implements RandomAccessIteratorConcept 66 * 67 * @brief Iterator class for @link Gaps @endlink. 68 * 69 * @signature template <typename TGaps, typename TSpec> 70 * class Iter<TGaps, GapsIterator<TSpec> >; 71 * 72 * @tparam TGaps The @link Gaps @endlink object for the iterator. 73 * @tparam TSpec The specializing tag. 74 */ 75 76 template <typename TSpec> 77 struct GapsIterator; 78 79 // ============================================================================ 80 // Metafunctions 81 // ============================================================================ 82 83 // ---------------------------------------------------------------------------- 84 // Metafunction Position 85 // ---------------------------------------------------------------------------- 86 87 template <typename TGaps, typename TSpec> 88 struct Position<Iter<TGaps, GapsIterator<TSpec> > > : 89 Position<TGaps> 90 {}; 91 92 template <typename TGaps, typename TSpec> 93 struct Position<Iter<TGaps, GapsIterator<TSpec> > const> : 94 Position<Iter<TGaps, GapsIterator<TSpec> > > 95 {}; 96 97 // ---------------------------------------------------------------------------- 98 // Metafunction Difference 99 // ---------------------------------------------------------------------------- 100 101 template <typename TGaps, typename TSpec> 102 struct Difference<Iter<TGaps, GapsIterator<TSpec> > > : 103 Difference<TGaps> 104 {}; 105 106 template <typename TGaps, typename TSpec> 107 struct Difference<Iter<TGaps, GapsIterator<TSpec> > const> : 108 Difference<Iter<TGaps, GapsIterator<TSpec> > > 109 {}; 110 111 // ---------------------------------------------------------------------------- 112 // Metafunction Source 113 // ---------------------------------------------------------------------------- 114 115 // TODO(holtgrew): Should this be Host? or SourceIterator? 116 117 template <typename TGaps, typename TSpec> 118 struct Source<Iter<TGaps, GapsIterator<TSpec> > > 119 { 120 typedef typename Source<TGaps>::Type TSource_; 121 typedef typename Iterator<TSource_, Rooted>::Type Type; 122 }; 123 124 template <typename TGaps, typename TSpec> 125 struct Source<Iter<TGaps, GapsIterator<TSpec> > const> 126 { 127 typedef typename Source<TGaps>::Type TSource_; 128 typedef typename Iterator<TSource_, Rooted>::Type Type; 129 }; 130 131 // ---------------------------------------------------------------------------- 132 // Metafunction Value 133 // ---------------------------------------------------------------------------- 134 135 template <typename TGaps, typename TSpec> 136 struct Value<Iter<TGaps, GapsIterator<TSpec> > > 137 { 138 typedef typename Source<Iter<TGaps, GapsIterator<TSpec> > >::Type TSource_; 139 typedef typename Value<TSource_>::Type TSourceValue_; 140 //typedef TSourceValue_ Type; 141 // TODO(holtgrew): We really want gapped values here but there are issues... 142 typedef typename GappedValueType<TSourceValue_>::Type Type; 143 }; 144 145 template <typename TGaps, typename TSpec> 146 struct Value<Iter<TGaps, GapsIterator<TSpec> > const> : 147 Value<Iter<TGaps, GapsIterator<TSpec> > > {}; 148 149 // ---------------------------------------------------------------------------- 150 // Metafunction GetValue 151 // ---------------------------------------------------------------------------- 152 153 template <typename TGaps, typename TSpec> 154 struct GetValue<Iter<TGaps, GapsIterator<TSpec> > > : 155 Value<Iter<TGaps, GapsIterator<TSpec> > > 156 { 157 }; 158 159 template <typename TGaps, typename TSpec> 160 struct GetValue<Iter<TGaps, GapsIterator<TSpec> > const> : 161 Value<Iter<TGaps, GapsIterator<TSpec> > const> 162 { 163 }; 164 165 // ---------------------------------------------------------------------------- 166 // Metafunction Reference 167 // ---------------------------------------------------------------------------- 168 169 template <typename TGaps, typename TSpec> 170 struct Reference<Iter<TGaps, GapsIterator<TSpec> > > 171 { 172 typedef Iter<TGaps, GapsIterator<TSpec> > TIterator_; 173 typedef Proxy<IteratorProxy<TIterator_> > Type; 174 }; 175 176 template <typename TGaps, typename TSpec> 177 struct Reference<Iter<TGaps, GapsIterator<TSpec> > const> 178 { 179 typedef Iter<TGaps, GapsIterator<TSpec> const > TIterator_; 180 typedef Proxy<IteratorProxy<TIterator_> > Type; 181 }; 182 183 // ============================================================================ 184 // Functions 185 // ============================================================================ 186 187 // ---------------------------------------------------------------------------- 188 // Function operator++ 189 // ---------------------------------------------------------------------------- 190 191 // TODO(holtgrew): Could be general forward 192 193 template <typename TGaps, typename TSpec> 194 inline Iter<TGaps, GapsIterator<TSpec> > & 195 operator++(Iter<TGaps, GapsIterator<TSpec> > & it) 196 { 197 goNext(it); 198 return it; 199 } 200 201 template <typename TGaps, typename TSpec> 202 inline Iter<TGaps, GapsIterator<TSpec> > 203 operator++(Iter<TGaps, GapsIterator<TSpec> > & it, int) 204 { 205 Iter<TGaps, GapsIterator<TSpec> > ret = it; 206 goNext(it); 207 return ret; 208 } 209 210 // ---------------------------------------------------------------------------- 211 // Function operator-- 212 // ---------------------------------------------------------------------------- 213 214 template <typename TGaps, typename TSpec> 215 inline Iter<TGaps, GapsIterator<TSpec> > & 216 operator--(Iter<TGaps, GapsIterator<TSpec> > & it) 217 { 218 goPrevious(it); 219 return it; 220 } 221 222 template <typename TGaps, typename TSpec> 223 inline Iter<TGaps, GapsIterator<TSpec> > 224 operator--(Iter<TGaps, GapsIterator<TSpec> > & it, int) 225 { 226 Iter<TGaps, GapsIterator<TSpec> > ret = it; 227 goPrevious(it); 228 return ret; 229 } 230 231 // ---------------------------------------------------------------------------- 232 // Function insertGap() 233 // ---------------------------------------------------------------------------- 234 235 /*! 236 * @fn GapsIterator#insertGap 237 * @brief Insert gap at the current position. 238 * 239 * @signature void insertGap(it); 240 * 241 * @param[in,out] it The iterator to insert gaps at. 242 */ 243 244 // Forward to insertGaps() which has to be implemented by the specific gap 245 // iterator. 246 247 template <typename TGaps, typename TSpec> 248 inline void 249 insertGap(Iter<TGaps, GapsIterator<TSpec> > & it) 250 { 251 insertGaps(it, 1); 252 } 253 254 // ---------------------------------------------------------------------------- 255 // Function isCharacter() 256 // ---------------------------------------------------------------------------- 257 258 /*! 259 * @fn GapsIterator#isCharacter 260 * @brief Query an iterator for being at a character 261 * 262 * @signature bool isCharacter(it); 263 * 264 * @param[in] it Iterator to query for pointing at a character. 265 * 266 * @return bool <tt>true</tt> if <tt>it</tt> is at a character and <tt>false</tt> otherwise. 267 */ 268 269 template <typename TGaps, typename TSpec> 270 bool isCharacter(Iter<TGaps, GapsIterator<TSpec> > const & it) 271 { 272 return !isGap(it); 273 } 274 275 // ---------------------------------------------------------------------------- 276 // Function countCharacters() 277 // ---------------------------------------------------------------------------- 278 279 /*! 280 * @fn GapsIterator#countCharacters 281 * @brief Count characters at iterator. 282 * 283 * @signature TSize countCharacters(it); 284 * 285 * @param[in] it Iterator for counting characters at. 286 * 287 * @return TSize Number of characters. 288 */ 289 290 // ---------------------------------------------------------------------------- 291 // Function isGap() 292 // ---------------------------------------------------------------------------- 293 294 /*! 295 * @fn GapsIterator#isGap 296 * @brief Query an iterator for being at a gap 297 * 298 * @signature bool isGap(it); 299 * 300 * @param[in] it Iterator to query for pointing at a gap. 301 * 302 * @return bool <tt>true</tt> if <tt>it</tt> is at a gap and <tt>false</tt> otherwise. 303 */ 304 305 // ---------------------------------------------------------------------------- 306 // Function countGaps() 307 // ---------------------------------------------------------------------------- 308 309 /*! 310 * @fn GapsIterator#countGaps 311 * @brief Count gaps at iterator. 312 * 313 * @signature TSize countGaps(it); 314 * 315 * @param[in] it Iterator for counting gaps at. 316 * 317 * @return TSize Number of gaps. 318 */ 319 320 // ---------------------------------------------------------------------------- 321 // Function insertGaps() 322 // ---------------------------------------------------------------------------- 323 324 /*! 325 * @fn GapsIterator#insertGaps 326 * @brief Insert gaps at the current position. 327 * 328 * @signature void insertGaps(it, num); 329 * 330 * @param[in,out] it Remove gap at the given position (if any). 331 * @param[in] num Number of gaps to insert. 332 */ 333 334 // ---------------------------------------------------------------------------- 335 // Function removeGap() 336 // ---------------------------------------------------------------------------- 337 338 /*! 339 * @fn GapsIterator#removeGap 340 * @brief Insert gap at the current position. 341 * 342 * @signature TSize removeGap(it); 343 * 344 * @param[in,out] it Remove gap at the given position (if any). 345 * 346 * @return TSize Number of removed gaps. 347 */ 348 349 // Forward to removeGaps() which has to be implemented by the specific gap 350 // iterator. 351 352 template <typename TGaps, typename TSpec> 353 inline typename Size<TGaps>::Type 354 removeGap(Iter<TGaps, GapsIterator<TSpec> > & it) 355 { 356 return removeGaps(it, 1); 357 } 358 359 // ---------------------------------------------------------------------------- 360 // Function removeGaps() 361 // ---------------------------------------------------------------------------- 362 363 /*! 364 * @fn GapsIterator#removeGaps 365 * @brief Remove gaps from the current position. 366 * 367 * @signature TSize removeGaps(it, num); 368 * 369 * @param[in,out] it Remove gap at the given position (if any). 370 * @param[in] num Number of gaps to remove. 371 * 372 * @return TSize Number of removed gaps. 373 */ 374 375 // ---------------------------------------------------------------------------- 376 // Function assignValue() 377 // ---------------------------------------------------------------------------- 378 379 // TODO(holtgrew): Const consistency problems. 380 381 template <typename TGaps, typename TSpec, typename TValue> 382 inline void 383 assignValue(Iter<TGaps, GapsIterator<TSpec> > & me, 384 TValue const & val) 385 { 386 if (!isGap(me)) 387 { 388 assignValue(source(me), val); 389 } 390 // TODO(holtgrew): Else, inserting gaps is problematic... 391 } 392 393 template <typename TGaps, typename TSpec, typename TValue> 394 inline void 395 assignValue(Iter<TGaps, GapsIterator<TSpec> > const & me, 396 TValue const & val) 397 { 398 if (!isGap(me)) 399 { 400 assignValue(source(me), val); 401 } 402 } 403 404 // ---------------------------------------------------------------------------- 405 // Function container() 406 // ---------------------------------------------------------------------------- 407 408 template <typename TGaps, typename TSpec> 409 inline TGaps & 410 container(Iter<TGaps, GapsIterator<TSpec> > & me) 411 { 412 return *me._container; 413 } 414 415 template <typename TGaps, typename TSpec> 416 inline TGaps & 417 container(Iter<TGaps, GapsIterator<TSpec> > const & me) 418 { 419 return *me._container; 420 } 421 422 // ---------------------------------------------------------------------------- 423 // Function source 424 // ---------------------------------------------------------------------------- 425 426 // Returns host iterator. 427 428 // TODO(holtgrew): Non-const version is superflous. 429 template <typename TGaps, typename TSpec> 430 inline typename Source<Iter<TGaps, GapsIterator<TSpec> > >::Type /*returns copy*/ 431 source(Iter<TGaps, GapsIterator<TSpec> > & it) 432 { 433 return iter(container(it), toSourcePosition(container(it), position(it))); 434 } 435 436 template <typename TGaps, typename TSpec> 437 inline typename Source<Iter<TGaps, GapsIterator<TSpec> > const>::Type /*returns copy*/ 438 source(Iter<TGaps, GapsIterator<TSpec> > const & it) 439 { 440 return iter(container(source(it)), toSourcePosition(container(it), position(it))); 441 } 442 443 // TODO(holtgrew): setSource? setContainer? 444 445 // ---------------------------------------------------------------------------- 446 // Function operator+= 447 // ---------------------------------------------------------------------------- 448 449 template <typename TGaps, typename TSpec, typename TDiff> 450 inline Iter<TGaps, GapsIterator<TSpec> > & 451 operator+=(Iter<TGaps, GapsIterator<TSpec> > & it, TDiff diff) 452 { 453 goFurther(it, diff); 454 return it; 455 } 456 457 // ---------------------------------------------------------------------------- 458 // Function operator-= 459 // ---------------------------------------------------------------------------- 460 461 template <typename TGaps, typename TSpec, typename TDiff> 462 inline Iter<TGaps, GapsIterator<TSpec> > & 463 operator-=(Iter<TGaps, GapsIterator<TSpec> > & it, TDiff diff) 464 { 465 goFurther(it, -(__int64)(diff)); 466 return it; 467 } 468 469 // ---------------------------------------------------------------------------- 470 // Function goFurther 471 // ---------------------------------------------------------------------------- 472 473 // TODO(holtgrew): Implementation could be faster. 474 template <typename TGaps, typename TSpec, typename TDifference> 475 inline void 476 goFurther(Iter<TGaps, GapsIterator<TSpec> > & it, 477 TDifference steps) 478 { 479 typedef typename MakeSigned<TDifference>::Type TSignedDifference; 480 if (steps > TDifference(0)) 481 for (; steps; --steps) 482 goNext(it); 483 else 484 for (; -static_cast<TSignedDifference>(steps); ++steps) 485 goPrevious(it); 486 } 487 488 // ---------------------------------------------------------------------------- 489 // Function isClipped() 490 // ---------------------------------------------------------------------------- 491 492 template <typename TGaps, typename TSpec> 493 inline bool 494 isClipped(Iter<TGaps, GapsIterator<TSpec> > const &) 495 { 496 return false; 497 } 498 499 } // namespace seqan 500 501 #endif // SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_BASE_H_ 502