Spec
Top Down History IteratorString tree iterator that can go down, right, and up. Supports depth-
first search.
String tree iterator that can go down, right, and up. Supports depth-
first search.
Extends | TopDownIterator |
---|---|
Implements | ForwardIteratorConcept |
All Extended | Iter, TopDownIterator, VSTreeIterator |
All Impl'd | CopyConstructibleConcept, DefaultConstructibleConcept, EqualityComparableConcept, ForwardIteratorConcept, InputIteratorConcept, IteratorAssociatedTypesConcept |
Defined in | <seqan/index.h> |
Signature |
template <typename TIndex, typename TSpec>
class Iter<TIndex, VSTree<TopDown<ParentLinks<TSpec> > > >;
|
Template Parameters
TSpec |
Specifies the depth-first search mode. Types: DfsOrder |
---|---|
TIndex |
Type of the container that can be iterated. Types: IndexDfi, IndexEsa, IndexWotd, FMIndex, IndexSa |
Member Function Overview
-
Iter::Iter(index);, Iter::Iter(iterator);
Constructor
Member Functions Inherited From Iter
Member Functions Inherited From TopDownIterator
Member Functions Inherited From EqualityComparableConcept
Interface Function Overview
-
bool goUp(iterator);
Iterates up one edge to the parent in a tree/trie. -
bool lca(a, b, result);
Returns the last common ancestor of two tree nodes. -
TSize lcp(a, b);
Returns the length of the longest-common-prefix of two suffix tree nodes. -
TSize nodeDepth(iterator);
Returns the zero-based node depth of the iterator node.
Interface Functions Inherited From TopDownIterator
emptyParentEdge
goDown
goRight
nodeUp
parentEdgeFirstChar
parentEdgeLabel
parentEdgeLength
parentRepLength
Interface Functions Inherited From VSTreeIterator
alignment
assignProperty
atEnd
childrenAreLeaves
countChildren
countOccurrences
getFrequency
getOccurrence
getOccurrences
getOccurrencesBwt
getProperty
goBegin
goNext
goRoot
isLeaf
isLeftMaximal
isPartiallyLeftExtensible
isRightTerminal
isRoot
isUnique
nodeHullPredicate
nodePredicate
property
range
repLength
representative
value
Interface Functions Inherited From InputIteratorConcept
Interface Functions Inherited From IteratorAssociatedTypesConcept
Interface Metafunction Overview
Interface Metafunctions Inherited From Iter
Interface Metafunctions Inherited From VSTreeIterator
Interface Metafunctions Inherited From IteratorAssociatedTypesConcept
Detailed Description
Note:
Instead of using the class Iter directly we recommend to use the result of the metafunction Iterator<TContainer, TopDown<ParentLinks<TSpec> > >::Type (which is Iter<TContainer, VSTree<ParentLinks<TopDown<TSpec> > > >).
If not copy-constructed the TopDownHistoryIterator starts in the root node of the string tree. Depending on the depth-first search mode the root is not the first DFS node. To go to the first DFS node use goBegin.
Example
Member Functions Detail
Iter::Iter(index);
Iter::Iter(iterator);
Constructor
Parameters
index
|
An index object. |
---|---|
iterator
|
Another TopDownHistory iterator. (copy constructor) Types: TopDownHistory Iterator |
If not copy-constructed the TopDownHistoryIterator starts in the root node of the string tree.
Interface Functions Detail
bool goUp(iterator);
Iterates up one edge to the parent in a tree/trie.
Parameters
iterator
|
An iterator of a string tree/trie. |
---|
Returns
bool |
true if the iterator could be moved, otherwise false. |
---|
Example
The following code shows how the function goUp is used.
#include <seqan/index.h> using namespace seqan; int main() { typedef Index<CharString> TIndex; TIndex index("tobeornottobe"); Iterator<TIndex, TopDown<ParentLinks<> > >::Type it(index); do { // Print the letters from the root to the current node std::cout << representative(it) << std::endl; if (!goDown(it) && !goRight(it)) while (goUp(it) && !goRight(it)) ; } while (!isRoot(it)); return 0; }
be beornottobe e eornottobe nottobe o obe obeornottobe ornottobe ottobe rnottobe t tobe tobeornottobe ttobe
bool lca(a, b, result);
Returns the last common ancestor of two tree nodes.
Parameters
a
|
The first node. Types: TopDownHistoryIterator |
---|---|
b
|
The second node. Types: TopDownHistoryIterator |
result
|
A reference to the resulting lca node. Types: TopDownHistoryIterator |
Returns
TReturn |
false if the lca of a and b is the root node, otherwise true. |
---|
TSize lcp(a, b);
Returns the length of the longest-common-prefix of two suffix tree
nodes.
Parameters
a
|
The first node. Types: TopDownHistoryIterator |
---|---|
b
|
The second node. Types: TopDownHistoryIterator |
Returns
TSize |
The lcp-length of a and b. The type of the result is the result of the metafunction Size of the Index of the iterator |
---|
TSize nodeDepth(iterator);
Returns the zero-based node depth of the iterator node.
Parameters
iterator
|
An iterator of a string tree. |
---|
Returns
TSize |
The length of the path from root to iterator node, e.g. 0 is returned for the root node. The type of the result is the result of the metafunction Size of the underlying index. |
---|