00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044 #ifndef _ROPE
00045 #define _ROPE 1
00046
00047 #include <algorithm>
00048 #include <iosfwd>
00049 #include <bits/stl_construct.h>
00050 #include <bits/stl_uninitialized.h>
00051 #include <bits/stl_function.h>
00052 #include <bits/stl_numeric.h>
00053 #include <bits/allocator.h>
00054 #include <bits/gthr.h>
00055 #include <tr1/functional>
00056
00057 # ifdef __GC
00058 # define __GC_CONST const
00059 # else
00060 # define __GC_CONST // constant except for deallocation
00061 # endif
00062
00063 #include <ext/memory>
00064
00065 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00066 {
00067 namespace __detail
00068 {
00069 enum { _S_max_rope_depth = 45 };
00070 enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
00071 }
00072
00073 using std::size_t;
00074 using std::ptrdiff_t;
00075 using std::allocator;
00076 using std::_Destroy;
00077
00078 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00079
00080
00081 template<typename _ForwardIterator, typename _Allocator>
00082 void
00083 _Destroy_const(_ForwardIterator __first,
00084 _ForwardIterator __last, _Allocator __alloc)
00085 {
00086 for (; __first != __last; ++__first)
00087 __alloc.destroy(&*__first);
00088 }
00089
00090 template<typename _ForwardIterator, typename _Tp>
00091 inline void
00092 _Destroy_const(_ForwardIterator __first,
00093 _ForwardIterator __last, allocator<_Tp>)
00094 { _Destroy(__first, __last); }
00095
00096
00097
00098
00099
00100
00101 template <class _CharT>
00102 inline _CharT
00103 _S_eos(_CharT*)
00104 { return _CharT(); }
00105
00106
00107
00108 template <class _CharT>
00109 inline bool
00110 _S_is_basic_char_type(_CharT*)
00111 { return false; }
00112
00113 template <class _CharT>
00114 inline bool
00115 _S_is_one_byte_char_type(_CharT*)
00116 { return false; }
00117
00118 inline bool
00119 _S_is_basic_char_type(char*)
00120 { return true; }
00121
00122 inline bool
00123 _S_is_one_byte_char_type(char*)
00124 { return true; }
00125
00126 inline bool
00127 _S_is_basic_char_type(wchar_t*)
00128 { return true; }
00129
00130
00131
00132 template <class _CharT>
00133 inline void
00134 _S_cond_store_eos(_CharT&) { }
00135
00136 inline void
00137 _S_cond_store_eos(char& __c)
00138 { __c = 0; }
00139
00140 inline void
00141 _S_cond_store_eos(wchar_t& __c)
00142 { __c = 0; }
00143
00144
00145
00146
00147
00148 template <class _CharT>
00149 class char_producer
00150 {
00151 public:
00152 virtual ~char_producer() { };
00153
00154 virtual void
00155 operator()(size_t __start_pos, size_t __len,
00156 _CharT* __buffer) = 0;
00157
00158
00159
00160
00161 };
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177 template<class _Sequence, size_t _Buf_sz = 100>
00178 class sequence_buffer
00179 : public std::iterator<std::output_iterator_tag, void, void, void, void>
00180 {
00181 public:
00182 typedef typename _Sequence::value_type value_type;
00183 protected:
00184 _Sequence* _M_prefix;
00185 value_type _M_buffer[_Buf_sz];
00186 size_t _M_buf_count;
00187 public:
00188
00189 void
00190 flush()
00191 {
00192 _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
00193 _M_buf_count = 0;
00194 }
00195
00196 ~sequence_buffer()
00197 { flush(); }
00198
00199 sequence_buffer()
00200 : _M_prefix(0), _M_buf_count(0) { }
00201
00202 sequence_buffer(const sequence_buffer& __x)
00203 {
00204 _M_prefix = __x._M_prefix;
00205 _M_buf_count = __x._M_buf_count;
00206 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
00207 }
00208
00209 sequence_buffer(sequence_buffer& __x)
00210 {
00211 __x.flush();
00212 _M_prefix = __x._M_prefix;
00213 _M_buf_count = 0;
00214 }
00215
00216 sequence_buffer(_Sequence& __s)
00217 : _M_prefix(&__s), _M_buf_count(0) { }
00218
00219 sequence_buffer&
00220 operator=(sequence_buffer& __x)
00221 {
00222 __x.flush();
00223 _M_prefix = __x._M_prefix;
00224 _M_buf_count = 0;
00225 return *this;
00226 }
00227
00228 sequence_buffer&
00229 operator=(const sequence_buffer& __x)
00230 {
00231 _M_prefix = __x._M_prefix;
00232 _M_buf_count = __x._M_buf_count;
00233 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
00234 return *this;
00235 }
00236
00237 void
00238 push_back(value_type __x)
00239 {
00240 if (_M_buf_count < _Buf_sz)
00241 {
00242 _M_buffer[_M_buf_count] = __x;
00243 ++_M_buf_count;
00244 }
00245 else
00246 {
00247 flush();
00248 _M_buffer[0] = __x;
00249 _M_buf_count = 1;
00250 }
00251 }
00252
00253 void
00254 append(value_type* __s, size_t __len)
00255 {
00256 if (__len + _M_buf_count <= _Buf_sz)
00257 {
00258 size_t __i = _M_buf_count;
00259 for (size_t __j = 0; __j < __len; __i++, __j++)
00260 _M_buffer[__i] = __s[__j];
00261 _M_buf_count += __len;
00262 }
00263 else if (0 == _M_buf_count)
00264 _M_prefix->append(__s, __s + __len);
00265 else
00266 {
00267 flush();
00268 append(__s, __len);
00269 }
00270 }
00271
00272 sequence_buffer&
00273 write(value_type* __s, size_t __len)
00274 {
00275 append(__s, __len);
00276 return *this;
00277 }
00278
00279 sequence_buffer&
00280 put(value_type __x)
00281 {
00282 push_back(__x);
00283 return *this;
00284 }
00285
00286 sequence_buffer&
00287 operator=(const value_type& __rhs)
00288 {
00289 push_back(__rhs);
00290 return *this;
00291 }
00292
00293 sequence_buffer&
00294 operator*()
00295 { return *this; }
00296
00297 sequence_buffer&
00298 operator++()
00299 { return *this; }
00300
00301 sequence_buffer
00302 operator++(int)
00303 { return *this; }
00304 };
00305
00306
00307 template<class _CharT>
00308 class _Rope_char_consumer
00309 {
00310 public:
00311
00312
00313
00314
00315
00316 virtual ~_Rope_char_consumer() { };
00317
00318 virtual bool
00319 operator()(const _CharT* __buffer, size_t __len) = 0;
00320 };
00321
00322
00323
00324
00325 template<class _CharT, class _Alloc = allocator<_CharT> >
00326 class rope;
00327
00328 template<class _CharT, class _Alloc>
00329 struct _Rope_RopeConcatenation;
00330
00331 template<class _CharT, class _Alloc>
00332 struct _Rope_RopeLeaf;
00333
00334 template<class _CharT, class _Alloc>
00335 struct _Rope_RopeFunction;
00336
00337 template<class _CharT, class _Alloc>
00338 struct _Rope_RopeSubstring;
00339
00340 template<class _CharT, class _Alloc>
00341 class _Rope_iterator;
00342
00343 template<class _CharT, class _Alloc>
00344 class _Rope_const_iterator;
00345
00346 template<class _CharT, class _Alloc>
00347 class _Rope_char_ref_proxy;
00348
00349 template<class _CharT, class _Alloc>
00350 class _Rope_char_ptr_proxy;
00351
00352 template<class _CharT, class _Alloc>
00353 bool
00354 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
00355 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
00356
00357 template<class _CharT, class _Alloc>
00358 _Rope_const_iterator<_CharT, _Alloc>
00359 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00360 ptrdiff_t __n);
00361
00362 template<class _CharT, class _Alloc>
00363 _Rope_const_iterator<_CharT, _Alloc>
00364 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00365 ptrdiff_t __n);
00366
00367 template<class _CharT, class _Alloc>
00368 _Rope_const_iterator<_CharT, _Alloc>
00369 operator+(ptrdiff_t __n,
00370 const _Rope_const_iterator<_CharT, _Alloc>& __x);
00371
00372 template<class _CharT, class _Alloc>
00373 bool
00374 operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00375 const _Rope_const_iterator<_CharT, _Alloc>& __y);
00376
00377 template<class _CharT, class _Alloc>
00378 bool
00379 operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00380 const _Rope_const_iterator<_CharT, _Alloc>& __y);
00381
00382 template<class _CharT, class _Alloc>
00383 ptrdiff_t
00384 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00385 const _Rope_const_iterator<_CharT, _Alloc>& __y);
00386
00387 template<class _CharT, class _Alloc>
00388 _Rope_iterator<_CharT, _Alloc>
00389 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
00390
00391 template<class _CharT, class _Alloc>
00392 _Rope_iterator<_CharT, _Alloc>
00393 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
00394
00395 template<class _CharT, class _Alloc>
00396 _Rope_iterator<_CharT, _Alloc>
00397 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
00398
00399 template<class _CharT, class _Alloc>
00400 bool
00401 operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
00402 const _Rope_iterator<_CharT, _Alloc>& __y);
00403
00404 template<class _CharT, class _Alloc>
00405 bool
00406 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
00407 const _Rope_iterator<_CharT, _Alloc>& __y);
00408
00409 template<class _CharT, class _Alloc>
00410 ptrdiff_t
00411 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
00412 const _Rope_iterator<_CharT, _Alloc>& __y);
00413
00414 template<class _CharT, class _Alloc>
00415 rope<_CharT, _Alloc>
00416 operator+(const rope<_CharT, _Alloc>& __left,
00417 const rope<_CharT, _Alloc>& __right);
00418
00419 template<class _CharT, class _Alloc>
00420 rope<_CharT, _Alloc>
00421 operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
00422
00423 template<class _CharT, class _Alloc>
00424 rope<_CharT, _Alloc>
00425 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
00426
00427
00428
00429
00430
00431
00432 template<class _CharT, class _Alloc>
00433 struct _Rope_Concat_fn
00434 : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
00435 rope<_CharT, _Alloc> >
00436 {
00437 rope<_CharT, _Alloc>
00438 operator()(const rope<_CharT, _Alloc>& __x,
00439 const rope<_CharT, _Alloc>& __y)
00440 { return __x + __y; }
00441 };
00442
00443 template <class _CharT, class _Alloc>
00444 inline rope<_CharT, _Alloc>
00445 identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
00446 { return rope<_CharT, _Alloc>(); }
00447
00448
00449
00450
00451
00452 struct _Refcount_Base
00453 {
00454
00455 typedef size_t _RC_t;
00456
00457
00458 volatile _RC_t _M_ref_count;
00459
00460
00461 __gthread_mutex_t _M_ref_count_lock;
00462
00463 _Refcount_Base(_RC_t __n) : _M_ref_count(__n), _M_ref_count_lock()
00464 {
00465 #ifdef __GTHREAD_MUTEX_INIT
00466 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
00467 _M_ref_count_lock = __tmp;
00468 #elif defined(__GTHREAD_MUTEX_INIT_FUNCTION)
00469 __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
00470 #else
00471 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
00472 #endif
00473 }
00474
00475 void
00476 _M_incr()
00477 {
00478 __gthread_mutex_lock(&_M_ref_count_lock);
00479 ++_M_ref_count;
00480 __gthread_mutex_unlock(&_M_ref_count_lock);
00481 }
00482
00483 _RC_t
00484 _M_decr()
00485 {
00486 __gthread_mutex_lock(&_M_ref_count_lock);
00487 volatile _RC_t __tmp = --_M_ref_count;
00488 __gthread_mutex_unlock(&_M_ref_count_lock);
00489 return __tmp;
00490 }
00491 };
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518 #define __ROPE_DEFINE_ALLOCS(__a) \
00519 __ROPE_DEFINE_ALLOC(_CharT,_Data) \
00520 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
00521 __ROPE_DEFINE_ALLOC(__C,_C) \
00522 typedef _Rope_RopeLeaf<_CharT,__a> __L; \
00523 __ROPE_DEFINE_ALLOC(__L,_L) \
00524 typedef _Rope_RopeFunction<_CharT,__a> __F; \
00525 __ROPE_DEFINE_ALLOC(__F,_F) \
00526 typedef _Rope_RopeSubstring<_CharT,__a> __S; \
00527 __ROPE_DEFINE_ALLOC(__S,_S)
00528
00529
00530
00531
00532
00533
00534
00535
00536 #define __STATIC_IF_SGI_ALLOC
00537
00538 template <class _CharT, class _Alloc>
00539 struct _Rope_rep_base
00540 : public _Alloc
00541 {
00542 typedef _Alloc allocator_type;
00543
00544 allocator_type
00545 get_allocator() const
00546 { return *static_cast<const _Alloc*>(this); }
00547
00548 allocator_type&
00549 _M_get_allocator()
00550 { return *static_cast<_Alloc*>(this); }
00551
00552 const allocator_type&
00553 _M_get_allocator() const
00554 { return *static_cast<const _Alloc*>(this); }
00555
00556 _Rope_rep_base(size_t __size, const allocator_type&)
00557 : _M_size(__size) { }
00558
00559 size_t _M_size;
00560
00561 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
00562 typedef typename \
00563 _Alloc::template rebind<_Tp>::other __name##Alloc; \
00564 static _Tp* __name##_allocate(size_t __n) \
00565 { return __name##Alloc().allocate(__n); } \
00566 static void __name##_deallocate(_Tp *__p, size_t __n) \
00567 { __name##Alloc().deallocate(__p, __n); }
00568 __ROPE_DEFINE_ALLOCS(_Alloc)
00569 # undef __ROPE_DEFINE_ALLOC
00570 };
00571
00572 template<class _CharT, class _Alloc>
00573 struct _Rope_RopeRep
00574 : public _Rope_rep_base<_CharT, _Alloc>
00575 # ifndef __GC
00576 , _Refcount_Base
00577 # endif
00578 {
00579 public:
00580 __detail::_Tag _M_tag:8;
00581 bool _M_is_balanced:8;
00582 unsigned char _M_depth;
00583 __GC_CONST _CharT* _M_c_string;
00584 __gthread_mutex_t _M_c_string_lock;
00585
00586
00587
00588
00589
00590
00591 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00592 allocator_type;
00593
00594 using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
00595 using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
00596
00597 _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
00598 const allocator_type& __a)
00599 : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
00600 #ifndef __GC
00601 _Refcount_Base(1),
00602 #endif
00603 _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
00604 #ifdef __GTHREAD_MUTEX_INIT
00605 {
00606
00607 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
00608 _M_c_string_lock = __tmp;
00609 }
00610 #else
00611 { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
00612 #endif
00613 #ifdef __GC
00614 void
00615 _M_incr () { }
00616 #endif
00617 static void
00618 _S_free_string(__GC_CONST _CharT*, size_t __len,
00619 allocator_type& __a);
00620 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
00621
00622
00623
00624
00625
00626
00627 #ifndef __GC
00628 void _M_free_c_string();
00629 void _M_free_tree();
00630
00631 void
00632 _M_unref_nonnil()
00633 {
00634 if (0 == _M_decr())
00635 _M_free_tree();
00636 }
00637
00638 void
00639 _M_ref_nonnil()
00640 { _M_incr(); }
00641
00642 static void
00643 _S_unref(_Rope_RopeRep* __t)
00644 {
00645 if (0 != __t)
00646 __t->_M_unref_nonnil();
00647 }
00648
00649 static void
00650 _S_ref(_Rope_RopeRep* __t)
00651 {
00652 if (0 != __t)
00653 __t->_M_incr();
00654 }
00655
00656 static void
00657 _S_free_if_unref(_Rope_RopeRep* __t)
00658 {
00659 if (0 != __t && 0 == __t->_M_ref_count)
00660 __t->_M_free_tree();
00661 }
00662 # else
00663 void _M_unref_nonnil() { }
00664 void _M_ref_nonnil() { }
00665 static void _S_unref(_Rope_RopeRep*) { }
00666 static void _S_ref(_Rope_RopeRep*) { }
00667 static void _S_free_if_unref(_Rope_RopeRep*) { }
00668 # endif
00669 protected:
00670 _Rope_RopeRep&
00671 operator=(const _Rope_RopeRep&);
00672
00673 _Rope_RopeRep(const _Rope_RopeRep&);
00674 };
00675
00676 template<class _CharT, class _Alloc>
00677 struct _Rope_RopeLeaf
00678 : public _Rope_RopeRep<_CharT, _Alloc>
00679 {
00680 public:
00681
00682
00683
00684
00685 enum { _S_alloc_granularity = 8 };
00686
00687 static size_t
00688 _S_rounded_up_size(size_t __n)
00689 {
00690 size_t __size_with_eos;
00691
00692 if (_S_is_basic_char_type((_CharT*)0))
00693 __size_with_eos = __n + 1;
00694 else
00695 __size_with_eos = __n;
00696 #ifdef __GC
00697 return __size_with_eos;
00698 #else
00699
00700 return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
00701 &~ (size_t(_S_alloc_granularity) - 1));
00702 #endif
00703 }
00704 __GC_CONST _CharT* _M_data;
00705
00706
00707
00708
00709 typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
00710 allocator_type;
00711
00712 _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
00713 const allocator_type& __a)
00714 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
00715 __size, __a), _M_data(__d)
00716 {
00717 if (_S_is_basic_char_type((_CharT *)0))
00718 {
00719
00720 this->_M_c_string = __d;
00721 }
00722 }
00723
00724
00725
00726 #ifndef __GC
00727 ~_Rope_RopeLeaf() throw()
00728 {
00729 if (_M_data != this->_M_c_string)
00730 this->_M_free_c_string();
00731
00732 __STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
00733 }
00734 #endif
00735 protected:
00736 _Rope_RopeLeaf&
00737 operator=(const _Rope_RopeLeaf&);
00738
00739 _Rope_RopeLeaf(const _Rope_RopeLeaf&);
00740 };
00741
00742 template<class _CharT, class _Alloc>
00743 struct _Rope_RopeConcatenation
00744 : public _Rope_RopeRep<_CharT, _Alloc>
00745 {
00746 public:
00747 _Rope_RopeRep<_CharT, _Alloc>* _M_left;
00748 _Rope_RopeRep<_CharT, _Alloc>* _M_right;
00749
00750 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00751 allocator_type;
00752
00753 _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
00754 _Rope_RopeRep<_CharT, _Alloc>* __r,
00755 const allocator_type& __a)
00756 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
00757 std::max(__l->_M_depth,
00758 __r->_M_depth) + 1,
00759 false,
00760 __l->_M_size + __r->_M_size, __a),
00761 _M_left(__l), _M_right(__r)
00762 { }
00763 #ifndef __GC
00764 ~_Rope_RopeConcatenation() throw()
00765 {
00766 this->_M_free_c_string();
00767 _M_left->_M_unref_nonnil();
00768 _M_right->_M_unref_nonnil();
00769 }
00770 #endif
00771 protected:
00772 _Rope_RopeConcatenation&
00773 operator=(const _Rope_RopeConcatenation&);
00774
00775 _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
00776 };
00777
00778 template<class _CharT, class _Alloc>
00779 struct _Rope_RopeFunction
00780 : public _Rope_RopeRep<_CharT, _Alloc>
00781 {
00782 public:
00783 char_producer<_CharT>* _M_fn;
00784 #ifndef __GC
00785 bool _M_delete_when_done;
00786
00787
00788
00789 #else
00790
00791
00792
00793
00794
00795 static void
00796 _S_fn_finalization_proc(void * __tree, void *)
00797 { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
00798 #endif
00799 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00800 allocator_type;
00801
00802 _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
00803 bool __d, const allocator_type& __a)
00804 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
00805 , _M_fn(__f)
00806 #ifndef __GC
00807 , _M_delete_when_done(__d)
00808 #endif
00809 {
00810 #ifdef __GC
00811 if (__d)
00812 {
00813 GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
00814 _S_fn_finalization_proc, 0, 0, 0);
00815 }
00816 #endif
00817 }
00818 #ifndef __GC
00819 ~_Rope_RopeFunction() throw()
00820 {
00821 this->_M_free_c_string();
00822 if (_M_delete_when_done)
00823 delete _M_fn;
00824 }
00825 # endif
00826 protected:
00827 _Rope_RopeFunction&
00828 operator=(const _Rope_RopeFunction&);
00829
00830 _Rope_RopeFunction(const _Rope_RopeFunction&);
00831 };
00832
00833
00834
00835
00836
00837
00838
00839 template<class _CharT, class _Alloc>
00840 struct _Rope_RopeSubstring
00841 : public _Rope_RopeFunction<_CharT, _Alloc>,
00842 public char_producer<_CharT>
00843 {
00844 public:
00845
00846 _Rope_RopeRep<_CharT,_Alloc>* _M_base;
00847 size_t _M_start;
00848
00849 virtual void
00850 operator()(size_t __start_pos, size_t __req_len,
00851 _CharT* __buffer)
00852 {
00853 switch(_M_base->_M_tag)
00854 {
00855 case __detail::_S_function:
00856 case __detail::_S_substringfn:
00857 {
00858 char_producer<_CharT>* __fn =
00859 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
00860 (*__fn)(__start_pos + _M_start, __req_len, __buffer);
00861 }
00862 break;
00863 case __detail::_S_leaf:
00864 {
00865 __GC_CONST _CharT* __s =
00866 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
00867 uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
00868 __buffer);
00869 }
00870 break;
00871 default:
00872 break;
00873 }
00874 }
00875
00876 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00877 allocator_type;
00878
00879 _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
00880 size_t __l, const allocator_type& __a)
00881 : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
00882 char_producer<_CharT>(), _M_base(__b), _M_start(__s)
00883 {
00884 #ifndef __GC
00885 _M_base->_M_ref_nonnil();
00886 #endif
00887 this->_M_tag = __detail::_S_substringfn;
00888 }
00889 virtual ~_Rope_RopeSubstring() throw()
00890 {
00891 #ifndef __GC
00892 _M_base->_M_unref_nonnil();
00893
00894 #endif
00895 }
00896 };
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906
00907 #ifndef __GC
00908 template<class _CharT, class _Alloc>
00909 struct _Rope_self_destruct_ptr
00910 {
00911 _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
00912
00913 ~_Rope_self_destruct_ptr()
00914 { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
00915 #ifdef __EXCEPTIONS
00916 _Rope_self_destruct_ptr() : _M_ptr(0) { };
00917 #else
00918 _Rope_self_destruct_ptr() { };
00919 #endif
00920 _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
00921 : _M_ptr(__p) { }
00922
00923 _Rope_RopeRep<_CharT, _Alloc>&
00924 operator*()
00925 { return *_M_ptr; }
00926
00927 _Rope_RopeRep<_CharT, _Alloc>*
00928 operator->()
00929 { return _M_ptr; }
00930
00931 operator _Rope_RopeRep<_CharT, _Alloc>*()
00932 { return _M_ptr; }
00933
00934 _Rope_self_destruct_ptr&
00935 operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
00936 { _M_ptr = __x; return *this; }
00937 };
00938 #endif
00939
00940
00941
00942
00943
00944
00945 template<class _CharT, class _Alloc>
00946 class _Rope_char_ref_proxy
00947 {
00948 friend class rope<_CharT, _Alloc>;
00949 friend class _Rope_iterator<_CharT, _Alloc>;
00950 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
00951 #ifdef __GC
00952 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
00953 #else
00954 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
00955 #endif
00956 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
00957 typedef rope<_CharT, _Alloc> _My_rope;
00958 size_t _M_pos;
00959 _CharT _M_current;
00960 bool _M_current_valid;
00961 _My_rope* _M_root;
00962 public:
00963 _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
00964 : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
00965
00966 _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
00967 : _M_pos(__x._M_pos), _M_current(__x._M_current),
00968 _M_current_valid(false), _M_root(__x._M_root) { }
00969
00970
00971
00972
00973
00974 _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
00975 : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
00976
00977 inline operator _CharT () const;
00978
00979 _Rope_char_ref_proxy&
00980 operator=(_CharT __c);
00981
00982 _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
00983
00984 _Rope_char_ref_proxy&
00985 operator=(const _Rope_char_ref_proxy& __c)
00986 { return operator=((_CharT)__c); }
00987 };
00988
00989 template<class _CharT, class __Alloc>
00990 inline void
00991 swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
00992 _Rope_char_ref_proxy <_CharT, __Alloc > __b)
00993 {
00994 _CharT __tmp = __a;
00995 __a = __b;
00996 __b = __tmp;
00997 }
00998
00999 template<class _CharT, class _Alloc>
01000 class _Rope_char_ptr_proxy
01001 {
01002
01003 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
01004 size_t _M_pos;
01005 rope<_CharT,_Alloc>* _M_root;
01006 public:
01007 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
01008 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
01009
01010 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
01011 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
01012
01013 _Rope_char_ptr_proxy() { }
01014
01015 _Rope_char_ptr_proxy(_CharT* __x)
01016 : _M_root(0), _M_pos(0) { }
01017
01018 _Rope_char_ptr_proxy&
01019 operator=(const _Rope_char_ptr_proxy& __x)
01020 {
01021 _M_pos = __x._M_pos;
01022 _M_root = __x._M_root;
01023 return *this;
01024 }
01025
01026 template<class _CharT2, class _Alloc2>
01027 friend bool
01028 operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
01029 const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
01030
01031 _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
01032 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
01033 };
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044 template<class _CharT, class _Alloc>
01045 class _Rope_iterator_base
01046 : public std::iterator<std::random_access_iterator_tag, _CharT>
01047 {
01048 friend class rope<_CharT, _Alloc>;
01049 public:
01050 typedef _Alloc _allocator_type;
01051 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01052
01053 protected:
01054 enum { _S_path_cache_len = 4 };
01055 enum { _S_iterator_buf_len = 15 };
01056 size_t _M_current_pos;
01057 _RopeRep* _M_root;
01058 size_t _M_leaf_pos;
01059 __GC_CONST _CharT* _M_buf_start;
01060
01061
01062 __GC_CONST _CharT* _M_buf_ptr;
01063
01064
01065 __GC_CONST _CharT* _M_buf_end;
01066
01067
01068
01069
01070
01071 const _RopeRep* _M_path_end[_S_path_cache_len];
01072 int _M_leaf_index;
01073
01074
01075 unsigned char _M_path_directions;
01076
01077
01078
01079
01080 _CharT _M_tmp_buf[_S_iterator_buf_len];
01081
01082
01083
01084
01085
01086
01087
01088 static void _S_setbuf(_Rope_iterator_base& __x);
01089
01090
01091 static void _S_setcache(_Rope_iterator_base& __x);
01092
01093
01094 static void _S_setcache_for_incr(_Rope_iterator_base& __x);
01095
01096
01097 _Rope_iterator_base() { }
01098
01099 _Rope_iterator_base(_RopeRep* __root, size_t __pos)
01100 : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
01101
01102 void _M_incr(size_t __n);
01103 void _M_decr(size_t __n);
01104 public:
01105 size_t
01106 index() const
01107 { return _M_current_pos; }
01108
01109 _Rope_iterator_base(const _Rope_iterator_base& __x)
01110 {
01111 if (0 != __x._M_buf_ptr)
01112 *this = __x;
01113 else
01114 {
01115 _M_current_pos = __x._M_current_pos;
01116 _M_root = __x._M_root;
01117 _M_buf_ptr = 0;
01118 }
01119 }
01120 };
01121
01122 template<class _CharT, class _Alloc>
01123 class _Rope_iterator;
01124
01125 template<class _CharT, class _Alloc>
01126 class _Rope_const_iterator
01127 : public _Rope_iterator_base<_CharT, _Alloc>
01128 {
01129 friend class rope<_CharT, _Alloc>;
01130 protected:
01131 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01132
01133 _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
01134 : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
01135 __pos)
01136
01137 { }
01138 public:
01139 typedef _CharT reference;
01140
01141
01142 typedef const _CharT* pointer;
01143
01144 public:
01145 _Rope_const_iterator() { };
01146
01147 _Rope_const_iterator(const _Rope_const_iterator& __x)
01148 : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
01149
01150 _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
01151
01152 _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
01153 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
01154
01155 _Rope_const_iterator&
01156 operator=(const _Rope_const_iterator& __x)
01157 {
01158 if (0 != __x._M_buf_ptr)
01159 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
01160 else
01161 {
01162 this->_M_current_pos = __x._M_current_pos;
01163 this->_M_root = __x._M_root;
01164 this->_M_buf_ptr = 0;
01165 }
01166 return(*this);
01167 }
01168
01169 reference
01170 operator*()
01171 {
01172 if (0 == this->_M_buf_ptr)
01173 _S_setcache(*this);
01174 return *this->_M_buf_ptr;
01175 }
01176
01177
01178
01179 reference
01180 operator*() const
01181 {
01182 return *const_cast<_Rope_const_iterator&>(*this);
01183 }
01184
01185 _Rope_const_iterator&
01186 operator++()
01187 {
01188 __GC_CONST _CharT* __next;
01189 if (0 != this->_M_buf_ptr
01190 && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
01191 {
01192 this->_M_buf_ptr = __next;
01193 ++this->_M_current_pos;
01194 }
01195 else
01196 this->_M_incr(1);
01197 return *this;
01198 }
01199
01200 _Rope_const_iterator&
01201 operator+=(ptrdiff_t __n)
01202 {
01203 if (__n >= 0)
01204 this->_M_incr(__n);
01205 else
01206 this->_M_decr(-__n);
01207 return *this;
01208 }
01209
01210 _Rope_const_iterator&
01211 operator--()
01212 {
01213 this->_M_decr(1);
01214 return *this;
01215 }
01216
01217 _Rope_const_iterator&
01218 operator-=(ptrdiff_t __n)
01219 {
01220 if (__n >= 0)
01221 this->_M_decr(__n);
01222 else
01223 this->_M_incr(-__n);
01224 return *this;
01225 }
01226
01227 _Rope_const_iterator
01228 operator++(int)
01229 {
01230 size_t __old_pos = this->_M_current_pos;
01231 this->_M_incr(1);
01232 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
01233
01234
01235
01236 }
01237
01238 _Rope_const_iterator
01239 operator--(int)
01240 {
01241 size_t __old_pos = this->_M_current_pos;
01242 this->_M_decr(1);
01243 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
01244 }
01245
01246 template<class _CharT2, class _Alloc2>
01247 friend _Rope_const_iterator<_CharT2, _Alloc2>
01248 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01249 ptrdiff_t __n);
01250
01251 template<class _CharT2, class _Alloc2>
01252 friend _Rope_const_iterator<_CharT2, _Alloc2>
01253 operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01254 ptrdiff_t __n);
01255
01256 template<class _CharT2, class _Alloc2>
01257 friend _Rope_const_iterator<_CharT2, _Alloc2>
01258 operator+(ptrdiff_t __n,
01259 const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
01260
01261 reference
01262 operator[](size_t __n)
01263 { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
01264 this->_M_current_pos + __n); }
01265
01266 template<class _CharT2, class _Alloc2>
01267 friend bool
01268 operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01269 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01270
01271 template<class _CharT2, class _Alloc2>
01272 friend bool
01273 operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01274 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01275
01276 template<class _CharT2, class _Alloc2>
01277 friend ptrdiff_t
01278 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01279 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01280 };
01281
01282 template<class _CharT, class _Alloc>
01283 class _Rope_iterator
01284 : public _Rope_iterator_base<_CharT, _Alloc>
01285 {
01286 friend class rope<_CharT, _Alloc>;
01287 protected:
01288 typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
01289 rope<_CharT, _Alloc>* _M_root_rope;
01290
01291
01292
01293
01294
01295
01296
01297 _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
01298 : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
01299 _M_root_rope(__r)
01300 { _RopeRep::_S_ref(this->_M_root);
01301 if (!(__r -> empty()))
01302 _S_setcache(*this);
01303 }
01304
01305 void _M_check();
01306 public:
01307 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
01308 typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
01309
01310 rope<_CharT, _Alloc>&
01311 container()
01312 { return *_M_root_rope; }
01313
01314 _Rope_iterator()
01315 {
01316 this->_M_root = 0;
01317 };
01318
01319 _Rope_iterator(const _Rope_iterator& __x)
01320 : _Rope_iterator_base<_CharT, _Alloc>(__x)
01321 {
01322 _M_root_rope = __x._M_root_rope;
01323 _RopeRep::_S_ref(this->_M_root);
01324 }
01325
01326 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
01327
01328 ~_Rope_iterator()
01329 { _RopeRep::_S_unref(this->_M_root); }
01330
01331 _Rope_iterator&
01332 operator=(const _Rope_iterator& __x)
01333 {
01334 _RopeRep* __old = this->_M_root;
01335
01336 _RopeRep::_S_ref(__x._M_root);
01337 if (0 != __x._M_buf_ptr)
01338 {
01339 _M_root_rope = __x._M_root_rope;
01340 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
01341 }
01342 else
01343 {
01344 this->_M_current_pos = __x._M_current_pos;
01345 this->_M_root = __x._M_root;
01346 _M_root_rope = __x._M_root_rope;
01347 this->_M_buf_ptr = 0;
01348 }
01349 _RopeRep::_S_unref(__old);
01350 return(*this);
01351 }
01352
01353 reference
01354 operator*()
01355 {
01356 _M_check();
01357 if (0 == this->_M_buf_ptr)
01358 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01359 this->_M_current_pos);
01360 else
01361 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01362 this->_M_current_pos,
01363 *this->_M_buf_ptr);
01364 }
01365
01366
01367 reference
01368 operator*() const
01369 {
01370 return *const_cast<_Rope_iterator&>(*this);
01371 }
01372
01373 _Rope_iterator&
01374 operator++()
01375 {
01376 this->_M_incr(1);
01377 return *this;
01378 }
01379
01380 _Rope_iterator&
01381 operator+=(ptrdiff_t __n)
01382 {
01383 if (__n >= 0)
01384 this->_M_incr(__n);
01385 else
01386 this->_M_decr(-__n);
01387 return *this;
01388 }
01389
01390 _Rope_iterator&
01391 operator--()
01392 {
01393 this->_M_decr(1);
01394 return *this;
01395 }
01396
01397 _Rope_iterator&
01398 operator-=(ptrdiff_t __n)
01399 {
01400 if (__n >= 0)
01401 this->_M_decr(__n);
01402 else
01403 this->_M_incr(-__n);
01404 return *this;
01405 }
01406
01407 _Rope_iterator
01408 operator++(int)
01409 {
01410 size_t __old_pos = this->_M_current_pos;
01411 this->_M_incr(1);
01412 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
01413 }
01414
01415 _Rope_iterator
01416 operator--(int)
01417 {
01418 size_t __old_pos = this->_M_current_pos;
01419 this->_M_decr(1);
01420 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
01421 }
01422
01423 reference
01424 operator[](ptrdiff_t __n)
01425 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01426 this->_M_current_pos
01427 + __n); }
01428
01429 template<class _CharT2, class _Alloc2>
01430 friend bool
01431 operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01432 const _Rope_iterator<_CharT2, _Alloc2>& __y);
01433
01434 template<class _CharT2, class _Alloc2>
01435 friend bool
01436 operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01437 const _Rope_iterator<_CharT2, _Alloc2>& __y);
01438
01439 template<class _CharT2, class _Alloc2>
01440 friend ptrdiff_t
01441 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01442 const _Rope_iterator<_CharT2, _Alloc2>& __y);
01443
01444 template<class _CharT2, class _Alloc2>
01445 friend _Rope_iterator<_CharT2, _Alloc2>
01446 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
01447
01448 template<class _CharT2, class _Alloc2>
01449 friend _Rope_iterator<_CharT2, _Alloc2>
01450 operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
01451
01452 template<class _CharT2, class _Alloc2>
01453 friend _Rope_iterator<_CharT2, _Alloc2>
01454 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
01455 };
01456
01457
01458 template <class _CharT, class _Alloc>
01459 struct _Rope_base
01460 : public _Alloc
01461 {
01462 typedef _Alloc allocator_type;
01463
01464 allocator_type
01465 get_allocator() const
01466 { return *static_cast<const _Alloc*>(this); }
01467
01468 allocator_type&
01469 _M_get_allocator()
01470 { return *static_cast<_Alloc*>(this); }
01471
01472 const allocator_type&
01473 _M_get_allocator() const
01474 { return *static_cast<const _Alloc*>(this); }
01475
01476 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01477
01478
01479 _Rope_base(_RopeRep* __t, const allocator_type&)
01480 : _M_tree_ptr(__t) { }
01481
01482 _Rope_base(const allocator_type&) { }
01483
01484
01485 _RopeRep *_M_tree_ptr;
01486
01487 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
01488 typedef typename \
01489 _Alloc::template rebind<_Tp>::other __name##Alloc; \
01490 static _Tp* __name##_allocate(size_t __n) \
01491 { return __name##Alloc().allocate(__n); } \
01492 static void __name##_deallocate(_Tp *__p, size_t __n) \
01493 { __name##Alloc().deallocate(__p, __n); }
01494 __ROPE_DEFINE_ALLOCS(_Alloc)
01495 #undef __ROPE_DEFINE_ALLOC
01496
01497 protected:
01498 _Rope_base&
01499 operator=(const _Rope_base&);
01500
01501 _Rope_base(const _Rope_base&);
01502 };
01503
01504
01505
01506
01507
01508
01509 template <class _CharT, class _Alloc>
01510 class rope : public _Rope_base<_CharT, _Alloc>
01511 {
01512 public:
01513 typedef _CharT value_type;
01514 typedef ptrdiff_t difference_type;
01515 typedef size_t size_type;
01516 typedef _CharT const_reference;
01517 typedef const _CharT* const_pointer;
01518 typedef _Rope_iterator<_CharT, _Alloc> iterator;
01519 typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
01520 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
01521 typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
01522
01523 friend class _Rope_iterator<_CharT, _Alloc>;
01524 friend class _Rope_const_iterator<_CharT, _Alloc>;
01525 friend struct _Rope_RopeRep<_CharT, _Alloc>;
01526 friend class _Rope_iterator_base<_CharT, _Alloc>;
01527 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
01528 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
01529 friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
01530
01531 protected:
01532 typedef _Rope_base<_CharT, _Alloc> _Base;
01533 typedef typename _Base::allocator_type allocator_type;
01534 using _Base::_M_tree_ptr;
01535 using _Base::get_allocator;
01536 using _Base::_M_get_allocator;
01537 typedef __GC_CONST _CharT* _Cstrptr;
01538
01539 static _CharT _S_empty_c_str[1];
01540
01541 static bool
01542 _S_is0(_CharT __c)
01543 { return __c == _S_eos((_CharT*)0); }
01544
01545 enum { _S_copy_max = 23 };
01546
01547
01548
01549 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01550 typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
01551 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
01552 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
01553 typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
01554
01555
01556 static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
01557
01558 #ifndef __GC
01559
01560
01561
01562
01563
01564
01565 static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
01566 #endif
01567
01568 static bool
01569 _S_apply_to_pieces(
01570 _Rope_char_consumer<_CharT>& __c,
01571 const _RopeRep* __r,
01572 size_t __begin, size_t __end);
01573
01574
01575 #ifndef __GC
01576 static void
01577 _S_unref(_RopeRep* __t)
01578 { _RopeRep::_S_unref(__t); }
01579
01580 static void
01581 _S_ref(_RopeRep* __t)
01582 { _RopeRep::_S_ref(__t); }
01583
01584 #else
01585 static void _S_unref(_RopeRep*) { }
01586 static void _S_ref(_RopeRep*) { }
01587 #endif
01588
01589 #ifdef __GC
01590 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
01591 #else
01592 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
01593 #endif
01594
01595
01596 static _RopeRep* _S_substring(_RopeRep* __base,
01597 size_t __start, size_t __endp1);
01598
01599 static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
01600 const _CharT* __iter, size_t __slen);
01601
01602
01603
01604 static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
01605 const _CharT* __iter,
01606 size_t __slen)
01607
01608
01609
01610 #ifdef __GC
01611
01612 { return _S_concat_char_iter(__r, __iter, __slen); }
01613 #else
01614 ;
01615 #endif
01616
01617 static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
01618
01619
01620
01621 public:
01622 void
01623 apply_to_pieces(size_t __begin, size_t __end,
01624 _Rope_char_consumer<_CharT>& __c) const
01625 { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
01626
01627 protected:
01628
01629 static size_t
01630 _S_rounded_up_size(size_t __n)
01631 { return _RopeLeaf::_S_rounded_up_size(__n); }
01632
01633 static size_t
01634 _S_allocated_capacity(size_t __n)
01635 {
01636 if (_S_is_basic_char_type((_CharT*)0))
01637 return _S_rounded_up_size(__n) - 1;
01638 else
01639 return _S_rounded_up_size(__n);
01640
01641 }
01642
01643
01644
01645 static _RopeLeaf*
01646 _S_new_RopeLeaf(__GC_CONST _CharT *__s,
01647 size_t __size, allocator_type& __a)
01648 {
01649 _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
01650 return new(__space) _RopeLeaf(__s, __size, __a);
01651 }
01652
01653 static _RopeConcatenation*
01654 _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
01655 allocator_type& __a)
01656 {
01657 _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
01658 return new(__space) _RopeConcatenation(__left, __right, __a);
01659 }
01660
01661 static _RopeFunction*
01662 _S_new_RopeFunction(char_producer<_CharT>* __f,
01663 size_t __size, bool __d, allocator_type& __a)
01664 {
01665 _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
01666 return new(__space) _RopeFunction(__f, __size, __d, __a);
01667 }
01668
01669 static _RopeSubstring*
01670 _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
01671 size_t __l, allocator_type& __a)
01672 {
01673 _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
01674 return new(__space) _RopeSubstring(__b, __s, __l, __a);
01675 }
01676
01677 static _RopeLeaf*
01678 _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
01679 size_t __size, allocator_type& __a)
01680 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
01681 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
01682 {
01683 if (0 == __size)
01684 return 0;
01685 _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
01686
01687 __uninitialized_copy_n_a(__s, __size, __buf, __a);
01688 _S_cond_store_eos(__buf[__size]);
01689 __try
01690 { return _S_new_RopeLeaf(__buf, __size, __a); }
01691 __catch(...)
01692 {
01693 _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
01694 __throw_exception_again;
01695 }
01696 }
01697
01698
01699
01700
01701
01702
01703
01704 static _RopeRep*
01705 _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
01706
01707
01708 static _RopeLeaf*
01709 _S_leaf_concat_char_iter(_RopeLeaf* __r,
01710 const _CharT* __iter, size_t __slen);
01711
01712
01713
01714 #ifndef __GC
01715 static _RopeLeaf*
01716 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
01717 const _CharT* __iter, size_t __slen);
01718
01719 #endif
01720
01721 private:
01722
01723 static size_t _S_char_ptr_len(const _CharT* __s);
01724
01725
01726 rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
01727 : _Base(__t, __a) { }
01728
01729
01730
01731
01732
01733 static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
01734
01735
01736
01737 static _CharT* _S_flatten(_RopeRep* __r,
01738 size_t __start, size_t __len,
01739 _CharT* __buffer);
01740
01741 static const unsigned long
01742 _S_min_len[__detail::_S_max_rope_depth + 1];
01743
01744 static bool
01745 _S_is_balanced(_RopeRep* __r)
01746 { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
01747
01748 static bool
01749 _S_is_almost_balanced(_RopeRep* __r)
01750 { return (__r->_M_depth == 0
01751 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
01752
01753 static bool
01754 _S_is_roughly_balanced(_RopeRep* __r)
01755 { return (__r->_M_depth <= 1
01756 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
01757
01758
01759 static _RopeRep*
01760 _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
01761 {
01762 _RopeRep* __result = _S_concat(__left, __right);
01763 if (_S_is_balanced(__result))
01764 __result->_M_is_balanced = true;
01765 return __result;
01766 }
01767
01768
01769
01770
01771
01772
01773 static _RopeRep* _S_balance(_RopeRep* __r);
01774
01775
01776
01777 static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
01778
01779
01780 static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
01781
01782
01783 static void _S_dump(_RopeRep* __r, int __indent = 0);
01784
01785
01786 static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
01787
01788 public:
01789 bool
01790 empty() const
01791 { return 0 == this->_M_tree_ptr; }
01792
01793
01794
01795
01796 int
01797 compare(const rope& __y) const
01798 { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
01799
01800 rope(const _CharT* __s, const allocator_type& __a = allocator_type())
01801 : _Base(__a)
01802 {
01803 this->_M_tree_ptr =
01804 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
01805 _M_get_allocator());
01806 }
01807
01808 rope(const _CharT* __s, size_t __len,
01809 const allocator_type& __a = allocator_type())
01810 : _Base(__a)
01811 {
01812 this->_M_tree_ptr =
01813 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
01814 }
01815
01816
01817
01818
01819 rope(const _CharT* __s, const _CharT* __e,
01820 const allocator_type& __a = allocator_type())
01821 : _Base(__a)
01822 {
01823 this->_M_tree_ptr =
01824 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
01825 }
01826
01827 rope(const const_iterator& __s, const const_iterator& __e,
01828 const allocator_type& __a = allocator_type())
01829 : _Base(_S_substring(__s._M_root, __s._M_current_pos,
01830 __e._M_current_pos), __a)
01831 { }
01832
01833 rope(const iterator& __s, const iterator& __e,
01834 const allocator_type& __a = allocator_type())
01835 : _Base(_S_substring(__s._M_root, __s._M_current_pos,
01836 __e._M_current_pos), __a)
01837 { }
01838
01839 rope(_CharT __c, const allocator_type& __a = allocator_type())
01840 : _Base(__a)
01841 {
01842 _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
01843
01844 _M_get_allocator().construct(__buf, __c);
01845 __try
01846 {
01847 this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
01848 _M_get_allocator());
01849 }
01850 __catch(...)
01851 {
01852 _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
01853 __throw_exception_again;
01854 }
01855 }
01856
01857 rope(size_t __n, _CharT __c,
01858 const allocator_type& __a = allocator_type());
01859
01860 rope(const allocator_type& __a = allocator_type())
01861 : _Base(0, __a) { }
01862
01863
01864 rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
01865 const allocator_type& __a = allocator_type())
01866 : _Base(__a)
01867 {
01868 this->_M_tree_ptr = (0 == __len) ?
01869 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
01870 }
01871
01872 rope(const rope& __x, const allocator_type& __a = allocator_type())
01873 : _Base(__x._M_tree_ptr, __a)
01874 { _S_ref(this->_M_tree_ptr); }
01875
01876 ~rope() throw()
01877 { _S_unref(this->_M_tree_ptr); }
01878
01879 rope&
01880 operator=(const rope& __x)
01881 {
01882 _RopeRep* __old = this->_M_tree_ptr;
01883 this->_M_tree_ptr = __x._M_tree_ptr;
01884 _S_ref(this->_M_tree_ptr);
01885 _S_unref(__old);
01886 return *this;
01887 }
01888
01889 void
01890 clear()
01891 {
01892 _S_unref(this->_M_tree_ptr);
01893 this->_M_tree_ptr = 0;
01894 }
01895
01896 void
01897 push_back(_CharT __x)
01898 {
01899 _RopeRep* __old = this->_M_tree_ptr;
01900 this->_M_tree_ptr
01901 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
01902 _S_unref(__old);
01903 }
01904
01905 void
01906 pop_back()
01907 {
01908 _RopeRep* __old = this->_M_tree_ptr;
01909 this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
01910 0, this->_M_tree_ptr->_M_size - 1);
01911 _S_unref(__old);
01912 }
01913
01914 _CharT
01915 back() const
01916 { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
01917
01918 void
01919 push_front(_CharT __x)
01920 {
01921 _RopeRep* __old = this->_M_tree_ptr;
01922 _RopeRep* __left =
01923 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
01924 __try
01925 {
01926 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
01927 _S_unref(__old);
01928 _S_unref(__left);
01929 }
01930 __catch(...)
01931 {
01932 _S_unref(__left);
01933 __throw_exception_again;
01934 }
01935 }
01936
01937 void
01938 pop_front()
01939 {
01940 _RopeRep* __old = this->_M_tree_ptr;
01941 this->_M_tree_ptr
01942 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
01943 _S_unref(__old);
01944 }
01945
01946 _CharT
01947 front() const
01948 { return _S_fetch(this->_M_tree_ptr, 0); }
01949
01950 void
01951 balance()
01952 {
01953 _RopeRep* __old = this->_M_tree_ptr;
01954 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
01955 _S_unref(__old);
01956 }
01957
01958 void
01959 copy(_CharT* __buffer) const
01960 {
01961 _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
01962 _S_flatten(this->_M_tree_ptr, __buffer);
01963 }
01964
01965
01966
01967
01968
01969
01970 size_type
01971 copy(size_type __pos, size_type __n, _CharT* __buffer) const
01972 {
01973 size_t __size = size();
01974 size_t __len = (__pos + __n > __size? __size - __pos : __n);
01975
01976 _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
01977 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
01978 return __len;
01979 }
01980
01981
01982
01983 void
01984 dump()
01985 { _S_dump(this->_M_tree_ptr); }
01986
01987
01988
01989 const _CharT* c_str() const;
01990
01991
01992
01993 const _CharT* replace_with_c_str();
01994
01995
01996
01997
01998 void
01999 delete_c_str ()
02000 {
02001 if (0 == this->_M_tree_ptr)
02002 return;
02003 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
02004 ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
02005 this->_M_tree_ptr->_M_c_string)
02006 {
02007
02008 return;
02009 }
02010 #ifndef __GC
02011 this->_M_tree_ptr->_M_free_c_string();
02012 #endif
02013 this->_M_tree_ptr->_M_c_string = 0;
02014 }
02015
02016 _CharT
02017 operator[] (size_type __pos) const
02018 { return _S_fetch(this->_M_tree_ptr, __pos); }
02019
02020 _CharT
02021 at(size_type __pos) const
02022 {
02023
02024 return (*this)[__pos];
02025 }
02026
02027 const_iterator
02028 begin() const
02029 { return(const_iterator(this->_M_tree_ptr, 0)); }
02030
02031
02032 const_iterator
02033 const_begin() const
02034 { return(const_iterator(this->_M_tree_ptr, 0)); }
02035
02036 const_iterator
02037 end() const
02038 { return(const_iterator(this->_M_tree_ptr, size())); }
02039
02040 const_iterator
02041 const_end() const
02042 { return(const_iterator(this->_M_tree_ptr, size())); }
02043
02044 size_type
02045 size() const
02046 { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
02047
02048 size_type
02049 length() const
02050 { return size(); }
02051
02052 size_type
02053 max_size() const
02054 {
02055 return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
02056
02057
02058
02059 }
02060
02061 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
02062
02063 const_reverse_iterator
02064 rbegin() const
02065 { return const_reverse_iterator(end()); }
02066
02067 const_reverse_iterator
02068 const_rbegin() const
02069 { return const_reverse_iterator(end()); }
02070
02071 const_reverse_iterator
02072 rend() const
02073 { return const_reverse_iterator(begin()); }
02074
02075 const_reverse_iterator
02076 const_rend() const
02077 { return const_reverse_iterator(begin()); }
02078
02079 template<class _CharT2, class _Alloc2>
02080 friend rope<_CharT2, _Alloc2>
02081 operator+(const rope<_CharT2, _Alloc2>& __left,
02082 const rope<_CharT2, _Alloc2>& __right);
02083
02084 template<class _CharT2, class _Alloc2>
02085 friend rope<_CharT2, _Alloc2>
02086 operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
02087
02088 template<class _CharT2, class _Alloc2>
02089 friend rope<_CharT2, _Alloc2>
02090 operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
02091
02092
02093
02094
02095
02096
02097
02098 rope&
02099 append(const _CharT* __iter, size_t __n)
02100 {
02101 _RopeRep* __result =
02102 _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
02103 _S_unref(this->_M_tree_ptr);
02104 this->_M_tree_ptr = __result;
02105 return *this;
02106 }
02107
02108 rope&
02109 append(const _CharT* __c_string)
02110 {
02111 size_t __len = _S_char_ptr_len(__c_string);
02112 append(__c_string, __len);
02113 return(*this);
02114 }
02115
02116 rope&
02117 append(const _CharT* __s, const _CharT* __e)
02118 {
02119 _RopeRep* __result =
02120 _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
02121 _S_unref(this->_M_tree_ptr);
02122 this->_M_tree_ptr = __result;
02123 return *this;
02124 }
02125
02126 rope&
02127 append(const_iterator __s, const_iterator __e)
02128 {
02129 _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
02130 __s._M_current_pos,
02131 __e._M_current_pos));
02132 _RopeRep* __result = _S_concat(this->_M_tree_ptr,
02133 (_RopeRep*)__appendee);
02134 _S_unref(this->_M_tree_ptr);
02135 this->_M_tree_ptr = __result;
02136 return *this;
02137 }
02138
02139 rope&
02140 append(_CharT __c)
02141 {
02142 _RopeRep* __result =
02143 _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
02144 _S_unref(this->_M_tree_ptr);
02145 this->_M_tree_ptr = __result;
02146 return *this;
02147 }
02148
02149 rope&
02150 append()
02151 { return append(_CharT()); }
02152
02153 rope&
02154 append(const rope& __y)
02155 {
02156 _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
02157 _S_unref(this->_M_tree_ptr);
02158 this->_M_tree_ptr = __result;
02159 return *this;
02160 }
02161
02162 rope&
02163 append(size_t __n, _CharT __c)
02164 {
02165 rope<_CharT,_Alloc> __last(__n, __c);
02166 return append(__last);
02167 }
02168
02169 void
02170 swap(rope& __b)
02171 {
02172 _RopeRep* __tmp = this->_M_tree_ptr;
02173 this->_M_tree_ptr = __b._M_tree_ptr;
02174 __b._M_tree_ptr = __tmp;
02175 }
02176
02177 protected:
02178
02179 static _RopeRep*
02180 replace(_RopeRep* __old, size_t __pos1,
02181 size_t __pos2, _RopeRep* __r)
02182 {
02183 if (0 == __old)
02184 {
02185 _S_ref(__r);
02186 return __r;
02187 }
02188 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
02189 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
02190 _RopeRep* __result;
02191
02192 if (0 == __r)
02193 __result = _S_concat(__left, __right);
02194 else
02195 {
02196 _Self_destruct_ptr __left_result(_S_concat(__left, __r));
02197 __result = _S_concat(__left_result, __right);
02198 }
02199 return __result;
02200 }
02201
02202 public:
02203 void
02204 insert(size_t __p, const rope& __r)
02205 {
02206 _RopeRep* __result =
02207 replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
02208 _S_unref(this->_M_tree_ptr);
02209 this->_M_tree_ptr = __result;
02210 }
02211
02212 void
02213 insert(size_t __p, size_t __n, _CharT __c)
02214 {
02215 rope<_CharT,_Alloc> __r(__n,__c);
02216 insert(__p, __r);
02217 }
02218
02219 void
02220 insert(size_t __p, const _CharT* __i, size_t __n)
02221 {
02222 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
02223 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
02224 __p, size()));
02225 _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
02226
02227
02228
02229 _RopeRep* __result = _S_concat(__left_result, __right);
02230 _S_unref(this->_M_tree_ptr);
02231 this->_M_tree_ptr = __result;
02232 }
02233
02234 void
02235 insert(size_t __p, const _CharT* __c_string)
02236 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
02237
02238 void
02239 insert(size_t __p, _CharT __c)
02240 { insert(__p, &__c, 1); }
02241
02242 void
02243 insert(size_t __p)
02244 {
02245 _CharT __c = _CharT();
02246 insert(__p, &__c, 1);
02247 }
02248
02249 void
02250 insert(size_t __p, const _CharT* __i, const _CharT* __j)
02251 {
02252 rope __r(__i, __j);
02253 insert(__p, __r);
02254 }
02255
02256 void
02257 insert(size_t __p, const const_iterator& __i,
02258 const const_iterator& __j)
02259 {
02260 rope __r(__i, __j);
02261 insert(__p, __r);
02262 }
02263
02264 void
02265 insert(size_t __p, const iterator& __i,
02266 const iterator& __j)
02267 {
02268 rope __r(__i, __j);
02269 insert(__p, __r);
02270 }
02271
02272
02273
02274 void
02275 replace(size_t __p, size_t __n, const rope& __r)
02276 {
02277 _RopeRep* __result =
02278 replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
02279 _S_unref(this->_M_tree_ptr);
02280 this->_M_tree_ptr = __result;
02281 }
02282
02283 void
02284 replace(size_t __p, size_t __n,
02285 const _CharT* __i, size_t __i_len)
02286 {
02287 rope __r(__i, __i_len);
02288 replace(__p, __n, __r);
02289 }
02290
02291 void
02292 replace(size_t __p, size_t __n, _CharT __c)
02293 {
02294 rope __r(__c);
02295 replace(__p, __n, __r);
02296 }
02297
02298 void
02299 replace(size_t __p, size_t __n, const _CharT* __c_string)
02300 {
02301 rope __r(__c_string);
02302 replace(__p, __n, __r);
02303 }
02304
02305 void
02306 replace(size_t __p, size_t __n,
02307 const _CharT* __i, const _CharT* __j)
02308 {
02309 rope __r(__i, __j);
02310 replace(__p, __n, __r);
02311 }
02312
02313 void
02314 replace(size_t __p, size_t __n,
02315 const const_iterator& __i, const const_iterator& __j)
02316 {
02317 rope __r(__i, __j);
02318 replace(__p, __n, __r);
02319 }
02320
02321 void
02322 replace(size_t __p, size_t __n,
02323 const iterator& __i, const iterator& __j)
02324 {
02325 rope __r(__i, __j);
02326 replace(__p, __n, __r);
02327 }
02328
02329
02330 void
02331 replace(size_t __p, _CharT __c)
02332 {
02333 iterator __i(this, __p);
02334 *__i = __c;
02335 }
02336
02337 void
02338 replace(size_t __p, const rope& __r)
02339 { replace(__p, 1, __r); }
02340
02341 void
02342 replace(size_t __p, const _CharT* __i, size_t __i_len)
02343 { replace(__p, 1, __i, __i_len); }
02344
02345 void
02346 replace(size_t __p, const _CharT* __c_string)
02347 { replace(__p, 1, __c_string); }
02348
02349 void
02350 replace(size_t __p, const _CharT* __i, const _CharT* __j)
02351 { replace(__p, 1, __i, __j); }
02352
02353 void
02354 replace(size_t __p, const const_iterator& __i,
02355 const const_iterator& __j)
02356 { replace(__p, 1, __i, __j); }
02357
02358 void
02359 replace(size_t __p, const iterator& __i,
02360 const iterator& __j)
02361 { replace(__p, 1, __i, __j); }
02362
02363
02364 void
02365 erase(size_t __p, size_t __n)
02366 {
02367 _RopeRep* __result = replace(this->_M_tree_ptr, __p,
02368 __p + __n, 0);
02369 _S_unref(this->_M_tree_ptr);
02370 this->_M_tree_ptr = __result;
02371 }
02372
02373
02374 void
02375 erase(size_t __p)
02376 { erase(__p, __p + 1); }
02377
02378
02379 iterator
02380 insert(const iterator& __p, const rope& __r)
02381 {
02382 insert(__p.index(), __r);
02383 return __p;
02384 }
02385
02386 iterator
02387 insert(const iterator& __p, size_t __n, _CharT __c)
02388 {
02389 insert(__p.index(), __n, __c);
02390 return __p;
02391 }
02392
02393 iterator insert(const iterator& __p, _CharT __c)
02394 {
02395 insert(__p.index(), __c);
02396 return __p;
02397 }
02398
02399 iterator
02400 insert(const iterator& __p )
02401 {
02402 insert(__p.index());
02403 return __p;
02404 }
02405
02406 iterator
02407 insert(const iterator& __p, const _CharT* c_string)
02408 {
02409 insert(__p.index(), c_string);
02410 return __p;
02411 }
02412
02413 iterator
02414 insert(const iterator& __p, const _CharT* __i, size_t __n)
02415 {
02416 insert(__p.index(), __i, __n);
02417 return __p;
02418 }
02419
02420 iterator
02421 insert(const iterator& __p, const _CharT* __i,
02422 const _CharT* __j)
02423 {
02424 insert(__p.index(), __i, __j);
02425 return __p;
02426 }
02427
02428 iterator
02429 insert(const iterator& __p,
02430 const const_iterator& __i, const const_iterator& __j)
02431 {
02432 insert(__p.index(), __i, __j);
02433 return __p;
02434 }
02435
02436 iterator
02437 insert(const iterator& __p,
02438 const iterator& __i, const iterator& __j)
02439 {
02440 insert(__p.index(), __i, __j);
02441 return __p;
02442 }
02443
02444
02445 void
02446 replace(const iterator& __p, const iterator& __q, const rope& __r)
02447 { replace(__p.index(), __q.index() - __p.index(), __r); }
02448
02449 void
02450 replace(const iterator& __p, const iterator& __q, _CharT __c)
02451 { replace(__p.index(), __q.index() - __p.index(), __c); }
02452
02453 void
02454 replace(const iterator& __p, const iterator& __q,
02455 const _CharT* __c_string)
02456 { replace(__p.index(), __q.index() - __p.index(), __c_string); }
02457
02458 void
02459 replace(const iterator& __p, const iterator& __q,
02460 const _CharT* __i, size_t __n)
02461 { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
02462
02463 void
02464 replace(const iterator& __p, const iterator& __q,
02465 const _CharT* __i, const _CharT* __j)
02466 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02467
02468 void
02469 replace(const iterator& __p, const iterator& __q,
02470 const const_iterator& __i, const const_iterator& __j)
02471 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02472
02473 void
02474 replace(const iterator& __p, const iterator& __q,
02475 const iterator& __i, const iterator& __j)
02476 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02477
02478
02479 void
02480 replace(const iterator& __p, const rope& __r)
02481 { replace(__p.index(), __r); }
02482
02483 void
02484 replace(const iterator& __p, _CharT __c)
02485 { replace(__p.index(), __c); }
02486
02487 void
02488 replace(const iterator& __p, const _CharT* __c_string)
02489 { replace(__p.index(), __c_string); }
02490
02491 void
02492 replace(const iterator& __p, const _CharT* __i, size_t __n)
02493 { replace(__p.index(), __i, __n); }
02494
02495 void
02496 replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
02497 { replace(__p.index(), __i, __j); }
02498
02499 void
02500 replace(const iterator& __p, const_iterator __i, const_iterator __j)
02501 { replace(__p.index(), __i, __j); }
02502
02503 void
02504 replace(const iterator& __p, iterator __i, iterator __j)
02505 { replace(__p.index(), __i, __j); }
02506
02507
02508 iterator
02509 erase(const iterator& __p, const iterator& __q)
02510 {
02511 size_t __p_index = __p.index();
02512 erase(__p_index, __q.index() - __p_index);
02513 return iterator(this, __p_index);
02514 }
02515
02516 iterator
02517 erase(const iterator& __p)
02518 {
02519 size_t __p_index = __p.index();
02520 erase(__p_index, 1);
02521 return iterator(this, __p_index);
02522 }
02523
02524 rope
02525 substr(size_t __start, size_t __len = 1) const
02526 {
02527 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02528 __start,
02529 __start + __len));
02530 }
02531
02532 rope
02533 substr(iterator __start, iterator __end) const
02534 {
02535 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02536 __start.index(),
02537 __end.index()));
02538 }
02539
02540 rope
02541 substr(iterator __start) const
02542 {
02543 size_t __pos = __start.index();
02544 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02545 __pos, __pos + 1));
02546 }
02547
02548 rope
02549 substr(const_iterator __start, const_iterator __end) const
02550 {
02551
02552
02553 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02554 __start.index(),
02555 __end.index()));
02556 }
02557
02558 rope<_CharT, _Alloc>
02559 substr(const_iterator __start)
02560 {
02561 size_t __pos = __start.index();
02562 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02563 __pos, __pos + 1));
02564 }
02565
02566 static const size_type npos;
02567
02568 size_type find(_CharT __c, size_type __pos = 0) const;
02569
02570 size_type
02571 find(const _CharT* __s, size_type __pos = 0) const
02572 {
02573 size_type __result_pos;
02574 const_iterator __result =
02575 std::search(const_begin() + __pos, const_end(),
02576 __s, __s + _S_char_ptr_len(__s));
02577 __result_pos = __result.index();
02578 #ifndef __STL_OLD_ROPE_SEMANTICS
02579 if (__result_pos == size())
02580 __result_pos = npos;
02581 #endif
02582 return __result_pos;
02583 }
02584
02585 iterator
02586 mutable_begin()
02587 { return(iterator(this, 0)); }
02588
02589 iterator
02590 mutable_end()
02591 { return(iterator(this, size())); }
02592
02593 typedef std::reverse_iterator<iterator> reverse_iterator;
02594
02595 reverse_iterator
02596 mutable_rbegin()
02597 { return reverse_iterator(mutable_end()); }
02598
02599 reverse_iterator
02600 mutable_rend()
02601 { return reverse_iterator(mutable_begin()); }
02602
02603 reference
02604 mutable_reference_at(size_type __pos)
02605 { return reference(this, __pos); }
02606
02607 #ifdef __STD_STUFF
02608 reference
02609 operator[] (size_type __pos)
02610 { return _char_ref_proxy(this, __pos); }
02611
02612 reference
02613 at(size_type __pos)
02614 {
02615
02616 return (*this)[__pos];
02617 }
02618
02619 void resize(size_type __n, _CharT __c) { }
02620 void resize(size_type __n) { }
02621 void reserve(size_type __res_arg = 0) { }
02622
02623 size_type
02624 capacity() const
02625 { return max_size(); }
02626
02627
02628
02629
02630 size_type
02631 copy(_CharT* __buffer, size_type __n,
02632 size_type __pos = 0) const
02633 { return copy(__pos, __n, __buffer); }
02634
02635 iterator
02636 end()
02637 { return mutable_end(); }
02638
02639 iterator
02640 begin()
02641 { return mutable_begin(); }
02642
02643 reverse_iterator
02644 rend()
02645 { return mutable_rend(); }
02646
02647 reverse_iterator
02648 rbegin()
02649 { return mutable_rbegin(); }
02650
02651 #else
02652 const_iterator
02653 end()
02654 { return const_end(); }
02655
02656 const_iterator
02657 begin()
02658 { return const_begin(); }
02659
02660 const_reverse_iterator
02661 rend()
02662 { return const_rend(); }
02663
02664 const_reverse_iterator
02665 rbegin()
02666 { return const_rbegin(); }
02667
02668 #endif
02669 };
02670
02671 template <class _CharT, class _Alloc>
02672 const typename rope<_CharT, _Alloc>::size_type
02673 rope<_CharT, _Alloc>::npos = (size_type)(-1);
02674
02675 template <class _CharT, class _Alloc>
02676 inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02677 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02678 { return (__x._M_current_pos == __y._M_current_pos
02679 && __x._M_root == __y._M_root); }
02680
02681 template <class _CharT, class _Alloc>
02682 inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02683 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02684 { return (__x._M_current_pos < __y._M_current_pos); }
02685
02686 template <class _CharT, class _Alloc>
02687 inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02688 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02689 { return !(__x == __y); }
02690
02691 template <class _CharT, class _Alloc>
02692 inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02693 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02694 { return __y < __x; }
02695
02696 template <class _CharT, class _Alloc>
02697 inline bool
02698 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02699 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02700 { return !(__y < __x); }
02701
02702 template <class _CharT, class _Alloc>
02703 inline bool
02704 operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02705 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02706 { return !(__x < __y); }
02707
02708 template <class _CharT, class _Alloc>
02709 inline ptrdiff_t
02710 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02711 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02712 { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
02713
02714 template <class _CharT, class _Alloc>
02715 inline _Rope_const_iterator<_CharT, _Alloc>
02716 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02717 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02718 __x._M_current_pos - __n); }
02719
02720 template <class _CharT, class _Alloc>
02721 inline _Rope_const_iterator<_CharT, _Alloc>
02722 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02723 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02724 __x._M_current_pos + __n); }
02725
02726 template <class _CharT, class _Alloc>
02727 inline _Rope_const_iterator<_CharT, _Alloc>
02728 operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
02729 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02730 __x._M_current_pos + __n); }
02731
02732 template <class _CharT, class _Alloc>
02733 inline bool
02734 operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
02735 const _Rope_iterator<_CharT, _Alloc>& __y)
02736 {return (__x._M_current_pos == __y._M_current_pos
02737 && __x._M_root_rope == __y._M_root_rope); }
02738
02739 template <class _CharT, class _Alloc>
02740 inline bool
02741 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
02742 const _Rope_iterator<_CharT, _Alloc>& __y)
02743 { return (__x._M_current_pos < __y._M_current_pos); }
02744
02745 template <class _CharT, class _Alloc>
02746 inline bool
02747 operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
02748 const _Rope_iterator<_CharT, _Alloc>& __y)
02749 { return !(__x == __y); }
02750
02751 template <class _CharT, class _Alloc>
02752 inline bool
02753 operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
02754 const _Rope_iterator<_CharT, _Alloc>& __y)
02755 { return __y < __x; }
02756
02757 template <class _CharT, class _Alloc>
02758 inline bool
02759 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
02760 const _Rope_iterator<_CharT, _Alloc>& __y)
02761 { return !(__y < __x); }
02762
02763 template <class _CharT, class _Alloc>
02764 inline bool
02765 operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
02766 const _Rope_iterator<_CharT, _Alloc>& __y)
02767 { return !(__x < __y); }
02768
02769 template <class _CharT, class _Alloc>
02770 inline ptrdiff_t
02771 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
02772 const _Rope_iterator<_CharT, _Alloc>& __y)
02773 { return ((ptrdiff_t)__x._M_current_pos
02774 - (ptrdiff_t)__y._M_current_pos); }
02775
02776 template <class _CharT, class _Alloc>
02777 inline _Rope_iterator<_CharT, _Alloc>
02778 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
02779 ptrdiff_t __n)
02780 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02781 __x._M_current_pos - __n); }
02782
02783 template <class _CharT, class _Alloc>
02784 inline _Rope_iterator<_CharT, _Alloc>
02785 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02786 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02787 __x._M_current_pos + __n); }
02788
02789 template <class _CharT, class _Alloc>
02790 inline _Rope_iterator<_CharT, _Alloc>
02791 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
02792 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02793 __x._M_current_pos + __n); }
02794
02795 template <class _CharT, class _Alloc>
02796 inline rope<_CharT, _Alloc>
02797 operator+(const rope<_CharT, _Alloc>& __left,
02798 const rope<_CharT, _Alloc>& __right)
02799 {
02800
02801
02802 typedef rope<_CharT, _Alloc> rope_type;
02803 return rope_type(rope_type::_S_concat(__left._M_tree_ptr,
02804 __right._M_tree_ptr));
02805 }
02806
02807 template <class _CharT, class _Alloc>
02808 inline rope<_CharT, _Alloc>&
02809 operator+=(rope<_CharT, _Alloc>& __left,
02810 const rope<_CharT, _Alloc>& __right)
02811 {
02812 __left.append(__right);
02813 return __left;
02814 }
02815
02816 template <class _CharT, class _Alloc>
02817 inline rope<_CharT, _Alloc>
02818 operator+(const rope<_CharT, _Alloc>& __left,
02819 const _CharT* __right)
02820 {
02821 typedef rope<_CharT, _Alloc> rope_type;
02822 size_t __rlen = rope_type::_S_char_ptr_len(__right);
02823 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
02824 __right, __rlen));
02825 }
02826
02827 template <class _CharT, class _Alloc>
02828 inline rope<_CharT, _Alloc>&
02829 operator+=(rope<_CharT, _Alloc>& __left,
02830 const _CharT* __right)
02831 {
02832 __left.append(__right);
02833 return __left;
02834 }
02835
02836 template <class _CharT, class _Alloc>
02837 inline rope<_CharT, _Alloc>
02838 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
02839 {
02840 typedef rope<_CharT, _Alloc> rope_type;
02841 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
02842 &__right, 1));
02843 }
02844
02845 template <class _CharT, class _Alloc>
02846 inline rope<_CharT, _Alloc>&
02847 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
02848 {
02849 __left.append(__right);
02850 return __left;
02851 }
02852
02853 template <class _CharT, class _Alloc>
02854 bool
02855 operator<(const rope<_CharT, _Alloc>& __left,
02856 const rope<_CharT, _Alloc>& __right)
02857 { return __left.compare(__right) < 0; }
02858
02859 template <class _CharT, class _Alloc>
02860 bool
02861 operator==(const rope<_CharT, _Alloc>& __left,
02862 const rope<_CharT, _Alloc>& __right)
02863 { return __left.compare(__right) == 0; }
02864
02865 template <class _CharT, class _Alloc>
02866 inline bool
02867 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
02868 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
02869 { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
02870
02871 template <class _CharT, class _Alloc>
02872 inline bool
02873 operator!=(const rope<_CharT, _Alloc>& __x,
02874 const rope<_CharT, _Alloc>& __y)
02875 { return !(__x == __y); }
02876
02877 template <class _CharT, class _Alloc>
02878 inline bool
02879 operator>(const rope<_CharT, _Alloc>& __x,
02880 const rope<_CharT, _Alloc>& __y)
02881 { return __y < __x; }
02882
02883 template <class _CharT, class _Alloc>
02884 inline bool
02885 operator<=(const rope<_CharT, _Alloc>& __x,
02886 const rope<_CharT, _Alloc>& __y)
02887 { return !(__y < __x); }
02888
02889 template <class _CharT, class _Alloc>
02890 inline bool
02891 operator>=(const rope<_CharT, _Alloc>& __x,
02892 const rope<_CharT, _Alloc>& __y)
02893 { return !(__x < __y); }
02894
02895 template <class _CharT, class _Alloc>
02896 inline bool
02897 operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
02898 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
02899 { return !(__x == __y); }
02900
02901 template<class _CharT, class _Traits, class _Alloc>
02902 std::basic_ostream<_CharT, _Traits>&
02903 operator<<(std::basic_ostream<_CharT, _Traits>& __o,
02904 const rope<_CharT, _Alloc>& __r);
02905
02906 typedef rope<char> crope;
02907 typedef rope<wchar_t> wrope;
02908
02909 inline crope::reference
02910 __mutable_reference_at(crope& __c, size_t __i)
02911 { return __c.mutable_reference_at(__i); }
02912
02913 inline wrope::reference
02914 __mutable_reference_at(wrope& __c, size_t __i)
02915 { return __c.mutable_reference_at(__i); }
02916
02917 template <class _CharT, class _Alloc>
02918 inline void
02919 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
02920 { __x.swap(__y); }
02921
02922 _GLIBCXX_END_NAMESPACE_VERSION
02923 }
02924
02925
02926 namespace std _GLIBCXX_VISIBILITY(default)
02927 {
02928 namespace tr1
02929 {
02930 _GLIBCXX_BEGIN_NAMESPACE_VERSION
02931
02932 template<>
02933 struct hash<__gnu_cxx::crope>
02934 {
02935 size_t
02936 operator()(const __gnu_cxx::crope& __str) const
02937 {
02938 size_t __size = __str.size();
02939 if (0 == __size)
02940 return 0;
02941 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
02942 }
02943 };
02944
02945
02946 template<>
02947 struct hash<__gnu_cxx::wrope>
02948 {
02949 size_t
02950 operator()(const __gnu_cxx::wrope& __str) const
02951 {
02952 size_t __size = __str.size();
02953 if (0 == __size)
02954 return 0;
02955 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
02956 }
02957 };
02958
02959 _GLIBCXX_END_NAMESPACE_VERSION
02960 }
02961 }
02962
02963 # include <ext/ropeimpl.h>
02964
02965 #endif