1// SGI's rope class -*- C++ -*-
2
3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 3, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/*
27 * Copyright (c) 1997
28 * Silicon Graphics Computer Systems, Inc.
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation.  Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose.  It is provided "as is" without express or implied warranty.
37 */
38
39/** @file ext/rope
40 *  This file is a GNU extension to the Standard C++ Library (possibly
41 *  containing extensions from the HP/SGI STL subset). 
42 */
43
44#ifndef _ROPE
45#define _ROPE 1
46
47#include <algorithm>
48#include <iosfwd>
49#include <bits/stl_construct.h>
50#include <bits/stl_uninitialized.h>
51#include <bits/stl_function.h>
52#include <bits/stl_numeric.h>
53#include <bits/allocator.h>
54#include <bits/gthr.h>
55#include <tr1/functional>
56
57# ifdef __GC
58#   define __GC_CONST const
59# else
60#   define __GC_CONST   // constant except for deallocation
61# endif
62
63#include <ext/memory> // For uninitialized_copy_n
64
65_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
66
67  namespace __detail
68  {
69    enum { _S_max_rope_depth = 45 };
70    enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
71  } // namespace __detail
72
73  using std::size_t;
74  using std::ptrdiff_t;
75  using std::allocator;
76  using std::_Destroy;
77
78  // See libstdc++/36832.
79  template<typename _ForwardIterator, typename _Allocator>
80    void
81    _Destroy_const(_ForwardIterator __first,
82		   _ForwardIterator __last, _Allocator __alloc)
83    {
84      for (; __first != __last; ++__first)
85	__alloc.destroy(&*__first);
86    }
87
88  template<typename _ForwardIterator, typename _Tp>
89    inline void
90    _Destroy_const(_ForwardIterator __first,
91		   _ForwardIterator __last, allocator<_Tp>)
92    { _Destroy(__first, __last); }
93
94  // The _S_eos function is used for those functions that
95  // convert to/from C-like strings to detect the end of the string.
96  
97  // The end-of-C-string character.
98  // This is what the draft standard says it should be.
99  template <class _CharT>
100    inline _CharT
101    _S_eos(_CharT*)
102    { return _CharT(); }
103
104  // Test for basic character types.
105  // For basic character types leaves having a trailing eos.
106  template <class _CharT>
107    inline bool
108    _S_is_basic_char_type(_CharT*)
109    { return false; }
110  
111  template <class _CharT>
112    inline bool
113    _S_is_one_byte_char_type(_CharT*)
114    { return false; }
115
116  inline bool
117  _S_is_basic_char_type(char*)
118  { return true; }
119  
120  inline bool
121  _S_is_one_byte_char_type(char*)
122  { return true; }
123  
124  inline bool
125  _S_is_basic_char_type(wchar_t*)
126  { return true; }
127
128  // Store an eos iff _CharT is a basic character type.
129  // Do not reference _S_eos if it isn't.
130  template <class _CharT>
131    inline void
132    _S_cond_store_eos(_CharT&) { }
133
134  inline void
135  _S_cond_store_eos(char& __c)
136  { __c = 0; }
137
138  inline void
139  _S_cond_store_eos(wchar_t& __c)
140  { __c = 0; }
141
142  // char_producers are logically functions that generate a section of
143  // a string.  These can be converted to ropes.  The resulting rope
144  // invokes the char_producer on demand.  This allows, for example,
145  // files to be viewed as ropes without reading the entire file.
146  template <class _CharT>
147    class char_producer
148    {
149    public:
150      virtual ~char_producer() { };
151
152      virtual void
153      operator()(size_t __start_pos, size_t __len,
154		 _CharT* __buffer) = 0;
155      // Buffer should really be an arbitrary output iterator.
156      // That way we could flatten directly into an ostream, etc.
157      // This is thoroughly impossible, since iterator types don't
158      // have runtime descriptions.
159    };
160
161  // Sequence buffers:
162  //
163  // Sequence must provide an append operation that appends an
164  // array to the sequence.  Sequence buffers are useful only if
165  // appending an entire array is cheaper than appending element by element.
166  // This is true for many string representations.
167  // This should  perhaps inherit from ostream<sequence::value_type>
168  // and be implemented correspondingly, so that they can be used
169  // for formatted.  For the sake of portability, we don't do this yet.
170  //
171  // For now, sequence buffers behave as output iterators.  But they also
172  // behave a little like basic_ostringstream<sequence::value_type> and a
173  // little like containers.
174
175  template<class _Sequence, size_t _Buf_sz = 100>
176    class sequence_buffer
177    : public std::iterator<std::output_iterator_tag, void, void, void, void>
178    {
179    public:
180      typedef typename _Sequence::value_type value_type;
181    protected:
182      _Sequence* _M_prefix;
183      value_type _M_buffer[_Buf_sz];
184      size_t     _M_buf_count;
185    public:
186
187      void
188      flush()
189      {
190	_M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
191	_M_buf_count = 0;
192      }
193      
194      ~sequence_buffer()
195      { flush(); }
196      
197      sequence_buffer()
198      : _M_prefix(0), _M_buf_count(0) { }
199
200      sequence_buffer(const sequence_buffer& __x)
201      {
202	_M_prefix = __x._M_prefix;
203	_M_buf_count = __x._M_buf_count;
204	std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
205      }
206      
207      sequence_buffer(sequence_buffer& __x)
208      {
209	__x.flush();
210	_M_prefix = __x._M_prefix;
211	_M_buf_count = 0;
212      }
213      
214      sequence_buffer(_Sequence& __s)
215      : _M_prefix(&__s), _M_buf_count(0) { }
216      
217      sequence_buffer&
218      operator=(sequence_buffer& __x)
219      {
220	__x.flush();
221	_M_prefix = __x._M_prefix;
222	_M_buf_count = 0;
223	return *this;
224      }
225
226      sequence_buffer&
227      operator=(const sequence_buffer& __x)
228      {
229	_M_prefix = __x._M_prefix;
230	_M_buf_count = __x._M_buf_count;
231	std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
232	return *this;
233      }
234      
235      void
236      push_back(value_type __x)
237      {
238	if (_M_buf_count < _Buf_sz)
239	  {
240	    _M_buffer[_M_buf_count] = __x;
241	    ++_M_buf_count;
242	  }
243	else
244	  {
245	    flush();
246	    _M_buffer[0] = __x;
247	    _M_buf_count = 1;
248	  }
249      }
250      
251      void
252      append(value_type* __s, size_t __len)
253      {
254	if (__len + _M_buf_count <= _Buf_sz)
255	  {
256	    size_t __i = _M_buf_count;
257	    for (size_t __j = 0; __j < __len; __i++, __j++)
258	      _M_buffer[__i] = __s[__j];
259	    _M_buf_count += __len;
260	  }
261	else if (0 == _M_buf_count)
262	  _M_prefix->append(__s, __s + __len);
263	else
264	  {
265	    flush();
266	    append(__s, __len);
267	  }
268      }
269
270      sequence_buffer&
271      write(value_type* __s, size_t __len)
272      {
273	append(__s, __len);
274	return *this;
275      }
276      
277      sequence_buffer&
278      put(value_type __x)
279      {
280	push_back(__x);
281	return *this;
282      }
283      
284      sequence_buffer&
285      operator=(const value_type& __rhs)
286      {
287	push_back(__rhs);
288	return *this;
289      }
290      
291      sequence_buffer&
292      operator*()
293      { return *this; }
294      
295      sequence_buffer&
296      operator++()
297      { return *this; }
298      
299      sequence_buffer
300      operator++(int)
301      { return *this; }
302    };
303  
304  // The following should be treated as private, at least for now.
305  template<class _CharT>
306    class _Rope_char_consumer
307    {
308    public:
309      // If we had member templates, these should not be virtual.
310      // For now we need to use run-time parametrization where
311      // compile-time would do.  Hence this should all be private
312      // for now.
313      // The symmetry with char_producer is accidental and temporary.
314      virtual ~_Rope_char_consumer() { };
315  
316      virtual bool
317      operator()(const _CharT* __buffer, size_t __len) = 0;
318    };
319  
320  // First a lot of forward declarations.  The standard seems to require
321  // much stricter "declaration before use" than many of the implementations
322  // that preceded it.
323  template<class _CharT, class _Alloc = allocator<_CharT> >
324    class rope;
325  
326  template<class _CharT, class _Alloc>
327    struct _Rope_RopeConcatenation;
328
329  template<class _CharT, class _Alloc>
330    struct _Rope_RopeLeaf;
331  
332  template<class _CharT, class _Alloc>
333    struct _Rope_RopeFunction;
334  
335  template<class _CharT, class _Alloc>
336    struct _Rope_RopeSubstring;
337  
338  template<class _CharT, class _Alloc>
339    class _Rope_iterator;
340  
341  template<class _CharT, class _Alloc>
342    class _Rope_const_iterator;
343  
344  template<class _CharT, class _Alloc>
345    class _Rope_char_ref_proxy;
346  
347  template<class _CharT, class _Alloc>
348    class _Rope_char_ptr_proxy;
349
350  template<class _CharT, class _Alloc>
351    bool
352    operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
353	       const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
354
355  template<class _CharT, class _Alloc>
356    _Rope_const_iterator<_CharT, _Alloc>
357    operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
358	      ptrdiff_t __n);
359
360  template<class _CharT, class _Alloc>
361    _Rope_const_iterator<_CharT, _Alloc>
362    operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
363	      ptrdiff_t __n);
364
365  template<class _CharT, class _Alloc>
366    _Rope_const_iterator<_CharT, _Alloc>
367    operator+(ptrdiff_t __n,
368	      const _Rope_const_iterator<_CharT, _Alloc>& __x);
369
370  template<class _CharT, class _Alloc>
371    bool
372    operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
373	       const _Rope_const_iterator<_CharT, _Alloc>& __y);
374
375  template<class _CharT, class _Alloc>
376    bool
377    operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
378	      const _Rope_const_iterator<_CharT, _Alloc>& __y);
379  
380  template<class _CharT, class _Alloc>
381    ptrdiff_t
382    operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
383	      const _Rope_const_iterator<_CharT, _Alloc>& __y);
384
385  template<class _CharT, class _Alloc>
386    _Rope_iterator<_CharT, _Alloc>
387    operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
388
389  template<class _CharT, class _Alloc>
390    _Rope_iterator<_CharT, _Alloc>
391    operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
392
393  template<class _CharT, class _Alloc>
394    _Rope_iterator<_CharT, _Alloc>
395    operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
396
397  template<class _CharT, class _Alloc>
398    bool
399    operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
400	       const _Rope_iterator<_CharT, _Alloc>& __y);
401
402  template<class _CharT, class _Alloc>
403    bool
404    operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
405	      const _Rope_iterator<_CharT, _Alloc>& __y);
406
407  template<class _CharT, class _Alloc>
408    ptrdiff_t
409    operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
410	      const _Rope_iterator<_CharT, _Alloc>& __y);
411
412  template<class _CharT, class _Alloc>
413    rope<_CharT, _Alloc>
414    operator+(const rope<_CharT, _Alloc>& __left,
415	      const rope<_CharT, _Alloc>& __right);
416
417  template<class _CharT, class _Alloc>
418    rope<_CharT, _Alloc>
419    operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
420
421  template<class _CharT, class _Alloc>
422    rope<_CharT, _Alloc>
423    operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
424
425  // Some helpers, so we can use power on ropes.
426  // See below for why this isn't local to the implementation.
427  
428  // This uses a nonstandard refcount convention.
429  // The result has refcount 0.
430  template<class _CharT, class _Alloc>
431    struct _Rope_Concat_fn
432    : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
433				  rope<_CharT, _Alloc> >
434    {
435      rope<_CharT, _Alloc>
436      operator()(const rope<_CharT, _Alloc>& __x,
437		 const rope<_CharT, _Alloc>& __y)
438      { return __x + __y; }
439    };
440
441  template <class _CharT, class _Alloc>
442    inline rope<_CharT, _Alloc>
443    identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
444    { return rope<_CharT, _Alloc>(); }
445
446  // Class _Refcount_Base provides a type, _RC_t, a data member,
447  // _M_ref_count, and member functions _M_incr and _M_decr, which perform
448  // atomic preincrement/predecrement.  The constructor initializes
449  // _M_ref_count.
450  struct _Refcount_Base
451  {
452    // The type _RC_t
453    typedef size_t _RC_t;
454    
455    // The data member _M_ref_count
456    volatile _RC_t _M_ref_count;
457
458    // Constructor
459    __gthread_mutex_t _M_ref_count_lock;
460
461    _Refcount_Base(_RC_t __n) : _M_ref_count(__n), _M_ref_count_lock()
462    {
463#ifdef __GTHREAD_MUTEX_INIT
464      __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
465      _M_ref_count_lock = __tmp;
466#elif defined(__GTHREAD_MUTEX_INIT_FUNCTION)
467      __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
468#else
469#error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
470#endif
471    }
472
473    void
474    _M_incr()
475    {
476      __gthread_mutex_lock(&_M_ref_count_lock);
477      ++_M_ref_count;
478      __gthread_mutex_unlock(&_M_ref_count_lock);
479    }
480
481    _RC_t
482    _M_decr()
483    {
484      __gthread_mutex_lock(&_M_ref_count_lock);
485      volatile _RC_t __tmp = --_M_ref_count;
486      __gthread_mutex_unlock(&_M_ref_count_lock);
487      return __tmp;
488    }
489  };
490
491  //
492  // What follows should really be local to rope.  Unfortunately,
493  // that doesn't work, since it makes it impossible to define generic
494  // equality on rope iterators.  According to the draft standard, the
495  // template parameters for such an equality operator cannot be inferred
496  // from the occurrence of a member class as a parameter.
497  // (SGI compilers in fact allow this, but the __result wouldn't be
498  // portable.)
499  // Similarly, some of the static member functions are member functions
500  // only to avoid polluting the global namespace, and to circumvent
501  // restrictions on type inference for template functions.
502  //
503
504  //
505  // The internal data structure for representing a rope.  This is
506  // private to the implementation.  A rope is really just a pointer
507  // to one of these.
508  //
509  // A few basic functions for manipulating this data structure
510  // are members of _RopeRep.  Most of the more complex algorithms
511  // are implemented as rope members.
512  //
513  // Some of the static member functions of _RopeRep have identically
514  // named functions in rope that simply invoke the _RopeRep versions.
515
516#define __ROPE_DEFINE_ALLOCS(__a) \
517        __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
518        typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
519        __ROPE_DEFINE_ALLOC(__C,_C) \
520        typedef _Rope_RopeLeaf<_CharT,__a> __L; \
521        __ROPE_DEFINE_ALLOC(__L,_L) \
522        typedef _Rope_RopeFunction<_CharT,__a> __F; \
523        __ROPE_DEFINE_ALLOC(__F,_F) \
524        typedef _Rope_RopeSubstring<_CharT,__a> __S; \
525        __ROPE_DEFINE_ALLOC(__S,_S)
526
527  //  Internal rope nodes potentially store a copy of the allocator
528  //  instance used to allocate them.  This is mostly redundant.
529  //  But the alternative would be to pass allocator instances around
530  //  in some form to nearly all internal functions, since any pointer
531  //  assignment may result in a zero reference count and thus require
532  //  deallocation.
533
534#define __STATIC_IF_SGI_ALLOC  /* not static */
535
536  template <class _CharT, class _Alloc>
537    struct _Rope_rep_base
538    : public _Alloc
539    {
540      typedef _Alloc allocator_type;
541
542      allocator_type
543      get_allocator() const
544      { return *static_cast<const _Alloc*>(this); }
545
546      allocator_type&
547      _M_get_allocator()
548      { return *static_cast<_Alloc*>(this); }
549
550      const allocator_type&
551      _M_get_allocator() const
552      { return *static_cast<const _Alloc*>(this); }
553
554      _Rope_rep_base(size_t __size, const allocator_type&)
555      : _M_size(__size) { }
556
557      size_t _M_size;
558
559# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
560        typedef typename \
561          _Alloc::template rebind<_Tp>::other __name##Alloc; \
562        static _Tp* __name##_allocate(size_t __n) \
563          { return __name##Alloc().allocate(__n); } \
564        static void __name##_deallocate(_Tp *__p, size_t __n) \
565          { __name##Alloc().deallocate(__p, __n); }
566      __ROPE_DEFINE_ALLOCS(_Alloc)
567# undef __ROPE_DEFINE_ALLOC
568    };
569
570  template<class _CharT, class _Alloc>
571    struct _Rope_RopeRep
572    : public _Rope_rep_base<_CharT, _Alloc>
573# ifndef __GC
574	     , _Refcount_Base
575# endif
576    {
577    public:
578      __detail::_Tag _M_tag:8;
579      bool _M_is_balanced:8;
580      unsigned char _M_depth;
581      __GC_CONST _CharT* _M_c_string;
582      __gthread_mutex_t _M_c_string_lock;
583                        /* Flattened version of string, if needed.  */
584                        /* typically 0.                             */
585                        /* If it's not 0, then the memory is owned  */
586                        /* by this node.                            */
587                        /* In the case of a leaf, this may point to */
588                        /* the same memory as the data field.       */
589      typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
590        allocator_type;
591
592      using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
593      using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
594
595      _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
596		    const allocator_type& __a)
597      : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
598#ifndef __GC
599	_Refcount_Base(1),
600#endif
601	_M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
602#ifdef __GTHREAD_MUTEX_INIT
603    {
604      // Do not copy a POSIX/gthr mutex once in use.  However, bits are bits.
605      __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
606      _M_c_string_lock = __tmp;
607    }
608#else
609    { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
610#endif
611#ifdef __GC
612      void
613      _M_incr () { }
614#endif
615      static void
616      _S_free_string(__GC_CONST _CharT*, size_t __len,
617		     allocator_type& __a);
618#define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
619                        // Deallocate data section of a leaf.
620                        // This shouldn't be a member function.
621                        // But its hard to do anything else at the
622                        // moment, because it's templatized w.r.t.
623                        // an allocator.
624                        // Does nothing if __GC is defined.
625#ifndef __GC
626      void _M_free_c_string();
627      void _M_free_tree();
628      // Deallocate t. Assumes t is not 0.
629      void
630      _M_unref_nonnil()
631      {
632	if (0 == _M_decr())
633	  _M_free_tree();
634      }
635
636      void
637      _M_ref_nonnil()
638      { _M_incr(); }
639
640      static void
641      _S_unref(_Rope_RopeRep* __t)
642      {
643	if (0 != __t)
644	  __t->_M_unref_nonnil();
645      }
646
647      static void
648      _S_ref(_Rope_RopeRep* __t)
649      {
650	if (0 != __t)
651	  __t->_M_incr();
652      }
653      
654      static void
655      _S_free_if_unref(_Rope_RopeRep* __t)
656      {
657	if (0 != __t && 0 == __t->_M_ref_count)
658	  __t->_M_free_tree();
659      }
660#   else /* __GC */
661      void _M_unref_nonnil() { }
662      void _M_ref_nonnil() { }
663      static void _S_unref(_Rope_RopeRep*) { }
664      static void _S_ref(_Rope_RopeRep*) { }
665      static void _S_free_if_unref(_Rope_RopeRep*) { }
666#   endif
667protected:
668      _Rope_RopeRep&
669      operator=(const _Rope_RopeRep&);
670
671      _Rope_RopeRep(const _Rope_RopeRep&);
672    };
673
674  template<class _CharT, class _Alloc>
675    struct _Rope_RopeLeaf
676    : public _Rope_RopeRep<_CharT, _Alloc>
677    {
678    public:
679      // Apparently needed by VC++
680      // The data fields of leaves are allocated with some
681      // extra space, to accommodate future growth and for basic
682      // character types, to hold a trailing eos character.
683      enum { _S_alloc_granularity = 8 };
684      
685      static size_t
686      _S_rounded_up_size(size_t __n)
687      {
688        size_t __size_with_eos;
689	
690        if (_S_is_basic_char_type((_CharT*)0))
691	  __size_with_eos = __n + 1;
692	else
693	  __size_with_eos = __n;
694#ifdef __GC
695	return __size_with_eos;
696#else
697	// Allow slop for in-place expansion.
698	return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
699		&~ (size_t(_S_alloc_granularity) - 1));
700#endif
701      }
702      __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
703                                  /* The allocated size is         */
704                                  /* _S_rounded_up_size(size), except */
705                                  /* in the GC case, in which it   */
706                                  /* doesn't matter.               */
707      typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
708        allocator_type;
709
710      _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
711		     const allocator_type& __a)
712      : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
713				      __size, __a), _M_data(__d)
714      {
715        if (_S_is_basic_char_type((_CharT *)0))
716	  {
717            // already eos terminated.
718            this->_M_c_string = __d;
719	  }
720      }
721      // The constructor assumes that d has been allocated with
722      // the proper allocator and the properly padded size.
723      // In contrast, the destructor deallocates the data:
724#ifndef __GC
725      ~_Rope_RopeLeaf() throw()
726      {
727        if (_M_data != this->_M_c_string)
728	  this->_M_free_c_string();
729	
730        __STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
731      }
732#endif
733protected:
734      _Rope_RopeLeaf&
735      operator=(const _Rope_RopeLeaf&);
736
737      _Rope_RopeLeaf(const _Rope_RopeLeaf&);
738    };
739
740  template<class _CharT, class _Alloc>
741    struct _Rope_RopeConcatenation
742    : public _Rope_RopeRep<_CharT, _Alloc>
743    {
744    public:
745      _Rope_RopeRep<_CharT, _Alloc>* _M_left;
746      _Rope_RopeRep<_CharT, _Alloc>* _M_right;
747
748      typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
749        allocator_type;
750
751      _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
752			      _Rope_RopeRep<_CharT, _Alloc>* __r,
753			      const allocator_type& __a)
754	: _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
755				      std::max(__l->_M_depth,
756					       __r->_M_depth) + 1,
757				      false,
758				      __l->_M_size + __r->_M_size, __a),
759        _M_left(__l), _M_right(__r)
760      { }
761#ifndef __GC
762      ~_Rope_RopeConcatenation() throw()
763      {
764	this->_M_free_c_string();
765	_M_left->_M_unref_nonnil();
766	_M_right->_M_unref_nonnil();
767      }
768#endif
769protected:
770      _Rope_RopeConcatenation&
771      operator=(const _Rope_RopeConcatenation&);
772      
773      _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
774    };
775
776  template<class _CharT, class _Alloc>
777    struct _Rope_RopeFunction
778    : public _Rope_RopeRep<_CharT, _Alloc>
779    {
780    public:
781      char_producer<_CharT>* _M_fn;
782#ifndef __GC
783      bool _M_delete_when_done; // Char_producer is owned by the
784                                // rope and should be explicitly
785                                // deleted when the rope becomes
786                                // inaccessible.
787#else
788      // In the GC case, we either register the rope for
789      // finalization, or not.  Thus the field is unnecessary;
790      // the information is stored in the collector data structures.
791      // We do need a finalization procedure to be invoked by the
792      // collector.
793      static void
794      _S_fn_finalization_proc(void * __tree, void *)
795      { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
796#endif
797    typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
798      allocator_type;
799
800      _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
801                        bool __d, const allocator_type& __a)
802      : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
803	, _M_fn(__f)
804#ifndef __GC
805	, _M_delete_when_done(__d)
806#endif
807      {
808#ifdef __GC
809	if (__d)
810	  {
811	    GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
812				  _S_fn_finalization_proc, 0, 0, 0);
813	  }
814#endif
815      }
816#ifndef __GC
817      ~_Rope_RopeFunction() throw()
818      {
819	this->_M_free_c_string();
820	if (_M_delete_when_done)
821	  delete _M_fn;
822      }
823# endif
824    protected:
825      _Rope_RopeFunction&
826      operator=(const _Rope_RopeFunction&);
827
828      _Rope_RopeFunction(const _Rope_RopeFunction&);
829    };
830  // Substring results are usually represented using just
831  // concatenation nodes.  But in the case of very long flat ropes
832  // or ropes with a functional representation that isn't practical.
833  // In that case, we represent the __result as a special case of
834  // RopeFunction, whose char_producer points back to the rope itself.
835  // In all cases except repeated substring operations and
836  // deallocation, we treat the __result as a RopeFunction.
837  template<class _CharT, class _Alloc>
838    struct _Rope_RopeSubstring
839    : public _Rope_RopeFunction<_CharT, _Alloc>,
840      public char_producer<_CharT>
841    {
842    public:
843      // XXX this whole class should be rewritten.
844      _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
845      size_t _M_start;
846
847      virtual void
848      operator()(size_t __start_pos, size_t __req_len,
849		 _CharT* __buffer)
850      {
851        switch(_M_base->_M_tag)
852	  {
853	  case __detail::_S_function:
854	  case __detail::_S_substringfn:
855	    {
856	      char_producer<_CharT>* __fn =
857		((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
858	      (*__fn)(__start_pos + _M_start, __req_len, __buffer);
859	    }
860	    break;
861	  case __detail::_S_leaf:
862	    {
863	      __GC_CONST _CharT* __s =
864		((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
865	      uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
866				   __buffer);
867	    }
868	    break;
869	  default:
870	    break;
871	  }
872      }
873      
874      typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
875        allocator_type;
876
877      _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
878                          size_t __l, const allocator_type& __a)
879      : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
880        char_producer<_CharT>(), _M_base(__b), _M_start(__s)
881      {
882#ifndef __GC
883	_M_base->_M_ref_nonnil();
884#endif
885        this->_M_tag = __detail::_S_substringfn;
886      }
887    virtual ~_Rope_RopeSubstring() throw()
888      {
889#ifndef __GC
890	_M_base->_M_unref_nonnil();
891	// _M_free_c_string();  -- done by parent class
892#endif
893      }
894    };
895
896  // Self-destructing pointers to Rope_rep.
897  // These are not conventional smart pointers.  Their
898  // only purpose in life is to ensure that unref is called
899  // on the pointer either at normal exit or if an exception
900  // is raised.  It is the caller's responsibility to
901  // adjust reference counts when these pointers are initialized
902  // or assigned to.  (This convention significantly reduces
903  // the number of potentially expensive reference count
904  // updates.)
905#ifndef __GC
906  template<class _CharT, class _Alloc>
907    struct _Rope_self_destruct_ptr
908    {
909      _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
910
911      ~_Rope_self_destruct_ptr()
912      { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
913#ifdef __EXCEPTIONS
914      _Rope_self_destruct_ptr() : _M_ptr(0) { };
915#else
916      _Rope_self_destruct_ptr() { };
917#endif
918      _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
919      : _M_ptr(__p) { }
920    
921      _Rope_RopeRep<_CharT, _Alloc>&
922      operator*()
923      { return *_M_ptr; }
924    
925      _Rope_RopeRep<_CharT, _Alloc>*
926      operator->()
927      { return _M_ptr; }
928    
929      operator _Rope_RopeRep<_CharT, _Alloc>*()
930      { return _M_ptr; }
931    
932      _Rope_self_destruct_ptr&
933      operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
934      { _M_ptr = __x; return *this; }
935    };
936#endif
937
938  // Dereferencing a nonconst iterator has to return something
939  // that behaves almost like a reference.  It's not possible to
940  // return an actual reference since assignment requires extra
941  // work.  And we would get into the same problems as with the
942  // CD2 version of basic_string.
943  template<class _CharT, class _Alloc>
944    class _Rope_char_ref_proxy
945    {
946      friend class rope<_CharT, _Alloc>;
947      friend class _Rope_iterator<_CharT, _Alloc>;
948      friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
949#ifdef __GC
950      typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
951#else
952      typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
953#endif
954      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
955      typedef rope<_CharT, _Alloc> _My_rope;
956      size_t _M_pos;
957      _CharT _M_current;
958      bool _M_current_valid;
959      _My_rope* _M_root;     // The whole rope.
960    public:
961      _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
962      :  _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
963
964      _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
965      : _M_pos(__x._M_pos), _M_current(__x._M_current), 
966	_M_current_valid(false), _M_root(__x._M_root) { }
967
968      // Don't preserve cache if the reference can outlive the
969      // expression.  We claim that's not possible without calling
970      // a copy constructor or generating reference to a proxy
971      // reference.  We declare the latter to have undefined semantics.
972      _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
973      : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
974
975      inline operator _CharT () const;
976
977      _Rope_char_ref_proxy&
978      operator=(_CharT __c);
979    
980      _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
981      
982      _Rope_char_ref_proxy&
983      operator=(const _Rope_char_ref_proxy& __c)
984      { return operator=((_CharT)__c); }
985    };
986
987  template<class _CharT, class __Alloc>
988    inline void
989    swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
990	 _Rope_char_ref_proxy <_CharT, __Alloc > __b)
991    {
992      _CharT __tmp = __a;
993      __a = __b;
994      __b = __tmp;
995    }
996
997  template<class _CharT, class _Alloc>
998    class _Rope_char_ptr_proxy
999    {
1000      // XXX this class should be rewritten.
1001      friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1002      size_t _M_pos;
1003      rope<_CharT,_Alloc>* _M_root;     // The whole rope.
1004    public:
1005      _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
1006      : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1007
1008      _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
1009      : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1010
1011      _Rope_char_ptr_proxy() { }
1012      
1013      _Rope_char_ptr_proxy(_CharT* __x)
1014      : _M_root(0), _M_pos(0) { }
1015
1016      _Rope_char_ptr_proxy&
1017      operator=(const _Rope_char_ptr_proxy& __x)
1018      {
1019        _M_pos = __x._M_pos;
1020        _M_root = __x._M_root;
1021        return *this;
1022      }
1023
1024      template<class _CharT2, class _Alloc2>
1025        friend bool
1026        operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
1027		   const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
1028
1029      _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
1030      { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
1031    };
1032
1033  // Rope iterators:
1034  // Unlike in the C version, we cache only part of the stack
1035  // for rope iterators, since they must be efficiently copyable.
1036  // When we run out of cache, we have to reconstruct the iterator
1037  // value.
1038  // Pointers from iterators are not included in reference counts.
1039  // Iterators are assumed to be thread private.  Ropes can
1040  // be shared.
1041  
1042  template<class _CharT, class _Alloc>
1043    class _Rope_iterator_base
1044    : public std::iterator<std::random_access_iterator_tag, _CharT>
1045    {
1046      friend class rope<_CharT, _Alloc>;
1047    public:
1048      typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround
1049      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1050      // Borland doesn't want this to be protected.
1051    protected:
1052      enum { _S_path_cache_len = 4 }; // Must be <= 9.
1053      enum { _S_iterator_buf_len = 15 };
1054      size_t _M_current_pos;
1055      _RopeRep* _M_root;     // The whole rope.
1056      size_t _M_leaf_pos;    // Starting position for current leaf
1057      __GC_CONST _CharT* _M_buf_start;
1058                             // Buffer possibly
1059                             // containing current char.
1060      __GC_CONST _CharT* _M_buf_ptr;
1061                             // Pointer to current char in buffer.
1062                             // != 0 ==> buffer valid.
1063      __GC_CONST _CharT* _M_buf_end;
1064                             // One past __last valid char in buffer.
1065      // What follows is the path cache.  We go out of our
1066      // way to make this compact.
1067      // Path_end contains the bottom section of the path from
1068      // the root to the current leaf.
1069      const _RopeRep* _M_path_end[_S_path_cache_len];
1070      int _M_leaf_index;     // Last valid __pos in path_end;
1071                             // _M_path_end[0] ... _M_path_end[leaf_index-1]
1072                             // point to concatenation nodes.
1073      unsigned char _M_path_directions;
1074                          // (path_directions >> __i) & 1 is 1
1075                          // iff we got from _M_path_end[leaf_index - __i - 1]
1076                          // to _M_path_end[leaf_index - __i] by going to the
1077                          // __right. Assumes path_cache_len <= 9.
1078      _CharT _M_tmp_buf[_S_iterator_buf_len];
1079                        // Short buffer for surrounding chars.
1080                        // This is useful primarily for
1081                        // RopeFunctions.  We put the buffer
1082                        // here to avoid locking in the
1083                        // multithreaded case.
1084      // The cached path is generally assumed to be valid
1085      // only if the buffer is valid.
1086      static void _S_setbuf(_Rope_iterator_base& __x);
1087                                        // Set buffer contents given
1088                                        // path cache.
1089      static void _S_setcache(_Rope_iterator_base& __x);
1090                                        // Set buffer contents and
1091                                        // path cache.
1092      static void _S_setcache_for_incr(_Rope_iterator_base& __x);
1093                                        // As above, but assumes path
1094                                        // cache is valid for previous posn.
1095      _Rope_iterator_base() { }
1096
1097      _Rope_iterator_base(_RopeRep* __root, size_t __pos)
1098      : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
1099
1100      void _M_incr(size_t __n);
1101      void _M_decr(size_t __n);
1102    public:
1103      size_t
1104      index() const
1105      { return _M_current_pos; }
1106    
1107      _Rope_iterator_base(const _Rope_iterator_base& __x)
1108      {
1109        if (0 != __x._M_buf_ptr)
1110	  *this = __x;
1111	else
1112	  {
1113            _M_current_pos = __x._M_current_pos;
1114            _M_root = __x._M_root;
1115            _M_buf_ptr = 0;
1116	  }
1117      }
1118    };
1119
1120  template<class _CharT, class _Alloc>
1121    class _Rope_iterator;
1122
1123  template<class _CharT, class _Alloc>
1124    class _Rope_const_iterator
1125    : public _Rope_iterator_base<_CharT, _Alloc>
1126    {
1127      friend class rope<_CharT, _Alloc>;
1128    protected:
1129      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1130      // The one from the base class may not be directly visible.
1131      _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
1132      : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
1133					    __pos)
1134                   // Only nonconst iterators modify root ref count
1135      { }
1136  public:
1137      typedef _CharT reference;   // Really a value.  Returning a reference
1138                                  // Would be a mess, since it would have
1139                                  // to be included in refcount.
1140      typedef const _CharT* pointer;
1141
1142    public:
1143      _Rope_const_iterator() { };
1144
1145      _Rope_const_iterator(const _Rope_const_iterator& __x)
1146      : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
1147
1148      _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
1149    
1150      _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
1151      : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
1152
1153      _Rope_const_iterator&
1154      operator=(const _Rope_const_iterator& __x)
1155      {
1156        if (0 != __x._M_buf_ptr)
1157	  *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1158	else
1159	  {
1160            this->_M_current_pos = __x._M_current_pos;
1161            this->_M_root = __x._M_root;
1162            this->_M_buf_ptr = 0;
1163	  }
1164        return(*this);
1165      }
1166
1167      reference
1168      operator*()
1169      {
1170        if (0 == this->_M_buf_ptr)
1171	  _S_setcache(*this);
1172        return *this->_M_buf_ptr;
1173      }
1174
1175      // Without this const version, Rope iterators do not meet the
1176      // requirements of an Input Iterator.
1177      reference
1178      operator*() const
1179      {
1180	return *const_cast<_Rope_const_iterator&>(*this);
1181      }
1182
1183      _Rope_const_iterator&
1184      operator++()
1185      {
1186        __GC_CONST _CharT* __next;
1187        if (0 != this->_M_buf_ptr
1188	    && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
1189	  {
1190            this->_M_buf_ptr = __next;
1191            ++this->_M_current_pos;
1192	  }
1193	else
1194	  this->_M_incr(1);
1195	return *this;
1196      }
1197
1198      _Rope_const_iterator&
1199      operator+=(ptrdiff_t __n)
1200      {
1201        if (__n >= 0)
1202	  this->_M_incr(__n);
1203	else
1204	  this->_M_decr(-__n);
1205	return *this;
1206      }
1207
1208      _Rope_const_iterator&
1209      operator--()
1210      {
1211        this->_M_decr(1);
1212        return *this;
1213      }
1214
1215      _Rope_const_iterator&
1216      operator-=(ptrdiff_t __n)
1217      {
1218        if (__n >= 0)
1219	  this->_M_decr(__n);
1220	else
1221	  this->_M_incr(-__n);
1222	return *this;
1223      }
1224
1225      _Rope_const_iterator
1226      operator++(int)
1227      {
1228        size_t __old_pos = this->_M_current_pos;
1229        this->_M_incr(1);
1230        return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1231        // This makes a subsequent dereference expensive.
1232        // Perhaps we should instead copy the iterator
1233        // if it has a valid cache?
1234      }
1235
1236      _Rope_const_iterator
1237      operator--(int)
1238      {
1239        size_t __old_pos = this->_M_current_pos;
1240        this->_M_decr(1);
1241        return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1242      }
1243
1244      template<class _CharT2, class _Alloc2>
1245        friend _Rope_const_iterator<_CharT2, _Alloc2>
1246        operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1247		  ptrdiff_t __n);
1248
1249      template<class _CharT2, class _Alloc2>
1250        friend _Rope_const_iterator<_CharT2, _Alloc2>
1251        operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1252		  ptrdiff_t __n);
1253
1254      template<class _CharT2, class _Alloc2>
1255        friend _Rope_const_iterator<_CharT2, _Alloc2>
1256        operator+(ptrdiff_t __n,
1257		  const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
1258
1259      reference
1260      operator[](size_t __n)
1261      { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
1262					      this->_M_current_pos + __n); }
1263
1264      template<class _CharT2, class _Alloc2>
1265        friend bool
1266        operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1267		   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1268
1269      template<class _CharT2, class _Alloc2>
1270        friend bool
1271        operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1272		  const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1273
1274      template<class _CharT2, class _Alloc2>
1275        friend ptrdiff_t
1276        operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1277		  const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1278    };
1279
1280  template<class _CharT, class _Alloc>
1281    class _Rope_iterator
1282    : public _Rope_iterator_base<_CharT, _Alloc>
1283    {
1284      friend class rope<_CharT, _Alloc>;
1285    protected:
1286      typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
1287      rope<_CharT, _Alloc>* _M_root_rope;
1288
1289      // root is treated as a cached version of this, and is used to
1290      // detect changes to the underlying rope.
1291
1292      // Root is included in the reference count.  This is necessary
1293      // so that we can detect changes reliably.  Unfortunately, it
1294      // requires careful bookkeeping for the nonGC case.
1295      _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
1296      : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
1297        _M_root_rope(__r)
1298      { _RopeRep::_S_ref(this->_M_root);
1299        if (!(__r -> empty()))
1300	  _S_setcache(*this);
1301      }
1302
1303      void _M_check();
1304    public:
1305      typedef _Rope_char_ref_proxy<_CharT, _Alloc>  reference;
1306      typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
1307
1308      rope<_CharT, _Alloc>&
1309      container()
1310      { return *_M_root_rope; }
1311
1312      _Rope_iterator()
1313      {
1314        this->_M_root = 0;  // Needed for reference counting.
1315      };
1316
1317      _Rope_iterator(const _Rope_iterator& __x)
1318      : _Rope_iterator_base<_CharT, _Alloc>(__x)
1319      {
1320        _M_root_rope = __x._M_root_rope;
1321        _RopeRep::_S_ref(this->_M_root);
1322      }
1323
1324      _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
1325
1326      ~_Rope_iterator()
1327      { _RopeRep::_S_unref(this->_M_root); }
1328
1329      _Rope_iterator&
1330      operator=(const _Rope_iterator& __x)
1331      {
1332        _RopeRep* __old = this->_M_root;
1333	
1334        _RopeRep::_S_ref(__x._M_root);
1335        if (0 != __x._M_buf_ptr)
1336	  {
1337            _M_root_rope = __x._M_root_rope;
1338            *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1339	  }
1340	else
1341	  {
1342	    this->_M_current_pos = __x._M_current_pos;
1343            this->_M_root = __x._M_root;
1344            _M_root_rope = __x._M_root_rope;
1345            this->_M_buf_ptr = 0;
1346	  }
1347        _RopeRep::_S_unref(__old);
1348        return(*this);
1349      }
1350
1351      reference
1352      operator*()
1353      {
1354        _M_check();
1355        if (0 == this->_M_buf_ptr)
1356	  return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1357						      this->_M_current_pos);
1358	else
1359	  return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1360						      this->_M_current_pos,
1361						      *this->_M_buf_ptr);
1362      }
1363
1364      // See above comment.
1365      reference
1366      operator*() const
1367      {
1368	return *const_cast<_Rope_iterator&>(*this);
1369      }
1370
1371      _Rope_iterator&
1372      operator++()
1373      {
1374        this->_M_incr(1);
1375        return *this;
1376      }
1377
1378      _Rope_iterator&
1379      operator+=(ptrdiff_t __n)
1380      {
1381        if (__n >= 0)
1382	  this->_M_incr(__n);
1383	else
1384	  this->_M_decr(-__n);
1385	return *this;
1386      }
1387
1388      _Rope_iterator&
1389      operator--()
1390      {
1391        this->_M_decr(1);
1392        return *this;
1393      }
1394
1395      _Rope_iterator&
1396      operator-=(ptrdiff_t __n)
1397      {
1398        if (__n >= 0)
1399	  this->_M_decr(__n);
1400	else
1401	  this->_M_incr(-__n);
1402	return *this;
1403      }
1404
1405      _Rope_iterator
1406      operator++(int)
1407      {
1408        size_t __old_pos = this->_M_current_pos;
1409        this->_M_incr(1);
1410        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1411      }
1412
1413      _Rope_iterator
1414      operator--(int)
1415      {
1416        size_t __old_pos = this->_M_current_pos;
1417        this->_M_decr(1);
1418        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1419      }
1420
1421      reference
1422      operator[](ptrdiff_t __n)
1423      { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1424						    this->_M_current_pos
1425						    + __n); }
1426
1427      template<class _CharT2, class _Alloc2>
1428        friend bool
1429        operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1430		   const _Rope_iterator<_CharT2, _Alloc2>& __y);
1431
1432      template<class _CharT2, class _Alloc2>
1433        friend bool
1434        operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1435		  const _Rope_iterator<_CharT2, _Alloc2>& __y);
1436
1437      template<class _CharT2, class _Alloc2>
1438        friend ptrdiff_t
1439        operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1440		  const _Rope_iterator<_CharT2, _Alloc2>& __y);
1441
1442      template<class _CharT2, class _Alloc2>
1443        friend _Rope_iterator<_CharT2, _Alloc2>
1444        operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1445
1446      template<class _CharT2, class _Alloc2>
1447        friend _Rope_iterator<_CharT2, _Alloc2>
1448        operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1449
1450      template<class _CharT2, class _Alloc2>
1451        friend _Rope_iterator<_CharT2, _Alloc2>
1452        operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
1453    };
1454
1455
1456  template <class _CharT, class _Alloc>
1457    struct _Rope_base
1458    : public _Alloc
1459    {
1460      typedef _Alloc allocator_type;
1461
1462      allocator_type
1463      get_allocator() const
1464      { return *static_cast<const _Alloc*>(this); }
1465
1466      allocator_type&
1467      _M_get_allocator()
1468      { return *static_cast<_Alloc*>(this); }
1469
1470      const allocator_type&
1471      _M_get_allocator() const
1472      { return *static_cast<const _Alloc*>(this); }
1473
1474      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1475      // The one in _Base may not be visible due to template rules.
1476
1477      _Rope_base(_RopeRep* __t, const allocator_type&)
1478      : _M_tree_ptr(__t) { }
1479
1480      _Rope_base(const allocator_type&) { }
1481
1482      // The only data member of a rope:
1483      _RopeRep *_M_tree_ptr;
1484
1485#define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1486        typedef typename \
1487          _Alloc::template rebind<_Tp>::other __name##Alloc; \
1488        static _Tp* __name##_allocate(size_t __n) \
1489          { return __name##Alloc().allocate(__n); } \
1490        static void __name##_deallocate(_Tp *__p, size_t __n) \
1491          { __name##Alloc().deallocate(__p, __n); }
1492      __ROPE_DEFINE_ALLOCS(_Alloc)
1493#undef __ROPE_DEFINE_ALLOC
1494
1495	protected:
1496      _Rope_base&
1497      operator=(const _Rope_base&);
1498      
1499      _Rope_base(const _Rope_base&);
1500    };
1501
1502  /**
1503   *  This is an SGI extension.
1504   *  @ingroup SGIextensions
1505   *  @doctodo
1506   */
1507  template <class _CharT, class _Alloc>
1508    class rope : public _Rope_base<_CharT, _Alloc>
1509    {
1510    public:
1511      typedef _CharT value_type;
1512      typedef ptrdiff_t difference_type;
1513      typedef size_t size_type;
1514      typedef _CharT const_reference;
1515      typedef const _CharT* const_pointer;
1516      typedef _Rope_iterator<_CharT, _Alloc> iterator;
1517      typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
1518      typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
1519      typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
1520
1521      friend class _Rope_iterator<_CharT, _Alloc>;
1522      friend class _Rope_const_iterator<_CharT, _Alloc>;
1523      friend struct _Rope_RopeRep<_CharT, _Alloc>;
1524      friend class _Rope_iterator_base<_CharT, _Alloc>;
1525      friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
1526      friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1527      friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
1528
1529    protected:
1530      typedef _Rope_base<_CharT, _Alloc> _Base;
1531      typedef typename _Base::allocator_type allocator_type;
1532      using _Base::_M_tree_ptr;
1533      using _Base::get_allocator;
1534      using _Base::_M_get_allocator;      
1535      typedef __GC_CONST _CharT* _Cstrptr;
1536      
1537      static _CharT _S_empty_c_str[1];
1538      
1539      static bool
1540      _S_is0(_CharT __c)
1541      { return __c == _S_eos((_CharT*)0); }
1542      
1543      enum { _S_copy_max = 23 };
1544                // For strings shorter than _S_copy_max, we copy to
1545                // concatenate.
1546
1547      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1548      typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
1549      typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
1550      typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
1551      typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
1552
1553      // Retrieve a character at the indicated position.
1554      static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
1555
1556#ifndef __GC
1557      // Obtain a pointer to the character at the indicated position.
1558      // The pointer can be used to change the character.
1559      // If such a pointer cannot be produced, as is frequently the
1560      // case, 0 is returned instead.
1561      // (Returns nonzero only if all nodes in the path have a refcount
1562      // of 1.)
1563      static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
1564#endif
1565
1566      static bool
1567      _S_apply_to_pieces(// should be template parameter
1568			 _Rope_char_consumer<_CharT>& __c,
1569			 const _RopeRep* __r,
1570			 size_t __begin, size_t __end);
1571                         // begin and end are assumed to be in range.
1572
1573#ifndef __GC
1574      static void
1575      _S_unref(_RopeRep* __t)
1576      { _RopeRep::_S_unref(__t); }
1577
1578      static void
1579      _S_ref(_RopeRep* __t)
1580      { _RopeRep::_S_ref(__t); }
1581
1582#else /* __GC */
1583      static void _S_unref(_RopeRep*) { }
1584      static void _S_ref(_RopeRep*) { }
1585#endif
1586
1587#ifdef __GC
1588      typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
1589#else
1590      typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
1591#endif
1592
1593      // _Result is counted in refcount.
1594      static _RopeRep* _S_substring(_RopeRep* __base,
1595                                    size_t __start, size_t __endp1);
1596
1597      static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
1598					   const _CharT* __iter, size_t __slen);
1599      // Concatenate rope and char ptr, copying __s.
1600      // Should really take an arbitrary iterator.
1601      // Result is counted in refcount.
1602      static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
1603						 const _CharT* __iter,
1604						 size_t __slen)
1605	// As above, but one reference to __r is about to be
1606	// destroyed.  Thus the pieces may be recycled if all
1607	// relevant reference counts are 1.
1608#ifdef __GC
1609	// We can't really do anything since refcounts are unavailable.
1610      { return _S_concat_char_iter(__r, __iter, __slen); }
1611#else
1612      ;
1613#endif
1614
1615      static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
1616      // General concatenation on _RopeRep.  _Result
1617      // has refcount of 1.  Adjusts argument refcounts.
1618
1619   public:
1620      void
1621      apply_to_pieces(size_t __begin, size_t __end,
1622		      _Rope_char_consumer<_CharT>& __c) const
1623      { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
1624
1625   protected:
1626
1627      static size_t
1628      _S_rounded_up_size(size_t __n)
1629      { return _RopeLeaf::_S_rounded_up_size(__n); }
1630
1631      static size_t
1632      _S_allocated_capacity(size_t __n)
1633      {
1634	if (_S_is_basic_char_type((_CharT*)0))
1635	  return _S_rounded_up_size(__n) - 1;
1636	else
1637	  return _S_rounded_up_size(__n);
1638	
1639      }
1640
1641      // Allocate and construct a RopeLeaf using the supplied allocator
1642      // Takes ownership of s instead of copying.
1643      static _RopeLeaf*
1644      _S_new_RopeLeaf(__GC_CONST _CharT *__s,
1645		      size_t __size, allocator_type& __a)
1646      {
1647	_RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
1648	return new(__space) _RopeLeaf(__s, __size, __a);
1649      }
1650
1651      static _RopeConcatenation*
1652      _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
1653			       allocator_type& __a)
1654      {
1655	_RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
1656	return new(__space) _RopeConcatenation(__left, __right, __a);
1657      }
1658
1659      static _RopeFunction*
1660      _S_new_RopeFunction(char_producer<_CharT>* __f,
1661			  size_t __size, bool __d, allocator_type& __a)
1662      {
1663	_RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
1664	return new(__space) _RopeFunction(__f, __size, __d, __a);
1665      }
1666
1667      static _RopeSubstring*
1668      _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
1669			   size_t __l, allocator_type& __a)
1670      {
1671	_RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
1672	return new(__space) _RopeSubstring(__b, __s, __l, __a);
1673      }
1674      
1675      static _RopeLeaf*
1676      _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
1677					size_t __size, allocator_type& __a)
1678#define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1679                _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1680      {
1681	if (0 == __size)
1682	  return 0;
1683	_CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
1684	
1685	__uninitialized_copy_n_a(__s, __size, __buf, __a);
1686	_S_cond_store_eos(__buf[__size]);
1687	__try
1688	  { return _S_new_RopeLeaf(__buf, __size, __a); }
1689	__catch(...)
1690	  {
1691	    _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
1692	    __throw_exception_again;
1693	  }
1694      }
1695
1696      // Concatenation of nonempty strings.
1697      // Always builds a concatenation node.
1698      // Rebalances if the result is too deep.
1699      // Result has refcount 1.
1700      // Does not increment left and right ref counts even though
1701      // they are referenced.
1702      static _RopeRep*
1703      _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
1704
1705      // Concatenation helper functions
1706      static _RopeLeaf*
1707      _S_leaf_concat_char_iter(_RopeLeaf* __r,
1708			       const _CharT* __iter, size_t __slen);
1709      // Concatenate by copying leaf.
1710      // should take an arbitrary iterator
1711      // result has refcount 1.
1712#ifndef __GC
1713      static _RopeLeaf*
1714      _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
1715				     const _CharT* __iter, size_t __slen);
1716      // A version that potentially clobbers __r if __r->_M_ref_count == 1.
1717#endif
1718
1719    private:
1720      
1721      static size_t _S_char_ptr_len(const _CharT* __s);
1722      // slightly generalized strlen
1723
1724      rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
1725      : _Base(__t, __a) { }
1726
1727
1728      // Copy __r to the _CharT buffer.
1729      // Returns __buffer + __r->_M_size.
1730      // Assumes that buffer is uninitialized.
1731      static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
1732
1733      // Again, with explicit starting position and length.
1734      // Assumes that buffer is uninitialized.
1735      static _CharT* _S_flatten(_RopeRep* __r,
1736				size_t __start, size_t __len,
1737				_CharT* __buffer);
1738
1739      static const unsigned long
1740      _S_min_len[__detail::_S_max_rope_depth + 1];
1741      
1742      static bool
1743      _S_is_balanced(_RopeRep* __r)
1744      { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
1745
1746      static bool
1747      _S_is_almost_balanced(_RopeRep* __r)
1748      { return (__r->_M_depth == 0
1749		|| __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
1750
1751      static bool
1752      _S_is_roughly_balanced(_RopeRep* __r)
1753      { return (__r->_M_depth <= 1
1754		|| __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
1755
1756      // Assumes the result is not empty.
1757      static _RopeRep*
1758      _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
1759      {
1760	_RopeRep* __result = _S_concat(__left, __right);
1761	if (_S_is_balanced(__result))
1762	  __result->_M_is_balanced = true;
1763	return __result;
1764      }
1765
1766      // The basic rebalancing operation.  Logically copies the
1767      // rope.  The result has refcount of 1.  The client will
1768      // usually decrement the reference count of __r.
1769      // The result is within height 2 of balanced by the above
1770      // definition.
1771      static _RopeRep* _S_balance(_RopeRep* __r);
1772
1773      // Add all unbalanced subtrees to the forest of balanced trees.
1774      // Used only by balance.
1775      static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
1776
1777      // Add __r to forest, assuming __r is already balanced.
1778      static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
1779      
1780      // Print to stdout, exposing structure
1781      static void _S_dump(_RopeRep* __r, int __indent = 0);
1782      
1783      // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
1784      static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
1785      
1786    public:
1787      bool
1788      empty() const
1789      { return 0 == this->_M_tree_ptr; }
1790      
1791      // Comparison member function.  This is public only for those
1792      // clients that need a ternary comparison.  Others
1793      // should use the comparison operators below.
1794      int
1795      compare(const rope& __y) const
1796      { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
1797
1798      rope(const _CharT* __s, const allocator_type& __a = allocator_type())
1799      : _Base(__a)
1800      {
1801	this->_M_tree_ptr =
1802	  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
1803					   _M_get_allocator());
1804      }
1805
1806      rope(const _CharT* __s, size_t __len,
1807	   const allocator_type& __a = allocator_type())
1808      : _Base(__a)
1809      {
1810	this->_M_tree_ptr =
1811	  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
1812      }
1813
1814      // Should perhaps be templatized with respect to the iterator type
1815      // and use Sequence_buffer.  (It should perhaps use sequence_buffer
1816      // even now.)
1817      rope(const _CharT* __s, const _CharT* __e,
1818	   const allocator_type& __a = allocator_type())
1819      : _Base(__a)
1820      {
1821	this->_M_tree_ptr =
1822	  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
1823      }
1824
1825      rope(const const_iterator& __s, const const_iterator& __e,
1826	   const allocator_type& __a = allocator_type())
1827      : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1828			   __e._M_current_pos), __a)
1829      { }
1830
1831      rope(const iterator& __s, const iterator& __e,
1832	   const allocator_type& __a = allocator_type())
1833      : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1834			   __e._M_current_pos), __a)
1835      { }
1836
1837      rope(_CharT __c, const allocator_type& __a = allocator_type())
1838      : _Base(__a)
1839      {
1840	_CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
1841	
1842	_M_get_allocator().construct(__buf, __c);
1843	__try
1844	  {
1845	    this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
1846						_M_get_allocator());
1847	  }
1848	__catch(...)
1849	  {
1850	    _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
1851	    __throw_exception_again;
1852	  }
1853      }
1854
1855      rope(size_t __n, _CharT __c,
1856	   const allocator_type& __a = allocator_type());
1857
1858      rope(const allocator_type& __a = allocator_type())
1859      : _Base(0, __a) { }
1860
1861      // Construct a rope from a function that can compute its members
1862      rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
1863	   const allocator_type& __a = allocator_type())
1864      : _Base(__a)
1865      {
1866	this->_M_tree_ptr = (0 == __len) ?
1867	  0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
1868      }
1869
1870      rope(const rope& __x, const allocator_type& __a = allocator_type())
1871      : _Base(__x._M_tree_ptr, __a)
1872      { _S_ref(this->_M_tree_ptr); }
1873
1874      ~rope() throw()
1875      { _S_unref(this->_M_tree_ptr); }
1876
1877      rope&
1878      operator=(const rope& __x)
1879      {
1880	_RopeRep* __old = this->_M_tree_ptr;
1881	this->_M_tree_ptr = __x._M_tree_ptr;
1882	_S_ref(this->_M_tree_ptr);
1883	_S_unref(__old);
1884	return *this;
1885      }
1886
1887      void
1888      clear()
1889      {
1890	_S_unref(this->_M_tree_ptr);
1891	this->_M_tree_ptr = 0;
1892      }
1893      
1894      void
1895      push_back(_CharT __x)
1896      {
1897	_RopeRep* __old = this->_M_tree_ptr;
1898	this->_M_tree_ptr
1899	  = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
1900	_S_unref(__old);
1901      }
1902
1903      void
1904      pop_back()
1905      {
1906	_RopeRep* __old = this->_M_tree_ptr;
1907	this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
1908					 0, this->_M_tree_ptr->_M_size - 1);
1909	_S_unref(__old);
1910      }
1911
1912      _CharT
1913      back() const
1914      { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
1915
1916      void
1917      push_front(_CharT __x)
1918      {
1919	_RopeRep* __old = this->_M_tree_ptr;
1920	_RopeRep* __left =
1921	  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
1922	__try
1923	  {
1924	    this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
1925	    _S_unref(__old);
1926	    _S_unref(__left);
1927	  }
1928	__catch(...)
1929	  {
1930	    _S_unref(__left);
1931	    __throw_exception_again;
1932	  }
1933      }
1934
1935      void
1936      pop_front()
1937      {
1938	_RopeRep* __old = this->_M_tree_ptr;
1939	this->_M_tree_ptr
1940	  = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
1941	_S_unref(__old);
1942      }
1943
1944      _CharT
1945      front() const
1946      { return _S_fetch(this->_M_tree_ptr, 0); }
1947
1948      void
1949      balance()
1950      {
1951	_RopeRep* __old = this->_M_tree_ptr;
1952	this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
1953	_S_unref(__old);
1954      }
1955
1956      void
1957      copy(_CharT* __buffer) const
1958      {
1959	_Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
1960	_S_flatten(this->_M_tree_ptr, __buffer);
1961      }
1962
1963      // This is the copy function from the standard, but
1964      // with the arguments reordered to make it consistent with the
1965      // rest of the interface.
1966      // Note that this guaranteed not to compile if the draft standard
1967      // order is assumed.
1968      size_type
1969      copy(size_type __pos, size_type __n, _CharT* __buffer) const
1970      {
1971	size_t __size = size();
1972	size_t __len = (__pos + __n > __size? __size - __pos : __n);
1973
1974	_Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
1975	_S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
1976	return __len;
1977      }
1978
1979      // Print to stdout, exposing structure.  May be useful for
1980      // performance debugging.
1981      void
1982      dump()
1983      { _S_dump(this->_M_tree_ptr); }
1984      
1985      // Convert to 0 terminated string in new allocated memory.
1986      // Embedded 0s in the input do not terminate the copy.
1987      const _CharT* c_str() const;
1988
1989      // As above, but also use the flattened representation as
1990      // the new rope representation.
1991      const _CharT* replace_with_c_str();
1992      
1993      // Reclaim memory for the c_str generated flattened string.
1994      // Intentionally undocumented, since it's hard to say when this
1995      // is safe for multiple threads.
1996      void
1997      delete_c_str ()
1998      {
1999	if (0 == this->_M_tree_ptr)
2000	  return;
2001	if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
2002	    ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
2003	    this->_M_tree_ptr->_M_c_string)
2004	  {
2005	    // Representation shared
2006	    return;
2007	  }
2008#ifndef __GC
2009	this->_M_tree_ptr->_M_free_c_string();
2010#endif
2011	this->_M_tree_ptr->_M_c_string = 0;
2012      }
2013
2014      _CharT
2015      operator[] (size_type __pos) const
2016      { return _S_fetch(this->_M_tree_ptr, __pos); }
2017
2018      _CharT
2019      at(size_type __pos) const
2020      {
2021	// if (__pos >= size()) throw out_of_range;  // XXX
2022	return (*this)[__pos];
2023      }
2024
2025      const_iterator
2026      begin() const
2027      { return(const_iterator(this->_M_tree_ptr, 0)); }
2028
2029      // An easy way to get a const iterator from a non-const container.
2030      const_iterator
2031      const_begin() const
2032      { return(const_iterator(this->_M_tree_ptr, 0)); }
2033
2034      const_iterator
2035      end() const
2036      { return(const_iterator(this->_M_tree_ptr, size())); }
2037
2038      const_iterator
2039      const_end() const
2040      { return(const_iterator(this->_M_tree_ptr, size())); }
2041
2042      size_type
2043      size() const
2044      {	return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
2045      
2046      size_type
2047      length() const
2048      {	return size(); }
2049
2050      size_type
2051      max_size() const
2052      {
2053	return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
2054	//  Guarantees that the result can be sufficiently
2055	//  balanced.  Longer ropes will probably still work,
2056	//  but it's harder to make guarantees.
2057      }
2058
2059      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2060
2061      const_reverse_iterator
2062      rbegin() const
2063      { return const_reverse_iterator(end()); }
2064
2065      const_reverse_iterator
2066      const_rbegin() const
2067      {	return const_reverse_iterator(end()); }
2068
2069      const_reverse_iterator
2070      rend() const
2071      { return const_reverse_iterator(begin()); }
2072      
2073      const_reverse_iterator
2074      const_rend() const
2075      {	return const_reverse_iterator(begin()); }
2076
2077      template<class _CharT2, class _Alloc2>
2078        friend rope<_CharT2, _Alloc2>
2079        operator+(const rope<_CharT2, _Alloc2>& __left,
2080		  const rope<_CharT2, _Alloc2>& __right);
2081
2082      template<class _CharT2, class _Alloc2>
2083        friend rope<_CharT2, _Alloc2>
2084        operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
2085
2086      template<class _CharT2, class _Alloc2>
2087        friend rope<_CharT2, _Alloc2>
2088        operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
2089
2090      // The symmetric cases are intentionally omitted, since they're
2091      // presumed to be less common, and we don't handle them as well.
2092
2093      // The following should really be templatized.  The first
2094      // argument should be an input iterator or forward iterator with
2095      // value_type _CharT.
2096      rope&
2097      append(const _CharT* __iter, size_t __n)
2098      {
2099	_RopeRep* __result =
2100	  _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
2101	_S_unref(this->_M_tree_ptr);
2102	this->_M_tree_ptr = __result;
2103	return *this;
2104      }
2105
2106      rope&
2107      append(const _CharT* __c_string)
2108      {
2109	size_t __len = _S_char_ptr_len(__c_string);
2110	append(__c_string, __len);
2111	return(*this);
2112      }
2113
2114      rope&
2115      append(const _CharT* __s, const _CharT* __e)
2116      {
2117	_RopeRep* __result =
2118	  _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
2119	_S_unref(this->_M_tree_ptr);
2120	this->_M_tree_ptr = __result;
2121	return *this;
2122      }
2123
2124      rope&
2125      append(const_iterator __s, const_iterator __e)
2126      {
2127	_Self_destruct_ptr __appendee(_S_substring(__s._M_root,
2128						   __s._M_current_pos,
2129						   __e._M_current_pos));
2130	_RopeRep* __result = _S_concat(this->_M_tree_ptr, 
2131				       (_RopeRep*)__appendee);
2132	_S_unref(this->_M_tree_ptr);
2133	this->_M_tree_ptr = __result;
2134	return *this;
2135      }
2136
2137      rope&
2138      append(_CharT __c)
2139      {
2140	_RopeRep* __result =
2141	  _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
2142	_S_unref(this->_M_tree_ptr);
2143	this->_M_tree_ptr = __result;
2144	return *this;
2145      }
2146
2147      rope&
2148      append()
2149      { return append(_CharT()); }  // XXX why?
2150
2151      rope&
2152      append(const rope& __y)
2153      {
2154	_RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
2155	_S_unref(this->_M_tree_ptr);
2156	this->_M_tree_ptr = __result;
2157	return *this;
2158      }
2159
2160      rope&
2161      append(size_t __n, _CharT __c)
2162      {
2163	rope<_CharT,_Alloc> __last(__n, __c);
2164	return append(__last);
2165      }
2166
2167      void
2168      swap(rope& __b)
2169      {
2170	_RopeRep* __tmp = this->_M_tree_ptr;
2171	this->_M_tree_ptr = __b._M_tree_ptr;
2172	__b._M_tree_ptr = __tmp;
2173      }
2174
2175    protected:
2176      // Result is included in refcount.
2177      static _RopeRep*
2178      replace(_RopeRep* __old, size_t __pos1,
2179	      size_t __pos2, _RopeRep* __r)
2180      {
2181	if (0 == __old)
2182	  {
2183	    _S_ref(__r);
2184	    return __r;
2185	  }
2186	_Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
2187	_Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
2188	_RopeRep* __result;
2189
2190	if (0 == __r)
2191	  __result = _S_concat(__left, __right);
2192	else
2193	  {
2194	    _Self_destruct_ptr __left_result(_S_concat(__left, __r));
2195	    __result = _S_concat(__left_result, __right);
2196	  }
2197	return __result;
2198      }
2199
2200    public:
2201      void
2202      insert(size_t __p, const rope& __r)
2203      {
2204	_RopeRep* __result =
2205	  replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
2206	_S_unref(this->_M_tree_ptr);
2207	this->_M_tree_ptr = __result;
2208      }
2209
2210      void
2211      insert(size_t __p, size_t __n, _CharT __c)
2212      {
2213	rope<_CharT,_Alloc> __r(__n,__c);
2214	insert(__p, __r);
2215      }
2216      
2217      void
2218      insert(size_t __p, const _CharT* __i, size_t __n)
2219      {
2220	_Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
2221	_Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
2222						__p, size()));
2223	_Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
2224	// _S_ destr_concat_char_iter should be safe here.
2225	// But as it stands it's probably not a win, since __left
2226	// is likely to have additional references.
2227	_RopeRep* __result = _S_concat(__left_result, __right);
2228	_S_unref(this->_M_tree_ptr);
2229	this->_M_tree_ptr = __result;
2230      }
2231
2232      void
2233      insert(size_t __p, const _CharT* __c_string)
2234      {	insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
2235
2236      void
2237      insert(size_t __p, _CharT __c)
2238      { insert(__p, &__c, 1); }
2239
2240      void
2241      insert(size_t __p)
2242      {
2243	_CharT __c = _CharT();
2244	insert(__p, &__c, 1);
2245      }
2246
2247      void
2248      insert(size_t __p, const _CharT* __i, const _CharT* __j)
2249      {
2250	rope __r(__i, __j);
2251	insert(__p, __r);
2252      }
2253
2254      void
2255      insert(size_t __p, const const_iterator& __i,
2256	     const const_iterator& __j)
2257      {
2258	rope __r(__i, __j);
2259	insert(__p, __r);
2260      }
2261
2262      void
2263      insert(size_t __p, const iterator& __i,
2264	     const iterator& __j)
2265      {
2266	rope __r(__i, __j);
2267	insert(__p, __r);
2268      }
2269
2270      // (position, length) versions of replace operations:
2271      
2272      void
2273      replace(size_t __p, size_t __n, const rope& __r)
2274      {
2275	_RopeRep* __result =
2276	  replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
2277	_S_unref(this->_M_tree_ptr);
2278	this->_M_tree_ptr = __result;
2279      }
2280
2281      void
2282      replace(size_t __p, size_t __n,
2283	      const _CharT* __i, size_t __i_len)
2284      {
2285	rope __r(__i, __i_len);
2286	replace(__p, __n, __r);
2287      }
2288
2289      void
2290      replace(size_t __p, size_t __n, _CharT __c)
2291      {
2292	rope __r(__c);
2293	replace(__p, __n, __r);
2294      }
2295
2296      void
2297      replace(size_t __p, size_t __n, const _CharT* __c_string)
2298      {
2299	rope __r(__c_string);
2300	replace(__p, __n, __r);
2301      }
2302      
2303      void
2304      replace(size_t __p, size_t __n,
2305	      const _CharT* __i, const _CharT* __j)
2306      {
2307	rope __r(__i, __j);
2308	replace(__p, __n, __r);
2309      }
2310      
2311      void
2312      replace(size_t __p, size_t __n,
2313	      const const_iterator& __i, const const_iterator& __j)
2314      {
2315	rope __r(__i, __j);
2316	replace(__p, __n, __r);
2317      }
2318
2319      void
2320      replace(size_t __p, size_t __n,
2321	      const iterator& __i, const iterator& __j)
2322      {
2323	rope __r(__i, __j);
2324	replace(__p, __n, __r);
2325      }
2326
2327      // Single character variants:
2328      void
2329      replace(size_t __p, _CharT __c)
2330      {
2331	iterator __i(this, __p);
2332	*__i = __c;
2333      }
2334
2335      void
2336      replace(size_t __p, const rope& __r)
2337      { replace(__p, 1, __r); }
2338
2339      void
2340      replace(size_t __p, const _CharT* __i, size_t __i_len)
2341      { replace(__p, 1, __i, __i_len); }
2342
2343      void
2344      replace(size_t __p, const _CharT* __c_string)
2345      {	replace(__p, 1, __c_string); }
2346
2347      void
2348      replace(size_t __p, const _CharT* __i, const _CharT* __j)
2349      {	replace(__p, 1, __i, __j); }
2350
2351      void
2352      replace(size_t __p, const const_iterator& __i,
2353	      const const_iterator& __j)
2354      { replace(__p, 1, __i, __j); }
2355
2356      void
2357      replace(size_t __p, const iterator& __i,
2358	      const iterator& __j)
2359      { replace(__p, 1, __i, __j); }
2360
2361      // Erase, (position, size) variant.
2362      void
2363      erase(size_t __p, size_t __n)
2364      {
2365	_RopeRep* __result = replace(this->_M_tree_ptr, __p,
2366				     __p + __n, 0);
2367	_S_unref(this->_M_tree_ptr);
2368	this->_M_tree_ptr = __result;
2369      }
2370
2371      // Erase, single character
2372      void
2373      erase(size_t __p)
2374      { erase(__p, __p + 1); }
2375
2376      // Insert, iterator variants.
2377      iterator
2378      insert(const iterator& __p, const rope& __r)
2379      {
2380	insert(__p.index(), __r);
2381	return __p;
2382      }
2383
2384      iterator
2385      insert(const iterator& __p, size_t __n, _CharT __c)
2386      {
2387	insert(__p.index(), __n, __c);
2388	return __p;
2389      }
2390
2391      iterator insert(const iterator& __p, _CharT __c)
2392      {
2393	insert(__p.index(), __c);
2394	return __p;
2395      }
2396      
2397      iterator
2398      insert(const iterator& __p )
2399      {
2400	insert(__p.index());
2401	return __p;
2402      }
2403      
2404      iterator
2405      insert(const iterator& __p, const _CharT* c_string)
2406      {
2407	insert(__p.index(), c_string);
2408	return __p;
2409      }
2410      
2411      iterator
2412      insert(const iterator& __p, const _CharT* __i, size_t __n)
2413      {
2414	insert(__p.index(), __i, __n);
2415	return __p;
2416      }
2417      
2418      iterator
2419      insert(const iterator& __p, const _CharT* __i,
2420	     const _CharT* __j)
2421      {
2422	insert(__p.index(), __i, __j); 
2423	return __p;
2424      }
2425      
2426      iterator
2427      insert(const iterator& __p,
2428	     const const_iterator& __i, const const_iterator& __j)
2429      {
2430	insert(__p.index(), __i, __j);
2431	return __p;
2432      }
2433      
2434      iterator
2435      insert(const iterator& __p,
2436	     const iterator& __i, const iterator& __j)
2437      {
2438	insert(__p.index(), __i, __j);
2439	return __p;
2440      }
2441
2442      // Replace, range variants.
2443      void
2444      replace(const iterator& __p, const iterator& __q, const rope& __r)
2445      {	replace(__p.index(), __q.index() - __p.index(), __r); }
2446
2447      void
2448      replace(const iterator& __p, const iterator& __q, _CharT __c)
2449      { replace(__p.index(), __q.index() - __p.index(), __c); }
2450      
2451      void
2452      replace(const iterator& __p, const iterator& __q,
2453	      const _CharT* __c_string)
2454      { replace(__p.index(), __q.index() - __p.index(), __c_string); }
2455      
2456      void
2457      replace(const iterator& __p, const iterator& __q,
2458	      const _CharT* __i, size_t __n)
2459      { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
2460      
2461      void
2462      replace(const iterator& __p, const iterator& __q,
2463	      const _CharT* __i, const _CharT* __j)
2464      { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2465      
2466      void
2467      replace(const iterator& __p, const iterator& __q,
2468	      const const_iterator& __i, const const_iterator& __j)
2469      { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2470      
2471      void
2472      replace(const iterator& __p, const iterator& __q,
2473	      const iterator& __i, const iterator& __j)
2474      { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2475
2476      // Replace, iterator variants.
2477      void
2478      replace(const iterator& __p, const rope& __r)
2479      { replace(__p.index(), __r); }
2480      
2481      void
2482      replace(const iterator& __p, _CharT __c)
2483      { replace(__p.index(), __c); }
2484      
2485      void
2486      replace(const iterator& __p, const _CharT* __c_string)
2487      { replace(__p.index(), __c_string); }
2488      
2489      void
2490      replace(const iterator& __p, const _CharT* __i, size_t __n)
2491      { replace(__p.index(), __i, __n); }
2492      
2493      void
2494      replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
2495      { replace(__p.index(), __i, __j); }
2496      
2497      void
2498      replace(const iterator& __p, const_iterator __i, const_iterator __j)
2499      { replace(__p.index(), __i, __j); }
2500      
2501      void
2502      replace(const iterator& __p, iterator __i, iterator __j)
2503      { replace(__p.index(), __i, __j); }
2504
2505      // Iterator and range variants of erase
2506      iterator
2507      erase(const iterator& __p, const iterator& __q)
2508      {
2509	size_t __p_index = __p.index();
2510	erase(__p_index, __q.index() - __p_index);
2511	return iterator(this, __p_index);
2512      }
2513
2514      iterator
2515      erase(const iterator& __p)
2516      {
2517	size_t __p_index = __p.index();
2518	erase(__p_index, 1);
2519	return iterator(this, __p_index);
2520      }
2521
2522      rope
2523      substr(size_t __start, size_t __len = 1) const
2524      {
2525	return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2526						 __start,
2527						 __start + __len));
2528      }
2529
2530      rope
2531      substr(iterator __start, iterator __end) const
2532      {
2533	return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2534						 __start.index(),
2535						 __end.index()));
2536      }
2537
2538      rope
2539      substr(iterator __start) const
2540      {
2541	size_t __pos = __start.index();
2542	return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2543						 __pos, __pos + 1));
2544      }
2545
2546      rope
2547      substr(const_iterator __start, const_iterator __end) const
2548      {
2549	// This might eventually take advantage of the cache in the
2550	// iterator.
2551	return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2552						 __start.index(),
2553						 __end.index()));
2554      }
2555
2556      rope<_CharT, _Alloc>
2557      substr(const_iterator __start)
2558      {
2559	size_t __pos = __start.index();
2560	return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2561						 __pos, __pos + 1));
2562      }
2563
2564      static const size_type npos;
2565
2566      size_type find(_CharT __c, size_type __pos = 0) const;
2567
2568      size_type
2569      find(const _CharT* __s, size_type __pos = 0) const
2570      {
2571	size_type __result_pos;
2572	const_iterator __result =
2573	  std::search(const_begin() + __pos, const_end(),
2574		      __s, __s + _S_char_ptr_len(__s));
2575	__result_pos = __result.index();
2576#ifndef __STL_OLD_ROPE_SEMANTICS
2577	if (__result_pos == size())
2578	  __result_pos = npos;
2579#endif
2580	return __result_pos;
2581      }
2582
2583      iterator
2584      mutable_begin()
2585      { return(iterator(this, 0)); }
2586      
2587      iterator
2588      mutable_end()
2589      { return(iterator(this, size())); }
2590
2591      typedef std::reverse_iterator<iterator> reverse_iterator;
2592      
2593      reverse_iterator
2594      mutable_rbegin()
2595      { return reverse_iterator(mutable_end()); }
2596
2597      reverse_iterator
2598      mutable_rend()
2599      { return reverse_iterator(mutable_begin()); }
2600
2601      reference
2602      mutable_reference_at(size_type __pos)
2603      { return reference(this, __pos); }
2604
2605#ifdef __STD_STUFF
2606      reference
2607      operator[] (size_type __pos)
2608      { return _char_ref_proxy(this, __pos); }
2609
2610      reference
2611      at(size_type __pos)
2612      {
2613	// if (__pos >= size()) throw out_of_range;  // XXX
2614	return (*this)[__pos];
2615      }
2616      
2617      void resize(size_type __n, _CharT __c) { }
2618      void resize(size_type __n) { }
2619      void reserve(size_type __res_arg = 0) { }
2620      
2621      size_type
2622      capacity() const
2623      { return max_size(); }
2624
2625      // Stuff below this line is dangerous because it's error prone.
2626      // I would really like to get rid of it.
2627      // copy function with funny arg ordering.
2628      size_type
2629      copy(_CharT* __buffer, size_type __n,
2630	   size_type __pos = 0) const
2631      { return copy(__pos, __n, __buffer); }
2632
2633      iterator
2634      end()
2635      { return mutable_end(); }
2636
2637      iterator
2638      begin()
2639      { return mutable_begin(); }
2640
2641      reverse_iterator
2642      rend()
2643      { return mutable_rend(); }
2644      
2645      reverse_iterator
2646      rbegin()
2647      { return mutable_rbegin(); }
2648
2649#else
2650      const_iterator
2651      end()
2652      { return const_end(); }
2653
2654      const_iterator
2655      begin()
2656      { return const_begin(); }
2657
2658      const_reverse_iterator
2659      rend()
2660      { return const_rend(); }
2661
2662      const_reverse_iterator
2663      rbegin()
2664      { return const_rbegin(); }
2665
2666#endif
2667    };
2668
2669  template <class _CharT, class _Alloc>
2670    const typename rope<_CharT, _Alloc>::size_type
2671    rope<_CharT, _Alloc>::npos = (size_type)(-1);
2672  
2673  template <class _CharT, class _Alloc>
2674    inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2675			   const _Rope_const_iterator<_CharT, _Alloc>& __y)
2676    { return (__x._M_current_pos == __y._M_current_pos
2677	      && __x._M_root == __y._M_root); }
2678
2679  template <class _CharT, class _Alloc>
2680    inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2681			  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2682    { return (__x._M_current_pos < __y._M_current_pos); }
2683
2684  template <class _CharT, class _Alloc>
2685    inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2686			   const _Rope_const_iterator<_CharT, _Alloc>& __y)
2687    { return !(__x == __y); }
2688
2689  template <class _CharT, class _Alloc>
2690    inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2691			  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2692    { return __y < __x; }
2693
2694  template <class _CharT, class _Alloc>
2695    inline bool
2696    operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2697	       const _Rope_const_iterator<_CharT, _Alloc>& __y)
2698    { return !(__y < __x); }
2699
2700  template <class _CharT, class _Alloc>
2701    inline bool
2702    operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2703	       const _Rope_const_iterator<_CharT, _Alloc>& __y)
2704    { return !(__x < __y); }
2705
2706  template <class _CharT, class _Alloc>
2707    inline ptrdiff_t
2708    operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2709	      const _Rope_const_iterator<_CharT, _Alloc>& __y)
2710    { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
2711
2712  template <class _CharT, class _Alloc>
2713    inline _Rope_const_iterator<_CharT, _Alloc>
2714    operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2715    { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2716						  __x._M_current_pos - __n); }
2717
2718  template <class _CharT, class _Alloc>
2719    inline _Rope_const_iterator<_CharT, _Alloc>
2720    operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2721    { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2722						  __x._M_current_pos + __n); }
2723
2724  template <class _CharT, class _Alloc>
2725    inline _Rope_const_iterator<_CharT, _Alloc>
2726    operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
2727  { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2728						__x._M_current_pos + __n); }
2729
2730  template <class _CharT, class _Alloc>
2731    inline bool
2732    operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
2733	       const _Rope_iterator<_CharT, _Alloc>& __y)
2734    {return (__x._M_current_pos == __y._M_current_pos
2735	     && __x._M_root_rope == __y._M_root_rope); }
2736  
2737  template <class _CharT, class _Alloc>
2738    inline bool
2739    operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
2740	      const _Rope_iterator<_CharT, _Alloc>& __y)
2741    { return (__x._M_current_pos < __y._M_current_pos); }
2742
2743  template <class _CharT, class _Alloc>
2744    inline bool
2745    operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
2746	       const _Rope_iterator<_CharT, _Alloc>& __y)
2747    { return !(__x == __y); }
2748
2749  template <class _CharT, class _Alloc>
2750    inline bool
2751    operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
2752	      const _Rope_iterator<_CharT, _Alloc>& __y)
2753    { return __y < __x; }
2754
2755  template <class _CharT, class _Alloc>
2756    inline bool
2757    operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
2758	       const _Rope_iterator<_CharT, _Alloc>& __y)
2759    { return !(__y < __x); }
2760
2761  template <class _CharT, class _Alloc>
2762    inline bool
2763    operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
2764	       const _Rope_iterator<_CharT, _Alloc>& __y)
2765    { return !(__x < __y); }
2766
2767  template <class _CharT, class _Alloc>
2768    inline ptrdiff_t
2769    operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2770	      const _Rope_iterator<_CharT, _Alloc>& __y)
2771    { return ((ptrdiff_t)__x._M_current_pos
2772	      - (ptrdiff_t)__y._M_current_pos); }
2773
2774  template <class _CharT, class _Alloc>
2775    inline _Rope_iterator<_CharT, _Alloc>
2776    operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2777	      ptrdiff_t __n)
2778    { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2779					    __x._M_current_pos - __n); }
2780
2781  template <class _CharT, class _Alloc>
2782    inline _Rope_iterator<_CharT, _Alloc>
2783    operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2784    { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2785					    __x._M_current_pos + __n); }
2786
2787  template <class _CharT, class _Alloc>
2788    inline _Rope_iterator<_CharT, _Alloc>
2789    operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
2790    { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2791					    __x._M_current_pos + __n); }
2792
2793  template <class _CharT, class _Alloc>
2794    inline rope<_CharT, _Alloc>
2795    operator+(const rope<_CharT, _Alloc>& __left,
2796	      const rope<_CharT, _Alloc>& __right)
2797    {
2798      // Inlining this should make it possible to keep __left and
2799      // __right in registers.
2800      typedef rope<_CharT, _Alloc> rope_type;
2801      return rope_type(rope_type::_S_concat(__left._M_tree_ptr, 
2802					    __right._M_tree_ptr));
2803    }
2804
2805  template <class _CharT, class _Alloc>
2806    inline rope<_CharT, _Alloc>&
2807    operator+=(rope<_CharT, _Alloc>& __left,
2808	       const rope<_CharT, _Alloc>& __right)
2809    {
2810      __left.append(__right);
2811      return __left;
2812    }
2813
2814  template <class _CharT, class _Alloc>
2815    inline rope<_CharT, _Alloc>
2816    operator+(const rope<_CharT, _Alloc>& __left,
2817	      const _CharT* __right)
2818    {
2819      typedef rope<_CharT, _Alloc> rope_type;
2820      size_t __rlen = rope_type::_S_char_ptr_len(__right);
2821      return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2822						      __right, __rlen));
2823    }
2824
2825  template <class _CharT, class _Alloc>
2826    inline rope<_CharT, _Alloc>&
2827    operator+=(rope<_CharT, _Alloc>& __left,
2828	       const _CharT* __right)
2829    {
2830      __left.append(__right);
2831      return __left;
2832    }
2833
2834  template <class _CharT, class _Alloc>
2835    inline rope<_CharT, _Alloc>
2836    operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
2837    {
2838      typedef rope<_CharT, _Alloc> rope_type;
2839      return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2840						      &__right, 1));
2841    }
2842
2843  template <class _CharT, class _Alloc>
2844    inline rope<_CharT, _Alloc>&
2845    operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
2846    {
2847      __left.append(__right);
2848      return __left;
2849    }
2850  
2851  template <class _CharT, class _Alloc>
2852    bool
2853    operator<(const rope<_CharT, _Alloc>& __left,
2854	      const rope<_CharT, _Alloc>& __right)
2855    { return __left.compare(__right) < 0; }
2856
2857  template <class _CharT, class _Alloc>
2858    bool
2859    operator==(const rope<_CharT, _Alloc>& __left,
2860	       const rope<_CharT, _Alloc>& __right)
2861    { return __left.compare(__right) == 0; }
2862
2863  template <class _CharT, class _Alloc>
2864    inline bool
2865    operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2866	       const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2867    { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
2868
2869  template <class _CharT, class _Alloc>
2870    inline bool
2871    operator!=(const rope<_CharT, _Alloc>& __x,
2872	       const rope<_CharT, _Alloc>& __y)
2873    { return !(__x == __y); }
2874
2875  template <class _CharT, class _Alloc>
2876    inline bool
2877    operator>(const rope<_CharT, _Alloc>& __x,
2878	      const rope<_CharT, _Alloc>& __y)
2879    { return __y < __x; }
2880
2881  template <class _CharT, class _Alloc>
2882    inline bool
2883    operator<=(const rope<_CharT, _Alloc>& __x,
2884	       const rope<_CharT, _Alloc>& __y)
2885    { return !(__y < __x); }
2886
2887  template <class _CharT, class _Alloc>
2888    inline bool
2889    operator>=(const rope<_CharT, _Alloc>& __x,
2890	       const rope<_CharT, _Alloc>& __y)
2891    { return !(__x < __y); }
2892
2893  template <class _CharT, class _Alloc>
2894    inline bool
2895    operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2896	       const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2897    { return !(__x == __y); }
2898
2899  template<class _CharT, class _Traits, class _Alloc>
2900    std::basic_ostream<_CharT, _Traits>&
2901    operator<<(std::basic_ostream<_CharT, _Traits>& __o,
2902	       const rope<_CharT, _Alloc>& __r);
2903
2904  typedef rope<char> crope;
2905  typedef rope<wchar_t> wrope;
2906
2907  inline crope::reference
2908  __mutable_reference_at(crope& __c, size_t __i)
2909  { return __c.mutable_reference_at(__i); }
2910
2911  inline wrope::reference
2912  __mutable_reference_at(wrope& __c, size_t __i)
2913  { return __c.mutable_reference_at(__i); }
2914
2915  template <class _CharT, class _Alloc>
2916    inline void
2917    swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
2918    { __x.swap(__y); }
2919
2920_GLIBCXX_END_NAMESPACE
2921
2922
2923namespace std
2924{ 
2925namespace tr1
2926{
2927  template<>
2928    struct hash<__gnu_cxx::crope>
2929    {
2930      size_t
2931      operator()(const __gnu_cxx::crope& __str) const
2932      {
2933	size_t __size = __str.size();
2934	if (0 == __size)
2935	  return 0;
2936	return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2937      }
2938    };
2939
2940
2941  template<>
2942    struct hash<__gnu_cxx::wrope>
2943    {
2944      size_t
2945      operator()(const __gnu_cxx::wrope& __str) const
2946      {
2947	size_t __size = __str.size();
2948	if (0 == __size)
2949	  return 0;
2950	return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2951      }
2952    };
2953} // namespace tr1
2954} // namespace std
2955
2956# include <ext/ropeimpl.h>
2957
2958#endif
2959