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