seqan-dev 1.3.1-1 / usr / include / seqan / index / index_wotd.h

// ==========================================================================
//                 SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2010, Knut Reinert, FU Berlin
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//     * Redistributions of source code must retain the above copyright
//       notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above copyright
//       notice, this list of conditions and the following disclaimer in the
//       documentation and/or other materials provided with the distribution.
//     * Neither the name of Knut Reinert or the FU Berlin nor the names of
//       its contributors may be used to endorse or promote products derived
//       from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.
//
// ==========================================================================
// Author: David Weese <david.weese@fu-berlin.de>
// ==========================================================================

#ifndef SEQAN_HEADER_INDEX_WOTD_H
#define SEQAN_HEADER_INDEX_WOTD_H

namespace SEQAN_NAMESPACE_MAIN
{


//////////////////////////////////////////////////////////////////////////////
// wotd tree index fibres

/**
.Tag.WOTD Index Fibres
..summary:Tag to select a specific fibre (e.g. table, object, ...) of an @Spec.IndexWotd@ index.
..remarks:These tags can be used to get @Metafunction.Fibre.Fibres@ of an WOTD based @Spec.IndexWotd@.
..remarks:TODO(holtgrew): Ask David.
..cat:Index

..tag.WotdText:The original text the index should be based on.
...remarks:TODO(holtgrew): Ask David.

..tag.WotdRawText:The raw text the index is really based on.
...remarks:TODO(holtgrew): Ask David.

..tag.WotdSA:The suffix array.
...remarks:TODO(holtgrew): Ask David.

..tag.WotdRawSA:The raw suffix array.
...remarks:TODO(holtgrew): Ask David.

..tag.WotdDir:The child table.
...remarks:TODO(holtgrew): Ask David.

..see:Metafunction.Fibre
..see:Function.getFibre
..see:Spec.IndexWotd
..include:seqan/index.h
*/
	typedef FibreText		WotdText;
	typedef FibreRawText	WotdRawText;
	typedef FibreSA		WotdSA;
	typedef FibreRawSA		WotdRawSA;
	typedef FibreDir		WotdDir;

///.Spec.VSTree Iterator.param.TContainer.type:Spec.IndexWotd
///.Spec.TopDown Iterator.param.TContainer.type:Spec.IndexWotd
///.Spec.TopDownHistory Iterator.param.TContainer.type:Spec.IndexWotd

//////////////////////////////////////////////////////////////////////////////
// wotd tree index

/**
.Spec.IndexWotd:
..summary:An index based on a lazy suffix tree (see Giegerich et al., "Efficient implementation of lazy suffix trees").
..cat:Index
..general:Class.Index
..signature:Index<TText, IndexWotd<> >
..param.TText:The text type.
...type:Class.String
..remarks:The fibres (see @Class.Index@ and @Metafunction.Fibre@) of this index are a partially sorted suffix array (see @Tag.WOTD Index Fibres.WotdSA@) and the wotd tree (see @Tag.WOTD Index Fibres.WotdDir@).
..include:seqan/index.h
*/

	struct WotdOriginal_;
	typedef Tag<WotdOriginal_> const WotdOriginal;

	template < typename TSpec = void >
	struct IndexWotd {};

/*
	template < typename TObject, typename TSpec >
	struct Fibre< Index<TObject, IndexWotd<TSpec> >, FibreDir> 
	{
		typedef Index<TObject, IndexWotd<TSpec> > TIndex;
		typedef String< 
			typename typename Size<TIndex>::Type,
			Alloc<>
		> Type;
	};
*/
	
	template < typename TObject, typename TSpec >
	class Index<TObject, IndexWotd<TSpec> > {
	public:
		typedef typename Fibre<Index, WotdText>::Type		TText;
		typedef typename Fibre<Index, WotdSA>::Type		TSA;
		typedef typename Fibre<Index, WotdDir>::Type		TDir;

		typedef typename Value<Index>::Type					TValue;
		typedef typename Size<TText>::Type					TSize;
		typedef String<TSize, Alloc<> >						TCounter;
		typedef String<typename Value<TSA>::Type, Alloc<> >	TTempSA;
		typedef typename Cargo<Index>::Type					TCargo;

		// 1st word flags
		static TSize const LEAF          = (TSize)1 << (BitsPerValue<TSize>::VALUE - 1); // this node is a leaf
		static TSize const LAST_CHILD    = (TSize)1 << (BitsPerValue<TSize>::VALUE - 2); // this node is the last child
		// 2nd word flag
		static TSize const UNEVALUATED   = (TSize)1 << (BitsPerValue<TSize>::VALUE - 1); // this node is partially evalutated and has no evaluated children
		static TSize const SENTINELS     = (TSize)1 << (BitsPerValue<TSize>::VALUE - 2); // the children of this node have solely $-edges

		static TSize const BITMASK0      = ~(LEAF | LAST_CHILD);
		static TSize const BITMASK1      = ~(UNEVALUATED | SENTINELS);


		Holder<TText>	text;	// underlying text
		TSA				sa;		// suffix array sorted by the first q chars
		TDir			dir;	// bucket directory
		TCargo			cargo;	// user-defined cargo


		TTempSA			tempSA;
		TCounter		tempOcc;
		TCounter		tempBound;

		TSize			sentinelOcc;
		TSize			sentinelBound;
		bool			interSentinelNodes;	// should virtually one (true) $-sign or many (false) $_i-signs be appended to the strings in text 

		Index():
			interSentinelNodes(false) {}

		Index(Index &other):
			text(other.text),
			sa(other.sa),
			dir(other.dir),
			cargo(other.cargo),
			tempSA(other.tempSA),
			tempBound(other.tempBound),
			sentinelOcc(other.sentinelOcc),
			sentinelBound(other.sentinelBound),
			interSentinelNodes(other.interSentinelNodes) {}

		Index(Index const &other):
			text(other.text),
			sa(other.sa),
			dir(other.dir),
			cargo(other.cargo),
			tempSA(other.tempSA),
			tempBound(other.tempBound),
			sentinelOcc(other.sentinelOcc),
			sentinelBound(other.sentinelBound),
			interSentinelNodes(other.interSentinelNodes) {}

		template <typename TText_>
		Index(TText_ &_text):
			text(_text),
			interSentinelNodes(false) {}

		template <typename TText_>
		Index(TText_ const &_text):
			text(_text),
			interSentinelNodes(false) {}
	};
/*
    template < typename TText, typename TSpec >
    struct Value< Index<TText, IndexWotd<TSpec> > > {
		typedef typename Value< typename Fibre< Index<TText, IndexWotd<TSpec> >, WotdRawText >::Type >::Type Type;
    };

	template < typename TText, typename TSpec >
    struct Size< Index<TText, IndexWotd<TSpec> > > {
		typedef typename Size< typename Fibre< Index<TText, IndexWotd<TSpec> >, WotdRawText >::Type >::Type Type;
    };
*/


//////////////////////////////////////////////////////////////////////////////
// default fibre creators

	template < typename TText, typename TSpec >
	struct DefaultIndexCreator<Index<TText, IndexWotd<TSpec> >, FibreDir> {
        typedef Default Type;
    };

	template < typename TText, typename TSSetSpec, typename TSpec >
	struct DefaultIndexCreator<Index<StringSet<TText, TSSetSpec>, IndexWotd<TSpec> >, FibreDir> {
        typedef Default Type;
    };

//////////////////////////////////////////////////////////////////////////////
// default finder

	template < typename TText, typename TSpec >
	struct DefaultFinder< Index<TText, IndexWotd<TSpec> > > {
        typedef FinderSTree Type;	// standard suffix array finder is mlr-heuristic
    };

//////////////////////////////////////////////////////////////////////////////


	template <typename TSize>
	struct VertexWotdOriginal_ {
		TSize		node;			// position of current node entry in directory
		TSize		parentRepLen;	// representative length of parent node
		TSize		edgeLen;		// length of edge above current node

		VertexWotdOriginal_() {}
		VertexWotdOriginal_(MinimalCtor):
			parentRepLen(0),
			edgeLen(0) 
		{
			_setSizeInval(node);
		}
	};

	template <typename TSize>
	struct VertexWotdModified_ {
		TSize		node;			// position of current node entry in directory
		TSize		parentRepLen;	// representative length of parent node
		TSize		edgeLen;		// length of edge above current node
		Pair<TSize> range;			// current SA interval of hits
		TSize		parentRight;	// right boundary of parent node's range (allows to go right)

