/*!
* @class VSTreeIterator VSTree Iterator
*
* @extends Iter
*
* @headerfile <seqan/index.h>
*
* @brief Abstract iterator for string trees, where string trees are trees
* constructed from a string.
*
* @signature template <typename TContainer, typename TSpec> class
* Iter<TContainer, VSTree<TSpec> >;
*
* @tparam TSpec The specialization type.
* @tparam TContainer Type of the container that can be iterated. Types: @link
* IndexDfi @endlink, @link IndexEsa @endlink, @link
* IndexWotd @endlink, @link FMIndex @endlink
*
* This iterator is a pointer to a node in the string tree of a given text.
* Depending on the index this can either be a suffix or prefix tree/trie. Every
* node can uniquely be mapped to an interval of suffices or prefixes.
*
* Default virtual string tree iterators depending on the @link Index @endlink
*
* <table border="1"> <tr> <td>IndexSa</td> <td>Virtual suffix trie
* iterator</td> </tr> <tr> <td>IndexEsa</td> <td>Virtual suffix tree
* iterator</td> </tr> <tr> <td>IndexWotd</td> <td>Virtual suffix tree
* iterator</td> </tr> <tr> <td>IndexDfi</td> <td>Virtual suffix tree
* iterator</td> </tr> <tr> <td>FMIndex</td> <td>Virtual prefix trie
* iterator</td> </tr> </table>
*
* @section 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.
*
* @include demos/dox/index/iterator.cpp
*
* @mfn VSTreeIterator#EdgeLabel
*
* @headerfile <seqan/index.h>
*
* @brief Type of a string representing the characters of edges.
*
* @signature EdgeLabel<TSpec>::Type;
*
* @tparam TSpec Tag to specify the object of which the type of the edge labels
* is requested.
*
* @return Type of a string representing the characters of edges.
*
* @fn VSTreeIterator#repLength
*
* @headerfile <seqan/index.h>
*
* @brief Returns the length of the substring representing the path from root to
* <tt>iterator</tt> node.
*
* @signature TSize repLength(iterator);
*
* @param[in] iterator An iterator of a string tree. Types: @link VSTreeIterator
* @endlink
*
* @return TSize The length of the sequence returned by @link
* VSTreeIterator#representative @endlink The return type is the
* result of the metafunction @link Size @endlink of the
* underlying index.
*
* @link DemoMummy @endlink @link DemoSupermaximalRepeats @endlink @link
* DemoMaximalUniqueMatches @endlink
*
* @fn VSTreeIterator#value
*
* @headerfile <seqan/index.h>
*
* @brief Returns a vertex descriptor of the current node.
*
* @signature TDesc value(iterator);
*
* @param[in] iterator An iterator of a string tree. Types: @link VSTreeIterator
* @endlink
*
* @return TDesc An object of type @link StringTreeConcept#VertexDescriptor
* @endlink that uniquely identifies the current node. The vertex
* descriptor can be used to store node specific values in an
* @link PropertyMapConcept @endlink.
*
* @fn VSTreeIterator#assignProperty
*
* @brief Assigns a property to an item in the property map.
*
* @signature void assignProperty(pm, value(iterator), val)
*
* @param[in,out] pm An @link PropertyMapConcept @endlink.
* @param[in] iterator An iterator of a string tree. Types: @link VSTreeIterator
* @endlink
* @param[in] val The new value, where the type of the new value must match the
* value type of the property map.
*
* @fn VSTreeIterator#property
*
* @brief Accesses the property of an item in the property map.
*
* @signature TRef property(pm, value(iterator))
*
* @param[in,out] pm An @link PropertyMapConcept @endlink.
* @param[in] iterator An iterator of a string tree. Types: @link VSTreeIterator
* @endlink
*
* @return TRef Reference to the item in the property map of type @link
* Reference @endlink.
*
* @fn VSTreeIterator#getProperty
*
* @brief Get method for an item's property.
*
* @signature TValue getProperty(pm, value(iterator))
*
* @param[in,out] pm An @link PropertyMapConcept @endlink.
* @param[in] iterator An iterator of a string tree. Types: @link VSTreeIterator
* @endlink
*
* @return TValue Reference to the item in the property map of type @link
* GetValue @endlink.
*
* @fn VSTreeIterator#getOccurrence
*
* @headerfile <seqan/index.h>
*
* @brief Returns an occurrence of the @link VSTreeIterator#representative
* @endlink substring in the index text.
*
* @signature TSAValue getOccurrence(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return TSAValue A position where the @link VSTreeIterator#representative
* @endlink of <tt>iterator</tt> occurs in the text. The return
* type is the result of the metafunction @link SAValue
* @endlink of the index type of the iterator.
*
* @fn VSTreeIterator#countOccurrences
*
* @headerfile <seqan/index.h>
*
* @brief Returns the number of occurrences of @link
* VSTreeIterator#representative @endlink substring in the index text.
*
* @signature TSize countOccurrences(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return TSize The number of positions where the @link
* VSTreeIterator#representative @endlink of <tt>iterator</tt>
* occurs in the text. The return type is the result of the
* metafunction @link Size @endlink of the index type of the
* iterator.
*
* The necessary index tables are built on-demand via @link Index#indexRequire
* @endlink if index is not <tt>const</tt>.
*
* @section Examples
*
* @include demos/dox/index/counting.cpp
*
* The result is as follows:
*
* @include demos/dox/index/counting.cpp.stdout
*
*
*
* @fn VSTreeIterator#range
*
* @headerfile <seqan/index.h>
*
* @brief Returns the suffix array interval borders of occurrences of @link
* VSTreeIterator#representative @endlink substring in the index text.
*
* @signature TPair range(iterator);
*
* @param[in] iterator An iterator of a string tree/trie.
*
* @return TPair All positions where a substring occurs in the text are stored
* in a contiguous range of the suffix array. <tt>range</tt>
* returns begin and end position of this range for occurrences of
* @link VSTreeIterator#representative @endlink. The type is @link
* Pair @endlink<@link Size @endlink< <tt>TIndex<tt> > > with
* TIndex being the index type of the iterator.
*
* The necessary index tables are built on-demand via @link Index#indexRequire
* @endlink if index is not <tt>const</tt>.
*
* @fn VSTreeIterator#getOccurrences
*
* @headerfile <seqan/index.h>
*
* @brief Returns all occurrences of the @link VSTreeIterator#representative
* @endlink substring in the index text.
*
* @signature TInfix getOccurrences(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return TInfix All positions where the @link VSTreeIterator#representative
* @endlink of <tt>iterator</tt> occurs in the text. Type @link
* SegmentableConcept#Infix @endlink<@link Fibre
* @endlink<TIndex, FibreSA>::Type>.
*
* The necessary index tables are built on-demand via @link Index#indexRequire
* @endlink if index is not <tt>const</tt>.
*
* @section Example
*
* @link DemoMummy @endlink @link DemoSupermaximalRepeats @endlink @link
* DemoMaximalUniqueMatches @endlink
*
* @see VSTreeIterator#isUnique
* @see VSTreeIterator#getFrequency
* @see VSTreeIterator#isPartiallyLeftExtensible
* @see VSTreeIterator#isLeftMaximal
* @see orderOccurrences
*
* @fn VSTreeIterator#alignment
*
* @brief Returns an alignment of the occurrences of the @link
* VSTreeIterator#representative @endlink substring in the index text.
*
* @note Internal function.
*
* @signature TAlign alignment(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return TAlign A local alignment corresponding to the seed of the
* <tt>iterator<tt>.
*
* The function @link VSTreeIterator#representative @endlink must uniquely occur
* in every sequence (e.g. in Mums), otherwise the seed returned is one many.
* The return type is a @link Align @endlink object.
*
* @fn VSTreeIterator#getOccurrencesBwt
*
* @headerfile <seqan/index.h>
*
* @brief Returns the characters left beside all occurrence of the @link
* VSTreeIterator#representative @endlink substring in the index text.
*
* @signature TReturn getOccurrencesBwt(iterator);
*
* @param[in] iterator An iterator of a suffix tree.
*
* @return TReturn All positions where the @link VSTreeIterator#representative
* @endlink of <tt>iterator</tt> occurs in the text.
*
* If <tt>iterator</tt>'s container type is <tt>TIndex</tt> the return type is
* <tt>Infix<Fibre<TIndex, EsaBwt>::Type const>::Type</tt>.
*
* @fn VSTreeIterator#representative
*
* @headerfile <seqan/index.h>
*
* @brief Returns a substring representing the path from root to
* <tt>iterator</tt> node.
*
* @signature TInfix representative(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return TInfix Infix<TSting> An @link InfixSegment @endlink of the text
* of an index. The type is <tt>Infix<Fibre<TIndex,
* FibreText>::Type>::Type</tt>.
*
* @section Examples
*
* @link DemoMummy @endlink @link DemoSupermaximalRepeats @endlink @link
* DemoConstraintIterator @endlink @link DemoMaximalRepeats @endlink @link
* DemoMaximalUniqueMatches @endlink
*
* @fn VSTreeIterator#countChildren
*
* @headerfile <seqan/index.h>
*
* @brief Count the number of children of a tree node.
*
* @signature TSize countChildren(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return TSize The number of children of a tree node. The type is the result
* of @link Size @endlink of the index type of the iterator.
*
* @section Examples
*
* @code{.cpp}
* // this code is in seqan/index/index_esa_stree.h
*
* typedef Index< String<char> > TMyIndex;
* TMyIndex myIndex(myString);
*
* Iterator< TMyIndex, TopDown<ParentLinks<PreorderEmptyEdges> > >::Type tdIterator(myIndex);
* Size<TMyIndex>::Type count;
*
* while (!atEnd(tdIterator)) {
* // We print out the representatives of all nodes that have more than 3 children and the number of occurrences.
* count = countChildren(tdIterator);
* if (count >= 3)
* {
* std::cout << "Representative " << representative(tdIterator) << " has " << count << " children and " << countOccurrences(tdIterator) << " Occurrences " << std::endl;
*
* ++tdIterator;
* }
* @endcode
*
*
* @link DemoIndexCountChildren @endlink
*
* @fn VSTreeIterator#nodePredicate
*
* @headerfile <seqan/index.h>
*
* @brief If <tt>false</tt> this node will be skipped during the bottom-up
* traversal.
*
* @signature bool nodePredicate(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return bool Returns whether or not the node will be skipped.
*
* @see DemoConstraintIterator
*
* @fn VSTreeIterator#nodeHullPredicate
*
* @headerfile <seqan/index.h>
*
* @brief If <tt>false</tt> this node and its subtree is concealed.
*
* @signature bool nodeHullPredicate(iterator);
*
* @param[in] iterator An iterator of a string tree.
*
* @return bool Returns whether or not a subtree is concealed.
*
* @link DemoConstraintIterator @endlink
*
* @fn VSTreeIterator#goRoot
*
* @headerfile <seqan/index.h>
*
* @brief Move iterator to the root node.
*
* @signature void goRoot(iterator);
*
* @param[in,out] iterator An iterator of a suffix tree.
*
* @fn VSTreeIterator#goBegin
*
* @headerfile <seqan/index.h>
*
* @brief Iterates to the first position of a container.
*
* @signature void goBegin(iterator);
*
* @param[in,out] iterator Object that iterates through
*
* This function is equivalent to <tt>iterator = begin(container)</tt>.
*
* @see StringTreeConcept#begin
*
* @fn VSTreeIterator#goNext
*
* @brief Go to next tree node.
*
* @signature void goNext(it);
*
* @param[in,out] it VSTreeIterator to advance.
*
* @fn VSTreeIterator#atEnd
*
* @headerfile <seqan/index.h>
*
* @brief Determines whether an virtual string tree iterator is at the end
* position.
*
* @signature bool atEnd(iterator);
*
* @param[in] iterator An iterator.
*
* @return bool <tt>true</tt> if <tt>iterator</tt> points behind the last item
* of the container, otherwise <tt>false</tt>.
*
* @section Examples
*
* The following example shows the usage of the @link VSTreeIterator#atEnd
* @endlink function.
*
* @include demos/dox/index/begin_atEnd_representative.cpp
*
* @fn VSTreeIterator#isRoot
*
* @headerfile <seqan/index.h>
*
* @brief Test whether a tree iterator points to the root node.
*
* @signature bool isRoot(iterator);
*
* @param[in] iterator An iterator of a tree.
*
* @return bool <tt>true</tt> if <tt>iterator</tt> points to the root of the
* tree, otherwise <tt>false</tt>.
*
* @section Example
*
* The following example shows the usage of the @Function.isRoot@ function.
*
* @include demos/dox/index/begin_atEnd_representative_bottomUp.cpp
*
* code{.output} output:AA ATAA A TAA TATAA TA @endcode
*
* @fn VSTreeIterator#isRightTerminal
*
* @headerfile <seqan/index.h>
*
* @brief Test whether iterator points to a suffix.
*
* @signature bool isRightTerminal(iterator);
*
* @param[in] iterator An iterator of a suffix tree.
*
* @return bool <tt>true</tt> if <tt>iterator</tt> points to the node
* representing a suffix, otherwise <tt>false</tt>.
*
* Every leaf is also a right terminal (see @link VSTreeIterator#isLeaf
* @endlink), but not vice versa.
*
* @fn VSTreeIterator#isLeftMaximal
*
* @headerfile <seqan/index.h>
*
* @brief Test whether the occurrences of an iterator's @link
* VSTreeIterator#representative @endlink mutually differ in the
* character left of the hits.
*
* @signature bool isLeftMaximal(iterator);
*
* @param[in] iterator An iterator of a suffix tree.
*
* @return bool <tt>true</tt> if there are at least two different characters
* left of the occurrences, otherwise <tt>false</tt>.
*
* @see VSTreeIterator#getOccurrences
*
* @fn VSTreeIterator#isPartiallyLeftExtensible
*
* @headerfile <seqan/index.h>
*
* @brief Test whether the characters left of the two occurrences of @link
* VSTreeIterator#representative @endlink are equal.
*
* @signature bool isPartiallyLeftExtensible(iterator);
*
* @param[in] iterator An iterator of a suffix tree.
*
* @return bool <tt>true</tt> if there are at least two different characters
* left of the occurrences, otherwise <tt>false</tt>.
*
* @see VSTreeIterator#getOccurrences
*
* @fn VSTreeIterator#isUnique
*
* @headerfile <seqan/index.h>
*
* @brief Test whether the @link VSTreeIterator#representative @endlink occurs
* only once in every sequence.
*
* @signature bool isUnique(iterator);
*
* @param[in] iterator An iterator of a suffix tree.
*
* @return bool <tt>true</tt> if there are at least two different characters
* left of the occurrences, otherwise <tt>false</tt>.
*
* @see VSTreeIterator#getOccurrences
*
* @fn VSTreeIterator#getFrequency
*
* @headerfile <seqan/index.h>
*
* @brief Returns the number of sequences, which contain the @link
* VSTreeIterator#representative @endlink as a substring.
*
* @signature int getFrequency(iterator);
*
* @param[in] iterator An iterator of a suffix tree. Types: @link VSTreeIterator
* @endlink
*
* @return int The number of different sequences containing the @link
* VSTreeIterator#representative @endlink.
*
* @section Example
*
* The following code how @link VSTreeIterator#getFrequency @endlink is used.
* Note that the result of alternative 1 and 2 is the same, however alternative
* one copies a string which requires more memory.
*
* @include demos/dox/index/getOccurrences_getFrequency_range_getFibre.cpp
*
* @code{.output}
* SSI occurs in 2 sequences.
* Hit in sequence 0 at position 5
* Hit in sequence 1 at position 4
* Hit in sequence 0 at position 2
* ----------------------------
* Hit in sequence 0 at position 5
* Hit in sequence 1 at position 4
* Hit in sequence 0 at position 2
* @endcode
*
*
* @see VSTreeIterator#getOccurrences
*
* @fn VSTreeIterator#childrenAreLeaves
*
* @headerfile <seqan/index.h>
*
* @brief Test whether iterator points to a node with only leaf-children.
*
* @signature bool childrenAreLeaves(iterator);
*
* @param[in] iterator An iterator of a suffix tree.
*
* @return bool <tt>true</tt> if <tt>iterator</tt> points to an inner node of
* the tree, whose children are leaves. Otherwise it is
* <tt>false</tt>.
*
* @fn VSTreeIterator#isLeaf
*
* @headerfile <seqan/index.h>
*
* @brief Test whether a tree iterator points to a leaf.
*
* @signature bool isLeaf(iterator);
*
* @param[in] iterator An iterator of a tree.
*
* @return bool <tt>true</tt> if <tt>iterator</tt> points to a leaf of the tree,
* otherwise <tt>false</tt>.
*
* @link DemoIndexCountChildren @endlink
*/