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