		VertexWotdModified_() {}
		VertexWotdModified_(MinimalCtor):
			node(0),
			parentRepLen(0),
			edgeLen(0),
			range(0,0),
			parentRight(0) {}
		VertexWotdModified_(Pair<TSize> const &otherRange, TSize otherParentRight):
			node(0),
			parentRepLen(0),
			edgeLen(0),
			range(otherRange),
			parentRight(otherParentRight) {}
	};

//////////////////////////////////////////////////////////////////////////////
///.Metafunction.VertexDescriptor.param.T.type:Spec.IndexWotd

	template < typename TText >
	struct VertexDescriptor< Index<TText, IndexWotd<WotdOriginal> > > {
		typedef typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type TSize;
		typedef VertexWotdOriginal_<TSize> Type;
	};

	template < typename TText, typename TSpec >
	struct VertexDescriptor< Index<TText, IndexWotd<TSpec> > > {
		typedef typename Size< Index<TText, IndexWotd<TSpec> > >::Type TSize;
		typedef VertexWotdModified_<TSize> Type;
	};

	template < typename TText, typename TSpec >
	void _indexRequireTopDownIteration(Index<TText, IndexWotd<TSpec> > &index) 
	{
		indexRequire(index, WotdDir());
	}

//////////////////////////////////////////////////////////////////////////////
// history stack functions

	template <typename TSize>
	struct HistoryStackWotdOriginal_
	{
		TSize		node;		// position of current node entry in directory
		TSize		edgeLen;	// length of edge above current node
	};

	template <typename TSize>
	struct HistoryStackWotdModified_
	{
		TSize		node;		// position of current node entry in directory
		TSize		edgeLen;	// length of edge above current node
		Pair<TSize> range;		// current SA interval of hits
	};

	template < typename TText, typename TSpec >
	struct HistoryStackEntry_< Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown< ParentLinks<TSpec> > > > > 
	{
		typedef Index<TText, IndexWotd<WotdOriginal> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;
		typedef HistoryStackWotdOriginal_<TSize>		Type;
	};

	template < typename TText, typename TIndexSpec, typename TSpec >
	struct HistoryStackEntry_< Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown< ParentLinks<TSpec> > > > >
	{
		typedef Index<TText, IndexWotd<TIndexSpec> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;
		typedef HistoryStackWotdModified_<TSize>		Type;
	};


	template < typename TText, typename TIndexSpec, typename TSpec >
	inline void 
	_historyPush(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown<TSpec> > > &it) 
	{
		it._parentDesc = value(it);
		value(it).parentRepLen += parentEdgeLength(it);
		value(it).parentRight = value(it).range.i2;
	}

