/*!
* @class Shape
*
* @headerfile <seqan/index.h>
*
* @brief Stores hash value and shape for an ungapped or gapped q-gram.
*
* @signature template <typename TValue, typename TSpec> class Shape;
*
* @tparam TSpec The specializing type. Default: @link SimpleShape @endlink, for
* ungapped q-grams.
* @tparam TValue The @link Value @endlink type of the string the shape is
* applied to (e.g. <tt>Dna</tt>).
*
* The @link FiniteOrderedAlphabetConcept#ValueSize @endlink of Shape is the
* ValueSize of TValue which is the alphabet size.
*
* To get the span or the weight of a shape call @link Shape#length @endlink or
* @link Shape#weight @endlink.
*
* @mfn Shape#Value
*
* @brief Returns the value type for a shape.
*
* @signature Value<TShape>::Type;
*
* @tparam TShape The Shape to query for its value type.
*
* @return Type The value type of the shape.
*
* @mfn Shape#Size
*
* @brief Returns the size type for a shape.
*
* @signature Size<TShape>::Type;
*
* @tparam TShape The Shape to query for its size type.
*
* @return Type The size type of the shape.
*
* @mfn Shape#LENGTH
*
* @brief Returns the length (span) of a shape.
*
* @signature LENGTH<TShape>::VALUE;
*
* @tparam TShape The Shape to query for its length (span).
*
* @return VALUE The length (span) of the shape.
*
* @mfn Shape#WEIGHT
*
* @brief Returns the weight (number of 1's) of a shape.
*
* @signature WEIGHT<TShape>::VALUE;
*
* @tparam TShape The Shape to query for its weight (number of 1's).
*
* @return VALUE The weight (number of 1's) of the shape.
*
* @mfn Shape#ValueSize
*
* @brief Returns the type to use for the value size.
*
* @signature ValueSize<TShape>::Type;
*
* @tparam TShape The Shape to query for value size type.
*
* @return Type Type to use for the value size.
*
* @mfn Shape#Host
*
* @brief Returns the host (= value) type to use.
*
* @signature Host<TShape>::Type;
*
* @tparam TShape The Shape to query for host (= value) type.
*
* @return Type Type to use for the host (= value) size.
*
* @fn Shape#value
*
* @headerfile <seqan/index.h>
*
* @brief Returns the current hash value of the Shape.
*
* @signature TValue value(shape);
*
* @param[in] shape The Shape to query for its value.
*
* @return TValue The hash value of the shape.
*
* @fn Shape#length
*
* @brief Returns the number of elements of the shape (span).
*
* @signature TSize length(shape);
*
* @param[in] shape Shape object for which the number of relevant positions is
* determined.
*
* @return TSize The number of elements of the shape (span) (Metafunction: @link
* Shape#Size @endlink).
*
* @fn Shape#weight
*
* @brief Number of relevant positions in a shape.
*
* @signature TSize weight(shape);
*
* @param[in] shape Shape object for which the number of relevant positions is
* determined.
*
* @return TSize Number of relevant positions (Metafunction: @link Shape#Size
* @endlink).
*
* For ungapped shapes the return value is the result of the @link Shape#length
* @endlink function. For gapped shapes this is the number of '1's.
*
* @fn Shape#resize
*
* @brief Resize a shape to a specified span.
*
* @signature TSize resize(shape, length)
*
* @param[in,out] shape Shape object for which the number of relevant positions
* is determined
* @param[in] length The new length (span) of the shape.
*
* @return TSize The new span of type (Metafunction: @link Shape#Size @endlink).
*
* @fn Shape#hash
*
* @brief Computes a (lower) hash value for a shape applied to a sequence.
*
* @signature TValue hash(shape, it[, charsLeft]);
*
* @param[in,out] shape Shape to be used for hashing. Types: @link Shape
* @endlink
* @param[in] it Sequence iterator pointing to the first character of the shape.
* @param[in] charsLeft The distance of <tt>it</tt> to the string end. If
* <tt>charsLeft</tt> is smaller than the shape's span, the
* hash value corresponds to the smallest shape beginning
* with <tt>charsLeft</tt> characters.
*
* @return TValue Hash value of the shape (Metafunction: @link Shape#Value
* @endlink).
*
* @see Shape#hashNext
* @see Shape#hashUpper
* @see Shape#hash2
* @see Shape#unhash
*
* @fn Shape#hashInit
*
* @brief Preprocessing step of a pure @link Shape#hashNext @endlink loop.
*
* @signature void hashInit(shape, it);
*
* @param[in,out] shape Shape to be used for hasing.
* @param[in] it The @link IteratorAssociatedTypesConcept iterator @endlink to
* use for initializing the shape.
*
* Overlapping q-grams can efficiently be hashed by calling @link Shape#hash
* @endlink on the first text position and @link Shape#hashNext @endlink on
* succeeding, adjacent positions. One drawback of this scenario is that for-
* loops cannot start with the first position directly and become more
* complicated. As a remedy, @link Shape#hashInit @endlink was introduced which
* initializes the Shape to be used with @link Shape#hashNext @endlink on the
* first position directly.
*
* @section Example
*
* Two hash loop examples. The first loop uses @link Shape#hash @endlink/@link
* Shape#hashNext @endlink while the second use @link Shape#hashInit
* @endlink/@link Shape#hashNext @endlink and can process all hashes within the
* loop.
*
* @include demos/index/shape_hash_init.cpp
*
* @code{.stdout}
* 0 0 1 4 17 4 18 11 47 63 62 56
* 0 0 1 4 17 4 18 11 47 63 62 56
* @endcode
*
*
* @fn Shape#hashUpper
*
* @brief Computes an upper hash value for a shape applied to a sequence.
*
* @signature TValue hashUpper(shape, it, charsLeft);
*
* @param[in,out] shape Shape to be used for hashing. Types: @link Shape
* @endlink
* @param[in] it Sequence iterator pointing to the first character of the shape.
* @param[in] charsLeft The distance of <tt>it</tt> to the string end.
*
* @return TValue Upper hash value of the shape. The hash value corresponds to
* the maximal @link Shape#hash @endlink value of a shape
* beginning with <tt>min(charsLeft,length(shape))</tt>
* characters + 1 (Metafunction: @link Shape#Value @endlink).
*
* This function in conjunction with @link Shape#hash @endlink is useful to
* search a q-gram index for p-grams with p < q.
*
* @see Shape#hash
*
* @fn Shape#hashNext
*
* @headerfile <seqan/index.h>
*
* @brief Computes the hash value for the adjacent shape.
*
* @signature TValue hashNext(shape, it);
*
* @param[in,out] shape Shape to be used for hashing. Types: @link Shape
* @endlink
* @param[in] it Sequence iterator pointing to the first character of the
* adjacent shape.
*
* @return TValue Hash value of the q-gram (Metafunction: @link Shape#Value
* @endlink).
*
* @link Shape#hash @endlink has to be called before.
*
* @see Shape#hash
*
* @fn Shape#hash2
*
* @brief Computes an unique hash value of a shape applied to a sequence, even
* if the sequence is shorter than the shape span.
*
* @signature TValue hash2(shape, it, charsLeft);
*
* @param[in,out] shape Shape to be used for hashing. Types: @link Shape
* @endlink
* @param[in] it Sequence iterator pointing to the first character of the shape.
* @param[in] charsLeft The distance of <tt>it</tt> to the string end.
*
* @return TValue Hash value of the shape (Metafunction: @link Shape#Value
* @endlink).
*
* @see Shape#hash2Next
* @see Shape#hash2Upper
* @see Shape#unhash
* @see Shape#hash
*
* @fn Shape#hash2Upper
*
* @brief Computes an upper unique hash value of a shape applied to a sequence,
* even if the sequence is shorter than the shape span.
*
* @signature TValue hash2Upper(shape, it, charsLeft);
*
* @param[in] shape Shape to be used for hashing. Types: @link Shape @endlink
* @param[in] it Sequence iterator pointing to the first character of the shape.
* @param[in] charsLeft The distance of <tt>it</tt> to the string end.
*
* @return TValue Upper hash value of the shape. The hash value corresponds to
* the maximal @link Shape#hash2 @endlink value of a shape
* beginning with the <tt>min(charsLeft,length(shape))</tt>
* characters + 1 (Metafunction: @link Shape#Value @endlink).
*
* This function in conjunction with @link Shape#hash2 @endlink is useful to
* search a q-gram index for p-grams with <i>p < q</i>.
*
* @see Shape#hash2
*
* @fn Shape#hash2Next
*
* @headerfile <seqan/index.h>
*
* @brief Computes a unique hash value for the adjacent shape, even if it is
* shorter than q.
*
* @signature TValue hash2Next(shape, it);
*
* @param[in,out] shape Shape to be used for hashing the q-gram. Types: @link
* Shape @endlink
* @param[in,out] it Sequence iterator pointing to the first character of the
* adjacent shape.
*
* @return TValue Hash value of the shape (Metafunction: @link Shape#Value
* @endlink).
*
* @link Shape#hash @endlink has to be called before with <tt>shape</tt> on the
* left adjacent q-gram.
*
* @see Shape#hash2
*
* @fn Shape#unhash
*
* @headerfile <seqan/index.h>
*
* @brief Inverse of the @link Shape#hash @endlink function; for ungapped
* shapes.
*
* @signature void unhash(result, hash, q);
*
* @param[out] result @link String @endlink to write the result to. Types: @link
* String @endlink.
* @param[in] hash The hash value previously computed with @link Shape#hash
* @endlink.
* @param[in] q The <tt>q</tt>-gram length. Types: <tt>unsigned</tt>
*
* @see Shape#hash
* @see Shape#hash2
*
* @fn Shape#stringToShape
*
* @brief Takes a shape given as a string of '1' (relevant position) and '0'
* (irrelevant position) and converts it into a Shape object.
*
* @signature bool stringToShape(shape, bitmap);
*
* @param[in,out] shape Shape object that is manipulated.
* @param[in] bitmap A character string of '1' and '0' representing relevant and
* irrelevant positions (blanks) respectively. This string
* must begin with a '1'. Trailing '0's are ignored. If
* <tt>shape</tt> is a @link SimpleShape @endlink at most one
* contiguous sequences of <tt>1</tt>s is allowed. If
* <tt>shape</tt> is a @link OneGappedShape @endlink at most
* two contiguous sequences of '1's are allowed (@link String
* @endlink of <tt>char</tt>).
*
* @return bool <tt>true</tt> if the conversion was successful.
*
* @see Shape#shapeToString
* @see reverse
*
* @fn Shape#shapeToString
*
* @brief Converts a given shape into a sequence of '1' (relevant position) and
* '0' (irrelevant position).
*
* @signature void shapeToString(bitmap, shape);
*
* @param[in,out] bitmap The resulting sequence object. Types: @link String
* @endlink
* @param[in] shape Shape object. Types: @link Shape @endlink
*
* @see Shape#stringToShape
*/