libstdc++
rope
Go to the documentation of this file.
00001 // SGI's rope class -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  * Copyright (c) 1997
00027  * Silicon Graphics Computer Systems, Inc.
00028  *
00029  * Permission to use, copy, modify, distribute and sell this software
00030  * and its documentation for any purpose is hereby granted without fee,
00031  * provided that the above copyright notice appear in all copies and
00032  * that both that copyright notice and this permission notice appear
00033  * in supporting documentation.  Silicon Graphics makes no
00034  * representations about the suitability of this software for any
00035  * purpose.  It is provided "as is" without express or implied warranty.
00036  */
00037 
00038 /** @file ext/rope
00039  *  This file is a GNU extension to the Standard C++ Library (possibly
00040  *  containing extensions from the HP/SGI STL subset). 
00041  */
00042 
00043 #ifndef _ROPE
00044 #define _ROPE 1
00045 
00046 #pragma GCC system_header
00047 
00048 #include <algorithm>
00049 #include <iosfwd>
00050 #include <bits/stl_construct.h>
00051 #include <bits/stl_uninitialized.h>
00052 #include <bits/stl_function.h>
00053 #include <bits/stl_numeric.h>
00054 #include <bits/allocator.h>
00055 #include <bits/gthr.h>
00056 #include <tr1/functional>
00057 
00058 # ifdef __GC
00059 #   define __GC_CONST const
00060 # else
00061 #   define __GC_CONST   // constant except for deallocation
00062 # endif
00063 
00064 #include <ext/memory> // For uninitialized_copy_n
00065 
00066 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00067 {
00068   namespace __detail
00069   {
00070     enum { _S_max_rope_depth = 45 };
00071     enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
00072   } // namespace __detail
00073 
00074   using std::size_t;
00075   using std::ptrdiff_t;
00076   using std::allocator;
00077   using std::_Destroy;
00078 
00079 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00080 
00081   // See libstdc++/36832.
00082   template<typename _ForwardIterator, typename _Allocator>
00083     void
00084     _Destroy_const(_ForwardIterator __first,
00085                    _ForwardIterator __last, _Allocator __alloc)
00086     {
00087       for (; __first != __last; ++__first)
00088         __alloc.destroy(&*__first);
00089     }
00090 
00091   template<typename _ForwardIterator, typename _Tp>
00092     inline void
00093     _Destroy_const(_ForwardIterator __first,
00094                    _ForwardIterator __last, allocator<_Tp>)
00095     { _Destroy(__first, __last); }
00096 
00097   // The _S_eos function is used for those functions that
00098   // convert to/from C-like strings to detect the end of the string.
00099   
00100   // The end-of-C-string character.
00101   // This is what the draft standard says it should be.
00102   template <class _CharT>
00103     inline _CharT
00104     _S_eos(_CharT*)
00105     { return _CharT(); }
00106 
00107   // Test for basic character types.
00108   // For basic character types leaves having a trailing eos.
00109   template <class _CharT>
00110     inline bool
00111     _S_is_basic_char_type(_CharT*)
00112     { return false; }
00113   
00114   template <class _CharT>
00115     inline bool
00116     _S_is_one_byte_char_type(_CharT*)
00117     { return false; }
00118 
00119   inline bool
00120   _S_is_basic_char_type(char*)
00121   { return true; }
00122   
00123   inline bool
00124   _S_is_one_byte_char_type(char*)
00125   { return true; }
00126   
00127   inline bool
00128   _S_is_basic_char_type(wchar_t*)
00129   { return true; }
00130 
00131   // Store an eos iff _CharT is a basic character type.
00132   // Do not reference _S_eos if it isn't.
00133   template <class _CharT>
00134     inline void
00135     _S_cond_store_eos(_CharT&) { }
00136 
00137   inline void
00138   _S_cond_store_eos(char& __c)
00139   { __c = 0; }
00140 
00141   inline void
00142   _S_cond_store_eos(wchar_t& __c)
00143   { __c = 0; }
00144 
00145   // char_producers are logically functions that generate a section of
00146   // a string.  These can be converted to ropes.  The resulting rope
00147   // invokes the char_producer on demand.  This allows, for example,
00148   // files to be viewed as ropes without reading the entire file.
00149   template <class _CharT>
00150     class char_producer
00151     {
00152     public:
00153       virtual ~char_producer() { };
00154 
00155       virtual void
00156       operator()(size_t __start_pos, size_t __len,
00157                  _CharT* __buffer) = 0;
00158       // Buffer should really be an arbitrary output iterator.
00159       // That way we could flatten directly into an ostream, etc.
00160       // This is thoroughly impossible, since iterator types don't
00161       // have runtime descriptions.
00162     };
00163 
00164   // Sequence buffers:
00165   //
00166   // Sequence must provide an append operation that appends an
00167   // array to the sequence.  Sequence buffers are useful only if
00168   // appending an entire array is cheaper than appending element by element.
00169   // This is true for many string representations.
00170   // This should  perhaps inherit from ostream<sequence::value_type>
00171   // and be implemented correspondingly, so that they can be used
00172   // for formatted.  For the sake of portability, we don't do this yet.
00173   //
00174   // For now, sequence buffers behave as output iterators.  But they also
00175   // behave a little like basic_ostringstream<sequence::value_type> and a
00176   // little like containers.
00177 
00178   template<class _Sequence, size_t _Buf_sz = 100>
00179     class sequence_buffer
00180     : public std::iterator<std::output_iterator_tag, void, void, void, void>
00181     {
00182     public:
00183       typedef typename _Sequence::value_type value_type;
00184     protected:
00185       _Sequence* _M_prefix;
00186       value_type _M_buffer[_Buf_sz];
00187       size_t     _M_buf_count;
00188     public:
00189 
00190       void
00191       flush()
00192       {
00193         _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
00194         _M_buf_count = 0;
00195       }
00196       
00197       ~sequence_buffer()
00198       { flush(); }
00199       
00200       sequence_buffer()
00201       : _M_prefix(0), _M_buf_count(0) { }
00202 
00203       sequence_buffer(const sequence_buffer& __x)
00204       {
00205         _M_prefix = __x._M_prefix;
00206         _M_buf_count = __x._M_buf_count;
00207         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
00208       }
00209       
00210       sequence_buffer(sequence_buffer& __x)
00211       {
00212         __x.flush();
00213         _M_prefix = __x._M_prefix;
00214         _M_buf_count = 0;
00215       }
00216       
00217       sequence_buffer(_Sequence& __s)
00218       : _M_prefix(&__s), _M_buf_count(0) { }
00219       
00220       sequence_buffer&
00221       operator=(sequence_buffer& __x)
00222       {
00223         __x.flush();
00224         _M_prefix = __x._M_prefix;
00225         _M_buf_count = 0;
00226         return *this;
00227       }
00228 
00229       sequence_buffer&
00230       operator=(const sequence_buffer& __x)
00231       {
00232         _M_prefix = __x._M_prefix;
00233         _M_buf_count = __x._M_buf_count;
00234         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
00235         return *this;
00236       }
00237       
00238       void
00239       push_back(value_type __x)
00240       {
00241         if (_M_buf_count < _Buf_sz)
00242           {
00243             _M_buffer[_M_buf_count] = __x;
00244             ++_M_buf_count;
00245           }
00246         else
00247           {
00248             flush();
00249             _M_buffer[0] = __x;
00250             _M_buf_count = 1;
00251           }
00252       }
00253       
00254       void
00255       append(value_type* __s, size_t __len)
00256       {
00257         if (__len + _M_buf_count <= _Buf_sz)
00258           {
00259             size_t __i = _M_buf_count;
00260             for (size_t __j = 0; __j < __len; __i++, __j++)
00261               _M_buffer[__i] = __s[__j];
00262             _M_buf_count += __len;
00263           }
00264         else if (0 == _M_buf_count)
00265           _M_prefix->append(__s, __s + __len);
00266         else
00267           {
00268             flush();
00269             append(__s, __len);
00270           }
00271       }
00272 
00273       sequence_buffer&
00274       write(value_type* __s, size_t __len)
00275       {
00276         append(__s, __len);
00277         return *this;
00278       }
00279       
00280       sequence_buffer&
00281       put(value_type __x)
00282       {
00283         push_back(__x);
00284         return *this;
00285       }
00286       
00287       sequence_buffer&
00288       operator=(const value_type& __rhs)
00289       {
00290         push_back(__rhs);
00291         return *this;
00292       }
00293       
00294       sequence_buffer&
00295       operator*()
00296       { return *this; }
00297       
00298       sequence_buffer&
00299       operator++()
00300       { return *this; }
00301       
00302       sequence_buffer
00303       operator++(int)
00304       { return *this; }
00305     };
00306   
00307   // The following should be treated as private, at least for now.
00308   template<class _CharT>
00309     class _Rope_char_consumer
00310     {
00311     public:
00312       // If we had member templates, these should not be virtual.
00313       // For now we need to use run-time parametrization where
00314       // compile-time would do.  Hence this should all be private
00315       // for now.
00316       // The symmetry with char_producer is accidental and temporary.
00317       virtual ~_Rope_char_consumer() { };
00318   
00319       virtual bool
00320       operator()(const _CharT* __buffer, size_t __len) = 0;
00321     };
00322   
00323   // First a lot of forward declarations.  The standard seems to require
00324   // much stricter "declaration before use" than many of the implementations
00325   // that preceded it.
00326   template<class _CharT, class _Alloc = allocator<_CharT> >
00327     class rope;
00328   
00329   template<class _CharT, class _Alloc>
00330     struct _Rope_RopeConcatenation;
00331 
00332   template<class _CharT, class _Alloc>
00333     struct _Rope_RopeLeaf;
00334   
00335   template<class _CharT, class _Alloc>
00336     struct _Rope_RopeFunction;
00337   
00338   template<class _CharT, class _Alloc>
00339     struct _Rope_RopeSubstring;
00340   
00341   template<class _CharT, class _Alloc>
00342     class _Rope_iterator;
00343   
00344   template<class _CharT, class _Alloc>
00345     class _Rope_const_iterator;
00346   
00347   template<class _CharT, class _Alloc>
00348     class _Rope_char_ref_proxy;
00349   
00350   template<class _CharT, class _Alloc>
00351     class _Rope_char_ptr_proxy;
00352 
00353   template<class _CharT, class _Alloc>
00354     bool
00355     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
00356                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
00357 
00358   template<class _CharT, class _Alloc>
00359     _Rope_const_iterator<_CharT, _Alloc>
00360     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00361               ptrdiff_t __n);
00362 
00363   template<class _CharT, class _Alloc>
00364     _Rope_const_iterator<_CharT, _Alloc>
00365     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00366               ptrdiff_t __n);
00367 
00368   template<class _CharT, class _Alloc>
00369     _Rope_const_iterator<_CharT, _Alloc>
00370     operator+(ptrdiff_t __n,
00371               const _Rope_const_iterator<_CharT, _Alloc>& __x);
00372 
00373   template<class _CharT, class _Alloc>
00374     bool
00375     operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00376                const _Rope_const_iterator<_CharT, _Alloc>& __y);
00377 
00378   template<class _CharT, class _Alloc>
00379     bool
00380     operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00381               const _Rope_const_iterator<_CharT, _Alloc>& __y);
00382   
00383   template<class _CharT, class _Alloc>
00384     ptrdiff_t
00385     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00386               const _Rope_const_iterator<_CharT, _Alloc>& __y);
00387 
00388   template<class _CharT, class _Alloc>
00389     _Rope_iterator<_CharT, _Alloc>
00390     operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
00391 
00392   template<class _CharT, class _Alloc>
00393     _Rope_iterator<_CharT, _Alloc>
00394     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
00395 
00396   template<class _CharT, class _Alloc>
00397     _Rope_iterator<_CharT, _Alloc>
00398     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
00399 
00400   template<class _CharT, class _Alloc>
00401     bool
00402     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
00403                const _Rope_iterator<_CharT, _Alloc>& __y);
00404 
00405   template<class _CharT, class _Alloc>
00406     bool
00407     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
00408               const _Rope_iterator<_CharT, _Alloc>& __y);
00409 
00410   template<class _CharT, class _Alloc>
00411     ptrdiff_t
00412     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
00413               const _Rope_iterator<_CharT, _Alloc>& __y);
00414 
00415   template<class _CharT, class _Alloc>
00416     rope<_CharT, _Alloc>
00417     operator+(const rope<_CharT, _Alloc>& __left,
00418               const rope<_CharT, _Alloc>& __right);
00419 
00420   template<class _CharT, class _Alloc>
00421     rope<_CharT, _Alloc>
00422     operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
00423 
00424   template<class _CharT, class _Alloc>
00425     rope<_CharT, _Alloc>
00426     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
00427 
00428   // Some helpers, so we can use power on ropes.
00429   // See below for why this isn't local to the implementation.
00430   
00431   // This uses a nonstandard refcount convention.
00432   // The result has refcount 0.
00433   template<class _CharT, class _Alloc>
00434     struct _Rope_Concat_fn
00435     : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
00436                                   rope<_CharT, _Alloc> >
00437     {
00438       rope<_CharT, _Alloc>
00439       operator()(const rope<_CharT, _Alloc>& __x,
00440                  const rope<_CharT, _Alloc>& __y)
00441       { return __x + __y; }
00442     };
00443 
00444   template <class _CharT, class _Alloc>
00445     inline rope<_CharT, _Alloc>
00446     identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
00447     { return rope<_CharT, _Alloc>(); }
00448 
00449   // Class _Refcount_Base provides a type, _RC_t, a data member,
00450   // _M_ref_count, and member functions _M_incr and _M_decr, which perform
00451   // atomic preincrement/predecrement.  The constructor initializes
00452   // _M_ref_count.
00453   struct _Refcount_Base
00454   {
00455     // The type _RC_t
00456     typedef size_t _RC_t;
00457     
00458     // The data member _M_ref_count
00459     volatile _RC_t _M_ref_count;
00460 
00461     // Constructor
00462 #ifdef __GTHREAD_MUTEX_INIT
00463     __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT;
00464 #else
00465     __gthread_mutex_t _M_ref_count_lock;
00466 #endif
00467 
00468     _Refcount_Base(_RC_t __n) : _M_ref_count(__n)
00469     {
00470 #ifndef __GTHREAD_MUTEX_INIT
00471 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
00472       __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
00473 #else
00474 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
00475 #endif
00476 #endif
00477     }
00478 
00479 #ifndef __GTHREAD_MUTEX_INIT
00480     ~_Refcount_Base()
00481     { __gthread_mutex_destroy(&_M_ref_count_lock); }
00482 #endif
00483 
00484     void
00485     _M_incr()
00486     {
00487       __gthread_mutex_lock(&_M_ref_count_lock);
00488       ++_M_ref_count;
00489       __gthread_mutex_unlock(&_M_ref_count_lock);
00490     }
00491 
00492     _RC_t
00493     _M_decr()
00494     {
00495       __gthread_mutex_lock(&_M_ref_count_lock);
00496       volatile _RC_t __tmp = --_M_ref_count;
00497       __gthread_mutex_unlock(&_M_ref_count_lock);
00498       return __tmp;
00499     }
00500   };
00501 
00502   //
00503   // What follows should really be local to rope.  Unfortunately,
00504   // that doesn't work, since it makes it impossible to define generic
00505   // equality on rope iterators.  According to the draft standard, the
00506   // template parameters for such an equality operator cannot be inferred
00507   // from the occurrence of a member class as a parameter.
00508   // (SGI compilers in fact allow this, but the __result wouldn't be
00509   // portable.)
00510   // Similarly, some of the static member functions are member functions
00511   // only to avoid polluting the global namespace, and to circumvent
00512   // restrictions on type inference for template functions.
00513   //
00514 
00515   //
00516   // The internal data structure for representing a rope.  This is
00517   // private to the implementation.  A rope is really just a pointer
00518   // to one of these.
00519   //
00520   // A few basic functions for manipulating this data structure
00521   // are members of _RopeRep.  Most of the more complex algorithms
00522   // are implemented as rope members.
00523   //
00524   // Some of the static member functions of _RopeRep have identically
00525   // named functions in rope that simply invoke the _RopeRep versions.
00526 
00527 #define __ROPE_DEFINE_ALLOCS(__a) \
00528         __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
00529         typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
00530         __ROPE_DEFINE_ALLOC(__C,_C) \
00531         typedef _Rope_RopeLeaf<_CharT,__a> __L; \
00532         __ROPE_DEFINE_ALLOC(__L,_L) \
00533         typedef _Rope_RopeFunction<_CharT,__a> __F; \
00534         __ROPE_DEFINE_ALLOC(__F,_F) \
00535         typedef _Rope_RopeSubstring<_CharT,__a> __S; \
00536         __ROPE_DEFINE_ALLOC(__S,_S)
00537 
00538   //  Internal rope nodes potentially store a copy of the allocator
00539   //  instance used to allocate them.  This is mostly redundant.
00540   //  But the alternative would be to pass allocator instances around
00541   //  in some form to nearly all internal functions, since any pointer
00542   //  assignment may result in a zero reference count and thus require
00543   //  deallocation.
00544 
00545 #define __STATIC_IF_SGI_ALLOC  /* not static */
00546 
00547   template <class _CharT, class _Alloc>
00548     struct _Rope_rep_base
00549     : public _Alloc
00550     {
00551       typedef _Alloc allocator_type;
00552 
00553       allocator_type
00554       get_allocator() const
00555       { return *static_cast<const _Alloc*>(this); }
00556 
00557       allocator_type&
00558       _M_get_allocator()
00559       { return *static_cast<_Alloc*>(this); }
00560 
00561       const allocator_type&
00562       _M_get_allocator() const
00563       { return *static_cast<const _Alloc*>(this); }
00564 
00565       _Rope_rep_base(size_t __size, const allocator_type&)
00566       : _M_size(__size) { }
00567 
00568       size_t _M_size;
00569 
00570 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
00571         typedef typename \
00572           _Alloc::template rebind<_Tp>::other __name##Alloc; \
00573         static _Tp* __name##_allocate(size_t __n) \
00574           { return __name##Alloc().allocate(__n); } \
00575         static void __name##_deallocate(_Tp *__p, size_t __n) \
00576           { __name##Alloc().deallocate(__p, __n); }
00577       __ROPE_DEFINE_ALLOCS(_Alloc)
00578 # undef __ROPE_DEFINE_ALLOC
00579     };
00580 
00581   template<class _CharT, class _Alloc>
00582     struct _Rope_RopeRep
00583     : public _Rope_rep_base<_CharT, _Alloc>
00584 # ifndef __GC
00585              , _Refcount_Base
00586 # endif
00587     {
00588     public:
00589       __detail::_Tag _M_tag:8;
00590       bool _M_is_balanced:8;
00591       unsigned char _M_depth;
00592       __GC_CONST _CharT* _M_c_string;
00593 #ifdef __GTHREAD_MUTEX_INIT
00594       __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT;
00595 #else
00596       __gthread_mutex_t _M_c_string_lock;
00597 #endif
00598                         /* Flattened version of string, if needed.  */
00599                         /* typically 0.                             */
00600                         /* If it's not 0, then the memory is owned  */
00601                         /* by this node.                            */
00602                         /* In the case of a leaf, this may point to */
00603                         /* the same memory as the data field.       */
00604       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00605         allocator_type;
00606 
00607       using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
00608       using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
00609 
00610       _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
00611                     const allocator_type& __a)
00612       : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
00613 #ifndef __GC
00614         _Refcount_Base(1),
00615 #endif
00616         _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
00617 #ifdef __GTHREAD_MUTEX_INIT
00618       { }
00619 #else
00620       { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
00621       ~_Rope_RopeRep()
00622       { __gthread_mutex_destroy (&_M_c_string_lock); }
00623 #endif
00624 #ifdef __GC
00625       void
00626       _M_incr () { }
00627 #endif
00628       static void
00629       _S_free_string(__GC_CONST _CharT*, size_t __len,
00630                      allocator_type& __a);
00631 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
00632                         // Deallocate data section of a leaf.
00633                         // This shouldn't be a member function.
00634                         // But its hard to do anything else at the
00635                         // moment, because it's templatized w.r.t.
00636                         // an allocator.
00637                         // Does nothing if __GC is defined.
00638 #ifndef __GC
00639       void _M_free_c_string();
00640       void _M_free_tree();
00641       // Deallocate t. Assumes t is not 0.
00642       void
00643       _M_unref_nonnil()
00644       {
00645         if (0 == _M_decr())
00646           _M_free_tree();
00647       }
00648 
00649       void
00650       _M_ref_nonnil()
00651       { _M_incr(); }
00652 
00653       static void
00654       _S_unref(_Rope_RopeRep* __t)
00655       {
00656         if (0 != __t)
00657           __t->_M_unref_nonnil();
00658       }
00659 
00660       static void
00661       _S_ref(_Rope_RopeRep* __t)
00662       {
00663         if (0 != __t)
00664           __t->_M_incr();
00665       }
00666       
00667       static void
00668       _S_free_if_unref(_Rope_RopeRep* __t)
00669       {
00670         if (0 != __t && 0 == __t->_M_ref_count)
00671           __t->_M_free_tree();
00672       }
00673 #   else /* __GC */
00674       void _M_unref_nonnil() { }
00675       void _M_ref_nonnil() { }
00676       static void _S_unref(_Rope_RopeRep*) { }
00677       static void _S_ref(_Rope_RopeRep*) { }
00678       static void _S_free_if_unref(_Rope_RopeRep*) { }
00679 #   endif
00680 protected:
00681       _Rope_RopeRep&
00682       operator=(const _Rope_RopeRep&);
00683 
00684       _Rope_RopeRep(const _Rope_RopeRep&);
00685     };
00686 
00687   template<class _CharT, class _Alloc>
00688     struct _Rope_RopeLeaf
00689     : public _Rope_RopeRep<_CharT, _Alloc>
00690     {
00691     public:
00692       // Apparently needed by VC++
00693       // The data fields of leaves are allocated with some
00694       // extra space, to accommodate future growth and for basic
00695       // character types, to hold a trailing eos character.
00696       enum { _S_alloc_granularity = 8 };
00697       
00698       static size_t
00699       _S_rounded_up_size(size_t __n)
00700       {
00701         size_t __size_with_eos;
00702         
00703         if (_S_is_basic_char_type((_CharT*)0))
00704           __size_with_eos = __n + 1;
00705         else
00706           __size_with_eos = __n;
00707 #ifdef __GC
00708         return __size_with_eos;
00709 #else
00710         // Allow slop for in-place expansion.
00711         return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
00712                 &~ (size_t(_S_alloc_granularity) - 1));
00713 #endif
00714       }
00715       __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
00716                                   /* The allocated size is         */
00717                                   /* _S_rounded_up_size(size), except */
00718                                   /* in the GC case, in which it   */
00719                                   /* doesn't matter.               */
00720       typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
00721         allocator_type;
00722 
00723       _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
00724                      const allocator_type& __a)
00725       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
00726                                       __size, __a), _M_data(__d)
00727       {
00728         if (_S_is_basic_char_type((_CharT *)0))
00729           {
00730             // already eos terminated.
00731             this->_M_c_string = __d;
00732           }
00733       }
00734       // The constructor assumes that d has been allocated with
00735       // the proper allocator and the properly padded size.
00736       // In contrast, the destructor deallocates the data:
00737 #ifndef __GC
00738       ~_Rope_RopeLeaf() throw()
00739       {
00740         if (_M_data != this->_M_c_string)
00741           this->_M_free_c_string();
00742         
00743         this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
00744       }
00745 #endif
00746 protected:
00747       _Rope_RopeLeaf&
00748       operator=(const _Rope_RopeLeaf&);
00749 
00750       _Rope_RopeLeaf(const _Rope_RopeLeaf&);
00751     };
00752 
00753   template<class _CharT, class _Alloc>
00754     struct _Rope_RopeConcatenation
00755     : public _Rope_RopeRep<_CharT, _Alloc>
00756     {
00757     public:
00758       _Rope_RopeRep<_CharT, _Alloc>* _M_left;
00759       _Rope_RopeRep<_CharT, _Alloc>* _M_right;
00760 
00761       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00762         allocator_type;
00763 
00764       _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
00765                               _Rope_RopeRep<_CharT, _Alloc>* __r,
00766                               const allocator_type& __a)
00767         : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
00768                                       std::max(__l->_M_depth,
00769                                                __r->_M_depth) + 1,
00770                                       false,
00771                                       __l->_M_size + __r->_M_size, __a),
00772         _M_left(__l), _M_right(__r)
00773       { }
00774 #ifndef __GC
00775       ~_Rope_RopeConcatenation() throw()
00776       {
00777         this->_M_free_c_string();
00778         _M_left->_M_unref_nonnil();
00779         _M_right->_M_unref_nonnil();
00780       }
00781 #endif
00782 protected:
00783       _Rope_RopeConcatenation&
00784       operator=(const _Rope_RopeConcatenation&);
00785       
00786       _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
00787     };
00788 
00789   template<class _CharT, class _Alloc>
00790     struct _Rope_RopeFunction
00791     : public _Rope_RopeRep<_CharT, _Alloc>
00792     {
00793     public:
00794       char_producer<_CharT>* _M_fn;
00795 #ifndef __GC
00796       bool _M_delete_when_done; // Char_producer is owned by the
00797                                 // rope and should be explicitly
00798                                 // deleted when the rope becomes
00799                                 // inaccessible.
00800 #else
00801       // In the GC case, we either register the rope for
00802       // finalization, or not.  Thus the field is unnecessary;
00803       // the information is stored in the collector data structures.
00804       // We do need a finalization procedure to be invoked by the
00805       // collector.
00806       static void
00807       _S_fn_finalization_proc(void * __tree, void *)
00808       { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
00809 #endif
00810     typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00811       allocator_type;
00812 
00813       _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
00814                         bool __d, const allocator_type& __a)
00815       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
00816         , _M_fn(__f)
00817 #ifndef __GC
00818         , _M_delete_when_done(__d)
00819 #endif
00820       {
00821 #ifdef __GC
00822         if (__d)
00823           {
00824             GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
00825                                   _S_fn_finalization_proc, 0, 0, 0);
00826           }
00827 #endif
00828       }
00829 #ifndef __GC
00830       ~_Rope_RopeFunction() throw()
00831       {
00832         this->_M_free_c_string();
00833         if (_M_delete_when_done)
00834           delete _M_fn;
00835       }
00836 # endif
00837     protected:
00838       _Rope_RopeFunction&
00839       operator=(const _Rope_RopeFunction&);
00840 
00841       _Rope_RopeFunction(const _Rope_RopeFunction&);
00842     };
00843   // Substring results are usually represented using just
00844   // concatenation nodes.  But in the case of very long flat ropes
00845   // or ropes with a functional representation that isn't practical.
00846   // In that case, we represent the __result as a special case of
00847   // RopeFunction, whose char_producer points back to the rope itself.
00848   // In all cases except repeated substring operations and
00849   // deallocation, we treat the __result as a RopeFunction.
00850   template<class _CharT, class _Alloc>
00851     struct _Rope_RopeSubstring
00852     : public _Rope_RopeFunction<_CharT, _Alloc>,
00853       public char_producer<_CharT>
00854     {
00855     public:
00856       // XXX this whole class should be rewritten.
00857       _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
00858       size_t _M_start;
00859 
00860       virtual void
00861       operator()(size_t __start_pos, size_t __req_len,
00862                  _CharT* __buffer)
00863       {
00864         switch(_M_base->_M_tag)
00865           {
00866           case __detail::_S_function:
00867           case __detail::_S_substringfn:
00868             {
00869               char_producer<_CharT>* __fn =
00870                 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
00871               (*__fn)(__start_pos + _M_start, __req_len, __buffer);
00872             }
00873             break;
00874           case __detail::_S_leaf:
00875             {
00876               __GC_CONST _CharT* __s =
00877                 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
00878               uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
00879                                    __buffer);
00880             }
00881             break;
00882           default:
00883             break;
00884           }
00885       }
00886       
00887       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00888         allocator_type;
00889 
00890       _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
00891                           size_t __l, const allocator_type& __a)
00892       : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
00893         char_producer<_CharT>(), _M_base(__b), _M_start(__s)
00894       {
00895 #ifndef __GC
00896         _M_base->_M_ref_nonnil();
00897 #endif
00898         this->_M_tag = __detail::_S_substringfn;
00899       }
00900     virtual ~_Rope_RopeSubstring() throw()
00901       {
00902 #ifndef __GC
00903         _M_base->_M_unref_nonnil();
00904         // _M_free_c_string();  -- done by parent class
00905 #endif
00906       }
00907     };
00908 
00909   // Self-destructing pointers to Rope_rep.
00910   // These are not conventional smart pointers.  Their
00911   // only purpose in life is to ensure that unref is called
00912   // on the pointer either at normal exit or if an exception
00913   // is raised.  It is the caller's responsibility to
00914   // adjust reference counts when these pointers are initialized
00915   // or assigned to.  (This convention significantly reduces
00916   // the number of potentially expensive reference count
00917   // updates.)
00918 #ifndef __GC
00919   template<class _CharT, class _Alloc>
00920     struct _Rope_self_destruct_ptr
00921     {
00922       _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
00923 
00924       ~_Rope_self_destruct_ptr()
00925       { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
00926 #if __cpp_exceptions
00927       _Rope_self_destruct_ptr() : _M_ptr(0) { };
00928 #else
00929       _Rope_self_destruct_ptr() { };
00930 #endif
00931       _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
00932       : _M_ptr(__p) { }
00933     
00934       _Rope_RopeRep<_CharT, _Alloc>&
00935       operator*()
00936       { return *_M_ptr; }
00937     
00938       _Rope_RopeRep<_CharT, _Alloc>*
00939       operator->()
00940       { return _M_ptr; }
00941     
00942       operator _Rope_RopeRep<_CharT, _Alloc>*()
00943       { return _M_ptr; }
00944     
00945       _Rope_self_destruct_ptr&
00946       operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
00947       { _M_ptr = __x; return *this; }
00948     };
00949 #endif
00950 
00951   // Dereferencing a nonconst iterator has to return something
00952   // that behaves almost like a reference.  It's not possible to
00953   // return an actual reference since assignment requires extra
00954   // work.  And we would get into the same problems as with the
00955   // CD2 version of basic_string.
00956   template<class _CharT, class _Alloc>
00957     class _Rope_char_ref_proxy
00958     {
00959       friend class rope<_CharT, _Alloc>;
00960       friend class _Rope_iterator<_CharT, _Alloc>;
00961       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
00962 #ifdef __GC
00963       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
00964 #else
00965       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
00966 #endif
00967       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
00968       typedef rope<_CharT, _Alloc> _My_rope;
00969       size_t _M_pos;
00970       _CharT _M_current;
00971       bool _M_current_valid;
00972       _My_rope* _M_root;     // The whole rope.
00973     public:
00974       _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
00975       :  _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
00976 
00977       _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
00978       : _M_pos(__x._M_pos), _M_current(__x._M_current), 
00979         _M_current_valid(false), _M_root(__x._M_root) { }
00980 
00981       // Don't preserve cache if the reference can outlive the
00982       // expression.  We claim that's not possible without calling
00983       // a copy constructor or generating reference to a proxy
00984       // reference.  We declare the latter to have undefined semantics.
00985       _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
00986       : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
00987 
00988       inline operator _CharT () const;
00989 
00990       _Rope_char_ref_proxy&
00991       operator=(_CharT __c);
00992     
00993       _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
00994       
00995       _Rope_char_ref_proxy&
00996       operator=(const _Rope_char_ref_proxy& __c)
00997       { return operator=((_CharT)__c); }
00998     };
00999 
01000   template<class _CharT, class __Alloc>
01001     inline void
01002     swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
01003          _Rope_char_ref_proxy <_CharT, __Alloc > __b)
01004     {
01005       _CharT __tmp = __a;
01006       __a = __b;
01007       __b = __tmp;
01008     }
01009 
01010   template<class _CharT, class _Alloc>
01011     class _Rope_char_ptr_proxy
01012     {
01013       // XXX this class should be rewritten.
01014       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
01015       size_t _M_pos;
01016       rope<_CharT,_Alloc>* _M_root;     // The whole rope.
01017     public:
01018       _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
01019       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
01020 
01021       _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
01022       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
01023 
01024       _Rope_char_ptr_proxy() { }
01025       
01026       _Rope_char_ptr_proxy(_CharT* __x)
01027       : _M_root(0), _M_pos(0) { }
01028 
01029       _Rope_char_ptr_proxy&
01030       operator=(const _Rope_char_ptr_proxy& __x)
01031       {
01032         _M_pos = __x._M_pos;
01033         _M_root = __x._M_root;
01034         return *this;
01035       }
01036 
01037       template<class _CharT2, class _Alloc2>
01038         friend bool
01039         operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
01040                    const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
01041 
01042       _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
01043       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
01044     };
01045 
01046   // Rope iterators:
01047   // Unlike in the C version, we cache only part of the stack
01048   // for rope iterators, since they must be efficiently copyable.
01049   // When we run out of cache, we have to reconstruct the iterator
01050   // value.
01051   // Pointers from iterators are not included in reference counts.
01052   // Iterators are assumed to be thread private.  Ropes can
01053   // be shared.
01054   
01055   template<class _CharT, class _Alloc>
01056     class _Rope_iterator_base
01057     : public std::iterator<std::random_access_iterator_tag, _CharT>
01058     {
01059       friend class rope<_CharT, _Alloc>;
01060     public:
01061       typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround
01062       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01063       // Borland doesn't want this to be protected.
01064     protected:
01065       enum { _S_path_cache_len = 4 }; // Must be <= 9.
01066       enum { _S_iterator_buf_len = 15 };
01067       size_t _M_current_pos;
01068       _RopeRep* _M_root;     // The whole rope.
01069       size_t _M_leaf_pos;    // Starting position for current leaf
01070       __GC_CONST _CharT* _M_buf_start;
01071                              // Buffer possibly
01072                              // containing current char.
01073       __GC_CONST _CharT* _M_buf_ptr;
01074                              // Pointer to current char in buffer.
01075                              // != 0 ==> buffer valid.
01076       __GC_CONST _CharT* _M_buf_end;
01077                              // One past __last valid char in buffer.
01078       // What follows is the path cache.  We go out of our
01079       // way to make this compact.
01080       // Path_end contains the bottom section of the path from
01081       // the root to the current leaf.
01082       const _RopeRep* _M_path_end[_S_path_cache_len];
01083       int _M_leaf_index;     // Last valid __pos in path_end;
01084                              // _M_path_end[0] ... _M_path_end[leaf_index-1]
01085                              // point to concatenation nodes.
01086       unsigned char _M_path_directions;
01087                           // (path_directions >> __i) & 1 is 1
01088                           // iff we got from _M_path_end[leaf_index - __i - 1]
01089                           // to _M_path_end[leaf_index - __i] by going to the
01090                           // __right. Assumes path_cache_len <= 9.
01091       _CharT _M_tmp_buf[_S_iterator_buf_len];
01092                         // Short buffer for surrounding chars.
01093                         // This is useful primarily for
01094                         // RopeFunctions.  We put the buffer
01095                         // here to avoid locking in the
01096                         // multithreaded case.
01097       // The cached path is generally assumed to be valid
01098       // only if the buffer is valid.
01099       static void _S_setbuf(_Rope_iterator_base& __x);
01100                                         // Set buffer contents given
01101                                         // path cache.
01102       static void _S_setcache(_Rope_iterator_base& __x);
01103                                         // Set buffer contents and
01104                                         // path cache.
01105       static void _S_setcache_for_incr(_Rope_iterator_base& __x);
01106                                         // As above, but assumes path
01107                                         // cache is valid for previous posn.
01108       _Rope_iterator_base() { }
01109 
01110       _Rope_iterator_base(_RopeRep* __root, size_t __pos)
01111       : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
01112 
01113       void _M_incr(size_t __n);
01114       void _M_decr(size_t __n);
01115     public:
01116       size_t
01117       index() const
01118       { return _M_current_pos; }
01119     
01120       _Rope_iterator_base(const _Rope_iterator_base& __x)
01121       {
01122         if (0 != __x._M_buf_ptr)
01123           *this = __x;
01124         else
01125           {
01126             _M_current_pos = __x._M_current_pos;
01127             _M_root = __x._M_root;
01128             _M_buf_ptr = 0;
01129           }
01130       }
01131     };
01132 
01133   template<class _CharT, class _Alloc>
01134     class _Rope_iterator;
01135 
01136   template<class _CharT, class _Alloc>
01137     class _Rope_const_iterator
01138     : public _Rope_iterator_base<_CharT, _Alloc>
01139     {
01140       friend class rope<_CharT, _Alloc>;
01141     protected:
01142       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01143       // The one from the base class may not be directly visible.
01144       _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
01145       : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
01146                                             __pos)
01147                    // Only nonconst iterators modify root ref count
01148       { }
01149   public:
01150       typedef _CharT reference;   // Really a value.  Returning a reference
01151                                   // Would be a mess, since it would have
01152                                   // to be included in refcount.
01153       typedef const _CharT* pointer;
01154 
01155     public:
01156       _Rope_const_iterator() { };
01157 
01158       _Rope_const_iterator(const _Rope_const_iterator& __x)
01159       : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
01160 
01161       _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
01162     
01163       _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
01164       : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
01165 
01166       _Rope_const_iterator&
01167       operator=(const _Rope_const_iterator& __x)
01168       {
01169         if (0 != __x._M_buf_ptr)
01170           *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
01171         else
01172           {
01173             this->_M_current_pos = __x._M_current_pos;
01174             this->_M_root = __x._M_root;
01175             this->_M_buf_ptr = 0;
01176           }
01177         return(*this);
01178       }
01179 
01180       reference
01181       operator*()
01182       {
01183         if (0 == this->_M_buf_ptr)
01184           this->_S_setcache(*this);
01185         return *this->_M_buf_ptr;
01186       }
01187 
01188       // Without this const version, Rope iterators do not meet the
01189       // requirements of an Input Iterator.
01190       reference
01191       operator*() const
01192       {
01193         return *const_cast<_Rope_const_iterator&>(*this);
01194       }
01195 
01196       _Rope_const_iterator&
01197       operator++()
01198       {
01199         __GC_CONST _CharT* __next;
01200         if (0 != this->_M_buf_ptr
01201             && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
01202           {
01203             this->_M_buf_ptr = __next;
01204             ++this->_M_current_pos;
01205           }
01206         else
01207           this->_M_incr(1);
01208         return *this;
01209       }
01210 
01211       _Rope_const_iterator&
01212       operator+=(ptrdiff_t __n)
01213       {
01214         if (__n >= 0)
01215           this->_M_incr(__n);
01216         else
01217           this->_M_decr(-__n);
01218         return *this;
01219       }
01220 
01221       _Rope_const_iterator&
01222       operator--()
01223       {
01224         this->_M_decr(1);
01225         return *this;
01226       }
01227 
01228       _Rope_const_iterator&
01229       operator-=(ptrdiff_t __n)
01230       {
01231         if (__n >= 0)
01232           this->_M_decr(__n);
01233         else
01234           this->_M_incr(-__n);
01235         return *this;
01236       }
01237 
01238       _Rope_const_iterator
01239       operator++(int)
01240       {
01241         size_t __old_pos = this->_M_current_pos;
01242         this->_M_incr(1);
01243         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
01244         // This makes a subsequent dereference expensive.
01245         // Perhaps we should instead copy the iterator
01246         // if it has a valid cache?
01247       }
01248 
01249       _Rope_const_iterator
01250       operator--(int)
01251       {
01252         size_t __old_pos = this->_M_current_pos;
01253         this->_M_decr(1);
01254         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
01255       }
01256 
01257       template<class _CharT2, class _Alloc2>
01258         friend _Rope_const_iterator<_CharT2, _Alloc2>
01259         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01260                   ptrdiff_t __n);
01261 
01262       template<class _CharT2, class _Alloc2>
01263         friend _Rope_const_iterator<_CharT2, _Alloc2>
01264         operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01265                   ptrdiff_t __n);
01266 
01267       template<class _CharT2, class _Alloc2>
01268         friend _Rope_const_iterator<_CharT2, _Alloc2>
01269         operator+(ptrdiff_t __n,
01270                   const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
01271 
01272       reference
01273       operator[](size_t __n)
01274       { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
01275                                               this->_M_current_pos + __n); }
01276 
01277       template<class _CharT2, class _Alloc2>
01278         friend bool
01279         operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01280                    const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01281 
01282       template<class _CharT2, class _Alloc2>
01283         friend bool
01284         operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01285                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01286 
01287       template<class _CharT2, class _Alloc2>
01288         friend ptrdiff_t
01289         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01290                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01291     };
01292 
01293   template<class _CharT, class _Alloc>
01294     class _Rope_iterator
01295     : public _Rope_iterator_base<_CharT, _Alloc>
01296     {
01297       friend class rope<_CharT, _Alloc>;
01298     protected:
01299       typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
01300       rope<_CharT, _Alloc>* _M_root_rope;
01301 
01302       // root is treated as a cached version of this, and is used to
01303       // detect changes to the underlying rope.
01304 
01305       // Root is included in the reference count.  This is necessary
01306       // so that we can detect changes reliably.  Unfortunately, it
01307       // requires careful bookkeeping for the nonGC case.
01308       _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
01309       : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
01310         _M_root_rope(__r)
01311       { _RopeRep::_S_ref(this->_M_root);
01312         if (!(__r -> empty()))
01313           this->_S_setcache(*this);
01314       }
01315 
01316       void _M_check();
01317     public:
01318       typedef _Rope_char_ref_proxy<_CharT, _Alloc>  reference;
01319       typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
01320 
01321       rope<_CharT, _Alloc>&
01322       container()
01323       { return *_M_root_rope; }
01324 
01325       _Rope_iterator()
01326       {
01327         this->_M_root = 0;  // Needed for reference counting.
01328       };
01329 
01330       _Rope_iterator(const _Rope_iterator& __x)
01331       : _Rope_iterator_base<_CharT, _Alloc>(__x)
01332       {
01333         _M_root_rope = __x._M_root_rope;
01334         _RopeRep::_S_ref(this->_M_root);
01335       }
01336 
01337       _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
01338 
01339       ~_Rope_iterator()
01340       { _RopeRep::_S_unref(this->_M_root); }
01341 
01342       _Rope_iterator&
01343       operator=(const _Rope_iterator& __x)
01344       {
01345         _RopeRep* __old = this->_M_root;
01346         
01347         _RopeRep::_S_ref(__x._M_root);
01348         if (0 != __x._M_buf_ptr)
01349           {
01350             _M_root_rope = __x._M_root_rope;
01351             *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
01352           }
01353         else
01354           {
01355             this->_M_current_pos = __x._M_current_pos;
01356             this->_M_root = __x._M_root;
01357             _M_root_rope = __x._M_root_rope;
01358             this->_M_buf_ptr = 0;
01359           }
01360         _RopeRep::_S_unref(__old);
01361         return(*this);
01362       }
01363 
01364       reference
01365       operator*()
01366       {
01367         _M_check();
01368         if (0 == this->_M_buf_ptr)
01369           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01370                                                       this->_M_current_pos);
01371         else
01372           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01373                                                       this->_M_current_pos,
01374                                                       *this->_M_buf_ptr);
01375       }
01376 
01377       // See above comment.
01378       reference
01379       operator*() const
01380       {
01381         return *const_cast<_Rope_iterator&>(*this);
01382       }
01383 
01384       _Rope_iterator&
01385       operator++()
01386       {
01387         this->_M_incr(1);
01388         return *this;
01389       }
01390 
01391       _Rope_iterator&
01392       operator+=(ptrdiff_t __n)
01393       {
01394         if (__n >= 0)
01395           this->_M_incr(__n);
01396         else
01397           this->_M_decr(-__n);
01398         return *this;
01399       }
01400 
01401       _Rope_iterator&
01402       operator--()
01403       {
01404         this->_M_decr(1);
01405         return *this;
01406       }
01407 
01408       _Rope_iterator&
01409       operator-=(ptrdiff_t __n)
01410       {
01411         if (__n >= 0)
01412           this->_M_decr(__n);
01413         else
01414           this->_M_incr(-__n);
01415         return *this;
01416       }
01417 
01418       _Rope_iterator
01419       operator++(int)
01420       {
01421         size_t __old_pos = this->_M_current_pos;
01422         this->_M_incr(1);
01423         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
01424       }
01425 
01426       _Rope_iterator
01427       operator--(int)
01428       {
01429         size_t __old_pos = this->_M_current_pos;
01430         this->_M_decr(1);
01431         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
01432       }
01433 
01434       reference
01435       operator[](ptrdiff_t __n)
01436       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01437                                                     this->_M_current_pos
01438                                                     + __n); }
01439 
01440       template<class _CharT2, class _Alloc2>
01441         friend bool
01442         operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01443                    const _Rope_iterator<_CharT2, _Alloc2>& __y);
01444 
01445       template<class _CharT2, class _Alloc2>
01446         friend bool
01447         operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01448                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
01449 
01450       template<class _CharT2, class _Alloc2>
01451         friend ptrdiff_t
01452         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01453                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
01454 
01455       template<class _CharT2, class _Alloc2>
01456         friend _Rope_iterator<_CharT2, _Alloc2>
01457         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
01458 
01459       template<class _CharT2, class _Alloc2>
01460         friend _Rope_iterator<_CharT2, _Alloc2>
01461         operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
01462 
01463       template<class _CharT2, class _Alloc2>
01464         friend _Rope_iterator<_CharT2, _Alloc2>
01465         operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
01466     };
01467 
01468 
01469   template <class _CharT, class _Alloc>
01470     struct _Rope_base
01471     : public _Alloc
01472     {
01473       typedef _Alloc allocator_type;
01474 
01475       allocator_type
01476       get_allocator() const
01477       { return *static_cast<const _Alloc*>(this); }
01478 
01479       allocator_type&
01480       _M_get_allocator()
01481       { return *static_cast<_Alloc*>(this); }
01482 
01483       const allocator_type&
01484       _M_get_allocator() const
01485       { return *static_cast<const _Alloc*>(this); }
01486 
01487       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01488       // The one in _Base may not be visible due to template rules.
01489 
01490       _Rope_base(_RopeRep* __t, const allocator_type&)
01491       : _M_tree_ptr(__t) { }
01492 
01493       _Rope_base(const allocator_type&) { }
01494 
01495       // The only data member of a rope:
01496       _RopeRep *_M_tree_ptr;
01497 
01498 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
01499         typedef typename \
01500           _Alloc::template rebind<_Tp>::other __name##Alloc; \
01501         static _Tp* __name##_allocate(size_t __n) \
01502           { return __name##Alloc().allocate(__n); } \
01503         static void __name##_deallocate(_Tp *__p, size_t __n) \
01504           { __name##Alloc().deallocate(__p, __n); }
01505       __ROPE_DEFINE_ALLOCS(_Alloc)
01506 #undef __ROPE_DEFINE_ALLOC
01507 
01508         protected:
01509       _Rope_base&
01510       operator=(const _Rope_base&);
01511       
01512       _Rope_base(const _Rope_base&);
01513     };
01514 
01515   /**
01516    *  This is an SGI extension.
01517    *  @ingroup SGIextensions
01518    *  @doctodo
01519    */
01520   template <class _CharT, class _Alloc>
01521     class rope : public _Rope_base<_CharT, _Alloc>
01522     {
01523     public:
01524       typedef _CharT value_type;
01525       typedef ptrdiff_t difference_type;
01526       typedef size_t size_type;
01527       typedef _CharT const_reference;
01528       typedef const _CharT* const_pointer;
01529       typedef _Rope_iterator<_CharT, _Alloc> iterator;
01530       typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
01531       typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
01532       typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
01533 
01534       friend class _Rope_iterator<_CharT, _Alloc>;
01535       friend class _Rope_const_iterator<_CharT, _Alloc>;
01536       friend struct _Rope_RopeRep<_CharT, _Alloc>;
01537       friend class _Rope_iterator_base<_CharT, _Alloc>;
01538       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
01539       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
01540       friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
01541 
01542     protected:
01543       typedef _Rope_base<_CharT, _Alloc> _Base;
01544       typedef typename _Base::allocator_type allocator_type;
01545       using _Base::_M_tree_ptr;
01546       using _Base::get_allocator;
01547       using _Base::_M_get_allocator;
01548       typedef __GC_CONST _CharT* _Cstrptr;
01549       
01550       static _CharT _S_empty_c_str[1];
01551       
01552       static bool
01553       _S_is0(_CharT __c)
01554       { return __c == _S_eos((_CharT*)0); }
01555       
01556       enum { _S_copy_max = 23 };
01557                 // For strings shorter than _S_copy_max, we copy to
01558                 // concatenate.
01559 
01560       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01561       typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
01562       typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
01563       typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
01564       typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
01565 
01566       // Retrieve a character at the indicated position.
01567       static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
01568 
01569 #ifndef __GC
01570       // Obtain a pointer to the character at the indicated position.
01571       // The pointer can be used to change the character.
01572       // If such a pointer cannot be produced, as is frequently the
01573       // case, 0 is returned instead.
01574       // (Returns nonzero only if all nodes in the path have a refcount
01575       // of 1.)
01576       static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
01577 #endif
01578 
01579       static bool
01580       _S_apply_to_pieces(// should be template parameter
01581                          _Rope_char_consumer<_CharT>& __c,
01582                          const _RopeRep* __r,
01583                          size_t __begin, size_t __end);
01584                          // begin and end are assumed to be in range.
01585 
01586 #ifndef __GC
01587       static void
01588       _S_unref(_RopeRep* __t)
01589       { _RopeRep::_S_unref(__t); }
01590 
01591       static void
01592       _S_ref(_RopeRep* __t)
01593       { _RopeRep::_S_ref(__t); }
01594 
01595 #else /* __GC */
01596       static void _S_unref(_RopeRep*) { }
01597       static void _S_ref(_RopeRep*) { }
01598 #endif
01599 
01600 #ifdef __GC
01601       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
01602 #else
01603       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
01604 #endif
01605 
01606       // _Result is counted in refcount.
01607       static _RopeRep* _S_substring(_RopeRep* __base,
01608                                     size_t __start, size_t __endp1);
01609 
01610       static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
01611                                            const _CharT* __iter, size_t __slen);
01612       // Concatenate rope and char ptr, copying __s.
01613       // Should really take an arbitrary iterator.
01614       // Result is counted in refcount.
01615       static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
01616                                                  const _CharT* __iter,
01617                                                  size_t __slen)
01618         // As above, but one reference to __r is about to be
01619         // destroyed.  Thus the pieces may be recycled if all
01620         // relevant reference counts are 1.
01621 #ifdef __GC
01622         // We can't really do anything since refcounts are unavailable.
01623       { return _S_concat_char_iter(__r, __iter, __slen); }
01624 #else
01625       ;
01626 #endif
01627 
01628       static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
01629       // General concatenation on _RopeRep.  _Result
01630       // has refcount of 1.  Adjusts argument refcounts.
01631 
01632    public:
01633       void
01634       apply_to_pieces(size_t __begin, size_t __end,
01635                       _Rope_char_consumer<_CharT>& __c) const
01636       { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
01637 
01638    protected:
01639 
01640       static size_t
01641       _S_rounded_up_size(size_t __n)
01642       { return _RopeLeaf::_S_rounded_up_size(__n); }
01643 
01644       static size_t
01645       _S_allocated_capacity(size_t __n)
01646       {
01647         if (_S_is_basic_char_type((_CharT*)0))
01648           return _S_rounded_up_size(__n) - 1;
01649         else
01650           return _S_rounded_up_size(__n);
01651         
01652       }
01653 
01654       // Allocate and construct a RopeLeaf using the supplied allocator
01655       // Takes ownership of s instead of copying.
01656       static _RopeLeaf*
01657       _S_new_RopeLeaf(__GC_CONST _CharT *__s,
01658                       size_t __size, allocator_type& __a)
01659       {
01660         _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
01661         return new(__space) _RopeLeaf(__s, __size, __a);
01662       }
01663 
01664       static _RopeConcatenation*
01665       _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
01666                                allocator_type& __a)
01667       {
01668         _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
01669         return new(__space) _RopeConcatenation(__left, __right, __a);
01670       }
01671 
01672       static _RopeFunction*
01673       _S_new_RopeFunction(char_producer<_CharT>* __f,
01674                           size_t __size, bool __d, allocator_type& __a)
01675       {
01676         _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
01677         return new(__space) _RopeFunction(__f, __size, __d, __a);
01678       }
01679 
01680       static _RopeSubstring*
01681       _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
01682                            size_t __l, allocator_type& __a)
01683       {
01684         _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
01685         return new(__space) _RopeSubstring(__b, __s, __l, __a);
01686       }
01687       
01688       static _RopeLeaf*
01689       _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
01690                                         size_t __size, allocator_type& __a)
01691 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
01692                 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
01693       {
01694         if (0 == __size)
01695           return 0;
01696         _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
01697         
01698         __uninitialized_copy_n_a(__s, __size, __buf, __a);
01699         _S_cond_store_eos(__buf[__size]);
01700         __try
01701           { return _S_new_RopeLeaf(__buf, __size, __a); }
01702         __catch(...)
01703           {
01704             _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
01705             __throw_exception_again;
01706           }
01707       }
01708 
01709       // Concatenation of nonempty strings.
01710       // Always builds a concatenation node.
01711       // Rebalances if the result is too deep.
01712       // Result has refcount 1.
01713       // Does not increment left and right ref counts even though
01714       // they are referenced.
01715       static _RopeRep*
01716       _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
01717 
01718       // Concatenation helper functions
01719       static _RopeLeaf*
01720       _S_leaf_concat_char_iter(_RopeLeaf* __r,
01721                                const _CharT* __iter, size_t __slen);
01722       // Concatenate by copying leaf.
01723       // should take an arbitrary iterator
01724       // result has refcount 1.
01725 #ifndef __GC
01726       static _RopeLeaf*
01727       _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
01728                                      const _CharT* __iter, size_t __slen);
01729       // A version that potentially clobbers __r if __r->_M_ref_count == 1.
01730 #endif
01731 
01732     private:
01733       
01734       static size_t _S_char_ptr_len(const _CharT* __s);
01735       // slightly generalized strlen
01736 
01737       rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
01738       : _Base(__t, __a) { }
01739 
01740 
01741       // Copy __r to the _CharT buffer.
01742       // Returns __buffer + __r->_M_size.
01743       // Assumes that buffer is uninitialized.
01744       static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
01745 
01746       // Again, with explicit starting position and length.
01747       // Assumes that buffer is uninitialized.
01748       static _CharT* _S_flatten(_RopeRep* __r,
01749                                 size_t __start, size_t __len,
01750                                 _CharT* __buffer);
01751 
01752       static const unsigned long
01753       _S_min_len[__detail::_S_max_rope_depth + 1];
01754       
01755       static bool
01756       _S_is_balanced(_RopeRep* __r)
01757       { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
01758 
01759       static bool
01760       _S_is_almost_balanced(_RopeRep* __r)
01761       { return (__r->_M_depth == 0
01762                 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
01763 
01764       static bool
01765       _S_is_roughly_balanced(_RopeRep* __r)
01766       { return (__r->_M_depth <= 1
01767                 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
01768 
01769       // Assumes the result is not empty.
01770       static _RopeRep*
01771       _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
01772       {
01773         _RopeRep* __result = _S_concat(__left, __right);
01774         if (_S_is_balanced(__result))
01775           __result->_M_is_balanced = true;
01776         return __result;
01777       }
01778 
01779       // The basic rebalancing operation.  Logically copies the
01780       // rope.  The result has refcount of 1.  The client will
01781       // usually decrement the reference count of __r.
01782       // The result is within height 2 of balanced by the above
01783       // definition.
01784       static _RopeRep* _S_balance(_RopeRep* __r);
01785 
01786       // Add all unbalanced subtrees to the forest of balanced trees.
01787       // Used only by balance.
01788       static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
01789 
01790       // Add __r to forest, assuming __r is already balanced.
01791       static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
01792       
01793       // Print to stdout, exposing structure
01794       static void _S_dump(_RopeRep* __r, int __indent = 0);
01795       
01796       // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
01797       static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
01798       
01799     public:
01800       bool
01801       empty() const
01802       { return 0 == this->_M_tree_ptr; }
01803       
01804       // Comparison member function.  This is public only for those
01805       // clients that need a ternary comparison.  Others
01806       // should use the comparison operators below.
01807       int
01808       compare(const rope& __y) const
01809       { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
01810 
01811       rope(const _CharT* __s, const allocator_type& __a = allocator_type())
01812       : _Base(__a)
01813       {
01814         this->_M_tree_ptr =
01815           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
01816                                            _M_get_allocator());
01817       }
01818 
01819       rope(const _CharT* __s, size_t __len,
01820            const allocator_type& __a = allocator_type())
01821       : _Base(__a)
01822       {
01823         this->_M_tree_ptr =
01824           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
01825       }
01826 
01827       // Should perhaps be templatized with respect to the iterator type
01828       // and use Sequence_buffer.  (It should perhaps use sequence_buffer
01829       // even now.)
01830       rope(const _CharT* __s, const _CharT* __e,
01831            const allocator_type& __a = allocator_type())
01832       : _Base(__a)
01833       {
01834         this->_M_tree_ptr =
01835           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
01836       }
01837 
01838       rope(const const_iterator& __s, const const_iterator& __e,
01839            const allocator_type& __a = allocator_type())
01840       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
01841                            __e._M_current_pos), __a)
01842       { }
01843 
01844       rope(const iterator& __s, const iterator& __e,
01845            const allocator_type& __a = allocator_type())
01846       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
01847                            __e._M_current_pos), __a)
01848       { }
01849 
01850       rope(_CharT __c, const allocator_type& __a = allocator_type())
01851       : _Base(__a)
01852       {
01853         _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
01854         
01855         _M_get_allocator().construct(__buf, __c);
01856         __try
01857           {
01858             this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
01859                                                 _M_get_allocator());
01860           }
01861         __catch(...)
01862           {
01863             _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
01864             __throw_exception_again;
01865           }
01866       }
01867 
01868       rope(size_t __n, _CharT __c,
01869            const allocator_type& __a = allocator_type());
01870 
01871       rope(const allocator_type& __a = allocator_type())
01872       : _Base(0, __a) { }
01873 
01874       // Construct a rope from a function that can compute its members
01875       rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
01876            const allocator_type& __a = allocator_type())
01877       : _Base(__a)
01878       {
01879         this->_M_tree_ptr = (0 == __len)
01880           ? 0
01881           : _S_new_RopeFunction(__fn, __len, __delete_fn, _M_get_allocator());
01882       }
01883 
01884       rope(const rope& __x, const allocator_type& __a = allocator_type())
01885       : _Base(__x._M_tree_ptr, __a)
01886       { _S_ref(this->_M_tree_ptr); }
01887 
01888       ~rope() throw()
01889       { _S_unref(this->_M_tree_ptr); }
01890 
01891       rope&
01892       operator=(const rope& __x)
01893       {
01894         _RopeRep* __old = this->_M_tree_ptr;
01895         this->_M_tree_ptr = __x._M_tree_ptr;
01896         _S_ref(this->_M_tree_ptr);
01897         _S_unref(__old);
01898         return *this;
01899       }
01900 
01901       void
01902       clear()
01903       {
01904         _S_unref(this->_M_tree_ptr);
01905         this->_M_tree_ptr = 0;
01906       }
01907       
01908       void
01909       push_back(_CharT __x)
01910       {
01911         _RopeRep* __old = this->_M_tree_ptr;
01912         this->_M_tree_ptr
01913           = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
01914         _S_unref(__old);
01915       }
01916 
01917       void
01918       pop_back()
01919       {
01920         _RopeRep* __old = this->_M_tree_ptr;
01921         this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
01922                                          0, this->_M_tree_ptr->_M_size - 1);
01923         _S_unref(__old);
01924       }
01925 
01926       _CharT
01927       back() const
01928       { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
01929 
01930       void
01931       push_front(_CharT __x)
01932       {
01933         _RopeRep* __old = this->_M_tree_ptr;
01934         _RopeRep* __left =
01935           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
01936         __try
01937           {
01938             this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
01939             _S_unref(__old);
01940             _S_unref(__left);
01941           }
01942         __catch(...)
01943           {
01944             _S_unref(__left);
01945             __throw_exception_again;
01946           }
01947       }
01948 
01949       void
01950       pop_front()
01951       {
01952         _RopeRep* __old = this->_M_tree_ptr;
01953         this->_M_tree_ptr
01954           = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
01955         _S_unref(__old);
01956       }
01957 
01958       _CharT
01959       front() const
01960       { return _S_fetch(this->_M_tree_ptr, 0); }
01961 
01962       void
01963       balance()
01964       {
01965         _RopeRep* __old = this->_M_tree_ptr;
01966         this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
01967         _S_unref(__old);
01968       }
01969 
01970       void
01971       copy(_CharT* __buffer) const
01972       {
01973         _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
01974         _S_flatten(this->_M_tree_ptr, __buffer);
01975       }
01976 
01977       // This is the copy function from the standard, but
01978       // with the arguments reordered to make it consistent with the
01979       // rest of the interface.
01980       // Note that this guaranteed not to compile if the draft standard
01981       // order is assumed.
01982       size_type
01983       copy(size_type __pos, size_type __n, _CharT* __buffer) const
01984       {
01985         size_t __size = size();
01986         size_t __len = (__pos + __n > __size? __size - __pos : __n);
01987 
01988         _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
01989         _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
01990         return __len;
01991       }
01992 
01993       // Print to stdout, exposing structure.  May be useful for
01994       // performance debugging.
01995       void
01996       dump()
01997       { _S_dump(this->_M_tree_ptr); }
01998       
01999       // Convert to 0 terminated string in new allocated memory.
02000       // Embedded 0s in the input do not terminate the copy.
02001       const _CharT* c_str() const;
02002 
02003       // As above, but also use the flattened representation as
02004       // the new rope representation.
02005       const _CharT* replace_with_c_str();
02006       
02007       // Reclaim memory for the c_str generated flattened string.
02008       // Intentionally undocumented, since it's hard to say when this
02009       // is safe for multiple threads.
02010       void
02011       delete_c_str ()
02012       {
02013         if (0 == this->_M_tree_ptr)
02014           return;
02015         if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
02016             ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
02017             this->_M_tree_ptr->_M_c_string)
02018           {
02019             // Representation shared
02020             return;
02021           }
02022 #ifndef __GC
02023         this->_M_tree_ptr->_M_free_c_string();
02024 #endif
02025         this->_M_tree_ptr->_M_c_string = 0;
02026       }
02027 
02028       _CharT
02029       operator[] (size_type __pos) const
02030       { return _S_fetch(this->_M_tree_ptr, __pos); }
02031 
02032       _CharT
02033       at(size_type __pos) const
02034       {
02035         // if (__pos >= size()) throw out_of_range;  // XXX
02036         return (*this)[__pos];
02037       }
02038 
02039       const_iterator
02040       begin() const
02041       { return(const_iterator(this->_M_tree_ptr, 0)); }
02042 
02043       // An easy way to get a const iterator from a non-const container.
02044       const_iterator
02045       const_begin() const
02046       { return(const_iterator(this->_M_tree_ptr, 0)); }
02047 
02048       const_iterator
02049       end() const
02050       { return(const_iterator(this->_M_tree_ptr, size())); }
02051 
02052       const_iterator
02053       const_end() const
02054       { return(const_iterator(this->_M_tree_ptr, size())); }
02055 
02056       size_type
02057       size() const
02058       { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
02059       
02060       size_type
02061       length() const
02062       { return size(); }
02063 
02064       size_type
02065       max_size() const
02066       {
02067         return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
02068         //  Guarantees that the result can be sufficiently
02069         //  balanced.  Longer ropes will probably still work,
02070         //  but it's harder to make guarantees.
02071       }
02072 
02073       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
02074 
02075       const_reverse_iterator
02076       rbegin() const
02077       { return const_reverse_iterator(end()); }
02078 
02079       const_reverse_iterator
02080       const_rbegin() const
02081       { return const_reverse_iterator(end()); }
02082 
02083       const_reverse_iterator
02084       rend() const
02085       { return const_reverse_iterator(begin()); }
02086       
02087       const_reverse_iterator
02088       const_rend() const
02089       { return const_reverse_iterator(begin()); }
02090 
02091       template<class _CharT2, class _Alloc2>
02092         friend rope<_CharT2, _Alloc2>
02093         operator+(const rope<_CharT2, _Alloc2>& __left,
02094                   const rope<_CharT2, _Alloc2>& __right);
02095 
02096       template<class _CharT2, class _Alloc2>
02097         friend rope<_CharT2, _Alloc2>
02098         operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
02099 
02100       template<class _CharT2, class _Alloc2>
02101         friend rope<_CharT2, _Alloc2>
02102         operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
02103 
02104       // The symmetric cases are intentionally omitted, since they're
02105       // presumed to be less common, and we don't handle them as well.
02106 
02107       // The following should really be templatized.  The first
02108       // argument should be an input iterator or forward iterator with
02109       // value_type _CharT.
02110       rope&
02111       append(const _CharT* __iter, size_t __n)
02112       {
02113         _RopeRep* __result =
02114           _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
02115         _S_unref(this->_M_tree_ptr);
02116         this->_M_tree_ptr = __result;
02117         return *this;
02118       }
02119 
02120       rope&
02121       append(const _CharT* __c_string)
02122       {
02123         size_t __len = _S_char_ptr_len(__c_string);
02124         append(__c_string, __len);
02125         return(*this);
02126       }
02127 
02128       rope&
02129       append(const _CharT* __s, const _CharT* __e)
02130       {
02131         _RopeRep* __result =
02132           _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
02133         _S_unref(this->_M_tree_ptr);
02134         this->_M_tree_ptr = __result;
02135         return *this;
02136       }
02137 
02138       rope&
02139       append(const_iterator __s, const_iterator __e)
02140       {
02141         _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
02142                                                    __s._M_current_pos,
02143                                                    __e._M_current_pos));
02144         _RopeRep* __result = _S_concat(this->_M_tree_ptr, 
02145                                        (_RopeRep*)__appendee);
02146         _S_unref(this->_M_tree_ptr);
02147         this->_M_tree_ptr = __result;
02148         return *this;
02149       }
02150 
02151       rope&
02152       append(_CharT __c)
02153       {
02154         _RopeRep* __result =
02155           _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
02156         _S_unref(this->_M_tree_ptr);
02157         this->_M_tree_ptr = __result;
02158         return *this;
02159       }
02160 
02161       rope&
02162       append()
02163       { return append(_CharT()); }  // XXX why?
02164 
02165       rope&
02166       append(const rope& __y)
02167       {
02168         _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
02169         _S_unref(this->_M_tree_ptr);
02170         this->_M_tree_ptr = __result;
02171         return *this;
02172       }
02173 
02174       rope&
02175       append(size_t __n, _CharT __c)
02176       {
02177         rope<_CharT,_Alloc> __last(__n, __c);
02178         return append(__last);
02179       }
02180 
02181       void
02182       swap(rope& __b)
02183       {
02184         _RopeRep* __tmp = this->_M_tree_ptr;
02185         this->_M_tree_ptr = __b._M_tree_ptr;
02186         __b._M_tree_ptr = __tmp;
02187       }
02188 
02189     protected:
02190       // Result is included in refcount.
02191       static _RopeRep*
02192       replace(_RopeRep* __old, size_t __pos1,
02193               size_t __pos2, _RopeRep* __r)
02194       {
02195         if (0 == __old)
02196           {
02197             _S_ref(__r);
02198             return __r;
02199           }
02200         _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
02201         _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
02202         _RopeRep* __result;
02203 
02204         if (0 == __r)
02205           __result = _S_concat(__left, __right);
02206         else
02207           {
02208             _Self_destruct_ptr __left_result(_S_concat(__left, __r));
02209             __result = _S_concat(__left_result, __right);
02210           }
02211         return __result;
02212       }
02213 
02214     public:
02215       void
02216       insert(size_t __p, const rope& __r)
02217       {
02218         _RopeRep* __result =
02219           replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
02220         _S_unref(this->_M_tree_ptr);
02221         this->_M_tree_ptr = __result;
02222       }
02223 
02224       void
02225       insert(size_t __p, size_t __n, _CharT __c)
02226       {
02227         rope<_CharT,_Alloc> __r(__n,__c);
02228         insert(__p, __r);
02229       }
02230       
02231       void
02232       insert(size_t __p, const _CharT* __i, size_t __n)
02233       {
02234         _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
02235         _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
02236                                                 __p, size()));
02237         _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
02238         // _S_ destr_concat_char_iter should be safe here.
02239         // But as it stands it's probably not a win, since __left
02240         // is likely to have additional references.
02241         _RopeRep* __result = _S_concat(__left_result, __right);
02242         _S_unref(this->_M_tree_ptr);
02243         this->_M_tree_ptr = __result;
02244       }
02245 
02246       void
02247       insert(size_t __p, const _CharT* __c_string)
02248       { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
02249 
02250       void
02251       insert(size_t __p, _CharT __c)
02252       { insert(__p, &__c, 1); }
02253 
02254       void
02255       insert(size_t __p)
02256       {
02257         _CharT __c = _CharT();
02258         insert(__p, &__c, 1);
02259       }
02260 
02261       void
02262       insert(size_t __p, const _CharT* __i, const _CharT* __j)
02263       {
02264         rope __r(__i, __j);
02265         insert(__p, __r);
02266       }
02267 
02268       void
02269       insert(size_t __p, const const_iterator& __i,
02270              const const_iterator& __j)
02271       {
02272         rope __r(__i, __j);
02273         insert(__p, __r);
02274       }
02275 
02276       void
02277       insert(size_t __p, const iterator& __i,
02278              const iterator& __j)
02279       {
02280         rope __r(__i, __j);
02281         insert(__p, __r);
02282       }
02283 
02284       // (position, length) versions of replace operations:
02285       
02286       void
02287       replace(size_t __p, size_t __n, const rope& __r)
02288       {
02289         _RopeRep* __result =
02290           replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
02291         _S_unref(this->_M_tree_ptr);
02292         this->_M_tree_ptr = __result;
02293       }
02294 
02295       void
02296       replace(size_t __p, size_t __n,
02297               const _CharT* __i, size_t __i_len)
02298       {
02299         rope __r(__i, __i_len);
02300         replace(__p, __n, __r);
02301       }
02302 
02303       void
02304       replace(size_t __p, size_t __n, _CharT __c)
02305       {
02306         rope __r(__c);
02307         replace(__p, __n, __r);
02308       }
02309 
02310       void
02311       replace(size_t __p, size_t __n, const _CharT* __c_string)
02312       {
02313         rope __r(__c_string);
02314         replace(__p, __n, __r);
02315       }
02316       
02317       void
02318       replace(size_t __p, size_t __n,
02319               const _CharT* __i, const _CharT* __j)
02320       {
02321         rope __r(__i, __j);
02322         replace(__p, __n, __r);
02323       }
02324       
02325       void
02326       replace(size_t __p, size_t __n,
02327               const const_iterator& __i, const const_iterator& __j)
02328       {
02329         rope __r(__i, __j);
02330         replace(__p, __n, __r);
02331       }
02332 
02333       void
02334       replace(size_t __p, size_t __n,
02335               const iterator& __i, const iterator& __j)
02336       {
02337         rope __r(__i, __j);
02338         replace(__p, __n, __r);
02339       }
02340 
02341       // Single character variants:
02342       void
02343       replace(size_t __p, _CharT __c)
02344       {
02345         iterator __i(this, __p);
02346         *__i = __c;
02347       }
02348 
02349       void
02350       replace(size_t __p, const rope& __r)
02351       { replace(__p, 1, __r); }
02352 
02353       void
02354       replace(size_t __p, const _CharT* __i, size_t __i_len)
02355       { replace(__p, 1, __i, __i_len); }
02356 
02357       void
02358       replace(size_t __p, const _CharT* __c_string)
02359       { replace(__p, 1, __c_string); }
02360 
02361       void
02362       replace(size_t __p, const _CharT* __i, const _CharT* __j)
02363       { replace(__p, 1, __i, __j); }
02364 
02365       void
02366       replace(size_t __p, const const_iterator& __i,
02367               const const_iterator& __j)
02368       { replace(__p, 1, __i, __j); }
02369 
02370       void
02371       replace(size_t __p, const iterator& __i,
02372               const iterator& __j)
02373       { replace(__p, 1, __i, __j); }
02374 
02375       // Erase, (position, size) variant.
02376       void
02377       erase(size_t __p, size_t __n)
02378       {
02379         _RopeRep* __result = replace(this->_M_tree_ptr, __p,
02380                                      __p + __n, 0);
02381         _S_unref(this->_M_tree_ptr);
02382         this->_M_tree_ptr = __result;
02383       }
02384 
02385       // Erase, single character
02386       void
02387       erase(size_t __p)
02388       { erase(__p, __p + 1); }
02389 
02390       // Insert, iterator variants.
02391       iterator
02392       insert(const iterator& __p, const rope& __r)
02393       {
02394         insert(__p.index(), __r);
02395         return __p;
02396       }
02397 
02398       iterator
02399       insert(const iterator& __p, size_t __n, _CharT __c)
02400       {
02401         insert(__p.index(), __n, __c);
02402         return __p;
02403       }
02404 
02405       iterator insert(const iterator& __p, _CharT __c)
02406       {
02407         insert(__p.index(), __c);
02408         return __p;
02409       }
02410       
02411       iterator
02412       insert(const iterator& __p )
02413       {
02414         insert(__p.index());
02415         return __p;
02416       }
02417       
02418       iterator
02419       insert(const iterator& __p, const _CharT* c_string)
02420       {
02421         insert(__p.index(), c_string);
02422         return __p;
02423       }
02424       
02425       iterator
02426       insert(const iterator& __p, const _CharT* __i, size_t __n)
02427       {
02428         insert(__p.index(), __i, __n);
02429         return __p;
02430       }
02431       
02432       iterator
02433       insert(const iterator& __p, const _CharT* __i,
02434              const _CharT* __j)
02435       {
02436         insert(__p.index(), __i, __j); 
02437         return __p;
02438       }
02439       
02440       iterator
02441       insert(const iterator& __p,
02442              const const_iterator& __i, const const_iterator& __j)
02443       {
02444         insert(__p.index(), __i, __j);
02445         return __p;
02446       }
02447       
02448       iterator
02449       insert(const iterator& __p,
02450              const iterator& __i, const iterator& __j)
02451       {
02452         insert(__p.index(), __i, __j);
02453         return __p;
02454       }
02455 
02456       // Replace, range variants.
02457       void
02458       replace(const iterator& __p, const iterator& __q, const rope& __r)
02459       { replace(__p.index(), __q.index() - __p.index(), __r); }
02460 
02461       void
02462       replace(const iterator& __p, const iterator& __q, _CharT __c)
02463       { replace(__p.index(), __q.index() - __p.index(), __c); }
02464       
02465       void
02466       replace(const iterator& __p, const iterator& __q,
02467               const _CharT* __c_string)
02468       { replace(__p.index(), __q.index() - __p.index(), __c_string); }
02469       
02470       void
02471       replace(const iterator& __p, const iterator& __q,
02472               const _CharT* __i, size_t __n)
02473       { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
02474       
02475       void
02476       replace(const iterator& __p, const iterator& __q,
02477               const _CharT* __i, const _CharT* __j)
02478       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02479       
02480       void
02481       replace(const iterator& __p, const iterator& __q,
02482               const const_iterator& __i, const const_iterator& __j)
02483       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02484       
02485       void
02486       replace(const iterator& __p, const iterator& __q,
02487               const iterator& __i, const iterator& __j)
02488       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02489 
02490       // Replace, iterator variants.
02491       void
02492       replace(const iterator& __p, const rope& __r)
02493       { replace(__p.index(), __r); }
02494       
02495       void
02496       replace(const iterator& __p, _CharT __c)
02497       { replace(__p.index(), __c); }
02498       
02499       void
02500       replace(const iterator& __p, const _CharT* __c_string)
02501       { replace(__p.index(), __c_string); }
02502       
02503       void
02504       replace(const iterator& __p, const _CharT* __i, size_t __n)
02505       { replace(__p.index(), __i, __n); }
02506       
02507       void
02508       replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
02509       { replace(__p.index(), __i, __j); }
02510       
02511       void
02512       replace(const iterator& __p, const_iterator __i, const_iterator __j)
02513       { replace(__p.index(), __i, __j); }
02514       
02515       void
02516       replace(const iterator& __p, iterator __i, iterator __j)
02517       { replace(__p.index(), __i, __j); }
02518 
02519       // Iterator and range variants of erase
02520       iterator
02521       erase(const iterator& __p, const iterator& __q)
02522       {
02523         size_t __p_index = __p.index();
02524         erase(__p_index, __q.index() - __p_index);
02525         return iterator(this, __p_index);
02526       }
02527 
02528       iterator
02529       erase(const iterator& __p)
02530       {
02531         size_t __p_index = __p.index();
02532         erase(__p_index, 1);
02533         return iterator(this, __p_index);
02534       }
02535 
02536       rope
02537       substr(size_t __start, size_t __len = 1) const
02538       {
02539         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02540                                                  __start,
02541                                                  __start + __len));
02542       }
02543 
02544       rope
02545       substr(iterator __start, iterator __end) const
02546       {
02547         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02548                                                  __start.index(),
02549                                                  __end.index()));
02550       }
02551 
02552       rope
02553       substr(iterator __start) const
02554       {
02555         size_t __pos = __start.index();
02556         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02557                                                  __pos, __pos + 1));
02558       }
02559 
02560       rope
02561       substr(const_iterator __start, const_iterator __end) const
02562       {
02563         // This might eventually take advantage of the cache in the
02564         // iterator.
02565         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02566                                                  __start.index(),
02567                                                  __end.index()));
02568       }
02569 
02570       rope<_CharT, _Alloc>
02571       substr(const_iterator __start)
02572       {
02573         size_t __pos = __start.index();
02574         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02575                                                  __pos, __pos + 1));
02576       }
02577 
02578       static const size_type npos;
02579 
02580       size_type find(_CharT __c, size_type __pos = 0) const;
02581 
02582       size_type
02583       find(const _CharT* __s, size_type __pos = 0) const
02584       {
02585         size_type __result_pos;
02586         const_iterator __result =
02587           std::search(const_begin() + __pos, const_end(),
02588                       __s, __s + _S_char_ptr_len(__s));
02589         __result_pos = __result.index();
02590 #ifndef __STL_OLD_ROPE_SEMANTICS
02591         if (__result_pos == size())
02592           __result_pos = npos;
02593 #endif
02594         return __result_pos;
02595       }
02596 
02597       iterator
02598       mutable_begin()
02599       { return(iterator(this, 0)); }
02600       
02601       iterator
02602       mutable_end()
02603       { return(iterator(this, size())); }
02604 
02605       typedef std::reverse_iterator<iterator> reverse_iterator;
02606       
02607       reverse_iterator
02608       mutable_rbegin()
02609       { return reverse_iterator(mutable_end()); }
02610 
02611       reverse_iterator
02612       mutable_rend()
02613       { return reverse_iterator(mutable_begin()); }
02614 
02615       reference
02616       mutable_reference_at(size_type __pos)
02617       { return reference(this, __pos); }
02618 
02619 #ifdef __STD_STUFF
02620       reference
02621       operator[] (size_type __pos)
02622       { return _char_ref_proxy(this, __pos); }
02623 
02624       reference
02625       at(size_type __pos)
02626       {
02627         // if (__pos >= size()) throw out_of_range;  // XXX
02628         return (*this)[__pos];
02629       }
02630       
02631       void resize(size_type __n, _CharT __c) { }
02632       void resize(size_type __n) { }
02633       void reserve(size_type __res_arg = 0) { }
02634       
02635       size_type
02636       capacity() const
02637       { return max_size(); }
02638 
02639       // Stuff below this line is dangerous because it's error prone.
02640       // I would really like to get rid of it.
02641       // copy function with funny arg ordering.
02642       size_type
02643       copy(_CharT* __buffer, size_type __n,
02644            size_type __pos = 0) const
02645       { return copy(__pos, __n, __buffer); }
02646 
02647       iterator
02648       end()
02649       { return mutable_end(); }
02650 
02651       iterator
02652       begin()
02653       { return mutable_begin(); }
02654 
02655       reverse_iterator
02656       rend()
02657       { return mutable_rend(); }
02658       
02659       reverse_iterator
02660       rbegin()
02661       { return mutable_rbegin(); }
02662 
02663 #else
02664       const_iterator
02665       end()
02666       { return const_end(); }
02667 
02668       const_iterator
02669       begin()
02670       { return const_begin(); }
02671 
02672       const_reverse_iterator
02673       rend()
02674       { return const_rend(); }
02675 
02676       const_reverse_iterator
02677       rbegin()
02678       { return const_rbegin(); }
02679 
02680 #endif
02681     };
02682 
02683   template <class _CharT, class _Alloc>
02684     const typename rope<_CharT, _Alloc>::size_type
02685     rope<_CharT, _Alloc>::npos = (size_type)(-1);
02686   
02687   template <class _CharT, class _Alloc>
02688     inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02689                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
02690     { return (__x._M_current_pos == __y._M_current_pos
02691               && __x._M_root == __y._M_root); }
02692 
02693   template <class _CharT, class _Alloc>
02694     inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02695                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
02696     { return (__x._M_current_pos < __y._M_current_pos); }
02697 
02698   template <class _CharT, class _Alloc>
02699     inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02700                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
02701     { return !(__x == __y); }
02702 
02703   template <class _CharT, class _Alloc>
02704     inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02705                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
02706     { return __y < __x; }
02707 
02708   template <class _CharT, class _Alloc>
02709     inline bool
02710     operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02711                const _Rope_const_iterator<_CharT, _Alloc>& __y)
02712     { return !(__y < __x); }
02713 
02714   template <class _CharT, class _Alloc>
02715     inline bool
02716     operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02717                const _Rope_const_iterator<_CharT, _Alloc>& __y)
02718     { return !(__x < __y); }
02719 
02720   template <class _CharT, class _Alloc>
02721     inline ptrdiff_t
02722     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02723               const _Rope_const_iterator<_CharT, _Alloc>& __y)
02724     { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
02725 
02726   template <class _CharT, class _Alloc>
02727     inline _Rope_const_iterator<_CharT, _Alloc>
02728     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02729     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02730                                                   __x._M_current_pos - __n); }
02731 
02732   template <class _CharT, class _Alloc>
02733     inline _Rope_const_iterator<_CharT, _Alloc>
02734     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02735     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02736                                                   __x._M_current_pos + __n); }
02737 
02738   template <class _CharT, class _Alloc>
02739     inline _Rope_const_iterator<_CharT, _Alloc>
02740     operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
02741   { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02742                                                 __x._M_current_pos + __n); }
02743 
02744   template <class _CharT, class _Alloc>
02745     inline bool
02746     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
02747                const _Rope_iterator<_CharT, _Alloc>& __y)
02748     {return (__x._M_current_pos == __y._M_current_pos
02749              && __x._M_root_rope == __y._M_root_rope); }
02750   
02751   template <class _CharT, class _Alloc>
02752     inline bool
02753     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
02754               const _Rope_iterator<_CharT, _Alloc>& __y)
02755     { return (__x._M_current_pos < __y._M_current_pos); }
02756 
02757   template <class _CharT, class _Alloc>
02758     inline bool
02759     operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
02760                const _Rope_iterator<_CharT, _Alloc>& __y)
02761     { return !(__x == __y); }
02762 
02763   template <class _CharT, class _Alloc>
02764     inline bool
02765     operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
02766               const _Rope_iterator<_CharT, _Alloc>& __y)
02767     { return __y < __x; }
02768 
02769   template <class _CharT, class _Alloc>
02770     inline bool
02771     operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
02772                const _Rope_iterator<_CharT, _Alloc>& __y)
02773     { return !(__y < __x); }
02774 
02775   template <class _CharT, class _Alloc>
02776     inline bool
02777     operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
02778                const _Rope_iterator<_CharT, _Alloc>& __y)
02779     { return !(__x < __y); }
02780 
02781   template <class _CharT, class _Alloc>
02782     inline ptrdiff_t
02783     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
02784               const _Rope_iterator<_CharT, _Alloc>& __y)
02785     { return ((ptrdiff_t)__x._M_current_pos
02786               - (ptrdiff_t)__y._M_current_pos); }
02787 
02788   template <class _CharT, class _Alloc>
02789     inline _Rope_iterator<_CharT, _Alloc>
02790     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
02791               ptrdiff_t __n)
02792     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02793                                             __x._M_current_pos - __n); }
02794 
02795   template <class _CharT, class _Alloc>
02796     inline _Rope_iterator<_CharT, _Alloc>
02797     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02798     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02799                                             __x._M_current_pos + __n); }
02800 
02801   template <class _CharT, class _Alloc>
02802     inline _Rope_iterator<_CharT, _Alloc>
02803     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
02804     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02805                                             __x._M_current_pos + __n); }
02806 
02807   template <class _CharT, class _Alloc>
02808     inline rope<_CharT, _Alloc>
02809     operator+(const rope<_CharT, _Alloc>& __left,
02810               const rope<_CharT, _Alloc>& __right)
02811     {
02812       // Inlining this should make it possible to keep __left and
02813       // __right in registers.
02814       typedef rope<_CharT, _Alloc> rope_type;
02815       return rope_type(rope_type::_S_concat(__left._M_tree_ptr, 
02816                                             __right._M_tree_ptr));
02817     }
02818 
02819   template <class _CharT, class _Alloc>
02820     inline rope<_CharT, _Alloc>&
02821     operator+=(rope<_CharT, _Alloc>& __left,
02822                const rope<_CharT, _Alloc>& __right)
02823     {
02824       __left.append(__right);
02825       return __left;
02826     }
02827 
02828   template <class _CharT, class _Alloc>
02829     inline rope<_CharT, _Alloc>
02830     operator+(const rope<_CharT, _Alloc>& __left,
02831               const _CharT* __right)
02832     {
02833       typedef rope<_CharT, _Alloc> rope_type;
02834       size_t __rlen = rope_type::_S_char_ptr_len(__right);
02835       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
02836                                                       __right, __rlen));
02837     }
02838 
02839   template <class _CharT, class _Alloc>
02840     inline rope<_CharT, _Alloc>&
02841     operator+=(rope<_CharT, _Alloc>& __left,
02842                const _CharT* __right)
02843     {
02844       __left.append(__right);
02845       return __left;
02846     }
02847 
02848   template <class _CharT, class _Alloc>
02849     inline rope<_CharT, _Alloc>
02850     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
02851     {
02852       typedef rope<_CharT, _Alloc> rope_type;
02853       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
02854                                                       &__right, 1));
02855     }
02856 
02857   template <class _CharT, class _Alloc>
02858     inline rope<_CharT, _Alloc>&
02859     operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
02860     {
02861       __left.append(__right);
02862       return __left;
02863     }
02864   
02865   template <class _CharT, class _Alloc>
02866     bool
02867     operator<(const rope<_CharT, _Alloc>& __left,
02868               const rope<_CharT, _Alloc>& __right)
02869     { return __left.compare(__right) < 0; }
02870 
02871   template <class _CharT, class _Alloc>
02872     bool
02873     operator==(const rope<_CharT, _Alloc>& __left,
02874                const rope<_CharT, _Alloc>& __right)
02875     { return __left.compare(__right) == 0; }
02876 
02877   template <class _CharT, class _Alloc>
02878     inline bool
02879     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
02880                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
02881     { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
02882 
02883   template <class _CharT, class _Alloc>
02884     inline bool
02885     operator!=(const rope<_CharT, _Alloc>& __x,
02886                const rope<_CharT, _Alloc>& __y)
02887     { return !(__x == __y); }
02888 
02889   template <class _CharT, class _Alloc>
02890     inline bool
02891     operator>(const rope<_CharT, _Alloc>& __x,
02892               const rope<_CharT, _Alloc>& __y)
02893     { return __y < __x; }
02894 
02895   template <class _CharT, class _Alloc>
02896     inline bool
02897     operator<=(const rope<_CharT, _Alloc>& __x,
02898                const rope<_CharT, _Alloc>& __y)
02899     { return !(__y < __x); }
02900 
02901   template <class _CharT, class _Alloc>
02902     inline bool
02903     operator>=(const rope<_CharT, _Alloc>& __x,
02904                const rope<_CharT, _Alloc>& __y)
02905     { return !(__x < __y); }
02906 
02907   template <class _CharT, class _Alloc>
02908     inline bool
02909     operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
02910                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
02911     { return !(__x == __y); }
02912 
02913   template<class _CharT, class _Traits, class _Alloc>
02914     std::basic_ostream<_CharT, _Traits>&
02915     operator<<(std::basic_ostream<_CharT, _Traits>& __o,
02916                const rope<_CharT, _Alloc>& __r);
02917 
02918   typedef rope<char> crope;
02919   typedef rope<wchar_t> wrope;
02920 
02921   inline crope::reference
02922   __mutable_reference_at(crope& __c, size_t __i)
02923   { return __c.mutable_reference_at(__i); }
02924 
02925   inline wrope::reference
02926   __mutable_reference_at(wrope& __c, size_t __i)
02927   { return __c.mutable_reference_at(__i); }
02928 
02929   template <class _CharT, class _Alloc>
02930     inline void
02931     swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
02932     { __x.swap(__y); }
02933 
02934 _GLIBCXX_END_NAMESPACE_VERSION
02935 } // namespace
02936 
02937 
02938 namespace std _GLIBCXX_VISIBILITY(default)
02939 { 
02940 namespace tr1
02941 {
02942 _GLIBCXX_BEGIN_NAMESPACE_VERSION
02943 
02944   template<>
02945     struct hash<__gnu_cxx::crope>
02946     {
02947       size_t
02948       operator()(const __gnu_cxx::crope& __str) const
02949       {
02950         size_t __size = __str.size();
02951         if (0 == __size)
02952           return 0;
02953         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
02954       }
02955     };
02956 
02957 
02958   template<>
02959     struct hash<__gnu_cxx::wrope>
02960     {
02961       size_t
02962       operator()(const __gnu_cxx::wrope& __str) const
02963       {
02964         size_t __size = __str.size();
02965         if (0 == __size)
02966           return 0;
02967         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
02968       }
02969     };
02970 
02971 _GLIBCXX_END_NAMESPACE_VERSION
02972 } // namespace tr1
02973 } // namespace std
02974 
02975 # include <ext/ropeimpl.h>
02976 
02977 #endif