	template < typename TText, typename TSpec >
	inline void 
	_historyPush(Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown< ParentLinks<TSpec> > > > &it) 
	{
		typedef typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type TSize;
		TSize edgeLen = parentEdgeLength(it);
		HistoryStackWotdOriginal_<TSize> entry = { value(it).node, edgeLen };
		push(it.history, entry);
		value(it).parentRepLen += edgeLen;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline void 
	_historyPush(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown< ParentLinks<TSpec> > > > &it) 
	{
		typedef typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type TSize;
		TSize edgeLen = parentEdgeLength(it);
		HistoryStackWotdModified_<TSize> entry = { value(it).node, edgeLen, value(it).range };
		push(it.history, entry);
		value(it).parentRepLen += edgeLen;
		value(it).parentRight = value(it).range.i2;
	}

//////////////////////////////////////////////////////////////////////////////
///.Function.resizeVertexMap.type:Spec.IndexWotd

	template < typename TText, typename TIndexSpec, typename TPropertyMap >
	inline void
	resizeVertexMap(
		Index<TText, IndexWotd<TIndexSpec> > const& index,
		TPropertyMap & pm)
	{
		resize(pm, length(indexDir(index)), Generous());
	}

/* // different interface compared to resizeVertexMap(graph, ...)
	template < typename TText, typename TIndexSpec, typename TPropertyMap, typename TProperty >
	inline void
	resizeVertexMap(
		Index<TText, IndexWotd<TIndexSpec> > const& index,
		TPropertyMap & pm,
		TProperty const & prop)
	{
		resize(pm, length(indexDir(index)), prop, Generous());
	}
*/
	template < typename TSize >
	inline typename Id< VertexWotdOriginal_<TSize> const >::Type
	_getId(VertexWotdOriginal_<TSize> const &desc) 
	{
		return desc.node;
	}

	template < typename TSize >
	inline typename Id< VertexWotdOriginal_<TSize> >::Type
	_getId(VertexWotdOriginal_<TSize> &desc) 
	{
		return _getId(const_cast<VertexWotdOriginal_<TSize> const &>(desc));
	}

	template < typename TSize >
	inline typename Id< VertexWotdModified_<TSize> const >::Type
	_getId(VertexWotdModified_<TSize> const &desc) 
	{
		return desc.node;
	}

	template < typename TSize >
	inline typename Id< VertexWotdModified_<TSize> >::Type
	_getId(VertexWotdModified_<TSize> &desc) 
	{
		return _getId(const_cast<VertexWotdModified_<TSize> const &>(desc));
	}

//////////////////////////////////////////////////////////////////////////////

	template < typename TSize >
	inline bool _isRoot(VertexWotdOriginal_<TSize> const &value) {
		return value.node == 0;
	}

	template < typename TSize >
	inline bool _isRoot(VertexWotdModified_<TSize> const &value) {
		return value.node == 0; 
	}

	// is this a leaf? (including empty $-edges)
	template < typename TText, typename TIndexSpec, typename TSpec, typename TDfsOrder >
	inline bool _isLeaf(
		Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree<TSpec> > const &it,
		VSTreeIteratorTraits<TDfsOrder, False> const)
	{
		typedef Index<TText, IndexWotd<TIndexSpec> > TIndex;
		TIndex const &index = container(it);
		return (dirAt(value(it).node, index) & index.LEAF) != 0;
	}

	// is this a leaf? (excluding empty $-edges)
	template < typename TText, typename TIndexSpec, typename TSpec, typename TDfsOrder >
	inline bool _isLeaf(
		Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree<TSpec> > const &it,
		VSTreeIteratorTraits<TDfsOrder, True> const)
	{
		typedef Index<TText, IndexWotd<TIndexSpec> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex const &index = container(it);
		if (dirAt(value(it).node, index) & index.LEAF)
			return true;

		// ensure node evaluation and test for sentinel child edges?
		return _wotdEvaluate(it) & index.SENTINELS;
	}


	// parentEdgeLength - ORIGINAL VERSION
	template < typename TIndex, typename TSize >
	inline typename Size<TIndex>::Type
	parentEdgeLength(TIndex const &index, VertexWotdOriginal_<TSize> &vDesc)
	{
		TSize edgeLen = vDesc.edgeLen;
		if (edgeLen != (TSize)-1)
			return edgeLen;

		TSize pos = vDesc.node;
		TSize w0 = dirAt(pos, index);
		if (w0 & index.LEAF)
			return vDesc.edgeLen = suffixLength(w0 & index.BITMASK0, index);

		TSize w1 = dirAt(pos + 1, index);
		if (w1 & index.UNEVALUATED)
			return vDesc.edgeLen = _bucketLcp(
				infix(indexSA(index), w0 & index.BITMASK0, w1 & index.BITMASK1),
				indexText(index));
		else
			return vDesc.edgeLen = _getNodeLP(index, w1) - (w0 & index.BITMASK0);
	}

	// parentEdgeLength - MODIFIED VERSION
	template < typename TIndex, typename TSize >
	inline typename Size<TIndex>::Type
	parentEdgeLength(TIndex const &index, VertexWotdModified_<TSize> &vDesc)
	{
		TSize edgeLen = vDesc.edgeLen;
		if (edgeLen != (TSize)-1)
			return edgeLen;

		TSize pos = vDesc.node;
		TSize w0 = dirAt(pos, index);
		if (w0 & index.LEAF)
			return vDesc.edgeLen =
				suffixLength(saAt(vDesc.range.i1, index), index) - vDesc.parentRepLen;

		TSize w1 = dirAt(pos + 1, index);
		if (w1 & index.UNEVALUATED)
			if (_isSizeInval(vDesc.range.i2))
				return vDesc.edgeLen = _bucketLcp(
					suffix(indexSA(index), vDesc.range.i1),
					indexText(index),
					vDesc.parentRepLen) - vDesc.parentRepLen;
			else
				return vDesc.edgeLen = _bucketLcp(
					infix(indexSA(index), vDesc.range.i1, vDesc.range.i2),
					indexText(index),
					vDesc.parentRepLen) - vDesc.parentRepLen;
		else
			return (dirAt(w1 & index.BITMASK1, index) & index.BITMASK0) - vDesc.parentRepLen;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type
	parentEdgeLength(Iter<
		Index<TText, IndexWotd<TIndexSpec> >, 
		VSTree< TopDown<TSpec> > > const &it)
	{
		typedef Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown<TSpec> > > TIter;
		return parentEdgeLength(container(it), value(const_cast<TIter&>(it)));
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type
	parentRepLength(Iter<
		Index<TText, IndexWotd<TIndexSpec> >, 
		VSTree< TopDown<TSpec> > > const &it)
	{
		return value(it).parentRepLen;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type
	parentRepLength(Iter<
		Index<TText, IndexWotd<TIndexSpec> >, 
		VSTree< TopDown< ParentLinks<TSpec> > > > const &it)
	{
		return value(it).parentRepLen;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type
	repLength(Iter<
		Index<TText, IndexWotd<TIndexSpec> >, 
		VSTree< TopDown<TSpec> > > const &it) 
	{
		return parentRepLength(it) + parentEdgeLength(it);
	}


	// parentEdgeLabel - ORIGINAL VERSION (doesn't work if TText is a StringSet)
	template < typename TText, typename TSpec >
	inline typename Infix< typename Fibre<Index<TText, IndexWotd<WotdOriginal> >, EsaText>::Type const >::Type 
	parentEdgeLabel(Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown<TSpec> > > const &it) 
	{
		typedef Index<TText, IndexWotd<WotdOriginal> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex const &index = container(it);

		if (isRoot(it))
			return infix(indexText(index), 0, 0);
		else {
			TSize occ = _getNodeLP(index, value(it).node);
			return infix(indexText(index), occ, occ + parentEdgeLength(it));
		}
	}

	// getOccurrence - ORIGINAL VERSION
	template < typename TText, typename TSpec >
	inline typename SAValue<Index<TText, IndexWotd<WotdOriginal> > >::Type 
	getOccurrence(Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree<TSpec> > const &it) {
		return _getNodeLP(container(it), value(it).node) - value(it).parentRepLen;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline bool
	emptyParentEdge(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree<TopDown<TSpec> > > const &it) 
	{
		typedef Index<TText, IndexWotd<TIndexSpec> > TIndex;

		TIndex const &index = container(it);
		typename SAValue<TIndex>::Type pos = getOccurrence(it);
		return getSeqOffset(pos, stringSetLimits(index)) + value(it).parentRepLen
			== sequenceLength(getSeqNo(pos, stringSetLimits(index)), index);
	}

	// to avoid ambiguity
	template < typename TText, typename TIndexSpec, typename TSpec >
	inline bool
	emptyParentEdge(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree<TopDown<ParentLinks<TSpec> > > > const &it) 
	{
		typedef Index<TText, IndexWotd<TIndexSpec> > TIndex;

		TIndex const &index = container(it);
		typename SAValue<TIndex>::Type pos = getOccurrence(it);
		return getSeqOffset(pos, stringSetLimits(index)) + value(it).parentRepLen
			== sequenceLength(getSeqNo(pos, stringSetLimits(index)), index);
	}



	template < typename TText, typename TSpec >
	inline void 
	goRoot(Iter<
		Index<TText, IndexWotd<WotdOriginal> >, 
		VSTree<TSpec> > &it) 
	{
		_historyClear(it);
		value(it).node = 0;			// start in root node (first entry in dir)
		value(it).parentRepLen = 0;	// parent prefix length is 0
		value(it).edgeLen = 0;		// edge length is 0
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline void 
	goRoot(Iter<
		Index<TText, IndexWotd<TIndexSpec> >, 
		VSTree<TSpec> > &it) 
	{
		_historyClear(it);
		value(it).range.i1 = 0;		// start in root node with range (0,infty)
		_setSizeInval(value(it).range.i2);	// infty is equivalent to length(index) and faster to compare
		value(it).node = 0;			// start in root node (first entry in dir)
		value(it).parentRepLen = 0;	// parent prefix length is 0
		value(it).edgeLen = 0;		// edge length is 0
	}

	template < typename TText, typename TSpec >
	inline bool atEnd(Iter<Index<TText, IndexWotd<WotdOriginal> >, VSTree<TSpec> > &it) 
	{
		return _isSizeInval(value(it).node);
	}

	template < typename TText, typename TSpec >
	inline bool atEnd(Iter<Index<TText, IndexWotd<WotdOriginal> >, VSTree<TSpec> > const &it) 
	{
		return _isSizeInval(value(it).node);
	}

		
	// adjust iterator's right border of SA range
	template < typename TText, typename TSpec >
	inline void
	_adjustRightBorder(
		Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown<TSpec> > > &) 
	{}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline void
	_adjustRightBorder(
		Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown<TSpec> > > &it)
	{
		typedef Index<TText, IndexWotd<TIndexSpec> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex	const &index = container(it);
		TSize	pos = value(it).node;

		TSize w0 = dirAt(pos, index);
		if (w0 & index.LEAF)
			value(it).range.i2 = value(it).range.i1 + 1;
		else
			if (w0 & index.LAST_CHILD)
				value(it).range.i2 = value(it).parentRight;
			else {
				w0 = dirAt(pos + 2, index);
				value(it).range.i2 = w0 & index.BITMASK0;
			}
	}

	// go down the leftmost edge (including empty $-edges)
	template < typename TText, typename TSpec, typename TDfsOrder, typename THideEmptyEdges >
	inline bool 
	_goDown(
		Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown<TSpec> > > &it,
		VSTreeIteratorTraits<TDfsOrder, THideEmptyEdges> const)
	{
		typedef Index<TText, IndexWotd<WotdOriginal> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		if (_isLeaf(it, EmptyEdges())) return false;

		TIndex &index = container(it);
		_historyPush(it);

		// ensure node evaluation
		TSize childNode = _wotdEvaluate(it);

		if (THideEmptyEdges::VALUE && (childNode & index.SENTINELS) != 0)
			return false;

		// go down
		value(it).node = childNode & index.BITMASK1;
		value(it).edgeLen = -1;

		// go right if parent edge is empty 
		// or hull predicate is false
		if ((THideEmptyEdges::VALUE && emptyParentEdge(it)) || !nodeHullPredicate(it))
			if (!goRight(it)) {
				_goUp(it);
				return false;
			}

		return true;
	}

	// go down the leftmost edge (excluding empty $-edges)
	template < typename TText, typename TIndexSpec, typename TSpec, typename TDfsOrder, typename THideEmptyEdges >
	inline bool 
	_goDown(
		Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown<TSpec> > > &it,
		VSTreeIteratorTraits<TDfsOrder, THideEmptyEdges> const)
	{
		typedef Index<TText, IndexWotd<TIndexSpec> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		if (_isLeaf(it, EmptyEdges())) return false;
		TIndex const &index = container(it);

		// ensure node evaluation
		TSize childNode = _wotdEvaluate(it);

		if (THideEmptyEdges::VALUE && (childNode & index.SENTINELS) != 0)
			return false;

		// go down
		_historyPush(it);
		value(it).node = childNode & index.BITMASK1;
		value(it).edgeLen = -1;
		_adjustRightBorder(it);

		// go right if parent edge is empty
		// or hull predicate is false
		if ((THideEmptyEdges::VALUE && emptyParentEdge(it)) || !nodeHullPredicate(it))
			if (!goRight(it)) {
				_goUp(it);
				return false;
			}

		return true;
	}

	// go right to the lexic. next sibling
	template < typename TText, typename TSpec, typename TDfsOrder, typename THideEmptyEdges >
	inline bool 
	_goRight(
		Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown<TSpec> > > &it,
		VSTreeIteratorTraits<TDfsOrder, THideEmptyEdges> const) 
	{
		typedef Index<TText, IndexWotd<WotdOriginal> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex const &index = container(it);

		do {
			TSize w0 = dirAt(value(it).node, index);
			if (w0 & index.LAST_CHILD)
				return false;

			value(it).node += (w0 & index.LEAF)? 1: 2;
			value(it).edgeLen = -1;

			_adjustRightBorder(it);
		} while ((THideEmptyEdges::VALUE && emptyParentEdge(it)) || !nodeHullPredicate(it));
		return true;
	}

	template < typename TText, typename TIndexSpec, typename TSpec, typename TDfsOrder, typename THideEmptyEdges >
	inline bool 
	_goRight(
		Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown<TSpec> > > &it,
		VSTreeIteratorTraits<TDfsOrder, THideEmptyEdges> const) 
	{
		typedef Index<TText, IndexWotd<TIndexSpec> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex const &index = container(it);

		do {
			TSize w0 = dirAt(value(it).node, index);
			if (w0 & index.LAST_CHILD)
				return false;

			value(it).node += (w0 & index.LEAF)? 1: 2;
			value(it).edgeLen = -1;

			value(it).range.i1 = value(it).range.i2;
			_adjustRightBorder(it);
		} while ((THideEmptyEdges::VALUE && emptyParentEdge(it)) || !nodeHullPredicate(it));
		return true;
	}

	// go up one edge (returns false if in root node)
	// can be used at most once, as no history stack is available
	template < typename TText, typename TWotdSpec, typename TSpec >
	inline bool 
	_goUp(Iter< Index<TText, IndexWotd<TWotdSpec> >, VSTree< TopDown<TSpec> > > &it) 
	{
		if (!isRoot(it)) {
			value(it) = it._parentDesc;
			return true;
		}
		return false;
	}

	// go up one edge (returns false if in root node)
	template < typename TText, typename TSpec >
	inline bool 
	_goUp(Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown< ParentLinks<TSpec> > > > &it) 
	{
		typedef typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type TSize;

		if (!empty(it.history)) {
			HistoryStackWotdOriginal_<TSize> const &entry = top(it.history);
			value(it).node = entry.node;
			value(it).parentRepLen -= entry.edgeLen;
			value(it).edgeLen = entry.edgeLen;
			pop(it.history);
			return true;
		}
		return false;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline bool 
	_goUp(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown< ParentLinks<TSpec> > > > &it) 
	{
		typedef typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type TSize;

		if (!empty(it.history)) 
		{
			HistoryStackWotdModified_<TSize> const &entry = top(it.history);
			value(it).node = entry.node;
			value(it).parentRepLen -= entry.edgeLen;
			value(it).edgeLen = entry.edgeLen;
			value(it).range = entry.range;
			pop(it.history);
			if (!empty(it.history))
				value(it).parentRight = top(it.history).range.i2;	// copy right boundary of parent's range
			return true;
		}
		return false;
	}

	// return vertex descriptor of parent's node
	template < typename TText, typename TSpec >
	inline typename VertexDescriptor< Index<TText, IndexWotd<WotdOriginal> > >::Type
	nodeUp(Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown< ParentLinks<TSpec> > > > const &it) 
	{
		typedef Index<TText, IndexWotd<WotdOriginal> > TIndex;
		typedef typename Size<TIndex>::Type TSize;

		if (!empty(it.history))
		{
			HistoryStackWotdModified_<TSize> const &entry = top(it.history);
			typename VertexDescriptor<TIndex>::Type desc;

			desc.node = entry.node;
			desc.parentRepLen = value(it).parentRepLen - entry.edgeLen;
			desc.edgeLen = entry.edgeLen;
			desc.range = entry.range;
			TSize h = length(it.history) - 1;
			if (h != 0) --h;
			desc.parentRight = it.history[h].range.i2;	// copy right boundary of parent's range
			return desc;
		} else
			return value(it);
	}

	// return vertex descriptor of parent's node
	template < typename TText, typename TIndexSpec, typename TSpec >
	inline typename VertexDescriptor< Index<TText, IndexWotd<TIndexSpec> > >::Type
	nodeUp(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown< ParentLinks<TSpec> > > > const &it) 
	{
		typedef Index<TText, IndexWotd<TIndexSpec> > TIndex;
		typedef typename Size<TIndex>::Type TSize;

		if (!empty(it.history))
		{
			HistoryStackWotdModified_<TSize> const &entry = top(it.history);
			typename VertexDescriptor<TIndex>::Type desc;

			desc.node = entry.node;
			desc.parentRepLen = value(it).parentRepLen - entry.edgeLen;
			desc.edgeLen = entry.edgeLen;
			return desc;
		} else
			return value(it);
	}

//////////////////////////////////////////////////////////////////////////////


	// Counting sort - Step 2a: Count characters
	template < typename TBuckets, typename TText >
	inline void
	_wotdCountChars(TBuckets &buckets, TText const &text)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type TTextIterator;

		TTextIterator itText = begin(text, Standard());
		TTextIterator itTextEnd = end(text, Standard());
		for (; itText != itTextEnd; ++itText)
			++buckets[ordValue(*itText)];
	}


	template < typename TBuckets, typename TText, typename TSpec >
	inline void
	_wotdCountChars(TBuckets &buckets, StringSet<TText, TSpec> const &stringSet)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type TTextIterator;

		for(unsigned seqNo = 0; seqNo < length(stringSet); ++seqNo) 
		{
			TText const &text = value(stringSet, seqNo);
			TTextIterator itText = begin(text, Standard());
			TTextIterator itTextEnd = end(text, Standard());
			for (; itText != itTextEnd; ++itText)
				++buckets[ordValue(*itText)];
		}
	}

	// Counting sort - Step 2b: Count the prefixLen'th characters of suffices
	template < typename TBuckets, typename TText, typename TSA, typename TSize >
	inline typename Size<TText>::Type
	_wotdCountCharsWotdOriginal(
		TBuckets &buckets, 
		TText const &text, 
		TSA &sa,
		TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA const, Standard>::Type	TSAIterator;
		typedef typename Size<TText>::Type						TTextSize;

		TTextIterator itText = begin(text, Standard());
		TSAIterator itSA = begin(sa, Standard());
		TSAIterator itSAEnd = end(sa, Standard());

		TTextSize sentinels = 0;
		TTextSize textLength = length(text);
		for (; itSA != itSAEnd; ++itSA) 
		{
			// add prefix on entries in sa
			TTextSize saValue = (*itSA += prefixLen);
			if (textLength > saValue)
				++buckets[ordValue(*(itText + saValue))];
			else
				if (textLength == saValue) ++sentinels;
		}
		return sentinels;
	}

	template < typename TBuckets, typename TText, typename TSA, typename TSize >
	inline typename Size<TText>::Type
	_wotdCountChars(
		TBuckets &buckets, 
		TText const &text, 
		TSA const &sa,
		TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA const, Standard>::Type	TSAIterator;
		typedef typename Size<TText>::Type						TTextSize;

		TTextIterator itText = begin(text, Standard()) + prefixLen;
		TSAIterator itSA = begin(sa, Standard());
		TSAIterator itSAEnd = end(sa, Standard());

		TTextSize sentinels = 0;
		TTextSize textLength = length(text) - prefixLen;
		for (; itSA != itSAEnd; ++itSA) 
		{
			TTextSize saValue = *itSA;
			if (textLength > saValue)
				++buckets[ordValue(*(itText + saValue))];
			else
				if (textLength == saValue) ++sentinels;
		}
		return sentinels;
	}

	template < 
		typename TBuckets, 
		typename TText, 
		typename TSpec, 
		typename TSA, 
		typename TSize 
	>
	inline typename Size<TText>::Type
	_wotdCountChars(
		TBuckets &buckets, 
		StringSet<TText, TSpec> const &stringSet,
		TSA const &sa,
		TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA const, Standard>::Type	TSAIterator;
		typedef typename Size<TText>::Type						TTextSize;

		TTextIterator itText = TTextIterator();
		TSAIterator itSA = begin(sa, Standard());
		TSAIterator itSAEnd = end(sa, Standard());

		TTextSize sentinels = 0;
		TTextSize textLength = 0;
		unsigned lastSeqSeen = -1;
		Pair<unsigned, TTextSize> lPos;
		for (; itSA != itSAEnd; ++itSA) 
		{
			posLocalize(lPos, *itSA, stringSetLimits(stringSet));
			if (lastSeqSeen != getSeqNo(lPos))
			{
				lastSeqSeen = getSeqNo(lPos);

				// shift textBegin and textLength by prefixLen
				textLength = length(stringSet[lastSeqSeen]) - prefixLen;
				itText = begin(stringSet[lastSeqSeen], Standard()) + prefixLen;
			}
			if (textLength > getSeqOffset(lPos))
				++buckets[ordValue(*(itText + getSeqOffset(lPos)))];
			else
				if (textLength == getSeqOffset(lPos)) ++sentinels;
		}
		return sentinels;
	}


//////////////////////////////////////////////////////////////////////////////


	// Counting sort - Step 3: Cumulative sum
	template < typename TBounds, typename TBuckets, typename TSize >
	inline typename Size<TBuckets>::Type
	_wotdCummulativeSum(TBounds &bounds, TBuckets const &buckets, TSize offset)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TBounds, Standard>::Type		TBoundIterator;
		typedef typename Iterator<TBuckets, Standard>::Type		TBucketsIterator;

		TBucketsIterator it = begin(buckets, Standard());
		TBucketsIterator itEnd = end(buckets, Standard());
		TBoundIterator bit = begin(bounds, Standard());

		typename Value<TBounds>::Type	sum = offset;
		typename Size<TBuckets>::Type	requiredSize = 0;
		typename Value<TBuckets>::Type	diff;

		for (; it != itEnd; ++it, ++bit)
			if ((diff = *it) != 0) {
				requiredSize += (diff > 1)? 2: 1;
				*bit = sum;
				sum += diff;
			}

		return requiredSize;
	}

	template < typename TBounds, typename TBuckets >
	inline typename Size<TBuckets>::Type
	_wotdCummulativeSum(TBounds &bounds, TBuckets const &buckets)
	{
		return _wotdCummulativeSum(bounds, buckets, 0);
	}

//////////////////////////////////////////////////////////////////////////////
/**
.Function.createWotdIndex:
..summary:Builds a q-gram index on a sequence. 
..cat:Index
..signature:createWotdIndex(sa, dir, text)
..param.text:The sequence.
..param.sa:The resulting list in which all q-grams are sorted alphabetically.
..param.dir:The resulting array that indicates at which position in index the corresponding q-grams can be found.
..returns:Index contains the sorted list of qgrams. For each possible q-gram pos contains the first position in index that corresponds to this q-gram. 
..include:seqan/index.h
*/

	// single sequence
	template < typename TIndex >
	typename Size<TIndex>::Type
	_sortFirstWotdBucket(TIndex &index)
	{
	SEQAN_CHECKPOINT
		typedef typename Fibre<TIndex, WotdText >::Type		TText;
		typedef typename Fibre<TIndex, WotdSA >::Type			TSA;
		typedef typename TIndex::TCounter						TCounter;

		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA, Standard>::Type			TSAIterator;
		typedef typename Iterator<TCounter, Standard>::Type		TCntIterator;
		typedef typename Size<TText>::Type						TSize;
		
		TText const &text = indexText(index);
		TCounter &occ = index.tempOcc;
		TCounter &bound = index.tempBound;

		// 1. clear counters and copy SA to temporary SA
		arrayFill(begin(occ, Standard()), end(occ, Standard()), 0);

		// 2. count characters
		_wotdCountChars(occ, text);

		// 3. cumulative sum
		TSize requiredSize = _wotdCummulativeSum(bound, occ);

		// 4. fill suffix array
		{
			TSA &sa = indexSA(index);
			TSAIterator saBeg = begin(sa, Standard());
			TCntIterator boundBeg = begin(bound, Standard());

			TTextIterator itText = begin(text, Standard());
			TTextIterator itTextEnd = end(text, Standard());
			for(TSize i = 0; itText != itTextEnd; ++itText, ++i)
				*(saBeg + (*(boundBeg + ordValue(*itText)))++) = i;
		}
		index.sentinelOcc = 0;
		index.sentinelBound = 0;

		return requiredSize;
	}

	// multiple sequences
	template < typename TText, typename TSpec, typename TIndexSpec >
	typename Size< Index<StringSet<TText, TSpec>, TIndexSpec> >::Type
	_sortFirstWotdBucket(Index<StringSet<TText, TSpec>, TIndexSpec> &index)
	{
	SEQAN_CHECKPOINT
		typedef Index<StringSet<TText, TSpec>, TIndexSpec>		TIndex;
		typedef typename Fibre<TIndex, WotdSA >::Type			TSA;
		typedef typename TIndex::TCounter						TCounter;

		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA, Standard>::Type			TSAIterator;
		typedef typename Iterator<TCounter, Standard>::Type		TCntIterator;
		typedef typename Size<TText>::Type						TSize;
		typedef typename Value<TText>::Type						TValue;
		
		StringSet<TText, TSpec> const &stringSet = indexText(index);
		TCounter &occ = index.tempOcc;
		TCounter &bound = index.tempBound;

		// 1. clear counters and copy SA to temporary SA
		arrayFill(begin(occ, Standard()), end(occ, Standard()), 0);

		// 2. count characters
		_wotdCountChars(occ, stringSet);

		// 3. cummulative sum
		TSize requiredSize = _wotdCummulativeSum(bound, occ);

		// 4. fill suffix array
		for(unsigned seqNo = 0; seqNo < length(stringSet); ++seqNo) 
		{
			TSA &sa = indexSA(index);
			TSAIterator saBeg = begin(sa, Standard());
			TCntIterator boundBeg = begin(bound, Standard());

			typename Value<TSA>::Type localPos;
			assignValueI1(localPos, seqNo);
			assignValueI2(localPos, 0);

			TText const &text = value(stringSet, seqNo);
			TTextIterator itText = begin(text, Standard());
			TTextIterator itTextEnd = end(text, Standard());
			for(; itText != itTextEnd; ++itText) 
			{
				*(saBeg + (*(boundBeg + ordValue(*itText)))++) = localPos;
				assignValueI2(localPos, getValueI2(localPos) + 1);
			}
		}
		index.sentinelOcc = 0;
		index.sentinelBound = 0;

		return requiredSize;
	}



	// sort bucket using counting sort
	// (nearly) ORIGINAL VERSION:
	// - brings the bucket with the longest suffix (lpBucket) to front
	// - all other buckets are in lexicographical order
	// - adds prefixLen to all SA entries in SA[left,right)
	template < typename TText, typename TBeginPos, typename TEndPos, typename TSize >
	TSize _sortWotdBucket(
		Index<TText, IndexWotd<WotdOriginal> > &index,
		TBeginPos left, 
		TEndPos right,
		TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef Index<TText, IndexWotd<WotdOriginal> >			TIndex;
		typedef typename Fibre<TIndex, WotdSA >::Type			TSA;
		typedef typename TIndex::TCounter						TCounter;

		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA, Standard>::Type			TSAIterator;
		typedef typename Iterator<TCounter, Standard>::Type		TCntIterator;
		typedef typename Size<TText>::Type						TTextSize;

		TText const &text = indexText(index);
		TCounter const &tempSA = index.tempSA;
		TCounter &occ = index.tempOcc;
		TCounter &bound = index.tempBound;

		// 1. clear counters and copy SA to temporary SA
		arrayFill(begin(occ, Standard()), end(occ, Standard()), 0);

		// 2. count characters
		index.tempSA = infix(indexSA(index), left, right);
		index.sentinelBound = 0;
		index.sentinelOcc =
			_wotdCountCharsWotdOriginal(occ, text, tempSA, prefixLen);

		// 3. cumulative sum
		TSize requiredSize = 0;

		// actually, here sentinelOcc<=1 holds (this is the original wotd)
		if (index.interSentinelNodes) {
			if (index.sentinelOcc != 0)
				requiredSize = (index.sentinelOcc > 1)? 2: 1;	// insert *one* $-edge for all $_i suffices
		} else
			requiredSize = index.sentinelOcc;					// insert each $_i suffix one-by-one

		requiredSize += _wotdCummulativeSum(bound, occ, left + index.sentinelOcc);
		index.sentinelBound = left;

		// 4. fill suffix array
		{
			TSA &sa = indexSA(index);
			TSAIterator saBeg = begin(sa, Standard());
			TCntIterator boundBeg = begin(bound, Standard());

			TTextIterator itText = begin(text, Standard());
			TCntIterator itSA = begin(tempSA, Standard());
			TCntIterator itSAEnd = end(tempSA, Standard());
			TTextSize textLength = length(text);
			for(; itSA != itSAEnd; ++itSA)
			{
				TTextSize saValue = *itSA;
				if (textLength > saValue)
					*(saBeg + (*(boundBeg + ordValue(*(itText + saValue))))++) = saValue;
				else
					if (textLength == saValue)
						*(saBeg + index.sentinelBound++) = saValue;
			}
		}

		// 5. move lpBucket to front and add saOffset to hash directory entries
		{
			TSize lpBucket = ordValue(text[tempSA[0]]);
			if (lpBucket != 0) {
				TSize lpBucketOcc = occ[lpBucket];
				TSize lpBucketBound = bound[lpBucket];

				TCntIterator itOcc = begin(occ, Standard()) + lpBucket;
				TCntIterator itBound = begin(bound, Standard()) + lpBucket;
				TCntIterator itBeg = begin(bound, Standard());
				for(; itBound != itBeg; --itBound, --itOcc) {
					*itOcc = *(itOcc - 1);
					*itBound = *(itBound - 1);
				}
				if (index.sentinelOcc != 0) {
					// bring first bucket before sentinel bucket
					*itOcc = index.sentinelOcc;
					*itBound = index.sentinelBound;
					index.sentinelOcc = lpBucketOcc;
					index.sentinelBound = lpBucketBound;
				} else {
					*itOcc = lpBucketOcc;
					*itBound = lpBucketBound;
				}
			} else
				if (index.sentinelOcc != 0) {
					// bring first bucket before sentinel bucket
					TSize swap = index.sentinelOcc;
					index.sentinelOcc = occ[0];
					occ[0] = swap;
					swap = index.sentinelBound;
					index.sentinelBound = bound[0];
					bound[0] = swap;
				}
		}

		return requiredSize;
	}





	// sort bucket using counting sort
	// MODIFIED VERSION:
	// - all buckets are in lexicographical order
	// - SA[left,right) contains real SA entries (the beginning positions of the suffices)

	// single sequence
	template < typename TIndex, typename TBeginPos, typename TEndPos, typename TSize >
	TSize _sortWotdBucket(
		TIndex &index,
		TBeginPos left, 
		TEndPos right,
		TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef typename Fibre<TIndex, WotdText >::Type		TText;
		typedef typename Fibre<TIndex, WotdSA >::Type			TSA;
		typedef typename TIndex::TCounter						TCounter;

		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA, Standard>::Type			TSAIterator;
		typedef typename Iterator<TCounter, Standard>::Type		TCntIterator;
		typedef typename Size<TText>::Type						TTextSize;

		TText const &text = indexText(index);
		TCounter const &tempSA = index.tempSA;
		TCounter &occ = index.tempOcc;
		TCounter &bound = index.tempBound;

		// 1. clear counters and copy SA to temporary SA
		arrayFill(begin(occ, Standard()), end(occ, Standard()), 0);
		index.tempSA = infix(indexSA(index), left, right);

		// 2. count characters
		index.sentinelBound = 0;
		index.sentinelOcc = _wotdCountChars(occ, text, tempSA, prefixLen);

		// 3. cumulative sum
		TSize requiredSize = 0;
		if (index.interSentinelNodes) {
			if (index.sentinelOcc != 0)
				requiredSize = (index.sentinelOcc > 1)? 2: 1;	// insert *one* $-edge for all $_i suffices
		} else
			requiredSize = index.sentinelOcc;					// insert each $_i suffix one-by-one

		requiredSize += _wotdCummulativeSum(bound, occ, left + index.sentinelOcc);
		index.sentinelBound = left;

		// 4. fill suffix array
		{
			TSA &sa = indexSA(index);
			TSAIterator saBeg = begin(sa, Standard());
			TCntIterator boundBeg = begin(bound, Standard());

			TTextIterator itText = begin(text, Standard()) + prefixLen;
			TCntIterator itSA = begin(tempSA, Standard());
			TCntIterator itSAEnd = end(tempSA, Standard());
			TTextSize textLength = length(text) - prefixLen;
			for(; itSA != itSAEnd; ++itSA)
			{
				TTextSize saValue = *itSA;
				if (textLength > saValue)
					*(saBeg + (*(boundBeg + ordValue(*(itText + saValue))))++) = saValue;
				else
					if (textLength == saValue)
						*(saBeg + index.sentinelBound++) = saValue;
			}
		}

		return requiredSize;
	}

	// multiple sequences
	template < typename TText, typename TSpec, typename TIndexSpec, typename TBeginPos, typename TEndPos, typename TSize >
	TSize _sortWotdBucket(
		Index<StringSet<TText, TSpec>, TIndexSpec> &index,
		TBeginPos left, 
		TEndPos right,
		TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef Index<StringSet<TText, TSpec>, TIndexSpec>			TIndex;
		typedef typename Fibre<TIndex, WotdSA >::Type				TSA;
		typedef typename TIndex::TCounter							TCounter;
		typedef typename TIndex::TTempSA							TTempSA;

		typedef typename Iterator<TText const, Standard>::Type		TTextIterator;
		typedef typename Iterator<TSA, Standard>::Type				TSAIterator;
		typedef typename Iterator<TTempSA, Standard>::Type			TTempSAIterator;
		typedef typename Iterator<TCounter, Standard>::Type			TCntIterator;
		typedef typename Size<TText>::Type							TTextSize;
		typedef typename Value<TText>::Type							TValue;

		StringSet<TText, TSpec> const &stringSet = indexText(index);
		TTempSA const &tempSA = index.tempSA;
		TCounter &occ = index.tempOcc;
		TCounter &bound = index.tempBound;

		// 1. clear counters and copy SA to temporary SA
		TCntIterator occBeg = begin(occ, Standard());

		arrayFill(occBeg, end(occ, Standard()), 0);
		index.tempSA = infix(indexSA(index), left, right);

		// 2. count characters
		index.sentinelBound = 0;
		index.sentinelOcc = _wotdCountChars(occ, stringSet, tempSA, prefixLen);

		// 3. cumulative sum
		TSize requiredSize = 0;
		if (index.interSentinelNodes) {
			if (index.sentinelOcc != 0)
				requiredSize = (index.sentinelOcc > 1)? 2: 1;	// insert *one* $-edge for all $_i suffices
		} else
			requiredSize = index.sentinelOcc;					// insert each $_i suffix one-by-one

		requiredSize += _wotdCummulativeSum(bound, occ, left + index.sentinelOcc);
		index.sentinelBound = left;

		// 4. fill suffix array
		{
			TSA &sa = indexSA(index);
			TSAIterator saBeg = begin(sa, Standard());
			TCntIterator boundBeg = begin(bound, Standard());

			TTextIterator itText = TTextIterator();
			TTempSAIterator itSA = begin(tempSA, Standard());
			TTempSAIterator itSAEnd = end(tempSA, Standard());
			TTextSize textLength = 0;
			unsigned lastSeqSeen = -1;
			Pair<unsigned, TTextSize> lPos;
			for(; itSA != itSAEnd; ++itSA)
			{
				posLocalize(lPos, *itSA, stringSetLimits(index));
				if (lastSeqSeen != getSeqNo(lPos))
				{
					lastSeqSeen = getSeqNo(lPos);

					// shift textBegin and textLength by prefixLen
					textLength = length(stringSet[lastSeqSeen]) - prefixLen;
					itText = begin(stringSet[lastSeqSeen], Standard()) + prefixLen;
				}
				if (textLength > getSeqOffset(lPos))
					*(saBeg + (*(boundBeg + ordValue(*(itText + getSeqOffset(lPos)))))++) = *itSA;
				else
					if (textLength == getSeqOffset(lPos))
						*(saBeg + index.sentinelBound++) = *itSA;
			}
		}

		return requiredSize;
	}





	template < typename TSA, typename TText >
	typename Size<TText>::Type 
	_bucketLcp(TSA const &sa, TText const &text)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA const, Standard>::Type	TSAIterator;
		typedef typename Value<TText>::Type						TValue;
		typedef typename Size<TText>::Type						TTextSize;

		TTextSize prefixLen = 0;
		
		if (length(sa) < 2) return prefixLen;

		TTextIterator itText = begin(text, Standard());
		TSAIterator itSAEnd = end(sa, Standard());
		TTextSize textLength = length(text);

		do {
			TSAIterator itSA = begin(sa, Standard());
			TTextSize sa = *itSA;
			if (textLength == sa) return prefixLen;

			TValue c = *(itText + sa);
			for(++itSA; itSA != itSAEnd; ++itSA) {
				sa = *itSA;
				if (textLength == sa || c != *(itText + sa))
					return prefixLen;
			}
			++prefixLen; --textLength;
			++itText;
		} while (true);
	}

	template < typename TSA, typename TText, typename TSize >
	typename Size<TText>::Type 
	_bucketLcp(TSA const &sa, TText const &text, TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA const, Standard>::Type	TSAIterator;
		typedef typename Value<TText>::Type						TValue;
		typedef typename Size<TText>::Type						TTextSize;

		if (length(sa) < 2) return prefixLen;

		TTextIterator itText = begin(text, Standard()) + prefixLen;
		TSAIterator itSAEnd = end(sa, Standard());
		TTextSize textLength = length(text) - prefixLen;

		do {
			TSAIterator itSA = begin(sa, Standard());
			TTextSize sa = *itSA;
			if (textLength == sa) return prefixLen;

			TValue c = *(itText + sa);
			for(++itSA; itSA != itSAEnd; ++itSA) {
				sa = *itSA;
				if (textLength == sa || c != *(itText + sa))
					return prefixLen;
			}
			++prefixLen; --textLength;
			++itText;
		} while (true);
	}

	template < typename TSA, typename TText, typename TSpec, typename TSize >
	typename Size<TText>::Type 
	_bucketLcp(TSA const &sa, StringSet<TText, TSpec> const &stringSet, TSize prefixLen)
	{
	SEQAN_CHECKPOINT
		typedef typename Iterator<TText const, Standard>::Type	TTextIterator;
		typedef typename Iterator<TSA const, Standard>::Type	TSAIterator;
		typedef typename Value<TText>::Type						TValue;
		typedef typename Size<TText>::Type						TTextSize;

		if (length(sa) < 2) return prefixLen;

		TSAIterator itSAEnd = end(sa, Standard());
		TTextIterator itText;
		TTextSize textLength;

		Pair<unsigned, TTextSize> lPos;
		do {
			TSAIterator itSA = begin(sa, Standard());
			posLocalize(lPos, *itSA, stringSetLimits(stringSet));

			unsigned lastSeqSeen = getSeqNo(*itSA);
			textLength = length(stringSet[lastSeqSeen]) - prefixLen;
			if (textLength == getSeqOffset(lPos)) return prefixLen;

			itText = begin(stringSet[lastSeqSeen], Standard()) + prefixLen;
			TValue c = *(itText + getSeqOffset(*itSA));
			for(++itSA; itSA != itSAEnd; ++itSA)
			{
				posLocalize(lPos, *itSA, stringSetLimits(stringSet));

				if (lastSeqSeen != getSeqNo(lPos))
				{
					lastSeqSeen = getSeqNo(lPos);

					// shift textBegin and textLength by prefixLen
					textLength = length(stringSet[lastSeqSeen]) - prefixLen;
					itText = begin(stringSet[lastSeqSeen], Standard()) + prefixLen;
				}

				if (textLength == getSeqOffset(lPos) || c != *(itText + getSeqOffset(lPos)))
					return prefixLen;
			}
			++prefixLen; --textLength;
			++itText;
		} while (true);
	}


	template <typename TText, typename TSpec, typename TPos>
	inline TPos
	_getNodeLP(
		Index<TText, IndexWotd<TSpec> > const &index, 
		TPos pos)
	{
		TPos w0 = dirAt(pos, index);
		if (w0 & index.LEAF)
			return w0 & index.BITMASK0;

		TPos w1 = dirAt(pos + 1, index);
		if (w1 & index.UNEVALUATED)
			return saAt(w0 & index.BITMASK0, index);
		else
			return w0 & index.BITMASK0;
	}

	// store buckets into directory 
	// ORIGINAL VERSION: storing SA entries and topology links in Dir
	template <typename TText, typename TPos>
	inline void 
	_storeWotdChildren(
		Index<TText, IndexWotd<WotdOriginal> > &index,
		TPos dirOfs)
	{
	SEQAN_CHECKPOINT
		typedef Index<TText, IndexWotd<WotdOriginal> >		TIndex;
		typedef typename Fibre<TIndex, WotdDir>::Type		TDir;
		typedef typename Iterator<TDir, Standard>::Type		TDirIterator;
		typedef typename Size<TDir>::Type					TDirSize;
		typedef typename TIndex::TCounter					TCounter;
		typedef typename Iterator<TCounter, Standard>::Type	TCntIterator;

		typedef typename Value<TCounter>::Type				TValue;

		TDirIterator itDir = begin(indexDir(index), Standard()) + dirOfs;
		TDirIterator itDirEnd = end(indexDir(index), Standard());
		TDirIterator itPrev = itDirEnd;

		TCntIterator it = begin(index.tempOcc, Standard());
		TCntIterator bit = begin(index.tempBound, Standard());
		TCntIterator itEnd = end(index.tempOcc, Standard());

		TValue occ;
		if (index.sentinelOcc != 0)
		{
			if (index.sentinelOcc > 1 && index.interSentinelNodes)	// occurs on multiseqs
			{
				itPrev = itDir;
				*itDir = index.sentinelBound - index.sentinelOcc;	++itDir;
				*itDir = index.sentinelBound | index.UNEVALUATED;	++itDir;
			} else
				for (TDirSize d = index.sentinelBound - index.sentinelOcc; d != index.sentinelBound; ++d)
				{
					itPrev = itDir;
					*itDir = saAt(d, index) | index.LEAF;			++itDir;
				}
		}
		for (; it != itEnd; ++it, ++bit)
		{
			if ((occ = *it) == 0) continue;
			if (occ > 1) {
				itPrev = itDir;
				*itDir = *bit - occ; 							++itDir;
				*itDir = *bit | index.UNEVALUATED;				++itDir;
			} else {
				itPrev = itDir;
				*itDir = saAt(*bit - occ, index) | index.LEAF;	++itDir;
			}
		}

		// mark the last child
		if (itPrev != itDirEnd)
			*itPrev |= index.LAST_CHILD;
	}

	// store buckets into directory
	// MODIFIED VERSION: storing SA links and topology links in Dir
	template <typename TText, typename TSpec, typename TSize>
	inline void 
	_storeWotdChildren(
		Index<TText, IndexWotd<TSpec> > &index,
		TSize dirOfs,
		TSize lcp)
	{
	SEQAN_CHECKPOINT
		typedef Index<TText, IndexWotd<TSpec> >			TIndex;
		typedef typename Fibre<TIndex, WotdDir>::Type		TDir;
		typedef typename Iterator<TDir, Standard>::Type		TDirIterator;
		typedef typename Size<TDir>::Type					TDirSize;
		typedef typename TIndex::TCounter					TCounter;
		typedef typename Iterator<TCounter, Standard>::Type	TCntIterator;

		typedef typename Value<TCounter>::Type				TValue;

		TDirIterator itDirBegin = begin(indexDir(index), Standard()) + dirOfs;
		TDirIterator itDirEnd = end(indexDir(index), Standard());
		TDirIterator itDir = itDirBegin;
		TDirIterator itPrev = itDirEnd;

		TCntIterator it = begin(index.tempOcc, Standard());
		TCntIterator bit = begin(index.tempBound, Standard());
		TCntIterator itEnd = end(index.tempOcc, Standard());

		TValue occ;
		if (index.sentinelOcc != 0)
		{
			if (index.sentinelOcc > 1 && index.interSentinelNodes)	// occurs on multiseqs
			{ 
				itPrev = itDir;
				*itDir = index.sentinelBound - index.sentinelOcc;	++itDir;
				*itDir = index.sentinelBound | index.UNEVALUATED;	++itDir;
			} else
				for (TDirSize d = index.sentinelBound - index.sentinelOcc; d != index.sentinelBound; ++d)
				{
					itPrev = itDir;
					*itDir = d | index.LEAF;						++itDir;
				}
		}
		for (; it != itEnd; ++it, ++bit)
		{
			if ((occ = *it) == 0) continue;
			if (occ > 1) {
				itPrev = itDir;
				*itDir = *bit - occ; 				++itDir;
				*itDir = *bit | index.UNEVALUATED;	++itDir;
			} else {
				itPrev = itDir;
				*itDir = (*bit - occ) | index.LEAF;	++itDir;
			}
		}

		// first child gets the mutual lcp value of the children (== parent repLength)
		*itDirBegin = ((*itDirBegin) & ~index.BITMASK0) | lcp;

		// mark the last child
		if (itPrev != itDirEnd)
			*itPrev |= index.LAST_CHILD;
	}


	template < typename TText, typename TSpec >
	inline typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type 
	_wotdEvaluate(Iter< Index<TText, IndexWotd<WotdOriginal> >, VSTree<TSpec> > const &it)
	{
		typedef Index<TText, IndexWotd<WotdOriginal> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex &index = const_cast<TIndex&>(container(it));
		TSize pos = value(it).node;
		TSize w1 = dirAt(pos + 1, index);

		// test for evaluation
		if (w1 & index.UNEVALUATED)
		{
			TSize w0 = dirAt(pos, index);
			TSize lp = saAt(w0 & index.BITMASK0, index);
			TSize dst = length(indexDir(index));

			TSize size = _sortWotdBucket(
				index, 
				w0 & index.BITMASK0, 
				w1 & index.BITMASK1, 
				parentEdgeLength(it));

			resize(indexDir(index), dst + size, Generous());
			_storeWotdChildren(index, dst);

			// mark nodes with solely empty child edges
			w1 = dst;
			if (index.sentinelOcc > 1)
				if (size == 2) w1 |= index.SENTINELS;

			assert(!(index.sentinelOcc == 1 && size == 1));

			dirAt(pos, index)     = (w0 & ~index.BITMASK0) | lp;
			dirAt(pos + 1, index) = w1;
		}

		return w1;
	}

	template < typename TText, typename TIndexSpec, typename TSpec >
	inline typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type 
	_wotdEvaluate(Iter< Index<TText, IndexWotd<TIndexSpec> >, VSTree<TSpec> > const &it)
	{
		typedef Index<TText, IndexWotd<TIndexSpec> >	TIndex;
		typedef typename Size<TIndex>::Type				TSize;

		TIndex &index = const_cast<TIndex&>(container(it));
		TSize pos = value(it).node;
		TSize w1 = dirAt(pos + 1, index);

		// test for evaluation
		if (w1 & index.UNEVALUATED) 
		{
			TSize dst = length(indexDir(index));

			TSize size = _sortWotdBucket(
				index, 
				value(it).range.i1, 
				w1 & index.BITMASK1, 
				repLength(it));

/*			if (globalDumpFlag) 
			{
				::std::cerr << '"' << representative(it) << '"' << ::std::endl;
				_dumpFreq(index);
			}
*/
			resize(indexDir(index), dst + size, Generous());
			_storeWotdChildren(index, dst, repLength(it));

			// mark nodes with solely empty child edges
			w1 = dst;
			if (index.sentinelOcc > 1)
				if (size == 2) w1 |= index.SENTINELS;

			dirAt(pos + 1, index) = w1;
		}

		return w1;
	}


	template <typename TText, typename TSpec>
	inline void
	_dump(Index<TText, IndexWotd<TSpec> > &index)
	{
		typedef Index<TText, IndexWotd<TSpec> >			TIndex;
		typedef typename Fibre<TIndex, WotdDir>::Type		TDir;
		typedef typename Value<TDir>::Type					TDirValue;

		::std::cout << "  Dir (wotd)" << ::std::endl;
		for(unsigned i=0; i < length(indexDir(index)); ++i) {
			TDirValue d = indexDir(index)[i];
			::std::cout << i << ":  " << (d & index.BITMASK0);
			if (d & index.LEAF)			::std::cout << "  (Leaf/Uneval)";
			if (d & index.LAST_CHILD)	::std::cout << "  (LastChild/SENTINELS)";
			::std::cout << ::std::endl;
		}

		::std::cout << ::std::endl << "  SA" << ::std::endl;
		for(unsigned i=0; i < length(indexSA(index)); ++i)
			::std::cout << i << ":  " << indexSA(index)[i] << "  " << suffix(indexText(index), indexSA(index)[i]) << ::std::endl;

		::std::cout << ::std::endl;

	}

//////////////////////////////////////////////////////////////////////////////
// _goDownChar

	template < typename TText, class TSpec, typename TValue >
	inline bool _goDownChar(
		Iter<Index<TText, IndexWotd<WotdOriginal> >, VSTree< TopDown<TSpec> > > &it,
		TValue c)
	{
		typedef Index<TText, IndexWotd<TSpec> >	TIndex;
		typedef typename Value<TIndex>::Type		TIndexValue;

		bool sorted = false;
		if (!goDown(it)) return false;
		do {
			if (parentEdgeLength(it) != 0) {
				TIndexValue edgeChar = parentEdgeLabel(it)[0];
				if (edgeChar == c) return true;		// the edge is found
				if (sorted && edgeChar > c) break;	// too far (except the first one,
			}										// child edges are sorted)
			sorted = true;
		} while (goRight(it));
		_goUp(it);
		return false;
	}

	template < typename TText, class TIndexSpec, class TSpec, typename TValue >
	inline bool _goDownChar(
		Iter<Index<TText, IndexWotd<TIndexSpec> >, VSTree< TopDown<TSpec> > > &it,
		TValue c)
	{
		typedef Index<TText, IndexWotd<TSpec> >	TIndex;
		typedef typename Value<TIndex>::Type		TIndexValue;

		if (!goDown(it)) return false;
		do {
			if (parentEdgeLength(it) != 0) {
				TIndexValue edgeChar = parentEdgeLabel(it)[0];
				if (edgeChar == c) return true;	// the edge is found
				if (edgeChar > c) break;		// too far (child edges are sorted)
			}
		} while (goRight(it));
		_goUp(it);
		return false;
	}

/*
	template < typename TText, typename TSpec, typename TValue >
	inline bool
	_getNodeByChar(
		Iter< Index<TText, IndexWotd<TSpec> >, VSTree<TSpec> > const &it,
		TValue c, 
		typename VertexDescriptor< Index<TText, IndexWotd<TSpec> > >::Type &childDesc)
	{
		typedef Index<TText, IndexWotd<TSpec> >			TIndex;
		typedef typename Fibre<TIndex, WotdDir>::Type		TDir;
		typedef typename Fibre<TIndex, WotdSA>::Type		TSA;

		typedef typename Value<TSA>::Type					TSAValue;
		typedef typename Value<TDir>::Type					TDirValue;

		typename Size<TIndex>::Type len = length(index);
		typename VertexDescriptor<TIndex>::Type	desc;

		TSAValue pos = _firstSuffixOfBucket(index, value(it).node);
		while (pos == len || value < (c = textAt(index, pos + value.i2))) {
			value.node += (dirAt(value.node, index) & index.LEAF)? 1: 2;
			pos = _firstSuffixOfBucket(index, value.node);
		}
		assert(pos != len);

		return c == value;
	}
*/

//////////////////////////////////////////////////////////////////////////////
// interface for automatic index creation 

	template <typename TText, typename TSpec>
	inline void _wotdCreateFirstLevel(Index<TText, IndexWotd<TSpec> > &index)
	{
		typedef Index<TText, IndexWotd<TSpec> >	TIndex;
		typedef typename Value<TIndex>::Type		TValue;
		typedef typename Size<TIndex>::Type			TSize;

		resize(index.tempOcc, ValueSize<TValue>::VALUE + 1);
		resize(index.tempBound, ValueSize<TValue>::VALUE + 1);

		TSize size;
		if (empty(indexSA(index)))
		{
			resize(indexSA(index), length(indexRawText(index)));
			size = _sortFirstWotdBucket(index);
		} else
		{
			size = _sortWotdBucket(index, 0, length(indexSA(index)), 0);
		}
		
		if (size > 0) 
		{
			resize(indexDir(index), size + 2, Generous());
			_storeWotdChildren(index, 2, 0);

			// mark nodes with solely empty child edges
			TSize w1 = 2;
			if (index.sentinelOcc > 1)
				if (size == 2) w1 |= index.SENTINELS;

			dirAt(0, index) = 0 | index.LAST_CHILD;
			dirAt(1, index) = w1;

		} else {
			resize(indexDir(index), 1);
			dirAt(0, index) = 0 | index.LAST_CHILD | index.LEAF;
		}
	}

	template <typename TText, typename TSpec>
	inline bool indexCreate(Index<TText, IndexWotd<TSpec> > &index, WotdDir const, Default const)
	{
		_wotdCreateFirstLevel(index);
		return true;
	}

//////////////////////////////////////////////////////////////////////////////
// clear

	template < typename TText, typename TSpec >
	inline void clear(Index<TText, IndexWotd<TSpec> > &index)
	{
		clear(getFibre(index, WotdSA()));
		clear(getFibre(index, WotdDir()));
	}

//////////////////////////////////////////////////////////////////////////////
// open

	template < typename TText, typename TSpec >
	inline bool open(
		Index< TText, IndexWotd<TSpec> > &index, 
		const char *fileName,
		int openMode)
	{
		String<char> name;
		name = fileName;	append(name, ".txt");
		bool result = true;
		if ((!open(getFibre(index, WotdText()), toCString(name), openMode)) && 
			(!open(getFibre(index, WotdText()), fileName, openMode)))
			result = false;
		name = fileName;	append(name, ".sa");	open(getFibre(index, WotdSA()), toCString(name), openMode);
		name = fileName;	append(name, ".dir");	open(getFibre(index, WotdDir()), toCString(name), openMode);
		return result;
	}
	template < typename TText, typename TSpec >
	inline bool open(
		Index< TText, IndexWotd<TSpec> > &index, 
		const char *fileName) 
	{
		return open(index, fileName, OPEN_RDONLY);
	}


//////////////////////////////////////////////////////////////////////////////
// save

	template < typename TText, typename TSpec >
	inline bool save(
		Index< TText, IndexWotd<TSpec> > &index, 
		const char *fileName,
		int openMode)
	{
		String<char> name;
		name = fileName;	append(name, ".txt");
		if ((!save(getFibre(index, WotdText()), toCString(name), openMode)) && 
			(!save(getFibre(index, WotdText()), fileName, openMode))) return false;

		name = fileName;	append(name, ".sa");	save(getFibre(index, WotdSA()), toCString(name), openMode);
		name = fileName;	append(name, ".dir");	save(getFibre(index, WotdDir()), toCString(name), openMode);
		return true;
	}
	template < typename TText, typename TSpec >
	inline bool save(
		Index< TText, IndexWotd<TSpec> > &index, 
		const char *fileName)
	{
		return save(index, fileName, OPEN_WRONLY | OPEN_CREATE);
	}
}

#endif //#ifndef SEQAN_HEADER_...