Spec Top Down History Iterator
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

Member Functions Inherited From Iter

Member Functions Inherited From TopDownIterator

Member Functions Inherited From EqualityComparableConcept

Interface Function Overview

Interface Functions Inherited From TopDownIterator

Interface Functions Inherited From VSTreeIterator

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

DemoConstraintIterator

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.

Data Races

Thread safety unknown!

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

Data Races

Thread safety unknown!

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.

Data Races

Thread safety unknown!

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

Data Races

Thread safety unknown!

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.

Data Races

Thread safety unknown!