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