SeqAn-1.1/seqan/sequence/string_alloc.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_alloc.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_SEQUENCE_STRING_ALLOC_H
  22 #define SEQAN_HEADER_SEQUENCE_STRING_ALLOC_H
  23
  24
  25 namespace SEQAN_NAMESPACE_MAIN
  26 {
  27
  28 /**
  29 .Spec.Alloc String:
  30 ..cat:Strings
  31 ..general:Class.String
  32 ..summary:Expandable string that is stored on heap.
  33 ..signature:String<TValue, Alloc<TSpec> >
  34 ..param.TValue:The value type, that is the type of the items/characters stored in the string.
  35 ...remarks:Use @Metafunction.Value@ to get the value type for a given class.
  36 ..param.TSpec:The specializing type.
  37 ...default:$void$
  38 */
  39 //////////////////////////////////////////////////////////////////////////////
  40 //expandable string
  41 //////////////////////////////////////////////////////////////////////////////
  42 //Default: TSpec == void
  43
  44 template <typename TValue>
  45 class String<TValue, Alloc<void> >
  46 {
  47 public:
  48         typename Value<String>::Type * data_begin;
  49         typename Value<String>::Type * data_end;
  50         size_t data_capacity;
  51
  52 //____________________________________________________________________________
  53
  54 public:
  55         String():
  56                 data_begin(0),
  57                 data_end(0),
  58                 data_capacity(0)
  59         {
  60 SEQAN_CHECKPOINT
  61         }
  62
  63         template <typename TSource>
  64         String(TSource & source):
  65                 data_begin(0),
  66                 data_end(0),
  67                 data_capacity(0)
  68         {
  69 SEQAN_CHECKPOINT
  70                 assign(*this, source);
  71         }
  72         template <typename TSource>
  73         String(TSource const & source):
  74                 data_begin(0),
  75                 data_end(0),
  76                 data_capacity(0)
  77         {
  78 SEQAN_CHECKPOINT
  79                 assign(*this, source);
  80         }
  81         String(String const & source):
  82                 data_begin(0),
  83                 data_end(0),
  84                 data_capacity(0)
  85         {
  86 SEQAN_CHECKPOINT
  87                 assign(*this, source);
  88         }
  89         String(String const & source, Move):
  90                 data_begin(0),
  91                 data_end(0),
  92                 data_capacity(0)
  93         {
  94 SEQAN_CHECKPOINT
  95                 move(*this, source);
  96         }
  97         template <typename TSource, typename TSize>
  98         String(TSource & source, TSize limit):
  99                 data_begin(0),
 100                 data_end(0),
 101                 data_capacity(0)
 102         {
 103 SEQAN_CHECKPOINT
 104                 assign(*this, source, limit);
 105         }
 106         template <typename TSource, typename TSize>
 107         String(TSource const & source, TSize limit):
 108                 data_begin(0),
 109                 data_end(0),
 110                 data_capacity(0)
 111         {
 112 SEQAN_CHECKPOINT
 113                 assign(*this, source, limit);
 114         }
 115
 116
 117         template <typename TSource>
 118         String & operator =(TSource const & source)
 119         {
 120 SEQAN_CHECKPOINT
 121                 assign(*this, source);
 122                 return *this;
 123         }
 124         String & operator =(String const & source)
 125         {
 126 SEQAN_CHECKPOINT
 127                 assign(*this, source);
 128                 return *this;
 129         }
 130
 131         ~String()
 132         {
 133 SEQAN_CHECKPOINT
 134                 arrayDestruct(this->data_begin, this->data_end);
 135                 _deallocateStorage(*this, this->data_begin, data_capacity);
 136         }
 137
 138
 139 //____________________________________________________________________________
 140
 141         template <typename TPos>
 142         inline typename Reference<String>::Type
 143         operator [] (TPos pos)
 144         {
 145 SEQAN_CHECKPOINT
 146                 return value(*this, pos);
 147         }
 148
 149         template <typename TPos>
 150         inline typename Reference<String const>::Type
 151         operator [] (TPos pos) const
 152         {
 153 SEQAN_CHECKPOINT
 154                 return value(*this, pos);
 155         }
 156
 157 //____________________________________________________________________________
 158
 159         friend inline typename Iterator<String, Standard>::Type
 160         begin(String & me,
 161                 Standard)
 162         {
 163 SEQAN_CHECKPOINT
 164                 return me.data_begin;
 165         }
 166         friend inline typename Iterator<String const, Standard>::Type
 167         begin(String const & me,
 168                 Standard)
 169         {
 170 SEQAN_CHECKPOINT
 171                 return me.data_begin;
 172         }
 173
 174 //____________________________________________________________________________
 175
 176         friend inline typename Iterator<String, Standard>::Type
 177         end(String & me,
 178                 Standard)
 179         {
 180 SEQAN_CHECKPOINT
 181                 return me.data_end;
 182         }
 183         friend inline typename Iterator<String const, Standard>::Type
 184         end(String const & me,
 185                 Standard)
 186         {
 187 SEQAN_CHECKPOINT
 188                 return me.data_end;
 189         }
 190
 191 //____________________________________________________________________________
 192
 193         friend inline size_t
 194         capacity(String & me)
 195         {
 196 SEQAN_CHECKPOINT
 197                 return me.data_capacity;
 198         }
 199
 200         friend inline size_t
 201         capacity(String const & me)
 202         {
 203 SEQAN_CHECKPOINT
 204                 return me.data_capacity;
 205         }
 206
 207 //____________________________________________________________________________
 208 /* Entwicklungsschrott?
 209         inline void
 210         move(String & target,
 211                  String & source)
 212         {
 213                 clear(target);
 214                 target.data_begin = source.data_begin;
 215                 target.data_end = source.data_end;
 216                 target.data_capacity = source.data_capacity;
 217
 218                 source.data_begin = 0;
 219                 source.data_end = 0;
 220                 source.data_capacity = 0;
 221         }
 222 */
 223 //____________________________________________________________________________
 224
 225 /**
 226 .Internal._setBegin:
 227 */
 228         friend inline void
 229         _setBegin(
 230                 String & me,
 231                 typename Value<String>::Type * new_begin)
 232         {
 233 SEQAN_CHECKPOINT
 234                 me.data_begin = new_begin;
 235         }
 236
 237 //____________________________________________________________________________
 238
 239 /**
 240 .Internal._setLength:
 241 ..cat:Functions
 242 ..summary:Set the length of container.
 243 ..signature:_setLength(object, new_length)
 244 ..param.object:A container.
 245 ..param.object.type:Spec.Alloc String
 246 ..param.new_length:The new length.
 247 */
 248         friend inline void
 249         _setLength(
 250                 String & me,
 251                 size_t new_length)
 252         {
 253 SEQAN_CHECKPOINT
 254                 me.data_end = me.data_begin + new_length;
 255         }
 256
 257 //____________________________________________________________________________
 258
 259 /**
 260 .Internal._setCapacity:
 261 */
 262         friend inline void
 263         _setCapacity(
 264                 String & me,
 265                 size_t new_capacity)
 266         {
 267 SEQAN_CHECKPOINT
 268                 me.data_capacity = new_capacity;
 269         }
 270
 271 //____________________________________________________________________________
 272
 273 /**
 274 .Internal._allocateStorage:
 275 ..cat:Functions
 276 ..summary:Allocates a new buffer for a container.
 277 ..signature:_allocateStorage(object, new_capacity)
 278 ..param.object:A container.
 279 ..param.object.type:Spec.Alloc String
 280 ..param.new_capacity:The capacity of the new allocated buffer.
 281 ..returns:The old butter $object$, that is replaced by the new allocated buffer.
 282 ..remarks:The returned buffer must be deallocated by @Internal._deallocateStorage@.
 283 ..remarks:This function does not construct objects in the allocated buffer.
 284 ..see:Internal._reallocateStorage
 285 */
 286         friend inline typename Value<String>::Type *
 287         _allocateStorage(
 288                 String & me,
 289                 size_t new_capacity)
 290         {
 291 SEQAN_CHECKPOINT
 292                 size_t size = _computeSize4Capacity(me, new_capacity);
 293                 typename Value<String>::Type * return_value = me.data_begin;
 294                 allocate(me, me.data_begin, size, TagAllocateStorage());
 295                 me.data_capacity = new_capacity;
 296                 return return_value;
 297         }
 298
 299         //____________________________________________________________________________
 300
 301 /**
 302 .Internal._deallocateStorage:
 303 ..cat:Functions
 304 ..summary:Deallocates a buffer of a container.
 305 ..signature:_deallocateStorage(object, buffer, capacity)
 306 ..param.object:A container.
 307 ..param.object.type:Spec.Alloc String
 308 ..param.buffer:The buffer that will be deallocated.
 309 ..param.capacity:The capacity of $buffer$.
 310 ..remarks:All objects in the buffer must be destroyed before calling $_deallocateStorage$.
 311 ..see:Internal._allocateStorage
 312 ..see:Internal._reallocateStorage
 313 */
 314         friend inline void
 315         _deallocateStorage(
 316                 String & me,
 317                 typename Value<String>::Type * ptr,
 318                 size_t capacity)
 319         {
 320 SEQAN_CHECKPOINT
 321                 size_t size = _computeSize4Capacity(me, capacity);
 322                 deallocate(me, ptr, size, TagAllocateStorage());
 323         }
 324
 325 //____________________________________________________________________________
 326
 327 };
 328
 329
 330 //////////////////////////////////////////////////////////////////////////////
 331
 332 template <typename TValue, typename TSpec>
 333 struct DefaultOverflowImplicit<String<TValue, Alloc<TSpec> > >
 334 {
 335         typedef Generous Type;
 336 };
 337
 338 template <typename TValue, typename TSpec>
 339 struct DefaultOverflowImplicit<String<TValue, Alloc<TSpec> > const >
 340 {
 341         typedef Generous Type;
 342 };
 343
 344 //////////////////////////////////////////////////////////////////////////////
 345
 346 template <typename TValue, typename TSpec>
 347 struct IsContiguous< String<TValue, Alloc<TSpec> > >
 348 {
 349     typedef True Type;
 350         enum { VALUE = true };
 351 };
 352
 353
 354 //////////////////////////////////////////////////////////////////////////////
 355
 356 template <typename TTargetValue, typename TSourceValue, typename TSpec>
 357 inline void
 358 move(String<TTargetValue, Alloc<TSpec> > & target,
 359          String<TSourceValue, Alloc<TSpec> > & source)
 360 {
 361         _moveContiguous(target, source);
 362 }
 363 template <typename TTargetValue, typename TSourceValue, typename TSpec>
 364 inline void
 365 move(String<TTargetValue, Alloc<TSpec> > & target,
 366          String<TSourceValue, Alloc<TSpec> > const & source)
 367 {
 368         _moveContiguous(target, source);
 369 }
 370
 371 template <typename TValue, typename TSpec>
 372 inline void
 373 move(String<TValue, Alloc<TSpec> > & target,
 374          String<TValue, Alloc<TSpec> > & source)
 375 {
 376         clear(target);
 377         target.data_begin = source.data_begin;
 378         target.data_end = source.data_end;
 379         target.data_capacity = source.data_capacity;
 380
 381         source.data_begin = 0;
 382         source.data_end = 0;
 383         source.data_capacity = 0;
 384 }
 385 template <typename TValue, typename TSpec>
 386 inline void
 387 move(String<TValue, Alloc<TSpec> > & target,
 388          String<TValue, Alloc<TSpec> > const & source)
 389 {
 390         clear(target);
 391         target.data_begin = source.data_begin;
 392         target.data_end = source.data_end;
 393         target.data_capacity = source.data_capacity;
 394
 395         source.data_begin = 0;
 396         source.data_end = 0;
 397         source.data_capacity = 0;
 398 }
 399
 400 //////////////////////////////////////////////////////////////////////////////
 401
 402 ///.Function.reserve.param.object.type:Spec.Alloc String
 403
 404 template <typename TValue, typename TSpec, typename _TSize, typename TExpand>
 405 inline typename Size< String<TValue, Alloc<TSpec> > >::Type
 406 reserve(
 407         String<TValue, Alloc<TSpec> > & seq,
 408         _TSize new_capacity,
 409         Tag<TExpand> const tag)
 410 {
 411 SEQAN_CHECKPOINT
 412         typedef typename Size< String<TValue, Alloc<TSpec> > >::Type TSize;
 413
 414         TSize old_capacity = capacity(seq);
 415         if (old_capacity >= (TSize)new_capacity) return new_capacity;
 416
 417         TSize seq_length = length(seq);
 418         typename Value< String<TValue, Alloc<TSpec> > >::Type * old_array = _reallocateStorage(seq, new_capacity, tag);
 419         if (old_array)
 420         {//buffer was replaced, destruct old buffer
 421                 arrayConstructCopy(old_array, old_array + seq_length, begin(seq, Standard()));
 422                 arrayDestruct(old_array, old_array + seq_length);
 423                 _deallocateStorage(seq, old_array, old_capacity);
 424                 _setLength(seq, seq_length);
 425         }
 426         else if (!old_capacity)
 427         {//new buffer created and the string had no buffer yet
 428                 _setLength(seq, seq_length);
 429         }
 430         return new_capacity;
 431 }
 432
 433 template <typename TValue, typename TSpec, typename _TSize>
 434 inline typename Size< String<TValue, Alloc<TSpec> > >::Type
 435 reserve(
 436         String<TValue, Alloc<TSpec> > & me,
 437         _TSize new_capacity,
 438         Limit)
 439 {
 440 SEQAN_CHECKPOINT
 441         typedef typename Size< String<TValue, Alloc<TSpec> > >::Type TSize;
 442
 443         TSize me_capacity = capacity(me);
 444         if (me_capacity < (TSize)new_capacity) return me_capacity;
 445         return new_capacity;
 446 }
 447
 448 template <typename TValue, typename TSpec, typename _TSize>
 449 inline typename Size< String<TValue, Alloc<TSpec> > >::Type
 450 reserve(
 451         String<TValue, Alloc<TSpec> > & /*me*/,
 452         _TSize new_capacity,
 453         Insist)
 454 {
 455 SEQAN_CHECKPOINT
 456         typedef typename Size< String<TValue, Alloc<TSpec> > >::Type TSize;
 457
 458         return new_capacity;
 459 }
 460
 461 //////////////////////////////////////////////////////////////////////////////
 462
 463
 464
 465 } //namespace SEQAN_NAMESPACE_MAIN
 466
 467 #endif //#ifndef SEQAN_HEADER_...