rope

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

Generated on Thu Jul 23 21:16:15 2009 for libstdc++ by  doxygen 1.5.8