rope

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

Generated on Thu Nov 1 13:12:22 2007 for libstdc++ by  doxygen 1.5.1