19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997
49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc.
59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997
79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology
89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999
109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev
119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed
139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk.
149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted
169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies.
179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted,
189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was
199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice.
209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* NOTE: This is an internal header file, included by other STL headers.
249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *   You should not attempt to use it directly.
259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// rope<_CharT,_Alloc> is a sequence of _CharT.
289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Ropes appear to be mutable, but update operations
299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// really copy enough of the data structure to leave the original
309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// valid.  Thus ropes can be logically copied by just copying
319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// a pointer value.
329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ROPE_H
349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_INTERNAL_ROPE_H
359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGOBASE_H
379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_algobase.h>
389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
40e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (_STLP_USE_NO_IOSTREAMS) && !defined (_STLP_INTERNAL_IOSFWD)
41e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#  include <stl/_iosfwd.h>
429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALLOC_H
459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_alloc.h>
469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ITERATOR_H
499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_iterator.h>
509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGO_H
539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_algo.h>
549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_function_base.h>
589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_NUMERIC_H
619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_numeric.h>
629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_HASH_FUN_H
659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_hash_fun.h>
669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_CHAR_TRAITS_H
699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/char_traits.h>
709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_THREADS_H
739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_threads.h>
749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifdef _STLP_SGI_THREADS
779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <mutex.h>
789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE
819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) (_Alloc_traits<_Tp,__atype>::create_allocator(__a))
829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) __stl_alloc_create(__a,(_Tp*)0)
849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE
879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// First a lot of forward declarations.  The standard seems to require
899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// much stricter "declaration before use" than many of the implementations
909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// that preceded it.
91e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate<class _CharT, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_CharT>) > class rope;
929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;
939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> struct _Rope_RopeRep;
949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> struct _Rope_RopeLeaf;
959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> struct _Rope_RopeFunction;
969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> struct _Rope_RopeSubstring;
979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> class _Rope_iterator;
989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> class _Rope_const_iterator;
999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> class _Rope_char_ref_proxy;
1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;
1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE
1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
104e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _CharT>
105e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct _BasicCharType { typedef __false_type _Ret; };
106e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott
107e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_TEMPLATE_NULL
108e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct _BasicCharType<char> { typedef __true_type _Ret; };
109e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott
110e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#ifdef _STLP_HAS_WCHAR_T
111e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_TEMPLATE_NULL
112e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct _BasicCharType<wchar_t> { typedef __true_type _Ret; };
113e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif
114e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott
1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Some helpers, so we can use the power algorithm on ropes.
1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// See below for why this isn't local to the implementation.
1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// This uses a nonstandard refcount convention.
1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// The result has refcount 0.
1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_Concat_fn
1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  : public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>,
1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                           rope<_CharT,_Alloc> > {
1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x,
1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                  const rope<_CharT,_Alloc>& __y) {
1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __x + __y;
1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline
1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>
1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return rope<_CharT,_Alloc>(); }
1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE
1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Store an eos
1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT>
1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void _S_construct_null_aux(_CharT *__p, const __true_type&)
1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ *__p = 0; }
1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT>
1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void _S_construct_null_aux(_CharT *__p, const __false_type&)
1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ _STLP_STD::_Construct(__p); }
1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT>
1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void _S_construct_null(_CharT *__p) {
1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _S_construct_null_aux(__p, _Char_Is_Integral());
1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}
1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// char_producers are logically functions that generate a section of
1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// a string.  These can be converted to ropes.  The resulting rope
1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// invokes the char_producer on demand.  This allows, for example,
1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// files to be viewed as ropes without reading the entire file.
1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT>
1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass char_producer {
1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  virtual ~char_producer() {}
1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  virtual void operator()(size_t __start_pos, size_t __len,
1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                          _CharT* __buffer) = 0;
1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Buffer should really be an arbitrary output iterator.
1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // That way we could flatten directly into an ostream, etc.
1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // This is thoroughly impossible, since iterator types don't
1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // have runtime descriptions.
1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Sequence buffers:
1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Sequence must provide an append operation that appends an
1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// array to the sequence.  Sequence buffers are useful only if
1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// appending an entire array is cheaper than appending element by element.
1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// This is true for many string representations.
1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// This should  perhaps inherit from ostream<sequence::value_type>
1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// and be implemented correspondingly, so that they can be used
1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// for formatted.  For the sake of portability, we don't do this yet.
1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// For now, sequence buffers behave as output iterators.  But they also
1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// behave a little like basic_ostringstream<sequence::value_type> and a
1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// little like containers.
1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _Sequence
1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \
1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))
1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block         , size_t _Buf_sz = 100
1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   if defined(__sgi) && !defined(__GNUC__)
1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   define __TYPEDEF_WORKAROUND
1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block         ,class _V = typename _Sequence::value_type
1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   endif /* __sgi */
1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block         >
1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// The 3rd parameter works around a common compiler bug.
1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass sequence_buffer : public iterator <output_iterator_tag, void, void, void, void> {
1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef __TYPEDEF_WORKAROUND
1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Sequence::value_type value_type;
1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef sequence_buffer<_Sequence
1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \
2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))
2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  , _Buf_sz
2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  > _Self;
2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# else /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  > _Self;
2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum { _Buf_sz = 100};
2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // # endif
2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# else /* __TYPEDEF_WORKAROUND */
2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _V value_type;
2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef sequence_buffer<_Sequence, _Buf_sz, _V> _Self;
2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif /* __TYPEDEF_WORKAROUND */
2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected:
2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Sequence* _M_prefix;
2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  value_type _M_buffer[_Buf_sz];
2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t     _M_buf_count;
2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void flush() {
2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buf_count = 0;
2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~sequence_buffer() { flush(); }
2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}
2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  sequence_buffer(const _Self& __x) {
2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_prefix = __x._M_prefix;
2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buf_count = __x._M_buf_count;
226e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _STLP_STD::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  sequence_buffer(_Self& __x) {
2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __x.flush();
2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_prefix = __x._M_prefix;
2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buf_count = 0;
2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}
2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (_Self& __x) {
2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __x.flush();
2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_prefix = __x._M_prefix;
2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buf_count = 0;
2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (const _Self& __x) {
2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_prefix = __x._M_prefix;
2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buf_count = __x._M_buf_count;
243e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _STLP_STD::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void push_back(value_type __x) {
2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (_M_buf_count < _Buf_sz) {
2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buffer[_M_buf_count] = __x;
2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      ++_M_buf_count;
2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      flush();
2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buffer[0] = __x;
2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_count = 1;
2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void append(const value_type *__s, size_t __len) {
2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__len + _M_buf_count <= _Buf_sz) {
2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      size_t __i = _M_buf_count;
2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      size_t __j = 0;
2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      for (; __j < __len; __i++, __j++) {
2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_buffer[__i] = __s[__j];
2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_count += __len;
2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else if (0 == _M_buf_count) {
2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_prefix->append(__s, __s + __len);
2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      flush();
2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      append(__s, __len);
2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& write(const value_type *__s, size_t __len) {
2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    append(__s, __len);
2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& put(value_type __x) {
2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    push_back(__x);
2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator=(const value_type& __rhs) {
2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    push_back(__rhs);
2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator*() { return *this; }
2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator++() { return *this; }
2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator++(int) { return *this; }
2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// The following should be treated as private, at least for now.
2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT>
2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_char_consumer {
2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_MEMBER_TEMPLATES)
2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //Without member templates we have to use run-time parameterization.
2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The symmetry with char_producer is accidental and temporary.
2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  virtual ~_Rope_char_consumer() {}
2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;
2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// What follows should really be local to rope.  Unfortunately,
3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// that doesn't work, since it makes it impossible to define generic
3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// equality on rope iterators.  According to the draft standard, the
3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// template parameters for such an equality operator cannot be inferred
3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// from the occurence of a member class as a parameter.
3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// (SGI compilers in fact allow this, but the __result wouldn't be
3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// portable.)
3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Similarly, some of the static member functions are member functions
3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// only to avoid polluting the global namespace, and to circumvent
3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// restrictions on type inference for template functions.
3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// The internal data structure for representing a rope.  This is
3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// private to the implementation.  A rope is really just a pointer
3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// to one of these.
3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// A few basic functions for manipulating this data structure
3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// are members of _RopeRep.  Most of the more complex algorithms
3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// are implemented as rope members.
3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Some of the static member functions of _RopeRep have identically
3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// named functions in rope that simply invoke the _RopeRep versions.
3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//
3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_RopeRep
3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  : public _Refcount_Base
3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{
3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT, _Alloc> _Self;
3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //
3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // GAB: 11/09/05
3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //
3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // "__ROPE_DEPTH_SIZE" is set to one more then the "__ROPE_MAX_DEPTH".
3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // This was originally just an addition of "__ROPE_MAX_DEPTH + 1"
3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // but this addition causes the sunpro compiler to complain about
3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // multiple declarations during the initialization of "_S_min_len".
3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Changed to be a fixed value and the sunpro compiler appears to
3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // be happy???
3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //
3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  define __ROPE_MAX_DEPTH  45
3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  define __ROPE_DEPTH_SIZE 46 // __ROPE_MAX_DEPTH + 1
3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum { _S_max_rope_depth = __ROPE_MAX_DEPTH };
3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Apparently needed by VC++
3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The data fields of leaves are allocated with some
3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // extra space, to accomodate future growth and for basic
3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // character types, to hold a trailing eos character.
3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum { _S_alloc_granularity = 8 };
3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Tag _M_tag:8;
3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool _M_is_balanced:8;
3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
356e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef _Alloc allocator_type;
3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  allocator_type get_allocator() const { return allocator_type(_M_size);  }
3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  unsigned char _M_depth;
3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT* _STLP_VOLATILE _M_c_string;
3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_PRIV _STLP_alloc_proxy<size_t, _CharT, allocator_type> _M_size;
3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
364e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#ifdef _STLP_NO_ARROW_OPERATOR
365e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  _Rope_RopeRep() : _Refcount_Base(1), _M_size(allocator_type(), 0) {
366e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#  if defined (_STLP_CHECK_RUNTIME_COMPATIBILITY)
367e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _STLP_CHECK_RUNTIME_COMPATIBILITY();
368e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#  endif
369e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  }
370e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif
3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* Flattened version of string, if needed.  */
3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* typically 0.                             */
3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* If it's not 0, then the memory is owned  */
3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* by this node.                            */
3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* In the case of a leaf, this may point to */
3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* the same memory as the data field.       */
3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeRep(_Tag __t, unsigned char __d, bool __b, size_t _p_size,
3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                allocator_type __a) :
3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Refcount_Base(1),
381e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0), _M_size(__a, _p_size) {
382e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (_STLP_CHECK_RUNTIME_COMPATIBILITY)
383e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _STLP_CHECK_RUNTIME_COMPATIBILITY();
384e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif
385e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    }
3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
387e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef _STLP_TYPENAME _STLP_PRIV _BasicCharType<_CharT>::_Ret _IsBasicCharType;
3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if 0
3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* Please tell why this code is necessary if you uncomment it.
3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * Problem with it is that rope implementation expect that _S_rounded_up_size(n)
3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * returns a size > n in order to store the terminating null charater. When
3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * instanciation type is not a char or wchar_t this is not guaranty resulting in
3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * memory overrun.
3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   */
3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _S_rounded_up_size_aux(size_t __n, __true_type const& /*_IsBasicCharType*/) {
3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // Allow slop for in-place expansion.
3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return (__n + _S_alloc_granularity) & ~(_S_alloc_granularity - 1);
3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _S_rounded_up_size_aux(size_t __n, __false_type const& /*_IsBasicCharType*/) {
4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // Allow slop for in-place expansion.
4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return (__n + _S_alloc_granularity - 1) & ~(_S_alloc_granularity - 1);
4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // fbp : moved from RopeLeaf
4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _S_rounded_up_size(size_t __n)
4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //{ return _S_rounded_up_size_aux(__n, _IsBasicCharType()); }
4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return (__n + _S_alloc_granularity) & ~(_S_alloc_granularity - 1); }
4109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_free_string( _CharT* __s, size_t __len,
4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                             allocator_type __a) {
4139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::_Destroy_Range(__s, __s + __len);
4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    //  This has to be a static member, so this gets a bit messy
4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE
4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __a.deallocate(__s, _S_rounded_up_size(__len));    //*ty 03/24/2001 - restored not to use __stl_alloc_rebind() since it is not defined under _STLP_MEMBER_TEMPLATE_CLASSES
4179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   else
4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __stl_alloc_rebind (__a, (_CharT*)0).deallocate(__s, _S_rounded_up_size(__len));
4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   endif
4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Deallocate data section of a leaf.
4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // This shouldn't be a member function.
4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // But its hard to do anything else at the
4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // moment, because it's templatized w.r.t.
4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // an allocator.
4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Does nothing if __GC is defined.
4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_free_c_string();
4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_free_tree();
4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Deallocate t. Assumes t is not 0.
4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_unref_nonnil() {
4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (_M_decr() == 0) _M_free_tree();
4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_ref_nonnil() {
4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_incr();
4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_unref(_Self* __t) {
4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 != __t) {
4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      __t->_M_unref_nonnil();
4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_ref(_Self* __t) {
4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 != __t) __t->_M_incr();
4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //static void _S_free_if_unref(_Self* __t) {
4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //  if (0 != __t && 0 == __t->_M_ref_count) __t->_M_free_tree();
4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //}
4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> {
4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT* _M_data; /* Not necessarily 0 terminated. */
4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                /* The allocated size is         */
4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                /* _S_rounded_up_size(size), except */
4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                /* in the GC case, in which it   */
4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                /* doesn't matter.               */
4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _RopeRep::_IsBasicCharType _IsBasicCharType;
4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_init(__true_type const& /*_IsBasicCharType*/) {
4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_c_string = _M_data;
4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_init(__false_type const& /*_IsBasicCharType*/) {}
4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _RopeRep::allocator_type allocator_type;
4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeLeaf( _CharT* __d, size_t _p_size, allocator_type __a)
4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _Rope_RopeRep<_CharT,_Alloc>(_RopeRep::_S_leaf, 0, true, _p_size, __a),
4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_data(__d) {
4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(_p_size > 0)
4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_init(_IsBasicCharType());
4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef _STLP_NO_ARROW_OPERATOR
4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeLeaf() {}
4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeLeaf(const _Rope_RopeLeaf<_CharT, _Alloc>& ) {}
4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// The constructor assumes that d has been allocated with
4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // the proper allocator and the properly padded size.
4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // In contrast, the destructor deallocates the data:
4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~_Rope_RopeLeaf() {
4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (_M_data != this->_M_c_string) {
4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_free_c_string();
4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_free_string(_M_data, this->_M_size._M_data, this->get_allocator());
4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT, _Alloc> {
4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _RopeRep* _M_left;
5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _RopeRep* _M_right;
5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _RopeRep::allocator_type allocator_type;
5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeConcatenation(_RopeRep* __l, _RopeRep* __r, allocator_type __a)
5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _Rope_RopeRep<_CharT,_Alloc>(_RopeRep::_S_concat,
5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                   (max)(__l->_M_depth, __r->_M_depth) + 1, false,
5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                   __l->_M_size._M_data + __r->_M_size._M_data, __a), _M_left(__l), _M_right(__r)
5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef _STLP_NO_ARROW_OPERATOR
5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeConcatenation() {}
5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeConcatenation(const _Rope_RopeConcatenation<_CharT, _Alloc>&) {}
5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~_Rope_RopeConcatenation() {
5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_free_c_string();
5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_left->_M_unref_nonnil();
5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_right->_M_unref_nonnil();
5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_RopeFunction : public _Rope_RopeRep<_CharT, _Alloc> {
5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  char_producer<_CharT>* _M_fn;
5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /*
5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * Char_producer is owned by the
5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * rope and should be explicitly
5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * deleted when the rope becomes
5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * inaccessible.
5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   */
5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool _M_delete_when_done;
5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Rope_RopeRep<_CharT,_Alloc>::allocator_type allocator_type;
5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef _STLP_NO_ARROW_OPERATOR
5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeFunction() {}
5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeFunction(const _Rope_RopeFunction<_CharT, _Alloc>& ) {}
5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeFunction(char_producer<_CharT>* __f, size_t _p_size,
5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                     bool __d, allocator_type __a)
5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _Rope_RopeRep<_CharT,_Alloc>(_RopeRep::_S_function, 0, true, _p_size, __a), _M_fn(__f)
5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    , _M_delete_when_done(__d)
5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _STLP_ASSERT(_p_size > 0) }
5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~_Rope_RopeFunction() {
5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_free_c_string();
5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (_M_delete_when_done) {
5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      delete _M_fn;
5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Substring results are usually represented using just
5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * concatenation nodes.  But in the case of very long flat ropes
5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or ropes with a functional representation that isn't practical.
5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * In that case, we represent the __result as a special case of
5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * RopeFunction, whose char_producer points back to the rope itself.
5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * In all cases except repeated substring operations and
5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * deallocation, we treat the __result as a RopeFunction.
5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
5639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_RopeSubstring : public char_producer<_CharT>, public _Rope_RopeFunction<_CharT,_Alloc> {
5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // XXX this whole class should be rewritten.
5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _RopeRep *_M_base;      // not 0
5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t _M_start;
5709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /* virtual */ void operator()(size_t __start_pos, size_t __req_len,
5719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                _CharT* __buffer) {
5729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    switch (_M_base->_M_tag) {
5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    case _RopeRep::_S_function:
5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    case _RopeRep::_S_substringfn:
5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      {
5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        char_producer<_CharT>* __fn =
5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          __STATIC_CAST(_RopeFunction*, _M_base)->_M_fn;
5809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _STLP_ASSERT(__start_pos + __req_len <= this->_M_size._M_data)
5819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _STLP_ASSERT(_M_start + this->_M_size._M_data <= _M_base->_M_size._M_data)
5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        (*__fn)(__start_pos + _M_start, __req_len, __buffer);
5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      break;
5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    case _RopeRep::_S_leaf:
5869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      {
5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _CharT* __s =
5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          __STATIC_CAST(_RopeLeaf*, _M_base)->_M_data;
5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _STLP_PRIV __ucopy_n(__s + __start_pos + _M_start, __req_len, __buffer);
5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      break;
5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    default:
5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _STLP_ASSERT(false)
5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        ;
5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _RopeRep::allocator_type allocator_type;
6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeSubstring(_RopeRep* __b, size_t __s, size_t __l, allocator_type __a)
6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a),
6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_base(__b), _M_start(__s) {
6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(__l > 0)
6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(__s + __l <= __b->_M_size._M_data)
6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_base->_M_ref_nonnil();
6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_tag = _RopeRep::_S_substringfn;
6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  virtual ~_Rope_RopeSubstring()
6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _M_base->_M_unref_nonnil(); }
6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Self-destructing pointers to Rope_rep.
6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * These are not conventional smart pointers.  Their
6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * only purpose in life is to ensure that unref is called
6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * on the pointer either at normal exit or if an exception
6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * is raised.  It is the caller's responsibility to
6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * adjust reference counts when these pointers are initialized
6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or assigned to.  (This convention significantly reduces
6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * the number of potentially expensive reference count
6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * updates.)
6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Rope_self_destruct_ptr {
6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeRep<_CharT,_Alloc>* _M_ptr;
6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~_Rope_self_destruct_ptr()
6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _Rope_RopeRep<_CharT,_Alloc>::_S_unref(_M_ptr); }
6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   ifdef _STLP_USE_EXCEPTIONS
6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_self_destruct_ptr() : _M_ptr(0) {}
6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   else
6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_self_destruct_ptr() {}
6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   endif
6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT,_Alloc>* __p) : _M_ptr(__p) {}
6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeRep<_CharT,_Alloc>& operator*() { return *_M_ptr; }
6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_RopeRep<_CharT,_Alloc>* operator->() { return _M_ptr; }
6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  operator _Rope_RopeRep<_CharT,_Alloc>*() { return _M_ptr; }
6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_self_destruct_ptr<_CharT, _Alloc>&
6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  operator= (_Rope_RopeRep<_CharT,_Alloc>* __x)
6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _M_ptr = __x; return *this; }
6419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Dereferencing a nonconst iterator has to return something
6459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * that behaves almost like a reference.  It's not possible to
6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * return an actual reference since assignment requires extra
6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * work.  And we would get into the same problems as with the
6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * CD2 version of basic_string.
6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_char_ref_proxy {
6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_ref_proxy<_CharT, _Alloc> _Self;
6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class rope<_CharT,_Alloc>;
6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_iterator<_CharT,_Alloc>;
6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_char_ptr_proxy<_CharT,_Alloc>;
6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;
6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef rope<_CharT,_Alloc> _My_rope;
6599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t _M_pos;
6609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT _M_current;
6619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool _M_current_valid;
6629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _My_rope* _M_root;     // The whole rope.
6639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
6649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ref_proxy(_My_rope* __r, size_t __p) :
6659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_pos(__p), _M_current_valid(false), _M_root(__r) {}
6669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ref_proxy(const _Self& __x) :
6679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_pos(__x._M_pos), _M_current_valid(false), _M_root(__x._M_root) {}
6689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Don't preserve cache if the reference can outlive the
6699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // expression.  We claim that's not possible without calling
6709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // a copy constructor or generating reference to a proxy
6719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // reference.  We declare the latter to have undefined semantics.
6729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
6739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {}
6749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  inline operator _CharT () const;
6759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (_CharT __c);
6769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ptr_proxy<_CharT, _Alloc> operator& () const;
6779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (const _Self& __c) {
6789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return operator=((_CharT)__c);
6799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
6809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
6819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
6839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class __Alloc>
6849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
6859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                 _Rope_char_ref_proxy <_CharT, __Alloc > __b) {
6869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT __tmp = __a;
6879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  __a = __b;
6889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  __b = __tmp;
6899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}
6909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
6919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// There is no really acceptable way to handle this.  The default
6929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// definition of swap doesn't work for proxy references.
6939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// It can't really be made to work, even with ugly hacks, since
6949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// the only unusual operation it uses is the copy constructor, which
6959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// is needed for other purposes.  We provide a macro for
6969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// full specializations, and instantiate the most common case.
6979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define _ROPE_SWAP_SPECIALIZATION(_CharT, __Alloc) \
6989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, \
6999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                     _Rope_char_ref_proxy <_CharT, __Alloc > __b) { \
7009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _CharT __tmp = __a; \
7019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __a = __b; \
7029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __b = __tmp; \
7039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
7049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
705e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_ROPE_SWAP_SPECIALIZATION(char, allocator<char>)
7069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef _STLP_NO_WCHAR_T
708e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_ROPE_SWAP_SPECIALIZATION(wchar_t, allocator<wchar_t>)
7099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
7109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* !_STLP_FUNCTION_TMPL_PARTIAL_ORDER */
7129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
7149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_char_ptr_proxy {
7159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // XXX this class should be rewritten.
7169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
7179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_ptr_proxy<_CharT, _Alloc> _Self;
7189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_char_ref_proxy<_CharT,_Alloc>;
7199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t _M_pos;
7209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope<_CharT,_Alloc>* _M_root;     // The whole rope.
7219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
7239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_pos(__x._M_pos), _M_root(__x._M_root) {}
7249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ptr_proxy(const _Self& __x)
7259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_pos(__x._M_pos), _M_root(__x._M_root) {}
7269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ptr_proxy() {}
7279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ptr_proxy(_CharT* __x) : _M_pos(0), _M_root(0) {
7289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(0 == __x)
7299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
7309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (const _Self& __x) {
7319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_pos = __x._M_pos;
7329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_root = __x._M_root;
7339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
7349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
7359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_char_ref_proxy<_CharT,_Alloc> operator*() const {
7379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Rope_char_ref_proxy<_CharT,_Alloc>(_M_root, _M_pos);
7389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
7399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
7409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
7439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Rope iterators:
7449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Unlike in the C version, we cache only part of the stack
7459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * for rope iterators, since they must be efficiently copyable.
7469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * When we run out of cache, we have to reconstruct the iterator
7479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * value.
7489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Pointers from iterators are not included in reference counts.
7499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Iterators are assumed to be thread private.  Ropes can
7509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * be shared.
7519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
7529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
7539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_iterator_base
7549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*   : public random_access_iterator<_CharT, ptrdiff_t>  */
7559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{
7569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class rope<_CharT,_Alloc>;
7579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_iterator_base<_CharT, _Alloc> _Self;
7589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcat;
7599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
7609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
7619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum { _S_path_cache_len = 4 }; // Must be <= 9 because of _M_path_direction.
7639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum { _S_iterator_buf_len = 15 };
7649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t _M_current_pos;
7659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The whole rope.
7669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _RopeRep* _M_root;
7679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Starting position for current leaf
7689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t _M_leaf_pos;
7699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Buffer possibly containing current char.
7709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT* _M_buf_start;
7719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Pointer to current char in buffer, != 0 ==> buffer valid.
7729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT* _M_buf_ptr;
7739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // One past __last valid char in buffer.
7749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT* _M_buf_end;
7759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
7769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // What follows is the path cache.  We go out of our
7779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // way to make this compact.
7789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Path_end contains the bottom section of the path from
7799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // the root to the current leaf.
7809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  struct {
7819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  if defined (__BORLANDC__) && (__BORLANDC__ < 0x560)
7829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep const*_M_data[4];
7839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  else
7849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep const*_M_data[_S_path_cache_len];
7859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  endif
7869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  } _M_path_end;
7879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Last valid __pos in path_end;
7889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // _M_path_end[0] ... _M_path_end[_M_leaf_index-1]
7899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // point to concatenation nodes.
7909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  int _M_leaf_index;
7919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // (_M_path_directions >> __i) & 1 is 1
7929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // if we got from _M_path_end[leaf_index - __i - 1]
7939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // to _M_path_end[leaf_index - __i] by going to the
7949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // __right. Assumes path_cache_len <= 9.
7959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  unsigned char _M_path_directions;
7969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Short buffer for surrounding chars.
7979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // This is useful primarily for
7989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // RopeFunctions.  We put the buffer
7999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // here to avoid locking in the
8009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // multithreaded case.
8019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The cached path is generally assumed to be valid
8029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // only if the buffer is valid.
8039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  struct {
8049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  if defined (__BORLANDC__) && (__BORLANDC__ < 0x560)
8059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _CharT _M_data[15];
8069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  else
8079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _CharT _M_data[_S_iterator_buf_len];
8089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  endif
8099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  } _M_tmp_buf;
8109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
8119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Set buffer contents given path cache.
8129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x);
8139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Set buffer contents and path cache.
8149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x);
8159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // As above, but assumes path cache is valid for previous posn.
8169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x);
8179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator_base() {}
8189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator_base(_RopeRep* __root, size_t __pos)
8199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_current_pos(__pos),_M_root(__root),  _M_buf_ptr(0) {}
8209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_incr(size_t __n);
8219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_decr(size_t __n);
8229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
8239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_t index() const { return _M_current_pos; }
8249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
8259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_copy_buf(const _Self& __x) {
8269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tmp_buf = __x._M_tmp_buf;
8279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__x._M_buf_start == __x._M_tmp_buf._M_data) {
8289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_start = _M_tmp_buf._M_data;
8299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_end = _M_buf_start + (__x._M_buf_end - __x._M_buf_start);
8309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_ptr = _M_buf_start + (__x._M_buf_ptr - __x._M_buf_start);
8319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
8329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_end = __x._M_buf_end;
8339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
8349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
8359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
8369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
8379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator_base(const _Self& __x) :
8389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_current_pos(__x._M_current_pos),
8399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_root(__x._M_root),
8409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_leaf_pos( __x._M_leaf_pos ),
8419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_start(__x._M_buf_start),
8429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buf_ptr(__x._M_buf_ptr),
8439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_path_end(__x._M_path_end),
8449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_leaf_index(__x._M_leaf_index),
8459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_path_directions(__x._M_path_directions)
8469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      {
8479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        if (0 != __x._M_buf_ptr) {
8489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          _M_copy_buf(__x);
8499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        }
8509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
8519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator = (const _Self& __x)
8529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      {
8539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_current_pos = __x._M_current_pos;
8549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_root = __x._M_root;
8559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_buf_start = __x._M_buf_start;
8569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_buf_ptr = __x._M_buf_ptr;
8579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_path_end = __x._M_path_end;
8589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_leaf_index = __x._M_leaf_index;
8599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_path_directions = __x._M_path_directions;
8609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_leaf_pos = __x._M_leaf_pos;
8619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        if (0 != __x._M_buf_ptr) {
8629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          _M_copy_buf(__x);
8639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        }
8649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        return *this;
8659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
8669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
8679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
8689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> class _Rope_iterator;
8699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
8709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
8719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_const_iterator : public _Rope_iterator_base<_CharT,_Alloc> {
8729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class rope<_CharT,_Alloc>;
8739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef  _Rope_const_iterator<_CharT, _Alloc> _Self;
8749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_iterator_base<_CharT,_Alloc> _Base;
8759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //  protected:
8769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
8779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   ifndef _STLP_HAS_NO_NAMESPACES
8789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
8799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The one from the base class may not be directly visible.
8809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#   endif
8819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_const_iterator(const _RopeRep* __root, size_t __pos):
8829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Rope_iterator_base<_CharT,_Alloc>(__CONST_CAST(_RopeRep*,__root), __pos)
8839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // Only nonconst iterators modify root ref count
8849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
8859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
8869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _CharT reference;   // Really a value.  Returning a reference
8879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                              // Would be a mess, since it would have
8889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                              // to be included in refcount.
8899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef const _CharT* pointer;
8909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _CharT value_type;
8919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef ptrdiff_t difference_type;
8929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef random_access_iterator_tag iterator_category;
8939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
8949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
8959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_const_iterator() {}
8969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_const_iterator(const _Self& __x) :
8979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Rope_iterator_base<_CharT,_Alloc>(__x) { }
8989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x):
8999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Rope_iterator_base<_CharT,_Alloc>(__x) {}
9009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_const_iterator(const rope<_CharT,_Alloc>& __r, size_t __pos) :
9019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos) {}
9029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (const _Self& __x) {
9039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Base::operator=(__x);
9049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
9059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference operator*() {
9079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == this->_M_buf_ptr)
908e67e5608677b105b6c1c5f2ff053f4532a72dd98Andrew Hsieh#if defined(__clang__) || (defined(__GNUC__) && (__GNUC__ > 4 || __GNUC_MINOR__ >= 7))
909e67e5608677b105b6c1c5f2ff053f4532a72dd98Andrew Hsieh      this->_S_setcache(*this);
910e67e5608677b105b6c1c5f2ff053f4532a72dd98Andrew Hsieh#elif !defined (__DMC__)
9119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_setcache(*this);
9129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
9139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    { _Rope_iterator_base<_CharT, _Alloc>* __x = this; _S_setcache(*__x); }
9149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
9159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *(this->_M_buf_ptr);
9169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
917e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  _Self& operator++()
918e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott      {
919e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott        if ( this->_M_buf_ptr != 0 ) {
920e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott          _CharT *__next = this->_M_buf_ptr + 1;
921e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott          if ( __next < this->_M_buf_end ) {
922e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott            this->_M_buf_ptr = __next;
923e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott            ++this->_M_current_pos;
924e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott            return *this;
925e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott          }
926e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott        }
927e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott        this->_M_incr(1);
928e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott        return *this;
929e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott      }
9309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator+=(ptrdiff_t __n) {
9319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__n >= 0) {
9329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_incr(__n);
9339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
9349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_decr(-__n);
9359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
9369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
9379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator--() {
9399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_decr(1);
9409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
9419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator-=(ptrdiff_t __n) {
9439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__n >= 0) {
9449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_decr(__n);
9459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
9469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_incr(-__n);
9479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
9489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
9499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self operator++(int) {
9519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __old_pos = this->_M_current_pos;
9529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_incr(1);
9539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
9549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // This makes a subsequent dereference expensive.
9559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // Perhaps we should instead copy the iterator
9569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // if it has a valid cache?
9579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self operator--(int) {
9599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __old_pos = this->_M_current_pos;
9609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_decr(1);
9619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
9629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  inline reference operator[](size_t __n);
9649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
9659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
9669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc>
9679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> {
9689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class rope<_CharT,_Alloc>;
9699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_iterator<_CharT, _Alloc> _Self;
9709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_iterator_base<_CharT,_Alloc> _Base;
9719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
9729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
9739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
9749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope<_CharT,_Alloc>* _M_root_rope;
9759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // root is treated as a cached version of this,
9769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // and is used to detect changes to the underlying
9779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // rope.
9789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Root is included in the reference count.
9799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // This is necessary so that we can detect changes reliably.
9809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Unfortunately, it requires careful bookkeeping for the
9819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // nonGC case.
9829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos);
9839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
9849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_check();
9859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
9869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_ref_proxy<_CharT,_Alloc>  reference;
9879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer;
9889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _CharT value_type;
9899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef ptrdiff_t difference_type;
9909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef random_access_iterator_tag iterator_category;
9919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
9929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~_Rope_iterator() {  //*TY 5/6/00 - added dtor to balance reference count
9939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_unref(this->_M_root);
9949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
9959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
9969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope<_CharT,_Alloc>& container() { return *_M_root_rope; }
9979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator() {
9989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_root = 0;  // Needed for reference counting.
9999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator(const  _Self& __x) :
10019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Rope_iterator_base<_CharT,_Alloc>(__x) {
10029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_root_rope = __x._M_root_rope;
10039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_ref(this->_M_root);
10049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos);
10069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (const  _Self& __x) {
10079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __old = this->_M_root;
10089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_ref(__x._M_root);
10099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Base::operator=(__x);
10109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_root_rope = __x._M_root_rope;
10119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_unref(__old);
10129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
10139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference operator*() {
10159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_check();
10169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == this->_M_buf_ptr) {
10179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return reference(_M_root_rope, this->_M_current_pos);
10189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
10199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return reference(_M_root_rope, this->_M_current_pos, *(this->_M_buf_ptr));
10209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
10219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator++() {
10239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_incr(1);
10249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
10259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator+=(ptrdiff_t __n) {
10279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__n >= 0) {
10289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_incr(__n);
10299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
10309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_decr(-__n);
10319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
10329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
10339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator--() {
10359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_decr(1);
10369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
10379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator-=(ptrdiff_t __n) {
10399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__n >= 0) {
10409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_decr(__n);
10419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
10429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      this->_M_incr(-__n);
10439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
10449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
10459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self operator++(int) {
10479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __old_pos = this->_M_current_pos;
10489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_incr(1);
10499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Self(_M_root_rope, __old_pos);
10509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self operator--(int) {
10529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __old_pos = this->_M_current_pos;
10539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    this->_M_decr(1);
10549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Self(_M_root_rope, __old_pos);
10559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference operator[](ptrdiff_t __n) {
10579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return reference(_M_root_rope, this->_M_current_pos + __n);
10589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
10599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
10609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
10619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
10629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline random_access_iterator_tag
10649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockiterator_category(const _Rope_iterator<_CharT,_Alloc>&) {  return random_access_iterator_tag();}
10659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _CharT* value_type(const _Rope_iterator<_CharT,_Alloc>&) { return 0; }
10679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline ptrdiff_t* distance_type(const _Rope_iterator<_CharT,_Alloc>&) { return 0; }
10699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline random_access_iterator_tag
10719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockiterator_category(const _Rope_const_iterator<_CharT,_Alloc>&) { return random_access_iterator_tag(); }
10729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _CharT* value_type(const _Rope_const_iterator<_CharT,_Alloc>&) { return 0; }
10749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline ptrdiff_t* distance_type(const _Rope_const_iterator<_CharT,_Alloc>&) { return 0; }
10769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_USE_OLD_HP_ITERATOR_QUERIES */
10779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
10789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc, class _CharConsumer>
10799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool _S_apply_to_pieces(_CharConsumer& __c,
10809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        _Rope_RopeRep<_CharT, _Alloc> *__r,
10819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        size_t __begin, size_t __end);
10829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        // begin and end are assumed to be in range.
10839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
10849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
10859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass rope
10869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
10879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block           : public __stlport_class<rope<_CharT, _Alloc> >
10889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
10899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{
10909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef rope<_CharT,_Alloc> _Self;
10919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
10929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _CharT value_type;
10939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef ptrdiff_t difference_type;
10949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef size_t size_type;
10959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _CharT const_reference;
10969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef const _CharT* const_pointer;
10979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_iterator<_CharT,_Alloc> iterator;
10989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_const_iterator<_CharT,_Alloc> const_iterator;
10999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_ref_proxy<_CharT,_Alloc> reference;
11009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_ptr_proxy<_CharT,_Alloc> pointer;
11019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_iterator<_CharT,_Alloc>;
11039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_const_iterator<_CharT,_Alloc>;
11049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend struct _Rope_RopeRep<_CharT,_Alloc>;
11059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_iterator_base<_CharT,_Alloc>;
11069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_char_ptr_proxy<_CharT,_Alloc>;
11079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend class _Rope_char_ref_proxy<_CharT,_Alloc>;
11089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend struct _Rope_RopeSubstring<_CharT,_Alloc>;
11099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
11119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected:
11139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _CharT* _Cstrptr;
11149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _CharT _S_empty_c_str[1];
11169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  enum { _S_copy_max = 23 };
11189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // For strings shorter than _S_copy_max, we copy to
11199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // concatenate.
11209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
11229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _RopeRep::_IsBasicCharType _IsBasicCharType;
11239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
11259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
1126e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef _Alloc allocator_type;
11279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
11299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The only data member of a rope:
11309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_PRIV _STLP_alloc_proxy<_RopeRep*, _CharT, allocator_type> _M_tree_ptr;
11319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
11339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  allocator_type get_allocator() const { return allocator_type(_M_tree_ptr); }
11349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
11369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
11379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
11389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
11399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_RopeSubstring<_CharT,_Alloc> _RopeSubstring;
11409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Retrieve a character at the indicated position.
11429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
11439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Obtain a pointer to the character at the indicated position.
11459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The pointer can be used to change the character.
11469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // If such a pointer cannot be produced, as is frequently the
11479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // case, 0 is returned instead.
11489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // (Returns nonzero only if all nodes in the path have a refcount
11499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // of 1.)
11509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
11519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_unref(_RopeRep* __t) {
11539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_unref(__t);
11549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
11559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_ref(_RopeRep* __t) {
11569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep::_S_ref(__t);
11579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
11589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;
11609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // _Result is counted in refcount.
11629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* _S_substring(_RopeRep* __base,
11639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                size_t __start, size_t __endp1);
11649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
11669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                       const _CharT* __iter, size_t __slen);
11679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Concatenate rope and char ptr, copying __s.
11689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Should really take an arbitrary iterator.
11699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Result is counted in refcount.
11709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
11719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                             const _CharT* __iter, size_t __slen);
11729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // As above, but one reference to __r is about to be
11739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // destroyed.  Thus the pieces may be recycled if all
11749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // relevent reference counts are 1.
11759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // General concatenation on _RopeRep.  _Result
11779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // has refcount of 1.  Adjusts argument refcounts.
11789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* _S_concat_rep(_RopeRep* __left, _RopeRep* __right);
11799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
11819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_MEMBER_TEMPLATES)
11829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _CharConsumer>
11839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
11849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Rope_char_consumer<_CharT> _CharConsumer;
11859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
11869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void apply_to_pieces(size_t __begin, size_t __end,
11879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                       _CharConsumer& __c) const
11889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __begin, __end); }
11899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected:
11919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _S_rounded_up_size(size_t __n)
11939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return _RopeRep::_S_rounded_up_size(__n); }
11949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
11959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Allocate and construct a RopeLeaf using the supplied allocator
11969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Takes ownership of s instead of copying.
11979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeLeaf* _S_new_RopeLeaf(_CharT *__s,
11989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                    size_t _p_size, allocator_type __a) {
11999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeLeaf* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
12009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                                _RopeLeaf).allocate(1);
12019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_TRY {
1202e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott      new(__space) _RopeLeaf(__s, _p_size, __a);
12039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
12049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   _STLP_UNWIND(_STLP_CREATE_ALLOCATOR(allocator_type,__a,
12059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                       _RopeLeaf).deallocate(__space, 1))
12069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __space;
12079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
12089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeConcatenation* _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
12109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                                      allocator_type __a) {
12119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   _RopeConcatenation* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
12129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                                        _RopeConcatenation).allocate(1);
1213e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    return new(__space) _RopeConcatenation(__left, __right, __a);
12149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
12159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeFunction* _S_new_RopeFunction(char_producer<_CharT>* __f,
12179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                            size_t _p_size, bool __d, allocator_type __a) {
12189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   _RopeFunction* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
12199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                                   _RopeFunction).allocate(1);
1220e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    return new(__space) _RopeFunction(__f, _p_size, __d, __a);
12219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
12229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeSubstring* _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
12249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                              size_t __l, allocator_type __a) {
12259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   _RopeSubstring* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
12269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                                    _RopeSubstring).allocate(1);
1227e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    return new(__space) _RopeSubstring(__b, __s, __l, __a);
12289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
12299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static
12319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
12329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                               size_t _p_size, allocator_type __a) {
12339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == _p_size) return 0;
12349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   _CharT* __buf = _STLP_CREATE_ALLOCATOR(allocator_type,__a, _CharT).allocate(_S_rounded_up_size(_p_size));
12369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_PRIV __ucopy_n(__s, _p_size, __buf);
12389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_construct_null(__buf + _p_size);
12399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_TRY {
12419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return _S_new_RopeLeaf(__buf, _p_size, __a);
12429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
12439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_UNWIND(_RopeRep::_S_free_string(__buf, _p_size, __a))
12449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_RET_AFTER_THROW(0)
12459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
12469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Concatenation of nonempty strings.
12499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Always builds a concatenation node.
12509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Rebalances if the result is too deep.
12519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Result has refcount 1.
12529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Does not increment left and right ref counts even though
12539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // they are referenced.
12549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep*
12559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
12569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Concatenation helper functions
12589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeLeaf*
12599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _S_leaf_concat_char_iter(_RopeLeaf* __r,
12609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                           const _CharT* __iter, size_t __slen);
12619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Concatenate by copying leaf.
12629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // should take an arbitrary iterator
12639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // result has refcount 1.
12649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeLeaf* _S_destr_leaf_concat_char_iter
12659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  (_RopeLeaf* __r, const _CharT* __iter, size_t __slen);
12669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // A version that potentially clobbers __r if __r->_M_ref_count == 1.
12679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // A helper function for exponentiating strings.
12709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // This uses a nonstandard refcount convention.
12719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The result has refcount 0.
12729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _Rope_Concat_fn<_CharT,_Alloc> _Concat_fn;
12739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (__GNUC__) || (__GNUC__ < 3)
12749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend _Concat_fn;
12759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
12769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  friend struct _STLP_PRIV _Rope_Concat_fn<_CharT,_Alloc>;
12779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
12789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
12809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _S_char_ptr_len(const _CharT* __s) {
12819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return char_traits<_CharT>::length(__s);
12829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
12839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: /* for operators */
12859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
12869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, __t) { }
12879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
12889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Copy __r to the _CharT buffer.
12899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Returns __buffer + __r->_M_size._M_data.
12909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Assumes that buffer is uninitialized.
12919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
12929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Again, with explicit starting position and length.
12949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Assumes that buffer is uninitialized.
12959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _CharT* _S_flatten(_RopeRep* __r,
12969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                            size_t __start, size_t __len,
12979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                            _CharT* __buffer);
12989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
12999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // fbp : HP aCC prohibits access to protected min_len from within static methods ( ?? )
13009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
13019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static const unsigned long _S_min_len[__ROPE_DEPTH_SIZE];
13029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected:
13039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static bool _S_is_balanced(_RopeRep* __r)
13049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return (__r->_M_size._M_data >= _S_min_len[__r->_M_depth]); }
13059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static bool _S_is_almost_balanced(_RopeRep* __r) {
13079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return (__r->_M_depth == 0 ||
13089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            __r->_M_size._M_data >= _S_min_len[__r->_M_depth - 1]);
13099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
13109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static bool _S_is_roughly_balanced(_RopeRep* __r) {
13129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return (__r->_M_depth <= 1 ||
13139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            __r->_M_size._M_data >= _S_min_len[__r->_M_depth - 2]);
13149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
13159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Assumes the result is not empty.
13179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* _S_concat_and_set_balanced(_RopeRep* __left,
13189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                              _RopeRep* __right) {
13199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __result = _S_concat_rep(__left, __right);
13209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (_S_is_balanced(__result)) __result->_M_is_balanced = true;
13219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __result;
13229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
13239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The basic rebalancing operation.  Logically copies the
13259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // rope.  The result has refcount of 1.  The client will
13269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // usually decrement the reference count of __r.
13279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The result is within height 2 of balanced by the above
13289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // definition.
13299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* _S_balance(_RopeRep* __r);
13309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Add all unbalanced subtrees to the forest of balanceed trees.
13329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Used only by balance.
13339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
13349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Add __r to forest, assuming __r is already balanced.
13369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
13379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifdef _STLP_DEBUG
13399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Print to stdout, exposing structure
13409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static void _S_dump(_RopeRep* __r, int __indent = 0);
13419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
13429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
13449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
13459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _STLP_FUNCTION_THROWS _M_throw_out_of_range() const;
13479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_reset(_RopeRep* __r) {
13499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    //if (__r != _M_tree_ptr._M_data) {
13509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_unref(_M_tree_ptr._M_data);
13519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_tree_ptr._M_data = __r;
13529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    //}
13539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
13549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
13569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool empty() const { return 0 == _M_tree_ptr._M_data; }
13579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Comparison member function.  This is public only for those
13599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // clients that need a ternary comparison.  Others
13609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // should use the comparison operators below.
13619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  int compare(const _Self& __y) const {
13629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _S_compare(_M_tree_ptr._M_data, __y._M_tree_ptr._M_data);
13639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
13649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const _CharT* __s, const allocator_type& __a = allocator_type())
13669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, _S_RopeLeaf_from_unowned_char_ptr(__s, _S_char_ptr_len(__s),__a))
13679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
13689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const _CharT* __s, size_t __len,
13709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       const allocator_type& __a = allocator_type())
13719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, (_S_RopeLeaf_from_unowned_char_ptr(__s, __len, __a)))
13729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
13739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Should perhaps be templatized with respect to the iterator type
13759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // and use Sequence_buffer.  (It should perhaps use sequence_buffer
13769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // even now.)
13779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const _CharT *__s, const _CharT *__e,
13789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       const allocator_type& __a = allocator_type())
13799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, _S_RopeLeaf_from_unowned_char_ptr(__s, __e - __s, __a))
13809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
13819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const const_iterator& __s, const const_iterator& __e,
13839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       const allocator_type& __a = allocator_type())
13849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, _S_substring(__s._M_root, __s._M_current_pos,
13859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                    __e._M_current_pos))
13869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
13879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const iterator& __s, const iterator& __e,
13899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       const allocator_type& __a = allocator_type())
13909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, _S_substring(__s._M_root, __s._M_current_pos,
13919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                    __e._M_current_pos))
13929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  {}
13939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(_CharT __c, const allocator_type& __a = allocator_type())
13959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, (_RopeRep*)0) {
13969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _CharT* __buf = _M_tree_ptr.allocate(_S_rounded_up_size(1));
13979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
13989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Copy_Construct(__buf, __c);
13999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_construct_null(__buf + 1);
14009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_TRY {
14029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_tree_ptr._M_data = _S_new_RopeLeaf(__buf, 1, __a);
14039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
14049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_UNWIND(_RopeRep::_S_free_string(__buf, 1, __a))
14059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
14069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(size_t __n, _CharT __c,
14089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       const allocator_type& __a = allocator_type()):
14099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr(__a, (_RopeRep*)0) {
14109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == __n)
14119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return;
14129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    rope<_CharT,_Alloc> __result;
14149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define  __exponentiate_threshold size_t(32)
14159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __remainder;
14169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    rope<_CharT,_Alloc> __remainder_rope;
14179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // gcc-2.7.2 bugs
14199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    typedef _STLP_PRIV _Rope_Concat_fn<_CharT,_Alloc> _Concat_fn;
14209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __exponent = __n / __exponentiate_threshold;
14229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __rest = __n % __exponentiate_threshold;
14239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == __rest) {
14249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      __remainder = 0;
14259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
14269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _CharT* __rest_buffer = _M_tree_ptr.allocate(_S_rounded_up_size(__rest));
14279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      uninitialized_fill_n(__rest_buffer, __rest, __c);
14289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_construct_null(__rest_buffer + __rest);
14299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _STLP_TRY {
14309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a);
14319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
14329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _STLP_UNWIND(_RopeRep::_S_free_string(__rest_buffer, __rest, __a))
14339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
14349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __remainder_rope._M_tree_ptr._M_data = __remainder;
14359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__exponent != 0) {
14369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _CharT* __base_buffer = _M_tree_ptr.allocate(_S_rounded_up_size(__exponentiate_threshold));
14379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _RopeLeaf* __base_leaf;
14389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      rope<_CharT,_Alloc> __base_rope;
14399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
14409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_construct_null(__base_buffer + __exponentiate_threshold);
14419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _STLP_TRY {
14429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __base_leaf = _S_new_RopeLeaf(__base_buffer,
14439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                      __exponentiate_threshold, __a);
14449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
14459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _STLP_UNWIND(_RopeRep::_S_free_string(__base_buffer,
14469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                            __exponentiate_threshold, __a))
14479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      __base_rope._M_tree_ptr._M_data = __base_leaf;
14489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      if (1 == __exponent) {
14499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __result = __base_rope;
14509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        // One each for base_rope and __result
14519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        //_STLP_ASSERT(2 == __result._M_tree_ptr._M_data->_M_ref_count)
14529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      } else {
14539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __result = _STLP_PRIV __power(__base_rope, __exponent, _Concat_fn());
14549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
14559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      if (0 != __remainder) {
14569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        __result += __remainder_rope;
14579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
14589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
14599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      __result = __remainder_rope;
14609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
14619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data = __result._M_tree_ptr._M_data;
14629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data->_M_ref_nonnil();
14639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __exponentiate_threshold
14649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
14659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const allocator_type& __a = allocator_type())
14679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, (_RopeRep*)0) {}
14689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Construct a rope from a function that can compute its members
14709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
14719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block       const allocator_type& __a = allocator_type())
14729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__a, (_RopeRep*)0) {
14739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data = (0 == __len) ?
14749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
14759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
14769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(const _Self& __x)
14789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__x._M_tree_ptr, __x._M_tree_ptr._M_data) {
14799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_ref(_M_tree_ptr._M_data);
14809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
14819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1482e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (_STLP_NO_MOVE_SEMANTIC)
14839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope(__move_source<_Self> __src)
14849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_tree_ptr(__src.get()._M_tree_ptr, __src.get()._M_tree_ptr._M_data) {
14859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __src.get()._M_tree_ptr._M_data = 0;
14869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1487e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif
14889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~rope() {
14909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_unref(_M_tree_ptr._M_data);
14919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
14929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
14939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator=(const _Self& __x) {
14949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(get_allocator() == __x.get_allocator())
14959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_ref(__x._M_tree_ptr._M_data);
14969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(__x._M_tree_ptr._M_data);
14979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
14989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
14999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void clear() {
15019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_unref(_M_tree_ptr._M_data);
15029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data = 0;
15039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void push_back(_CharT __x) {
15059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_destr_concat_char_iter(_M_tree_ptr._M_data, &__x, 1));
15069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void pop_back() {
15099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __old = _M_tree_ptr._M_data;
15109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data =
15119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_substring(_M_tree_ptr._M_data, 0, _M_tree_ptr._M_data->_M_size._M_data - 1);
15129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_unref(__old);
15139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT back() const {
15169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _S_fetch(_M_tree_ptr._M_data, _M_tree_ptr._M_data->_M_size._M_data - 1);
15179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void push_front(_CharT __x) {
15209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __old = _M_tree_ptr._M_data;
15219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __left =
15229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_RopeLeaf_from_unowned_char_ptr(&__x, 1, _M_tree_ptr);
15239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_TRY {
15249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_tree_ptr._M_data = _S_concat_rep(__left, _M_tree_ptr._M_data);
15259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_unref(__old);
15269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _S_unref(__left);
15279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
15289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_UNWIND(_S_unref(__left))
15299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void pop_front() {
15329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __old = _M_tree_ptr._M_data;
15339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data = _S_substring(_M_tree_ptr._M_data, 1, _M_tree_ptr._M_data->_M_size._M_data);
15349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_unref(__old);
15359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT front() const {
15389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _S_fetch(_M_tree_ptr._M_data, 0);
15399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void balance() {
15429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __old = _M_tree_ptr._M_data;
15439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data = _S_balance(_M_tree_ptr._M_data);
15449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_unref(__old);
15459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void copy(_CharT* __buffer) const {
15489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::_Destroy_Range(__buffer, __buffer + size());
15499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_flatten(_M_tree_ptr._M_data, __buffer);
15509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /*
15539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * This is the copy function from the standard, but
15549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * with the arguments reordered to make it consistent with the
15559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * rest of the interface.
15569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * Note that this guaranteed not to compile if the draft standard
15579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * order is assumed.
15589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   */
15599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type copy(size_type __pos, size_type __n, _CharT* __buffer) const {
15609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t _p_size = size();
15619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __len = (__pos + __n > _p_size? _p_size - __pos : __n);
15629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::_Destroy_Range(__buffer, __buffer + __len);
15649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_flatten(_M_tree_ptr._M_data, __pos, __len, __buffer);
15659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __len;
15669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef _STLP_DEBUG
15699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Print to stdout, exposing structure.  May be useful for
15709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // performance debugging.
15719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void dump() {
15729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _S_dump(_M_tree_ptr._M_data);
15739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
15759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Convert to 0 terminated string in new allocated memory.
15779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Embedded 0s in the input do not terminate the copy.
15789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const _CharT* c_str() const;
15799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // As above, but also use the flattened representation as the
15819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // the new rope representation.
15829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const _CharT* replace_with_c_str();
15839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Reclaim memory for the c_str generated flattened string.
15859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Intentionally undocumented, since it's hard to say when this
15869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // is safe for multiple threads.
15879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void delete_c_str () {
15889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == _M_tree_ptr._M_data) return;
15899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag &&
15909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        ((_RopeLeaf*)_M_tree_ptr._M_data)->_M_data ==
15919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _M_tree_ptr._M_data->_M_c_string) {
15929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      // Representation shared
15939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return;
15949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
15959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data->_M_free_c_string();
15969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr._M_data->_M_c_string = 0;
15979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
15989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
15999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT operator[] (size_type __pos) const {
16009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _S_fetch(_M_tree_ptr._M_data, __pos);
16019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _CharT at(size_type __pos) const {
16049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__pos >= size()) _M_throw_out_of_range();
16059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return (*this)[__pos];
16069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator begin() const {
16099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(const_iterator(_M_tree_ptr._M_data, 0));
16109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // An easy way to get a const iterator from a non-const container.
16139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator const_begin() const {
16149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(const_iterator(_M_tree_ptr._M_data, 0));
16159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator end() const {
16189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(const_iterator(_M_tree_ptr._M_data, size()));
16199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator const_end() const {
16229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(const_iterator(_M_tree_ptr._M_data, size()));
16239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type size() const {
16269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(0 == _M_tree_ptr._M_data? 0 : _M_tree_ptr._M_data->_M_size._M_data);
16279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type length() const {
16309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return size();
16319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type max_size() const {
16349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _S_min_len[__ROPE_MAX_DEPTH-1] - 1;
16359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    //  Guarantees that the result can be sufficiently
16369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    //  balanced.  Longer ropes will probably still work,
16379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    //  but it's harder to make guarantees.
16389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_reverse_iterator rbegin() const {
16419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return const_reverse_iterator(end());
16429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_reverse_iterator const_rbegin() const {
16459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return const_reverse_iterator(end());
16469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_reverse_iterator rend() const {
16499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return const_reverse_iterator(begin());
16509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_reverse_iterator const_rend() const {
16539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return const_reverse_iterator(begin());
16549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The symmetric cases are intentionally omitted, since they're presumed
16569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // to be less common, and we don't handle them as well.
16579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The following should really be templatized.
16599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // The first argument should be an input iterator or
16609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // forward iterator with value_type _CharT.
16619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(const _CharT* __iter, size_t __n) {
16629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_destr_concat_char_iter(_M_tree_ptr._M_data, __iter, __n));
16639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
16649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(const _CharT* __c_string) {
16679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __len = _S_char_ptr_len(__c_string);
16689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    append(__c_string, __len);
16699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
16709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(const _CharT* __s, const _CharT* __e) {
16739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_destr_concat_char_iter(_M_tree_ptr._M_data, __s, __e - __s));
16749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
16759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(const_iterator __s, const_iterator __e) {
16789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(__s._M_root == __e._M_root)
16799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(get_allocator() == __s._M_root->get_allocator())
16809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self_destruct_ptr __appendee(_S_substring(__s._M_root, __s._M_current_pos, __e._M_current_pos));
16819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_concat_rep(_M_tree_ptr._M_data, (_RopeRep*)__appendee));
16829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
16839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(_CharT __c) {
16869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_destr_concat_char_iter(_M_tree_ptr._M_data, &__c, 1));
16879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
16889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append() { return append(_CharT()); }  // XXX why?
16919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(const _Self& __y) {
16939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(__y.get_allocator() == get_allocator())
16949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_concat_rep(_M_tree_ptr._M_data, __y._M_tree_ptr._M_data));
16959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
16969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
16979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
16989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& append(size_t __n, _CharT __c) {
16999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    rope<_CharT,_Alloc> __last(__n, __c);
17009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return append(__last);
17019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void swap(_Self& __b) {
17049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_tree_ptr.swap(__b._M_tree_ptr);
17059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1706e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
1707e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  void _M_swap_workaround(_Self& __x) { swap(__x); }
1708e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif
17099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected:
17119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Result is included in refcount.
17129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static _RopeRep* replace(_RopeRep* __old, size_t __pos1,
17139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                           size_t __pos2, _RopeRep* __r) {
17149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == __old) { _S_ref(__r); return __r; }
17159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
17169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size._M_data));
17179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_MPWFIX_TRY  //*TY 06/01/2000 -
17189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _RopeRep* __result;
17199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (0 == __r) {
17219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      __result = _S_concat_rep(__left, __right);
17229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    } else {
17239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _STLP_ASSERT(__old->get_allocator() == __r->get_allocator())
17249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _Self_destruct_ptr __left_result(_S_concat_rep(__left, __r));
17259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      __result = _S_concat_rep(__left_result, __right);
17269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
17279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __result;
17289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_MPWFIX_CATCH  //*TY 06/01/2000 -
17299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
17329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, const _Self& __r) {
17339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__p > size()) _M_throw_out_of_range();
17349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_ASSERT(get_allocator() == __r.get_allocator())
17359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(replace(_M_tree_ptr._M_data, __p, __p, __r._M_tree_ptr._M_data));
17369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, size_t __n, _CharT __c) {
17399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    rope<_CharT,_Alloc> __r(__n,__c);
17409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, __r);
17419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, const _CharT* __i, size_t __n) {
17449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__p > size()) _M_throw_out_of_range();
17459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self_destruct_ptr __left(_S_substring(_M_tree_ptr._M_data, 0, __p));
17469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self_destruct_ptr __right(_S_substring(_M_tree_ptr._M_data, __p, size()));
17479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self_destruct_ptr __left_result(
17489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                     _S_concat_char_iter(__left, __i, __n));
17499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // _S_ destr_concat_char_iter should be safe here.
17509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // But as it stands it's probably not a win, since __left
17519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // is likely to have additional references.
17529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(_S_concat_rep(__left_result, __right));
17539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, const _CharT* __c_string) {
17569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, __c_string, _S_char_ptr_len(__c_string));
17579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, _CharT __c) {
17609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, &__c, 1);
17619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p) {
17649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _CharT __c = _CharT();
17659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, &__c, 1);
17669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, const _CharT* __i, const _CharT* __j) {
17699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __j);
17709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, __r);
17719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, const const_iterator& __i,
17749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                          const const_iterator& __j) {
17759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __j);
17769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, __r);
17779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert(size_t __p, const iterator& __i,
17809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                          const iterator& __j) {
17819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __j);
17829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    insert(__p, __r);
17839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // (position, length) versions of replace operations:
17869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n, const _Self& __r) {
17879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__p > size()) _M_throw_out_of_range();
17889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(replace(_M_tree_ptr._M_data, __p, __p + __n, __r._M_tree_ptr._M_data));
17899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n,
17929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const _CharT* __i, size_t __i_len) {
17939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __i_len);
17949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, __n, __r);
17959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
17969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
17979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n, _CharT __c) {
17989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__c);
17999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, __n, __r);
18009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n, const _CharT* __c_string) {
18039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__c_string);
18049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, __n, __r);
18059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n,
18089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const _CharT* __i, const _CharT* __j) {
18099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __j);
18109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, __n, __r);
18119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n,
18149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const const_iterator& __i, const const_iterator& __j) {
18159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __j);
18169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, __n, __r);
18179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, size_t __n,
18209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const iterator& __i, const iterator& __j) {
18219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __r(__i, __j);
18229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, __n, __r);
18239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Single character variants:
18269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, _CharT __c) {
18279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__p > size()) _M_throw_out_of_range();
18289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    iterator __i(this, __p);
18299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    *__i = __c;
18309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, const _Self& __r) {
18339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, 1, __r);
18349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, const _CharT* __i, size_t __i_len) {
18379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, 1, __i, __i_len);
18389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, const _CharT* __c_string) {
18419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, 1, __c_string);
18429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, const _CharT* __i, const _CharT* __j) {
18459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, 1, __i, __j);
18469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, const const_iterator& __i,
18499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                           const const_iterator& __j) {
18509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, 1, __i, __j);
18519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(size_t __p, const iterator& __i,
18549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                           const iterator& __j) {
18559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    replace(__p, 1, __i, __j);
18569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Erase, (position, size) variant.
18599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void erase(size_t __p, size_t __n) {
18609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__p > size()) _M_throw_out_of_range();
18619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_reset(replace(_M_tree_ptr._M_data, __p, __p + __n, 0));
18629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Erase, single character
18659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void erase(size_t __p) {
18669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    erase(__p, __p + 1);
18679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
18689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Insert, iterator variants.
18709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p, const _Self& __r)
18719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __r); return __p; }
18729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p, size_t __n, _CharT __c)
18739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __n, __c); return __p; }
18749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p, _CharT __c)
18759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __c); return __p; }
18769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p )
18779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index()); return __p; }
18789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p, const _CharT* c_string)
18799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), c_string); return __p; }
18809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p, const _CharT* __i, size_t __n)
18819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __i, __n); return __p; }
18829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p, const _CharT* __i,
18839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                  const _CharT* __j)
18849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __i, __j);  return __p; }
18859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p,
18869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                  const const_iterator& __i, const const_iterator& __j)
18879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __i, __j); return __p; }
18889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert(const iterator& __p,
18899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                  const iterator& __i, const iterator& __j)
18909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert(__p.index(), __i, __j); return __p; }
18919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
18929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Replace, range variants.
18939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q,
18949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const _Self& __r)
18959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __r); }
18969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q, _CharT __c)
18979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __c); }
18989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q,
18999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const _CharT* __c_string)
19009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __c_string); }
19019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q,
19029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const _CharT* __i, size_t __n)
19039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
19049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q,
19059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const _CharT* __i, const _CharT* __j)
19069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
19079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q,
19089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const const_iterator& __i, const const_iterator& __j)
19099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
19109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const iterator& __q,
19119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const iterator& __i, const iterator& __j)
19129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
19139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Replace, iterator variants.
19159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const _Self& __r)
19169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __r); }
19179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, _CharT __c)
19189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __c); }
19199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const _CharT* __c_string)
19209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __c_string); }
19219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const _CharT* __i, size_t __n)
19229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __i, __n); }
19239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
19249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __i, __j); }
19259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, const_iterator __i,
19269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block               const_iterator __j)
19279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __i, __j); }
19289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void replace(const iterator& __p, iterator __i, iterator __j)
19299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { replace(__p.index(), __i, __j); }
19309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Iterator and range variants of erase
19329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator erase(const iterator& __p, const iterator& __q) {
19339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __p_index = __p.index();
19349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    erase(__p_index, __q.index() - __p_index);
19359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return iterator(this, __p_index);
19369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator erase(const iterator& __p) {
19389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __p_index = __p.index();
19399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    erase(__p_index, 1);
19409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return iterator(this, __p_index);
19419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self substr(size_t __start, size_t __len = 1) const {
19449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__start > size()) _M_throw_out_of_range();
19459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return rope<_CharT,_Alloc>(_S_substring(_M_tree_ptr._M_data, __start, __start + __len));
19469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self substr(iterator __start, iterator __end) const {
19499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return rope<_CharT,_Alloc>(_S_substring(_M_tree_ptr._M_data, __start.index(), __end.index()));
19509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self substr(iterator __start) const {
19539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __pos = __start.index();
19549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return rope<_CharT,_Alloc>(_S_substring(_M_tree_ptr._M_data, __pos, __pos + 1));
19559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self substr(const_iterator __start, const_iterator __end) const {
19589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // This might eventually take advantage of the cache in the
19599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    // iterator.
19609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return rope<_CharT,_Alloc>(_S_substring(_M_tree_ptr._M_data, __start.index(), __end.index()));
19619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  rope<_CharT,_Alloc> substr(const_iterator __start) {
19649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_t __pos = __start.index();
19659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return rope<_CharT,_Alloc>(_S_substring(_M_tree_ptr._M_data, __pos, __pos + 1));
19669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#include <stl/_string_npos.h>
19699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type find(const _Self& __s, size_type __pos = 0) const {
19719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__pos >= size())
19729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef _STLP_OLD_ROPE_SEMANTICS
19739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return npos;
19749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# else
19759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return size();
19769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
19779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_type __result_pos;
1979e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    const_iterator __result = _STLP_STD::search(const_begin() + (ptrdiff_t)__pos, const_end(), __s.begin(), __s.end() );
19809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __result_pos = __result.index();
19819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef _STLP_OLD_ROPE_SEMANTICS
19829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__result_pos == size()) __result_pos = npos;
19839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
19849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __result_pos;
19859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type find(_CharT __c, size_type __pos = 0) const;
19879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type find(const _CharT* __s, size_type __pos = 0) const {
19889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_type __result_pos;
1989e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    const_iterator __result = _STLP_STD::search(const_begin() + (ptrdiff_t)__pos, const_end(),
1990e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott                                                __s, __s + _S_char_ptr_len(__s));
19919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    __result_pos = __result.index();
19929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef _STLP_OLD_ROPE_SEMANTICS
19939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__result_pos == size()) __result_pos = npos;
19949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
19959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __result_pos;
19969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
19979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
19989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator mutable_begin() {
19999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(iterator(this, 0));
20009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator mutable_end() {
20039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return(iterator(this, size()));
20049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reverse_iterator mutable_rbegin() {
20079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return reverse_iterator(mutable_end());
20089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reverse_iterator mutable_rend() {
20119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return reverse_iterator(mutable_begin());
20129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference mutable_reference_at(size_type __pos) {
20159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return reference(this, __pos);
20169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef __STD_STUFF
20199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference operator[] (size_type __pos) {
20209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return reference(this, __pos);
20219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference at(size_type __pos) {
20249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__pos >= size()) _M_throw_out_of_range();
20259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return (*this)[__pos];
20269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void resize(size_type, _CharT) {}
20299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void resize(size_type) {}
20309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void reserve(size_type = 0) {}
20319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type capacity() const {
20329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return max_size();
20339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // Stuff below this line is dangerous because it's error prone.
20369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // I would really like to get rid of it.
20379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // copy function with funny arg ordering.
20389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type copy(_CharT* __buffer, size_type __n,
20399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                 size_type __pos = 0) const {
20409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return copy(__pos, __n, __buffer);
20419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
20429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator end() { return mutable_end(); }
20449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator begin() { return mutable_begin(); }
20469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reverse_iterator rend() { return mutable_rend(); }
20489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reverse_iterator rbegin() { return mutable_rbegin(); }
20509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# else
20529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator end() { return const_end(); }
20549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator begin() { return const_begin(); }
20569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_reverse_iterator rend() { return const_rend(); }
20589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_reverse_iterator rbegin() { return const_rbegin(); }
20609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
20629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; //class rope
20639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2064e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (__GNUC__) && (__GNUC__ == 2) && (__GNUC_MINOR__ == 96)
20659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst size_t rope<_CharT, _Alloc>::npos = ~(size_t) 0;
20679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
20689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _CharT
20719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_const_iterator< _CharT, _Alloc>::operator[](size_t __n)
20729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return rope<_CharT,_Alloc>::_S_fetch(this->_M_root, this->_M_current_pos + __n); }
20739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator== (const _Rope_const_iterator<_CharT,_Alloc>& __x,
20769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_const_iterator<_CharT,_Alloc>& __y) {
20779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  return (__x._M_current_pos == __y._M_current_pos &&
20789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          __x._M_root == __y._M_root);
20799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}
20809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator< (const _Rope_const_iterator<_CharT,_Alloc>& __x,
20839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                       const _Rope_const_iterator<_CharT,_Alloc>& __y)
20849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (__x._M_current_pos < __y._M_current_pos); }
20859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
20879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator!= (const _Rope_const_iterator<_CharT,_Alloc>& __x,
20909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_const_iterator<_CharT,_Alloc>& __y)
20919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return !(__x == __y); }
20929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator> (const _Rope_const_iterator<_CharT,_Alloc>& __x,
20959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                       const _Rope_const_iterator<_CharT,_Alloc>& __y)
20969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return __y < __x; }
20979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
20989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
20999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator<= (const _Rope_const_iterator<_CharT,_Alloc>& __x,
21009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_const_iterator<_CharT,_Alloc>& __y)
21019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return !(__y < __x); }
21029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator>= (const _Rope_const_iterator<_CharT,_Alloc>& __x,
21059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_const_iterator<_CharT,_Alloc>& __y)
21069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return !(__x < __y); }
21079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
21099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline ptrdiff_t operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x,
21129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                           const _Rope_const_iterator<_CharT,_Alloc>& __y)
21139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
21149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined( __MWERKS__ ) || __MWERKS__ >= 0x2000  // dwa 8/21/97  - "ambiguous access to overloaded function" bug.
21169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Rope_const_iterator<_CharT,_Alloc>
21189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockoperator-(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n)
21199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return _Rope_const_iterator<_CharT,_Alloc>(__x._M_root, __x._M_current_pos - __n); }
21209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif
21219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Rope_const_iterator<_CharT,_Alloc>
21249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockoperator+(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n)
21259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return _Rope_const_iterator<_CharT,_Alloc>(__x._M_root, __x._M_current_pos + __n); }
21269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Rope_const_iterator<_CharT,_Alloc>
21299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockoperator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT,_Alloc>& __x)
21309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return _Rope_const_iterator<_CharT,_Alloc>(__x._M_root, __x._M_current_pos + __n); }
21319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator== (const _Rope_iterator<_CharT,_Alloc>& __x,
21349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_iterator<_CharT,_Alloc>& __y) {
21359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  return (__x._M_current_pos == __y._M_current_pos &&
21369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          __x._M_root_rope == __y._M_root_rope);
21379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}
21389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator< (const _Rope_iterator<_CharT,_Alloc>& __x,
21419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                       const _Rope_iterator<_CharT,_Alloc>& __y)
21429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (__x._M_current_pos < __y._M_current_pos); }
21439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_SEPARATE_RELOPS_NAMESPACE)
21459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator!= (const _Rope_iterator<_CharT,_Alloc>& __x,
21479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_iterator<_CharT,_Alloc>& __y)
21489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return !(__x == __y); }
21499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator> (const _Rope_iterator<_CharT,_Alloc>& __x,
21529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                       const _Rope_iterator<_CharT,_Alloc>& __y)
21539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return __y < __x; }
21549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator<= (const _Rope_iterator<_CharT,_Alloc>& __x,
21579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_iterator<_CharT,_Alloc>& __y)
21589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return !(__y < __x); }
21599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
21609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc>
21619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline bool operator>= (const _Rope_iterator<_CharT,_Alloc>& __x,
21629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                        const _Rope_iterator<_CharT,_Alloc>& __y)
21639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return !(__x < __y); }
21649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
21659720d5f59b9c1f5d1b9ecbc9173dbcb