Wave: a Standard conformant C++ preprocessor library

// This code is taken from
// Generic<Programming>: A Policy-Based basic_string Implementation
// Copyright(c) Andrei Alexandrescu
// The code is considered to be in the public domain.
// http://www.cuj.com/experts/1906/alexandr.htm?topic=experts
//
// #HK030306: 
//      - Moved into the namespace wave::util 
//      - Added a bunch of missing typename(s) 
//      - Integrated with boost config
//      - Added a missing header include
//      - Added special constructors and operator= to allow CowString to be 
//        a real COW-string (removed unnecessary data copying)
//

#ifndef FLEX_STRING_INC_
#define FLEX_STRING_INC_

#include <boost/config.hpp>

#include <memory>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stdexcept>

#if defined(BOOST_NO_STD_ALLOCATOR)
#define NO_ALLOCATOR_REBIND
#endif
#if defined(BOOST_NO_STD_ITERATOR_TRAITS)
#define NO_ITERATOR_TRAITS
#endif

namespace wave {
namespace util {

////////////////////////////////////////////////////////////////////////////////
// class template SimpleStringStorage
// Allocates memory with new
////////////////////////////////////////////////////////////////////////////////

template <typename E, class A = std::allocator<E> >
class SimpleStringStorage
{
    // The "public" below exists because MSVC can't do template typedefs
public:
    struct Data
    {
        E* pEnd_;
        E* pEndOfMem_;
        E buffer_[1];
    };
    static const Data emptyString_;
    
    typedef typename A::size_type size_type;

private:
    Data* pData_;

    void Init(size_type size, size_type capacity)
    {
        assert(size <= capacity);
        if (capacity == 0)
        {
            pData_ = const_cast<Data*>(&emptyString_);
        }
        else
        {
            pData_ = static_cast<Data*>(
                operator new(sizeof(Data) + capacity * sizeof(E)));
            assert(pData_ != 0);
            pData_->pEnd_ = pData_->buffer_ + size;
            pData_->pEndOfMem_ = pData_->buffer_ + capacity;
        }
    }
    
private:
    // Warning - this doesn't initialize pData_. Used in reserve()
    SimpleStringStorage()
    {}
    
public:
    typedef E* iterator;
    typedef const E* const_iterator;
    typedef A allocator_type;
    
    SimpleStringStorage(const SimpleStringStorage& s) 
    {
        Init(s.size(), s.size());
        // s.end() + 1 to get the terminating zero as well
        if (size()) std::uninitialized_copy(s.begin(), s.end() + 1, begin());
    }
    
    SimpleStringStorage(const A&)
    { pData_ = const_cast<Data*>(&emptyString_); }
    
    SimpleStringStorage(const E* s, size_type len, const A&)
    {
        Init(len, len);        
        std::uninitialized_copy(s, s + len, begin());
        // Terminating zero
        if (size()) new(end()) E(0);
    }

    SimpleStringStorage(size_type len, E c, const A&)
    {
        Init(len, len);
        std::uninitialized_fill(begin(), end(), c);
        // Terminating zero
        if (size()) new(end()) E(0);
    }
    
    ~SimpleStringStorage()
    {
        assert(begin() <= end());

        for (iterator i = end(); i != begin(); )
        {
            --i;
            i->~E();
        }

        if (pData_ != &emptyString_)
        {
            end()->~E();
            operator delete(pData_);
        }
    }

    SimpleStringStorage &operator= (SimpleStringStorage const &s)
    {
        if (&s == this) return *this;
        
        for (iterator i = end(); i != begin(); )
        {
            --i;
            i->~E();
        }
        if (pData_ != &emptyString_)
        {
            end()->~E();
            operator delete(pData_);
        }
        
        Init(s.size(), s.size());
        // s.end() + 1 to get the terminating zero as well
        if (size()) std::uninitialized_copy(s.begin(), s.end() + 1, begin());

        return *this;
    }
    
    iterator begin()
    { return pData_->buffer_; }
    
    const_iterator begin() const
    { return pData_->buffer_; }
    
    iterator end()
    { return pData_->pEnd_; }
    
    const_iterator end() const
    { return pData_->pEnd_; }
    
    size_type size() const
    { return pData_->pEnd_ - pData_->buffer_; }

    size_type max_size() const
    { return std::size_t(-1) / sizeof(E) - sizeof(Data) - 1; }

    size_type capacity() const
    { return pData_->pEndOfMem_ - pData_->buffer_; }

    void resize(size_type n, E c)
    {
        reserve(n);
        iterator newEnd = begin() + n;
        if (n > size()) std::uninitialized_fill(end(), newEnd, c);
        pData_->pEnd_ = newEnd;
    }

    void reserve(size_type res_arg)
    {
        if (res_arg <= capacity())
        {
            if (res_arg <= capacity() / 2)
            {
                // shrink to fit
                SimpleStringStorage temp(*this);
                if (temp.capacity() < res_arg) temp.reserve(res_arg);
                temp.swap(*this);
            }
            return;
        }
        
        SimpleStringStorage newStr;
        newStr.Init(size(), res_arg);
        
        // end() + 1 to copy the null terminator, too
        std::uninitialized_copy(begin(), end() + 1, newStr.begin());
        
        swap(newStr);
    }
    
    void swap(SimpleStringStorage& rhs)
    {
        std::swap(pData_, rhs.pData_);
    }
    
    const E* c_str() const
    { return pData_->buffer_; }

    const E* data() const
    { return pData_->buffer_; }
    
    A get_allocator() const
    { return A(); }
};

template <typename E, class A>
const typename SimpleStringStorage<E, A>::Data
SimpleStringStorage<E, A>::emptyString_ = 
{ 
    const_cast<E*>(emptyString_.buffer_), 
    const_cast<E*>(emptyString_.buffer_), 
    { E(0) }
};

////////////////////////////////////////////////////////////////////////////////
// class template AllocatorStringStorage
// Allocates with your allocator
// Takes advantage of the Empty Base Optimization if available
////////////////////////////////////////////////////////////////////////////////

template <typename E, class A = std::allocator<E> >
class AllocatorStringStorage : public A
{
    typedef typename A::size_type size_type;
    typedef typename SimpleStringStorage<E, A>::Data Data;

    typedef 
#ifdef NO_ALLOCATOR_REBIND
    std::allocator<Data>
#else
    typename A::template rebind<Data>::other
#endif
        data_allocator;

