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