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