    // EBO = Empty Base Optimization
    // Exploit EBO for char_allocator
    struct EBO : public data_allocator
    {
        typedef typename data_allocator::size_type size_type;
#ifdef NO_ALLOCATOR_REBIND
        static data_allocator ConvertAllocator(const A&)
        { return data_allocator(); }
#else
        static data_allocator ConvertAllocator(const A& a)
        { return data_allocator(a); }
#endif

        EBO(const A& a) : data_allocator(ConvertAllocator(a))
        {}

        Data* pData_;

        void Init(size_type size, size_type cap)
        {
            assert(size <= cap);

            if (cap == 0)
            {
                pData_ = const_cast<Data*>(
                    &SimpleStringStorage<E, A>::emptyString_);
            }
            else
            {
                const size_type dataBlocks = 1 + 
                    (cap * sizeof(E) + sizeof(Data) - 1) / sizeof(Data);
                cap = ((dataBlocks - 1) * sizeof(Data)) / sizeof(E);
                pData_ = allocate(dataBlocks, 0);
                pData_->pEnd_ = pData_->buffer_ + size;
                pData_->pEndOfMem_ = pData_->buffer_ + cap;
            }
        }
    } ebo_;

public: //protected:
    typedef A allocator_type;
    typedef typename A::pointer iterator;
    typedef typename A::const_pointer const_iterator;
    
    AllocatorStringStorage(const AllocatorStringStorage& s) 
    : A(s.get_allocator()), ebo_(s.get_allocator())
    {
        size_type len = s.size();
        ebo_.Init(len, len);
        // s.end() + 1 to get the terminating zero as well
        if (size()) 
            std::uninitialized_copy(s.begin(), s.end() + 1, begin());
    }
    
    AllocatorStringStorage(const A& a) : A(a), ebo_(a)
    { 
        ebo_.pData_ = const_cast<Data*>(
            &SimpleStringStorage<E, A>::emptyString_);
    }
    
    AllocatorStringStorage(const E* s, size_type len, const A& a)
    : A(a), ebo_(a)
    {
        ebo_.Init(len, len);        
        std::uninitialized_copy(s, s + len, begin());
        // Terminating zero
        if (size()) 
            new(end()) E(0);
    }

    AllocatorStringStorage(size_type len, E c, const A& a)
    : A(a), ebo_(a)
    {
        ebo_.Init(len, len);
        std::uninitialized_fill(begin(), end(), c);
        // Terminating zero
        if (size()) 
            new(end()) E(0);
    }
    
    ~AllocatorStringStorage()
    {
        iterator start = begin();
        for (iterator i = end(); i != start; )
        {
            A::destroy(&*--i);
        }

        if (size())
        {
            ebo_.deallocate(ebo_.pData_, 1 + 
                (capacity() * sizeof(E) + sizeof(Data) - 1) / sizeof(Data));
        }
    }

    AllocatorStringStorage &operator= (AllocatorStringStorage const &s)
    {
        if (&s == this) 
            return *this;
        
        iterator start (begin());
        for (iterator i = end(); i != start; /**/)
        {
            A::destroy(&*--i);
        }
        if (size())
        {
            ebo_.deallocate(ebo_.pData_, 1 + 
                (capacity() * sizeof(E) + sizeof(Data) - 1) / sizeof(Data));
        }
        
        size_type len = s.size();
        ebo_.Init(len, len);
        // s.end() + 1 to get the terminating zero as well
        if (size()) 
            std::uninitialized_copy(s.begin(), s.end() + 1, begin());

        return *this;
    }
    
    iterator begin()
    { return ebo_.pData_->buffer_; }
    
    const_iterator begin() const
    { return ebo_.pData_->buffer_; }
    
    iterator end()
    { return ebo_.pData_->pEnd_; }
    
    const_iterator end() const
    { return ebo_.pData_->pEnd_; }
    
    size_type size() const
    { return ebo_.pData_->pEnd_ - ebo_.pData_->buffer_; }

    size_type max_size() const
    { return A::max_size(); }

    size_type capacity() const
    { return ebo_.pData_->pEndOfMem_ - ebo_.pData_->buffer_; }

    void resize(size_type n, E c)
    {
        reserve(n);
        if (n > size()) 
            std::uninitialized_fill(end(), begin() + n, c);
        ebo_.pData_->pEnd_ = begin() + n;
    }

    void reserve(size_type res_arg)
    {
        if (res_arg <= capacity())
        {
            if (res_arg <= capacity() / 2)
            {
                // shrink to fit
                AllocatorStringStorage temp(*this);
                if (temp.capacity() < res_arg) 
                    temp.reserve(res_arg);
                temp.swap(*this);
            }
            return;
        }
        
        AllocatorStringStorage newStr(get_allocator());
        newStr.ebo_.Init(size(), res_arg);
        
        // end() + 1 to copy the null terminator, too
        std::uninitialized_copy(begin(), end() + 1, newStr.begin());
        
        swap(newStr);
    }
    
    void swap(AllocatorStringStorage& rhs)
    {
        // The following line is commented due to a bug in MSVC
        //std::swap(lhsAlloc, rhsAlloc);
        std::swap(ebo_, rhs.ebo_);
    }
    
    const E* c_str() const
    { return &*begin(); }

    const E* data() const
    { return &*begin(); }
    
    A get_allocator() const
    { return *this; }
};

////////////////////////////////////////////////////////////////////////////////
// class template VectorStringStorage
// Uses std::vector
// Takes advantage of the Empty Base Optimization if available
////////////////////////////////////////////////////////////////////////////////

template <typename E, class A = std::allocator<E> >
class VectorStringStorage : protected std::vector<E, A>
{
    typedef std::vector<E, A> base;
    typedef typename A::size_type size_type;

public: // protected:
    typedef typename base::iterator iterator;
    typedef typename base::const_iterator const_iterator;
    typedef A allocator_type;
    
    VectorStringStorage(const VectorStringStorage& s) : base(s)
    { }
    
    VectorStringStorage(const A& a) : base(1, E(0), a)
    { }
    
    VectorStringStorage(const E* s, size_type len, const A& a)
    : base(a)
    {
        base::reserve(len + 1);
        base::insert(base::end(), s, s + len);
        // Terminating zero
        base::insert(base::end(), E(0));
    }

    VectorStringStorage(size_type len, E c, const A& a)
    : base(len + 1, c, a)
    {
        // Terminating zero
        base::back() = E(0);
    }

    VectorStringStorage &operator= (VectorStringStorage const &s)
    {
        if (&s == this) return *this;
        base::clear();
        
        base::reserve(len + 1);
        base::insert(base::end(), s, s + len);
        // Terminating zero
        base::insert(base::end(), E(0));
        
        return *this;
    }
        
