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: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de> 33 // ========================================================================== 34 // Specialization "Chained" for class Seed. 35 // ========================================================================== 36 37 #ifndef SEQAN_SEEDS_SEEDS_SEED_CHAINED_H_ 38 #define SEQAN_SEEDS_SEEDS_SEED_CHAINED_H_ 39 40 namespace seqan { 41 42 // =========================================================================== 43 // Enums, Tags, Classes, Specializations 44 // =========================================================================== 45 46 // --------------------------------------------------------------------------- 47 // Class Chained Seed 48 // --------------------------------------------------------------------------- 49 50 struct Chained_; 51 typedef Tag<Chained_> ChainedSeed; // TODO(holtgrew): Chained already taken as template in file. Maybe prefer non-parameterized types for simpler names. 52 53 /*! 54 * @class ChainedSeed 55 * @implements ContainerConcept 56 * @extends Seed 57 * @headerfile <seqan/seeds.h> 58 * 59 * @brief Describes a seed with start and end position2 and diagonal upper and lower bounds. 60 * 61 * @signature template <[typename TConfig]> 62 * class Seed<ChainedSeed, TConfig>; 63 * 64 * @tparam TConfig The configuration to use for the chained seed specialization. Defaults to 65 * @link DefaultSeedConfig @endlink. 66 * 67 * Diagonals are stored as @link SeedDiagonal @endlink objects. 68 * 69 * 70 * @fn ChainedSeed::Seed 71 * @brief Constructor 72 * 73 * @signature Seed::Seed(); 74 * @signature Seed::Seed(beginPosH, beginPosV, length); 75 * 76 * @param[in] beginPosH Begin position in dat abase (horizontal). 77 * @param[in] beginPosV Begin position in query (vertical). 78 * @param[in] length The length of the seed. 79 */ 80 81 template <typename TConfig> 82 class Seed<ChainedSeed, TConfig> 83 { 84 public: 85 typedef typename TConfig::TPosition TPosition; 86 typedef typename TConfig::TSize TSize; 87 typedef typename TConfig::TDiagonal TDiagonal; 88 typedef typename TConfig::TScoreValue TScoreValue; 89 90 typedef SeedDiagonal<TPosition, TSize> TSeedDiagonal; 91 92 std::list<TSeedDiagonal> _seedDiagonals; 93 TDiagonal _lowerDiagonal; 94 TDiagonal _upperDiagonal; 95 96 TScoreValue _score; 97 Seed()98 Seed() : _lowerDiagonal(0), _upperDiagonal(0), _score(0) 99 {} 100 Seed(TPosition beginPositionH,TPosition beginPositionV,TPosition seedLength)101 Seed(TPosition beginPositionH, TPosition beginPositionV, TPosition seedLength) : 102 _lowerDiagonal(beginPositionH - beginPositionV), _upperDiagonal(beginPositionH - beginPositionV), _score(0) 103 { 104 appendValue(_seedDiagonals, TSeedDiagonal(beginPositionH, beginPositionV, seedLength)); 105 } 106 }; 107 108 // =========================================================================== 109 // Metafunctions 110 // =========================================================================== 111 112 // --------------------------------------------------------------------------- 113 // Metafunction Value 114 // --------------------------------------------------------------------------- 115 116 /*! 117 * @mfn ChainedSeed#Value 118 * @brief The type of the diagonals in the ChainedSeed. 119 * 120 * @signature Value<TChainedSeed>::Type; 121 * 122 * @tparam TChainedSeed The seed to query for its diagonal object type. 123 * 124 * @return Type The resulting diagonal seed. 125 */ 126 127 template <typename TConfig> 128 struct Value<Seed<ChainedSeed, TConfig> > 129 { 130 typedef Seed<ChainedSeed, TConfig> TSeed_; 131 typedef typename Position<TSeed_>::Type TPosition_; 132 typedef typename Size<TSeed_>::Type TSize_; 133 134 typedef SeedDiagonal<TPosition_, TSize_> Type; 135 }; 136 137 template <typename TConfig> 138 struct Value<Seed<ChainedSeed, TConfig> const> 139 { 140 typedef Seed<ChainedSeed, TConfig> TSeed_; 141 typedef typename Position<TSeed_>::Type TPosition_; 142 typedef typename Size<TSeed_>::Type TSize_; 143 144 typedef SeedDiagonal<TPosition_, TSize_> const Type; 145 }; 146 147 // --------------------------------------------------------------------------- 148 // Metafunction Reference 149 // --------------------------------------------------------------------------- 150 151 /*! 152 * @mfn ChainedSeed#Reference 153 * @brief Reference to the seed diagonal type. 154 * 155 * @signature Reference<TChainedSeed>::Type; 156 * 157 * @tparam TChainedSeed The seed to query for the reference to diagonal values. 158 * 159 * @return Type Reference to the contained seeds. 160 */ 161 162 template <typename TConfig> 163 struct Reference<Seed<ChainedSeed, TConfig> > 164 { 165 typedef Seed<ChainedSeed, TConfig> TSeed_; 166 typedef typename Value<TSeed_>::Type TSeedDiagonal_; 167 typedef TSeedDiagonal_ & Type; 168 }; 169 170 template <typename TConfig> 171 struct Reference<Seed<ChainedSeed, TConfig> const> 172 { 173 typedef Seed<ChainedSeed, TConfig> TSeed_; 174 typedef typename Value<TSeed_>::Type TSeedDiagonal_; 175 typedef TSeedDiagonal_ const & Type; 176 }; 177 178 // --------------------------------------------------------------------------- 179 // Metafunction Iterator 180 // --------------------------------------------------------------------------- 181 182 /*! 183 * @mfn ChainedSeed#Iterator 184 * @brief The type for iterating over the diagonals in a seed. 185 * 186 * @signature Iterator<TChainedSeed[, Tag]>::Type; 187 * 188 * @tparam TChainedSeed The seed to query for the diagonal iterator type. 189 * @tparam Tag The tag to select the iterator with. One of <tt>Standard</tt> and <tt>Rooted</tt>. 190 * 191 * @return Type Reference to the contained seeds. 192 */ 193 194 template <typename TConfig> 195 struct Iterator<Seed<ChainedSeed, TConfig>, Standard> 196 { 197 typedef Seed<ChainedSeed, TConfig> TSeed_; 198 typedef typename Value<TSeed_>::Type TSeedDiagonal_; 199 typedef typename std::list<TSeedDiagonal_>::iterator Type; 200 }; 201 202 template <typename TConfig> 203 struct Iterator<Seed<ChainedSeed, TConfig> const, Standard> 204 { 205 typedef Seed<ChainedSeed, TConfig> TSeed_; 206 typedef typename Value<TSeed_>::Type TSeedDiagonal_; 207 typedef typename std::list<TSeedDiagonal_>::const_iterator Type; 208 }; 209 210 // =========================================================================== 211 // Functions 212 // =========================================================================== 213 214 // --------------------------------------------------------------------------- 215 // Debug Function operator<<() 216 // --------------------------------------------------------------------------- 217 218 template <typename TStream, typename TConfig> 219 inline TStream & 220 operator<<(TStream & stream, Seed<ChainedSeed, TConfig> const & seed) 221 { 222 typedef Seed<ChainedSeed, TConfig> const TSeed; 223 typedef typename Iterator<TSeed>::Type TIterator; 224 225 stream << "Seed<ChainedSeed, TConfig>(["; 226 for (TIterator it = begin(seed); it != end(seed); ++it) { 227 if (it != begin(seed)) 228 stream << ", "; 229 stream << *it; 230 } 231 stream << "])"; 232 return stream; 233 } 234 235 // --------------------------------------------------------------------------- 236 // Function operator==() 237 // --------------------------------------------------------------------------- 238 239 // TODO(holtgrew): Documentation comes through concept. 240 241 template <typename TConfig> 242 inline bool 243 operator==(Seed<ChainedSeed, TConfig> const & a, Seed<ChainedSeed, TConfig> const & b) 244 { 245 return a._seedDiagonals == b._seedDiagonals && 246 a._upperDiagonal == b._upperDiagonal && 247 a._lowerDiagonal == b._lowerDiagonal; 248 } 249 250 // --------------------------------------------------------------------------- 251 // Function beginPositionH() 252 // --------------------------------------------------------------------------- 253 254 template <typename TConfig> 255 inline typename Position<Seed<ChainedSeed, TConfig> >::Type 256 beginPositionH(Seed<ChainedSeed, TConfig> const & seed) 257 { 258 return front(seed._seedDiagonals).beginPositionH; 259 } 260 261 // --------------------------------------------------------------------------- 262 // Function endPositionH() 263 // --------------------------------------------------------------------------- 264 265 template <typename TConfig> 266 inline typename Position<Seed<ChainedSeed, TConfig> >::Type 267 endPositionH(Seed<ChainedSeed, TConfig> const & seed) 268 { 269 return back(seed._seedDiagonals).beginPositionH + back(seed._seedDiagonals).length; 270 } 271 272 // --------------------------------------------------------------------------- 273 // Function beginPositionV() 274 // --------------------------------------------------------------------------- 275 276 template <typename TConfig> 277 inline typename Position<Seed<ChainedSeed, TConfig> >::Type 278 beginPositionV(Seed<ChainedSeed, TConfig> const & seed) 279 { 280 return front(seed._seedDiagonals).beginPositionV; 281 } 282 283 // --------------------------------------------------------------------------- 284 // Function endPositionV() 285 // --------------------------------------------------------------------------- 286 287 template <typename TConfig> 288 inline typename Position<Seed<ChainedSeed, TConfig> >::Type 289 endPositionV(Seed<ChainedSeed, TConfig> const & seed) 290 { 291 return back(seed._seedDiagonals).beginPositionV + back(seed._seedDiagonals).length; 292 } 293 294 // --------------------------------------------------------------------------- 295 // Function length() 296 // --------------------------------------------------------------------------- 297 298 /*! 299 * @fn ChainedSeed#length 300 * @brief Returns the number of diagonals in the ChainedSeed. 301 * 302 * @signature TSize length(seed); 303 * 304 * @param[in] seed The ChainedSeed to query for its number of diagonals. 305 * 306 * @return TSize The number of diagonals in the ChainedSeed. TSize is the @link ContainerConcept#Size @endlink type of 307 * <tt>seed</tt> 308 */ 309 310 template <typename TConfig> 311 inline typename Size<Seed<ChainedSeed, TConfig> >::Type 312 length(Seed<ChainedSeed, TConfig> const & seed) 313 { 314 return length(seed._seedDiagonals); 315 } 316 317 // --------------------------------------------------------------------------- 318 // Function appendDiagonal() 319 // --------------------------------------------------------------------------- 320 321 /*! 322 * @fn ChainedSeed#appendDiagonal 323 * @brief Adds a digional to a ChainedSeed. 324 * 325 * @signature void appendSeed(seed, diagonal); 326 * 327 * @param[in,out] seed The ChainedSeed to which the digonal should be added. 328 * @param[in] diagonal The SeedDiagional to add to <tt>seed</tt>. 329 */ 330 331 template <typename TConfig> 332 inline void 333 appendDiagonal(Seed<ChainedSeed, TConfig> & seed, 334 typename Value<Seed<ChainedSeed, TConfig> >::Type const & diagonal) 335 { 336 // TODO(holtgrew): Add empty(). 337 if (length(seed) > 0) 338 { 339 SEQAN_ASSERT_LEQ(back(seed._seedDiagonals).beginPositionH + back(seed._seedDiagonals).length, diagonal.beginPositionH); 340 SEQAN_ASSERT_LEQ(back(seed._seedDiagonals).beginPositionV + back(seed._seedDiagonals).length, diagonal.beginPositionV); 341 } 342 343 appendValue(seed._seedDiagonals, diagonal); 344 } 345 346 // --------------------------------------------------------------------------- 347 // Function truncateDiagonals() 348 // --------------------------------------------------------------------------- 349 350 /*! 351 * @fn ChainedSeed#truncateDiagonals 352 * @brief Removes diagonals from the given first one to the end of the seed's diagonals. 353 * 354 * @signature void truncateDiagonals(seed, first); 355 * 356 * @param[in,out] seed The ChainedSeed to truncate diagonals from. 357 * @param[in] first An iterator into the ChainedSeed, as returned by @link ChainedSeed#Iterator @endlink. 358 */ 359 360 template <typename TConfig> 361 inline void 362 truncateDiagonals(Seed<ChainedSeed, TConfig> & seed, 363 typename Iterator<Seed<ChainedSeed, TConfig> >::Type const & first) 364 { 365 // TODO(holtgrew): Add erase() to std::list adaptors? 366 seed._seedDiagonals.erase(first, seed._seedDiagonals.end()); 367 } 368 369 // --------------------------------------------------------------------------- 370 // Function begin() 371 // --------------------------------------------------------------------------- 372 373 /*! 374 * @fn ChainedSeed#begin 375 * @brief Returns an iterator to the beginning of the ChainedSeed's diagonals. 376 * 377 * @signature TIter begin(seed[, tag]); 378 * 379 * @param[in] seed The ChainedSeed to the begin iterator for. 380 * @param[in] tag A tag for selecting the type of the iterator, one of <tt>Standard</tt> and <tt>Rooted</tt>. 381 */ 382 383 template <typename TConfig> 384 inline typename Iterator<Seed<ChainedSeed, TConfig> >::Type 385 begin(Seed<ChainedSeed, TConfig> & seed, Standard const &) 386 { 387 return seed._seedDiagonals.begin(); 388 } 389 390 template <typename TConfig> 391 inline typename Iterator<Seed<ChainedSeed, TConfig> const>::Type 392 begin(Seed<ChainedSeed, TConfig> const & seed, Standard const &) 393 { 394 return seed._seedDiagonals.begin(); 395 } 396 397 // --------------------------------------------------------------------------- 398 // Function end() 399 // --------------------------------------------------------------------------- 400 401 /*! 402 * @fn ChainedSeed#end 403 * @brief Returns an iterator to the end of the ChainedSeed's diagonals. 404 * 405 * @signature TIter end(seed[, tag]); 406 * 407 * @param[in] seed The ChainedSeed to the end iterator for. 408 * @param[in] tag A tag for selecting the type of the iterator, one of <tt>Standard</tt> and <tt>Rooted</tt>. 409 */ 410 411 template <typename TConfig> 412 inline typename Iterator<Seed<ChainedSeed, TConfig> >::Type 413 end(Seed<ChainedSeed, TConfig> & seed, Standard const &) 414 { 415 return seed._seedDiagonals.end(); 416 } 417 418 template <typename TConfig> 419 inline typename Iterator<Seed<ChainedSeed, TConfig> const>::Type 420 end(Seed<ChainedSeed, TConfig> const & seed, Standard const &) 421 { 422 return seed._seedDiagonals.end(); 423 } 424 425 // --------------------------------------------------------------------------- 426 // Function front() 427 // --------------------------------------------------------------------------- 428 429 /*! 430 * @fn ChainedSeed#front 431 * @brief Returns a reference to the first ChainedSeed diagonal. 432 * 433 * @signature TReference front(seed); 434 * 435 * @param[in] seed The ChainedSeed to query. 436 * 437 * @return TReference Reference to first ChainedSeed diagonal. TReference is the reference type of <tt>seed</tt>. 438 */ 439 440 template <typename TConfig> 441 inline typename Reference<Seed<ChainedSeed, TConfig> >::Type 442 front(Seed<ChainedSeed, TConfig> & seed) 443 { 444 return front(seed._seedDiagonals); 445 } 446 447 template <typename TConfig> 448 inline typename Reference<Seed<ChainedSeed, TConfig> const>::Type 449 front(Seed<ChainedSeed, TConfig> const & seed) 450 { 451 return front(seed._seedDiagonals); 452 } 453 454 // --------------------------------------------------------------------------- 455 // Function back() 456 // --------------------------------------------------------------------------- 457 458 /*! 459 * @fn ChainedSeed#back 460 * @brief Returns a reference to the ChainedSeed diagonal. 461 * 462 * @signature TReference back(seed); 463 * 464 * @param[in] seed The ChainedSeed to query. 465 * 466 * @return TReference Reference to the last ChainedSeed diagonal. TReference is the reference type of <tt>seed</tt>. 467 */ 468 469 template <typename TConfig> 470 inline typename Reference<Seed<ChainedSeed, TConfig> >::Type 471 back(Seed<ChainedSeed, TConfig> & seed) 472 { 473 SEQAN_CHECKPOINT; 474 return back(seed._seedDiagonals); 475 } 476 477 template <typename TConfig> 478 inline typename Reference<Seed<ChainedSeed, TConfig> const>::Type 479 back(Seed<ChainedSeed, TConfig> const & seed) 480 { 481 SEQAN_CHECKPOINT; 482 return back(seed._seedDiagonals); 483 } 484 485 // --------------------------------------------------------------------------- 486 // Debug Function 487 // --------------------------------------------------------------------------- 488 489 template <typename TStream, typename TConfig> 490 inline void 491 __write(TStream & stream, Seed<ChainedSeed, TConfig> const & seed, Tikz_ const &) 492 { 493 //IOREV _nodoc_ specialization not documented 494 // Overall seed. 495 stream << "\\draw[seed] (" << getBeginDim1(seed) << ", -" << getBeginDim0(seed) << ") -- (" << (getEndDim1(seed) - 1) << ", -" << (getEndDim0(seed) - 1) << ");" << std::endl; 496 // Diagonals. 497 typedef Seed<ChainedSeed, TConfig> TSeed; 498 typedef typename Iterator<TSeed const, Standard>::Type TIterator; 499 for (TIterator it = begin(seed); it != end(seed); ++it) 500 stream << "\\draw[seed diagonal] (" << it->beginDim1 << ", -" << it->beginDim0 << ") -- (" << (it->beginDim1 + it->length - 1) << ", -" << (it->beginDim0 + it->length - 1) << ");" << std::endl; 501 } 502 503 } // namespace seqan 504 505 #endif // SEQAN_SEEDS_SEEDS_SEED_CHAINED_H_ 506