libstdc++-v3/include/ext/rope

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