    iterator begin()
    { return base::begin(); }
    
    const_iterator begin() const
    { return base::begin(); }
    
    iterator end()
    { return base::end() - 1; }
    
    const_iterator end() const
    { return base::end() - 1; }
    
    size_type size() const
    { return base::size() - 1; }

    size_type max_size() const
    { return base::max_size() - 1; }

    size_type capacity() const
    { return base::capacity() - 1; }

    void resize(size_type n, E c)
    {
        base::reserve(n + 1);
        base::back() = c;
        base::resize(n + 1, c);
        base::back() = E(0);
    }

    void reserve(size_type res_arg)
    { base::reserve(res_arg + 1); }
    
    void swap(VectorStringStorage& rhs)
    { base::swap(rhs); }
    
    const E* c_str() const
    { return &*begin(); }

    const E* data() const
    { return &*begin(); }
    
    A get_allocator() const
    { return base::get_allocator(); }
};

////////////////////////////////////////////////////////////////////////////////
// class template SmallStringOpt
// Builds the small string optimization over any other storage
////////////////////////////////////////////////////////////////////////////////

template <typename E, unsigned int threshold, class Storage, typename Align = E*>
class SmallStringOpt
{
    enum { temp1 = threshold * sizeof(E) > sizeof(Storage) 
        ? threshold  * sizeof(E) 
        : sizeof(Storage) };
    
    enum { temp2 = temp1 > sizeof(Align) ? temp1 : sizeof(Align) };

public:
    enum { maxSmallString = (temp2 + sizeof(E) - 1) / sizeof(E) };
    
private:
    enum { magic = maxSmallString + 1 };
    
    union
    {
        E buf_[maxSmallString + 1];
        Align align_;
    };
    
    Storage& GetStorage()
    {
        assert(buf_[maxSmallString] == magic);
        Storage* p = reinterpret_cast<Storage*>(&buf_[0]);
        return *p;
    }
    
    const Storage& GetStorage() const
    {
        assert(buf_[maxSmallString] == magic);
        const Storage *p = reinterpret_cast<const Storage*>(&buf_[0]);
        return *p;
    }
    
    bool Small() const
    {
        return buf_[maxSmallString] != magic;
    }

public:
    typedef typename Storage::iterator iterator;
    typedef typename Storage::const_iterator const_iterator;
    typedef typename Storage::allocator_type allocator_type;
    typedef typename allocator_type::size_type size_type;
    
    SmallStringOpt(const SmallStringOpt& s)
    {
        if (s.Small())
        {
            std::uninitialized_copy(s.buf_, s.buf_ + s.size() + 1, 
                buf_);
            new(&buf_[maxSmallString]) E(s.buf_[maxSmallString]);
        }
        else
        {
            new(buf_) Storage(s.GetStorage());
            new(&buf_[maxSmallString]) E(magic);
        }
    }
    
    SmallStringOpt(const allocator_type&)
    {
        new(buf_) E(0);
        new(&buf_[maxSmallString]) E(maxSmallString);
    }
    
    SmallStringOpt(const E* s, size_type len, const allocator_type& a)
    {
        if (len <= maxSmallString)
        {
            std::uninitialized_copy(s, s + len, buf_);
            buf_[len] = E(0);
            buf_[maxSmallString] = E(maxSmallString - len);
        }
        else
        {
            new(buf_) Storage(s, len, a);
            new(&buf_[maxSmallString]) E(magic);
        }
    }

    SmallStringOpt(size_type len, E c, const allocator_type& a)
    {
        if (len <= maxSmallString)
        {
            std::uninitialized_fill(buf_, buf_ + len, c);
            new(&buf_[len]) E(0);
            new(&buf_[maxSmallString]) E(
                static_cast<E>(maxSmallString - len));
        }
        else
        {
            new(buf_) Storage(len, c, a);
            new(&buf_[maxSmallString]) E(magic);
        }
    }
    
    ~SmallStringOpt()
    {
        if (!Small()) GetStorage().~Storage();
    }

    SmallStringOpt& operator=(const SmallStringOpt& s)
    {
        if (&s == this) return *this;
        
        if (!Small()) GetStorage().~Storage();

        if (s.Small())
        {
            std::uninitialized_copy(s.buf_, s.buf_ + s.size() + 1, 
                buf_);
            new(&buf_[maxSmallString]) E(s.buf_[maxSmallString]);
        }
        else 
        {
            new(buf_) Storage(s.GetStorage());
            new(&buf_[maxSmallString]) E(magic);
        }
        return *this;
    }

    iterator begin()
    {
        if (Small()) return buf_;
        return GetStorage().begin(); 
    }
    
    const_iterator begin() const
    {
        if (Small()) return buf_;
        return GetStorage().begin(); 
    }
    
    iterator end()
    {
        if (Small()) return buf_ + size();
        return GetStorage().end(); 
    }
    
    const_iterator end() const
    {
        if (Small()) return buf_ + size();
        return GetStorage().end(); 
    }
    
    size_type size() const
    {
        return Small() 
            ? maxSmallString - buf_[maxSmallString] 
            : GetStorage().size();
    }

    size_type max_size() const
    { return Small() ? std::size_t(-1) / sizeof(E) : GetStorage().max_size(); }

    size_type capacity() const
    { return Small() ? maxSmallString : GetStorage().capacity(); }

    void resize(size_type n, E c)
    {
        if (Small())
        {
            if (n > maxSmallString)
            {
                // Small string resized to big string
                SmallStringOpt temp(*this); // can't throw
                this->~SmallStringOpt();
                new(&buf_[0]) Storage(temp.data(), temp.size(), 
                    temp.get_allocator());
                new(&buf_[maxSmallString]) E(magic);
                GetStorage().resize(n, c);
            }
            else
            {
                // Small string resized to small string
                size_type toFill = n > size() ? n - size() : 0;
                std::uninitialized_fill(end(), end() + toFill, c);
                buf_[maxSmallString] = E(maxSmallString - n);
            }
        }
        else
        {
            if (n > maxSmallString)
            {
                // Big string resized to big string
                GetStorage().resize(n, c);
            }
            else
            {
                // Big string resized to small string
                assert(size() > n);
                SmallStringOpt newObj(data(), n, get_allocator());
                newObj.swap(*this);
            }
        }
    }

    void reserve(size_type res_arg)
    {
        if (Small())
        {
            if (res_arg <= maxSmallString) return;
            SmallStringOpt temp(*this);
            this->~SmallStringOpt();
            new(buf_) Storage(temp.data(), temp.size(), 
                temp.get_allocator());
            new(&buf_[maxSmallString]) E(magic);
            GetStorage().reserve(res_arg);
        }
        else
        {
            GetStorage().reserve(res_arg);
        }
        assert(capacity() >= res_arg);
    }
    
