Spec Top Down Iterator
Iterator for virtual trees/tries that can go down and right beginning from the root.

Extends VSTreeIterator
All Extended Iter, VSTreeIterator
All Subcl's TopDownHistoryIterator
All Impl'd IteratorAssociatedTypesConcept
Defined in <seqan/index.h>
Signature template <typename TIndex, typename TSpec> class Iter<TContainer, VSTree< TopDown<TSpec> > >;

Template Parameters

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

Member Function Overview

Member Functions Inherited From Iter

Interface Function Overview

Interface Functions Inherited From VSTreeIterator

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&t;TContainer, TopDown<TSpec> >::Type (which is Iter<TContainer, VSTree<TopDown<TSpec> > >).

If not copy-constructed the TopDownIterator starts in the root node of the virtual tree/trie.

Member Functions Detail

Iter::Iter(index[, vertexDesc]); Iter::Iter(iterator);

Constructor

Parameters

index An index object.
iterator Another TopDown iterator. (copy constructor) Types: TopDown Iterator, TopDownHistory Iterator
vertexDesc The vertex descriptor of a node the iterator should start in. The iterator starts in the root node by default.

If not copy-constructed the TopDownIterator starts in the root node of the virtual tree.

Interface Functions Detail

bool emptyParentEdge(iterator);

Returns true iff the edge label from the iterator node to its parent is empty.

Parameters

iterator An iterator of a string tree. Types: TopDownIterator

Returns

bool true if parentEdgeLength returns 0, otherwise false$.

bool goDown(iterator); bool goDown(iterator, char); bool goDown(iterator, text[, lcp]);

Iterates down one edge or a path in a tree.

Parameters

char iterator goes down the edge beginning with char.
text iterator goes down the path representing text. If text ends within an edge, iterator will point to the child-end of this edge.
lcp A reference of a size type. When goDown returns, lcp contains the length of the longest-common-prefix of text and a path beginning at the iterator node. Types: String, Segment
iterator An iterator of a tree.

Returns

bool true if the edge or path to go down exists, otherwise false.

goDown(iterator) goes down the leftmost edge in the tree, i.e. the edge beginning with the lexicographically smallest character.

Example

The following code shows a simple example how the function goDown is used.

#include <seqan/index.h>

using namespace seqan;

int main()
{
    typedef Index<CharString> TIndex;

    TIndex index("MISSISSIPPI");
    Iterator<TIndex, TopDown<> >::Type it(index);

    goDown(it, "ISSI");
    std::cout << "The string " << representative(it) << " occurs " << range(it).i2 - range(it).i1 <<
    " times in MISSISSIPPI and has " << repLength(it) << " characters." << std::endl;

    // Note that goDown follows the path STARTING with a given text. It only stops at the next node. Therefore the
    // output for the following code is the same as above, even though the search string changed.
    goRoot(it);
    goDown(it, "ISS");

    std::cout << "The string " << representative(it) << " occurs " << range(it).i2 - range(it).i1 <<
    " times in MISSISSIPPI and has " << repLength(it) << " characters." << std::endl;

    return 0;
}
The string ISSI occurs 2 times in MISSISSIPPI and has 4 characters.
The string ISSI occurs 2 times in MISSISSIPPI and has 4 characters.

bool goRight(iterator);

Iterates to the next sibling in a tree.

Parameters

iterator An iterator of a string tree.

Returns

bool true if the iterator could be moved, otherwise false.

TVertexDiscriptor nodeUp(iterator);

Returns the vertex descriptor of the parent node.

Parameters

iterator An iterator of a string tree/trie.

Returns

TVertexDescriptor The vertex descriptor of the parent node. The type is VertexDescriptor of TIndex. If iterator points at the root node, the vertex descriptor of it is returned.

TValue parentEdgeFirstChar(iterator);

Returns the first character of the edge from an iterator node to its parent.

Parameters

iterator An iterator of a string tree.

Returns

TValue A single character of type Value<TIndex>::Type which is identical to Value<Fibre<TIndex, EsaRawText>::Type>::Type.

TEdgeLabel parentEdgeLabel(iterator);

Returns a substring representing the edge from an iterator node to its parent.

Parameters

iterator An iterator of a string tree/trie.

Returns

TEdgeLabel Returns a substring representing the edge from an iterator node to its parent. and its type is the result of the metafunction EdgeLabel of the iterator.

TSize parentEdgeLength(iterator);

Returns the length of the edge from the iterator node to its parent.

Parameters

iterator An iterator of a string tree.

Returns

TSize The returned value is equal to length(parentEdgeLabel(iterator)) and its type is the result of the metafunction Size of the underlying index.

TSize parentRepLength(iterator);

Returns the length of the substring representing the path from root to iterator's parent node.

Parameters

iterator An iterator of a string tree.

Returns

TReturn The length of the sequence returned by representative of the parent node. The result type is the resultof the metafunction Size of the underlying index.