TopDownHistory Iterator

Class Specialization

String tree iterator that can go down, right, and up. Supports depth-first search.



IteratorAssociatedTypesConcept

Iter

VSTree Iterator

ForwardIteratorConcept

TopDown Iterator

TopDownHistory Iterator

Iterator<TContainer, TopDown< ParentLinks<TSpec> > >::Type

Iter<TContainer, VSTree< TopDown< ParentLinks<TSpec> > > >

Include Headers

seqan/index.h

Parameters

TContainer	Type of the container that can be iterated. Metafunctions: Container Types: IndexDfi, IndexEsa, IndexWotd
TSpec	The specialization type. Specifies the depth-first search mode. Types: Postorder, PostorderEmptyEdges, Preorder, PreorderEmptyEdges

Remarks

If not copy-constructed the TopDownHistory Iterator 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.

Note that the virtual tree can either be a virtual suffix tree or a virtual prefix tree. The suffix tree is shown in Figure 1 and is implemented with the IndexDfi, IndexEsa and IndexWotd. In contrast the FMIndex implements a prefix trie shown in Figure 2.

Specialization of

TopDown Iterator

Implements

ForwardIteratorConcept, IteratorAssociatedTypesConcept

Metafunctions

Container	Type of the container given an iterator. (Iter)
Difference	Type of an object that stores the difference between two iterators. (Iter)
GetValue	Type for reading values. (Iter)
Iterator	Type of iterator objects that are used to traverse the container. (Iter)
Position	Type of an object that represents a position in a container. (Iter)
Reference	Reference type. (Iter)
Spec	The spec of a class. (Iter)
Value	Type of the items in the container or behind an iterator. (Iter)

Member Functions

Iterator

Constructor (TopDown Iterator)

Functions

alignment	Returns an alignment of the occurrences of the representative substring in the index text. (VSTree Iterator)
assignValue	Assigns value to item. (Iter)
atBegin	Determines whether an iterator is at the beginning position. (Iter)
atEnd	Determines whether an iterator is at the end position.
atEndOfSequence	Returns true if the iterator is at the end of a sequence. (Iter)
childrenAreLeaves	Test whether iterator points to a node with only leaf-children. (VSTree Iterator)
container	Container of an iterator. (VSTree Iterator)
countChildren	Count the number of children of a tree node. (VSTree Iterator)
countOccurrences	Returns the number of occurrences of representative substring or a q-gram in the index text. (VSTree Iterator)
difference	The difference between two iterators. (Iter)
emptyParentEdge	Returns true iff the edge label from the iterator node to its parent is empty. (TopDown Iterator)
getFrequency	Returns the number of sequences, which contain the representative as a substring. (VSTree Iterator)
getOccurrence	Returns an occurrence of the representative substring or a q-gram in the index text. (VSTree Iterator)
getOccurrences	Returns all occurrences of the representative substring or a q-gram in the index text. (VSTree Iterator)
getOccurrencesBwt	Returns the characters left beside all occurrence of the representative substring in the index text. (VSTree Iterator)
getValue	Access to the value. (Iter)
goBegin	Iterates to the first position of a container.
goDown	Iterates down one edge or a path in a tree. (TopDown Iterator)
goEnd	Iterates to the last position of a container.
goFurther	Iterates some steps further. (Iter)
goNext	Iterates to next position.
goPrevious	Iterates to pevious position. (Iter)
goRight	Iterates to the next sibling in a tree. (TopDown Iterator)
goRoot	Move iterator to the root node. (TopDown Iterator)
goUp	Iterates up one edge to the parent in a tree.
isLeaf	Test whether a tree iterator points to a leaf. (VSTree Iterator)
isLeftMaximal	Test whether the occurrences of an iterator's representative mutually differ in the character left of the hits. (VSTree Iterator)
isPartiallyLeftExtensible	Test whether the characters left of the two occurrences of representative are equal. (VSTree Iterator)
isRightTerminal	Test whether iterator points to a suffix. (VSTree Iterator)
isRoot	Test whether a tree iterator points to the root node. (VSTree Iterator)
isUnique	Test whether the representative occurs only once in every sequence. (VSTree Iterator)
lca	Returns the last common ancestor of two tree nodes.
lcp	Returns the length of the longest-common-prefix of two suffix tree nodes.
moveValue	Assigns value to item. (Iter)
nodeDepth	Returns the zero-based node depth of the iterator node.
nodeHullPredicate	If false this node and its subtree is concealed. (VSTree Iterator)
nodePredicate	If false this node will be skipped during the bottom-up traversal. (VSTree Iterator)
nodeUp	Returns the vertex descriptor of the parent node. (TopDown Iterator)
parentEdgeFirstChar	Returns the first character of the edge from an iterator node to its parent. (TopDown Iterator)
parentEdgeLabel	Returns a substring representing the edge from an iterator node to its parent. (TopDown Iterator)
parentEdgeLength	Returns the length of the edge from the iterator node to its parent. (TopDown Iterator)
parentRepLength	Returns the length of the substring representing the path from root to iterator's parent node. (TopDown Iterator)
position	Position of an iterator. (Iter)
range	Returns the suffix array interval borders of occurrences of representative substring or a q-gram in the index text. (VSTree Iterator)
repLength	Returns the length of the substring representing the path from root to iterator node. (VSTree Iterator)
representative	Returns a substring representing the path from root to iterator node. (VSTree Iterator)
value	Reference to the value. (VSTree Iterator)

Example Programs

Constraint Iterator

SeqAn - Sequence Analysis Library - www.seqan.de