git.cworth.org Git - vogl/blob - src/extlib/loki/include/loki/flex/flex_string_shell.h

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // flex_string
   3 // Copyright (c) 2001 by Andrei Alexandrescu
   4 // Permission to use, copy, modify, distribute and sell this software for any
   5 //     purpose is hereby granted without fee, provided that the above copyright
   6 //     notice appear in all copies and that both that copyright notice and this
   7 //     permission notice appear in supporting documentation.
   8 // The author makes no representations about the
   9 //     suitability of this software for any purpose. It is provided "as is"
  10 //     without express or implied warranty.
  11 ////////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef FLEX_STRING_SHELL_INC_
  14 #define FLEX_STRING_SHELL_INC_
  15
  16 // $Id: flex_string_shell.h 948 2009-01-26 01:55:50Z rich_sposato $
  17
  18
  19 ///////////////////////////////////////////////////////////////////////////////
  20 // class template flex_string
  21 // This file does not include any storage policy headers
  22 ///////////////////////////////////////////////////////////////////////////////
  23
  24 #include <memory>
  25 #include <algorithm>
  26 #include <functional>
  27 #include <cassert>
  28 #include <limits>
  29 #include <stdexcept>
  30 #include "flex_string_details.h"
  31 #include <string>
  32
  33 // Forward declaration for default storage policy
  34 template <typename E, class A> class AllocatorStringStorage;
  35
  36
  37 template <class T> class mallocator
  38 {
  39 public:
  40         typedef T                 value_type;
  41         typedef value_type       *pointer;
  42         typedef const value_type *const_pointer;
  43         typedef value_type       &reference;
  44         typedef const value_type &const_reference;
  45         typedef std::size_t       size_type;
  46         //typedef unsigned int      size_type;
  47         //typedef std::ptrdiff_t    difference_type;
  48         typedef int               difference_type;
  49
  50         template <class U>
  51         struct rebind
  52         {
  53                 typedef mallocator<U> other;
  54         };
  55
  56         mallocator() {}
  57         mallocator(const mallocator &) {}
  58         //template <class U>
  59         //mallocator(const mallocator<U>&) {}
  60         ~mallocator() {}
  61
  62         pointer address(reference x) const
  63         {
  64                 return &x;
  65         }
  66         const_pointer address(const_reference x) const
  67         {
  68                 return x;
  69         }
  70
  71         pointer allocate(size_type n, const_pointer = 0)
  72         {
  73                 using namespace std;
  74                 void *p = malloc(n * sizeof(T));
  75                 if (!p) throw bad_alloc();
  76                 return static_cast<pointer>(p);
  77         }
  78
  79         void deallocate(pointer p, size_type)
  80         {
  81                 using namespace std;
  82                 free(p);
  83         }
  84
  85         size_type max_size() const
  86         {
  87                 return static_cast<size_type>(-1) / sizeof(T);
  88         }
  89
  90         void construct(pointer p, const value_type &x)
  91         {
  92                 new(p) value_type(x);
  93         }
  94
  95         void destroy(pointer p)
  96         {
  97                 p->~value_type();
  98         }
  99
 100 private:
 101         void operator=(const mallocator &);
 102 };
 103
 104 template<> class mallocator<void>
 105 {
 106         typedef void        value_type;
 107         typedef void       *pointer;
 108         typedef const void *const_pointer;
 109
 110         template <class U>
 111         struct rebind
 112         {
 113                 typedef mallocator<U> other;
 114         };
 115 };
 116
 117 template <class T>
 118 inline bool operator==(const mallocator<T>&,
 119                        const mallocator<T>&)
 120 {
 121         return true;
 122 }
 123
 124 template <class T>
 125 inline bool operator!=(const mallocator<T>&,
 126                        const mallocator<T>&)
 127 {
 128         return false;
 129 }
 130
 131 template <class Allocator>
 132 typename Allocator::pointer Reallocate(
 133     Allocator &alloc,
 134     typename Allocator::pointer p,
 135     typename Allocator::size_type oldObjCount,
 136     typename Allocator::size_type newObjCount,
 137     void *)
 138 {
 139         // @@@ not implemented
 140 }
 141
 142 template <class Allocator>
 143 typename Allocator::pointer Reallocate(
 144     Allocator &alloc,
 145     typename Allocator::pointer p,
 146     typename Allocator::size_type oldObjCount,
 147     typename Allocator::size_type newObjCount,
 148     mallocator<void>*)
 149 {
 150         // @@@ not implemented
 151 }
 152
 153
 154 ////////////////////////////////////////////////////////////////////////////////
 155 // class template flex_string
 156 // a std::basic_string compatible implementation
 157 // Uses a Storage policy
 158 ////////////////////////////////////////////////////////////////////////////////
 159
 160 template <typename E,
 161          class T = std::char_traits<E>,
 162          class A = std::allocator<E>,
 163          class Storage = AllocatorStringStorage<E, A> >
 164 class flex_string : private Storage
 165 {
 166
 167         template <typename Exception>
 168         static void Enforce(bool condition, Exception *, const char *msg)
 169         {
 170                 if (!condition) throw Exception(msg);
 171         }
 172
 173         bool Sane() const
 174         {
 175                 return
 176                     begin() <= end() &&
 177                     empty() == (size() == 0) &&
 178                     empty() == (begin() == end()) &&
 179                     size() <= max_size() &&
 180                     capacity() <= max_size() &&
 181                     size() <= capacity();
 182         }
 183
 184         struct Invariant;
 185         friend struct Invariant;
 186         struct Invariant
 187         {
 188 #ifndef NDEBUG
 189                 Invariant(const flex_string &s) : s_(s)
 190                 {
 191                         assert(s_.Sane());
 192                 }
 193                 ~Invariant()
 194                 {
 195                         assert(s_.Sane());
 196                 }
 197         private:
 198                 const flex_string &s_;
 199 #else
 200                 Invariant(const flex_string &) {}
 201 #endif
 202                 Invariant &operator=(const Invariant &);
 203         };
 204
 205 public:
 206         // types
 207         typedef T traits_type;
 208         typedef typename traits_type::char_type value_type;
 209         typedef A allocator_type;
 210         typedef typename A::size_type size_type;
 211         typedef typename A::difference_type difference_type;
 212
 213         typedef typename Storage::reference reference;
 214         typedef typename A::const_reference const_reference;
 215         typedef typename A::pointer pointer;
 216         typedef typename A::const_pointer const_pointer;
 217
 218         typedef typename Storage::iterator iterator;
 219         typedef typename Storage::const_iterator const_iterator;
 220         typedef std::reverse_iterator<iterator
 221 #ifdef NO_ITERATOR_TRAITS
 222         , value_type
 223 #endif
 224         > reverse_iterator;
 225         typedef std::reverse_iterator<const_iterator
 226 #ifdef NO_ITERATOR_TRAITS
 227         , const value_type
 228 #endif
 229         > const_reverse_iterator;
 230
 231         static const size_type npos;    // = size_type(-1)
 232
 233 private:
 234         static size_type Min(size_type lhs, size_type rhs)
 235         {
 236                 return lhs < rhs ? lhs : rhs;
 237         }
 238         static size_type Max(size_type lhs, size_type rhs)
 239         {
 240                 return lhs > rhs ? lhs : rhs;
 241         }
 242         static void Procust(size_type &n, size_type nmax)
 243         {
 244                 if (n > nmax) n = nmax;
 245         }
 246
 247 public:
 248         // 21.3.1 construct/copy/destroy
 249         explicit flex_string(const A &a = A())
 250                 : Storage(a)
 251         {}
 252
 253         flex_string(const flex_string &str)
 254                 : Storage(str)
 255         {}
 256
 257         flex_string(const flex_string &str, size_type pos,
 258                     size_type n = npos, const A &a = A())
 259                 : Storage(a)
 260         {
 261                 assign(str, pos, n);
 262         }
 263
 264         flex_string(const value_type *s, const A &a = A())
 265                 : Storage(s, traits_type::length(s), a)
 266         {}
 267
 268         flex_string(const value_type *s, size_type n, const A &a = A())
 269                 : Storage(s, n, a)
 270         {}
 271
 272         flex_string(size_type n, value_type c, const A &a = A())
 273                 : Storage(n, c, a)
 274         {}
 275
 276         template <class InputIterator>
 277         flex_string(InputIterator begin, InputIterator end, const A &a = A())
 278                 : Storage(a)
 279         {
 280                 assign(begin, end);
 281         }
 282
 283         ~flex_string()
 284         {}
 285
 286         flex_string &operator=(const flex_string &str)
 287         {
 288                 Storage &s = *this;
 289                 s = str;
 290                 return *this;
 291         }
 292
 293         flex_string &operator=(const value_type *s)
 294         {
 295                 assign(s);
 296                 return *this;
 297         }
 298
 299         flex_string &operator=(value_type c)
 300         {
 301                 assign(1, c);
 302                 return *this;
 303         }
 304
 305         // 21.3.2 iterators:
 306         iterator begin()
 307         {
 308                 return Storage::begin();
 309         }
 310
 311         const_iterator begin() const
 312         {
 313                 return Storage::begin();
 314         }
 315
 316         iterator end()
 317         {
 318                 return Storage::end();
 319         }
 320
 321         const_iterator end() const
 322         {
 323                 return Storage::end();
 324         }
 325
 326         reverse_iterator rbegin()
 327         {
 328                 return reverse_iterator(end());
 329         }
 330
 331         const_reverse_iterator rbegin() const
 332         {
 333                 return const_reverse_iterator(end());
 334         }
 335
 336         reverse_iterator rend()
 337         {
 338                 return reverse_iterator(begin());
 339         }
 340
 341         const_reverse_iterator rend() const
 342         {
 343                 return const_reverse_iterator(begin());
 344         }
 345
 346         // 21.3.3 capacity:
 347         size_type size() const
 348         {
 349                 return Storage::size();
 350         }
 351
 352         size_type length() const
 353         {
 354                 return size();
 355         }
 356
 357         size_type max_size() const
 358         {
 359                 return Storage::max_size();
 360         }
 361
 362         void resize(size_type n, value_type c)
 363         {
 364                 Storage::resize(n, c);
 365         }
 366
 367         void resize(size_type n)
 368         {
 369                 resize(n, value_type());
 370         }
 371
 372         size_type capacity() const
 373         {
 374                 return Storage::capacity();
 375         }
 376
 377         void reserve(size_type res_arg = 0)
 378         {
 379                 Enforce(res_arg <= max_size(), static_cast<std::length_error *>(0), "");
 380                 Storage::reserve(res_arg);
 381         }
 382
 383         void clear()
 384         {
 385                 resize(0);
 386         }
 387
 388         bool empty() const
 389         {
 390                 return size() == 0;
 391         }
 392
 393         // 21.3.4 element access:
 394         const_reference operator[](size_type pos) const
 395         {
 396                 return *(c_str() + pos);
 397         }
 398
 399         reference operator[](size_type pos)
 400         {
 401                 return *(begin() + pos);
 402         }
 403
 404         const_reference at(size_type n) const
 405         {
 406                 Enforce(n <= size(), static_cast<std::out_of_range *>(0), "");
 407                 return (*this)[n];
 408         }
 409
 410         reference at(size_type n)
 411         {
 412                 Enforce(n < size(), static_cast<std::out_of_range *>(0), "");
 413                 return (*this)[n];
 414         }
 415
 416         // 21.3.5 modifiers:
 417         flex_string &operator+=(const flex_string &str)
 418         {
 419                 return append(str);
 420         }
 421
 422         flex_string &operator+=(const value_type *s)
 423         {
 424                 return append(s);
 425         }
 426
 427         flex_string &operator+=(const value_type c)
 428         {
 429                 push_back(c);
 430                 return *this;
 431         }
 432
 433         flex_string &append(const flex_string &str)
 434         {
 435                 return append(str.data(), str.length());
 436         }
 437
 438         flex_string &append(const flex_string &str, const size_type pos,
 439                             size_type n)
 440         {
 441                 const size_type sz = str.size();
 442                 Enforce(pos <= sz, static_cast<std::out_of_range *>(0), "");
 443                 Procust(n, sz - pos);
 444                 return append(str.data() + pos, n);
 445         }
 446
 447         flex_string &append(const value_type *s, const size_type n)
 448         {
 449                 Invariant checker(*this);
 450                 (void) checker;
 451                 static std::less_equal<const value_type *> le;
 452                 if (le(&*begin(), s) && le(s, &*end())) // aliasing
 453                 {
 454                         const size_type offset = s - &*begin();
 455                         Storage::reserve(size() + n);
 456                         s = &*begin() + offset;
 457                 }
 458                 Storage::append(s, s + n);
 459                 return *this;
 460         }
 461
 462         flex_string &append(const value_type *s)
 463         {
 464                 return append(s, traits_type::length(s));
 465         }
 466
 467         flex_string &append(size_type n, value_type c)
 468         {
 469                 resize(size() + n, c);
 470                 return *this;
 471         }
 472
 473         template<class InputIterator>
 474         flex_string &append(InputIterator first, InputIterator last)
 475         {
 476                 insert(end(), first, last);
 477                 return *this;
 478         }
 479
 480         void push_back(const value_type c) // primitive
 481         {
 482                 const size_type cap = capacity();
 483                 if (size() == cap)
 484                 {
 485                         reserve(cap << 1u);
 486                 }
 487                 Storage::append(&c, &c + 1);
 488         }
 489
 490         flex_string &assign(const flex_string &str)
 491         {
 492                 if (&str == this) return *this;
 493                 return assign(str.data(), str.size());
 494         }
 495
 496         flex_string &assign(const flex_string &str, const size_type pos,
 497                             size_type n)
 498         {
 499                 const size_type sz = str.size();
 500                 Enforce(pos <= sz, static_cast<std::out_of_range *>(0), "");
 501                 Procust(n, sz - pos);
 502                 return assign(str.data() + pos, n);
 503         }
 504
 505         flex_string &assign(const value_type *s, const size_type n)
 506         {
 507                 Invariant checker(*this);
 508                 (void) checker;
 509                 if (size() >= n)
 510                 {
 511                         std::copy(s, s + n, begin());
 512                         resize(n);
 513                 }
 514                 else
 515                 {
 516                         const value_type *const s2 = s + size();
 517                         std::copy(s, s2, begin());
 518                         append(s2, n - size());
 519                 }
 520                 return *this;
 521         }
 522
 523         flex_string &assign(const value_type *s)
 524         {
 525                 return assign(s, traits_type::length(s));
 526         }
 527
 528         template <class ItOrLength, class ItOrChar>
 529         flex_string &assign(ItOrLength first_or_n, ItOrChar last_or_c)
 530         {
 531                 return replace(begin(), end(), first_or_n, last_or_c);
 532         }
 533
 534         flex_string &insert(size_type pos1, const flex_string &str)
 535         {
 536                 return insert(pos1, str.data(), str.size());
 537         }
 538
 539         flex_string &insert(size_type pos1, const flex_string &str,
 540                             size_type pos2, size_type n)
 541         {
 542                 Enforce(pos2 <= str.length(), static_cast<std::out_of_range *>(0), "");
 543                 Procust(n, str.length() - pos2);
 544                 return insert(pos1, str.data() + pos2, n);
 545         }
 546
 547         flex_string &insert(size_type pos, const value_type *s, size_type n)
 548         {
 549                 Enforce(pos <= length(), static_cast<std::out_of_range *>(0), "");
 550                 insert(begin() + pos, s, s + n);
 551                 return *this;
 552         }
 553
 554         flex_string &insert(size_type pos, const value_type *s)
 555         {
 556                 return insert(pos, s, traits_type::length(s));
 557         }
 558
 559         flex_string &insert(size_type pos, size_type n, value_type c)
 560         {
 561                 Enforce(pos <= length(), static_cast<std::out_of_range *>(0), "");
 562                 insert(begin() + pos, n, c);
 563                 return *this;
 564         }
 565
 566         iterator insert(const iterator p, const value_type c)
 567         {
 568                 const size_type pos = p - begin();
 569                 insert(p, 1, c);
 570                 return begin() + pos;
 571         }
 572
 573 private:
 574         template <int i> class Selector {};
 575
 576         flex_string &InsertImplDiscr(iterator p,
 577                                      size_type n, value_type c, Selector<1>)
 578         {
 579                 Invariant checker(*this);
 580                 (void) checker;
 581                 assert(p >= begin() && p <= end());
 582                 if (capacity() - size() < n)
 583                 {
 584                         const size_type sz = p - begin();
 585                         reserve(size() + n);
 586                         p = begin() + sz;
 587                 }
 588                 const iterator oldEnd = end();
 589                 //if (p + n < oldEnd) // replaced because of crash (pk)
 590                 if( n < size_type(oldEnd - p))
 591                 {
 592                         append(oldEnd - n, oldEnd);
 593                         //std::copy(
 594                         //    reverse_iterator(oldEnd - n),
 595                         //    reverse_iterator(p),
 596                         //    reverse_iterator(oldEnd));
 597                         flex_string_details::pod_move(&*p, &*oldEnd - n, &*p + n);
 598                         std::fill(p, p + n, c);
 599                 }
 600                 else
 601                 {
 602                         append(n - (end() - p), c);
 603                         append(p, oldEnd);
 604                         std::fill(p, oldEnd, c);
 605                 }
 606                 return *this;
 607         }
 608
 609         template<class InputIterator>
 610         flex_string &InsertImplDiscr(iterator i,
 611                                      InputIterator b, InputIterator e, Selector<0>)
 612         {
 613                 InsertImpl(i, b, e,
 614                            typename std::iterator_traits<InputIterator>::iterator_category());
 615                 return *this;
 616         }
 617
 618         template <class FwdIterator>
 619         void InsertImpl(iterator i,
 620                         FwdIterator s1, FwdIterator s2, std::forward_iterator_tag)
 621         {
 622                 Invariant checker(*this);
 623                 (void) checker;
 624                 const size_type pos = i - begin();
 625                 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
 626                     std::distance(s1, s2);
 627                 assert(n2 >= 0);
 628                 using namespace flex_string_details;
 629                 assert(pos <= size());
 630
 631                 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
 632                     capacity() - size();
 633                 if (maxn2 < n2)
 634                 {
 635                         // realloc the string
 636                         static const std::less_equal<const value_type *> le =
 637                             std::less_equal<const value_type *>();
 638                         assert(!(le(&*begin(), &*s1) && le(&*s1, &*end())));
 639                         reserve(size() + n2);
 640                         i = begin() + pos;
 641                 }
 642                 if (pos + n2 <= size())
 643                 {
 644                         //const iterator oldEnd = end();
 645                         //Storage::append(oldEnd - n2, n2);
 646                         //std::copy(i, oldEnd - n2, i + n2);
 647                         const iterator tailBegin = end() - n2;
 648                         Storage::append(tailBegin, tailBegin + n2);
 649                         //std::copy(i, tailBegin, i + n2);
 650                         std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
 651                                   reverse_iterator(tailBegin + n2));
 652                         std::copy(s1, s2, i);
 653                 }
 654                 else
 655                 {
 656                         FwdIterator t = s1;
 657                         const size_type old_size = size();
 658                         std::advance(t, old_size - pos);
 659                         assert(std::distance(t, s2) >= 0);
 660                         Storage::append(t, s2);
 661                         Storage::append(data() + pos, data() + old_size);
 662                         std::copy(s1, t, i);
 663                 }
 664         }
 665
 666         template <class InputIterator>
 667         void InsertImpl(iterator i1, iterator i2,
 668                         InputIterator b, InputIterator e, std::input_iterator_tag)
 669         {
 670                 flex_string temp(begin(), i1);
 671                 for (; b != e; ++b)
 672                 {
 673                         temp.push_back(*b);
 674                 }
 675                 temp.append(i2, end());
 676                 swap(temp);
 677         }
 678
 679 public:
 680         template <class ItOrLength, class ItOrChar>
 681         void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c)
 682         {
 683                 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
 684                 InsertImplDiscr(p, first_or_n, last_or_c, sel);
 685         }
 686
 687         flex_string &erase(size_type pos = 0, size_type n = npos)
 688         {
 689                 Invariant checker(*this);
 690                 (void) checker;
 691                 Enforce(pos <= length(), static_cast<std::out_of_range *>(0), "");
 692                 Procust(n, length() - pos);
 693                 std::copy(begin() + pos + n, end(), begin() + pos);
 694                 resize(length() - n);
 695                 return *this;
 696         }
 697
 698         iterator erase(iterator position)
 699         {
 700                 const size_type pos(position - begin());
 701                 erase(pos, 1);
 702                 return begin() + pos;
 703         }
 704
 705         iterator erase(iterator first, iterator last)
 706         {
 707                 const size_type pos(first - begin());
 708                 erase(pos, last - first);
 709                 return begin() + pos;
 710         }
 711
 712         // Replaces at most n1 chars of *this, starting with pos1 with the content of str
 713         flex_string &replace(size_type pos1, size_type n1, const flex_string &str)
 714         {
 715                 return replace(pos1, n1, str.data(), str.size());
 716         }
 717
 718         // Replaces at most n1 chars of *this, starting with pos1,
 719         // with at most n2 chars of str starting with pos2
 720         flex_string &replace(size_type pos1, size_type n1, const flex_string &str,
 721                              size_type pos2, size_type n2)
 722         {
 723                 Enforce(pos2 <= str.length(), static_cast<std::out_of_range *>(0), "");
 724                 return replace(pos1, n1, str.data() + pos2,
 725                                Min(n2, str.size() - pos2));
 726         }
 727
 728         /*
 729             // Replaces at most n1 chars of *this, starting with pos,
 730             // with at most n2 chars of str.
 731             // str must have at least n2 chars.
 732             flex_string& replace(const size_type pos, size_type n1,
 733                 const value_type* s1, const size_type n2)
 734             {
 735                 Invariant checker(*this);
 736                 (void) checker;
 737                 Enforce(pos <= size(), (std::out_of_range*)0, "");
 738                 Procust(n1, size() - pos);
 739                 const iterator b = begin() + pos;
 740                 return replace(b, b + n1, s1, s1 + n2);
 741                 using namespace flex_string_details;
 742                 const int delta = int(n2 - n1);
 743                 static const std::less_equal<const value_type*> le;
 744                 const bool aliased = le(&*begin(), s1) && le(s1, &*end());
 745
 746                 // From here on we're dealing with an aliased replace
 747                 if (delta <= 0)
 748                 {
 749                     // simple case, we're shrinking
 750                     pod_move(s1, s1 + n2, &*begin() + pos);
 751                     pod_move(&*begin() + pos + n1, &*end(), &*begin() + pos + n1 + delta);
 752                     resize(size() + delta);
 753                     return *this;
 754                 }
 755
 756                 // From here on we deal with aliased growth
 757                 if (capacity() < size() + delta)
 758                 {
 759                     // realloc the string
 760                     const size_type offset = s1 - data();
 761                     reserve(size() + delta);
 762                     s1 = data() + offset;
 763                 }
 764
 765                 const value_type* s2 = s1 + n2;
 766                 value_type* d1 = &*begin() + pos;
 767                 value_type* d2 = d1 + n1;
 768
 769                 const int tailLen = int(&*end() - d2);
 770
 771                 if (delta <= tailLen)
 772                 {
 773                     value_type* oldEnd = &*end();
 774                     // simple case
 775                     Storage::append(oldEnd - delta, delta);
 776
 777                     pod_move(d2, d2 + (tailLen - delta), d2 + delta);
 778                     if (le(d2, s1))
 779                     {
 780                         pod_copy(s1 + delta, s2 + delta, d1);
 781                     }
 782                     else
 783                     {
 784                         // d2 > s1
 785                         if (le(d2, s2))
 786                         {
 787                             pod_move(s1, d2, d1);
 788                             pod_move(d2 + delta, s2 + delta, d1 + (d2 - s1));
 789                         }
 790                         else
 791                         {
 792                             pod_move(s1, s2, d1);
 793                         }
 794                     }
 795                 }
 796                 else
 797                 {
 798                     const size_type sz = delta - tailLen;
 799                     Storage::append(s2 - sz, sz);
 800                     Storage::append(d2, tailLen);
 801                     pod_move(s1, s2 - (delta - tailLen), d1);
 802                 }
 803                 return *this;
 804             }
 805         */
 806
 807         // Replaces at most n1 chars of *this, starting with pos, with chars from s
 808         flex_string &replace(size_type pos, size_type n1, const value_type *s)
 809         {
 810                 return replace(pos, n1, s, traits_type::length(s));
 811         }
 812
 813         // Replaces at most n1 chars of *this, starting with pos, with n2 occurences of c
 814         // consolidated with
 815         // Replaces at most n1 chars of *this, starting with pos,
 816         // with at most n2 chars of str.
 817         // str must have at least n2 chars.
 818         template <class StrOrLength, class NumOrChar>
 819         flex_string &replace(size_type pos, size_type n1,
 820                              StrOrLength s_or_n2, NumOrChar n_or_c)
 821         {
 822                 Invariant checker(*this);
 823                 (void) checker;
 824                 Enforce(pos <= size(), static_cast<std::out_of_range *>(0), "");
 825                 Procust(n1, length() - pos);
 826                 const iterator b = begin() + pos;
 827                 return replace(b, b + n1, s_or_n2, n_or_c);
 828         }
 829
 830         flex_string &replace(iterator i1, iterator i2, const flex_string &str)
 831         {
 832                 return replace(i1, i2, str.data(), str.length());
 833         }
 834
 835         flex_string &replace(iterator i1, iterator i2, const value_type *s)
 836         {
 837                 return replace(i1, i2, s, traits_type::length(s));
 838         }
 839
 840 private:
 841         flex_string &ReplaceImplDiscr(iterator i1, iterator i2,
 842                                       const value_type *s, size_type n, Selector<2>)
 843         {
 844                 assert(i1 <= i2);
 845                 assert(begin() <= i1 && i1 <= end());
 846                 assert(begin() <= i2 && i2 <= end());
 847                 return replace(i1, i2, s, s + n);
 848         }
 849
 850         flex_string &ReplaceImplDiscr(iterator i1, iterator i2,
 851                                       size_type n2, value_type c, Selector<1>)
 852         {
 853                 const size_type n1 = i2 - i1;
 854                 if (n1 > n2)
 855                 {
 856                         std::fill(i1, i1 + n2, c);
 857                         erase(i1 + n2, i2);
 858                 }
 859                 else
 860                 {
 861                         std::fill(i1, i2, c);
 862                         insert(i2, n2 - n1, c);
 863                 }
 864                 return *this;
 865         }
 866
 867         template <class InputIterator>
 868         flex_string &ReplaceImplDiscr(iterator i1, iterator i2,
 869                                       InputIterator b, InputIterator e, Selector<0>)
 870         {
 871                 ReplaceImpl(i1, i2, b, e,
 872                             typename std::iterator_traits<InputIterator>::iterator_category());
 873                 return *this;
 874         }
 875
 876         template <class FwdIterator>
 877         void ReplaceImpl(iterator i1, iterator i2,
 878                          FwdIterator s1, FwdIterator s2, std::forward_iterator_tag)
 879         {
 880                 Invariant checker(*this);
 881                 (void) checker;
 882                 const typename std::iterator_traits<iterator>::difference_type n1 =
 883                     i2 - i1;
 884                 assert(n1 >= 0);
 885                 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
 886                     std::distance(s1, s2);
 887                 assert(n2 >= 0);
 888
 889                 // Handle aliased replace
 890                 static const std::less_equal<const value_type *> le =
 891                     std::less_equal<const value_type *>();
 892                 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
 893                 if (aliased /* && capacity() < size() - n1 + n2 */)
 894                 {
 895                         // Aliased replace, copy to new string
 896                         flex_string temp;
 897                         temp.reserve(size() - n1 + n2);
 898                         temp.append(begin(), i1).append(s1, s2).append(i2, end());
 899                         swap(temp);
 900                         return;
 901                 }
 902
 903                 if (n1 > n2)
 904                 {
 905                         // shrinks
 906                         std::copy(s1, s2, i1);
 907                         erase(i1 + n2, i2);
 908                 }
 909                 else
 910                 {
 911                         // grows
 912                         flex_string_details::copy_n(s1, n1, i1);
 913                         std::advance(s1, n1);
 914                         insert(i2, s1, s2);
 915                 }
 916         }
 917
 918         template <class InputIterator>
 919         void ReplaceImpl(iterator i1, iterator i2,
 920                          InputIterator b, InputIterator e, std::input_iterator_tag)
 921         {
 922                 flex_string temp(begin(), i1);
 923                 temp.append(b, e).append(i2, end());
 924                 swap(temp);
 925         }
 926
 927 public:
 928         template <class T1, class T2>
 929         flex_string &replace(iterator i1, iterator i2,
 930                              T1 first_or_n_or_s, T2 last_or_c_or_n)
 931         {
 932                 const bool
 933                 num1 = std::numeric_limits<T1>::is_specialized,
 934                 num2 = std::numeric_limits<T2>::is_specialized;
 935                 return ReplaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n,
 936                                         Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
 937         }
 938
 939         size_type copy(value_type *s, size_type n, size_type pos = 0) const
 940         {
 941                 Enforce(pos <= size(), static_cast<std::out_of_range *>(0), "");
 942                 Procust(n, size() - pos);
 943
 944                 flex_string_details::pod_copy(
 945                     data() + pos,
 946                     data() + pos + n,
 947                     s);
 948                 return n;
 949         }
 950
 951         void swap(flex_string &rhs)
 952         {
 953                 Storage &srhs = rhs;
 954                 this->Storage::swap(srhs);
 955         }
 956
 957         // 21.3.6 string operations:
 958         const value_type *c_str() const
 959         {
 960                 return Storage::c_str();
 961         }
 962
 963         const value_type *data() const
 964         {
 965                 return Storage::data();
 966         }
 967
 968         allocator_type get_allocator() const
 969         {
 970                 return Storage::get_allocator();
 971         }
 972
 973         size_type find(const flex_string &str, size_type pos = 0) const
 974         {
 975                 return find(str.data(), pos, str.length());
 976         }
 977
 978         size_type find (const value_type *s, size_type pos, size_type n) const
 979         {
 980                 if (n + pos > size())
 981                         return npos;
 982                 for (; pos + n <= size(); ++pos)
 983                 {
 984                         if (traits_type::compare(data() + pos, s, n) == 0)
 985                         {
 986                                 return pos;
 987                         }
 988                 }
 989                 return npos;
 990         }
 991
 992         size_type find (const value_type *s, size_type pos = 0) const
 993         {
 994                 return find(s, pos, traits_type::length(s));
 995         }
 996
 997         size_type find (value_type c, size_type pos = 0) const
 998         {
 999                 return find(&c, pos, 1);
1000         }
1001
1002         size_type rfind(const flex_string &str, size_type pos = npos) const
1003         {
1004                 return rfind(str.data(), pos, str.length());
1005         }
1006
1007         size_type rfind(const value_type *s, size_type pos, size_type n) const
1008         {
1009                 if (n > length()) return npos;
1010                 pos = Min(pos, length() - n);
1011                 if (n == 0) return pos;
1012
1013                 const_iterator i(begin() + pos);
1014                 for (; ; --i)
1015                 {
1016                         if (traits_type::eq(*i, *s)
1017                                 && traits_type::compare(&*i, s, n) == 0)
1018                         {
1019                                 return i - begin();
1020                         }
1021                         if (i == begin()) break;
1022                 }
1023                 return npos;
1024         }
1025
1026         size_type rfind(const value_type *s, size_type pos = npos) const
1027         {
1028                 return rfind(s, pos, traits_type::length(s));
1029         }
1030
1031         size_type rfind(value_type c, size_type pos = npos) const
1032         {
1033                 return rfind(&c, pos, 1);
1034         }
1035
1036         size_type find_first_of(const flex_string &str, size_type pos = 0) const
1037         {
1038                 return find_first_of(str.data(), pos, str.length());
1039         }
1040
1041         size_type find_first_of(const value_type *s,
1042                                 size_type pos, size_type n) const
1043         {
1044                 if (pos > length() || n == 0) return npos;
1045                 const_iterator i(begin() + pos),
1046                                finish(end());
1047                 for (; i != finish; ++i)
1048                 {
1049                         if (traits_type::find(s, n, *i) != 0)
1050                         {
1051                                 return i - begin();
1052                         }
1053                 }
1054                 return npos;
1055         }
1056
1057         size_type find_first_of(const value_type *s, size_type pos = 0) const
1058         {
1059                 return find_first_of(s, pos, traits_type::length(s));
1060         }
1061
1062         size_type find_first_of(value_type c, size_type pos = 0) const
1063         {
1064                 return find_first_of(&c, pos, 1);
1065         }
1066
1067         size_type find_last_of (const flex_string &str,
1068                                 size_type pos = npos) const
1069         {
1070                 return find_last_of(str.data(), pos, str.length());
1071         }
1072
1073         size_type find_last_of (const value_type *s, size_type pos,
1074                                 size_type n) const
1075         {
1076                 if (!empty() && n > 0)
1077                 {
1078                         pos = Min(pos, length() - 1);
1079                         const_iterator i(begin() + pos);
1080                         for (;; --i)
1081                         {
1082                                 if (traits_type::find(s, n, *i) != 0)
1083                                 {
1084                                         return i - begin();
1085                                 }
1086                                 if (i == begin()) break;
1087                         }
1088                 }
1089                 return npos;
1090         }
1091
1092         size_type find_last_of (const value_type *s,
1093                                 size_type pos = npos) const
1094         {
1095                 return find_last_of(s, pos, traits_type::length(s));
1096         }
1097
1098         size_type find_last_of (value_type c, size_type pos = npos) const
1099         {
1100                 return find_last_of(&c, pos, 1);
1101         }
1102
1103         size_type find_first_not_of(const flex_string &str,
1104                                     size_type pos = 0) const
1105         {
1106                 return find_first_not_of(str.data(), pos, str.size());
1107         }
1108
1109         size_type find_first_not_of(const value_type *s, size_type pos,
1110                                     size_type n) const
1111         {
1112                 if (pos < length())
1113                 {
1114                         const_iterator
1115                         i(begin() + pos),
1116                           finish(end());
1117                         for (; i != finish; ++i)
1118                         {
1119                                 if (traits_type::find(s, n, *i) == 0)
1120                                 {
1121                                         return i - begin();
1122                                 }
1123                         }
1124                 }
1125                 return npos;
1126         }
1127
1128         size_type find_first_not_of(const value_type *s,
1129                                     size_type pos = 0) const
1130         {
1131                 return find_first_not_of(s, pos, traits_type::length(s));
1132         }
1133
1134         size_type find_first_not_of(value_type c, size_type pos = 0) const
1135         {
1136                 return find_first_not_of(&c, pos, 1);
1137         }
1138
1139         size_type find_last_not_of(const flex_string &str,
1140                                    size_type pos = npos) const
1141         {
1142                 return find_last_not_of(str.data(), pos, str.length());
1143         }
1144
1145         size_type find_last_not_of(const value_type *s, size_type pos,
1146                                    size_type n) const
1147         {
1148                 if (!this->empty())
1149                 {
1150                         pos = Min(pos, size() - 1);
1151                         const_iterator i(begin() + pos);
1152                         for (;; --i)
1153                         {
1154                                 if (traits_type::find(s, n, *i) == 0)
1155                                 {
1156                                         return i - begin();
1157                                 }
1158                                 if (i == begin()) break;
1159                         }
1160                 }
1161                 return npos;
1162         }
1163
1164         size_type find_last_not_of(const value_type *s,
1165                                    size_type pos = npos) const
1166         {
1167                 return find_last_not_of(s, pos, traits_type::length(s));
1168         }
1169
1170         size_type find_last_not_of (value_type c, size_type pos = npos) const
1171         {
1172                 return find_last_not_of(&c, pos, 1);
1173         }
1174
1175         flex_string substr(size_type pos = 0, size_type n = npos) const
1176         {
1177                 Enforce(pos <= size(), static_cast<std::out_of_range *>(0), "");
1178                 return flex_string(data() + pos, Min(n, size() - pos));
1179         }
1180
1181         int compare(const flex_string &str) const
1182         {
1183                 // FIX due to Goncalo N M de Carvalho July 18, 2005
1184                 return compare(0, size(), str);
1185         }
1186
1187         int compare(size_type pos1, size_type n1,
1188                     const flex_string &str) const
1189         {
1190                 return compare(pos1, n1, str.data(), str.size());
1191         }
1192
1193         // FIX to compare: added the TC
1194         // (http://www.comeaucomputing.com/iso/lwg-defects.html number 5)
1195         // Thanks to Caleb Epstein for the fix
1196
1197         int compare(size_type pos1, size_type n1,
1198                     const value_type *s) const
1199         {
1200                 return compare(pos1, n1, s, traits_type::length(s));
1201         }
1202
1203         int compare(size_type pos1, size_type n1,
1204                     const value_type *s, size_type n2) const
1205         {
1206                 Enforce(pos1 <= size(), static_cast<std::out_of_range *>(0), "");
1207                 Procust(n1, size() - pos1);
1208                 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1209                 const int r = traits_type::compare(pos1 + data(), s, Min(n1, n2));
1210                 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1211         }
1212
1213         int compare(size_type pos1, size_type n1,
1214                     const flex_string &str,
1215                     size_type pos2, size_type n2) const
1216         {
1217                 Enforce(pos2 <= str.size(), static_cast<std::out_of_range *>(0), "");
1218                 return compare(pos1, n1, str.data() + pos2, Min(n2, str.size() - pos2));
1219         }
1220
1221         // Code from Jean-Francois Bastien (03/26/2007)
1222         int compare(const value_type *s) const
1223         {
1224                 // Could forward to compare(0, size(), s, traits_type::length(s))
1225                 // but that does two extra checks
1226                 const size_type n1(size()), n2(traits_type::length(s));
1227                 const int r = traits_type::compare(data(), s, Min(n1, n2));
1228                 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1229         }
1230 };
1231
1232 // non-member functions
1233 template <typename E, class T, class A, class S>
1234 flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
1235                                   const flex_string<E, T, A, S>& rhs)
1236 {
1237         flex_string<E, T, A, S> result;
1238         result.reserve(lhs.size() + rhs.size());
1239         result.append(lhs).append(rhs);
1240         return result;
1241 }
1242
1243 template <typename E, class T, class A, class S>
1244 flex_string<E, T, A, S> operator+(const typename flex_string<E, T, A, S>::value_type *lhs,
1245                                   const flex_string<E, T, A, S>& rhs)
1246 {
1247         flex_string<E, T, A, S> result;
1248         const typename flex_string<E, T, A, S>::size_type len =
1249             flex_string<E, T, A, S>::traits_type::length(lhs);
1250         result.reserve(len + rhs.size());
1251         result.append(lhs, len).append(rhs);
1252         return result;
1253 }
1254
1255 template <typename E, class T, class A, class S>
1256 flex_string<E, T, A, S> operator+(
1257     typename flex_string<E, T, A, S>::value_type lhs,
1258     const flex_string<E, T, A, S>& rhs)
1259 {
1260         flex_string<E, T, A, S> result;
1261         result.reserve(1 + rhs.size());
1262         result.push_back(lhs);
1263         result.append(rhs);
1264         return result;
1265 }
1266
1267 template <typename E, class T, class A, class S>
1268 flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
1269                                   const typename flex_string<E, T, A, S>::value_type *rhs)
1270 {
1271         typedef typename flex_string<E, T, A, S>::size_type size_type;
1272         typedef typename flex_string<E, T, A, S>::traits_type traits_type;
1273
1274         flex_string<E, T, A, S> result;
1275         const size_type len = traits_type::length(rhs);
1276         result.reserve(lhs.size() + len);
1277         result.append(lhs).append(rhs, len);
1278         return result;
1279 }
1280
1281 template <typename E, class T, class A, class S>
1282 flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
1283                                   typename flex_string<E, T, A, S>::value_type rhs)
1284 {
1285         flex_string<E, T, A, S> result;
1286         result.reserve(lhs.size() + 1);
1287         result.append(lhs);
1288         result.push_back(rhs);
1289         return result;
1290 }
1291
1292 template <typename E, class T, class A, class S>
1293 bool operator==(const flex_string<E, T, A, S>& lhs,
1294                 const flex_string<E, T, A, S>& rhs)
1295 {
1296         return lhs.compare(rhs) == 0;
1297 }
1298
1299 template <typename E, class T, class A, class S>
1300 bool operator==(const typename flex_string<E, T, A, S>::value_type *lhs,
1301                 const flex_string<E, T, A, S>& rhs)
1302 {
1303         return rhs == lhs;
1304 }
1305
1306 template <typename E, class T, class A, class S>
1307 bool operator==(const flex_string<E, T, A, S>& lhs,
1308                 const typename flex_string<E, T, A, S>::value_type *rhs)
1309 {
1310         return lhs.compare(rhs) == 0;
1311 }
1312
1313 template <typename E, class T, class A, class S>
1314 bool operator!=(const flex_string<E, T, A, S>& lhs,
1315                 const flex_string<E, T, A, S>& rhs)
1316 {
1317         return !(lhs == rhs);
1318 }
1319
1320 template <typename E, class T, class A, class S>
1321 bool operator!=(const typename flex_string<E, T, A, S>::value_type *lhs,
1322                 const flex_string<E, T, A, S>& rhs)
1323 {
1324         return !(lhs == rhs);
1325 }
1326
1327 template <typename E, class T, class A, class S>
1328 bool operator!=(const flex_string<E, T, A, S>& lhs,
1329                 const typename flex_string<E, T, A, S>::value_type *rhs)
1330 {
1331         return !(lhs == rhs);
1332 }
1333
1334 template <typename E, class T, class A, class S>
1335 bool operator<(const flex_string<E, T, A, S>& lhs,
1336                const flex_string<E, T, A, S>& rhs)
1337 {
1338         return lhs.compare(rhs) < 0;
1339 }
1340
1341 template <typename E, class T, class A, class S>
1342 bool operator<(const flex_string<E, T, A, S>& lhs,
1343                const typename flex_string<E, T, A, S>::value_type *rhs)
1344 {
1345         return lhs.compare(rhs) < 0;
1346 }
1347
1348 template <typename E, class T, class A, class S>
1349 bool operator<(const typename flex_string<E, T, A, S>::value_type *lhs,
1350                const flex_string<E, T, A, S>& rhs)
1351 {
1352         return rhs.compare(lhs) > 0;
1353 }
1354
1355 template <typename E, class T, class A, class S>
1356 bool operator>(const flex_string<E, T, A, S>& lhs,
1357                const flex_string<E, T, A, S>& rhs)
1358 {
1359         return rhs < lhs;
1360 }
1361
1362 template <typename E, class T, class A, class S>
1363 bool operator>(const flex_string<E, T, A, S>& lhs,
1364                const typename flex_string<E, T, A, S>::value_type *rhs)
1365 {
1366         return rhs < lhs;
1367 }
1368
1369 template <typename E, class T, class A, class S>
1370 bool operator>(const typename flex_string<E, T, A, S>::value_type *lhs,
1371                const flex_string<E, T, A, S>& rhs)
1372 {
1373         return rhs < lhs;
1374 }
1375
1376 template <typename E, class T, class A, class S>
1377 bool operator<=(const flex_string<E, T, A, S>& lhs,
1378                 const flex_string<E, T, A, S>& rhs)
1379 {
1380         return !(rhs < lhs);
1381 }
1382
1383 template <typename E, class T, class A, class S>
1384 bool operator<=(const flex_string<E, T, A, S>& lhs,
1385                 const typename flex_string<E, T, A, S>::value_type *rhs)
1386 {
1387         return !(rhs < lhs);
1388 }
1389
1390 template <typename E, class T, class A, class S>
1391 bool operator<=(const typename flex_string<E, T, A, S>::value_type *lhs,
1392                 const flex_string<E, T, A, S>& rhs)
1393 {
1394         return !(rhs < lhs);
1395 }
1396
1397 template <typename E, class T, class A, class S>
1398 bool operator>=(const flex_string<E, T, A, S>& lhs,
1399                 const flex_string<E, T, A, S>& rhs)
1400 {
1401         return !(lhs < rhs);
1402 }
1403
1404 template <typename E, class T, class A, class S>
1405 bool operator>=(const flex_string<E, T, A, S>& lhs,
1406                 const typename flex_string<E, T, A, S>::value_type *rhs)
1407 {
1408         return !(lhs < rhs);
1409 }
1410
1411 template <typename E, class T, class A, class S>
1412 bool operator>=(const typename flex_string<E, T, A, S>::value_type *lhs,
1413                 const flex_string<E, T, A, S>& rhs)
1414 {
1415         return !(lhs < rhs);
1416 }
1417
1418 // subclause 21.3.7.8:
1419 //void swap(flex_string<E, T, A, S>& lhs, flex_string<E, T, A, S>& rhs);    // to do
1420
1421 template <typename E, class T, class A, class S>
1422 std::basic_istream<typename flex_string<E, T, A, S>::value_type,
1423     typename flex_string<E, T, A, S>::traits_type>&
1424     operator>>(
1425         std::basic_istream<typename flex_string<E, T, A, S>::value_type,
1426         typename flex_string<E, T, A, S>::traits_type>& is,
1427         flex_string<E, T, A, S>& str);
1428
1429 template <typename E, class T, class A, class S>
1430 std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
1431     typename flex_string<E, T, A, S>::traits_type>&
1432     operator<<(
1433         std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
1434         typename flex_string<E, T, A, S>::traits_type>& os,
1435         const flex_string<E, T, A, S>& str)
1436 {
1437         return os << str.c_str();
1438 }
1439
1440 template <typename E, class T, class A, class S>
1441 std::basic_istream<typename flex_string<E, T, A, S>::value_type,
1442     typename flex_string<E, T, A, S>::traits_type>&
1443     getline(
1444         std::basic_istream<typename flex_string<E, T, A, S>::value_type,
1445         typename flex_string<E, T, A, S>::traits_type>& is,
1446         flex_string<E, T, A, S>& str,
1447         typename flex_string<E, T, A, S>::value_type delim);
1448
1449 template <typename E, class T, class A, class S>
1450 std::basic_istream<typename flex_string<E, T, A, S>::value_type,
1451     typename flex_string<E, T, A, S>::traits_type>&
1452     getline(
1453         std::basic_istream<typename flex_string<E, T, A, S>::value_type,
1454         typename flex_string<E, T, A, S>::traits_type>& is,
1455         flex_string<E, T, A, S>& str);
1456
1457 template <typename E1, class T, class A, class S>
1458 const typename flex_string<E1, T, A, S>::size_type
1459 flex_string<E1, T, A, S>::npos = static_cast<typename flex_string<E1, T, A, S>::size_type>(-1);
1460
1461 #endif // FLEX_STRING_SHELL_INC_