    void swap(SmallStringOpt& rhs)
    {
        if (Small())
        {
            if (rhs.Small())
            {
                // Small swapped with small
                std::swap_ranges(buf_, buf_ + maxSmallString + 1, 
                    rhs.buf_);
            }
            else
            {
                // Small swapped with big
                // Make a copy of myself - can't throw
                SmallStringOpt temp(*this);
                // Nuke myself
                this->~SmallStringOpt();
                // Make an empty storage for myself (likely won't throw)
                new(buf_) Storage(0, E(0), rhs.get_allocator());
                new(&buf_[maxSmallString]) E(magic);
                // Recurse to this same function
                swap(rhs);
                // Nuke rhs
                rhs.~SmallStringOpt();
                // Build the new small string into rhs
                new(&rhs) SmallStringOpt(temp);
            }
        }
        else
        {
            if (rhs.Small())
            {
                // Big swapped with small
                // Already implemented, recurse with reversed args
                rhs.swap(*this);
            }
            else
            {
                // Big swapped with big
                GetStorage().swap(rhs.GetStorage());
            }
        }
    }
    
    const E* c_str() const
    { return &*begin(); }

    const E* data() const
    { return &*begin(); }
    
    allocator_type get_allocator() const
    { return allocator_type(); }
};

////////////////////////////////////////////////////////////////////////////////
// class template CowString
// Implements Copy on Write over any storage
////////////////////////////////////////////////////////////////////////////////

template <typename E, class Storage>
class CowString
{
public:
    typedef typename Storage::allocator_type allocator_type;
    typedef typename allocator_type::size_type size_type;
    
private:
    struct Data
    {
        Storage s_;
        unsigned int refs_;

        Data(const Data& d)
            : s_(d.s_), refs_(1)
        {}

        Data(const allocator_type& a)
            : s_(a), refs_(1)
        {}

        Data(const E* s, size_type len, const allocator_type& a)
            : s_(s, len, a), refs_(1)
        {}

        Data(size_type len, E c, const allocator_type& a)
            : s_(len, c, a), refs_(1)
        {}
    };

    Data* pData_;
    
    Storage& GetStorage_()
    {
        assert(pData_);
        return pData_->s_;
    }
    
    const Storage& GetStorage_() const
    {
        assert(pData_);
        return pData_->s_;
    }

    void MakeUnique()
    {
        if (pData_->refs_ > 1) 
            pData_ = new Data(*pData_);
        assert(pData_->refs_ == 1);
    }

public:
    class iterator;
    friend class iterator;
    class const_iterator;
    friend class const_iterator;

    class iterator
    {
        friend class const_iterator;

        CowString* pParent_;
        mutable typename Storage::iterator iter_;

        void MakeUnique() const
        {
            if (pParent_ == 0) return;

            const difference_type offset = 
                iter_ - pParent_->pData_->s_.begin();
            pParent_->MakeUnique();
            iter_ = pParent_->pData_->s_.begin() + offset;
        }

    public:
        typedef std::random_access_iterator_tag iterator_category;
        typedef E value_type;
        typedef typename allocator_type::difference_type difference_type;
        typedef typename allocator_type::pointer pointer;
        typedef typename allocator_type::reference reference;

        iterator() : pParent_(0)
        {
        }

        iterator(typename Storage::iterator i) 
            : pParent_(0), iter_(i)
        {
        }

        iterator(CowString* pS, typename Storage::iterator i) 
            : pParent_(pS), iter_(i)
        {
        }

        reference operator*() const
        {
            MakeUnique();
            return *iter_;
        }

        iterator& operator++()
        {
            ++iter_;
            return *this;
        }

        iterator operator++(int)
        {
            iterator tmp(*this);
            ++*this;
            return tmp;
        }

        iterator& operator--()
        {
            --iter_;
            return *this;
        }

        iterator operator--(int)
        {
            iterator tmp(*this);
            --*this;
            return tmp;
        }

        iterator& operator+=(difference_type offset)
        {
            iter_ += offset;
            return *this;
        }

        iterator operator+(difference_type offset) const
        {
            iterator tmp(*this);
            return tmp += offset;
        }

        iterator& operator-=(difference_type offset)
        {
            iter_ -= offset;
            return *this;
        }

        iterator operator-(difference_type offset) const
        {
            iterator tmp(*this);
            return tmp -= offset;
        }

        difference_type operator-(const iterator& rhs) const
        {
            return iter_ - rhs.iter_;
        }

        reference operator[](difference_type offset) const
        {
            MakeUnique();
            return iter_[offset];
        }

        bool operator==(const iterator& rhs) const
        {
            return iter_ == rhs.iter_;
        }

        bool operator!=(const iterator& rhs) const
        {
            return !(*this == rhs);
        }

        bool operator<(const iterator& rhs) const
        {
            return iter_ < rhs.iter_;
        }

        bool operator>(const iterator& rhs) const
        {
            return rhs < *this;
        }

        bool operator<=(const iterator& rhs) const
        {
            return !(rhs < *this);
        }

        bool operator>=(const iterator& rhs) const
        {
            return !(*this < rhs);
        }

        friend iterator operator+(difference_type lhs,
            const iterator& rhs)
        {
            return rhs + lhs;
        }
    };
    
