libstdc++

rope

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