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_iterator.h,v 1.1 2008/08/25 16:20:01 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_BASIC_ITERATOR_H
22 #define SEQAN_HEADER_BASIC_ITERATOR_H
24 namespace SEQAN_NAMESPACE_MAIN
26 //////////////////////////////////////////////////////////////////////////////
28 //////////////////////////////////////////////////////////////////////////////
32 ..summary:Specifies the kind of an iterator.
33 ..tag.Rooted:Rooted iterator.
35 ....text:This iterator implements some more advanced functions like
36 @Function.container@ and @Function.position@.
37 ....concept:Concept.Rooted Iterator
38 ..tag.Standard:Standard conform iterator.
40 ....text:Note that standard iterators need not to implement all functions
41 that are available for rooted iterators.
42 ....concept:Concept.Iterator
43 ..remarks.text:The default iterator spec is given by @Metafunction.DefaultIteratorSpec@.
44 ..see:Metafunction.DefaultIteratorSpec
45 ..see:Concept.Iterator
49 typedef Tag<TagRooted_> const Rooted;
52 typedef Tag<TagStandard_> const Standard;
55 //////////////////////////////////////////////////////////////////////////////
57 //////////////////////////////////////////////////////////////////////////////
60 .Metafunction.DefaultIteratorSpec:
62 ..summary:Specifies default kind of iterator.
63 ..signature:DefaultIteratorSpec<T>::Type
64 ..param.T:Container type for which the default iterator spec is determined.
65 ...concept:Concept.Container
66 ..returns.param.Type:Iterator spec of $T$.
67 ..see:Metafunction.Iterator
71 struct DefaultIteratorSpec
73 typedef Standard Type;
76 //////////////////////////////////////////////////////////////////////////////
79 .Metafunction.DefaultGetIteratorSpec:
81 ..summary:Specifies default kind of iterator returned by functions.
82 ..signature:DefaultGetIteratorSpec<T>::Type
83 ..param.T:Container type for which the spec is determined.
84 ...concept:Concept.Container
85 ..returns.param.Type:Iterator spec of $T$.
86 ..remarks:This metafunction returns the iterator spec of iterators that are returned by functions like
87 @Function.begin@, @Function.end@, or @Function.iter@.
88 ..see:Metafunction.Iterator
89 ..see:Metafunction.DefaultIteratorSpec
93 struct DefaultGetIteratorSpec
98 //////////////////////////////////////////////////////////////////////////////
101 .Metafunction.Iterator:
102 ..summary:Type of iterator objects that are used to traverse the container.
103 ..signature:Iterator<T, TSpec>::Type
104 ..param.T:Type for which the iterator type is determined.
105 ...concept:Concept.Container
107 ..param.TSpec:Specifies an @Tag.Iterator Spec.iterator spec@.
108 ...default:The default iterator spec is given by @Metafunction.DefaultIteratorSpec@.
109 ..returns.param.Type:Iterator type of $T$.
110 ..remarks.text:Iterators behave like pointers in some respects.
111 For example, you can use $*it$ to access the value object the iterator $it$ points to.
112 But note that $Iterator<T>::Type$ can differ from $T *$, depending on $T$.
113 ..see:Metafunction.Position
116 //____________________________________________________________________________
118 template <typename T, typename TSpec>
119 struct Iterator_Default_Imp;
121 //Iterator_Default_Imp<T, Standard> is implemented in basic_iterator_simple.h
122 //Iterator_Default_Imp<T, Rooted> is implemented in basic_iterator_adaptor.h
124 //____________________________________________________________________________
126 template <typename T, typename TSpec = typename DefaultIteratorSpec<T>::Type>
128 Iterator_Default_Imp<T, TSpec>
133 //////////////////////////////////////////////////////////////////////////////
136 .Metafunction.Container:
137 ..summary:Type of the container given an iterator.
138 ..signature:Container<T>::Type
139 ..param.T:Iterator type.
141 ...concept:Concept.Iterator
142 ..returns.param.Type:The container type to $T$.
145 template <typename T>
152 //////////////////////////////////////////////////////////////////////////////
154 //////////////////////////////////////////////////////////////////////////////
156 //////////////////////////////////////////////////////////////////////////////
158 //////////////////////////////////////////////////////////////////////////////
162 ..signature:Reference value(object)
163 ..param.object:An object that holds a value or an iterator that points to a value.
165 ...concept:Concept.Iterator
168 template <typename T>
169 inline typename Reference<T>::Type
175 template <typename T>
176 inline typename Reference<T const>::Type
184 template <typename T>
192 //////////////////////////////////////////////////////////////////////////////
194 //////////////////////////////////////////////////////////////////////////////
200 ..signature:GetValue getValue(object)
201 ..param.object:An object that holds a value or points to a value.
203 ...concept:Concept.Iterator
204 ..see:Metafunction.GetValue
207 template <typename T>
208 inline typename GetValue<T>::Type
214 template <typename T>
215 inline typename GetValue<T const>::Type
216 getValue(T const & me)
222 template <typename T>
230 //////////////////////////////////////////////////////////////////////////////
232 //////////////////////////////////////////////////////////////////////////////
233 //Nimmt eine Reference und macht daraus einen GetValue
234 //???TODO toGetValue()
236 //////////////////////////////////////////////////////////////////////////////
238 //////////////////////////////////////////////////////////////////////////////
240 .Function.assignValue:
242 ..summary:Assigns value to item.
243 ..signature:assignValue(object, value)
244 ..param.object:An object that holds a value or points to a value.
246 ...concept:Concept.Iterator
247 ..param.value:A value that is assigned to the item $object$ holds or points to.
248 ..remarks.text:This function is similar to @Function.assign@.
249 The difference is, that $assignValue$ just changes a value stored in $object$ or the value $object$ points to,
250 while @Function.assign@ changes the whole object.
251 ..see:Function.assign
254 template <typename T, typename TValue>
257 TValue const & _value)
260 assign(value(me), _value);
263 //const version for iterators as targets
264 template <typename T, typename TValue>
266 assignValue(T const & me,
267 TValue const & _value)
270 assign(value(me), _value);
273 //////////////////////////////////////////////////////////////////////////////
275 //////////////////////////////////////////////////////////////////////////////
280 ..summary:Assigns value to item.
281 ..signature:moveValue(object, value)
282 ..param.object:An object that holds a value or points to a value.
284 ...concept:Concept.Iterator
285 ..param.value:A value that is handed over to the item $object$ holds or points to.
286 ..remarks.text:This function is similar to @Function.move@.
287 The difference is, that $moveValue$ just changes a value stored in $object$ or the value $object$ points to,
288 while @Function.move@ changes the whole object.
290 ..see:Function.assignValue
293 template <typename T, typename TValue>
296 TValue const & _value)
299 move(value(me), _value);
301 //const version for iterators as targets
302 template <typename T, typename TValue>
304 moveValue(T const & me,
305 TValue const & _value)
308 move(value(me), _value);
311 //////////////////////////////////////////////////////////////////////////////
316 ..summary:Container of an iterator.
317 ..signature:Container container(iterator)
318 ..param.iterator:An iterator.
320 ...concept:Concept.Rooted Iterator
321 ..returns:The container that $iterator$ traverses.
322 ...metafunction:Metafunction.Container
325 template <typename T>
326 inline typename Container<T>::Type
333 //////////////////////////////////////////////////////////////////////////////
337 ..summary:Position of an iterator.
339 ..signature:Position position(iterator [, container])
340 ..param.iterator:An iterator.
342 ...concept:Concept.Iterator
343 ..param.container:A container.
344 ...concept:Concept.Container
345 ...remarks:If $iterator$ implements @Concept.Rooted Iterator@, then $container$ is optional.
346 ...remarks:If $container$ is specified, $iterator$ must be a container of $container$.
347 ..returns:The position of the value in the container $iterator$ points to.
348 ...metafunction:Metafunction.Position
351 template <typename T>
352 inline typename Position<T>::Type
359 template <typename TContainer, typename TIterator>
360 inline typename Position<TContainer>::Type
361 position(TIterator const & it,
362 TContainer const & me)
365 return it - begin(me, Standard());
368 //////////////////////////////////////////////////////////////////////////////
371 //////////////////////////////////////////////////////////////////////////////
373 //////////////////////////////////////////////////////////////////////////////
378 ..summary:Determines whether an iterator is at the beginning position.
379 ..signature:bool atBegin(iterator [, container])
380 ..param.iterator:An iterator.
382 ...concept:Concept.Iterator
383 ..param.container:Container of $iterator$. (optional)
384 ...remarks.text:If $iterator$ implements @Concept.Rooted Iterator@ then $container$ is optional otherwise $container$ is required.
385 ..returns:$true$ if $iterator$ points to the fist item of the container, otherwise $false$.
389 //TODO???: Was, wenn der Container leer ist?
391 template <typename T, typename TContainer>
393 atBegin(T const & it, TContainer const & cont)
396 return it == begin(cont, Standard());
399 //____________________________________________________________________________
401 template <typename T>
403 atBegin(T const & it)
406 return atBegin(it, container(it));
411 //////////////////////////////////////////////////////////////////////////////
413 //////////////////////////////////////////////////////////////////////////////
417 ..summary:Determines whether an iterator is at the end position.
418 ..signature:bool atEnd(iterator [, container])
419 ..param.iterator:An iterator.
421 ...concept:Concept.Iterator
422 ..param.container:Container of $iterator$.
423 ...remarks.text:If $iterator$ implements @Concept.Rooted Iterator@ then $container$ is optional.
424 ....text:$container$ is also optional for iterators to @Adaption.char array.char arrays@.
425 ....text:Otherwise, $container$ is required.
426 ..returns:$true$ if $iterator$ points behind the last item of the container, otherwise $false$.
427 ..see:Function.atBegin
431 template <typename T, typename TContainer>
434 TContainer const & cont)
437 return it == end(cont, Standard());
439 template <typename T, typename TContainer>
442 TContainer const & cont)
445 return it == end(cont, Standard());
447 //____________________________________________________________________________
449 template <typename T>
454 return atEnd(it, container(it));
456 template <typename T>
461 return atEnd(it, container(it));
464 //////////////////////////////////////////////////////////////////////////////
466 //////////////////////////////////////////////////////////////////////////////
470 ..summary:Iterates to the first position of a container.
471 ..signature:goBegin(iterator [, container])
472 ..param.iterator:Object that iterates through $container$.
474 ...concept:Concept.Iterator
475 ...text:$iterator$ is set to the position of the first item in $container$.
476 ..param.container:Container of $iterator$.
477 ...remarks.text:If $iterator$ implements @Concept.Rooted Iterator@ then $container$ is optional,
478 otherwise $container$ is required.
479 ..remarks:This function is equivalent to $iterator = begin(container)$.
481 ..see:Function.atBegin
484 template <typename TIterator, typename TContainer>
486 goBegin(TIterator & it,
487 TContainer & container)
490 it = begin(container);
493 template <typename TIterator, typename TContainer>
495 goBegin(TIterator & it,
496 TContainer const & container)
499 it = begin(container);
503 template <typename TIterator>
505 goBegin(TIterator & it)
508 goBegin(it, container(it));
511 //////////////////////////////////////////////////////////////////////////////
513 //////////////////////////////////////////////////////////////////////////////
517 ..summary:Iterates to the last position of a container.
518 ..signature:goEnd(iterator [, container])
519 ..param.iterator:Object that iterates through $container$.
521 ...concept:Concept.Iterator
522 ...text:$iterator$ is set to the position behin the last item in $container$.
523 ..param.container:Container of $iterator$.
524 ...remarks.text:If $iterator$ implements @Concept.Rooted Iterator@ then $container$ is optional,
525 otherwise $container$ is required.
526 ..remarks:This function is equivalent to $iterator = end(container)$.
529 ..see:Function.goBegin
532 template <typename TIterator, typename TContainer>
534 goEnd(TIterator & it,
535 TContainer & container)
540 template <typename TIterator, typename TContainer>
542 goEnd(TIterator & it,
543 TContainer const & container)
549 template <typename TIterator>
551 goEnd(TIterator & it)
554 goEnd(it, container(it));
557 //////////////////////////////////////////////////////////////////////////////
559 //////////////////////////////////////////////////////////////////////////////
563 ..summary:Iterates to next position.
564 ..signature:goNext(iterator)
565 ..param.iterator:An iterator.
567 ...concept:Concept.Iterator
568 ...text:$iterator$ is set to the next position of an iteration through its container.
569 ..remarks:This function is equivalent to $++iterator$.
570 ..see:Function.goBegin
573 template <typename TIterator>
575 goNext(TIterator & it)
581 //////////////////////////////////////////////////////////////////////////////
583 //////////////////////////////////////////////////////////////////////////////
587 ..summary:Iterates some steps further.
588 ..signature:goFurther(iterator, steps)
589 ..param.iterator:An iterator.
591 ...concept:Concept.Iterator
592 ...text:$iterator$ is set $steps$ positions further in the iteration through the container.
593 ..param.steps:Number of steps $iterator$ should be moved further.
594 ...remarks:If $iterator$ supports bidirectional iteration, $steps$ could also be negativ.
595 ..remarks:This function is equivalent to $iterator += steps$ for random access iterators.
596 ..see:Function.goNext
597 ..see:Function.goPrevious
600 template <typename TIterator, typename TDiff> inline
601 void goFurther(TIterator & it, TDiff steps)
602 { // return distance type from arbitrary argument
606 //////////////////////////////////////////////////////////////////////////////
608 //////////////////////////////////////////////////////////////////////////////
610 .Function.goPrevious:
612 ..summary:Iterates to pevious position.
613 ..signature:goPrevious(iterator)
614 ..param.iterator:An iterator.
616 ...concept:Concept.Iterator
617 ...text:$iterator$ is set to the pevious position of an iteration through its container.
618 ..remarks:This function is equivalent to $--iterator$.
619 ..see:Function.goBegin
621 ..see:Function.goNext
623 template <typename TIterator>
625 goPrevious(TIterator & it)
631 //////////////////////////////////////////////////////////////////////////////
633 //////////////////////////////////////////////////////////////////////////////
635 .Function.difference:
637 ..summary:The difference between two iterators.
638 ..signature:difference(begin, end)
639 ..param.begin:Iterator to the first position of a range.
642 ..param.end:Iterator behind the last position of a range.
645 ..returns:Length of the range between $begin$ and $end$.
646 ..remarks:This function is equivalent to $begin - end$.
647 ...text:Usually, $begin$ and $end$ have the same type.
650 ..see:Function.length
653 template <typename TIterator> inline
654 typename Difference<TIterator>::Type difference(
655 TIterator const & begin,
656 TIterator const & end)
657 { // return distance type from arbitrary argument
662 //////////////////////////////////////////////////////////////////////////////
664 //////////////////////////////////////////////////////////////////////////////
670 ..summary:Moves iterator to nil position.
671 ..signature:goNil(iterator)
672 ..param.iterator:The iterator that will be moved.
674 ..remarks:$iterator$ is set to an invalid position, e.g. $NULL$ for pointer types.
678 template <typename TIterator>
680 goNil(TIterator & me)
686 template <typename TIterator>
688 goNil(TIterator * & me)
694 //////////////////////////////////////////////////////////////////////////////
696 //////////////////////////////////////////////////////////////////////////////
702 ..summary:Tests whether iterator is at nil position.
703 ..signature:bool atNil(iterator)
704 ..param.iterator:An iterator.
706 ..returns:$true$ if $iterator$ points to an ivalid position, e.g. $iterator$ is a $NULL$ pointer.
711 template <typename TIterator>
713 atNil(TIterator & me)
716 return me == TIterator();
720 template <typename TIterator>
722 atNil(TIterator * me)
728 //////////////////////////////////////////////////////////////////////////////
730 } //namespace SEQAN_NAMESPACE_MAIN
732 #endif //#ifndef SEQAN_HEADER_...