    class const_iterator
        : public std::iterator<std::random_access_iterator_tag, E>
    {
    protected:
        mutable typename Storage::const_iterator iter_;
    
    public:
        typedef std::random_access_iterator_tag iterator_category;
        typedef E value_type;
        typedef typename allocator_type::difference_type difference_type;
        typedef typename allocator_type::const_pointer pointer;
        typedef typename allocator_type::const_reference reference;

        const_iterator()
        {
        }

        const_iterator(typename Storage::const_iterator i) : iter_(i)
        {
        }

        const_iterator(typename Storage::iterator i) : iter_(i.iter_)
        {
        }

        reference operator*() const
        {
            return *iter_;
        }

        const_iterator& operator++()
        {
            ++iter_;
            return *this;
        }

        const_iterator operator++(int)
        {
            const_iterator tmp(*this);
            ++*this;
            return tmp;
        }

        const_iterator& operator--()
        {
            --iter_;
            return *this;
        }

        const_iterator operator--(int)
        {
            const_iterator tmp(*this);
            --*this;
            return tmp;
        }

        const_iterator& operator+=(difference_type offset)
        {
            iter_ += offset;
            return *this;
        }

        const_iterator operator+(difference_type offset) const
        {
            const_iterator tmp(*this);
            return tmp += offset;
        }

        const_iterator& operator-=(difference_type offset)
        {
            iter_ -= offset;
            return *this;
        }

        const_iterator operator-(difference_type offset) const
        {
            const_iterator tmp(*this);
            return tmp -= offset;
        }

        difference_type operator-(const const_iterator& rhs) const
        {
            return iter_ - rhs.iter_;
        }

        reference operator[](difference_type offset) const
        {
            return iter_[offset];
        }

        bool operator==(const const_iterator& rhs) const
        {
            return iter_ == rhs.iter_;
        }

        bool operator!=(const const_iterator& rhs) const
        {
            return !(*this == rhs);
        }

        bool operator<(const const_iterator& rhs) const
        {
            return iter_ < rhs.iter_;
        }

        bool operator>(const const_iterator& rhs) const
        {
            return rhs < *this;
        }

        bool operator<=(const const_iterator& rhs) const
        {
            return !(rhs < *this);
        }

        bool operator>=(const const_iterator& rhs) const
        {
            return !(*this < rhs);
        }

        friend const_iterator operator+(difference_type lhs,
            const const_iterator& rhs)
        {
            return rhs + lhs;
        }
    };

public:
    
    CowString(const CowString& s)
    : pData_(s.pData_)
    {
        ++pData_->refs_;
    }
    
    CowString(const allocator_type& a)
        : pData_(new Data(a))
    {}
    
    CowString(const E* s, size_type len, const allocator_type& a)
        : pData_(new Data(s, len, a))
    {}

    CowString(size_type len, E c, const allocator_type& a)
        : pData_(new Data(len, c, a))
    {}
    
    ~CowString()
    {
        if (--pData_->refs_ == 0) delete pData_;
    }

    CowString& operator=(const CowString& s)
    {
        if (&s == this) return *this;
        if (--pData_->refs_ == 0) delete pData_;
        pData_ = s.pData_;
        ++pData_->refs_;
        return *this;
    }
    
    iterator begin()
    {
        return iterator(this, GetStorage_().begin()); 
    }
    
    const_iterator begin() const
    {
        return GetStorage_().begin(); 
    }
    
    iterator end()
    {
        return iterator(this, GetStorage_().end()); 
    }
    
    const_iterator end() const
    {
        return GetStorage_().end(); 
    }
    
    size_type size() const
    { 
        return GetStorage_().size();
    }

    size_type max_size() const
    { 
        return GetStorage_().max_size();
    }

    size_type capacity() const
    { 
        return GetStorage_().capacity();
    }

    void resize(size_type n, E c)
    {
        MakeUnique();
        GetStorage_().resize(n, c);
    }

    void reserve(size_type res_arg)
    {
        MakeUnique();
        GetStorage_().reserve(res_arg);
    }
    
    void swap(CowString& rhs)
    {
        std::swap(pData_, rhs.pData_);
    }
    
    const E* c_str() const
    { 
        return GetStorage_().c_str();
    }

    const E* data() const
    { 
        return GetStorage_().data();
    }
    
    allocator_type get_allocator() const
    { 
        return GetStorage_().get_allocator();
    }
};

////////////////////////////////////////////////////////////////////////////////
// class template flex_string
// a std::basic_string compatible implementation 
// Uses a Storage policy 
////////////////////////////////////////////////////////////////////////////////

template <typename E,
    class T = std::char_traits<E>,
    class A = std::allocator<E>,
    class Storage = AllocatorStringStorage<E, A> >
class flex_string : private Storage
{
#if defined(THROW_ON_ENFORCE)
    template <typename Exception>
    static inline void Enforce(bool condition, Exception*, const char* msg)
    { if (!condition) throw Exception(msg); }
#else
    template <typename Exception>
    static inline void Enforce(bool condition, Exception*, const char* msg)
    { assert(condition && msg); }
#endif // defined(THROW_ON_ENFORCE)

public:
    // types
    typedef T traits_type;
    typedef typename traits_type::char_type value_type;
    typedef A allocator_type;
    typedef typename A::size_type size_type;
    typedef typename A::difference_type difference_type;
    
    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;
    typedef typename A::pointer pointer;
    typedef typename A::const_pointer const_pointer;
    
    typedef typename Storage::iterator iterator;
    typedef typename Storage::const_iterator const_iterator;
    typedef std::reverse_iterator<iterator
#ifdef NO_ITERATOR_TRAITS
    , value_type
#endif
    > reverse_iterator;
    typedef std::reverse_iterator<const_iterator
#ifdef NO_ITERATOR_TRAITS
    , const value_type 
#endif
    > const_reverse_iterator;

    static const size_type npos;    // = size_type(-1)

private:
    static size_type Min(size_type lhs, size_type rhs)
    { return lhs < rhs ? lhs : rhs; }
    
public:    
    // 21.3.1 construct/copy/destroy
    explicit flex_string(const A& a = A())
    : Storage(a) 
    {}
    
    flex_string(const flex_string& str, size_type pos, 
        size_type n = npos, const A& a = A())
    : Storage(str) 
    {
        Enforce(pos <= str.size(), (std::out_of_range*)0, "");
        assign(str, pos, n);
    }
    
    flex_string(const flex_string& str)
    : Storage(str) 
    {
    }
    
    flex_string(const value_type* s, const A& a = A())
    : Storage(s, traits_type::length(s), a)
    {}
    
    flex_string(const value_type* s, size_type n, const A& a = A())
    : Storage(s, n, a)
    {}
    
    flex_string(size_type n, value_type c, const A& a = A())
    : Storage(n, c, a)
    {}
    
    template <class InputIterator>
    flex_string(InputIterator begin, InputIterator end, const A& a = A())
    : Storage(a)
    {
        // to do: optimize depending on iterator type
        for (; begin != end; ++begin) *this += E(*begin);
    }

    ~flex_string()
    {}
    
    flex_string& operator=(const flex_string& str)
    {
        if (&str == this) return *this;
        static_cast<Storage &>(*this) = str;
        return *this;
    }
    
    flex_string& operator=(const value_type* s)
    {
        flex_string(s).swap(*this);
        return *this;
    }

    flex_string& operator=(value_type c)
    {
        assign(&c, 1);
        return *this;
    }
    
    // 21.3.2 iterators:
    iterator begin()
    { return Storage::begin(); }
    
    const_iterator begin() const
    { return Storage::begin(); }
    
