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