VSTree Iterator

Class Specialization

VSTree Iterator

Abstract iterator for suffix trees.



IteratorAssociatedTypesConcept

Iter

VSTree Iterator

BottomUp Iterator

TopDown Iterator


MaxRepeats Iterator	MultiMems Iterator	Mums Iterator




SuperMaxRepeats Iterator	SuperMaxRepeatsFast Iterator

TopDownHistory Iterator

Iter<TContainer, VSTree<TSpec> >

Include Headers

seqan/index.h

Parameters

TContainer	Type of the container that can be iterated. Metafunctions: Container Types: FMIndex, IndexDfi, IndexEsa, IndexWotd
TSpec	The specialization type.

Remarks

This iterator is a pointer to a node in the suffix tree (given by the enhanced suffix array IndexEsa). Every node can uniquely be mapped to an interval of the suffix array containing all suffixes of the node's subtree. This interval and some extra information constitute the VertexDescriptor returned by the value function of the iterator.

Specialization of

Iter

Implements

IteratorAssociatedTypesConcept

Specializations

BottomUp Iterator	Iterator for an efficient postorder depth-first search in a suffix tree.
TopDown Iterator	Iterator for virtual trees that can go down and right beginning from the root.

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)

Functions

alignment	Returns an alignment of the occurrences of the representative substring in the index text.
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. (Iter)
atEndOfSequence	Returns true if the iterator is at the end of a sequence. (Iter)
begin	Returns an iterator pointing to the root node of the virtual string tree/trie of an index. The only exception are Postorder iterators, where begin returns an iterator pointing to the leftmost node in the tree/trie.
childrenAreLeaves	Test whether iterator points to a node with only leaf-children.
container	Container of an iterator.
countChildren	Count the number of children of a tree node.
countOccurrences	Returns the number of occurrences of representative substring or a q-gram in the index text.
difference	The difference between two iterators. (Iter)
getFrequency	Returns the number of sequences, which contain the representative as a substring.
getOccurrence	Returns an occurrence of the representative substring or a q-gram in the index text.
getOccurrences	Returns all occurrences of the representative substring or a q-gram in the index text.
getOccurrencesBwt	Returns the characters left beside all occurrence of the representative substring in the index text.
getValue	Access to the value. (Iter)
goBegin	Iterates to the first position of a container. (Iter)
goEnd	Iterates to the last position of a container. (Iter)
goFurther	Iterates some steps further. (Iter)
goNext	Iterates to next position. (Iter)
goPrevious	Iterates to pevious position. (Iter)
isLeaf	Test whether a tree iterator points to a leaf.
isLeftMaximal	Test whether the occurrences of an iterator's representative mutually differ in the character left of the hits.
isPartiallyLeftExtensible	Test whether the characters left of the two occurrences of representative are equal.
isRightTerminal	Test whether iterator points to a suffix.
isRoot	Test whether a tree iterator points to the root node.
isUnique	Test whether the representative occurs only once in every sequence.
moveValue	Assigns value to item. (Iter)
nodeHullPredicate	If false this node and its subtree is concealed.
nodePredicate	If false this node will be skipped during the bottom-up traversal.
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.
repLength	Returns the length of the substring representing the path from root to iterator node.
representative	Returns a substring representing the path from root to iterator node.
value	Reference to the value.

Examples

This code shows how an index can be used with iterators to achieve a pre-order tree like traversal in DFS of the text "tobeornottobe". In order to do so a Top-Down History iterator is used.

File "index_iterator.cpp"

1	#include <seqan/index.h>
2
3	using namespace seqan;
4
5	int main ()
6	{
7	typedef Index<CharString> TIndex;
8
9	TIndex index("tobeornottobe");
10	Iterator<TIndex, TopDown<ParentLinks<> > >::Type it(index);
11
12	do {
13	// Print theletters from the root to the current node
14	std::cout << representative(it) << std::endl;
15
16	if (!goDown(it) && !goRight(it))
17	while (goUp(it) && !goRight(it)) ;
18	} while (!isRoot(it));
19
20	return 0;
21	}

be
beornottobe
e
eornottobe
nottobe
o
obe
obeornottobe
ornottobe
ottobe
rnottobe
t
tobe
tobeornottobe
ttobe

SeqAn - Sequence Analysis Library - www.seqan.de