    iterator end()
    { return Storage::end(); }
    
    const_iterator end() const
    { return Storage::end(); }

    reverse_iterator rbegin()
    { return reverse_iterator(end()); }
    
    const_reverse_iterator rbegin() const
    { return const_reverse_iterator(end()); }
    
    reverse_iterator rend()
    { return reverse_iterator(begin()); }
    
    const_reverse_iterator rend() const
    { return const_reverse_iterator(begin()); }
    
    // 21.3.3 capacity:
    size_type size() const
    { return Storage::size(); }
    
    size_type length() const
    { return size(); }
    
    size_type max_size() const
    { return Storage::max_size(); }

    void resize(size_type n, value_type c)
    { Storage::resize(n, c); }
    
    void resize(size_type n)
    { resize(n, E(0)); }
    
    size_type capacity() const
    { return Storage::capacity(); }
    
    void reserve(size_type res_arg = 0)
    {
        Enforce(res_arg <= max_size(), (std::length_error*)0, "");
        Storage::reserve(res_arg);
    }
    
    void clear()
    { resize(0); } 
    
    bool empty() const
    { return size() == 0; }
    
    // 21.3.4 element access:
    const_reference operator[](size_type pos) const
    { return *(begin() + pos); }
    
    reference operator[](size_type pos)
    { return *(begin() + pos); }

    const_reference at(size_type n) const
    {
        Enforce(n < size(), (std::out_of_range*)0, "");
        return (*this)[n];
    }
    
    reference at(size_type n)
    {
        Enforce(n < size(), (std::out_of_range*)0, "");
        return (*this)[n];
    }
    
    // 21.3.5 modifiers:
    flex_string& operator+=(const flex_string& str)
    { return append(str); }
    
    flex_string& operator+=(const value_type* s)
    { return append(s); }

    flex_string& operator+=(value_type c)
    { return append(1, c); }
    
    flex_string& append(const flex_string& str)
    { return append(str, 0, npos); }
    
    flex_string& append(const flex_string& str, size_type pos,
        size_type n)
    { return insert(size(), str, pos, n); }
    
    flex_string& append(const value_type* s, size_type n)
    { return insert(size(), s, n); }
    
    flex_string& append(const value_type* s)
    { return append(s, traits_type::length(s)); }
    
    flex_string& append(size_type n, value_type c)
    { return insert(size(), n, c); }
    
    template<class InputIterator>
    flex_string& append(InputIterator first, InputIterator last)
    {
        for (; first != last; ++first) *this += E(*first);
        return *this;
    }
    
    flex_string& assign(const flex_string& str)
    { return assign(str, 0, npos); }
    
    flex_string& assign(const flex_string& str, size_type pos,
        size_type n)
    { 
        Enforce(pos <= str.size(), (std::out_of_range*)0, "");
        return assign(&*(str.begin() + pos), Min(n, str.size() - pos));
    }
    
    flex_string& assign(const value_type* s, size_type n)
    { return replace(begin(), end(), s, n); }
    
    flex_string& assign(const value_type* s)
    { return assign(s, traits_type::length(s)); }
    
    flex_string& assign(size_type n, value_type c)
    { return replace(begin(), end(), n, c); } 
    
    template<class InputIterator>
    flex_string& assign(InputIterator first, InputIterator last)
    { return replace(begin(), end(), first, last); }
    
    flex_string& insert(size_type pos1, const flex_string& str)
    { return insert(pos1, str, 0, npos); }
    
    flex_string& insert(size_type pos1, const flex_string& str,
        size_type pos2, size_type n)
    { return replace(pos1, 0, str, pos2, n); }
    
    flex_string& insert(size_type pos, const value_type* s, size_type n)
    { return replace(pos, 0, s, n); }
    
    flex_string& insert(size_type pos, const value_type* s)
    { return insert(pos, s, traits_type::length(s)); }
    
    flex_string& insert(size_type pos, size_type n, value_type c)
    { return replace(pos, 0, n, c); }
    
    iterator insert(iterator p, value_type c = value_type()) 
    {
        const size_type pos = p - begin();
        insert(pos, &c, 1);
        return begin() + pos;
    }
    
    void insert(iterator p, size_type n, value_type c)
    { insert(p - begin(), n, c); }
    
    template<class InputIterator>
    void insert(iterator p, InputIterator first, InputIterator last)
    { replace(p, p, first, last); }
    
    flex_string& erase(size_type pos = 0, size_type n = npos)
    { return replace(pos, n, 0, value_type()); }
    
    iterator erase(iterator position)
    {
        const size_type pos(position - begin());
        erase(pos, 1);
        return begin() + pos;
    }
    
    iterator erase(iterator first, iterator last)
    {
        const size_type pos(first - begin());
        erase(pos, last - first);
        return begin() + pos;
    }
    
    flex_string& replace(size_type pos1, size_type n1, const flex_string& str)
    { return replace(pos1, n1, str, 0, npos); }
    
    flex_string& replace(size_type pos1, size_type n1, const flex_string& str,
        size_type pos2, size_type n2)
    {
        Enforce(pos1 <= length() && pos2 <= str.length(), 
            (std::out_of_range*)0, "");
        return replace(pos1, n1, &*str.begin() + pos2, Min(n2, str.length() - pos2));
    }
    
    flex_string& replace(size_type pos, size_type n1, const value_type* s,
        size_type n2)
    {
        Enforce(pos <= size(), (std::length_error*)0, "");
        n1 = Min(size() - pos, n1);
        
        Enforce(n2 <= max_size() - pos, (std::length_error*)0, "");
        Enforce(size() - n1 <= max_size() - n2, (std::length_error*)0, "");

        const size_type oldSize = size();
        if (n1 < n2) resize(oldSize - n1 + n2);

        traits_type::move(
            &*begin() + pos + n2,
            &*begin() + pos + n1, 
            oldSize - pos - n1);
            
        std::copy(
            s,
            s + n2,
            begin() + pos);

        if (pos + n2 > oldSize)    // ensure trailing '\0'
            *(begin() + pos + n2) = value_type(0);
            
        if (n1 > n2) resize(size() - n1 + n2);
        
        return *this;
    }
    
    flex_string& replace(size_type pos, size_type n1, const value_type* s)
    { return replace(pos, n1, s, traits_type::length(s)); }
    
    flex_string& replace(size_type pos, size_type n1, size_type n2, 
        value_type c)
    { return replace(pos, n1, flex_string(n2, c)); }
        
    flex_string& replace(iterator i1, iterator i2, const flex_string& str)
    { return replace(i1, i2, str.c_str(), str.length()); }
    
