source: NonGTP/Boost/boost/wave/util/flex_string.hpp @ 857

Revision 857, 66.1 KB checked in by igarcia, 19 years ago (diff)
Line 
1/*=============================================================================
2    Boost.Wave: A Standard compliant C++ preprocessor library
3    http://www.boost.org/
4
5    Copyright (c) 2001 by Andrei Alexandrescu. Distributed under the Boost
6    Software License, Version 1.0. (See accompanying file
7    LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8=============================================================================*/
9
10// This code is taken from:
11// Andrei Alexandrescu, Generic<Programming>: A Policy-Based basic_string
12// Implementation. http://www.cuj.com/documents/s=7994/cujcexp1906alexandr/
13//
14// #HK030306:
15//      - Moved into the namespace boost::wave::util
16//      - Added a bunch of missing typename(s)
17//      - Integrated with boost config
18//      - Added a missing header include
19//      - Added special constructors and operator= to allow CowString to be
20//        a real COW-string (removed unnecessary data copying)
21//      - Fixed a string terminating bug in append
22//
23// #HK040109:
24//      - Incorporated the changes from Andrei's latest version of this class
25
26#ifndef FLEX_STRING_INC_
27#define FLEX_STRING_INC_
28
29/*
30////////////////////////////////////////////////////////////////////////////////
31template <typename E, class A = @>
32class StoragePolicy
33{
34    typedef E value_type;
35    typedef @ iterator;
36    typedef @ const_iterator;
37    typedef A allocator_type;
38    typedef @ size_type;
39   
40    StoragePolicy(const StoragePolicy& s);
41    StoragePolicy(const A&);
42    StoragePolicy(const E* s, size_type len, const A&);
43    StoragePolicy(size_type len, E c, const A&);
44    ~StoragePolicy();
45
46    iterator begin();
47    const_iterator begin() const;
48    iterator end();
49    const_iterator end() const;
50   
51    size_type size() const;
52    size_type max_size() const;
53    size_type capacity() const;
54
55    void reserve(size_type res_arg);
56
57    void append(const E* s, size_type sz);
58   
59    template <class InputIterator>
60    void append(InputIterator b, InputIterator e);
61
62    void resize(size_type newSize, E fill);
63
64    void swap(StoragePolicy& rhs);
65   
66    const E* c_str() const;
67    const E* data() const;
68   
69    A get_allocator() const;
70};
71////////////////////////////////////////////////////////////////////////////////
72*/
73
74#include <boost/config.hpp>
75#include <boost/assert.hpp>
76#include <boost/iterator/reverse_iterator.hpp>
77
78#include <memory>
79#include <string>
80#include <vector>
81#include <algorithm>
82#include <functional>
83#include <limits>
84#include <stdexcept>
85#include <cstddef>
86
87///////////////////////////////////////////////////////////////////////////////
88namespace boost {
89namespace wave {
90namespace util {
91
92namespace flex_string_details
93{
94    template <class Pod, class T>
95    inline void pod_fill(Pod* b, Pod* e, T c)
96    {
97        switch ((e - b) & 7)
98        {
99        case 0:
100            while (b != e)
101            {
102                *b = c; ++b;
103        case 7: *b = c; ++b;
104        case 6: *b = c; ++b;
105        case 5: *b = c; ++b;
106        case 4: *b = c; ++b;
107        case 3: *b = c; ++b;
108        case 2: *b = c; ++b;
109        case 1: *b = c; ++b;
110            }
111        }
112    }
113
114    template <class Pod>
115    inline void pod_move(const Pod* b, const Pod* e, Pod* d)
116    {
117        using namespace std;
118        memmove(d, b, (e - b) * sizeof(*b));
119    }
120
121    template <class Pod>
122    inline Pod* pod_copy(const Pod* b, const Pod* e, Pod* d)
123    {
124        const std::size_t s = e - b;
125        using namespace std;
126        memcpy(d, b, s * sizeof(*b));
127        return d + s;
128    }
129
130    template <typename T> struct get_unsigned
131    {
132        typedef T result;
133    };
134
135    template <> struct get_unsigned<char>
136    {
137        typedef unsigned char result;
138    };
139
140    template <> struct get_unsigned<signed char>
141    {
142        typedef unsigned char result;
143    };
144
145    template <> struct get_unsigned<short int>
146    {
147        typedef unsigned short int result;
148    };
149
150    template <> struct get_unsigned<int>
151    {
152        typedef unsigned int result;
153    };
154
155    template <> struct get_unsigned<long int>
156    {
157        typedef unsigned long int result;
158    };
159
160    enum Shallow {};
161}
162
163template <class T> class mallocator
164{
165public:
166    typedef T                 value_type;
167    typedef value_type*       pointer;
168    typedef const value_type* const_pointer;
169    typedef value_type&       reference;
170    typedef const value_type& const_reference;
171    typedef std::size_t       size_type;
172    //typedef unsigned int      size_type;
173    //typedef std::ptrdiff_t    difference_type;
174    typedef int               difference_type;
175
176    template <class U>
177    struct rebind { typedef mallocator<U> other; };
178
179    mallocator() {}
180    mallocator(const mallocator&) {}
181    //template <class U>
182    //mallocator(const mallocator<U>&) {}
183    ~mallocator() {}
184
185    pointer address(reference x) const { return &x; }
186    const_pointer address(const_reference x) const
187    {
188        return x;
189    }
190
191    pointer allocate(size_type n, const_pointer = 0)
192    {
193        using namespace std;
194        void* p = malloc(n * sizeof(T));
195        if (!p) throw bad_alloc();
196        return static_cast<pointer>(p);
197    }
198
199    void deallocate(pointer p, size_type)
200    {
201        using namespace std;
202        free(p);
203    }
204
205    size_type max_size() const
206    {
207        return static_cast<size_type>(-1) / sizeof(T);
208    }
209
210    void construct(pointer p, const value_type& x)
211    {
212        new(p) value_type(x);
213    }
214
215    void destroy(pointer p)
216    {
217        p->~value_type();
218    }
219
220private:
221    void operator=(const mallocator&);
222};
223
224template<> class mallocator<void>
225{
226  typedef void        value_type;
227  typedef void*       pointer;
228  typedef const void* const_pointer;
229
230  template <class U>
231  struct rebind { typedef mallocator<U> other; };
232};
233
234template <class T>
235inline bool operator==(const mallocator<T>&,
236                       const mallocator<T>&) {
237  return true;
238}
239
240template <class T>
241inline bool operator!=(const mallocator<T>&,
242                       const mallocator<T>&) {
243  return false;
244}
245
246template <class Allocator>
247typename Allocator::pointer Reallocate(
248    Allocator& alloc,
249    typename Allocator::pointer p,
250    typename Allocator::size_type oldObjCount,
251    typename Allocator::size_type newObjCount,
252    void*)
253{
254    // @@@ not implemented
255    return NULL;
256}
257
258template <class Allocator>
259typename Allocator::pointer Reallocate(
260    Allocator& alloc,
261    typename Allocator::pointer p,
262    typename Allocator::size_type oldObjCount,
263    typename Allocator::size_type newObjCount,
264    mallocator<void>*)
265{
266    // @@@ not implemented
267    return NULL;
268}
269
270////////////////////////////////////////////////////////////////////////////////
271// class template SimpleStringStorage
272// Allocates memory with malloc
273////////////////////////////////////////////////////////////////////////////////
274
275template <typename E, class A = std::allocator<E> >
276class SimpleStringStorage
277{
278    // The "public" below exists because MSVC can't do template typedefs
279public:
280    struct Data
281    {
282        Data() : pEnd_(buffer_), pEndOfMem_(buffer_) { buffer_[0] = E(0); }
283
284        E* pEnd_;
285        E* pEndOfMem_;
286        E buffer_[1];
287    };
288    static const Data emptyString_;
289   
290    typedef typename A::size_type size_type;
291
292private:
293    Data* pData_;
294
295    void Init(size_type size, size_type capacity)
296    {
297        BOOST_ASSERT(size <= capacity);
298        if (capacity == 0)
299        {
300            pData_ = const_cast<Data*>(&emptyString_);
301        }
302        else
303        {
304            // 11-17-2000: comment added:
305            //     No need to allocate (capacity + 1) to
306            //     accomodate the terminating 0, because Data already
307            //     has one one character in there
308            pData_ = static_cast<Data*>(
309                malloc(sizeof(Data) + capacity * sizeof(E)));
310            if (!pData_) throw std::bad_alloc();
311            pData_->pEnd_ = pData_->buffer_ + size;
312            pData_->pEndOfMem_ = pData_->buffer_ + capacity;
313        }
314    }
315   
316private:
317    // Warning - this doesn't initialize pData_. Used in reserve()
318    SimpleStringStorage()
319    { }
320   
321public:
322    typedef E value_type;
323    typedef E* iterator;
324    typedef const E* const_iterator;
325    typedef A allocator_type;
326   
327    SimpleStringStorage(const SimpleStringStorage& rhs)
328    {
329        const size_type sz = rhs.size();
330        Init(sz, sz);
331        if (sz) flex_string_details::pod_copy(rhs.begin(), rhs.end(), begin());
332    }
333   
334    SimpleStringStorage(const SimpleStringStorage& s,
335        flex_string_details::Shallow)
336        : pData_(s.pData_)
337    {
338    }
339   
340    SimpleStringStorage(const A&)
341    { pData_ = const_cast<Data*>(&emptyString_); }
342   
343    SimpleStringStorage(const E* s, size_type len, const A&)
344    {
345        Init(len, len);
346        flex_string_details::pod_copy(s, s + len, begin());
347    }
348
349    SimpleStringStorage(size_type len, E c, const A&)
350    {
351        Init(len, len);
352        flex_string_details::pod_fill(begin(), end(), c);
353    }
354   
355    SimpleStringStorage& operator=(const SimpleStringStorage& rhs)
356    {
357        const size_type sz = rhs.size();
358        reserve(sz);
359        flex_string_details::pod_copy(&*rhs.begin(), &*rhs.end(), begin());
360        pData_->pEnd_ = &*begin() + sz;
361        return *this;
362    }
363
364    ~SimpleStringStorage()
365    {
366        BOOST_ASSERT(begin() <= end());
367        if (pData_ != &emptyString_) free(pData_);
368    }
369
370    iterator begin()
371    { return pData_->buffer_; }
372   
373    const_iterator begin() const
374    { return pData_->buffer_; }
375   
376    iterator end()
377    { return pData_->pEnd_; }
378   
379    const_iterator end() const
380    { return pData_->pEnd_; }
381   
382    size_type size() const
383    { return pData_->pEnd_ - pData_->buffer_; }
384
385    size_type max_size() const
386    { return std::size_t(-1) / sizeof(E) - sizeof(Data) - 1; }
387
388    size_type capacity() const
389    { return pData_->pEndOfMem_ - pData_->buffer_; }
390
391    void reserve(size_type res_arg)
392    {
393        if (res_arg <= capacity())
394        {
395            // @@@ insert shrinkage here if you wish
396            return;
397        }
398
399        if (pData_ == &emptyString_)
400        {
401            Init(0, res_arg);
402        }
403        else
404        {
405            const size_type sz = size();
406
407            void* p = realloc(pData_,
408                sizeof(Data) + res_arg * sizeof(E));
409            if (!p) throw std::bad_alloc();
410       
411            if (p != pData_)
412            {
413                pData_ = static_cast<Data*>(p);
414                pData_->pEnd_ = pData_->buffer_ + sz;
415            }
416            pData_->pEndOfMem_ = pData_->buffer_ + res_arg;
417        }
418    }
419
420    void append(const E* s, size_type sz)
421    {
422        const size_type neededCapacity = size() + sz;
423
424        if (capacity() < neededCapacity)
425        {
426            const iterator b = begin();
427            static std::less_equal<const E*> le;
428            if (le(b, s) && le(s, end()))
429            {
430               // aliased
431                const size_type offset = s - b;
432                reserve(neededCapacity);
433                s = begin() + offset;
434            }
435            else
436            {
437                reserve(neededCapacity);
438            }
439        }
440        flex_string_details::pod_copy(s, s + sz, end());
441        pData_->pEnd_ += sz;
442    }
443   
444    template <class InputIterator>
445    void append(InputIterator b, InputIterator e)
446    {
447        // @@@ todo: optimize this depending on iterator type
448        for (; b != e; ++b)
449        {
450            *this += *b;
451        }
452    }
453
454    void resize(size_type newSize, E fill)
455    {
456        const int delta = int(newSize - size());
457        if (delta == 0) return;
458
459        if (delta > 0)
460        {
461            if (newSize > capacity())
462            {
463                reserve(newSize);
464            }
465            E* e = &*end();
466            flex_string_details::pod_fill(e, e + delta, fill);
467        }
468        pData_->pEnd_ = pData_->buffer_ + newSize;
469    }
470
471    void swap(SimpleStringStorage& rhs)
472    {
473        std::swap(pData_, rhs.pData_);
474    }
475   
476    const E* c_str() const
477    {
478        if (pData_ != &emptyString_) *pData_->pEnd_ = E();
479        return pData_->buffer_;
480    }
481
482    const E* data() const
483    { return pData_->buffer_; }
484   
485    A get_allocator() const
486    { return A(); }
487};
488
489template <typename E, class A>
490const typename SimpleStringStorage<E, A>::Data
491SimpleStringStorage<E, A>::emptyString_ = typename SimpleStringStorage<E, A>::Data();
492//{
493//  const_cast<E*>(SimpleStringStorage<E, A>::emptyString_.buffer_),
494//  const_cast<E*>(SimpleStringStorage<E, A>::emptyString_.buffer_),
495//  { E() }
496//};
497
498////////////////////////////////////////////////////////////////////////////////
499// class template AllocatorStringStorage
500// Allocates with your allocator
501// Takes advantage of the Empty Base Optimization if available
502////////////////////////////////////////////////////////////////////////////////
503
504template <typename E, class A = std::allocator<E> >
505class AllocatorStringStorage : public A
506{
507    typedef typename A::size_type size_type;
508    typedef typename SimpleStringStorage<E, A>::Data Data;
509
510    void* Alloc(size_type sz, const void* p = 0)
511    {
512        return A::allocate(1 + (sz - 1) / sizeof(E),
513            static_cast<const char*>(p));
514    }
515
516    void* Realloc(void* p, size_type oldSz, size_type newSz)
517    {
518        void* r = Alloc(newSz);
519        flex_string_details::pod_copy(p, p + Min(oldSz, newSz), r);
520        Free(p, oldSz);
521        return r;
522    }
523
524    void Free(void* p, size_type sz)
525    {
526        A::deallocate(static_cast<E*>(p), sz);
527    }
528
529    Data* pData_;
530
531    void Init(size_type size, size_type cap)
532    {
533        BOOST_ASSERT(size <= cap);
534
535        if (cap == 0)
536        {
537            pData_ = const_cast<Data*>(
538                &SimpleStringStorage<E, A>::emptyString_);
539        }
540        else
541        {
542            pData_ = static_cast<Data*>(Alloc(
543                cap * sizeof(E) + sizeof(Data)));
544            pData_->pEnd_ = pData_->buffer_ + size;
545            pData_->pEndOfMem_ = pData_->buffer_ + cap;
546        }
547    }
548   
549public:
550    typedef E value_type;
551    typedef A allocator_type;
552    typedef typename A::pointer iterator;
553    typedef typename A::const_pointer const_iterator;
554   
555    AllocatorStringStorage(const AllocatorStringStorage& rhs)
556    : A(rhs.get_allocator())
557    {
558        const size_type sz = rhs.size();
559        Init(sz, sz);
560        if (sz) flex_string_details::pod_copy(rhs.begin(), rhs.end(), begin());
561    }
562   
563    AllocatorStringStorage(const AllocatorStringStorage& s,
564        flex_string_details::Shallow)
565    : A(s.get_allocator())
566    {
567        pData_ = s.pData_;
568    }
569   
570    AllocatorStringStorage(const A& a) : A(a)
571    {
572        pData_ = const_cast<Data*>(
573            &SimpleStringStorage<E, A>::emptyString_);
574    }
575   
576    AllocatorStringStorage(const E* s, size_type len, const A& a)
577    : A(a)
578    {
579        Init(len, len);       
580        flex_string_details::pod_copy(s, s + len, begin());
581    }
582
583    AllocatorStringStorage(size_type len, E c, const A& a)
584    : A(a)
585    {
586        Init(len, len);
587        flex_string_details::pod_fill(&*begin(), &*end(), c);
588    }
589   
590    AllocatorStringStorage& operator=(const AllocatorStringStorage& rhs)
591    {
592        const size_type sz = rhs.size();
593        reserve(sz);
594        flex_string_details::pod_copy(&*rhs.begin(), &*rhs.end(), begin());
595        pData_->pEnd_ = &*begin() + rhs.size();
596        return *this;
597    }
598   
599    ~AllocatorStringStorage()
600    {
601        if (capacity())
602        {
603            Free(pData_,
604                sizeof(Data) + capacity() * sizeof(E));
605        }
606    }
607       
608    iterator begin()
609    { return pData_->buffer_; }
610   
611    const_iterator begin() const
612    { return pData_->buffer_; }
613   
614    iterator end()
615    { return pData_->pEnd_; }
616   
617    const_iterator end() const
618    { return pData_->pEnd_; }
619   
620    size_type size() const
621    { return size_type(end() - begin()); }
622
623    size_type max_size() const
624    { return A::max_size(); }
625
626    size_type capacity() const
627    { return size_type(pData_->pEndOfMem_ - pData_->buffer_); }
628
629    void resize(size_type n, E c)
630    {
631        reserve(n);
632        iterator newEnd = begin() + n;
633        iterator oldEnd = end();
634        if (newEnd > oldEnd)
635        {
636            // Copy the characters
637            flex_string_details::pod_fill(oldEnd, newEnd, c);
638        }
639        if (capacity()) pData_->pEnd_ = newEnd;
640    }
641
642    void reserve(size_type res_arg)
643    {
644        if (res_arg <= capacity())
645        {
646            // @@@ shrink to fit here
647            return;
648        }
649       
650        A& myAlloc = *this;
651        AllocatorStringStorage newStr(myAlloc);
652        newStr.Init(size(), res_arg);
653       
654        flex_string_details::pod_copy(begin(), end(), newStr.begin());
655       
656        swap(newStr);
657    }
658
659    void append(const E* s, size_type sz)
660    {
661        const size_type neededCapacity = size() + sz;
662
663        if (capacity() < neededCapacity)
664        {
665            const iterator b = begin();
666            static std::less_equal<const E*> le;
667            if (le(b, s) && le(s, end()))
668            {
669               // aliased
670                const size_type offset = s - b;
671                reserve(neededCapacity);
672                s = begin() + offset;
673            }
674            else
675            {
676                reserve(neededCapacity);
677            }
678        }
679        flex_string_details::pod_copy(s, s + sz, end());
680        pData_->pEnd_ += sz;
681    }
682   
683    void swap(AllocatorStringStorage& rhs)
684    {
685        // @@@ The following line is commented due to a bug in MSVC
686        //std::swap(lhsAlloc, rhsAlloc);
687        std::swap(pData_, rhs.pData_);
688    }
689   
690    const E* c_str() const
691    {
692        if (pData_ != &SimpleStringStorage<E, A>::emptyString_)
693        {
694            *pData_->pEnd_ = E();
695        }
696        return &*begin();
697    }
698
699    const E* data() const
700    { return &*begin(); }
701   
702    A get_allocator() const
703    { return *this; }
704};
705
706////////////////////////////////////////////////////////////////////////////////
707// class template VectorStringStorage
708// Uses std::vector
709// Takes advantage of the Empty Base Optimization if available
710////////////////////////////////////////////////////////////////////////////////
711
712template <typename E, class A = std::allocator<E> >
713class VectorStringStorage : protected std::vector<E, A>
714{
715    typedef std::vector<E, A> base;
716
717public: // protected:
718    typedef E value_type;
719    typedef typename base::iterator iterator;
720    typedef typename base::const_iterator const_iterator;
721    typedef A allocator_type;
722    typedef typename A::size_type size_type;
723   
724    VectorStringStorage(const VectorStringStorage& s) : base(s)
725    { }
726   
727    VectorStringStorage(const A& a) : base(1, E(), a)
728    { }
729   
730    VectorStringStorage(const E* s, size_type len, const A& a)
731    : base(a)
732    {
733        base::reserve(len + 1);
734        base::insert(base::end(), s, s + len);
735        // Terminating zero
736        base::insert(base::end(), E());
737    }
738
739    VectorStringStorage(size_type len, E c, const A& a)
740    : base(len + 1, c, a)
741    {
742        // Terminating zero
743        base::back() = E();
744    }
745   
746    VectorStringStorage& operator=(const VectorStringStorage& rhs)
747    {
748        base& v = *this;
749        v = rhs;
750        return *this;
751    }
752   
753    iterator begin()
754    { return base::begin(); }
755   
756    const_iterator begin() const
757    { return base::begin(); }
758   
759    iterator end()
760    { return base::end() - 1; }
761   
762    const_iterator end() const
763    { return base::end() - 1; }
764   
765    size_type size() const
766    { return base::size() - 1; }
767
768    size_type max_size() const
769    { return base::max_size() - 1; }
770
771    size_type capacity() const
772    { return base::capacity() - 1; }
773
774    void reserve(size_type res_arg)
775    {
776        BOOST_ASSERT(res_arg < max_size());
777        base::reserve(res_arg + 1);
778    }
779   
780    void append(const E* s, size_type sz)
781    {
782        // Check for aliasing because std::vector doesn't do it.
783        static std::less_equal<const E*> le;
784        if (!base::empty())
785        {
786            const E* start = &base::front();
787            if (le(start, s) && le(s, start + size()))
788            {
789                // aliased
790                const size_type offset = s - start;
791                reserve(size() + sz);
792                s = &base::front() + offset;
793            }
794        }
795        base::insert(end(), s, s + sz);
796    }
797   
798    template <class InputIterator>
799    void append(InputIterator b, InputIterator e)
800    {
801        base::insert(end(), b, e);
802    }
803
804    void resize(size_type n, E c)
805    {
806        base::reserve(n + 1);
807        base::back() = c;
808        base::resize(n + 1, c);
809        base::back() = E();
810    }
811
812    void swap(VectorStringStorage& rhs)
813    { base::swap(rhs); }
814   
815    const E* c_str() const
816    { return &*begin(); }
817
818    const E* data() const
819    { return &*begin(); }
820   
821    A get_allocator() const
822    { return base::get_allocator(); }
823};
824
825////////////////////////////////////////////////////////////////////////////////
826// class template SmallStringOpt
827// Builds the small string optimization over any other storage
828////////////////////////////////////////////////////////////////////////////////
829
830template <class Storage, unsigned int threshold,
831    typename Align = typename Storage::value_type*>
832class SmallStringOpt
833{
834public:
835    typedef typename Storage::value_type value_type;
836    typedef value_type* iterator;
837    typedef const value_type* const_iterator;
838    typedef typename Storage::allocator_type allocator_type;
839    typedef typename allocator_type::size_type size_type;
840   
841private:
842  enum { temp1 = threshold * sizeof(value_type) > sizeof(Storage)
843        ? threshold  * sizeof(value_type)
844        : sizeof(Storage) };
845   
846    enum { temp2 = temp1 > sizeof(Align) ? temp1 : sizeof(Align) };
847
848public:
849    enum { maxSmallString =
850    (temp2 + sizeof(value_type) - 1) / sizeof(value_type) };
851   
852private:
853    enum { magic = maxSmallString + 1 };
854   
855    union
856    {
857        mutable value_type buf_[maxSmallString + 1];
858        Align align_;
859    };
860   
861    Storage& GetStorage()
862    {
863        BOOST_ASSERT(buf_[maxSmallString] == magic);
864        Storage* p = reinterpret_cast<Storage*>(&buf_[0]);
865        return *p;
866    }
867   
868    const Storage& GetStorage() const
869    {
870        BOOST_ASSERT(buf_[maxSmallString] == magic);
871        const Storage *p = reinterpret_cast<const Storage*>(&buf_[0]);
872        return *p;
873    }
874   
875    bool Small() const
876    {
877        return buf_[maxSmallString] != magic;
878    }
879       
880public:
881  SmallStringOpt(const SmallStringOpt& s)
882    {
883        if (s.Small())
884        {
885            flex_string_details::pod_copy(
886                s.buf_,
887                s.buf_ + s.size(),
888                buf_);
889        }
890        else
891        {
892            new(buf_) Storage(s.GetStorage());
893        }
894        buf_[maxSmallString] = s.buf_[maxSmallString];
895    }
896   
897    SmallStringOpt(const allocator_type&)
898    {
899        buf_[maxSmallString] = maxSmallString;
900    }
901   
902    SmallStringOpt(const value_type* s, size_type len, const allocator_type& a)
903    {
904        if (len <= maxSmallString)
905        {
906            flex_string_details::pod_copy(s, s + len, buf_);
907            buf_[maxSmallString] = value_type(maxSmallString - len);
908        }
909        else
910        {
911            new(buf_) Storage(s, len, a);
912            buf_[maxSmallString] = magic;
913        }
914    }
915
916    SmallStringOpt(size_type len, value_type c, const allocator_type& a)
917    {
918        if (len <= maxSmallString)
919        {
920            flex_string_details::pod_fill(buf_, buf_ + len, c);
921            buf_[maxSmallString] = value_type(maxSmallString - len);
922        }
923        else
924        {
925            new(buf_) Storage(len, c, a);
926            buf_[maxSmallString] = magic;
927        }
928    }
929   
930    SmallStringOpt& operator=(const SmallStringOpt& rhs)
931    {
932        reserve(rhs.size());
933        resize(0, 0);
934        append(rhs.data(), rhs.size());
935        return *this;
936    }
937
938    ~SmallStringOpt()
939    {
940        if (!Small()) GetStorage().~Storage();
941    }
942
943    iterator begin()
944    {
945        if (Small()) return buf_;
946        return &*GetStorage().begin();
947    }
948   
949    const_iterator begin() const
950    {
951        if (Small()) return buf_;
952        return &*GetStorage().begin();
953    }
954   
955    iterator end()
956    {
957        if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
958        return &*GetStorage().end();
959    }
960   
961    const_iterator end() const
962    {
963        if (Small()) return buf_ + maxSmallString - buf_[maxSmallString];
964        return &*GetStorage().end();
965    }
966   
967    size_type size() const
968    {
969        BOOST_ASSERT(!Small() || maxSmallString >= buf_[maxSmallString]);
970        return Small()
971            ? maxSmallString - buf_[maxSmallString]
972            : GetStorage().size();
973    }
974
975    size_type max_size() const
976    { return get_allocator().max_size(); }
977
978    size_type capacity() const
979    { return Small() ? maxSmallString : GetStorage().capacity(); }
980
981    void reserve(size_type res_arg)
982    {
983        if (Small())
984        {
985            if (res_arg <= maxSmallString) return;
986            SmallStringOpt temp(*this);
987            this->~SmallStringOpt();
988            new(buf_) Storage(temp.data(), temp.size(),
989                temp.get_allocator());
990            buf_[maxSmallString] = magic;
991            GetStorage().reserve(res_arg);
992        }
993        else
994        {
995            GetStorage().reserve(res_arg);
996        }
997        BOOST_ASSERT(capacity() >= res_arg);
998    }
999   
1000    void append(const value_type* s, size_type sz)
1001    {
1002        if (!Small())
1003        {
1004            GetStorage().append(s, sz);
1005        }
1006        else
1007        {
1008            // append to a small string
1009            const size_type neededCapacity =
1010                maxSmallString - buf_[maxSmallString] + sz;
1011
1012            if (maxSmallString < neededCapacity)
1013            {
1014                // need to change storage strategy
1015                allocator_type alloc;
1016                Storage temp(alloc);
1017                temp.reserve(neededCapacity);
1018                temp.append(buf_, maxSmallString - buf_[maxSmallString]);
1019                temp.append(s, sz);
1020                buf_[maxSmallString] = magic;
1021                new(buf_) Storage(temp.get_allocator());
1022                GetStorage().swap(temp);
1023            }
1024            else
1025            {
1026                flex_string_details::pod_move(s, s + sz,
1027                    buf_ + maxSmallString - buf_[maxSmallString]);
1028                buf_[maxSmallString] -= value_type(sz);
1029            }
1030        }
1031    }
1032   
1033    template <class InputIterator>
1034    void append(InputIterator b, InputIterator e)
1035    {
1036        // @@@ todo: optimize this depending on iterator type
1037        for (; b != e; ++b)
1038        {
1039            *this += *b;
1040        }
1041    }
1042
1043    void resize(size_type n, value_type c)
1044    {
1045        if (Small())
1046        {
1047            if (n > maxSmallString)
1048            {
1049                // Small string resized to big string
1050                SmallStringOpt temp(*this); // can't throw
1051                // 11-17-2001: correct exception safety bug
1052                Storage newString(temp.data(), temp.size(),
1053                    temp.get_allocator());
1054                newString.resize(n, c);
1055                // We make the reasonable assumption that an empty Storage
1056                //     constructor won't throw
1057                this->~SmallStringOpt();
1058                new(&buf_[0]) Storage(temp.get_allocator());
1059                buf_[maxSmallString] = value_type(magic);
1060                GetStorage().swap(newString);
1061            }
1062            else
1063            {
1064                // Small string resized to small string
1065                // 11-17-2001: bug fix: terminating zero not copied
1066                size_type toFill = n > size() ? n - size() : 0;
1067                flex_string_details::pod_fill(end(), end() + toFill, c);
1068                buf_[maxSmallString] = value_type(maxSmallString - n);
1069            }
1070        }
1071        else
1072        {
1073            if (n > maxSmallString)
1074            {
1075                // Big string resized to big string
1076                GetStorage().resize(n, c);
1077            }
1078            else
1079            {
1080                // Big string resized to small string
1081                // 11-17=2001: bug fix in the BOOST_ASSERTion below
1082                BOOST_ASSERT(capacity() > n);
1083                SmallStringOpt newObj(data(), n, get_allocator());
1084                newObj.swap(*this);
1085            }
1086        }
1087    }
1088
1089    void swap(SmallStringOpt& rhs)
1090    {
1091        if (Small())
1092        {
1093            if (rhs.Small())
1094            {
1095                // Small swapped with small
1096                std::swap_ranges(buf_, buf_ + maxSmallString + 1,
1097                    rhs.buf_);
1098            }
1099            else
1100            {
1101                // Small swapped with big
1102                // Make a copy of myself - can't throw
1103                SmallStringOpt temp(*this);
1104                // Nuke myself
1105                this->~SmallStringOpt();
1106                // Make an empty storage for myself (likely won't throw)
1107                new(buf_) Storage(0, value_type(), rhs.get_allocator());
1108                buf_[maxSmallString] = magic;
1109                // Recurse to this same function
1110                swap(rhs);
1111                // Nuke rhs
1112                rhs.~SmallStringOpt();
1113                // Build the new small string into rhs
1114                new(&rhs) SmallStringOpt(temp);
1115            }
1116        }
1117        else
1118        {
1119            if (rhs.Small())
1120            {
1121                // Big swapped with small
1122                // Already implemented, recurse with reversed args
1123                rhs.swap(*this);
1124            }
1125            else
1126            {
1127                // Big swapped with big
1128                GetStorage().swap(rhs.GetStorage());
1129            }
1130        }
1131    }
1132   
1133    const value_type* c_str() const
1134    {
1135        if (!Small()) return GetStorage().c_str();
1136        buf_[maxSmallString - buf_[maxSmallString]] = value_type();
1137        return buf_;
1138    }
1139
1140    const value_type* data() const
1141    { return Small() ? buf_ : GetStorage().data(); }
1142   
1143    allocator_type get_allocator() const
1144    { return allocator_type(); }
1145};
1146
1147////////////////////////////////////////////////////////////////////////////////
1148// class template CowString
1149// Implements Copy on Write over any storage
1150////////////////////////////////////////////////////////////////////////////////
1151
1152template <
1153    typename Storage,
1154    typename Align = BOOST_DEDUCED_TYPENAME Storage::value_type*
1155>
1156class CowString
1157{
1158    typedef typename Storage::value_type E;
1159    typedef typename flex_string_details::get_unsigned<E>::result RefCountType;
1160
1161public:
1162    typedef E value_type;
1163    typedef typename Storage::iterator iterator;
1164    typedef typename Storage::const_iterator const_iterator;
1165    typedef typename Storage::allocator_type allocator_type;
1166    typedef typename allocator_type::size_type size_type;
1167   
1168private:
1169    union
1170    {
1171        mutable char buf_[sizeof(Storage)];
1172        Align align_;
1173    };
1174
1175    Storage& Data() const
1176    { return *reinterpret_cast<Storage*>(buf_); }
1177
1178    RefCountType GetRefs() const
1179    {
1180        const Storage& d = Data();
1181        BOOST_ASSERT(d.size() > 0);
1182        BOOST_ASSERT(static_cast<RefCountType>(*d.begin()) != 0);
1183        return *d.begin();
1184    }
1185   
1186    RefCountType& Refs()
1187    {
1188        Storage& d = Data();
1189        BOOST_ASSERT(d.size() > 0);
1190        return reinterpret_cast<RefCountType&>(*d.begin());
1191    }
1192   
1193    void MakeUnique() const
1194    {
1195        BOOST_ASSERT(GetRefs() >= 1);
1196        if (GetRefs() == 1) return;
1197
1198        union
1199        {
1200            char buf_[sizeof(Storage)];
1201            Align align_;
1202        } temp;
1203
1204        new(buf_) Storage(
1205            *new(temp.buf_) Storage(Data()),
1206            flex_string_details::Shallow());
1207        *Data().begin() = 1;
1208    }
1209
1210public:
1211    CowString(const CowString& s)
1212    {
1213        if (s.GetRefs() == (std::numeric_limits<RefCountType>::max)())
1214        {
1215            // must make a brand new copy
1216            new(buf_) Storage(s.Data()); // non shallow
1217            Refs() = 1;
1218        }
1219        else
1220        {
1221            new(buf_) Storage(s.Data(), flex_string_details::Shallow());
1222            ++Refs();
1223        }
1224        BOOST_ASSERT(Data().size() > 0);
1225    }
1226   
1227    CowString(const allocator_type& a)
1228    {
1229        new(buf_) Storage(1, 1, a);
1230    }
1231   
1232    CowString(const E* s, size_type len, const allocator_type& a)
1233    {
1234        // Warning - MSVC's debugger has trouble tracing through the code below.
1235        // It seems to be a const-correctness issue
1236        //
1237        new(buf_) Storage(a);
1238        Data().reserve(len + 1);
1239        Data().resize(1, 1);
1240        Data().append(s, len);
1241    }
1242
1243    CowString(size_type len, E c, const allocator_type& a)
1244    {
1245        new(buf_) Storage(len + 1, c, a);
1246        Refs() = 1;
1247    }
1248   
1249    CowString& operator=(const CowString& rhs)
1250    {
1251//        CowString(rhs).swap(*this);
1252        if (--Refs() == 0) Data().~Storage();
1253        if (rhs.GetRefs() == (std::numeric_limits<RefCountType>::max)())
1254        {
1255            // must make a brand new copy
1256            new(buf_) Storage(rhs.Data()); // non shallow
1257            Refs() = 1;
1258        }
1259        else
1260        {
1261            new(buf_) Storage(rhs.Data(), flex_string_details::Shallow());
1262            ++Refs();
1263        }
1264        BOOST_ASSERT(Data().size() > 0);
1265        return *this;
1266    }
1267
1268    ~CowString()
1269    {
1270        BOOST_ASSERT(Data().size() > 0);
1271        if (--Refs() == 0) Data().~Storage();
1272    }
1273
1274    iterator begin()
1275    {
1276        BOOST_ASSERT(Data().size() > 0);
1277        MakeUnique();
1278        return Data().begin() + 1;
1279    }
1280   
1281    const_iterator begin() const
1282    {
1283        BOOST_ASSERT(Data().size() > 0);
1284        return Data().begin() + 1;
1285    }
1286   
1287    iterator end()
1288    {
1289        MakeUnique();
1290        return Data().end();
1291    }
1292   
1293    const_iterator end() const
1294    {
1295        return Data().end();
1296    }
1297   
1298    size_type size() const
1299    {
1300        BOOST_ASSERT(Data().size() > 0);
1301        return Data().size() - 1;
1302    }
1303
1304    size_type max_size() const
1305    {
1306        BOOST_ASSERT(Data().max_size() > 0);
1307        return Data().max_size() - 1;
1308    }
1309
1310    size_type capacity() const
1311    {
1312        BOOST_ASSERT(Data().capacity() > 0);
1313        return Data().capacity() - 1;
1314    }
1315
1316    void resize(size_type n, E c)
1317    {
1318        BOOST_ASSERT(Data().size() > 0);
1319        MakeUnique();
1320        Data().resize(n + 1, c);
1321    }
1322
1323    void append(const E* s, size_type sz)
1324    {
1325        MakeUnique();
1326        Data().append(s, sz);
1327    }
1328   
1329    template <class InputIterator>
1330    void append(InputIterator b, InputIterator e)
1331    {
1332        MakeUnique();
1333        // @@@ todo: optimize this depending on iterator type
1334        for (; b != e; ++b)
1335        {
1336            *this += *b;
1337        }
1338    }
1339
1340    void reserve(size_type res_arg)
1341    {
1342        if (capacity() > res_arg) return;
1343        MakeUnique();
1344        Data().reserve(res_arg + 1);
1345    }
1346   
1347    void swap(CowString& rhs)
1348    {
1349        Data().swap(rhs.Data());
1350    }
1351   
1352    const E* c_str() const
1353    {
1354        BOOST_ASSERT(Data().size() > 0);
1355        return Data().c_str() + 1;
1356    }
1357
1358    const E* data() const
1359    {
1360        BOOST_ASSERT(Data().size() > 0);
1361        return Data().data() + 1;
1362    }
1363   
1364    allocator_type get_allocator() const
1365    {
1366        return Data().get_allocator();
1367    }
1368};
1369
1370////////////////////////////////////////////////////////////////////////////////
1371// class template flex_string
1372// a std::basic_string compatible implementation
1373// Uses a Storage policy
1374////////////////////////////////////////////////////////////////////////////////
1375
1376template <typename E,
1377    class T = std::char_traits<E>,
1378    class A = std::allocator<E>,
1379    class Storage = AllocatorStringStorage<E, A> >
1380class flex_string : private Storage
1381{
1382#if defined(THROW_ON_ENFORCE)
1383    template <typename Exception>
1384    static void Enforce(bool condition, Exception*, const char* msg)
1385    { if (!condition) throw Exception(msg); }
1386#else
1387    template <typename Exception>
1388    static inline void Enforce(bool condition, Exception*, const char* msg)
1389    { BOOST_ASSERT(condition && msg); }
1390#endif // defined(THROW_ON_ENFORCE)
1391
1392    bool Sane() const
1393    {
1394        return
1395            begin() <= end() &&
1396            empty() == (size() == 0) &&
1397            empty() == (begin() == end()) &&
1398            size() <= max_size() &&
1399            capacity() <= max_size() &&
1400            size() <= capacity();
1401    }
1402
1403    struct Invariant;
1404    friend struct Invariant;
1405    struct Invariant
1406    {
1407        Invariant(const flex_string& s) : s_(s)
1408        {
1409            BOOST_ASSERT(s_.Sane());
1410        }
1411        ~Invariant()
1412        {
1413            BOOST_ASSERT(s_.Sane());
1414        }
1415    private:
1416        const flex_string& s_;
1417    };
1418   
1419public:
1420    // types
1421    typedef T traits_type;
1422    typedef typename traits_type::char_type value_type;
1423    typedef A allocator_type;
1424    typedef typename A::size_type size_type;
1425    typedef typename A::difference_type difference_type;
1426   
1427    typedef typename A::reference reference;
1428    typedef typename A::const_reference const_reference;
1429    typedef typename A::pointer pointer;
1430    typedef typename A::const_pointer const_pointer;
1431   
1432    typedef typename Storage::iterator iterator;
1433    typedef typename Storage::const_iterator const_iterator;
1434
1435    typedef boost::reverse_iterator<iterator> reverse_iterator;
1436    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
1437
1438    static const size_type npos;    // = size_type(-1)
1439
1440private:
1441    static size_type Min(size_type lhs, size_type rhs)
1442    { return lhs < rhs ? lhs : rhs; }
1443   
1444public:   
1445    // 21.3.1 construct/copy/destroy
1446    explicit flex_string(const A& a = A())
1447    : Storage(a)
1448    {}
1449   
1450    flex_string(const flex_string& str)
1451    : Storage(str)
1452    {
1453    }
1454   
1455    flex_string(const flex_string& str, size_type pos,
1456        size_type n = npos, const A& a = A())
1457    : Storage(a)
1458    {
1459        Enforce(pos <= str.size(), (std::out_of_range*)0, "");
1460        assign(str, pos, n);
1461    }
1462   
1463    flex_string(const value_type* s, const A& a = A())
1464    : Storage(s, traits_type::length(s), a)
1465    {}
1466   
1467    flex_string(const value_type* s, size_type n, const A& a = A())
1468    : Storage(s, n, a)
1469    {}
1470   
1471    flex_string(size_type n, value_type c, const A& a = A())
1472    : Storage(n, c, a)
1473    {}
1474
1475    template <class InputIterator>
1476    flex_string(InputIterator begin, InputIterator end, const A& a = A())
1477    : Storage(a)
1478    {
1479        assign(begin, end);
1480    }
1481
1482    ~flex_string()
1483    {}
1484   
1485    flex_string& operator=(const flex_string& str)
1486    {
1487        if (this != &str) {
1488            Storage& s = *this;
1489            s = str;
1490        }
1491        return *this;
1492    }   
1493   
1494    flex_string& operator=(const value_type* s)
1495    {
1496        assign(s);
1497        return *this;
1498    }
1499
1500    flex_string& operator=(value_type c)
1501    {
1502        assign(1, c);
1503        return *this;
1504    }
1505   
1506    // 21.3.2 iterators:
1507    iterator begin()
1508    { return Storage::begin(); }
1509   
1510    const_iterator begin() const
1511    { return Storage::begin(); }
1512   
1513    iterator end()
1514    { return Storage::end(); }
1515   
1516    const_iterator end() const
1517    { return Storage::end(); }
1518
1519    reverse_iterator rbegin()
1520    { return reverse_iterator(end()); }
1521   
1522    const_reverse_iterator rbegin() const
1523    { return const_reverse_iterator(end()); }
1524   
1525    reverse_iterator rend()
1526    { return reverse_iterator(begin()); }
1527   
1528    const_reverse_iterator rend() const
1529    { return const_reverse_iterator(begin()); }
1530   
1531    // 21.3.3 capacity:
1532    size_type size() const
1533    { return Storage::size(); }
1534   
1535    size_type length() const
1536    { return size(); }
1537   
1538    size_type max_size() const
1539    { return Storage::max_size(); }
1540
1541    void resize(size_type n, value_type c)
1542    { Storage::resize(n, c); }
1543   
1544    void resize(size_type n)
1545    { resize(n, value_type()); }
1546   
1547    size_type capacity() const
1548    { return Storage::capacity(); }
1549   
1550    void reserve(size_type res_arg = 0)
1551    {
1552        Enforce(res_arg <= max_size(), (std::length_error*)0, "");
1553        Storage::reserve(res_arg);
1554    }
1555   
1556    void clear()
1557    { resize(0); }
1558   
1559    bool empty() const
1560    { return size() == 0; }
1561   
1562    // 21.3.4 element access:
1563    const_reference operator[](size_type pos) const
1564    { return *(begin() + pos); }
1565   
1566    reference operator[](size_type pos)
1567    { return *(begin() + pos); }
1568
1569    const_reference at(size_type n) const
1570    {
1571        Enforce(n < size(), (std::out_of_range*)0, "");
1572        return (*this)[n];
1573    }
1574   
1575    reference at(size_type n)
1576    {
1577        Enforce(n < size(), (std::out_of_range*)0, "");
1578        return (*this)[n];
1579    }
1580   
1581    // 21.3.5 modifiers:
1582    flex_string& operator+=(const flex_string& str)
1583    { return append(str); }
1584   
1585    flex_string& operator+=(const value_type* s)
1586    { return append(s); }
1587
1588    flex_string& operator+=(value_type c)
1589    {
1590        const size_type cap = capacity();
1591        if (size() == cap)
1592        {
1593            reserve(cap << 1u);
1594        }
1595        resize(size() + 1, c);
1596        return *this;
1597    }
1598   
1599    flex_string& append(const flex_string& str)
1600    { return append(str, 0, npos); }
1601   
1602    flex_string& append(const flex_string& str, size_type pos,
1603        size_type n)
1604    {
1605        const size_type sz = str.size();
1606        Enforce(pos <= sz, (std::out_of_range*)0, "");
1607        return append(str.c_str() + pos, Min(n, sz - pos));
1608    }
1609   
1610    flex_string& append(const value_type* s, size_type n)
1611    {
1612        Storage::append(s, n);
1613        return *this;
1614    }
1615   
1616    flex_string& append(const value_type* s)
1617    { return append(s, traits_type::length(s)); }
1618   
1619    flex_string& append(size_type n, value_type c)
1620    {
1621        resize(size() + n, c);
1622        return *this;
1623    }
1624/*   
1625    template<class InputIterator>
1626    flex_string& append(InputIterator first, InputIterator last)
1627    {
1628        for (; first != last; ++first) *this += E(*first);
1629        return *this;
1630    }
1631*/   
1632    void push_back(value_type c)
1633    {
1634        *this += c;
1635    }
1636
1637    flex_string& assign(const flex_string& str)
1638    {
1639        if (&str == this) return *this;
1640        replace(0, size(), &*str.begin(), str.size());
1641        return *this;
1642    }
1643   
1644    flex_string& assign(const flex_string& str, size_type pos,
1645        size_type n)
1646    {
1647        Enforce(pos <= str.size(), (std::out_of_range*)0, "");
1648        return assign(str.data() + pos, Min(n, str.size() - pos));
1649    }
1650   
1651    flex_string& assign(const value_type* s, size_type n)
1652    {
1653        if (size() >= n)
1654        {
1655            flex_string_details::pod_move(s, s + n, &*begin());
1656            resize(n, value_type());
1657        }
1658        else
1659        {
1660            flex_string_details::pod_move(s, s + size(), &*begin());
1661            Storage::append(s + size(), n - size());
1662        }
1663        return *this;
1664    }
1665   
1666    flex_string& assign(const value_type* s)
1667    { return assign(s, traits_type::length(s)); }
1668   
1669    flex_string& assign(size_type n, value_type c)
1670    { return replace(begin(), end(), n, c); }
1671   
1672    template<class InputIterator>
1673    flex_string& assign(InputIterator first, InputIterator last)
1674    { return replace(begin(), end(), first, last); }
1675   
1676    flex_string& insert(size_type pos1, const flex_string& str)
1677    { return insert(pos1, str, 0, npos); }
1678   
1679    flex_string& insert(size_type pos1, const flex_string& str,
1680        size_type pos2, size_type n)
1681    { return replace(pos1, 0, str, pos2, n); }
1682   
1683    flex_string& insert(size_type pos, const value_type* s, size_type n)
1684    { return replace(pos, 0, s, n); }
1685   
1686    flex_string& insert(size_type pos, const value_type* s)
1687    { return insert(pos, s, traits_type::length(s)); }
1688   
1689    flex_string& insert(size_type pos, size_type n, value_type c)
1690    { return replace(pos, 0, n, c); }
1691   
1692    iterator insert(iterator p, value_type c = value_type())
1693    {
1694        const size_type pos = p - begin();
1695        insert(pos, &c, 1);
1696        return begin() + pos;
1697    }
1698   
1699    void insert(iterator p, size_type n, value_type c)
1700    { insert(p - begin(), n, c); }
1701   
1702    template<class InputIterator>
1703    void insert(iterator p, InputIterator first, InputIterator last)
1704    { replace(p, p, first, last); }
1705   
1706    flex_string& erase(size_type pos = 0, size_type n = npos)
1707    {
1708        return replace(pos, Min(n, size() - pos), 0, value_type());
1709    }
1710   
1711    iterator erase(iterator position)
1712    {
1713        const size_type pos(position - begin());
1714        erase(pos, 1);
1715        return begin() + pos;
1716    }
1717   
1718    iterator erase(iterator first, iterator last)
1719    {
1720        const size_type pos(first - begin());
1721        erase(pos, last - first);
1722        return begin() + pos;
1723    }
1724
1725    // @@@ replace
1726
1727    flex_string& replace(size_type pos1, size_type n1, const flex_string& str)
1728    { return replace(pos1, n1, str, 0, npos); }
1729   
1730    flex_string& replace(size_type pos1, size_type n1, const flex_string& str,
1731        size_type pos2, size_type n2)
1732    {
1733        Enforce(pos1 <= length() && pos2 <= str.length(),
1734            (std::out_of_range*)0, "");
1735        return replace(pos1, n1, &*str.begin() + pos2,
1736            Min(n2, str.length() - pos2));
1737    }
1738   
1739    flex_string& replace(const size_type d, size_type n1, const value_type* s1,
1740        const size_type n2)
1741    {
1742        using namespace flex_string_details;
1743        Enforce(d <= size(), (std::out_of_range*)0, "");
1744        if (d + n1 > size()) n1 = size() - d;
1745        const int delta = int(n2 - n1);
1746        static const std::less_equal<const value_type*> le =
1747            std::less_equal<const value_type*>();
1748        const bool aliased = le(&*begin(), s1) && le(s1, &*end());
1749
1750        if (delta > 0)
1751        {
1752            if (capacity() < size() + delta)
1753            {
1754                // realloc the string
1755                if (aliased)
1756                {
1757                    const size_type offset = s1 - &*begin();
1758                    reserve(size() + delta);
1759                    s1 = &*begin() + offset;
1760                }
1761                else
1762                {
1763                    reserve(size() + delta);
1764                }
1765            }
1766
1767            const value_type* s2 = s1 + n2;
1768            value_type* d1 = &*begin() + d;
1769            value_type* d2 = d1 + n1;
1770
1771            const int tailLen = int(&*end() - d2);
1772
1773            if (delta <= tailLen)
1774            {
1775                value_type* oldEnd = &*end();
1776                // simple case
1777                Storage::append(oldEnd - delta, delta);
1778
1779                pod_move(d2, d2 + (tailLen - delta), d2 + delta);
1780                if (le(d2, s1))
1781                {
1782                    if (aliased)
1783                    {
1784                        pod_copy(s1 + delta, s2 + delta, d1);
1785                    }
1786                    else
1787                    {
1788                        pod_copy(s1, s2, d1);
1789                    }
1790                }
1791                else
1792                {
1793                    // d2 > s1
1794                    if (le(d2, s2))
1795                    {
1796                        BOOST_ASSERT(aliased);
1797                        pod_move(s1, d2, d1);
1798                        pod_move(d2 + delta, s2 + delta, d1 + (d2 - s1));
1799                    }
1800                    else
1801                    {
1802                        pod_move(s1, s2, d1);
1803                    }
1804                }
1805            }
1806            else
1807            {
1808                const size_type sz = delta - tailLen;
1809                Storage::append(s2 - sz, sz);
1810                Storage::append(d2, tailLen);
1811                pod_move(s1, s2 - (delta - tailLen), d1);
1812            }
1813        }
1814        else
1815        {
1816            pod_move(s1, s1 + n2, &*begin() + d);
1817            pod_move(&*begin() + d + n1, &*end(), &*begin() + d + n1 + delta);
1818            resize(size() + delta);
1819        }
1820        return *this;
1821    }
1822
1823    flex_string& replace(size_type pos, size_type n1, const value_type* s)
1824    { return replace(pos, n1, s, traits_type::length(s)); }
1825   
1826    flex_string& replace(size_type pos, size_type n1, size_type n2,
1827        value_type c)
1828    {
1829        if (pos + n1 > size()) n1 = size() - pos;
1830        const size_type oldSize = size();
1831        if (pos + n2 > oldSize)
1832        {
1833            resize(pos + n2, c);
1834            Storage::append(&*begin() + pos + n1, oldSize - pos - n1);
1835            flex_string_details::pod_fill(&*begin() + pos,
1836                &*begin() + oldSize, c);
1837        }
1838        else
1839        {
1840            if (n2 > n1)
1841            {
1842                const size_type delta = n2 - n1;
1843                Storage::append(&*begin() + oldSize - delta, delta);
1844                flex_string_details::pod_move(
1845                    &*begin() + pos + n1,
1846                    &*begin() + oldSize - delta,
1847                    &*begin() + pos + n2);
1848            }
1849            else
1850            {
1851                flex_string_details::pod_move(&*begin() + pos + n1, &*end(),
1852                    &*begin() + pos + n2);
1853                resize(oldSize - (n1 - n2));
1854            }
1855            flex_string_details::pod_fill(&*begin() + pos,
1856                &*begin() + pos + n2, c);
1857        }
1858        return *this;
1859    }
1860       
1861    flex_string& replace(iterator i1, iterator i2, const flex_string& str)
1862    { return replace(i1, i2, str.c_str(), str.length()); }
1863   
1864    flex_string& replace(iterator i1, iterator i2,
1865        const value_type* s, size_type n)
1866    { return replace(i1 - begin(), i2 - i1, s, n); }
1867   
1868    flex_string& replace(iterator i1, iterator i2, const value_type* s)
1869    { return replace(i1, i2, s, traits_type::length(s)); }
1870   
1871    flex_string& replace(iterator i1, iterator i2,
1872        size_type n, value_type c)
1873    { return replace(i1 - begin(), i2 - i1, n, c); }
1874   
1875private:
1876    template <int i> class Selector {};
1877   
1878//    template <class U1, class U2> struct SameType
1879//    {
1880//        enum { result = false };
1881//    };
1882//   
1883//    template <class U> struct SameType<U, U>
1884//    {
1885//        enum { result = true };
1886//    };
1887   
1888    template<class ReallyAnIntegral>
1889    flex_string& ReplaceImpl(iterator i1, iterator i2,
1890        ReallyAnIntegral n, ReallyAnIntegral c, Selector<1>)
1891    {
1892        return replace(i1, i2, static_cast<size_type>(n),
1893            static_cast<value_type>(c));
1894    }   
1895
1896    template<class InputIterator>
1897    flex_string& ReplaceImpl(iterator i1, iterator i2,
1898        InputIterator b, InputIterator e, Selector<0>)
1899    {
1900        BOOST_ASSERT(false);
1901        return *this;
1902    }   
1903
1904public:
1905    template<class InputIterator>
1906    flex_string& replace(iterator i1, iterator i2,
1907        InputIterator j1, InputIterator j2)
1908    {
1909        return ReplaceImpl(i1, i2, j1, j2,
1910            Selector<std::numeric_limits<InputIterator>::is_specialized>());
1911    }
1912       
1913    size_type copy(value_type* s, size_type n, size_type pos = 0) const
1914    {
1915        Enforce(pos <= size(), (std::out_of_range*)0, "");
1916        n = Min(n, size() - pos);
1917       
1918        flex_string_details::pod_copy(
1919            &*begin() + pos,
1920            &*begin() + pos + n,
1921            s);
1922        return n;
1923    }
1924   
1925    void swap(flex_string& rhs)
1926    {
1927        Storage& srhs = rhs;
1928        this->Storage::swap(srhs);
1929    }
1930   
1931    // 21.3.6 string operations:
1932    const value_type* c_str() const
1933    { return Storage::c_str(); }
1934   
1935    const value_type* data() const
1936    { return Storage::data(); }
1937   
1938    allocator_type get_allocator() const
1939    { return Storage::get_allocator(); }
1940   
1941    size_type find(const flex_string& str, size_type pos = 0) const
1942    { return find(str.data(), pos, str.length()); }
1943   
1944    size_type find (const value_type* s, size_type pos, size_type n) const
1945    {
1946        for (; pos <= size(); ++pos)
1947        {
1948            if (traits_type::compare(&*begin() + pos, s, n) == 0)
1949            {
1950                return pos;
1951            }
1952        }
1953        return npos;
1954    }
1955   
1956    size_type find (const value_type* s, size_type pos = 0) const
1957    { return find(s, pos, traits_type::length(s)); }
1958
1959    size_type find (value_type c, size_type pos = 0) const
1960    { return find(&c, pos, 1); }
1961   
1962    size_type rfind(const flex_string& str, size_type pos = npos) const
1963    { return rfind(str.c_str(), pos, str.length()); }
1964   
1965    size_type rfind(const value_type* s, size_type pos, size_type n) const
1966    {
1967        if (n > length()) return npos;
1968        pos = Min(pos, length() - n);
1969        if (n == 0) return pos;
1970
1971        const_iterator i(begin() + pos);
1972        for (; ; --i)
1973        {
1974            if (traits_type::eq(*i, *s)
1975                && traits_type::compare(&*i, s, n) == 0)
1976            {
1977                return i - begin();
1978            }
1979            if (i == begin()) break;
1980        }
1981        return npos;
1982    }
1983
1984    size_type rfind(const value_type* s, size_type pos = npos) const
1985    { return rfind(s, pos, traits_type::length(s)); }
1986
1987    size_type rfind(value_type c, size_type pos = npos) const
1988    { return rfind(&c, pos, 1); }
1989   
1990    size_type find_first_of(const flex_string& str, size_type pos = 0) const
1991    { return find_first_of(str.c_str(), pos, str.length()); }
1992   
1993    size_type find_first_of(const value_type* s,
1994        size_type pos, size_type n) const
1995    {
1996        if (pos > length() || n == 0) return npos;
1997        const_iterator i(begin() + pos),
1998            finish(end());
1999        for (; i != finish; ++i)
2000        {
2001            if (traits_type::find(s, n, *i) != 0)
2002            {
2003                return i - begin();
2004            }
2005        }
2006        return npos;
2007    }
2008       
2009    size_type find_first_of(const value_type* s, size_type pos = 0) const
2010    { return find_first_of(s, pos, traits_type::length(s)); }
2011   
2012    size_type find_first_of(value_type c, size_type pos = 0) const
2013    { return find_first_of(&c, pos, 1); }
2014   
2015    size_type find_last_of (const flex_string& str,
2016        size_type pos = npos) const
2017    { return find_last_of(str.c_str(), pos, str.length()); }
2018   
2019    size_type find_last_of (const value_type* s, size_type pos,
2020        size_type n) const
2021    {
2022        if (!empty() && n > 0)
2023        {
2024            pos = Min(pos, length() - 1);
2025            const_iterator i(begin() + pos);
2026            for (;; --i)
2027            {
2028                if (traits_type::find(s, n, *i) != 0)
2029                {
2030                    return i - begin();
2031                }
2032                if (i == begin()) break;
2033            }
2034        }
2035        return npos;
2036    }
2037
2038    size_type find_last_of (const value_type* s,
2039        size_type pos = npos) const
2040    { return find_last_of(s, pos, traits_type::length(s)); }
2041
2042    size_type find_last_of (value_type c, size_type pos = npos) const
2043    { return find_last_of(&c, pos, 1); }
2044   
2045    size_type find_first_not_of(const flex_string& str,
2046        size_type pos = 0) const
2047    { return find_first_not_of(str.data(), pos, str.size()); }
2048   
2049    size_type find_first_not_of(const value_type* s, size_type pos,
2050        size_type n) const
2051    {
2052        if (pos < length())
2053        {
2054            const_iterator
2055                i(begin() + pos),
2056                finish(end());
2057            for (; i != finish; ++i)
2058            {
2059                if (traits_type::find(s, n, *i) == 0)
2060                {
2061                    return i - begin();
2062                }
2063            }
2064        }
2065        return npos;
2066    }
2067   
2068    size_type find_first_not_of(const value_type* s,
2069        size_type pos = 0) const
2070    { return find_first_not_of(s, pos, traits_type::length(s)); }
2071       
2072    size_type find_first_not_of(value_type c, size_type pos = 0) const
2073    { return find_first_not_of(&c, pos, 1); }
2074   
2075    size_type find_last_not_of(const flex_string& str,
2076        size_type pos = npos) const
2077    { return find_last_not_of(str.c_str(), pos, str.length()); }
2078   
2079    size_type find_last_not_of(const value_type* s, size_type pos,
2080        size_type n) const
2081    {
2082        if (!empty())
2083        {
2084            pos = Min(pos, size() - 1);
2085            const_iterator i(begin() + pos);
2086            for (;; --i)
2087            {
2088                if (traits_type::find(s, n, *i) == 0)
2089                {
2090                    return i - begin();
2091                }
2092                if (i == begin()) break;
2093            }
2094        }
2095        return npos;
2096    }
2097
2098    size_type find_last_not_of(const value_type* s,
2099        size_type pos = npos) const
2100    { return find_last_not_of(s, pos, traits_type::length(s)); }
2101   
2102    size_type find_last_not_of (value_type c, size_type pos = npos) const
2103    { return find_last_not_of(&c, pos, 1); }
2104   
2105    flex_string substr(size_type pos = 0, size_type n = npos) const
2106    {
2107        Enforce(pos <= size(), (std::out_of_range*)0, "");
2108        return flex_string(data() + pos, Min(n, size() - pos));
2109    }
2110
2111    std::ptrdiff_t compare(const flex_string& str) const
2112    { return compare(0, size(), str.data(), str.length()); }
2113   
2114    std::ptrdiff_t compare(size_type pos1, size_type n1,
2115        const flex_string& str) const
2116    { return compare(pos1, n1, str.data(), str.size()); }
2117   
2118    std::ptrdiff_t compare(size_type pos1, size_type n1,
2119        const value_type* s, size_type n2 = npos) const
2120    {
2121        Enforce(pos1 <= size(), (std::out_of_range*)0, "");
2122
2123        n1 = Min(size() - pos1, n1);
2124        const std::ptrdiff_t result = traits_type::compare(data() + pos1, s, Min(n1, n2));
2125        return (result != 0) ? result : int(n1 - n2);
2126    }
2127   
2128    std::ptrdiff_t compare(size_type pos1, size_type n1,
2129        const flex_string& str,
2130        size_type pos2, size_type n2) const
2131    {
2132        Enforce(pos2 <= str.size(), (std::out_of_range*)0, "");
2133        return compare(pos1, n1, str.data() + pos2, Min(n2, str.size() - pos2));
2134    }
2135
2136    std::ptrdiff_t compare(const value_type* s) const
2137    { return compare(0, size(), s, traits_type::length(s)); }
2138};
2139
2140// non-member functions
2141template <typename E, class T, class A, class S>
2142flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
2143    const flex_string<E, T, A, S>& rhs)
2144{
2145    flex_string<E, T, A, S> result;
2146    result.reserve(lhs.size() + rhs.size());
2147    result.append(lhs);
2148    result.append(rhs);
2149    return result;
2150}
2151
2152template <typename E, class T, class A, class S>
2153flex_string<E, T, A, S> operator+(const typename flex_string<E, T, A, S>::value_type* lhs,
2154    const flex_string<E, T, A, S>& rhs)
2155{
2156    flex_string<E, T, A, S> result;
2157    const typename flex_string<E, T, A, S>::size_type len =
2158        flex_string<E, T, A, S>::traits_type::length(lhs);
2159    result.reserve(len + rhs.size());
2160    result.append(lhs, len);
2161    result.append(rhs);
2162    return result;
2163}
2164
2165template <typename E, class T, class A, class S>
2166flex_string<E, T, A, S> operator+(
2167    typename flex_string<E, T, A, S>::value_type lhs,
2168    const flex_string<E, T, A, S>& rhs)
2169{
2170    flex_string<E, T, A, S> result;
2171    result.reserve(1 + rhs.size());
2172    result.push_back(lhs);
2173    result.append(rhs);
2174    return result;
2175}
2176
2177template <typename E, class T, class A, class S>
2178flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
2179    const typename flex_string<E, T, A, S>::value_type* rhs)
2180{
2181    typedef typename flex_string<E, T, A, S>::size_type size_type;
2182    typedef typename flex_string<E, T, A, S>::traits_type traits_type;
2183
2184    flex_string<E, T, A, S> result;
2185    const size_type len = traits_type::length(rhs);
2186    result.reserve(lhs.size() + len);
2187    result.append(lhs);
2188    result.append(rhs, len);
2189    return result;
2190}
2191
2192template <typename E, class T, class A, class S>
2193flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs,
2194    typename flex_string<E, T, A, S>::value_type rhs)
2195{
2196    flex_string<E, T, A, S> result;
2197    result.reserve(lhs.size() + 1);
2198    result.append(lhs);
2199    result.push_back(rhs);
2200    return result;
2201}
2202
2203template <typename E, class T, class A, class S>
2204bool operator==(const flex_string<E, T, A, S>& lhs,
2205    const flex_string<E, T, A, S>& rhs)
2206{ return lhs.compare(rhs) == 0; }
2207
2208template <typename E, class T, class A, class S>
2209bool operator==(const typename flex_string<E, T, A, S>::value_type* lhs,
2210    const flex_string<E, T, A, S>& rhs)
2211{ return rhs == lhs; }
2212
2213template <typename E, class T, class A, class S>
2214bool operator==(const flex_string<E, T, A, S>& lhs,
2215    const typename flex_string<E, T, A, S>::value_type* rhs)
2216{ return lhs.compare(rhs) == 0; }
2217
2218template <typename E, class T, class A, class S>
2219bool operator!=(const flex_string<E, T, A, S>& lhs,
2220    const flex_string<E, T, A, S>& rhs)
2221{ return !(lhs == rhs); }
2222
2223template <typename E, class T, class A, class S>
2224bool operator!=(const typename flex_string<E, T, A, S>::value_type* lhs,
2225    const flex_string<E, T, A, S>& rhs)
2226{ return !(lhs == rhs); }
2227
2228template <typename E, class T, class A, class S>
2229bool operator!=(const flex_string<E, T, A, S>& lhs,
2230    const typename flex_string<E, T, A, S>::value_type* rhs)
2231{ return !(lhs == rhs); }
2232
2233template <typename E, class T, class A, class S>
2234bool operator<(const flex_string<E, T, A, S>& lhs,
2235    const flex_string<E, T, A, S>& rhs)
2236{ return lhs.compare(rhs) < 0; }
2237
2238template <typename E, class T, class A, class S>
2239bool operator<(const flex_string<E, T, A, S>& lhs,
2240    const typename flex_string<E, T, A, S>::value_type* rhs)
2241{ return lhs.compare(rhs) < 0; }
2242
2243template <typename E, class T, class A, class S>
2244bool operator<(const typename flex_string<E, T, A, S>::value_type* lhs,
2245    const flex_string<E, T, A, S>& rhs)
2246{ return rhs.compare(lhs) > 0; }
2247
2248template <typename E, class T, class A, class S>
2249bool operator>(const flex_string<E, T, A, S>& lhs,
2250    const flex_string<E, T, A, S>& rhs)
2251{ return rhs < lhs; }
2252
2253template <typename E, class T, class A, class S>
2254bool operator>(const flex_string<E, T, A, S>& lhs,
2255    const typename flex_string<E, T, A, S>::value_type* rhs)
2256{ return rhs < lhs; }
2257
2258template <typename E, class T, class A, class S>
2259bool operator>(const typename flex_string<E, T, A, S>::value_type* lhs,
2260    const flex_string<E, T, A, S>& rhs)
2261{ return rhs < lhs; }
2262
2263template <typename E, class T, class A, class S>
2264bool operator<=(const flex_string<E, T, A, S>& lhs,
2265    const flex_string<E, T, A, S>& rhs)
2266{ return !(rhs < lhs); }
2267
2268template <typename E, class T, class A, class S>
2269bool operator<=(const flex_string<E, T, A, S>& lhs,
2270    const typename flex_string<E, T, A, S>::value_type* rhs)
2271{ return !(rhs < lhs); }
2272
2273template <typename E, class T, class A, class S>
2274bool operator<=(const typename flex_string<E, T, A, S>::value_type* lhs,
2275    const flex_string<E, T, A, S>& rhs)
2276{ return !(rhs < lhs); }
2277
2278template <typename E, class T, class A, class S>
2279bool operator>=(const flex_string<E, T, A, S>& lhs,
2280    const flex_string<E, T, A, S>& rhs)
2281{ return !(lhs < rhs); }
2282
2283template <typename E, class T, class A, class S>
2284bool operator>=(const flex_string<E, T, A, S>& lhs,
2285    const typename flex_string<E, T, A, S>::value_type* rhs)
2286{ return !(lhs < rhs); }
2287
2288template <typename E, class T, class A, class S>
2289bool operator>=(const typename flex_string<E, T, A, S>::value_type* lhs,
2290    const flex_string<E, T, A, S>& rhs)
2291{ return !(lhs < rhs); }
2292
2293// subclause 21.3.7.8:
2294//void swap(flex_string<E, T, A, S>& lhs, flex_string<E, T, A, S>& rhs);    // to do
2295
2296template <typename E, class T, class A, class S>
2297std::basic_istream<typename flex_string<E, T, A, S>::value_type,
2298    typename flex_string<E, T, A, S>::traits_type>&
2299operator>>(
2300    std::basic_istream<typename flex_string<E, T, A, S>::value_type,
2301    typename flex_string<E, T, A, S>::traits_type>& is,
2302    flex_string<E, T, A, S>& str);
2303
2304template <typename E, class T, class A, class S>
2305std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
2306    typename flex_string<E, T, A, S>::traits_type>&
2307operator<<(
2308    std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
2309    typename flex_string<E, T, A, S>::traits_type>& os,
2310    const flex_string<E, T, A, S>& str)
2311{ return os << str.c_str(); }
2312
2313template <typename E, class T, class A, class S>
2314std::basic_istream<typename flex_string<E, T, A, S>::value_type,
2315    typename flex_string<E, T, A, S>::traits_type>&
2316getline(
2317    std::basic_istream<typename flex_string<E, T, A, S>::value_type,
2318        typename flex_string<E, T, A, S>::traits_type>& is,
2319    flex_string<E, T, A, S>& str,
2320    typename flex_string<E, T, A, S>::value_type delim);
2321
2322template <typename E, class T, class A, class S>
2323std::basic_istream<typename flex_string<E, T, A, S>::value_type,
2324    typename flex_string<E, T, A, S>::traits_type>&
2325getline(
2326    std::basic_istream<typename flex_string<E, T, A, S>::value_type,
2327        typename flex_string<E, T, A, S>::traits_type>& is,
2328    flex_string<E, T, A, S>& str);
2329
2330template <typename E1, class T, class A, class S>
2331const typename flex_string<E1, T, A, S>::size_type
2332flex_string<E1, T, A, S>::npos = (typename flex_string<E1, T, A, S>::size_type)(-1);
2333
2334///////////////////////////////////////////////////////////////////////////////
2335}   // namespace util
2336}   // namespace wave
2337}   // namespace boost
2338
2339#endif // FLEX_STRING_INC_
Note: See TracBrowser for help on using the repository browser.