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