    flex_string& replace(iterator i1, iterator i2, 
        const value_type* s, size_type n)
    { return replace(i1 - begin(), i2 - i1, s, n); }
    
    flex_string& replace(iterator i1, iterator i2, const value_type* s)
    { return replace(i1, i2, s, traits_type::length(s)); }
    
    flex_string& replace(iterator i1, iterator i2,
        size_type n, value_type c)
    { return replace(i1 - begin(), i2 - i1, n, c); }
    
    template<class InputIterator>
    flex_string& replace(iterator i1, iterator i2,
        InputIterator j1, InputIterator j2)
    { return replace(i1, i2, flex_string(j1, j2)); }
       
    size_type copy(value_type* s, size_type n, size_type pos = 0) const
    {
        Enforce(pos <= size(), (std::out_of_range*)0, "");
        n = Min(n, size() - pos);
        
        std::copy(
            begin() + pos,
            begin() + pos + n,
            s);
        return n;
    }
    
    void swap(flex_string& rhs)
    {
        Storage& srhs = rhs;
        this->Storage::swap(srhs);
    }
    
    // 21.3.6 string operations:
    const value_type* c_str() const
    { return Storage::c_str(); }
    
    const value_type* data() const
    { return Storage::data(); }
    
    allocator_type get_allocator() const
    { return Storage::get_allocator(); }
    
    size_type find(const flex_string& str, size_type pos = 0) const
    { return find(str.data(), pos, str.length()); }
    
    size_type find (const value_type* s, size_type pos, size_type n) const
    {
        for (; pos <= size(); ++pos)
        {
            if (traits_type::compare(&*begin() + pos, s, n) == 0)
            {
                return pos;
            }
        }
        return npos;
    }
    
    size_type find (const value_type* s, size_type pos = 0) const
    { return find(s, pos, traits_type::length(s)); }

    size_type find (value_type c, size_type pos = 0) const
    { return find(&c, pos, 1); }
    
    size_type rfind(const flex_string& str, size_type pos = npos) const
    { return rfind(str.c_str(), pos, str.length()); }
    
    size_type rfind(const value_type* s, size_type pos, size_type n) const
    {
        if (n > length()) return npos;
        pos = Min(pos, length() - n);
        if (n == 0) return pos;

        const_iterator i(begin() + pos);
        for (; ; --i)
        {
            if (traits_type::eq(*i, *s) 
                && traits_type::compare(&*i, s, n) == 0)
            {
                return i - begin();
            }
            if (i == begin()) break;
        }
        return npos;
    }

    size_type rfind(const value_type* s, size_type pos = npos) const
    { return rfind(s, pos, traits_type::length(s)); }

    size_type rfind(value_type c, size_type pos = npos) const
    { return rfind(&c, pos, 1); }
    
    size_type find_first_of(const flex_string& str, size_type pos = 0) const
    { return find_first_of(str.c_str(), pos, str.length()); }
    
    size_type find_first_of(const value_type* s, 
        size_type pos, size_type n) const
    {
        if (pos > length() || n == 0) return npos;
        const_iterator i(begin() + pos),
            finish(end());
        for (; i != finish; ++i)
        {
            if (traits_type::find(s, n, *i) != 0)
            {
                return i - begin();
            }
        }
        return npos;
    }
        
    size_type find_first_of(const value_type* s, size_type pos = 0) const
    { return find_first_of(s, pos, traits_type::length(s)); }
    
    size_type find_first_of(value_type c, size_type pos = 0) const
    { return find_first_of(&c, pos, 1); }
    
    size_type find_last_of (const flex_string& str,
        size_type pos = npos) const
    { return find_last_of(str.c_str(), pos, str.length()); }
    
    size_type find_last_of (const value_type* s, size_type pos, 
        size_type n) const
    {
        if (!empty() && n > 0)
        {
            pos = Min(pos, length() - 1);
            const_iterator i(begin() + pos);
            for (;; --i)
            {
                if (traits_type::find(s, n, *i) != 0)
                {
                    return i - begin();
                }
                if (i == begin()) break;
            }
        }
        return npos;
    }

    size_type find_last_of (const value_type* s, 
        size_type pos = npos) const
    { return find_last_of(s, pos, traits_type::length(s)); }

    size_type find_last_of (value_type c, size_type pos = npos) const
    { return find_last_of(&c, pos, 1); }
    
    size_type find_first_not_of(const flex_string& str,
        size_type pos = 0) const
    { return find_first_not_of(str.c_str(), pos, str.length()); }
    
    size_type find_first_not_of(const value_type* s, size_type pos,
        size_type n) const
    {
        if (pos < length())
        {
            const_iterator 
                i(begin() + pos),
                finish(end());
            for (; i != finish; ++i)
            {
                if (traits_type::find(s, n, *i) == 0)
                {
                    return i - begin();
                }
            }
        }
        return npos;
    }
    
    size_type find_first_not_of(const value_type* s, 
        size_type pos = 0) const
    { return find_first_not_of(s, pos, traits_type::length(s)); }
        
    size_type find_first_not_of(value_type c, size_type pos = 0) const
    { return find_first_not_of(&c, pos, 1); }
    
    size_type find_last_not_of (const flex_string& str,
        size_type pos = npos) const
    { return find_last_not_of(str.c_str(), pos, str.length()); }
    
    size_type find_last_not_of (const value_type* s, size_type pos,
        size_type n) const
    {
        if (!empty() && n > 0)
        {
            pos = Min(pos, length() - 1);
            const_iterator i(begin() + pos);
            for (;; --i)
            {
                if (traits_type::find(s, n, *i) == 0)
                {
                    return i - begin();
                }
                if (i == begin()) break;
            }
        }
        return npos;
    }

    size_type find_last_not_of(const value_type* s, 
        size_type pos = npos) const
    { return find_last_not_of(s, pos, traits_type::length(s)); }
    
    size_type find_last_not_of (value_type c, size_type pos = npos) const
    { return find_last_not_of(&c, pos, 1); }
    
    flex_string substr(size_type pos = 0, size_type n = npos) const
    {
        Enforce(pos <= size(), (std::out_of_range*)0, "");
        return flex_string(data() + pos, Min(n, size() - pos));
    }

    std::ptrdiff_t compare(const flex_string& str) const
    { return compare(0, size(), str.data(), str.length()); }
    
    std::ptrdiff_t compare(size_type pos1, size_type n1,
        const flex_string& str) const
    { return compare(pos1, n1, str.data(), str.size()); }
    
