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

Generated on Wed Mar 26 00:43:06 2008 for libstdc++ by  doxygen 1.5.1