// 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_