    std::ptrdiff_t compare(size_type pos1, size_type n1,
        const value_type* s, size_type n2 = npos) const
    {
        Enforce(pos1 <= size(), (std::out_of_range*)0, "");

        n1 = Min(size() - pos1, n1);
        std::ptrdiff_t result = traits_type::compare(data() + pos1, s, Min(n1, n2));
        return (result != 0) ? result : (n1 - n2);
    }
    
    std::ptrdiff_t compare(size_type pos1, size_type n1,
        const flex_string& str,
        size_type pos2, size_type n2) const
    {
        Enforce(pos2 <= str.size(), (std::out_of_range*)0, "");
        return compare(pos1, n1, str.data() + pos2, Min(n2, str.size() - pos2));
    }

    std::ptrdiff_t compare(const value_type* s) const
    { return compare(0, size(), s, traits_type::length(s)); }
};

// non-member functions
template <typename E, class T, class A, class S>
flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{
    flex_string<E, T, A, S> result;
    result.reserve(lhs.size() + rhs.size());
    result.append(lhs);
    result.append(rhs);
    return result;
}

template <typename E, class T, class A, class S>
flex_string<E, T, A, S> operator+(
    const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{
    typedef typename flex_string<E, T, A, S>::traits_type flex_traits_type;

    flex_string<E, T, A, S> result;
    const typename A::size_type len = flex_traits_type::length(lhs);
    result.reserve(len + rhs.size());
    result.append(lhs, len);
    result.append(rhs);
    return result;
}

template <typename E, class T, class A, class S>
flex_string<E, T, A, S> operator+(
    typename flex_string<E, T, A, S>::value_type lhs, 
    const flex_string<E, T, A, S>& rhs)
{
    flex_string<E, T, A, S> result;
    result.reserve(1 + rhs.size());
    result.append(lhs);
    result.append(rhs);
    return result;
}

template <typename E, class T, class A, class S>
flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{
    typedef typename flex_string<E, T, A, S>::traits_type flex_traits_type;
    
    flex_string<E, T, A, S> result;
    const typename A::size_type len = flex_traits_type::length(rhs);
    result.reserve(lhs.size() + len);
    result.append(lhs);
    result.append(rhs, len);
    return result;
}

template <typename E, class T, class A, class S>
flex_string<E, T, A, S> operator+(const flex_string<E, T, A, S>& lhs, 
    typename flex_string<E, T, A, S>::value_type rhs)
{
    flex_string<E, T, A, S> result;
    result.reserve(lhs.size() + 1);
    result.append(lhs);
    result.append(rhs);
    return result;
}

template <typename E, class T, class A, class S>
bool operator==(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return lhs.compare(rhs) == 0; }

template <typename E, class T, class A, class S>
bool operator==(const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return rhs == lhs; }

template <typename E, class T, class A, class S>
bool operator==(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{ return lhs.compare(rhs) == 0; }

template <typename E, class T, class A, class S>
bool operator!=(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return !(lhs == rhs); }

template <typename E, class T, class A, class S>
bool operator!=(const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return !(lhs == rhs); }

template <typename E, class T, class A, class S>
bool operator!=(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{ return !(lhs == rhs); }

template <typename E, class T, class A, class S>
bool operator<(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return lhs.compare(rhs) < 0; }

template <typename E, class T, class A, class S>
bool operator<(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{ return lhs.compare(rhs) < 0; }

template <typename E, class T, class A, class S>
bool operator<(const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return rhs.compare(lhs) > 0; }

template <typename E, class T, class A, class S>
bool operator>(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return rhs < lhs; }

template <typename E, class T, class A, class S>
bool operator>(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{ return rhs < lhs; }

template <typename E, class T, class A, class S>
bool operator>(const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return rhs < lhs; }

template <typename E, class T, class A, class S>
bool operator<=(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return !(rhs < lhs); }

template <typename E, class T, class A, class S>
bool operator<=(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{ return !(rhs < lhs); }

template <typename E, class T, class A, class S>
bool operator<=(const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return !(rhs < lhs); }

template <typename E, class T, class A, class S>
bool operator>=(const flex_string<E, T, A, S>& lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return !(lhs < rhs); }

template <typename E, class T, class A, class S>
bool operator>=(const flex_string<E, T, A, S>& lhs, 
    const typename flex_string<E, T, A, S>::value_type* rhs)
{ return !(lhs < rhs); }

template <typename E, class T, class A, class S>
bool operator>=(const typename flex_string<E, T, A, S>::value_type* lhs, 
    const flex_string<E, T, A, S>& rhs)
{ return !(lhs < rhs); }

// subclause 21.3.7.8:
//void swap(flex_string<E, T, A, S>& lhs, flex_string<E, T, A, S>& rhs);    // to do

template <typename E, class T, class A, class S>
std::basic_istream<typename flex_string<E, T, A, S>::value_type, 
    typename flex_string<E, T, A, S>::traits_type>&
operator>>(
    std::basic_istream<typename flex_string<E, T, A, S>::value_type, 
        typename flex_string<E, T, A, S>::traits_type>& is,
    flex_string<E, T, A, S>& str);

template <typename E, class T, class A, class S>
std::basic_ostream<typename flex_string<E, T, A, S>::value_type,
    typename flex_string<E, T, A, S>::traits_type>&
operator<<(
    std::basic_ostream<typename flex_string<E, T, A, S>::value_type, 
        typename flex_string<E, T, A, S>::traits_type>& os,
    const flex_string<E, T, A, S>& str)
{ return os << str.c_str(); }

template <typename E, class T, class A, class S>
std::basic_istream<typename flex_string<E, T, A, S>::value_type,
    typename flex_string<E, T, A, S>::traits_type>&
getline(
    std::basic_istream<typename flex_string<E, T, A, S>::value_type, 
        typename flex_string<E, T, A, S>::traits_type>& is,
    flex_string<E, T, A, S>& str,
    typename flex_string<E, T, A, S>::value_type delim);

template <typename E, class T, class A, class S>
std::basic_istream<typename flex_string<E, T, A, S>::value_type, 
    typename flex_string<E, T, A, S>::traits_type>&
getline(
    std::basic_istream<typename flex_string<E, T, A, S>::value_type, 
        typename flex_string<E, T, A, S>::traits_type>& is,
    flex_string<E, T, A, S>& str);

template <typename E, class T, class A, class S>
const typename flex_string<E, T, A, S>::size_type
flex_string<E, T, A, S>::npos = (typename flex_string<E, T, A, S>::size_type)(-1);

}   // namespace util
}   // namespace wave

#endif // FLEX_STRING_INC_