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