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