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