1 /*==========================================================================
2 SeqAn - The Library for Sequence Analysis
4 ============================================================================
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 3 of the License, or (at your option) any later version.
12 This library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
17 ============================================================================
18 $Id: string_stack.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_GRAPH_STACK_H
22 #define SEQAN_HEADER_GRAPH_STACK_H
25 //////////////////////////////////////////////////////////////////////////////
27 namespace SEQAN_NAMESPACE_MAIN
30 //////////////////////////////////////////////////////////////////////////////
32 //////////////////////////////////////////////////////////////////////////////
37 ..general:Class.String
38 ..summary:String optimized for push_back, top, and pop (Stack behaviour).
39 ..signature:String<TValue, Block<size> >
40 ..param.TValue:The value type, that is the type of the items/characters stored in the string.
41 ...remarks:Use @Metafunction.Value@ to get the value type for a given class.
42 ..param.size:A positive integer that specifies the number of values in each allocated block.
43 ...remarks: Size should be a power of 2, e.g., 1024.
46 template<unsigned int SPACE = 4096>
49 //////////////////////////////////////////////////////////////////////////////
52 template<typename TValue, unsigned int SPACE>
53 class String<TValue, Block<SPACE> >
55 typedef String<TValue, Array<SPACE> > TBlock;
56 typedef TBlock* PBlock;
57 typedef Allocator< SinglePool<sizeof(TBlock)> > TAllocator;
60 typedef typename Iterator<TBlock, Standard>::Type TBlockIter;
61 typedef String<PBlock> TBlockTable;
64 TBlockIter blockFirst, blockLast; // current block boundaries
65 TBlockIter lastValue; // pointer to top value
68 //____________________________________________________________________________
72 blockFirst(TBlockIter()),
73 blockLast(TBlockIter()),
74 lastValue(TBlockIter()) {}
76 template<typename TSource>
77 String(TSource const& source):
78 blockFirst(TBlockIter()),
79 blockLast(TBlockIter()),
80 lastValue(TBlockIter())
83 assign(*this, source);
86 String(String const & source):
87 blockFirst(TBlockIter()),
88 blockLast(TBlockIter()),
89 lastValue(TBlockIter())
92 assign(*this, source);
95 template<typename TSource>
96 String & operator =(TSource const& source)
99 assign(*this, source);
103 String & operator =(String const& _other)
106 if (this == &_other) return *this;
107 assign(*this, _other);
116 //____________________________________________________________________________
119 template<typename TPos>
120 inline typename Reference<String>::Type
121 operator[] (TPos pos)
124 return value(*this, pos);
127 template<typename TPos>
128 inline typename Reference<String const>::Type
129 operator[] (TPos pos) const
132 return value(*this, pos);
137 template<typename TValue, unsigned int SPACE>
138 struct DefaultOverflowImplicit< String<TValue, Block<SPACE> > >
140 typedef Generous Type;
144 //////////////////////////////////////////////////////////////////////////////
145 // Block metafunctions
146 //////////////////////////////////////////////////////////////////////////////
148 //////////////////////////////////////////////////////////////////////////////
150 //////////////////////////////////////////////////////////////////////////////
152 ///.Metafunction.Iterator.param.T.type:Spec.Block String
154 template<typename TValue, unsigned int SPACE>
155 struct Iterator<String<TValue, Block<SPACE> >, Standard>
157 typedef Iter<String<TValue, Block<SPACE> >, PositionIterator> Type;
160 template<typename TValue, unsigned int SPACE>
161 struct Iterator<String<TValue, Block<SPACE> > const, Standard>
163 typedef Iter<String<TValue, Block<SPACE> > const, PositionIterator> Type;
166 template<typename TValue, unsigned int SPACE>
167 struct Iterator<String<TValue, Block<SPACE> >, Rooted>
169 typedef Iter<String<TValue, Block<SPACE> >, PositionIterator> Type;
172 template<typename TValue, unsigned int SPACE>
173 struct Iterator<String<TValue, Block<SPACE> > const, Rooted>
175 typedef Iter<String<TValue, Block<SPACE> > const, PositionIterator> Type;
179 ///////////////////////////////////////////////////////////////
181 ///////////////////////////////////////////////////////////////
184 //////////////////////////////////////////////////////////////////////////////
186 //////////////////////////////////////////////////////////////////////////////
188 template<typename TValue, unsigned int SPACE, typename TSpec>
189 inline typename Iterator<String<TValue, Block<SPACE> >, Tag<TSpec> const >::Type
190 begin(String<TValue, Block<SPACE> > &me, Tag<TSpec> const)
193 return Iter<String<TValue, Block<SPACE> >, PositionIterator>(me, 0);
196 template<typename TValue, unsigned int SPACE, typename TSpec>
197 inline typename Iterator<String<TValue, Block<SPACE> > const, Tag<TSpec> const>::Type
198 begin(String<TValue, Block<SPACE> > const &me, Tag<TSpec> const)
201 return Iter<String<TValue, Block<SPACE> > const, PositionIterator>(me, 0);
205 template<typename TValue, unsigned int SPACE, typename TSpec>
206 inline typename Iterator<String<TValue, Block<SPACE> >, Tag<TSpec> const >::Type
207 end(String<TValue, Block<SPACE> > &me, Tag<TSpec> const)
210 return Iter<String<TValue, Block<SPACE> >, PositionIterator>(me, length(me));
213 template<typename TValue, unsigned int SPACE, typename TSpec>
214 inline typename Iterator<String<TValue, Block<SPACE> > const, Tag<TSpec> const>::Type
215 end(String<TValue, Block<SPACE> > const &me, Tag<TSpec> const)
218 return Iter<String<TValue, Block<SPACE> > const, PositionIterator>(me, length(me));
221 template<typename TValue, unsigned int SPACE, typename TSource>
224 String<TValue, Block<SPACE> >& target,
225 TSource const& source)
229 typedef typename Iterator<TSource const, Standard>::Type TIter;
230 for(TIter it = begin(source, Standard()); !atEnd(it, source); goNext(it))
235 template<typename TValue, unsigned int SPACE, typename TPos>
236 inline typename Reference<String<TValue, Block<SPACE> > >::Type
238 String<TValue, Block<SPACE> >& stack,
242 return value(*(stack.blocks[pos / SPACE]), pos % SPACE);
245 template<typename TValue, unsigned int SPACE, typename TPos>
246 inline typename Reference<String<TValue, Block<SPACE> > >::Type
248 String<TValue, Block<SPACE> > const& stack,
252 return value(*(stack.blocks[pos / SPACE]), pos % SPACE);
255 template<typename TValue, unsigned int SPACE, typename TIteratorSpec>
258 Iter<String<TValue, Block<SPACE> >, TIteratorSpec>& it,
259 String<TValue, Block<SPACE> >& container)
262 typedef typename Iterator<String<TValue, Block<SPACE> >, Standard>::Type TIter;
263 TIter endIt = end(container, Standard());
264 return (it == endIt);
268 template<typename TValue, unsigned int SPACE>
270 clear(String<TValue, Block<SPACE> >& me)
273 typedef String<TValue, Block<SPACE> > TBlockString;
274 typedef typename TBlockString::TBlockTable TBlockTable;
275 typedef typename Iterator<TBlockTable, Standard>::Type TIter;
277 TIter it = begin(me.blocks), itEnd = end(me.blocks);
278 while (it != itEnd) {
279 deallocate(me.alloc, *it, 1);
283 me.lastValue = me.blockLast = typename TBlockString::TBlockIter();
287 //////////////////////////////////////////////////////////////////////////////
288 ///.Function.reserve.param.object.type:Spec.Block String
290 template <typename TValue, unsigned int SPACE, typename TSize, typename TExpand>
291 inline typename Size< String<TValue, Block<SPACE> > >::Type
293 String<TValue, Block<SPACE> >& me,
295 Tag<TExpand> const tag)
298 reserve(me.blocks, (new_capacity + SPACE - 1) / SPACE, tag);
299 return capacity(me.blocks) * SPACE;
303 template<typename TValue, unsigned int SPACE, typename TSize2, typename TExpand>
304 inline typename Size< String<TValue, Block<SPACE> > >::Type
305 resize(String<TValue, Block<SPACE> > & me,
310 typedef String<TValue, Block<SPACE> > TBlockString;
311 typedef typename Size<TBlockString>::Type TSize;
312 TSize len = length(me);
314 if (new_length > len)
316 for (; len < new_length; ++len) push(me);
318 else if (new_length < len)
320 for (; len > new_length; --len) pop(me);
324 template<typename TValue, unsigned int SPACE, typename TSize2>
325 inline typename Size< String<TValue, Block<SPACE> > >::Type
326 resize(String<TValue, Block<SPACE> > & me,
331 typedef String<TValue, Block<SPACE> > TBlockString;
332 typedef typename Size<TBlockString>::Type TSize;
333 TSize len = length(me);
335 if (new_length > capacity(me)) new_length = capacity(me);
337 if (new_length > len)
340 for (; len < new_length; ++len) push(me, val);
342 else if (new_length < len)
344 for (; len > new_length; --len) pop(me);
350 //dummy implementation
351 template<typename TValue, unsigned int SPACE, typename TSize, typename TExpand>
352 inline typename Size< String<TValue, Block<SPACE> > >::Type
353 reserve(String<TValue, Block<SPACE> > & me,
362 template<typename TValue, unsigned int SPACE, typename TSource, typename TExpand>
365 String<TValue, Block<SPACE> >& me,
366 TSource const& source,
367 Tag<TExpand> const tag)
370 typedef typename Iterator<TSource const, Standard>::Type TIter;
371 for(TIter it = begin(source, Standard()); !atEnd(it, source); goNext(it))
372 appendValue(me, *it);
375 //////////////////////////////////////////////////////////////////////////////
376 ///.Function.appendValue.param.target.type:Spec.Block String
378 template<typename TValue, unsigned int SPACE, typename TVal, typename TExpand>
381 String<TValue, Block<SPACE> >& me,
383 Tag<TExpand> const tag)
386 if (me.lastValue == me.blockLast) {
387 typename Size< String<TValue, Block<SPACE> > >::Type last = length(me.blocks);
389 resize(me.blocks, last + 1, tag);
390 allocate(me.alloc, me.blocks[last], 1);
391 me.lastValue = me.blockFirst = begin(*me.blocks[last]);
392 me.blockLast = (me.blockFirst + (SPACE - 1));
395 valueConstruct(me.lastValue, source);
398 template<typename TValue, unsigned int SPACE, typename TVal>
401 String<TValue, Block<SPACE> >& me,
404 appendValue(me, source);
407 template<typename TValue, unsigned int SPACE>
409 push(String<TValue, Block<SPACE> >& me)
412 if (me.lastValue == me.blockLast) {
413 typename Size< String<TValue, Block<SPACE> > >::Type last = length(me.blocks);
415 resize(me.blocks, last + 1, typename DefaultOverflowImplicit<String<TValue, Block<SPACE> > >::Type());
416 allocate(me.alloc, me.blocks[last], 1);
417 me.lastValue = me.blockFirst = begin(*me.blocks[last]);
418 me.blockLast = (me.blockFirst + (SPACE - 1));
421 valueConstruct(me.lastValue);
424 template<typename TValue, unsigned int SPACE, typename TVal>
427 String<TValue, Block<SPACE> >& me,
430 appendValue(me, source);
433 template<typename TValue, unsigned int SPACE>
435 top(String<TValue, Block<SPACE> > & me)
438 return *me.lastValue;
441 template<typename TValue, unsigned int SPACE>
442 inline TValue const &
443 top(String<TValue, Block<SPACE> > const& me)
446 return *me.lastValue;
449 template<typename TValue, unsigned int SPACE>
451 topPrev(String<TValue, Block<SPACE> > & me)
454 if (me.lastValue != me.blockFirst)
455 return *(me.lastValue - 1);
457 return *(begin(*me.blocks[length(me.blocks) - 1]) + (SPACE - 1));
460 template<typename TValue, unsigned int SPACE>
461 inline TValue const &
462 topPrev(String<TValue, Block<SPACE> > const& me)
465 if (me.lastValue != me.blockFirst)
466 return *(me.lastValue - 1);
468 return *(begin(*me.blocks[length(me.blocks) - 1]) + (SPACE - 1));
471 template<typename TValue, unsigned int SPACE>
473 pop(String<TValue, Block<SPACE> >& me)
476 if (me.lastValue == me.blockFirst) {
477 typename Size< String<TValue, Block<SPACE> > >::Type last = length(me.blocks);
480 valueDestruct(me.lastValue);
481 deallocate(me.alloc, me.blocks[--last], 1);
482 resize(me.blocks, last);
484 me.blockFirst = begin(*me.blocks[--last]);
485 me.lastValue = me.blockLast = (me.blockFirst + (SPACE - 1));
489 valueDestruct(me.lastValue);
494 template<typename TValue, unsigned int SPACE>
496 pop_back(String<TValue, Block<SPACE> >& me) {
500 template<typename TValue, unsigned int SPACE>
502 empty(String<TValue, Block<SPACE> > const& me)
505 return length(me.blocks) == 0;
508 template<typename TValue, unsigned int SPACE>
509 inline typename Size<String<TValue, Block<SPACE> > >::Type
510 length(String<TValue, Block<SPACE> > const & me)
513 if (length(me.blocks))
514 return (length(me.blocks) - 1) * SPACE + (me.lastValue - me.blockFirst) + 1;
519 template<typename TValue, unsigned int SPACE>
520 inline typename Size<String<TValue, Block<SPACE> > >::Type
521 capacity(String<TValue, Block<SPACE> > const & me)
524 if (length(me.blocks))
525 return length(me.blocks) * SPACE;
530 }// namespace SEQAN_NAMESPACE_MAIN
532 #endif //#ifndef SEQAN_HEADER_...