1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2018, 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-Döring <andreas.doering@mdc-berlin.de> 33 // ========================================================================== 34 // Iterator interface with default implementations. 35 // ========================================================================== 36 37 // TODO(holtgrew): Split into iterator_interface.h and iterator_adapt_pointer.h. 38 39 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ITERATOR_INTERFACE_H_ 40 #define SEQAN_INCLUDE_SEQAN_BASIC_ITERATOR_INTERFACE_H_ 41 42 namespace seqan { 43 44 // ============================================================================ 45 // Forwards 46 // ============================================================================ 47 48 // ============================================================================ 49 // Tags, Classes, Enums 50 // ============================================================================ 51 52 /*! 53 * @defgroup ContainerIteratorTags Container Iterator Tags 54 * @brief Tags for container iterators. 55 * 56 * The tags <tt>Standard</tt> and <tt>Rooted</tt> can be used for selecting specific iterator types with the 57 * @link ContainerConcept#Iterator @endlink metafunction. Rooted iterators also carry a pointer to the container 58 * they are iterating whereas standard iterators do not carry this information. 59 * 60 * @tag ContainerIteratorTags#Standard 61 * @headerfile <seqan/basic.h> 62 * @brief Tag for selecting standard iterators. 63 * @signature struct Standard_; 64 * typedef Tag<Standard_> Standard; 65 * 66 * @tag ContainerIteratorTags#Rooted 67 * @headerfile <seqan/basic.h> 68 * @brief Tag for selecting rooted iterators. 69 * @signature struct Rooted_; 70 * typedef Tag<Rooted_> Rooted; 71 */ 72 73 struct Rooted_; 74 typedef Tag<Rooted_> const Rooted; 75 76 struct Standard_; 77 typedef Tag<Standard_> const Standard; 78 79 // ============================================================================ 80 // Metafunctions 81 // ============================================================================ 82 83 // ---------------------------------------------------------------------------- 84 // Metafunction DefaultIteratorSpec 85 // ---------------------------------------------------------------------------- 86 87 /*! 88 * @mfn ContainerConcept#DefaultIteratorSpec 89 * @brief Returns the default iterator specialization. 90 * 91 * @signature DefaultIteratorSpec<TContainer>::Type 92 * 93 * @tparam TContainer The Container type to query. 94 * @return Type The iterator specialization tag type. 95 * 96 * Used by @link ContainerConcept#Iterator @endlink to select the default value for <tt>TSpec</tt>. 97 * 98 * @see ContainerConcept#Iterator 99 */ 100 101 template <typename T> 102 struct DefaultIteratorSpec 103 { 104 typedef Standard Type; 105 }; 106 107 // ---------------------------------------------------------------------------- 108 // Metafunction DefaultGetIteratorSpec 109 // ---------------------------------------------------------------------------- 110 111 /*! 112 * @mfn ContainerConcept#DefaultGetIteratorSpec 113 * @brief Returns the default iterator specialization for functions. 114 * 115 * @signature DefaultGetIteratorSpec<TContainer>::Type 116 * 117 * @tparam TContainer The Container type to query. 118 * @return Type The iterator specialization tag type. 119 * 120 * Used by functions such as @link ContainerConcept#begin @endlink and @link ContainerConcept#end @endlink for the <tt>TSpec</tt> 121 * parameter. 122 * 123 * @see ContainerConcept#Iterator 124 */ 125 126 template <typename T> 127 struct DefaultGetIteratorSpec 128 { 129 typedef Rooted Type; 130 }; 131 132 // ---------------------------------------------------------------------------- 133 // Metafunction Iterator 134 // ---------------------------------------------------------------------------- 135 136 template <typename T, typename TSpec> 137 struct IteratorDefaultImp_; 138 139 // We use plain pointers as standard iterators. 140 template <typename T> 141 struct IteratorDefaultImp_<T, Standard> 142 { 143 typedef typename Value<T>::Type * Type; 144 }; 145 146 // (weese): This definition is important and defines default const-iterators. Don't remove. 147 // However, there are different places where const-correctness is broken that must be fixed before we can uncomment this 148 149 template <typename T> 150 struct IteratorDefaultImp_<T const, Standard> 151 { 152 typedef typename Value<T>::Type const * Type; 153 }; 154 155 //IteratorDefaultImp_<T, Rooted> is implemented in basic_iterator_adaptor.h 156 157 // TODO(weese): Mmh. What was the reason to introduce the helper struct IteratorDefaultImp_ instead of directly defining it here. 158 // Aah. I guess in to allow to specialize Iterator only in the first template argument. However, right now it is always 159 // specialized for both the first and second argument everywhere in the code. 160 template <typename T, typename TSpec = typename DefaultIteratorSpec<T>::Type> 161 struct Iterator : IteratorDefaultImp_<T, TSpec> 162 { 163 }; 164 165 // ---------------------------------------------------------------------------- 166 // Metafunction Container 167 // ---------------------------------------------------------------------------- 168 169 // TODO(holtgrew): Remove the default implementation; anti-auto-sequence. Also, using plain pointers for strings does not work any more. Will probably only work for rooted/adaptor/positional iterators. Same below. 170 171 template <typename T> 172 struct Container 173 { 174 typedef T Type; 175 }; 176 177 // ============================================================================ 178 // Functions 179 // ============================================================================ 180 181 // --------------------------------------------------------------------------- 182 // Function value() 183 // --------------------------------------------------------------------------- 184 185 template <typename T> 186 [[deprecated("Use operator*() instead.")]] 187 inline typename Reference<T>::Type 188 value(T & me) 189 { 190 return *me; 191 } 192 193 template <typename T> 194 [[deprecated("Use operator*() instead.")]] 195 inline typename Reference<T const>::Type 196 value(T const & me) 197 { 198 return *me; 199 } 200 201 // --------------------------------------------------------------------------- 202 // Function getValue() 203 // --------------------------------------------------------------------------- 204 205 template <typename T> 206 [[deprecated("Use operator*() instead.")]] 207 inline typename GetValue<T>::Type 208 getValue(T & me) 209 { 210 return *me; 211 } 212 213 template <typename T> 214 [[deprecated("Use operator*() instead.")]] 215 inline typename GetValue<T const>::Type 216 getValue(T const & me) 217 { 218 return *me; 219 } 220 221 // --------------------------------------------------------------------------- 222 // Function toGetValue() 223 // --------------------------------------------------------------------------- 224 225 //Nimmt eine Reference und macht daraus einen GetValue 226 // TODO(doering):toGetValue() 227 228 // --------------------------------------------------------------------------- 229 // Function assignValue() 230 // --------------------------------------------------------------------------- 231 232 template <typename T, typename TValue> 233 [[deprecated("Use dereferencement and assignment instead.")]] 234 inline void 235 assignValue(T & me, 236 TValue const & _value) 237 { 238 assign(*me, _value); 239 } 240 241 //const version for iterators as targets 242 template <typename T, typename TValue> 243 [[deprecated("Use dereferencement and assignment instead.")]] 244 inline void 245 assignValue(T const & me, 246 TValue const & _value) 247 { 248 assign(*me, _value); 249 } 250 251 // --------------------------------------------------------------------------- 252 // Function moveValue() 253 // --------------------------------------------------------------------------- 254 255 /*! 256 * @fn OutputIteratorConcept#moveValue 257 * @headerfile <seqan/sequence.h> 258 * @brief Move a value of a container to a given position. 259 * 260 * @signature void moveValue(container, pos, value); 261 * 262 * @param[in,out] container The container to manipulate. 263 * @param[in] pos The position of the item in the container to manipulate. 264 * @param[in,out] value The value to move to <tt>container[pos]</tt>. 265 */ 266 267 template <typename T, typename TValue> 268 inline void 269 moveValue(T & me, 270 TValue const & _value) 271 { 272 move(value(me), _value); 273 } 274 275 //const version for iterators as targets 276 template <typename T, typename TValue> 277 inline void 278 moveValue(T const & me, 279 TValue const & _value) 280 { 281 move(value(me), _value); 282 } 283 284 // --------------------------------------------------------------------------- 285 // Function setValue() 286 // --------------------------------------------------------------------------- 287 288 template <typename T, typename TValue> 289 inline void 290 setValue(T * & ptr, 291 TValue & _value) 292 { 293 ptr = &_value; 294 } 295 296 //const version for iterators as targets 297 template <typename T, typename TValue> 298 inline void 299 setValue(T const * & ptr, 300 TValue const & _value) 301 { 302 ptr = &_value; 303 } 304 305 // --------------------------------------------------------------------------- 306 // Function container() 307 // --------------------------------------------------------------------------- 308 309 template <typename T> 310 inline 311 typename Container<T>::Type & 312 container(T me) 313 { 314 // TODO(holtgrew): Default implementation with auto-sequences, remove? 315 return me; 316 } 317 318 // --------------------------------------------------------------------------- 319 // Function position() 320 // --------------------------------------------------------------------------- 321 322 template <typename T> 323 inline typename Position<T>::Type 324 position(T * /*me*/) 325 { 326 // TODO(holtgrew): Default implementation with auto-sequences, remove? 327 return 0; 328 } 329 330 template <typename TContainer, typename TIterator> 331 inline typename Position<TContainer>::Type 332 position(TIterator const & it, 333 TContainer const & me) 334 { 335 return it - begin(me, Standard()); 336 } 337 338 // --------------------------------------------------------------------------- 339 // Function atBegin() 340 // --------------------------------------------------------------------------- 341 342 // TODO(doering): Was, wenn der Container leer ist? 343 344 template <typename T, typename TContainer> 345 inline bool 346 atBegin(T const & it, 347 TContainer const & cont) 348 { 349 return it == begin(cont, Standard()); 350 } 351 352 template <typename T> 353 inline bool 354 atBegin(T const & it) 355 { 356 return atBegin(it, container(it)); 357 } 358 359 // --------------------------------------------------------------------------- 360 // Function atEnd() 361 // --------------------------------------------------------------------------- 362 363 template <typename T, typename TContainer> 364 inline bool 365 atEnd(T const & it, 366 TContainer const & cont) 367 { 368 return it == end(cont, Standard()); 369 } 370 371 template <typename T> 372 inline bool 373 atEnd(T const & it) 374 { 375 return atEnd(it, container(it)); 376 } 377 378 // --------------------------------------------------------------------------- 379 // Function goBegin() 380 // --------------------------------------------------------------------------- 381 382 template <typename TIterator, typename TContainer> 383 inline void 384 goBegin(TIterator & it, 385 TContainer & container) 386 { 387 it = begin(container); 388 } 389 390 // template <typename TIterator, typename TContainer> 391 // inline void 392 // goBegin(TIterator & it, 393 // TContainer const & container) 394 // { 395 // it = begin(container); 396 // } 397 398 template <typename TIterator> 399 inline void 400 goBegin(TIterator & it) 401 { 402 typename Parameter_<typename Container<TIterator>::Type>::Type tmpContainer = container(it); 403 goBegin(it, tmpContainer); 404 } 405 406 // --------------------------------------------------------------------------- 407 // Function goEnd() 408 // --------------------------------------------------------------------------- 409 410 template <typename TIterator, typename TContainer> 411 inline void 412 goEnd(TIterator & it, 413 TContainer & container) 414 { 415 it = end(container); 416 } 417 418 template <typename TIterator, typename TContainer> 419 inline void 420 goEnd(TIterator & it, 421 TContainer const & container) 422 { 423 it = end(container); 424 } 425 426 template <typename TIterator> 427 inline void 428 goEnd(TIterator & it) 429 { 430 goEnd(it, container(it)); 431 } 432 433 // --------------------------------------------------------------------------- 434 // Function goNext() 435 // --------------------------------------------------------------------------- 436 437 template <typename TIterator> 438 inline void 439 goNext(TIterator & it) 440 { 441 ++it; 442 } 443 444 // --------------------------------------------------------------------------- 445 // Function goFurther() 446 // --------------------------------------------------------------------------- 447 448 template <typename TIterator, typename TDiff> 449 inline void 450 goFurther(TIterator & it, 451 TDiff steps) 452 { // return distance type from arbitrary argument 453 it += steps; 454 } 455 456 // --------------------------------------------------------------------------- 457 // Function goPrevious() 458 // --------------------------------------------------------------------------- 459 460 template <typename TIterator> 461 inline void 462 goPrevious(TIterator & it) 463 { 464 --it; 465 } 466 467 // --------------------------------------------------------------------------- 468 // Function difference() 469 // --------------------------------------------------------------------------- 470 471 template <typename TIterator> 472 inline 473 typename Difference<TIterator>::Type 474 difference(TIterator const & begin, 475 TIterator const & end) 476 { 477 return end - begin; 478 } 479 480 // --------------------------------------------------------------------------- 481 // Function goNil() 482 // --------------------------------------------------------------------------- 483 484 template <typename TIterator> 485 inline void 486 goNil(TIterator & me) 487 { 488 me = TIterator(); 489 } 490 491 template <typename TIterator> 492 inline void 493 goNil(TIterator * & me) 494 { 495 me = 0; 496 } 497 498 // --------------------------------------------------------------------------- 499 // Function atNil() 500 // --------------------------------------------------------------------------- 501 502 template <typename TIterator> 503 inline bool 504 atNil(TIterator & me) 505 { 506 return me == TIterator(); 507 } 508 509 template <typename TIterator> 510 inline bool 511 atNil(TIterator * me) 512 { 513 return me == 0; 514 } 515 516 } // namespace seqan 517 518 #endif // #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ITERATOR_INTERFACE_H_ 519