1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2010, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 //     * Redistributions of source code must retain the above copyright
11 //       notice, this list of conditions and the following disclaimer.
12 //     * Redistributions in binary form must reproduce the above copyright
13 //       notice, this list of conditions and the following disclaimer in the
14 //       documentation and/or other materials provided with the distribution.
15 //     * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 //       its contributors may be used to endorse or promote products derived
17 //       from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: David Weese <david.weese@fu-berlin.de>
33 // ==========================================================================
34 
35 #ifndef SEQAN_HEADER_STORE_ANNOTATION_H
36 #define SEQAN_HEADER_STORE_ANNOTATION_H
37 
38 namespace SEQAN_NAMESPACE_MAIN
39 {
40 
41 //////////////////////////////////////////////////////////////////////////////
42 // Annotation Store
43 //////////////////////////////////////////////////////////////////////////////
44 
45 template <typename TPos_, typename TSpec = void>
46 struct AnnotationStoreElement
47 {
48 	typedef typename Id<AnnotationStoreElement>::Type		TId;
49 	typedef TPos_											TPos;
50 	typedef StringSet<CharString, Owner< ConcatDirect<> > >	TValues;
51 
52 	static const TId  INVALID_ID;
53 	static const TPos INVALID_POS;
54 
55 	TId					parentId;
56 	TId					contigId;
57 	TId					countId;
58 	TId					typeId;			// gene, intron, ...
59 
60 	TPos				beginPos;		// begin position of the gapped sequence in gapped contig sequence
61 	TPos				endPos;			// end position of ..., for reverse aligned reads holds end < begin
62 
63 	TId					lastChildId;	// generated back links to child
64 	TId					nextSiblingId;	// and sibling
65 
66 	TValues				values;			// stores values for each keyId of (key,value) pairs
67 
AnnotationStoreElementAnnotationStoreElement68 	AnnotationStoreElement() :
69 		parentId(INVALID_ID), contigId(INVALID_ID), countId(INVALID_ID), typeId(INVALID_ID),
70 		beginPos(INVALID_POS), endPos(INVALID_POS),
71 		lastChildId(INVALID_ID), nextSiblingId(INVALID_ID) {}
72 };
73 
74 //////////////////////////////////////////////////////////////////////////////
75 
76 template <typename TPos, typename TSpec>
77 const typename Id<AnnotationStoreElement<TPos, TSpec> >::Type
78 AnnotationStoreElement<TPos, TSpec>::INVALID_ID = MaxValue<typename Id<AnnotationStoreElement<TPos, TSpec> >::Type>::VALUE;
79 
80 template <typename TPos, typename TSpec>
81 const TPos
82 AnnotationStoreElement<TPos, TSpec>::INVALID_POS = MaxValue<TPos>::VALUE;
83 
84 //////////////////////////////////////////////////////////////////////////////
85 
86 template <typename TSpec = void>
87 struct AnnotationTree {};
88 
89 template <typename TFragmentStore, typename TSpec>
90 class Iter<TFragmentStore, AnnotationTree<TSpec> >
91 {
92 public:
93 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
94 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
95 	typedef typename TAnnotation::TId					TId;
96 
97 	TFragmentStore *store;
98 	TId id;
99 
Iter()100 	Iter():
101 		store(NULL),
102 		id(TAnnotation::INVALID_ID) {}
103 
Iter(TFragmentStore & _store)104 	Iter(TFragmentStore &_store):
105 		store(&_store),
106 		id(0) {}
107 
Iter(TFragmentStore & _store,MinimalCtor)108 	Iter(TFragmentStore &_store, MinimalCtor):
109 		store(&_store),
110 		id(TAnnotation::INVALID_ID) {}
111 
112 	inline Iter const &
113 	operator = (Iter const &_origin)
114 	{
115 		store = &container(_origin);
116 		id = _origin.id;
117 		return *this;
118 	}
119 };
120 
121 //////////////////////////////////////////////////////////////////////////////
122 
123 template <typename TFragmentStore, typename TSpec>
124 struct Iterator< TFragmentStore, AnnotationTree<TSpec> > {
125 	typedef Iter< TFragmentStore, AnnotationTree<TSpec> > Type;
126 };
127 
128 //////////////////////////////////////////////////////////////////////////////
129 
130 template <typename TFragmentStore, typename TSpec>
131 struct Value< Iter< TFragmentStore, AnnotationTree<TSpec> > >:
132 	VertexDescriptor<TFragmentStore> {};
133 
134 template <typename TFragmentStore, typename TSpec>
135 struct Size< Iter< TFragmentStore, AnnotationTree<TSpec> > > :
136 	Size<TFragmentStore> {};
137 
138 template <typename TFragmentStore, typename TSpec>
139 struct Position< Iter< TFragmentStore, AnnotationTree<TSpec> > > :
140 	Position<TFragmentStore> {};
141 
142 //////////////////////////////////////////////////////////////////////////////
143 
144 template <typename TFragmentStore, typename TSpec>
145 inline typename VertexDescriptor<TFragmentStore>::Type &
146 value(Iter< TFragmentStore, AnnotationTree<TSpec> > &it) {
147 	return it.id;
148 }
149 
150 template <typename TFragmentStore, typename TSpec>
151 inline typename VertexDescriptor<TFragmentStore>::Type const &
152 value(Iter< TFragmentStore, AnnotationTree<TSpec> > const &it) {
153 	return it.id;
154 }
155 
156 //////////////////////////////////////////////////////////////////////////////
157 
158 template <typename TFragmentStore, typename TSpec>
159 inline TFragmentStore &
160 container(Iter< TFragmentStore, AnnotationTree<TSpec> > &it) {
161 	return *it.store;
162 }
163 
164 template <typename TFragmentStore, typename TSpec>
165 inline TFragmentStore &
166 container(Iter< TFragmentStore, AnnotationTree<TSpec> > const &it) {
167 	return *it.store;
168 }
169 
170 //////////////////////////////////////////////////////////////////////////////
171 
172 template <typename TFragmentStore, typename TSpec>
173 inline typename Reference<typename TFragmentStore::TAnnotationStore>::Type
174 getAnnotation(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
175 {
176 	return it.store->annotationStore[it.id];
177 }
178 
179 template <typename TFragmentStore, typename TSpec>
180 inline typename GetValue<typename TFragmentStore::TAnnotationNameStore>::Type
181 getName(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
182 {
183 	return getAnnoName(*it.store, it.id);
184 }
185 
186 template <typename TFragmentStore, typename TSpec, typename TName>
187 inline typename GetValue<typename TFragmentStore::TAnnotationNameStore>::Type
188 setName(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it, TName & name)
189 {
190 	if (length(it.store->annotationNameStore) <= it.id)
191 		resize(it.store->annotationNameStore, it.id + 1);
192 	it.store->annotationNameStore[it.id] = name;
193 }
194 
195 template <typename TFragmentStore, typename TSpec>
196 inline typename GetValue<typename TFragmentStore::TAnnotationNameStore>::Type
197 getParentName(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
198 {
199 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
200 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
201 	typedef typename TAnnotation::TId					TId;
202 
203 	TId parentId = it.store->annotationStore[it.id].parentId;
204 	if (parentId == TAnnotation::INVALID_ID) parentId = it.id;
205 	return getAnnoName(*it.store, parentId);
206 }
207 
208 //////////////////////////////////////////////////////////////////////////////
209 
210 template <typename TFragmentStore, typename TSpec>
211 inline typename GetValue<typename TFragmentStore::TAnnotationTypeStore>::Type
212 getType(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
213 {
214 	return getAnnoType(*it.store, it.id);
215 }
216 
217 template <typename TFragmentStore, typename TSpec, typename TTypeName>
218 inline void
219 setType(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it, TTypeName & typeName)
220 {
221 	_storeAppendType(*it.store, getAnnotation(it).typeId, typeName);
222 }
223 
224 //////////////////////////////////////////////////////////////////////////////
225 
226 template <typename TFragmentStore, typename TSpec>
227 inline CharString
228 getUniqueName(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
229 {
230 	return getAnnoUniqueName(*it.store, it.id);
231 }
232 
233 //////////////////////////////////////////////////////////////////////////////
234 
235 template <typename TFragmentStore, typename TSpec>
236 inline void
237 clearValues(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
238 {
239 	clear(getAnnotation(it).values);
240 }
241 
242 template <typename TFragmentStore, typename TSpec, typename TKey, typename TValue>
243 inline void
244 assignValueByKey(
245 	Iter<TFragmentStore, AnnotationTree<TSpec> > & it,
246 	TKey const & key,
247 	TValue const & value)
248 {
249 	annotationAssignValueByKey(*it.store, getAnnotation(it), key, value);
250 }
251 
252 template <typename TFragmentStore, typename TSpec, typename TKey, typename TValue>
253 inline bool
254 getValueByKey(
255 	Iter<TFragmentStore, AnnotationTree<TSpec> > const & it,
256 	TKey const & key,
257 	TValue & value)
258 {
259 	return annotationGetValueByKey(*it.store, getAnnotation(it), key, value);
260 }
261 
262 template <typename TFragmentStore, typename TSpec, typename TKey>
263 inline CharString
264 getValueByKey(
265 	Iter<TFragmentStore, AnnotationTree<TSpec> > const & it,
266 	TKey const & key)
267 {
268 	return annotationGetValueByKey(*it.store, getAnnotation(it), key);
269 }
270 
271 //////////////////////////////////////////////////////////////////////////////
272 
273 template <typename TFragmentStore, typename TSpec>
274 inline void
275 goBegin(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
276 {
277 	it.id = 0;
278 }
279 
280 template <typename TFragmentStore, typename TSpec>
281 inline void
282 goEnd(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
283 {
284 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
285 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
286 
287 	it.id = TAnnotation::INVALID_ID;
288 }
289 
290 template <typename TFragmentStore, typename TSpec>
291 inline void
292 clear(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
293 {
294 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
295 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
296 
297 	it.id = TAnnotation::INVALID_ID;
298 }
299 
300 //////////////////////////////////////////////////////////////////////////////
301 
302 template <typename TFragmentStore, typename TSpec>
303 inline bool
304 atBegin(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
305 {
306 	return it.id == 0;
307 }
308 
309 template <typename TFragmentStore, typename TSpec>
310 inline bool
311 atEnd(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
312 {
313 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
314 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
315 
316 	return it.id == TAnnotation::INVALID_ID;
317 }
318 
319 //////////////////////////////////////////////////////////////////////////////
320 
321 template <typename TFragmentStore, typename TSpec>
322 inline void
323 goNext(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
324 {
325 	// preorder dfs
326 	if (!goDown(it) && !goRight(it))
327 		while (goUp(it) && !goRight(it)) ;
328 	if (isRoot(it)) {
329 		clear(it);
330 		return;
331 	}
332 }
333 
334 template <typename TFragmentStore, typename TSpec>
335 inline void
336 goNextRight(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
337 {
338 	// preorder dfs
339 	if (!goRight(it))
340 		while (goUp(it) && !goRight(it)) ;
341 	if (isRoot(it)) {
342 		clear(it);
343 		return;
344 	}
345 }
346 
347 template <typename TFragmentStore, typename TSpec>
348 inline void
349 goNextUp(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
350 {
351 	// preorder dfs
352 	while (goUp(it) && !goRight(it)) ;
353 	if (isRoot(it)) {
354 		clear(it);
355 		return;
356 	}
357 }
358 
359 //////////////////////////////////////////////////////////////////////////////
360 
361 template <typename TFragmentStore, typename TSpec>
362 inline void
363 goRoot(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
364 {
365 	it.id = 0;
366 }
367 
368 template <typename TFragmentStore, typename TSpec>
369 inline bool
370 goUp(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
371 {
372 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
373 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
374 	typedef typename TAnnotation::TId					TId;
375 
376 	TId parentId = getAnnotation(it).parentId;
377 	if (parentId != TAnnotation::INVALID_ID)
378 	{
379 		it.id = parentId;
380 		return true;
381 	}
382 	return false;
383 }
384 
385 template <typename TFragmentStore, typename TSpec>
386 inline bool
387 goDown(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
388 {
389 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
390 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
391 	typedef typename TAnnotation::TId					TId;
392 
393 	TId lastChildId = getAnnotation(it).lastChildId;
394 	if (lastChildId != TAnnotation::INVALID_ID)
395 	{
396 		it.id = it.store->annotationStore[lastChildId].nextSiblingId;
397 		return true;
398 	}
399 	return false;
400 }
401 
402 template <typename TFragmentStore, typename TSpec>
403 inline bool
404 goRight(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
405 {
406 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
407 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
408 	typedef typename TAnnotation::TId					TId;
409 
410 	TAnnotation &anno = getAnnotation(it);
411 	TId nextSiblingId = anno.nextSiblingId;
412 	if (nextSiblingId != TAnnotation::INVALID_ID)
413 	{
414 		TId lastChildId = it.store->annotationStore[anno.parentId].lastChildId;
415 		if (it.id != lastChildId)
416 		{
417 			it.id = nextSiblingId;
418 			return true;
419 		}
420 	}
421 	return false;
422 }
423 
424 //////////////////////////////////////////////////////////////////////////////
425 
426 template <typename TFragmentStore, typename TSpec>
427 inline Iter<TFragmentStore, AnnotationTree<TSpec> >
428 nodeUp(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
429 {
430 	Iter<TFragmentStore, AnnotationTree<TSpec> > tmp(it);
431 	goUp(tmp);
432 	return tmp;
433 }
434 
435 template <typename TFragmentStore, typename TSpec>
436 inline Iter<TFragmentStore, AnnotationTree<TSpec> >
437 nodeDown(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
438 {
439 	Iter<TFragmentStore, AnnotationTree<TSpec> > tmp(it);
440 	goDown(tmp);
441 	return tmp;
442 }
443 
444 template <typename TFragmentStore, typename TSpec>
445 inline Iter<TFragmentStore, AnnotationTree<TSpec> >
446 nodeRight(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
447 {
448 	Iter<TFragmentStore, AnnotationTree<TSpec> > tmp(it);
449 	goRight(tmp);
450 	return tmp;
451 }
452 
453 //////////////////////////////////////////////////////////////////////////////
454 
455 // insert a new id into a cyclic list and returns new last child id
456 template <typename TAnnotationStore, typename TId>
457 inline TId
458 _cyclicListFrontInsert(TAnnotationStore & annotationStore, TId newId, TId lastChildId)
459 {
460 	typedef typename Value<TAnnotationStore>::Type TAnnotation;
461 
462 	TId nextId, newLastId;
463 	if (lastChildId != TAnnotation::INVALID_ID)
464 	{
465 		// get last node in the cycle
466 		TAnnotation &lastChild = annotationStore[lastChildId];
467 		// last child points to first child
468 		nextId = lastChild.nextSiblingId;
469 		// insert new node between last and first
470 		lastChild.nextSiblingId = newId;
471 		// last child remains the same
472 		newLastId = lastChildId;
473 	} else
474 		// cyclic list was empty
475 		newLastId = nextId = newId;
476 
477 	// link new node to former first node
478 	annotationStore[newId].nextSiblingId = nextId;
479 
480 	return newLastId;
481 }
482 
483 // delete an id from a cyclic list and returns new last child id
484 template <typename TAnnotationStore, typename TId>
485 inline TId
486 _cyclicListSearchPrev(TAnnotationStore & annotationStore, TId id, TId lastChildId)
487 {
488 	typedef typename Value<TAnnotationStore>::Type TAnnotation;
489 
490 	if (lastChildId == TAnnotation::INVALID_ID)
491 		return TAnnotation::INVALID_ID;
492 
493 	TId prevId, i = lastChildId;
494 	do {
495 		prevId = i;
496 		i = annotationStore[i].nextSiblingId;
497 		if (i == id) break;
498 	} while (i != lastChildId);
499 
500 	if (i == id)
501 		return prevId;
502 	else
503 		return TAnnotation::INVALID_ID;
504 }
505 
506 // delete an id from a cyclic list and returns new last child id
507 template <typename TAnnotationStore, typename TId>
508 inline TId
509 _cyclicListRemove(TAnnotationStore & annotationStore, TId id, TId lastChildId)
510 {
511 	typedef typename Value<TAnnotationStore>::Type TAnnotation;
512 
513 	TId prevId = _cyclicListSearchPrev(annotationStore, id, lastChildId);
514 
515 	if (prevId != TAnnotation::INVALID_ID)
516 	{
517 		annotationStore[prevId].nextSiblingId = annotationStore[id].nextSiblingId;
518 
519 		if (id == lastChildId)
520 		{
521 			if (prevId != id)
522 				return prevId;
523 			else
524 				return TAnnotation::INVALID_ID;
525 		} else
526 			return lastChildId;
527 	}
528 	return lastChildId;
529 }
530 
531 template <typename TFragmentStore, typename TSpec>
532 inline Iter<TFragmentStore, AnnotationTree<TSpec> >
533 createLeftChild(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
534 {
535 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
536 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
537 	typedef typename TAnnotation::TId					TId;
538 
539 	appendValue(it.store->annotationStore, getAnnotation(it));
540 	TAnnotation &parentAnno = getAnnotation(it);
541 
542 	TId childId = length(it.store->annotationStore) - 1;
543 	TAnnotation &childAnno = it.store->annotationStore[childId];
544 
545 	parentAnno.lastChildId = _cyclicListFrontInsert(it.store->annotationStore, childId, parentAnno.lastChildId);
546 	childAnno.parentId = it.id;
547 	childAnno.lastChildId = TAnnotation::INVALID_ID;
548 
549 	Iter<TFragmentStore, AnnotationTree<TSpec> > childIter(it);
550 	childIter.id = childId;
551 	return childIter;
552 }
553 
554 template <typename TFragmentStore, typename TSpec>
555 inline Iter<TFragmentStore, AnnotationTree<TSpec> >
556 createRightChild(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
557 {
558 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
559 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
560 	typedef typename TAnnotation::TId					TId;
561 
562 	appendValue(it.store->annotationStore, getAnnotation(it));
563 	TAnnotation &parentAnno = getAnnotation(it);
564 
565 	TId childId = length(it.store->annotationStore) - 1;
566 	TAnnotation &childAnno = it.store->annotationStore[childId];
567 
568 	_cyclicListFrontInsert(it.store->annotationStore, childId, parentAnno.lastChildId);
569 	parentAnno.lastChildId = childId;
570 	childAnno.parentId = it.id;
571 	childAnno.lastChildId = TAnnotation::INVALID_ID;
572 
573 	Iter<TFragmentStore, AnnotationTree<TSpec> > childIter(it);
574 	childIter.id = childId;
575 	return childIter;
576 }
577 
578 template <typename TFragmentStore, typename TSpec>
579 inline Iter<TFragmentStore, AnnotationTree<TSpec> >
580 createSibling(Iter<TFragmentStore, AnnotationTree<TSpec> > & it)
581 {
582 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
583 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
584 	typedef typename TAnnotation::TId					TId;
585 
586 	appendValue(it.store->annotationStore, getAnnotation(it));
587 	TAnnotation &anno = getAnnotation(it);
588 
589 	TId siblingId = length(it.store->annotationStore) - 1;
590 
591 	TAnnotation &parentAnno = it.store->annotationStore[anno.parentId];
592 	if (parentAnno.lastChildId == it.id)
593 		parentAnno.lastChildId = siblingId;
594 
595 	TAnnotation &siblingAnno = it.store->annotationStore[siblingId];
596 	siblingAnno.nextSiblingId = anno.nextSiblingId;
597 	siblingAnno.parentId = anno.parentId;
598 	siblingAnno.lastChildId = TAnnotation::INVALID_ID;
599 	anno.nextSiblingId = siblingId;
600 
601 	Iter<TFragmentStore, AnnotationTree<TSpec> > siblingIter(it);
602 	siblingIter.id = siblingId;
603 	return siblingIter;
604 }
605 
606 //////////////////////////////////////////////////////////////////////////////
607 
608 template <typename TFragmentStore, typename TSpec>
609 inline bool
610 isRoot(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
611 {
612 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
613 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
614 
615 //	if (it.id >= length(it.store->annotationStore)) return false;
616 	return it.store->annotationStore[it.id].parentId == TAnnotation::INVALID_ID;
617 }
618 
619 template <typename TFragmentStore, typename TSpec>
620 inline bool
621 isLeaf(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
622 {
623 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
624 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
625 
626 //	if (it.id >= length(it.store->annotationStore)) return false;
627 	return it.store->annotationStore[it.id].lastChildId == TAnnotation::INVALID_ID;
628 }
629 
630 template <typename TFragmentStore, typename TSpec>
631 inline bool
632 isLastChild(Iter<TFragmentStore, AnnotationTree<TSpec> > const & it)
633 {
634 	typedef typename TFragmentStore::TAnnotationStore	TAnnotationStore;
635 	typedef typename Value<TAnnotationStore>::Type		TAnnotation;
636 	typedef typename TAnnotation::TId					TId;
637 
638 	TAnnotation &anno = getAnnotation(it);
639 	TId nextSiblingId = anno.nextSiblingId;
640 	if (nextSiblingId != TAnnotation::INVALID_ID)
641 	{
642 		TId lastChildId = it.store->annotationStore[anno.parentId].lastChildId;
643 		return it.id == lastChildId;
644 	}
645 	return true;
646 }
647 
648 //////////////////////////////////////////////////////////////////////////////
649 
650 template <typename TAnnotationStore>
651 inline void
652 _storeClearAnnoBackLinks(TAnnotationStore & me)
653 {
654 	typedef typename Value<TAnnotationStore>::Type				TAnnotation;
655 	typedef typename Iterator<TAnnotationStore, Standard>::Type TAnnoIter;
656 
657 	TAnnoIter it = begin(me, Standard());
658 	TAnnoIter itEnd = end(me, Standard());
659 
660 	for (; it != itEnd; ++it)
661 	{
662 		(*it).lastChildId = TAnnotation::INVALID_ID;
663 		(*it).nextSiblingId = TAnnotation::INVALID_ID;
664 	}
665 }
666 
667 template <typename TAnnotationStore>
668 inline void
669 _storeCreateAnnoBackLinks(TAnnotationStore & me)
670 {
671 	typedef typename Value<TAnnotationStore>::Type				TAnnotation;
672 	typedef typename TAnnotation::TId							TId;
673 	typedef typename Iterator<TAnnotationStore, Standard>::Type TAnnoIter;
674 
675 	TAnnoIter itBegin = begin(me, Standard());
676 	TAnnoIter itEnd = end(me, Standard());
677 	TId id = (itEnd - itBegin) - 1;
678 	TAnnoIter it = itBegin + id;
679 
680 	for (; itBegin <= it; --it, --id)
681 	{
682 		if ((*it).parentId != TAnnotation::INVALID_ID)
683 		{
684 			TAnnoIter parent = itBegin + (*it).parentId;
685 			if ((*parent).lastChildId == TAnnotation::INVALID_ID)
686 			{
687 				(*parent).lastChildId = id;
688 				(*it).nextSiblingId = id;
689 			}
690 
691 			if ((*it).nextSiblingId == TAnnotation::INVALID_ID)
692 			{
693 				TAnnoIter lastChild = itBegin + (*parent).lastChildId;
694 				(*it).nextSiblingId = (*lastChild).nextSiblingId;
695 				(*lastChild).nextSiblingId = id;
696 			}
697 		}
698 		else
699 			(*it).nextSiblingId = TAnnotation::INVALID_ID;
700 	}
701 }
702 
703 }// namespace SEQAN_NAMESPACE_MAIN
704 
705 #endif //#ifndef SEQAN_HEADER_...
706