contrib/gcc-4.7/libstdc++-v3/include/ext/rope

   1 // SGI's rope class -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
   4 // 2012 Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  * Copyright (c) 1997
  28  * Silicon Graphics Computer Systems, Inc.
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Silicon Graphics makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  */
  38
  39 /** @file ext/rope
  40  *  This file is a GNU extension to the Standard C++ Library (possibly
  41  *  containing extensions from the HP/SGI STL subset).
  42  */
  43
  44 #ifndef _ROPE
  45 #define _ROPE 1
  46
  47 #pragma GCC system_header
  48
  49 #include <algorithm>
  50 #include <iosfwd>
  51 #include <bits/stl_construct.h>
  52 #include <bits/stl_uninitialized.h>
  53 #include <bits/stl_function.h>
  54 #include <bits/stl_numeric.h>
  55 #include <bits/allocator.h>
  56 #include <bits/gthr.h>
  57 #include <tr1/functional>
  58
  59 # ifdef __GC
  60 #   define __GC_CONST const
  61 # else
  62 #   define __GC_CONST   // constant except for deallocation
  63 # endif
  64
  65 #include <ext/memory> // For uninitialized_copy_n
  66
  67 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  68 {
  69   namespace __detail
  70   {
  71     enum { _S_max_rope_depth = 45 };
  72     enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
  73   } // namespace __detail
  74
  75   using std::size_t;
  76   using std::ptrdiff_t;
  77   using std::allocator;
  78   using std::_Destroy;
  79
  80 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  81
  82   // See libstdc++/36832.
  83   template<typename _ForwardIterator, typename _Allocator>
  84     void
  85     _Destroy_const(_ForwardIterator __first,
  86                    _ForwardIterator __last, _Allocator __alloc)
  87     {
  88       for (; __first != __last; ++__first)
  89         __alloc.destroy(&*__first);
  90     }
  91
  92   template<typename _ForwardIterator, typename _Tp>
  93     inline void
  94     _Destroy_const(_ForwardIterator __first,
  95                    _ForwardIterator __last, allocator<_Tp>)
  96     { _Destroy(__first, __last); }
  97
  98   // The _S_eos function is used for those functions that
  99   // convert to/from C-like strings to detect the end of the string.
 100
 101   // The end-of-C-string character.
 102   // This is what the draft standard says it should be.
 103   template <class _CharT>
 104     inline _CharT
 105     _S_eos(_CharT*)
 106     { return _CharT(); }
 107
 108   // Test for basic character types.
 109   // For basic character types leaves having a trailing eos.
 110   template <class _CharT>
 111     inline bool
 112     _S_is_basic_char_type(_CharT*)
 113     { return false; }
 114
 115   template <class _CharT>
 116     inline bool
 117     _S_is_one_byte_char_type(_CharT*)
 118     { return false; }
 119
 120   inline bool
 121   _S_is_basic_char_type(char*)
 122   { return true; }
 123
 124   inline bool
 125   _S_is_one_byte_char_type(char*)
 126   { return true; }
 127
 128   inline bool
 129   _S_is_basic_char_type(wchar_t*)
 130   { return true; }
 131
 132   // Store an eos iff _CharT is a basic character type.
 133   // Do not reference _S_eos if it isn't.
 134   template <class _CharT>
 135     inline void
 136     _S_cond_store_eos(_CharT&) { }
 137
 138   inline void
 139   _S_cond_store_eos(char& __c)
 140   { __c = 0; }
 141
 142   inline void
 143   _S_cond_store_eos(wchar_t& __c)
 144   { __c = 0; }
 145
 146   // char_producers are logically functions that generate a section of
 147   // a string.  These can be converted to ropes.  The resulting rope
 148   // invokes the char_producer on demand.  This allows, for example,
 149   // files to be viewed as ropes without reading the entire file.
 150   template <class _CharT>
 151     class char_producer
 152     {
 153     public:
 154       virtual ~char_producer() { };
 155
 156       virtual void
 157       operator()(size_t __start_pos, size_t __len,
 158                  _CharT* __buffer) = 0;
 159       // Buffer should really be an arbitrary output iterator.
 160       // That way we could flatten directly into an ostream, etc.
 161       // This is thoroughly impossible, since iterator types don't
 162       // have runtime descriptions.
 163     };
 164
 165   // Sequence buffers:
 166   //
 167   // Sequence must provide an append operation that appends an
 168   // array to the sequence.  Sequence buffers are useful only if
 169   // appending an entire array is cheaper than appending element by element.
 170   // This is true for many string representations.
 171   // This should  perhaps inherit from ostream<sequence::value_type>
 172   // and be implemented correspondingly, so that they can be used
 173   // for formatted.  For the sake of portability, we don't do this yet.
 174   //
 175   // For now, sequence buffers behave as output iterators.  But they also
 176   // behave a little like basic_ostringstream<sequence::value_type> and a
 177   // little like containers.
 178
 179   template<class _Sequence, size_t _Buf_sz = 100>
 180     class sequence_buffer
 181     : public std::iterator<std::output_iterator_tag, void, void, void, void>
 182     {
 183     public:
 184       typedef typename _Sequence::value_type value_type;
 185     protected:
 186       _Sequence* _M_prefix;
 187       value_type _M_buffer[_Buf_sz];
 188       size_t     _M_buf_count;
 189     public:
 190
 191       void
 192       flush()
 193       {
 194         _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
 195         _M_buf_count = 0;
 196       }
 197
 198       ~sequence_buffer()
 199       { flush(); }
 200
 201       sequence_buffer()
 202       : _M_prefix(0), _M_buf_count(0) { }
 203
 204       sequence_buffer(const sequence_buffer& __x)
 205       {
 206         _M_prefix = __x._M_prefix;
 207         _M_buf_count = __x._M_buf_count;
 208         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
 209       }
 210
 211       sequence_buffer(sequence_buffer& __x)
 212       {
 213         __x.flush();
 214         _M_prefix = __x._M_prefix;
 215         _M_buf_count = 0;
 216       }
 217
 218       sequence_buffer(_Sequence& __s)
 219       : _M_prefix(&__s), _M_buf_count(0) { }
 220
 221       sequence_buffer&
 222       operator=(sequence_buffer& __x)
 223       {
 224         __x.flush();
 225         _M_prefix = __x._M_prefix;
 226         _M_buf_count = 0;
 227         return *this;
 228       }
 229
 230       sequence_buffer&
 231       operator=(const sequence_buffer& __x)
 232       {
 233         _M_prefix = __x._M_prefix;
 234         _M_buf_count = __x._M_buf_count;
 235         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
 236         return *this;
 237       }
 238
 239       void
 240       push_back(value_type __x)
 241       {
 242         if (_M_buf_count < _Buf_sz)
 243           {
 244             _M_buffer[_M_buf_count] = __x;
 245             ++_M_buf_count;
 246           }
 247         else
 248           {
 249             flush();
 250             _M_buffer[0] = __x;
 251             _M_buf_count = 1;
 252           }
 253       }
 254
 255       void
 256       append(value_type* __s, size_t __len)
 257       {
 258         if (__len + _M_buf_count <= _Buf_sz)
 259           {
 260             size_t __i = _M_buf_count;
 261             for (size_t __j = 0; __j < __len; __i++, __j++)
 262               _M_buffer[__i] = __s[__j];
 263             _M_buf_count += __len;
 264           }
 265         else if (0 == _M_buf_count)
 266           _M_prefix->append(__s, __s + __len);
 267         else
 268           {
 269             flush();
 270             append(__s, __len);
 271           }
 272       }
 273
 274       sequence_buffer&
 275       write(value_type* __s, size_t __len)
 276       {
 277         append(__s, __len);
 278         return *this;
 279       }
 280
 281       sequence_buffer&
 282       put(value_type __x)
 283       {
 284         push_back(__x);
 285         return *this;
 286       }
 287
 288       sequence_buffer&
 289       operator=(const value_type& __rhs)
 290       {
 291         push_back(__rhs);
 292         return *this;
 293       }
 294
 295       sequence_buffer&
 296       operator*()
 297       { return *this; }
 298
 299       sequence_buffer&
 300       operator++()
 301       { return *this; }
 302
 303       sequence_buffer
 304       operator++(int)
 305       { return *this; }
 306     };
 307
 308   // The following should be treated as private, at least for now.
 309   template<class _CharT>
 310     class _Rope_char_consumer
 311     {
 312     public:
 313       // If we had member templates, these should not be virtual.
 314       // For now we need to use run-time parametrization where
 315       // compile-time would do.  Hence this should all be private
 316       // for now.
 317       // The symmetry with char_producer is accidental and temporary.
 318       virtual ~_Rope_char_consumer() { };
 319
 320       virtual bool
 321       operator()(const _CharT* __buffer, size_t __len) = 0;
 322     };
 323
 324   // First a lot of forward declarations.  The standard seems to require
 325   // much stricter "declaration before use" than many of the implementations
 326   // that preceded it.
 327   template<class _CharT, class _Alloc = allocator<_CharT> >
 328     class rope;
 329
 330   template<class _CharT, class _Alloc>
 331     struct _Rope_RopeConcatenation;
 332
 333   template<class _CharT, class _Alloc>
 334     struct _Rope_RopeLeaf;
 335
 336   template<class _CharT, class _Alloc>
 337     struct _Rope_RopeFunction;
 338
 339   template<class _CharT, class _Alloc>
 340     struct _Rope_RopeSubstring;
 341
 342   template<class _CharT, class _Alloc>
 343     class _Rope_iterator;
 344
 345   template<class _CharT, class _Alloc>
 346     class _Rope_const_iterator;
 347
 348   template<class _CharT, class _Alloc>
 349     class _Rope_char_ref_proxy;
 350
 351   template<class _CharT, class _Alloc>
 352     class _Rope_char_ptr_proxy;
 353
 354   template<class _CharT, class _Alloc>
 355     bool
 356     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
 357                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
 358
 359   template<class _CharT, class _Alloc>
 360     _Rope_const_iterator<_CharT, _Alloc>
 361     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
 362               ptrdiff_t __n);
 363
 364   template<class _CharT, class _Alloc>
 365     _Rope_const_iterator<_CharT, _Alloc>
 366     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
 367               ptrdiff_t __n);
 368
 369   template<class _CharT, class _Alloc>
 370     _Rope_const_iterator<_CharT, _Alloc>
 371     operator+(ptrdiff_t __n,
 372               const _Rope_const_iterator<_CharT, _Alloc>& __x);
 373
 374   template<class _CharT, class _Alloc>
 375     bool
 376     operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
 377                const _Rope_const_iterator<_CharT, _Alloc>& __y);
 378
 379   template<class _CharT, class _Alloc>
 380     bool
 381     operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
 382               const _Rope_const_iterator<_CharT, _Alloc>& __y);
 383
 384   template<class _CharT, class _Alloc>
 385     ptrdiff_t
 386     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
 387               const _Rope_const_iterator<_CharT, _Alloc>& __y);
 388
 389   template<class _CharT, class _Alloc>
 390     _Rope_iterator<_CharT, _Alloc>
 391     operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
 392
 393   template<class _CharT, class _Alloc>
 394     _Rope_iterator<_CharT, _Alloc>
 395     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
 396
 397   template<class _CharT, class _Alloc>
 398     _Rope_iterator<_CharT, _Alloc>
 399     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
 400
 401   template<class _CharT, class _Alloc>
 402     bool
 403     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
 404                const _Rope_iterator<_CharT, _Alloc>& __y);
 405
 406   template<class _CharT, class _Alloc>
 407     bool
 408     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
 409               const _Rope_iterator<_CharT, _Alloc>& __y);
 410
 411   template<class _CharT, class _Alloc>
 412     ptrdiff_t
 413     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
 414               const _Rope_iterator<_CharT, _Alloc>& __y);
 415
 416   template<class _CharT, class _Alloc>
 417     rope<_CharT, _Alloc>
 418     operator+(const rope<_CharT, _Alloc>& __left,
 419               const rope<_CharT, _Alloc>& __right);
 420
 421   template<class _CharT, class _Alloc>
 422     rope<_CharT, _Alloc>
 423     operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
 424
 425   template<class _CharT, class _Alloc>
 426     rope<_CharT, _Alloc>
 427     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
 428
 429   // Some helpers, so we can use power on ropes.
 430   // See below for why this isn't local to the implementation.
 431
 432   // This uses a nonstandard refcount convention.
 433   // The result has refcount 0.
 434   template<class _CharT, class _Alloc>
 435     struct _Rope_Concat_fn
 436     : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
 437                                   rope<_CharT, _Alloc> >
 438     {
 439       rope<_CharT, _Alloc>
 440       operator()(const rope<_CharT, _Alloc>& __x,
 441                  const rope<_CharT, _Alloc>& __y)
 442       { return __x + __y; }
 443     };
 444
 445   template <class _CharT, class _Alloc>
 446     inline rope<_CharT, _Alloc>
 447     identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
 448     { return rope<_CharT, _Alloc>(); }
 449
 450   // Class _Refcount_Base provides a type, _RC_t, a data member,
 451   // _M_ref_count, and member functions _M_incr and _M_decr, which perform
 452   // atomic preincrement/predecrement.  The constructor initializes
 453   // _M_ref_count.
 454   struct _Refcount_Base
 455   {
 456     // The type _RC_t
 457     typedef size_t _RC_t;
 458
 459     // The data member _M_ref_count
 460     volatile _RC_t _M_ref_count;
 461
 462     // Constructor
 463 #ifdef __GTHREAD_MUTEX_INIT
 464     __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT;
 465 #else
 466     __gthread_mutex_t _M_ref_count_lock;
 467 #endif
 468
 469     _Refcount_Base(_RC_t __n) : _M_ref_count(__n)
 470     {
 471 #ifndef __GTHREAD_MUTEX_INIT
 472 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
 473       __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
 474 #else
 475 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
 476 #endif
 477 #endif
 478     }
 479
 480 #ifndef __GTHREAD_MUTEX_INIT
 481     ~_Refcount_Base()
 482     { __gthread_mutex_destroy(&_M_ref_count_lock); }
 483 #endif
 484
 485     void
 486     _M_incr()
 487     {
 488       __gthread_mutex_lock(&_M_ref_count_lock);
 489       ++_M_ref_count;
 490       __gthread_mutex_unlock(&_M_ref_count_lock);
 491     }
 492
 493     _RC_t
 494     _M_decr()
 495     {
 496       __gthread_mutex_lock(&_M_ref_count_lock);
 497       volatile _RC_t __tmp = --_M_ref_count;
 498       __gthread_mutex_unlock(&_M_ref_count_lock);
 499       return __tmp;
 500     }
 501   };
 502
 503   //
 504   // What follows should really be local to rope.  Unfortunately,
 505   // that doesn't work, since it makes it impossible to define generic
 506   // equality on rope iterators.  According to the draft standard, the
 507   // template parameters for such an equality operator cannot be inferred
 508   // from the occurrence of a member class as a parameter.
 509   // (SGI compilers in fact allow this, but the __result wouldn't be
 510   // portable.)
 511   // Similarly, some of the static member functions are member functions
 512   // only to avoid polluting the global namespace, and to circumvent
 513   // restrictions on type inference for template functions.
 514   //
 515
 516   //
 517   // The internal data structure for representing a rope.  This is
 518   // private to the implementation.  A rope is really just a pointer
 519   // to one of these.
 520   //
 521   // A few basic functions for manipulating this data structure
 522   // are members of _RopeRep.  Most of the more complex algorithms
 523   // are implemented as rope members.
 524   //
 525   // Some of the static member functions of _RopeRep have identically
 526   // named functions in rope that simply invoke the _RopeRep versions.
 527
 528 #define __ROPE_DEFINE_ALLOCS(__a) \
 529         __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
 530         typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
 531         __ROPE_DEFINE_ALLOC(__C,_C) \
 532         typedef _Rope_RopeLeaf<_CharT,__a> __L; \
 533         __ROPE_DEFINE_ALLOC(__L,_L) \
 534         typedef _Rope_RopeFunction<_CharT,__a> __F; \
 535         __ROPE_DEFINE_ALLOC(__F,_F) \
 536         typedef _Rope_RopeSubstring<_CharT,__a> __S; \
 537         __ROPE_DEFINE_ALLOC(__S,_S)
 538
 539   //  Internal rope nodes potentially store a copy of the allocator
 540   //  instance used to allocate them.  This is mostly redundant.
 541   //  But the alternative would be to pass allocator instances around
 542   //  in some form to nearly all internal functions, since any pointer
 543   //  assignment may result in a zero reference count and thus require
 544   //  deallocation.
 545
 546 #define __STATIC_IF_SGI_ALLOC  /* not static */
 547
 548   template <class _CharT, class _Alloc>
 549     struct _Rope_rep_base
 550     : public _Alloc
 551     {
 552       typedef _Alloc allocator_type;
 553
 554       allocator_type
 555       get_allocator() const
 556       { return *static_cast<const _Alloc*>(this); }
 557
 558       allocator_type&
 559       _M_get_allocator()
 560       { return *static_cast<_Alloc*>(this); }
 561
 562       const allocator_type&
 563       _M_get_allocator() const
 564       { return *static_cast<const _Alloc*>(this); }
 565
 566       _Rope_rep_base(size_t __size, const allocator_type&)
 567       : _M_size(__size) { }
 568
 569       size_t _M_size;
 570
 571 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
 572         typedef typename \
 573           _Alloc::template rebind<_Tp>::other __name##Alloc; \
 574         static _Tp* __name##_allocate(size_t __n) \
 575           { return __name##Alloc().allocate(__n); } \
 576         static void __name##_deallocate(_Tp *__p, size_t __n) \
 577           { __name##Alloc().deallocate(__p, __n); }
 578       __ROPE_DEFINE_ALLOCS(_Alloc)
 579 # undef __ROPE_DEFINE_ALLOC
 580     };
 581
 582   template<class _CharT, class _Alloc>
 583     struct _Rope_RopeRep
 584     : public _Rope_rep_base<_CharT, _Alloc>
 585 # ifndef __GC
 586              , _Refcount_Base
 587 # endif
 588     {
 589     public:
 590       __detail::_Tag _M_tag:8;
 591       bool _M_is_balanced:8;
 592       unsigned char _M_depth;
 593       __GC_CONST _CharT* _M_c_string;
 594 #ifdef __GTHREAD_MUTEX_INIT
 595       __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT;
 596 #else
 597       __gthread_mutex_t _M_c_string_lock;
 598 #endif
 599                         /* Flattened version of string, if needed.  */
 600                         /* typically 0.                             */
 601                         /* If it's not 0, then the memory is owned  */
 602                         /* by this node.                            */
 603                         /* In the case of a leaf, this may point to */
 604                         /* the same memory as the data field.       */
 605       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
 606         allocator_type;
 607
 608       using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
 609       using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
 610
 611       _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
 612                     const allocator_type& __a)
 613       : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
 614 #ifndef __GC
 615         _Refcount_Base(1),
 616 #endif
 617         _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
 618 #ifdef __GTHREAD_MUTEX_INIT
 619       { }
 620 #else
 621       { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
 622       ~_Rope_RopeRep()
 623       { __gthread_mutex_destroy (&_M_c_string_lock); }
 624 #endif
 625 #ifdef __GC
 626       void
 627       _M_incr () { }
 628 #endif
 629       static void
 630       _S_free_string(__GC_CONST _CharT*, size_t __len,
 631                      allocator_type& __a);
 632 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
 633                         // Deallocate data section of a leaf.
 634                         // This shouldn't be a member function.
 635                         // But its hard to do anything else at the
 636                         // moment, because it's templatized w.r.t.
 637                         // an allocator.
 638                         // Does nothing if __GC is defined.
 639 #ifndef __GC
 640       void _M_free_c_string();
 641       void _M_free_tree();
 642       // Deallocate t. Assumes t is not 0.
 643       void
 644       _M_unref_nonnil()
 645       {
 646         if (0 == _M_decr())
 647           _M_free_tree();
 648       }
 649
 650       void
 651       _M_ref_nonnil()
 652       { _M_incr(); }
 653
 654       static void
 655       _S_unref(_Rope_RopeRep* __t)
 656       {
 657         if (0 != __t)
 658           __t->_M_unref_nonnil();
 659       }
 660
 661       static void
 662       _S_ref(_Rope_RopeRep* __t)
 663       {
 664         if (0 != __t)
 665           __t->_M_incr();
 666       }
 667
 668       static void
 669       _S_free_if_unref(_Rope_RopeRep* __t)
 670       {
 671         if (0 != __t && 0 == __t->_M_ref_count)
 672           __t->_M_free_tree();
 673       }
 674 #   else /* __GC */
 675       void _M_unref_nonnil() { }
 676       void _M_ref_nonnil() { }
 677       static void _S_unref(_Rope_RopeRep*) { }
 678       static void _S_ref(_Rope_RopeRep*) { }
 679       static void _S_free_if_unref(_Rope_RopeRep*) { }
 680 #   endif
 681 protected:
 682       _Rope_RopeRep&
 683       operator=(const _Rope_RopeRep&);
 684
 685       _Rope_RopeRep(const _Rope_RopeRep&);
 686     };
 687
 688   template<class _CharT, class _Alloc>
 689     struct _Rope_RopeLeaf
 690     : public _Rope_RopeRep<_CharT, _Alloc>
 691     {
 692     public:
 693       // Apparently needed by VC++
 694       // The data fields of leaves are allocated with some
 695       // extra space, to accommodate future growth and for basic
 696       // character types, to hold a trailing eos character.
 697       enum { _S_alloc_granularity = 8 };
 698
 699       static size_t
 700       _S_rounded_up_size(size_t __n)
 701       {
 702         size_t __size_with_eos;
 703
 704         if (_S_is_basic_char_type((_CharT*)0))
 705           __size_with_eos = __n + 1;
 706         else
 707           __size_with_eos = __n;
 708 #ifdef __GC
 709         return __size_with_eos;
 710 #else
 711         // Allow slop for in-place expansion.
 712         return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
 713                 &~ (size_t(_S_alloc_granularity) - 1));
 714 #endif
 715       }
 716       __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
 717                                   /* The allocated size is         */
 718                                   /* _S_rounded_up_size(size), except */
 719                                   /* in the GC case, in which it   */
 720                                   /* doesn't matter.               */
 721       typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
 722         allocator_type;
 723
 724       _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
 725                      const allocator_type& __a)
 726       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
 727                                       __size, __a), _M_data(__d)
 728       {
 729         if (_S_is_basic_char_type((_CharT *)0))
 730           {
 731             // already eos terminated.
 732             this->_M_c_string = __d;
 733           }
 734       }
 735       // The constructor assumes that d has been allocated with
 736       // the proper allocator and the properly padded size.
 737       // In contrast, the destructor deallocates the data:
 738 #ifndef __GC
 739       ~_Rope_RopeLeaf() throw()
 740       {
 741         if (_M_data != this->_M_c_string)
 742           this->_M_free_c_string();
 743
 744         this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
 745       }
 746 #endif
 747 protected:
 748       _Rope_RopeLeaf&
 749       operator=(const _Rope_RopeLeaf&);
 750
 751       _Rope_RopeLeaf(const _Rope_RopeLeaf&);
 752     };
 753
 754   template<class _CharT, class _Alloc>
 755     struct _Rope_RopeConcatenation
 756     : public _Rope_RopeRep<_CharT, _Alloc>
 757     {
 758     public:
 759       _Rope_RopeRep<_CharT, _Alloc>* _M_left;
 760       _Rope_RopeRep<_CharT, _Alloc>* _M_right;
 761
 762       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
 763         allocator_type;
 764
 765       _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
 766                               _Rope_RopeRep<_CharT, _Alloc>* __r,
 767                               const allocator_type& __a)
 768         : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
 769                                       std::max(__l->_M_depth,
 770                                                __r->_M_depth) + 1,
 771                                       false,
 772                                       __l->_M_size + __r->_M_size, __a),
 773         _M_left(__l), _M_right(__r)
 774       { }
 775 #ifndef __GC
 776       ~_Rope_RopeConcatenation() throw()
 777       {
 778         this->_M_free_c_string();
 779         _M_left->_M_unref_nonnil();
 780         _M_right->_M_unref_nonnil();
 781       }
 782 #endif
 783 protected:
 784       _Rope_RopeConcatenation&
 785       operator=(const _Rope_RopeConcatenation&);
 786
 787       _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
 788     };
 789
 790   template<class _CharT, class _Alloc>
 791     struct _Rope_RopeFunction
 792     : public _Rope_RopeRep<_CharT, _Alloc>
 793     {
 794     public:
 795       char_producer<_CharT>* _M_fn;
 796 #ifndef __GC
 797       bool _M_delete_when_done; // Char_producer is owned by the
 798                                 // rope and should be explicitly
 799                                 // deleted when the rope becomes
 800                                 // inaccessible.
 801 #else
 802       // In the GC case, we either register the rope for
 803       // finalization, or not.  Thus the field is unnecessary;
 804       // the information is stored in the collector data structures.
 805       // We do need a finalization procedure to be invoked by the
 806       // collector.
 807       static void
 808       _S_fn_finalization_proc(void * __tree, void *)
 809       { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
 810 #endif
 811     typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
 812       allocator_type;
 813
 814       _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
 815                         bool __d, const allocator_type& __a)
 816       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
 817         , _M_fn(__f)
 818 #ifndef __GC
 819         , _M_delete_when_done(__d)
 820 #endif
 821       {
 822 #ifdef __GC
 823         if (__d)
 824           {
 825             GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
 826                                   _S_fn_finalization_proc, 0, 0, 0);
 827           }
 828 #endif
 829       }
 830 #ifndef __GC
 831       ~_Rope_RopeFunction() throw()
 832       {
 833         this->_M_free_c_string();
 834         if (_M_delete_when_done)
 835           delete _M_fn;
 836       }
 837 # endif
 838     protected:
 839       _Rope_RopeFunction&
 840       operator=(const _Rope_RopeFunction&);
 841
 842       _Rope_RopeFunction(const _Rope_RopeFunction&);
 843     };
 844   // Substring results are usually represented using just
 845   // concatenation nodes.  But in the case of very long flat ropes
 846   // or ropes with a functional representation that isn't practical.
 847   // In that case, we represent the __result as a special case of
 848   // RopeFunction, whose char_producer points back to the rope itself.
 849   // In all cases except repeated substring operations and
 850   // deallocation, we treat the __result as a RopeFunction.
 851   template<class _CharT, class _Alloc>
 852     struct _Rope_RopeSubstring
 853     : public _Rope_RopeFunction<_CharT, _Alloc>,
 854       public char_producer<_CharT>
 855     {
 856     public:
 857       // XXX this whole class should be rewritten.
 858       _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
 859       size_t _M_start;
 860
 861       virtual void
 862       operator()(size_t __start_pos, size_t __req_len,
 863                  _CharT* __buffer)
 864       {
 865         switch(_M_base->_M_tag)
 866           {
 867           case __detail::_S_function:
 868           case __detail::_S_substringfn:
 869             {
 870               char_producer<_CharT>* __fn =
 871                 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
 872               (*__fn)(__start_pos + _M_start, __req_len, __buffer);
 873             }
 874             break;
 875           case __detail::_S_leaf:
 876             {
 877               __GC_CONST _CharT* __s =
 878                 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
 879               uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
 880                                    __buffer);
 881             }
 882             break;
 883           default:
 884             break;
 885           }
 886       }
 887
 888       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
 889         allocator_type;
 890
 891       _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
 892                           size_t __l, const allocator_type& __a)
 893       : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
 894         char_producer<_CharT>(), _M_base(__b), _M_start(__s)
 895       {
 896 #ifndef __GC
 897         _M_base->_M_ref_nonnil();
 898 #endif
 899         this->_M_tag = __detail::_S_substringfn;
 900       }
 901     virtual ~_Rope_RopeSubstring() throw()
 902       {
 903 #ifndef __GC
 904         _M_base->_M_unref_nonnil();
 905         // _M_free_c_string();  -- done by parent class
 906 #endif
 907       }
 908     };
 909
 910   // Self-destructing pointers to Rope_rep.
 911   // These are not conventional smart pointers.  Their
 912   // only purpose in life is to ensure that unref is called
 913   // on the pointer either at normal exit or if an exception
 914   // is raised.  It is the caller's responsibility to
 915   // adjust reference counts when these pointers are initialized
 916   // or assigned to.  (This convention significantly reduces
 917   // the number of potentially expensive reference count
 918   // updates.)
 919 #ifndef __GC
 920   template<class _CharT, class _Alloc>
 921     struct _Rope_self_destruct_ptr
 922     {
 923       _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
 924
 925       ~_Rope_self_destruct_ptr()
 926       { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
 927 #ifdef __EXCEPTIONS
 928       _Rope_self_destruct_ptr() : _M_ptr(0) { };
 929 #else
 930       _Rope_self_destruct_ptr() { };
 931 #endif
 932       _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
 933       : _M_ptr(__p) { }
 934
 935       _Rope_RopeRep<_CharT, _Alloc>&
 936       operator*()
 937       { return *_M_ptr; }
 938
 939       _Rope_RopeRep<_CharT, _Alloc>*
 940       operator->()
 941       { return _M_ptr; }
 942
 943       operator _Rope_RopeRep<_CharT, _Alloc>*()
 944       { return _M_ptr; }
 945
 946       _Rope_self_destruct_ptr&
 947       operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
 948       { _M_ptr = __x; return *this; }
 949     };
 950 #endif
 951
 952   // Dereferencing a nonconst iterator has to return something
 953   // that behaves almost like a reference.  It's not possible to
 954   // return an actual reference since assignment requires extra
 955   // work.  And we would get into the same problems as with the
 956   // CD2 version of basic_string.
 957   template<class _CharT, class _Alloc>
 958     class _Rope_char_ref_proxy
 959     {
 960       friend class rope<_CharT, _Alloc>;
 961       friend class _Rope_iterator<_CharT, _Alloc>;
 962       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
 963 #ifdef __GC
 964       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
 965 #else
 966       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
 967 #endif
 968       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
 969       typedef rope<_CharT, _Alloc> _My_rope;
 970       size_t _M_pos;
 971       _CharT _M_current;
 972       bool _M_current_valid;
 973       _My_rope* _M_root;     // The whole rope.
 974     public:
 975       _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
 976       :  _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
 977
 978       _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
 979       : _M_pos(__x._M_pos), _M_current(__x._M_current),
 980         _M_current_valid(false), _M_root(__x._M_root) { }
 981
 982       // Don't preserve cache if the reference can outlive the
 983       // expression.  We claim that's not possible without calling
 984       // a copy constructor or generating reference to a proxy
 985       // reference.  We declare the latter to have undefined semantics.
 986       _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
 987       : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
 988
 989       inline operator _CharT () const;
 990
 991       _Rope_char_ref_proxy&
 992       operator=(_CharT __c);
 993
 994       _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
 995
 996       _Rope_char_ref_proxy&
 997       operator=(const _Rope_char_ref_proxy& __c)
 998       { return operator=((_CharT)__c); }
 999     };
1000
1001   template<class _CharT, class __Alloc>
1002     inline void
1003     swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
1004          _Rope_char_ref_proxy <_CharT, __Alloc > __b)
1005     {
1006       _CharT __tmp = __a;
1007       __a = __b;
1008       __b = __tmp;
1009     }
1010
1011   template<class _CharT, class _Alloc>
1012     class _Rope_char_ptr_proxy
1013     {
1014       // XXX this class should be rewritten.
1015       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1016       size_t _M_pos;
1017       rope<_CharT,_Alloc>* _M_root;     // The whole rope.
1018     public:
1019       _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
1020       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1021
1022       _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
1023       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1024
1025       _Rope_char_ptr_proxy() { }
1026
1027       _Rope_char_ptr_proxy(_CharT* __x)
1028       : _M_root(0), _M_pos(0) { }
1029
1030       _Rope_char_ptr_proxy&
1031       operator=(const _Rope_char_ptr_proxy& __x)
1032       {
1033         _M_pos = __x._M_pos;
1034         _M_root = __x._M_root;
1035         return *this;
1036       }
1037
1038       template<class _CharT2, class _Alloc2>
1039         friend bool
1040         operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
1041                    const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
1042
1043       _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
1044       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
1045     };
1046
1047   // Rope iterators:
1048   // Unlike in the C version, we cache only part of the stack
1049   // for rope iterators, since they must be efficiently copyable.
1050   // When we run out of cache, we have to reconstruct the iterator
1051   // value.
1052   // Pointers from iterators are not included in reference counts.
1053   // Iterators are assumed to be thread private.  Ropes can
1054   // be shared.
1055
1056   template<class _CharT, class _Alloc>
1057     class _Rope_iterator_base
1058     : public std::iterator<std::random_access_iterator_tag, _CharT>
1059     {
1060       friend class rope<_CharT, _Alloc>;
1061     public:
1062       typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround
1063       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1064       // Borland doesn't want this to be protected.
1065     protected:
1066       enum { _S_path_cache_len = 4 }; // Must be <= 9.
1067       enum { _S_iterator_buf_len = 15 };
1068       size_t _M_current_pos;
1069       _RopeRep* _M_root;     // The whole rope.
1070       size_t _M_leaf_pos;    // Starting position for current leaf
1071       __GC_CONST _CharT* _M_buf_start;
1072                              // Buffer possibly
1073                              // containing current char.
1074       __GC_CONST _CharT* _M_buf_ptr;
1075                              // Pointer to current char in buffer.
1076                              // != 0 ==> buffer valid.
1077       __GC_CONST _CharT* _M_buf_end;
1078                              // One past __last valid char in buffer.
1079       // What follows is the path cache.  We go out of our
1080       // way to make this compact.
1081       // Path_end contains the bottom section of the path from
1082       // the root to the current leaf.
1083       const _RopeRep* _M_path_end[_S_path_cache_len];
1084       int _M_leaf_index;     // Last valid __pos in path_end;
1085                              // _M_path_end[0] ... _M_path_end[leaf_index-1]
1086                              // point to concatenation nodes.
1087       unsigned char _M_path_directions;
1088                           // (path_directions >> __i) & 1 is 1
1089                           // iff we got from _M_path_end[leaf_index - __i - 1]
1090                           // to _M_path_end[leaf_index - __i] by going to the
1091                           // __right. Assumes path_cache_len <= 9.
1092       _CharT _M_tmp_buf[_S_iterator_buf_len];
1093                         // Short buffer for surrounding chars.
1094                         // This is useful primarily for
1095                         // RopeFunctions.  We put the buffer
1096                         // here to avoid locking in the
1097                         // multithreaded case.
1098       // The cached path is generally assumed to be valid
1099       // only if the buffer is valid.
1100       static void _S_setbuf(_Rope_iterator_base& __x);
1101                                         // Set buffer contents given
1102                                         // path cache.
1103       static void _S_setcache(_Rope_iterator_base& __x);
1104                                         // Set buffer contents and
1105                                         // path cache.
1106       static void _S_setcache_for_incr(_Rope_iterator_base& __x);
1107                                         // As above, but assumes path
1108                                         // cache is valid for previous posn.
1109       _Rope_iterator_base() { }
1110
1111       _Rope_iterator_base(_RopeRep* __root, size_t __pos)
1112       : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
1113
1114       void _M_incr(size_t __n);
1115       void _M_decr(size_t __n);
1116     public:
1117       size_t
1118       index() const
1119       { return _M_current_pos; }
1120
1121       _Rope_iterator_base(const _Rope_iterator_base& __x)
1122       {
1123         if (0 != __x._M_buf_ptr)
1124           *this = __x;
1125         else
1126           {
1127             _M_current_pos = __x._M_current_pos;
1128             _M_root = __x._M_root;
1129             _M_buf_ptr = 0;
1130           }
1131       }
1132     };
1133
1134   template<class _CharT, class _Alloc>
1135     class _Rope_iterator;
1136
1137   template<class _CharT, class _Alloc>
1138     class _Rope_const_iterator
1139     : public _Rope_iterator_base<_CharT, _Alloc>
1140     {
1141       friend class rope<_CharT, _Alloc>;
1142     protected:
1143       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1144       // The one from the base class may not be directly visible.
1145       _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
1146       : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
1147                                             __pos)
1148                    // Only nonconst iterators modify root ref count
1149       { }
1150   public:
1151       typedef _CharT reference;   // Really a value.  Returning a reference
1152                                   // Would be a mess, since it would have
1153                                   // to be included in refcount.
1154       typedef const _CharT* pointer;
1155
1156     public:
1157       _Rope_const_iterator() { };
1158
1159       _Rope_const_iterator(const _Rope_const_iterator& __x)
1160       : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
1161
1162       _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
1163
1164       _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
1165       : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
1166
1167       _Rope_const_iterator&
1168       operator=(const _Rope_const_iterator& __x)
1169       {
1170         if (0 != __x._M_buf_ptr)
1171           *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1172         else
1173           {
1174             this->_M_current_pos = __x._M_current_pos;
1175             this->_M_root = __x._M_root;
1176             this->_M_buf_ptr = 0;
1177           }
1178         return(*this);
1179       }
1180
1181       reference
1182       operator*()
1183       {
1184         if (0 == this->_M_buf_ptr)
1185           this->_S_setcache(*this);
1186         return *this->_M_buf_ptr;
1187       }
1188
1189       // Without this const version, Rope iterators do not meet the
1190       // requirements of an Input Iterator.
1191       reference
1192       operator*() const
1193       {
1194         return *const_cast<_Rope_const_iterator&>(*this);
1195       }
1196
1197       _Rope_const_iterator&
1198       operator++()
1199       {
1200         __GC_CONST _CharT* __next;
1201         if (0 != this->_M_buf_ptr
1202             && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
1203           {
1204             this->_M_buf_ptr = __next;
1205             ++this->_M_current_pos;
1206           }
1207         else
1208           this->_M_incr(1);
1209         return *this;
1210       }
1211
1212       _Rope_const_iterator&
1213       operator+=(ptrdiff_t __n)
1214       {
1215         if (__n >= 0)
1216           this->_M_incr(__n);
1217         else
1218           this->_M_decr(-__n);
1219         return *this;
1220       }
1221
1222       _Rope_const_iterator&
1223       operator--()
1224       {
1225         this->_M_decr(1);
1226         return *this;
1227       }
1228
1229       _Rope_const_iterator&
1230       operator-=(ptrdiff_t __n)
1231       {
1232         if (__n >= 0)
1233           this->_M_decr(__n);
1234         else
1235           this->_M_incr(-__n);
1236         return *this;
1237       }
1238
1239       _Rope_const_iterator
1240       operator++(int)
1241       {
1242         size_t __old_pos = this->_M_current_pos;
1243         this->_M_incr(1);
1244         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1245         // This makes a subsequent dereference expensive.
1246         // Perhaps we should instead copy the iterator
1247         // if it has a valid cache?
1248       }
1249
1250       _Rope_const_iterator
1251       operator--(int)
1252       {
1253         size_t __old_pos = this->_M_current_pos;
1254         this->_M_decr(1);
1255         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1256       }
1257
1258       template<class _CharT2, class _Alloc2>
1259         friend _Rope_const_iterator<_CharT2, _Alloc2>
1260         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1261                   ptrdiff_t __n);
1262
1263       template<class _CharT2, class _Alloc2>
1264         friend _Rope_const_iterator<_CharT2, _Alloc2>
1265         operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1266                   ptrdiff_t __n);
1267
1268       template<class _CharT2, class _Alloc2>
1269         friend _Rope_const_iterator<_CharT2, _Alloc2>
1270         operator+(ptrdiff_t __n,
1271                   const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
1272
1273       reference
1274       operator[](size_t __n)
1275       { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
1276                                               this->_M_current_pos + __n); }
1277
1278       template<class _CharT2, class _Alloc2>
1279         friend bool
1280         operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1281                    const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1282
1283       template<class _CharT2, class _Alloc2>
1284         friend bool
1285         operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1286                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1287
1288       template<class _CharT2, class _Alloc2>
1289         friend ptrdiff_t
1290         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1291                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1292     };
1293
1294   template<class _CharT, class _Alloc>
1295     class _Rope_iterator
1296     : public _Rope_iterator_base<_CharT, _Alloc>
1297     {
1298       friend class rope<_CharT, _Alloc>;
1299     protected:
1300       typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
1301       rope<_CharT, _Alloc>* _M_root_rope;
1302
1303       // root is treated as a cached version of this, and is used to
1304       // detect changes to the underlying rope.
1305
1306       // Root is included in the reference count.  This is necessary
1307       // so that we can detect changes reliably.  Unfortunately, it
1308       // requires careful bookkeeping for the nonGC case.
1309       _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
1310       : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
1311         _M_root_rope(__r)
1312       { _RopeRep::_S_ref(this->_M_root);
1313         if (!(__r -> empty()))
1314           this->_S_setcache(*this);
1315       }
1316
1317       void _M_check();
1318     public:
1319       typedef _Rope_char_ref_proxy<_CharT, _Alloc>  reference;
1320       typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
1321
1322       rope<_CharT, _Alloc>&
1323       container()
1324       { return *_M_root_rope; }
1325
1326       _Rope_iterator()
1327       {
1328         this->_M_root = 0;  // Needed for reference counting.
1329       };
1330
1331       _Rope_iterator(const _Rope_iterator& __x)
1332       : _Rope_iterator_base<_CharT, _Alloc>(__x)
1333       {
1334         _M_root_rope = __x._M_root_rope;
1335         _RopeRep::_S_ref(this->_M_root);
1336       }
1337
1338       _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
1339
1340       ~_Rope_iterator()
1341       { _RopeRep::_S_unref(this->_M_root); }
1342
1343       _Rope_iterator&
1344       operator=(const _Rope_iterator& __x)
1345       {
1346         _RopeRep* __old = this->_M_root;
1347
1348         _RopeRep::_S_ref(__x._M_root);
1349         if (0 != __x._M_buf_ptr)
1350           {
1351             _M_root_rope = __x._M_root_rope;
1352             *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1353           }
1354         else
1355           {
1356             this->_M_current_pos = __x._M_current_pos;
1357             this->_M_root = __x._M_root;
1358             _M_root_rope = __x._M_root_rope;
1359             this->_M_buf_ptr = 0;
1360           }
1361         _RopeRep::_S_unref(__old);
1362         return(*this);
1363       }
1364
1365       reference
1366       operator*()
1367       {
1368         _M_check();
1369         if (0 == this->_M_buf_ptr)
1370           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1371                                                       this->_M_current_pos);
1372         else
1373           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1374                                                       this->_M_current_pos,
1375                                                       *this->_M_buf_ptr);
1376       }
1377
1378       // See above comment.
1379       reference
1380       operator*() const
1381       {
1382         return *const_cast<_Rope_iterator&>(*this);
1383       }
1384
1385       _Rope_iterator&
1386       operator++()
1387       {
1388         this->_M_incr(1);
1389         return *this;
1390       }
1391
1392       _Rope_iterator&
1393       operator+=(ptrdiff_t __n)
1394       {
1395         if (__n >= 0)
1396           this->_M_incr(__n);
1397         else
1398           this->_M_decr(-__n);
1399         return *this;
1400       }
1401
1402       _Rope_iterator&
1403       operator--()
1404       {
1405         this->_M_decr(1);
1406         return *this;
1407       }
1408
1409       _Rope_iterator&
1410       operator-=(ptrdiff_t __n)
1411       {
1412         if (__n >= 0)
1413           this->_M_decr(__n);
1414         else
1415           this->_M_incr(-__n);
1416         return *this;
1417       }
1418
1419       _Rope_iterator
1420       operator++(int)
1421       {
1422         size_t __old_pos = this->_M_current_pos;
1423         this->_M_incr(1);
1424         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1425       }
1426
1427       _Rope_iterator
1428       operator--(int)
1429       {
1430         size_t __old_pos = this->_M_current_pos;
1431         this->_M_decr(1);
1432         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1433       }
1434
1435       reference
1436       operator[](ptrdiff_t __n)
1437       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1438                                                     this->_M_current_pos
1439                                                     + __n); }
1440
1441       template<class _CharT2, class _Alloc2>
1442         friend bool
1443         operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1444                    const _Rope_iterator<_CharT2, _Alloc2>& __y);
1445
1446       template<class _CharT2, class _Alloc2>
1447         friend bool
1448         operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1449                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
1450
1451       template<class _CharT2, class _Alloc2>
1452         friend ptrdiff_t
1453         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1454                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
1455
1456       template<class _CharT2, class _Alloc2>
1457         friend _Rope_iterator<_CharT2, _Alloc2>
1458         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1459
1460       template<class _CharT2, class _Alloc2>
1461         friend _Rope_iterator<_CharT2, _Alloc2>
1462         operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1463
1464       template<class _CharT2, class _Alloc2>
1465         friend _Rope_iterator<_CharT2, _Alloc2>
1466         operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
1467     };
1468
1469
1470   template <class _CharT, class _Alloc>
1471     struct _Rope_base
1472     : public _Alloc
1473     {
1474       typedef _Alloc allocator_type;
1475
1476       allocator_type
1477       get_allocator() const
1478       { return *static_cast<const _Alloc*>(this); }
1479
1480       allocator_type&
1481       _M_get_allocator()
1482       { return *static_cast<_Alloc*>(this); }
1483
1484       const allocator_type&
1485       _M_get_allocator() const
1486       { return *static_cast<const _Alloc*>(this); }
1487
1488       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1489       // The one in _Base may not be visible due to template rules.
1490
1491       _Rope_base(_RopeRep* __t, const allocator_type&)
1492       : _M_tree_ptr(__t) { }
1493
1494       _Rope_base(const allocator_type&) { }
1495
1496       // The only data member of a rope:
1497       _RopeRep *_M_tree_ptr;
1498
1499 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1500         typedef typename \
1501           _Alloc::template rebind<_Tp>::other __name##Alloc; \
1502         static _Tp* __name##_allocate(size_t __n) \
1503           { return __name##Alloc().allocate(__n); } \
1504         static void __name##_deallocate(_Tp *__p, size_t __n) \
1505           { __name##Alloc().deallocate(__p, __n); }
1506       __ROPE_DEFINE_ALLOCS(_Alloc)
1507 #undef __ROPE_DEFINE_ALLOC
1508
1509         protected:
1510       _Rope_base&
1511       operator=(const _Rope_base&);
1512
1513       _Rope_base(const _Rope_base&);
1514     };
1515
1516   /**
1517    *  This is an SGI extension.
1518    *  @ingroup SGIextensions
1519    *  @doctodo
1520    */
1521   template <class _CharT, class _Alloc>
1522     class rope : public _Rope_base<_CharT, _Alloc>
1523     {
1524     public:
1525       typedef _CharT value_type;
1526       typedef ptrdiff_t difference_type;
1527       typedef size_t size_type;
1528       typedef _CharT const_reference;
1529       typedef const _CharT* const_pointer;
1530       typedef _Rope_iterator<_CharT, _Alloc> iterator;
1531       typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
1532       typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
1533       typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
1534
1535       friend class _Rope_iterator<_CharT, _Alloc>;
1536       friend class _Rope_const_iterator<_CharT, _Alloc>;
1537       friend struct _Rope_RopeRep<_CharT, _Alloc>;
1538       friend class _Rope_iterator_base<_CharT, _Alloc>;
1539       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
1540       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1541       friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
1542
1543     protected:
1544       typedef _Rope_base<_CharT, _Alloc> _Base;
1545       typedef typename _Base::allocator_type allocator_type;
1546       using _Base::_M_tree_ptr;
1547       using _Base::get_allocator;
1548       using _Base::_M_get_allocator;
1549       typedef __GC_CONST _CharT* _Cstrptr;
1550
1551       static _CharT _S_empty_c_str[1];
1552
1553       static bool
1554       _S_is0(_CharT __c)
1555       { return __c == _S_eos((_CharT*)0); }
1556
1557       enum { _S_copy_max = 23 };
1558                 // For strings shorter than _S_copy_max, we copy to
1559                 // concatenate.
1560
1561       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1562       typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
1563       typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
1564       typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
1565       typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
1566
1567       // Retrieve a character at the indicated position.
1568       static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
1569
1570 #ifndef __GC
1571       // Obtain a pointer to the character at the indicated position.
1572       // The pointer can be used to change the character.
1573       // If such a pointer cannot be produced, as is frequently the
1574       // case, 0 is returned instead.
1575       // (Returns nonzero only if all nodes in the path have a refcount
1576       // of 1.)
1577       static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
1578 #endif
1579
1580       static bool
1581       _S_apply_to_pieces(// should be template parameter
1582                          _Rope_char_consumer<_CharT>& __c,
1583                          const _RopeRep* __r,
1584                          size_t __begin, size_t __end);
1585                          // begin and end are assumed to be in range.
1586
1587 #ifndef __GC
1588       static void
1589       _S_unref(_RopeRep* __t)
1590       { _RopeRep::_S_unref(__t); }
1591
1592       static void
1593       _S_ref(_RopeRep* __t)
1594       { _RopeRep::_S_ref(__t); }
1595
1596 #else /* __GC */
1597       static void _S_unref(_RopeRep*) { }
1598       static void _S_ref(_RopeRep*) { }
1599 #endif
1600
1601 #ifdef __GC
1602       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
1603 #else
1604       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
1605 #endif
1606
1607       // _Result is counted in refcount.
1608       static _RopeRep* _S_substring(_RopeRep* __base,
1609                                     size_t __start, size_t __endp1);
1610
1611       static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
1612                                            const _CharT* __iter, size_t __slen);
1613       // Concatenate rope and char ptr, copying __s.
1614       // Should really take an arbitrary iterator.
1615       // Result is counted in refcount.
1616       static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
1617                                                  const _CharT* __iter,
1618                                                  size_t __slen)
1619         // As above, but one reference to __r is about to be
1620         // destroyed.  Thus the pieces may be recycled if all
1621         // relevant reference counts are 1.
1622 #ifdef __GC
1623         // We can't really do anything since refcounts are unavailable.
1624       { return _S_concat_char_iter(__r, __iter, __slen); }
1625 #else
1626       ;
1627 #endif
1628
1629       static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
1630       // General concatenation on _RopeRep.  _Result
1631       // has refcount of 1.  Adjusts argument refcounts.
1632
1633    public:
1634       void
1635       apply_to_pieces(size_t __begin, size_t __end,
1636                       _Rope_char_consumer<_CharT>& __c) const
1637       { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
1638
1639    protected:
1640
1641       static size_t
1642       _S_rounded_up_size(size_t __n)
1643       { return _RopeLeaf::_S_rounded_up_size(__n); }
1644
1645       static size_t
1646       _S_allocated_capacity(size_t __n)
1647       {
1648         if (_S_is_basic_char_type((_CharT*)0))
1649           return _S_rounded_up_size(__n) - 1;
1650         else
1651           return _S_rounded_up_size(__n);
1652
1653       }
1654
1655       // Allocate and construct a RopeLeaf using the supplied allocator
1656       // Takes ownership of s instead of copying.
1657       static _RopeLeaf*
1658       _S_new_RopeLeaf(__GC_CONST _CharT *__s,
1659                       size_t __size, allocator_type& __a)
1660       {
1661         _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
1662         return new(__space) _RopeLeaf(__s, __size, __a);
1663       }
1664
1665       static _RopeConcatenation*
1666       _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
1667                                allocator_type& __a)
1668       {
1669         _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
1670         return new(__space) _RopeConcatenation(__left, __right, __a);
1671       }
1672
1673       static _RopeFunction*
1674       _S_new_RopeFunction(char_producer<_CharT>* __f,
1675                           size_t __size, bool __d, allocator_type& __a)
1676       {
1677         _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
1678         return new(__space) _RopeFunction(__f, __size, __d, __a);
1679       }
1680
1681       static _RopeSubstring*
1682       _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
1683                            size_t __l, allocator_type& __a)
1684       {
1685         _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
1686         return new(__space) _RopeSubstring(__b, __s, __l, __a);
1687       }
1688
1689       static _RopeLeaf*
1690       _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
1691                                         size_t __size, allocator_type& __a)
1692 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1693                 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1694       {
1695         if (0 == __size)
1696           return 0;
1697         _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
1698
1699         __uninitialized_copy_n_a(__s, __size, __buf, __a);
1700         _S_cond_store_eos(__buf[__size]);
1701         __try
1702           { return _S_new_RopeLeaf(__buf, __size, __a); }
1703         __catch(...)
1704           {
1705             _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
1706             __throw_exception_again;
1707           }
1708       }
1709
1710       // Concatenation of nonempty strings.
1711       // Always builds a concatenation node.
1712       // Rebalances if the result is too deep.
1713       // Result has refcount 1.
1714       // Does not increment left and right ref counts even though
1715       // they are referenced.
1716       static _RopeRep*
1717       _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
1718
1719       // Concatenation helper functions
1720       static _RopeLeaf*
1721       _S_leaf_concat_char_iter(_RopeLeaf* __r,
1722                                const _CharT* __iter, size_t __slen);
1723       // Concatenate by copying leaf.
1724       // should take an arbitrary iterator
1725       // result has refcount 1.
1726 #ifndef __GC
1727       static _RopeLeaf*
1728       _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
1729                                      const _CharT* __iter, size_t __slen);
1730       // A version that potentially clobbers __r if __r->_M_ref_count == 1.
1731 #endif
1732
1733     private:
1734
1735       static size_t _S_char_ptr_len(const _CharT* __s);
1736       // slightly generalized strlen
1737
1738       rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
1739       : _Base(__t, __a) { }
1740
1741
1742       // Copy __r to the _CharT buffer.
1743       // Returns __buffer + __r->_M_size.
1744       // Assumes that buffer is uninitialized.
1745       static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
1746
1747       // Again, with explicit starting position and length.
1748       // Assumes that buffer is uninitialized.
1749       static _CharT* _S_flatten(_RopeRep* __r,
1750                                 size_t __start, size_t __len,
1751                                 _CharT* __buffer);
1752
1753       static const unsigned long
1754       _S_min_len[__detail::_S_max_rope_depth + 1];
1755
1756       static bool
1757       _S_is_balanced(_RopeRep* __r)
1758       { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
1759
1760       static bool
1761       _S_is_almost_balanced(_RopeRep* __r)
1762       { return (__r->_M_depth == 0
1763                 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
1764
1765       static bool
1766       _S_is_roughly_balanced(_RopeRep* __r)
1767       { return (__r->_M_depth <= 1
1768                 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
1769
1770       // Assumes the result is not empty.
1771       static _RopeRep*
1772       _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
1773       {
1774         _RopeRep* __result = _S_concat(__left, __right);
1775         if (_S_is_balanced(__result))
1776           __result->_M_is_balanced = true;
1777         return __result;
1778       }
1779
1780       // The basic rebalancing operation.  Logically copies the
1781       // rope.  The result has refcount of 1.  The client will
1782       // usually decrement the reference count of __r.
1783       // The result is within height 2 of balanced by the above
1784       // definition.
1785       static _RopeRep* _S_balance(_RopeRep* __r);
1786
1787       // Add all unbalanced subtrees to the forest of balanced trees.
1788       // Used only by balance.
1789       static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
1790
1791       // Add __r to forest, assuming __r is already balanced.
1792       static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
1793
1794       // Print to stdout, exposing structure
1795       static void _S_dump(_RopeRep* __r, int __indent = 0);
1796
1797       // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
1798       static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
1799
1800     public:
1801       bool
1802       empty() const
1803       { return 0 == this->_M_tree_ptr; }
1804
1805       // Comparison member function.  This is public only for those
1806       // clients that need a ternary comparison.  Others
1807       // should use the comparison operators below.
1808       int
1809       compare(const rope& __y) const
1810       { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
1811
1812       rope(const _CharT* __s, const allocator_type& __a = allocator_type())
1813       : _Base(__a)
1814       {
1815         this->_M_tree_ptr =
1816           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
1817                                            _M_get_allocator());
1818       }
1819
1820       rope(const _CharT* __s, size_t __len,
1821            const allocator_type& __a = allocator_type())
1822       : _Base(__a)
1823       {
1824         this->_M_tree_ptr =
1825           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
1826       }
1827
1828       // Should perhaps be templatized with respect to the iterator type
1829       // and use Sequence_buffer.  (It should perhaps use sequence_buffer
1830       // even now.)
1831       rope(const _CharT* __s, const _CharT* __e,
1832            const allocator_type& __a = allocator_type())
1833       : _Base(__a)
1834       {
1835         this->_M_tree_ptr =
1836           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
1837       }
1838
1839       rope(const const_iterator& __s, const const_iterator& __e,
1840            const allocator_type& __a = allocator_type())
1841       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1842                            __e._M_current_pos), __a)
1843       { }
1844
1845       rope(const iterator& __s, const iterator& __e,
1846            const allocator_type& __a = allocator_type())
1847       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1848                            __e._M_current_pos), __a)
1849       { }
1850
1851       rope(_CharT __c, const allocator_type& __a = allocator_type())
1852       : _Base(__a)
1853       {
1854         _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
1855
1856         _M_get_allocator().construct(__buf, __c);
1857         __try
1858           {
1859             this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
1860                                                 _M_get_allocator());
1861           }
1862         __catch(...)
1863           {
1864             _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
1865             __throw_exception_again;
1866           }
1867       }
1868
1869       rope(size_t __n, _CharT __c,
1870            const allocator_type& __a = allocator_type());
1871
1872       rope(const allocator_type& __a = allocator_type())
1873       : _Base(0, __a) { }
1874
1875       // Construct a rope from a function that can compute its members
1876       rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
1877            const allocator_type& __a = allocator_type())
1878       : _Base(__a)
1879       {
1880         this->_M_tree_ptr = (0 == __len) ?
1881           0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
1882       }
1883
1884       rope(const rope& __x, const allocator_type& __a = allocator_type())
1885       : _Base(__x._M_tree_ptr, __a)
1886       { _S_ref(this->_M_tree_ptr); }
1887
1888       ~rope() throw()
1889       { _S_unref(this->_M_tree_ptr); }
1890
1891       rope&
1892       operator=(const rope& __x)
1893       {
1894         _RopeRep* __old = this->_M_tree_ptr;
1895         this->_M_tree_ptr = __x._M_tree_ptr;
1896         _S_ref(this->_M_tree_ptr);
1897         _S_unref(__old);
1898         return *this;
1899       }
1900
1901       void
1902       clear()
1903       {
1904         _S_unref(this->_M_tree_ptr);
1905         this->_M_tree_ptr = 0;
1906       }
1907
1908       void
1909       push_back(_CharT __x)
1910       {
1911         _RopeRep* __old = this->_M_tree_ptr;
1912         this->_M_tree_ptr
1913           = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
1914         _S_unref(__old);
1915       }
1916
1917       void
1918       pop_back()
1919       {
1920         _RopeRep* __old = this->_M_tree_ptr;
1921         this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
1922                                          0, this->_M_tree_ptr->_M_size - 1);
1923         _S_unref(__old);
1924       }
1925
1926       _CharT
1927       back() const
1928       { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
1929
1930       void
1931       push_front(_CharT __x)
1932       {
1933         _RopeRep* __old = this->_M_tree_ptr;
1934         _RopeRep* __left =
1935           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
1936         __try
1937           {
1938             this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
1939             _S_unref(__old);
1940             _S_unref(__left);
1941           }
1942         __catch(...)
1943           {
1944             _S_unref(__left);
1945             __throw_exception_again;
1946           }
1947       }
1948
1949       void
1950       pop_front()
1951       {
1952         _RopeRep* __old = this->_M_tree_ptr;
1953         this->_M_tree_ptr
1954           = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
1955         _S_unref(__old);
1956       }
1957
1958       _CharT
1959       front() const
1960       { return _S_fetch(this->_M_tree_ptr, 0); }
1961
1962       void
1963       balance()
1964       {
1965         _RopeRep* __old = this->_M_tree_ptr;
1966         this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
1967         _S_unref(__old);
1968       }
1969
1970       void
1971       copy(_CharT* __buffer) const
1972       {
1973         _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
1974         _S_flatten(this->_M_tree_ptr, __buffer);
1975       }
1976
1977       // This is the copy function from the standard, but
1978       // with the arguments reordered to make it consistent with the
1979       // rest of the interface.
1980       // Note that this guaranteed not to compile if the draft standard
1981       // order is assumed.
1982       size_type
1983       copy(size_type __pos, size_type __n, _CharT* __buffer) const
1984       {
1985         size_t __size = size();
1986         size_t __len = (__pos + __n > __size? __size - __pos : __n);
1987
1988         _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
1989         _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
1990         return __len;
1991       }
1992
1993       // Print to stdout, exposing structure.  May be useful for
1994       // performance debugging.
1995       void
1996       dump()
1997       { _S_dump(this->_M_tree_ptr); }
1998
1999       // Convert to 0 terminated string in new allocated memory.
2000       // Embedded 0s in the input do not terminate the copy.
2001       const _CharT* c_str() const;
2002
2003       // As above, but also use the flattened representation as
2004       // the new rope representation.
2005       const _CharT* replace_with_c_str();
2006
2007       // Reclaim memory for the c_str generated flattened string.
2008       // Intentionally undocumented, since it's hard to say when this
2009       // is safe for multiple threads.
2010       void
2011       delete_c_str ()
2012       {
2013         if (0 == this->_M_tree_ptr)
2014           return;
2015         if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
2016             ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
2017             this->_M_tree_ptr->_M_c_string)
2018           {
2019             // Representation shared
2020             return;
2021           }
2022 #ifndef __GC
2023         this->_M_tree_ptr->_M_free_c_string();
2024 #endif
2025         this->_M_tree_ptr->_M_c_string = 0;
2026       }
2027
2028       _CharT
2029       operator[] (size_type __pos) const
2030       { return _S_fetch(this->_M_tree_ptr, __pos); }
2031
2032       _CharT
2033       at(size_type __pos) const
2034       {
2035         // if (__pos >= size()) throw out_of_range;  // XXX
2036         return (*this)[__pos];
2037       }
2038
2039       const_iterator
2040       begin() const
2041       { return(const_iterator(this->_M_tree_ptr, 0)); }
2042
2043       // An easy way to get a const iterator from a non-const container.
2044       const_iterator
2045       const_begin() const
2046       { return(const_iterator(this->_M_tree_ptr, 0)); }
2047
2048       const_iterator
2049       end() const
2050       { return(const_iterator(this->_M_tree_ptr, size())); }
2051
2052       const_iterator
2053       const_end() const
2054       { return(const_iterator(this->_M_tree_ptr, size())); }
2055
2056       size_type
2057       size() const
2058       { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
2059
2060       size_type
2061       length() const
2062       { return size(); }
2063
2064       size_type
2065       max_size() const
2066       {
2067         return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
2068         //  Guarantees that the result can be sufficiently
2069         //  balanced.  Longer ropes will probably still work,
2070         //  but it's harder to make guarantees.
2071       }
2072
2073       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2074
2075       const_reverse_iterator
2076       rbegin() const
2077       { return const_reverse_iterator(end()); }
2078
2079       const_reverse_iterator
2080       const_rbegin() const
2081       { return const_reverse_iterator(end()); }
2082
2083       const_reverse_iterator
2084       rend() const
2085       { return const_reverse_iterator(begin()); }
2086
2087       const_reverse_iterator
2088       const_rend() const
2089       { return const_reverse_iterator(begin()); }
2090
2091       template<class _CharT2, class _Alloc2>
2092         friend rope<_CharT2, _Alloc2>
2093         operator+(const rope<_CharT2, _Alloc2>& __left,
2094                   const rope<_CharT2, _Alloc2>& __right);
2095
2096       template<class _CharT2, class _Alloc2>
2097         friend rope<_CharT2, _Alloc2>
2098         operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
2099
2100       template<class _CharT2, class _Alloc2>
2101         friend rope<_CharT2, _Alloc2>
2102         operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
2103
2104       // The symmetric cases are intentionally omitted, since they're
2105       // presumed to be less common, and we don't handle them as well.
2106
2107       // The following should really be templatized.  The first
2108       // argument should be an input iterator or forward iterator with
2109       // value_type _CharT.
2110       rope&
2111       append(const _CharT* __iter, size_t __n)
2112       {
2113         _RopeRep* __result =
2114           _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
2115         _S_unref(this->_M_tree_ptr);
2116         this->_M_tree_ptr = __result;
2117         return *this;
2118       }
2119
2120       rope&
2121       append(const _CharT* __c_string)
2122       {
2123         size_t __len = _S_char_ptr_len(__c_string);
2124         append(__c_string, __len);
2125         return(*this);
2126       }
2127
2128       rope&
2129       append(const _CharT* __s, const _CharT* __e)
2130       {
2131         _RopeRep* __result =
2132           _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
2133         _S_unref(this->_M_tree_ptr);
2134         this->_M_tree_ptr = __result;
2135         return *this;
2136       }
2137
2138       rope&
2139       append(const_iterator __s, const_iterator __e)
2140       {
2141         _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
2142                                                    __s._M_current_pos,
2143                                                    __e._M_current_pos));
2144         _RopeRep* __result = _S_concat(this->_M_tree_ptr,
2145                                        (_RopeRep*)__appendee);
2146         _S_unref(this->_M_tree_ptr);
2147         this->_M_tree_ptr = __result;
2148         return *this;
2149       }
2150
2151       rope&
2152       append(_CharT __c)
2153       {
2154         _RopeRep* __result =
2155           _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
2156         _S_unref(this->_M_tree_ptr);
2157         this->_M_tree_ptr = __result;
2158         return *this;
2159       }
2160
2161       rope&
2162       append()
2163       { return append(_CharT()); }  // XXX why?
2164
2165       rope&
2166       append(const rope& __y)
2167       {
2168         _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
2169         _S_unref(this->_M_tree_ptr);
2170         this->_M_tree_ptr = __result;
2171         return *this;
2172       }
2173
2174       rope&
2175       append(size_t __n, _CharT __c)
2176       {
2177         rope<_CharT,_Alloc> __last(__n, __c);
2178         return append(__last);
2179       }
2180
2181       void
2182       swap(rope& __b)
2183       {
2184         _RopeRep* __tmp = this->_M_tree_ptr;
2185         this->_M_tree_ptr = __b._M_tree_ptr;
2186         __b._M_tree_ptr = __tmp;
2187       }
2188
2189     protected:
2190       // Result is included in refcount.
2191       static _RopeRep*
2192       replace(_RopeRep* __old, size_t __pos1,
2193               size_t __pos2, _RopeRep* __r)
2194       {
2195         if (0 == __old)
2196           {
2197             _S_ref(__r);
2198             return __r;
2199           }
2200         _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
2201         _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
2202         _RopeRep* __result;
2203
2204         if (0 == __r)
2205           __result = _S_concat(__left, __right);
2206         else
2207           {
2208             _Self_destruct_ptr __left_result(_S_concat(__left, __r));
2209             __result = _S_concat(__left_result, __right);
2210           }
2211         return __result;
2212       }
2213
2214     public:
2215       void
2216       insert(size_t __p, const rope& __r)
2217       {
2218         _RopeRep* __result =
2219           replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
2220         _S_unref(this->_M_tree_ptr);
2221         this->_M_tree_ptr = __result;
2222       }
2223
2224       void
2225       insert(size_t __p, size_t __n, _CharT __c)
2226       {
2227         rope<_CharT,_Alloc> __r(__n,__c);
2228         insert(__p, __r);
2229       }
2230
2231       void
2232       insert(size_t __p, const _CharT* __i, size_t __n)
2233       {
2234         _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
2235         _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
2236                                                 __p, size()));
2237         _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
2238         // _S_ destr_concat_char_iter should be safe here.
2239         // But as it stands it's probably not a win, since __left
2240         // is likely to have additional references.
2241         _RopeRep* __result = _S_concat(__left_result, __right);
2242         _S_unref(this->_M_tree_ptr);
2243         this->_M_tree_ptr = __result;
2244       }
2245
2246       void
2247       insert(size_t __p, const _CharT* __c_string)
2248       { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
2249
2250       void
2251       insert(size_t __p, _CharT __c)
2252       { insert(__p, &__c, 1); }
2253
2254       void
2255       insert(size_t __p)
2256       {
2257         _CharT __c = _CharT();
2258         insert(__p, &__c, 1);
2259       }
2260
2261       void
2262       insert(size_t __p, const _CharT* __i, const _CharT* __j)
2263       {
2264         rope __r(__i, __j);
2265         insert(__p, __r);
2266       }
2267
2268       void
2269       insert(size_t __p, const const_iterator& __i,
2270              const const_iterator& __j)
2271       {
2272         rope __r(__i, __j);
2273         insert(__p, __r);
2274       }
2275
2276       void
2277       insert(size_t __p, const iterator& __i,
2278              const iterator& __j)
2279       {
2280         rope __r(__i, __j);
2281         insert(__p, __r);
2282       }
2283
2284       // (position, length) versions of replace operations:
2285
2286       void
2287       replace(size_t __p, size_t __n, const rope& __r)
2288       {
2289         _RopeRep* __result =
2290           replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
2291         _S_unref(this->_M_tree_ptr);
2292         this->_M_tree_ptr = __result;
2293       }
2294
2295       void
2296       replace(size_t __p, size_t __n,
2297               const _CharT* __i, size_t __i_len)
2298       {
2299         rope __r(__i, __i_len);
2300         replace(__p, __n, __r);
2301       }
2302
2303       void
2304       replace(size_t __p, size_t __n, _CharT __c)
2305       {
2306         rope __r(__c);
2307         replace(__p, __n, __r);
2308       }
2309
2310       void
2311       replace(size_t __p, size_t __n, const _CharT* __c_string)
2312       {
2313         rope __r(__c_string);
2314         replace(__p, __n, __r);
2315       }
2316
2317       void
2318       replace(size_t __p, size_t __n,
2319               const _CharT* __i, const _CharT* __j)
2320       {
2321         rope __r(__i, __j);
2322         replace(__p, __n, __r);
2323       }
2324
2325       void
2326       replace(size_t __p, size_t __n,
2327               const const_iterator& __i, const const_iterator& __j)
2328       {
2329         rope __r(__i, __j);
2330         replace(__p, __n, __r);
2331       }
2332
2333       void
2334       replace(size_t __p, size_t __n,
2335               const iterator& __i, const iterator& __j)
2336       {
2337         rope __r(__i, __j);
2338         replace(__p, __n, __r);
2339       }
2340
2341       // Single character variants:
2342       void
2343       replace(size_t __p, _CharT __c)
2344       {
2345         iterator __i(this, __p);
2346         *__i = __c;
2347       }
2348
2349       void
2350       replace(size_t __p, const rope& __r)
2351       { replace(__p, 1, __r); }
2352
2353       void
2354       replace(size_t __p, const _CharT* __i, size_t __i_len)
2355       { replace(__p, 1, __i, __i_len); }
2356
2357       void
2358       replace(size_t __p, const _CharT* __c_string)
2359       { replace(__p, 1, __c_string); }
2360
2361       void
2362       replace(size_t __p, const _CharT* __i, const _CharT* __j)
2363       { replace(__p, 1, __i, __j); }
2364
2365       void
2366       replace(size_t __p, const const_iterator& __i,
2367               const const_iterator& __j)
2368       { replace(__p, 1, __i, __j); }
2369
2370       void
2371       replace(size_t __p, const iterator& __i,
2372               const iterator& __j)
2373       { replace(__p, 1, __i, __j); }
2374
2375       // Erase, (position, size) variant.
2376       void
2377       erase(size_t __p, size_t __n)
2378       {
2379         _RopeRep* __result = replace(this->_M_tree_ptr, __p,
2380                                      __p + __n, 0);
2381         _S_unref(this->_M_tree_ptr);
2382         this->_M_tree_ptr = __result;
2383       }
2384
2385       // Erase, single character
2386       void
2387       erase(size_t __p)
2388       { erase(__p, __p + 1); }
2389
2390       // Insert, iterator variants.
2391       iterator
2392       insert(const iterator& __p, const rope& __r)
2393       {
2394         insert(__p.index(), __r);
2395         return __p;
2396       }
2397
2398       iterator
2399       insert(const iterator& __p, size_t __n, _CharT __c)
2400       {
2401         insert(__p.index(), __n, __c);
2402         return __p;
2403       }
2404
2405       iterator insert(const iterator& __p, _CharT __c)
2406       {
2407         insert(__p.index(), __c);
2408         return __p;
2409       }
2410
2411       iterator
2412       insert(const iterator& __p )
2413       {
2414         insert(__p.index());
2415         return __p;
2416       }
2417
2418       iterator
2419       insert(const iterator& __p, const _CharT* c_string)
2420       {
2421         insert(__p.index(), c_string);
2422         return __p;
2423       }
2424
2425       iterator
2426       insert(const iterator& __p, const _CharT* __i, size_t __n)
2427       {
2428         insert(__p.index(), __i, __n);
2429         return __p;
2430       }
2431
2432       iterator
2433       insert(const iterator& __p, const _CharT* __i,
2434              const _CharT* __j)
2435       {
2436         insert(__p.index(), __i, __j);
2437         return __p;
2438       }
2439
2440       iterator
2441       insert(const iterator& __p,
2442              const const_iterator& __i, const const_iterator& __j)
2443       {
2444         insert(__p.index(), __i, __j);
2445         return __p;
2446       }
2447
2448       iterator
2449       insert(const iterator& __p,
2450              const iterator& __i, const iterator& __j)
2451       {
2452         insert(__p.index(), __i, __j);
2453         return __p;
2454       }
2455
2456       // Replace, range variants.
2457       void
2458       replace(const iterator& __p, const iterator& __q, const rope& __r)
2459       { replace(__p.index(), __q.index() - __p.index(), __r); }
2460
2461       void
2462       replace(const iterator& __p, const iterator& __q, _CharT __c)
2463       { replace(__p.index(), __q.index() - __p.index(), __c); }
2464
2465       void
2466       replace(const iterator& __p, const iterator& __q,
2467               const _CharT* __c_string)
2468       { replace(__p.index(), __q.index() - __p.index(), __c_string); }
2469
2470       void
2471       replace(const iterator& __p, const iterator& __q,
2472               const _CharT* __i, size_t __n)
2473       { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
2474
2475       void
2476       replace(const iterator& __p, const iterator& __q,
2477               const _CharT* __i, const _CharT* __j)
2478       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2479
2480       void
2481       replace(const iterator& __p, const iterator& __q,
2482               const const_iterator& __i, const const_iterator& __j)
2483       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2484
2485       void
2486       replace(const iterator& __p, const iterator& __q,
2487               const iterator& __i, const iterator& __j)
2488       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2489
2490       // Replace, iterator variants.
2491       void
2492       replace(const iterator& __p, const rope& __r)
2493       { replace(__p.index(), __r); }
2494
2495       void
2496       replace(const iterator& __p, _CharT __c)
2497       { replace(__p.index(), __c); }
2498
2499       void
2500       replace(const iterator& __p, const _CharT* __c_string)
2501       { replace(__p.index(), __c_string); }
2502
2503       void
2504       replace(const iterator& __p, const _CharT* __i, size_t __n)
2505       { replace(__p.index(), __i, __n); }
2506
2507       void
2508       replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
2509       { replace(__p.index(), __i, __j); }
2510
2511       void
2512       replace(const iterator& __p, const_iterator __i, const_iterator __j)
2513       { replace(__p.index(), __i, __j); }
2514
2515       void
2516       replace(const iterator& __p, iterator __i, iterator __j)
2517       { replace(__p.index(), __i, __j); }
2518
2519       // Iterator and range variants of erase
2520       iterator
2521       erase(const iterator& __p, const iterator& __q)
2522       {
2523         size_t __p_index = __p.index();
2524         erase(__p_index, __q.index() - __p_index);
2525         return iterator(this, __p_index);
2526       }
2527
2528       iterator
2529       erase(const iterator& __p)
2530       {
2531         size_t __p_index = __p.index();
2532         erase(__p_index, 1);
2533         return iterator(this, __p_index);
2534       }
2535
2536       rope
2537       substr(size_t __start, size_t __len = 1) const
2538       {
2539         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2540                                                  __start,
2541                                                  __start + __len));
2542       }
2543
2544       rope
2545       substr(iterator __start, iterator __end) const
2546       {
2547         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2548                                                  __start.index(),
2549                                                  __end.index()));
2550       }
2551
2552       rope
2553       substr(iterator __start) const
2554       {
2555         size_t __pos = __start.index();
2556         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2557                                                  __pos, __pos + 1));
2558       }
2559
2560       rope
2561       substr(const_iterator __start, const_iterator __end) const
2562       {
2563         // This might eventually take advantage of the cache in the
2564         // iterator.
2565         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2566                                                  __start.index(),
2567                                                  __end.index()));
2568       }
2569
2570       rope<_CharT, _Alloc>
2571       substr(const_iterator __start)
2572       {
2573         size_t __pos = __start.index();
2574         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2575                                                  __pos, __pos + 1));
2576       }
2577
2578       static const size_type npos;
2579
2580       size_type find(_CharT __c, size_type __pos = 0) const;
2581
2582       size_type
2583       find(const _CharT* __s, size_type __pos = 0) const
2584       {
2585         size_type __result_pos;
2586         const_iterator __result =
2587           std::search(const_begin() + __pos, const_end(),
2588                       __s, __s + _S_char_ptr_len(__s));
2589         __result_pos = __result.index();
2590 #ifndef __STL_OLD_ROPE_SEMANTICS
2591         if (__result_pos == size())
2592           __result_pos = npos;
2593 #endif
2594         return __result_pos;
2595       }
2596
2597       iterator
2598       mutable_begin()
2599       { return(iterator(this, 0)); }
2600
2601       iterator
2602       mutable_end()
2603       { return(iterator(this, size())); }
2604
2605       typedef std::reverse_iterator<iterator> reverse_iterator;
2606
2607       reverse_iterator
2608       mutable_rbegin()
2609       { return reverse_iterator(mutable_end()); }
2610
2611       reverse_iterator
2612       mutable_rend()
2613       { return reverse_iterator(mutable_begin()); }
2614
2615       reference
2616       mutable_reference_at(size_type __pos)
2617       { return reference(this, __pos); }
2618
2619 #ifdef __STD_STUFF
2620       reference
2621       operator[] (size_type __pos)
2622       { return _char_ref_proxy(this, __pos); }
2623
2624       reference
2625       at(size_type __pos)
2626       {
2627         // if (__pos >= size()) throw out_of_range;  // XXX
2628         return (*this)[__pos];
2629       }
2630
2631       void resize(size_type __n, _CharT __c) { }
2632       void resize(size_type __n) { }
2633       void reserve(size_type __res_arg = 0) { }
2634
2635       size_type
2636       capacity() const
2637       { return max_size(); }
2638
2639       // Stuff below this line is dangerous because it's error prone.
2640       // I would really like to get rid of it.
2641       // copy function with funny arg ordering.
2642       size_type
2643       copy(_CharT* __buffer, size_type __n,
2644            size_type __pos = 0) const
2645       { return copy(__pos, __n, __buffer); }
2646
2647       iterator
2648       end()
2649       { return mutable_end(); }
2650
2651       iterator
2652       begin()
2653       { return mutable_begin(); }
2654
2655       reverse_iterator
2656       rend()
2657       { return mutable_rend(); }
2658
2659       reverse_iterator
2660       rbegin()
2661       { return mutable_rbegin(); }
2662
2663 #else
2664       const_iterator
2665       end()
2666       { return const_end(); }
2667
2668       const_iterator
2669       begin()
2670       { return const_begin(); }
2671
2672       const_reverse_iterator
2673       rend()
2674       { return const_rend(); }
2675
2676       const_reverse_iterator
2677       rbegin()
2678       { return const_rbegin(); }
2679
2680 #endif
2681     };
2682
2683   template <class _CharT, class _Alloc>
2684     const typename rope<_CharT, _Alloc>::size_type
2685     rope<_CharT, _Alloc>::npos = (size_type)(-1);
2686
2687   template <class _CharT, class _Alloc>
2688     inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2689                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
2690     { return (__x._M_current_pos == __y._M_current_pos
2691               && __x._M_root == __y._M_root); }
2692
2693   template <class _CharT, class _Alloc>
2694     inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2695                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
2696     { return (__x._M_current_pos < __y._M_current_pos); }
2697
2698   template <class _CharT, class _Alloc>
2699     inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2700                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
2701     { return !(__x == __y); }
2702
2703   template <class _CharT, class _Alloc>
2704     inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2705                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
2706     { return __y < __x; }
2707
2708   template <class _CharT, class _Alloc>
2709     inline bool
2710     operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2711                const _Rope_const_iterator<_CharT, _Alloc>& __y)
2712     { return !(__y < __x); }
2713
2714   template <class _CharT, class _Alloc>
2715     inline bool
2716     operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2717                const _Rope_const_iterator<_CharT, _Alloc>& __y)
2718     { return !(__x < __y); }
2719
2720   template <class _CharT, class _Alloc>
2721     inline ptrdiff_t
2722     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2723               const _Rope_const_iterator<_CharT, _Alloc>& __y)
2724     { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
2725
2726   template <class _CharT, class _Alloc>
2727     inline _Rope_const_iterator<_CharT, _Alloc>
2728     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2729     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2730                                                   __x._M_current_pos - __n); }
2731
2732   template <class _CharT, class _Alloc>
2733     inline _Rope_const_iterator<_CharT, _Alloc>
2734     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2735     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2736                                                   __x._M_current_pos + __n); }
2737
2738   template <class _CharT, class _Alloc>
2739     inline _Rope_const_iterator<_CharT, _Alloc>
2740     operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
2741   { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2742                                                 __x._M_current_pos + __n); }
2743
2744   template <class _CharT, class _Alloc>
2745     inline bool
2746     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
2747                const _Rope_iterator<_CharT, _Alloc>& __y)
2748     {return (__x._M_current_pos == __y._M_current_pos
2749              && __x._M_root_rope == __y._M_root_rope); }
2750
2751   template <class _CharT, class _Alloc>
2752     inline bool
2753     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
2754               const _Rope_iterator<_CharT, _Alloc>& __y)
2755     { return (__x._M_current_pos < __y._M_current_pos); }
2756
2757   template <class _CharT, class _Alloc>
2758     inline bool
2759     operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
2760                const _Rope_iterator<_CharT, _Alloc>& __y)
2761     { return !(__x == __y); }
2762
2763   template <class _CharT, class _Alloc>
2764     inline bool
2765     operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
2766               const _Rope_iterator<_CharT, _Alloc>& __y)
2767     { return __y < __x; }
2768
2769   template <class _CharT, class _Alloc>
2770     inline bool
2771     operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
2772                const _Rope_iterator<_CharT, _Alloc>& __y)
2773     { return !(__y < __x); }
2774
2775   template <class _CharT, class _Alloc>
2776     inline bool
2777     operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
2778                const _Rope_iterator<_CharT, _Alloc>& __y)
2779     { return !(__x < __y); }
2780
2781   template <class _CharT, class _Alloc>
2782     inline ptrdiff_t
2783     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2784               const _Rope_iterator<_CharT, _Alloc>& __y)
2785     { return ((ptrdiff_t)__x._M_current_pos
2786               - (ptrdiff_t)__y._M_current_pos); }
2787
2788   template <class _CharT, class _Alloc>
2789     inline _Rope_iterator<_CharT, _Alloc>
2790     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2791               ptrdiff_t __n)
2792     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2793                                             __x._M_current_pos - __n); }
2794
2795   template <class _CharT, class _Alloc>
2796     inline _Rope_iterator<_CharT, _Alloc>
2797     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2798     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2799                                             __x._M_current_pos + __n); }
2800
2801   template <class _CharT, class _Alloc>
2802     inline _Rope_iterator<_CharT, _Alloc>
2803     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
2804     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2805                                             __x._M_current_pos + __n); }
2806
2807   template <class _CharT, class _Alloc>
2808     inline rope<_CharT, _Alloc>
2809     operator+(const rope<_CharT, _Alloc>& __left,
2810               const rope<_CharT, _Alloc>& __right)
2811     {
2812       // Inlining this should make it possible to keep __left and
2813       // __right in registers.
2814       typedef rope<_CharT, _Alloc> rope_type;
2815       return rope_type(rope_type::_S_concat(__left._M_tree_ptr,
2816                                             __right._M_tree_ptr));
2817     }
2818
2819   template <class _CharT, class _Alloc>
2820     inline rope<_CharT, _Alloc>&
2821     operator+=(rope<_CharT, _Alloc>& __left,
2822                const rope<_CharT, _Alloc>& __right)
2823     {
2824       __left.append(__right);
2825       return __left;
2826     }
2827
2828   template <class _CharT, class _Alloc>
2829     inline rope<_CharT, _Alloc>
2830     operator+(const rope<_CharT, _Alloc>& __left,
2831               const _CharT* __right)
2832     {
2833       typedef rope<_CharT, _Alloc> rope_type;
2834       size_t __rlen = rope_type::_S_char_ptr_len(__right);
2835       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2836                                                       __right, __rlen));
2837     }
2838
2839   template <class _CharT, class _Alloc>
2840     inline rope<_CharT, _Alloc>&
2841     operator+=(rope<_CharT, _Alloc>& __left,
2842                const _CharT* __right)
2843     {
2844       __left.append(__right);
2845       return __left;
2846     }
2847
2848   template <class _CharT, class _Alloc>
2849     inline rope<_CharT, _Alloc>
2850     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
2851     {
2852       typedef rope<_CharT, _Alloc> rope_type;
2853       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2854                                                       &__right, 1));
2855     }
2856
2857   template <class _CharT, class _Alloc>
2858     inline rope<_CharT, _Alloc>&
2859     operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
2860     {
2861       __left.append(__right);
2862       return __left;
2863     }
2864
2865   template <class _CharT, class _Alloc>
2866     bool
2867     operator<(const rope<_CharT, _Alloc>& __left,
2868               const rope<_CharT, _Alloc>& __right)
2869     { return __left.compare(__right) < 0; }
2870
2871   template <class _CharT, class _Alloc>
2872     bool
2873     operator==(const rope<_CharT, _Alloc>& __left,
2874                const rope<_CharT, _Alloc>& __right)
2875     { return __left.compare(__right) == 0; }
2876
2877   template <class _CharT, class _Alloc>
2878     inline bool
2879     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2880                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2881     { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
2882
2883   template <class _CharT, class _Alloc>
2884     inline bool
2885     operator!=(const rope<_CharT, _Alloc>& __x,
2886                const rope<_CharT, _Alloc>& __y)
2887     { return !(__x == __y); }
2888
2889   template <class _CharT, class _Alloc>
2890     inline bool
2891     operator>(const rope<_CharT, _Alloc>& __x,
2892               const rope<_CharT, _Alloc>& __y)
2893     { return __y < __x; }
2894
2895   template <class _CharT, class _Alloc>
2896     inline bool
2897     operator<=(const rope<_CharT, _Alloc>& __x,
2898                const rope<_CharT, _Alloc>& __y)
2899     { return !(__y < __x); }
2900
2901   template <class _CharT, class _Alloc>
2902     inline bool
2903     operator>=(const rope<_CharT, _Alloc>& __x,
2904                const rope<_CharT, _Alloc>& __y)
2905     { return !(__x < __y); }
2906
2907   template <class _CharT, class _Alloc>
2908     inline bool
2909     operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2910                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2911     { return !(__x == __y); }
2912
2913   template<class _CharT, class _Traits, class _Alloc>
2914     std::basic_ostream<_CharT, _Traits>&
2915     operator<<(std::basic_ostream<_CharT, _Traits>& __o,
2916                const rope<_CharT, _Alloc>& __r);
2917
2918   typedef rope<char> crope;
2919   typedef rope<wchar_t> wrope;
2920
2921   inline crope::reference
2922   __mutable_reference_at(crope& __c, size_t __i)
2923   { return __c.mutable_reference_at(__i); }
2924
2925   inline wrope::reference
2926   __mutable_reference_at(wrope& __c, size_t __i)
2927   { return __c.mutable_reference_at(__i); }
2928
2929   template <class _CharT, class _Alloc>
2930     inline void
2931     swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
2932     { __x.swap(__y); }
2933
2934 _GLIBCXX_END_NAMESPACE_VERSION
2935 } // namespace
2936
2937
2938 namespace std _GLIBCXX_VISIBILITY(default)
2939 {
2940 namespace tr1
2941 {
2942 _GLIBCXX_BEGIN_NAMESPACE_VERSION
2943
2944   template<>
2945     struct hash<__gnu_cxx::crope>
2946     {
2947       size_t
2948       operator()(const __gnu_cxx::crope& __str) const
2949       {
2950         size_t __size = __str.size();
2951         if (0 == __size)
2952           return 0;
2953         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2954       }
2955     };
2956
2957
2958   template<>
2959     struct hash<__gnu_cxx::wrope>
2960     {
2961       size_t
2962       operator()(const __gnu_cxx::wrope& __str) const
2963       {
2964         size_t __size = __str.size();
2965         if (0 == __size)
2966           return 0;
2967         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2968       }
2969     };
2970
2971 _GLIBCXX_END_NAMESPACE_VERSION
2972 } // namespace tr1
2973 } // namespace std
2974
2975 # include <ext/ropeimpl.h>
2976
2977 #endif