SeqAn-1.1/seqan/sequence/string_stack.h

   1  /*==========================================================================
   2                 SeqAn - The Library for Sequence Analysis
   3                           http://www.seqan.de
   4  ============================================================================
   5   Copyright (C) 2007
   6
   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.
  11
  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.
  16
  17  ============================================================================
  18   $Id: string_stack.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_GRAPH_STACK_H
  22 #define SEQAN_HEADER_GRAPH_STACK_H
  23
  24
  25 //////////////////////////////////////////////////////////////////////////////
  26
  27 namespace SEQAN_NAMESPACE_MAIN
  28 {
  29
  30 //////////////////////////////////////////////////////////////////////////////
  31 // TAGS
  32 //////////////////////////////////////////////////////////////////////////////
  33
  34 /**
  35 .Spec.Block String:
  36 ..cat:Strings
  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.
  44 */
  45
  46         template<unsigned int SPACE = 4096>
  47         struct Block;
  48
  49 //////////////////////////////////////////////////////////////////////////////
  50
  51
  52         template<typename TValue, unsigned int SPACE>
  53         class String<TValue, Block<SPACE> >
  54         {
  55                 typedef String<TValue, Array<SPACE> >                           TBlock;
  56                 typedef TBlock*                                                                         PBlock;
  57                 typedef Allocator< SinglePool<sizeof(TBlock)> >         TAllocator;
  58
  59         public:
  60                 typedef typename Iterator<TBlock, Standard>::Type       TBlockIter;
  61                 typedef String<PBlock>                                                          TBlockTable;
  62
  63                 TBlockTable             blocks;
  64                 TBlockIter              blockFirst, blockLast;  // current block boundaries
  65                 TBlockIter              lastValue;                              // pointer to top value
  66                 TAllocator              alloc;
  67
  68         //____________________________________________________________________________
  69
  70                 public:
  71                         String():
  72                                 blockFirst(TBlockIter()),
  73                                 blockLast(TBlockIter()),
  74                                 lastValue(TBlockIter()) {}
  75
  76                         template<typename TSource>
  77                         String(TSource const& source):
  78                                 blockFirst(TBlockIter()),
  79                                 blockLast(TBlockIter()),
  80                                 lastValue(TBlockIter())
  81                         {
  82                         SEQAN_CHECKPOINT
  83                                 assign(*this, source);
  84                         }
  85
  86                         String(String const & source):
  87                                 blockFirst(TBlockIter()),
  88                                 blockLast(TBlockIter()),
  89                                 lastValue(TBlockIter())
  90                         {
  91                         SEQAN_CHECKPOINT
  92                                 assign(*this, source);
  93                         }
  94
  95                         template<typename TSource>
  96                         String & operator =(TSource const& source)
  97                         {
  98                         SEQAN_CHECKPOINT
  99                                 assign(*this, source);
 100                                 return *this;
 101                         }
 102
 103                         String & operator =(String const& _other)
 104                         {
 105                         SEQAN_CHECKPOINT
 106                                 if (this == &_other) return *this;
 107                                 assign(*this, _other);
 108                                 return *this;
 109                         }
 110
 111                         ~String()
 112                         {
 113                                 clear(*this);
 114                         }
 115
 116         //____________________________________________________________________________
 117
 118                 public:
 119                         template<typename TPos>
 120                         inline typename Reference<String>::Type
 121                                 operator[] (TPos pos)
 122                         {
 123                         SEQAN_CHECKPOINT
 124                                 return value(*this, pos);
 125                         }
 126
 127                         template<typename TPos>
 128                         inline typename Reference<String const>::Type
 129                                 operator[] (TPos pos) const
 130                         {
 131                         SEQAN_CHECKPOINT
 132                                 return value(*this, pos);
 133                         }
 134         };
 135
 136
 137         template<typename TValue, unsigned int SPACE>
 138         struct DefaultOverflowImplicit< String<TValue, Block<SPACE> > >
 139         {
 140                 typedef Generous Type;
 141         };
 142
 143
 144 //////////////////////////////////////////////////////////////////////////////
 145 // Block metafunctions
 146 //////////////////////////////////////////////////////////////////////////////
 147
 148 //////////////////////////////////////////////////////////////////////////////
 149 // Iterators
 150 //////////////////////////////////////////////////////////////////////////////
 151
 152 ///.Metafunction.Iterator.param.T.type:Spec.Block String
 153
 154         template<typename TValue, unsigned int SPACE>
 155         struct Iterator<String<TValue, Block<SPACE> >, Standard>
 156         {
 157                 typedef Iter<String<TValue, Block<SPACE> >, PositionIterator> Type;
 158         };
 159
 160         template<typename TValue, unsigned int SPACE>
 161         struct Iterator<String<TValue, Block<SPACE> > const, Standard>
 162         {
 163                 typedef Iter<String<TValue, Block<SPACE> > const, PositionIterator> Type;
 164         };
 165
 166         template<typename TValue, unsigned int SPACE>
 167         struct Iterator<String<TValue, Block<SPACE> >, Rooted>
 168         {
 169                 typedef Iter<String<TValue, Block<SPACE> >, PositionIterator> Type;
 170         };
 171
 172         template<typename TValue, unsigned int SPACE>
 173         struct Iterator<String<TValue, Block<SPACE> > const, Rooted>
 174         {
 175                 typedef Iter<String<TValue, Block<SPACE> > const, PositionIterator> Type;
 176         };
 177
 178
 179 ///////////////////////////////////////////////////////////////
 180 // Block interface
 181 ///////////////////////////////////////////////////////////////
 182
 183
 184 //////////////////////////////////////////////////////////////////////////////
 185 // begin
 186 //////////////////////////////////////////////////////////////////////////////
 187
 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)
 191         {
 192         SEQAN_CHECKPOINT
 193                 return Iter<String<TValue, Block<SPACE> >, PositionIterator>(me, 0);
 194         }
 195
 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)
 199         {
 200         SEQAN_CHECKPOINT
 201                 return Iter<String<TValue, Block<SPACE> > const, PositionIterator>(me, 0);
 202         }
 203
 204
 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)
 208         {
 209         SEQAN_CHECKPOINT
 210                 return Iter<String<TValue, Block<SPACE> >, PositionIterator>(me, length(me));
 211         }
 212
 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)
 216         {
 217         SEQAN_CHECKPOINT
 218                 return Iter<String<TValue, Block<SPACE> > const, PositionIterator>(me, length(me));
 219         }
 220
 221         template<typename TValue, unsigned int SPACE, typename TSource>
 222         inline void
 223         assign(
 224                 String<TValue, Block<SPACE> >& target,
 225                 TSource const& source)
 226         {
 227         SEQAN_CHECKPOINT
 228                 clear(target);
 229                 typedef typename Iterator<TSource const, Standard>::Type TIter;
 230                 for(TIter it = begin(source, Standard()); !atEnd(it, source); goNext(it))
 231                         push(target, *it);
 232         }
 233
 234
 235         template<typename TValue, unsigned int SPACE, typename TPos>
 236         inline typename Reference<String<TValue, Block<SPACE> > >::Type
 237         value(
 238                 String<TValue, Block<SPACE> >& stack,
 239                 TPos const pos)
 240         {
 241         SEQAN_CHECKPOINT
 242                 return value(*(stack.blocks[pos / SPACE]), pos % SPACE);
 243         }
 244
 245         template<typename TValue, unsigned int SPACE, typename TPos>
 246         inline typename Reference<String<TValue, Block<SPACE> > >::Type
 247         value(
 248                 String<TValue, Block<SPACE> > const& stack,
 249                 TPos const pos)
 250         {
 251         SEQAN_CHECKPOINT
 252                 return value(*(stack.blocks[pos / SPACE]), pos % SPACE);
 253         }
 254
 255         template<typename TValue, unsigned int SPACE, typename TIteratorSpec>
 256         inline bool
 257         atEnd(
 258                 Iter<String<TValue, Block<SPACE> >, TIteratorSpec>& it,
 259                 String<TValue, Block<SPACE> >& container)
 260         {
 261         SEQAN_CHECKPOINT
 262                 typedef typename Iterator<String<TValue, Block<SPACE> >, Standard>::Type TIter;
 263                 TIter endIt = end(container, Standard());
 264                 return (it == endIt);
 265         }
 266
 267
 268         template<typename TValue, unsigned int SPACE>
 269         inline void
 270         clear(String<TValue, Block<SPACE> >& me)
 271         {
 272         SEQAN_CHECKPOINT
 273                 typedef String<TValue, Block<SPACE>     >                       TBlockString;
 274                 typedef typename TBlockString::TBlockTable              TBlockTable;
 275                 typedef typename Iterator<TBlockTable, Standard>::Type  TIter;
 276
 277                 TIter it = begin(me.blocks), itEnd = end(me.blocks);
 278                 while (it != itEnd) {
 279                         deallocate(me.alloc, *it, 1);
 280                         ++it;
 281                 }
 282                 clear(me.blocks);
 283                 me.lastValue = me.blockLast = typename TBlockString::TBlockIter();
 284         }
 285
 286
 287 //////////////////////////////////////////////////////////////////////////////
 288 ///.Function.reserve.param.object.type:Spec.Block String
 289 /*
 290         template <typename TValue, unsigned int SPACE, typename TSize, typename TExpand>
 291         inline typename Size< String<TValue, Block<SPACE> > >::Type
 292         reserve(
 293                 String<TValue, Block<SPACE> >& me,
 294                 TSize new_capacity,
 295                 Tag<TExpand> const tag)
 296         {
 297         SEQAN_CHECKPOINT
 298                 reserve(me.blocks, (new_capacity + SPACE - 1) / SPACE, tag);
 299                 return capacity(me.blocks) * SPACE;
 300         }
 301 */
 302
 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,
 306                 TSize2 new_length,
 307                 Tag<TExpand> const)
 308         {
 309         SEQAN_CHECKPOINT
 310                 typedef String<TValue, Block<SPACE>     >                       TBlockString;
 311                 typedef typename Size<TBlockString>::Type               TSize;
 312                 TSize len = length(me);
 313
 314                 if (new_length > len)
 315                 {
 316                         for (; len < new_length; ++len) push(me);
 317                 }
 318                 else if (new_length < len)
 319                 {
 320                         for (; len > new_length; --len) pop(me);
 321                 }
 322                 return new_length;
 323         }
 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,
 327                 TSize2 new_length,
 328                 Limit)
 329         {
 330         SEQAN_CHECKPOINT
 331                 typedef String<TValue, Block<SPACE>     >                       TBlockString;
 332                 typedef typename Size<TBlockString>::Type               TSize;
 333                 TSize len = length(me);
 334
 335                 if (new_length > capacity(me)) new_length = capacity(me);
 336
 337                 if (new_length > len)
 338                 {
 339                         TValue val;
 340                         for (; len < new_length; ++len) push(me, val);
 341                 }
 342                 else if (new_length < len)
 343                 {
 344                         for (; len > new_length; --len) pop(me);
 345                 }
 346                 return new_length;
 347         }
 348
 349
 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,
 354                 TSize new_capacity,
 355                 Tag<TExpand> const)
 356         {
 357         SEQAN_CHECKPOINT
 358                 return new_capacity;
 359         }
 360
 361
 362         template<typename TValue, unsigned int SPACE, typename TSource, typename TExpand>
 363         inline void
 364         append(
 365                 String<TValue, Block<SPACE> >& me,
 366                 TSource const& source,
 367                 Tag<TExpand> const tag)
 368         {
 369         SEQAN_CHECKPOINT
 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);
 373         }
 374
 375 //////////////////////////////////////////////////////////////////////////////
 376 ///.Function.appendValue.param.target.type:Spec.Block String
 377
 378         template<typename TValue, unsigned int SPACE, typename TVal, typename TExpand>
 379         inline void
 380         appendValue(
 381                 String<TValue, Block<SPACE> >& me,
 382                 TVal const& source,
 383                 Tag<TExpand> const tag)
 384         {
 385         SEQAN_CHECKPOINT
 386                 if (me.lastValue == me.blockLast) {
 387                         typename Size< String<TValue, Block<SPACE> > >::Type last = length(me.blocks);
 388
 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));
 393                 } else
 394                         ++me.lastValue;
 395                 valueConstruct(me.lastValue, source);
 396         }
 397
 398         template<typename TValue, unsigned int SPACE, typename TVal>
 399         inline void
 400         push(
 401                 String<TValue, Block<SPACE> >& me,
 402                 TVal const& source)
 403         {
 404                 appendValue(me, source);
 405         }
 406
 407         template<typename TValue, unsigned int SPACE>
 408         inline void
 409         push(String<TValue, Block<SPACE> >& me)
 410         {
 411         SEQAN_CHECKPOINT
 412                 if (me.lastValue == me.blockLast) {
 413                         typename Size< String<TValue, Block<SPACE> > >::Type last = length(me.blocks);
 414
 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));
 419                 } else
 420                         ++me.lastValue;
 421                 valueConstruct(me.lastValue);
 422         }
 423
 424         template<typename TValue, unsigned int SPACE, typename TVal>
 425         inline void
 426         push_back(
 427                 String<TValue, Block<SPACE> >& me,
 428                 TVal const& source)
 429         {
 430                 appendValue(me, source);
 431         }
 432
 433         template<typename TValue, unsigned int SPACE>
 434         inline TValue &
 435         top(String<TValue, Block<SPACE> > & me)
 436         {
 437         SEQAN_CHECKPOINT
 438                 return *me.lastValue;
 439         }
 440
 441         template<typename TValue, unsigned int SPACE>
 442         inline TValue const &
 443         top(String<TValue, Block<SPACE> > const& me)
 444         {
 445         SEQAN_CHECKPOINT
 446                 return *me.lastValue;
 447         }
 448
 449         template<typename TValue, unsigned int SPACE>
 450         inline TValue &
 451         topPrev(String<TValue, Block<SPACE> > & me)
 452         {
 453         SEQAN_CHECKPOINT
 454                 if (me.lastValue != me.blockFirst)
 455                         return *(me.lastValue - 1);
 456                 else
 457                         return *(begin(*me.blocks[length(me.blocks) - 1]) + (SPACE - 1));
 458         }
 459
 460         template<typename TValue, unsigned int SPACE>
 461         inline TValue const &
 462         topPrev(String<TValue, Block<SPACE> > const& me)
 463         {
 464         SEQAN_CHECKPOINT
 465                 if (me.lastValue != me.blockFirst)
 466                         return *(me.lastValue - 1);
 467                 else
 468                         return *(begin(*me.blocks[length(me.blocks) - 1]) + (SPACE - 1));
 469         }
 470
 471         template<typename TValue, unsigned int SPACE>
 472         inline void
 473         pop(String<TValue, Block<SPACE> >& me)
 474         {
 475         SEQAN_CHECKPOINT
 476                 if (me.lastValue == me.blockFirst) {
 477                         typename Size< String<TValue, Block<SPACE> > >::Type last = length(me.blocks);
 478
 479                         if (last) {
 480                                 valueDestruct(me.lastValue);
 481                                 deallocate(me.alloc, me.blocks[--last], 1);
 482                                 resize(me.blocks, last);
 483                                 if (last) {
 484                                         me.blockFirst = begin(*me.blocks[--last]);
 485                                         me.lastValue = me.blockLast = (me.blockFirst + (SPACE - 1));
 486                                 }
 487                         }
 488                 } else {
 489                         valueDestruct(me.lastValue);
 490                         --me.lastValue;
 491                 }
 492         }
 493
 494         template<typename TValue, unsigned int SPACE>
 495         inline void
 496         pop_back(String<TValue, Block<SPACE> >& me) {
 497                 pop(me);
 498         }
 499
 500         template<typename TValue, unsigned int SPACE>
 501         inline bool
 502         empty(String<TValue, Block<SPACE> > const& me)
 503         {
 504         SEQAN_CHECKPOINT
 505                 return length(me.blocks) == 0;
 506         }
 507
 508         template<typename TValue, unsigned int SPACE>
 509         inline typename Size<String<TValue, Block<SPACE> > >::Type
 510         length(String<TValue, Block<SPACE> > const & me)
 511         {
 512         SEQAN_CHECKPOINT
 513                 if (length(me.blocks))
 514                         return (length(me.blocks) - 1) * SPACE + (me.lastValue - me.blockFirst) + 1;
 515                 else
 516                         return 0;
 517         }
 518
 519         template<typename TValue, unsigned int SPACE>
 520         inline typename Size<String<TValue, Block<SPACE> > >::Type
 521         capacity(String<TValue, Block<SPACE> > const & me)
 522         {
 523         SEQAN_CHECKPOINT
 524                 if (length(me.blocks))
 525                         return length(me.blocks) * SPACE;
 526                 else
 527                         return 0;
 528         }
 529
 530 }// namespace SEQAN_NAMESPACE_MAIN
 531
 532 #endif //#ifndef SEQAN_HEADER_...