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