seqan/index/index_wotd.h

123 		typedef typename Size<TText>::Type					TSize;  typedef
124 		typedef String<TSize, Alloc<> >						TCounter;
129 …static TSize const LEAF          = (TSize)1 << (BitsPerValue<TSize>::VALUE - 1); // this node is a…
130 …static TSize const LAST_CHILD    = (TSize)1 << (BitsPerValue<TSize>::VALUE - 2); // this node is t…
132 …static TSize const UNEVALUATED   = (TSize)1 << (BitsPerValue<TSize>::VALUE - 1); // this node is p…
133 …static TSize const SENTINELS     = (TSize)1 << (BitsPerValue<TSize>::VALUE - 2); // the children o…
135 		static TSize const BITMASK0      = ~(LEAF | LAST_CHILD);
136 		static TSize const BITMASK1      = ~(UNEVALUATED | SENTINELS);
149 		TSize			sentinelOcc;
150 		TSize			sentinelBound;
225 	template <typename TSize>
227 		TSize		node;			// position of current node entry in directory
228 		TSize		parentRepLen;	// representative length of parent node
229 		TSize		edgeLen;		// length of edge above current node
240 	template <typename TSize>
242 		TSize		node;			// position of current node entry in directory
243 		TSize		parentRepLen;	// representative length of parent node
244 		TSize		edgeLen;		// length of edge above current node
245 		Pair<TSize> range;			// current SA interval of hits
246 		TSize		parentRight;	// right boundary of parent node's range (allows to go right)
255 		VertexWotdModified_(Pair<TSize> const &otherRange, TSize otherParentRight):
268 		typedef typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type TSize;
269 		typedef VertexWotdOriginal_<TSize> Type;
274 		typedef typename Size< Index<TText, IndexWotd<TSpec> > >::Type TSize;
275 		typedef VertexWotdModified_<TSize> Type;
287 	template <typename TSize>
290 		TSize		node;		// position of current node entry in directory
291 		TSize		edgeLen;	// length of edge above current node
294 	template <typename TSize>
297 		TSize		node;		// position of current node entry in directory
298 		TSize		edgeLen;	// length of edge above current node
299 		Pair<TSize> range;		// current SA interval of hits
306 		typedef typename Size<TIndex>::Type				TSize;
307 		typedef HistoryStackWotdOriginal_<TSize>		Type;
314 		typedef typename Size<TIndex>::Type				TSize;
315 		typedef HistoryStackWotdModified_<TSize>		Type;
332 		typedef typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type TSize;
333 		TSize edgeLen = parentEdgeLength(it);
334 		HistoryStackWotdOriginal_<TSize> entry = { value(it).node, edgeLen };
343 		typedef typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type TSize;
344 		TSize edgeLen = parentEdgeLength(it);
345 		HistoryStackWotdModified_<TSize> entry = { value(it).node, edgeLen, value(it).range };
374 	template < typename TSize >
375 	inline typename Id< VertexWotdOriginal_<TSize> const >::Type
376 	_getId(VertexWotdOriginal_<TSize> const &desc)
381 	template < typename TSize >
382 	inline typename Id< VertexWotdOriginal_<TSize> >::Type
383 	_getId(VertexWotdOriginal_<TSize> &desc)
385 		return _getId(const_cast<VertexWotdOriginal_<TSize> const &>(desc));
388 	template < typename TSize >
389 	inline typename Id< VertexWotdModified_<TSize> const >::Type
390 	_getId(VertexWotdModified_<TSize> const &desc)
395 	template < typename TSize >
396 	inline typename Id< VertexWotdModified_<TSize> >::Type
397 	_getId(VertexWotdModified_<TSize> &desc)
399 		return _getId(const_cast<VertexWotdModified_<TSize> const &>(desc));
404 	template < typename TSize >
405 	inline bool _isRoot(VertexWotdOriginal_<TSize> const &value) {
409 	template < typename TSize >
410 	inline bool _isRoot(VertexWotdModified_<TSize> const &value) {
432 		typedef typename Size<TIndex>::Type				TSize;
444 	template < typename TIndex, typename TSize >
446 	parentEdgeLength(TIndex const &index, VertexWotdOriginal_<TSize> &vDesc)
448 		TSize edgeLen = vDesc.edgeLen;
449 		if (edgeLen != (TSize)-1)
452 		TSize pos = vDesc.node;
453 		TSize w0 = dirAt(pos, index);
457 		TSize w1 = dirAt(pos + 1, index);
467 	template < typename TIndex, typename TSize >
469 	parentEdgeLength(TIndex const &index, VertexWotdModified_<TSize> &vDesc)
471 		TSize edgeLen = vDesc.edgeLen;
472 		if (edgeLen != (TSize)-1)
475 		TSize pos = vDesc.node;
476 		TSize w0 = dirAt(pos, index);
481 		TSize w1 = dirAt(pos + 1, index);
541 		typedef typename Size<TIndex>::Type				TSize;
548 			TSize occ = _getNodeLP(index, value(it).node);
639 		typedef typename Size<TIndex>::Type				TSize;
642 		TSize	pos = value(it).node;
644 		TSize w0 = dirAt(pos, index);
664 		typedef typename Size<TIndex>::Type				TSize;
672 		TSize childNode = _wotdEvaluate(it);
700 		typedef typename Size<TIndex>::Type				TSize;
706 		TSize childNode = _wotdEvaluate(it);
736 		typedef typename Size<TIndex>::Type				TSize;
741 			TSize w0 = dirAt(value(it).node, index);
760 		typedef typename Size<TIndex>::Type				TSize;
765 			TSize w0 = dirAt(value(it).node, index);
796 		typedef typename Size< Index<TText, IndexWotd<WotdOriginal> > >::Type TSize;
799 			HistoryStackWotdOriginal_<TSize> const &entry = top(it.history);
813 		typedef typename Size< Index<TText, IndexWotd<TIndexSpec> > >::Type TSize;
817 			HistoryStackWotdModified_<TSize> const &entry = top(it.history);
836 		typedef typename Size<TIndex>::Type TSize;
840 			HistoryStackWotdModified_<TSize> const &entry = top(it.history);
847 			TSize h = length(it.history) - 1;
861 		typedef typename Size<TIndex>::Type TSize;
865 			HistoryStackWotdModified_<TSize> const &entry = top(it.history);
912 	template < typename TBuckets, typename TText, typename TSA, typename TSize >
918 		TSize prefixLen)
943 	template < typename TBuckets, typename TText, typename TSA, typename TSize >
949 		TSize prefixLen)
978 		typename TSize
985 		TSize prefixLen)
1024 	template < typename TBounds, typename TBuckets, typename TSize >
1026 	_wotdCummulativeSum(TBounds &bounds, TBuckets const &buckets, TSize offset)
1083 		typedef typename Size<TText>::Type						TSize;
1096 		TSize requiredSize = _wotdCummulativeSum(bound, occ);
1106 			for(TSize i = 0; itText != itTextEnd; ++itText, ++i)
1128 		typedef typename Size<TText>::Type						TSize;
1142 		TSize requiredSize = _wotdCummulativeSum(bound, occ);
1177 	template < typename TText, typename TBeginPos, typename TEndPos, typename TSize >
1178 	TSize _sortWotdBucket(
1182 		TSize prefixLen)
1209 		TSize requiredSize = 0;
1244 			TSize lpBucket = ordValue(text[tempSA[0]]);
1246 				TSize lpBucketOcc = occ[lpBucket];
1247 				TSize lpBucketBound = bound[lpBucket];
1269 					TSize swap = index.sentinelOcc;
1291 	template < typename TIndex, typename TBeginPos, typename TEndPos, typename TSize >
1292 	TSize _sortWotdBucket(
1296 		TSize prefixLen)
1322 		TSize requiredSize = 0;
1357 … TText, typename TSpec, typename TIndexSpec, typename TBeginPos, typename TEndPos, typename TSize >
1358 	TSize _sortWotdBucket(
1362 		TSize prefixLen)
1393 		TSize requiredSize = 0;
1475 	template < typename TSA, typename TText, typename TSize >
1477 	_bucketLcp(TSA const &sa, TText const &text, TSize prefixLen)
1507 	template < typename TSA, typename TText, typename TSpec, typename TSize >
1509 	_bucketLcp(TSA const &sa, StringSet<TText, TSpec> const &stringSet, TSize prefixLen)
1634 	template <typename TText, typename TSpec, typename TSize>
1638 		TSize dirOfs,
1639 		TSize lcp)
1702 		typedef typename Size<TIndex>::Type				TSize;
1705 		TSize pos = value(it).node;
1706 		TSize w1 = dirAt(pos + 1, index);
1711 			TSize w0 = dirAt(pos, index);
1712 			TSize lp = saAt(w0 & index.BITMASK0, index);
1713 			TSize dst = length(indexDir(index));
1715 			TSize size = _sortWotdBucket(
1743 		typedef typename Size<TIndex>::Type				TSize;
1746 		TSize pos = value(it).node;
1747 		TSize w1 = dirAt(pos + 1, index);
1752 			TSize dst = length(indexDir(index));
1754 			TSize size = _sortWotdBucket(
1888 		typedef typename Size<TIndex>::Type			TSize;
1893 		TSize size;
1909 			TSize w1 = 2;