/*

 * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1997

 * Moscow Center for SPARC Technology

 *

 * Copyright (c) 1999 

 * Boris Fomitchev

 *

 * This material is provided "as is", with absolutely no warranty expressed

 * or implied. Any use is at your own risk.

 *

 * Permission to use or copy this software for any purpose is hereby granted 

 * without fee, provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

/* NOTE: This is an internal header file, included by other STL headers.

 *   You should not attempt to use it directly.

 */

// rope<_CharT,_Alloc> is a sequence of _CharT.

// Ropes appear to be mutable, but update operations

// really copy enough of the data structure to leave the original

// valid.  Thus ropes can be logically copied by just copying

// a pointer value.

#ifndef _STLP_INTERNAL_ROPE_H

# define _STLP_INTERNAL_ROPE_H

# ifndef _STLP_INTERNAL_ALGOBASE_H

#  include <stl/_algobase.h>

# endif

# ifndef _STLP_IOSFWD

#  include <iosfwd>

# endif

# ifndef _STLP_INTERNAL_ALLOC_H

#  include <stl/_alloc.h>

# endif

# ifndef _STLP_INTERNAL_ITERATOR_H

#  include <stl/_iterator.h>

# endif

# ifndef _STLP_INTERNAL_ALGO_H

#  include <stl/_algo.h>

# endif

# ifndef _STLP_INTERNAL_FUNCTION_H

#  include <stl/_function.h>

# endif

# ifndef _STLP_INTERNAL_NUMERIC_H

#  include <stl/_numeric.h>

# endif

# ifndef _STLP_INTERNAL_HASH_FUN_H

#  include <stl/_hash_fun.h>

# endif

# ifdef __GC

#   define __GC_CONST const

# else

# include <stl/_threads.h>

#   define __GC_CONST   // constant except for deallocation

# endif

# ifdef _STLP_SGI_THREADS

#    include <mutex.h>

# endif

#ifdef _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM 

#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) (_Alloc_traits<_Tp,__atype>::create_allocator(__a)) 

#elif defined(__MRC__)||defined(__SC__) 

#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) __stl_alloc_create<_Tp,__atype>(__a,(_Tp*)0) 

#else 

#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) __stl_alloc_create(__a,(_Tp*)0) 

#endif 

_STLP_BEGIN_NAMESPACE

// First a lot of forward declarations.  The standard seems to require

// much stricter "declaration before use" than many of the implementations

// that preceded it.

template<class _CharT, _STLP_DEFAULT_ALLOCATOR_SELECT(_CharT) > class rope;

template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;

template<class _CharT, class _Alloc> struct _Rope_RopeRep;

template<class _CharT, class _Alloc> struct _Rope_RopeLeaf;

template<class _CharT, class _Alloc> struct _Rope_RopeFunction;

template<class _CharT, class _Alloc> struct _Rope_RopeSubstring;

template<class _CharT, class _Alloc> class _Rope_iterator;

template<class _CharT, class _Alloc> class _Rope_const_iterator;

template<class _CharT, class _Alloc> class _Rope_char_ref_proxy;

template<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;

// Some helpers, so we can use power on ropes.

// See below for why this isn't local to the implementation.

// This uses a nonstandard refcount convention.

// The result has refcount 0.

template<class _CharT, class _Alloc>

struct _Rope_Concat_fn

  : public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>,

  rope<_CharT,_Alloc> > {

  rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x,

                                  const rope<_CharT,_Alloc>& __y) {

    return __x + __y;

  }

};

template <class _CharT, class _Alloc>

inline

rope<_CharT,_Alloc>

__identity_element(_Rope_Concat_fn<_CharT, _Alloc>)

{

  return rope<_CharT,_Alloc>();

}

// The _S_eos function is used for those functions that

// convert to/from C-like strings to detect the end of the string.

// The end-of-C-string character.

// This is what the draft standard says it should be.

template <class _CharT>

inline _CharT _S_eos(_CharT*) { return _CharT(); }

// fbp : some compilers fail to zero-initialize builtins ;(

inline const char _S_eos(const char*) { return 0; }

# ifdef _STLP_HAS_WCHAR_T

inline const wchar_t _S_eos(const wchar_t*) { return 0; }

# endif

// Test for basic character types.

// For basic character types leaves having a trailing eos.

template <class _CharT>

inline bool _S_is_basic_char_type(_CharT*) { return false; }

template <class _CharT>

inline bool _S_is_one_byte_char_type(_CharT*) { return false; }

inline bool _S_is_basic_char_type(char*) { return true; }

inline bool _S_is_one_byte_char_type(char*) { return true; }

# ifdef _STLP_HAS_WCHAR_T

inline bool _S_is_basic_char_type(wchar_t*) { return true; }

# endif

// Store an eos iff _CharT is a basic character type.

// Do not reference _S_eos if it isn't.

template <class _CharT>

inline void _S_cond_store_eos(_CharT&) {}

inline void _S_cond_store_eos(char& __c) { __c = 0; }

# ifdef _STLP_HAS_WCHAR_T

inline void _S_cond_store_eos(wchar_t& __c) { __c = 0; }

# endif

// char_producers are logically functions that generate a section of

// a string.  These can be convereted to ropes.  The resulting rope

// invokes the char_producer on demand.  This allows, for example,

// files to be viewed as ropes without reading the entire file.

template <class _CharT>

class char_producer {

public:

  virtual ~char_producer() {};

  virtual void operator()(size_t __start_pos, size_t __len, 

                          _CharT* __buffer) = 0;

  // Buffer should really be an arbitrary output iterator.

  // That way we could flatten directly into an ostream, etc.

  // This is thoroughly impossible, since iterator types don't

  // have runtime descriptions.

};

// Sequence buffers:

//

// Sequence must provide an append operation that appends an

// array to the sequence.  Sequence buffers are useful only if

// appending an entire array is cheaper than appending element by element.

// This is true for many string representations.

// This should  perhaps inherit from ostream<sequence::value_type>

// and be implemented correspondingly, so that they can be used

// for formatted.  For the sake of portability, we don't do this yet.

//

// For now, sequence buffers behave as output iterators.  But they also

// behave a little like basic_ostringstream<sequence::value_type> and a

// little like containers.

template<class _Sequence

# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \

       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))

, size_t _Buf_sz = 100

#   if defined(__sgi) && !defined(__GNUC__)

#	 define __TYPEDEF_WORKAROUND

,class _V = typename _Sequence::value_type

#   endif /* __sgi */

# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */

>

// The 3rd parameter works around a common compiler bug.

class sequence_buffer : public iterator <output_iterator_tag, void, void, void, void> {

public:

#       ifndef __TYPEDEF_WORKAROUND

  typedef typename _Sequence::value_type value_type;

  typedef sequence_buffer<_Sequence

# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \

       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))

  , _Buf_sz

  > _Self;

# else /* _STLP_NON_TYPE_TMPL_PARAM_BUG */

  > _Self;

  enum { _Buf_sz = 100}; 

# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */

  // # endif

#	else /* __TYPEDEF_WORKAROUND */

  typedef _V value_type;

  typedef sequence_buffer<_Sequence, _Buf_sz, _V> _Self;

#	endif /* __TYPEDEF_WORKAROUND */

protected:

  _Sequence* _M_prefix;

  value_type _M_buffer[_Buf_sz];

  size_t     _M_buf_count;

public:

  void flush() {

    _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);

    _M_buf_count = 0;

  }

  ~sequence_buffer() { flush(); }

  sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}

  sequence_buffer(const _Self& __x) {

    _M_prefix = __x._M_prefix;

    _M_buf_count = __x._M_buf_count;

    copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);

  }

  sequence_buffer(_Self& __x) {

    __x.flush();

    _M_prefix = __x._M_prefix;

    _M_buf_count = 0;

  }

  sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}

  _Self& operator= (_Self& __x) {

    __x.flush();

    _M_prefix = __x._M_prefix;

    _M_buf_count = 0;

    return *this;

  }

  _Self& operator= (const _Self& __x) {

    _M_prefix = __x._M_prefix;

    _M_buf_count = __x._M_buf_count;

    copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);

    return *this;

  }

  void push_back(value_type __x)

  {

    if (_M_buf_count < _Buf_sz) {

      _M_buffer[_M_buf_count] = __x;

      ++_M_buf_count;

    } else {

      flush();

      _M_buffer[0] = __x;

      _M_buf_count = 1;

    }

  }

  void append(value_type* __s, size_t __len)

  {

    if (__len + _M_buf_count <= _Buf_sz) {

      size_t __i = _M_buf_count;

      size_t __j = 0;

      for (; __j < __len; __i++, __j++) {

        _M_buffer[__i] = __s[__j];

      }

      _M_buf_count += __len;

    } else if (0 == _M_buf_count) {

      _M_prefix->append(__s, __s + __len);

    } else {

      flush();

      append(__s, __len);

    }

  }

  _Self& write(value_type* __s, size_t __len)

  {

    append(__s, __len);

    return *this;

  }

  _Self& put(value_type __x)

  {

    push_back(__x);

    return *this;

  }

  _Self& operator=(const value_type& __rhs)

  {

    push_back(__rhs);

    return *this;

  }

  _Self& operator*() { return *this; }

  _Self& operator++() { return *this; }

  _Self& operator++(int) { return *this; }

};

// The following should be treated as private, at least for now.

template<class _CharT>

class _Rope_char_consumer {

public:

  // If we had member templates, these should not be virtual.

  // For now we need to use run-time parametrization where

  // compile-time would do.  _Hence this should all be private

  // for now.

  // The symmetry with char_producer is accidental and temporary.

  virtual ~_Rope_char_consumer() {};

  virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;

};

//

// What follows should really be local to rope.  Unfortunately,

// that doesn't work, since it makes it impossible to define generic

// equality on rope iterators.  According to the draft standard, the

// template parameters for such an equality operator cannot be inferred

// from the occurence of a member class as a parameter.

// (SGI compilers in fact allow this, but the __result wouldn't be

// portable.)

// Similarly, some of the static member functions are member functions

// only to avoid polluting the global namespace, and to circumvent

// restrictions on type inference for template functions.

//

//

// The internal data structure for representing a rope.  This is

// private to the implementation.  A rope is really just a pointer

// to one of these.

//

// A few basic functions for manipulating this data structure

// are members of _RopeRep.  Most of the more complex algorithms

// are implemented as rope members.

//

// Some of the static member functions of _RopeRep have identically

// named functions in rope that simply invoke the _RopeRep versions.

//

// A macro to introduce various allocation and deallocation functions

// These need to be defined differently depending on whether or not

// we are using standard conforming allocators, and whether the allocator

// instances have real state.  Thus this macro is invoked repeatedly

// with different definitions of __ROPE_DEFINE_ALLOC.

#if defined (_STLP_MEMBER_TEMPLATE_CLASSES)

# define __ROPE_DEFINE_ALLOC(_Tp, __name, _M_proxy) \

        typedef typename \

          _Alloc_traits<_Tp,_Alloc>::allocator_type __name##Allocator;

#define __ROPE_DEFINE_ALLOCS(__a, _M_proxy) \

        __ROPE_DEFINE_ALLOC(_CharT,_Data, _M_proxy) /* character data */ \

        typedef _Rope_RopeConcatenation<_CharT,__a> __C; \

        __ROPE_DEFINE_ALLOC(__C,_C, _M_proxy) \

        typedef _Rope_RopeLeaf<_CharT,__a> __L; \

        __ROPE_DEFINE_ALLOC(__L,_L, _M_proxy) \

        typedef _Rope_RopeFunction<_CharT,__a> __F; \

        __ROPE_DEFINE_ALLOC(__F,_F, _M_proxy) \

        typedef _Rope_RopeSubstring<_CharT,__a> __S; \

        __ROPE_DEFINE_ALLOC(__S,_S,_M_proxy)

#else

#define __ROPE_DEFINE_ALLOC(_Tp, __name, _M_proxy) 

#define __ROPE_DEFINE_ALLOCS(__a, _M_proxy)

#endif

template<class _CharT, class _Alloc>

struct _Rope_RopeRep

# ifndef __GC

  : public _Refcount_Base

# endif

{

  typedef _Rope_RopeRep<_CharT, _Alloc> _Self;

public:

#  define __ROPE_MAX_DEPTH  45

#  define __ROPE_DEPTH_SIZE 46

  enum { _S_max_rope_depth = __ROPE_MAX_DEPTH };

  enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};

  // Apparently needed by VC++

  // The data fields of leaves are allocated with some

  // extra space, to accomodate future growth and for basic

  // character types, to hold a trailing eos character.

  enum { _S_alloc_granularity = 8 };

  _Tag _M_tag:8;

  bool _M_is_balanced:8;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Alloc_traits<_CharT,_Alloc>::allocator_type

  allocator_type;

  allocator_type get_allocator() const { return allocator_type(_M_size);  }

  unsigned char _M_depth;

  __GC_CONST _CharT* _M_c_string;

  _STLP_alloc_proxy<size_t, _CharT, allocator_type> _M_size;

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeRep() : _Refcount_Base(1), _M_size(allocator_type(), 0) {}

# endif

  /* Flattened version of string, if needed.  */

  /* typically 0.                             */

  /* If it's not 0, then the memory is owned  */

  /* by this node.                            */

  /* In the case of a leaf, this may point to */

  /* the same memory as the data field.       */

  _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t _p_size,

                allocator_type __a) :

#         ifndef __GC

    _Refcount_Base(1),

#	  endif

    _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0), _M_size(__a, _p_size)

  { }

#   ifdef __GC

  void _M_incr () {}

#   endif

  // fbp : moved from RopeLeaf

  static size_t _S_rounded_up_size(size_t __n) {

    size_t __size_with_eos;

    if (_S_is_basic_char_type((_CharT*)0)) {

      __size_with_eos = __n + 1;

    } else {

      __size_with_eos = __n;

    }

#       ifdef __GC

    return __size_with_eos;

#       else

    // Allow slop for in-place expansion.

    return (__size_with_eos + _S_alloc_granularity-1)

      &~ (_S_alloc_granularity-1);

#       endif

  }

  static void _S_free_string(__GC_CONST _CharT* __s, size_t __len,

                             allocator_type __a) {

    if (!_S_is_basic_char_type((_CharT*)0)) {

      _STLP_STD::_Destroy(__s, __s + __len);

    }

    //  This has to be a static member, so this gets a bit messy

#   ifdef _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM

    __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

#   else

    __stl_alloc_rebind (__a, (_CharT*)0).deallocate(__s, _S_rounded_up_size(__len));

#   endif

  }

  // Deallocate data section of a leaf.

  // This shouldn't be a member function.

  // But its hard to do anything else at the

  // moment, because it's templatized w.r.t.

  // an allocator.

  // Does nothing if __GC is defined.

#   ifndef __GC

  void _M_free_c_string();

  void _M_free_tree();

  // Deallocate t. Assumes t is not 0.

  void _M_unref_nonnil()

  {

    _M_decr(); if (!_M_ref_count) _M_free_tree();

  }

  void _M_ref_nonnil()

  {

    _M_incr();

  }

  static void _S_unref(_Self* __t)

  {

    if (0 != __t) {

      __t->_M_unref_nonnil();

    }

  }

  static void _S_ref(_Self* __t)

  {

    if (0 != __t) __t->_M_incr();

  }

  static void _S_free_if_unref(_Self* __t)

  {

    if (0 != __t && 0 == __t->_M_ref_count) __t->_M_free_tree();

  }

#   else /* __GC */

  void _M_unref_nonnil() {}

  void _M_ref_nonnil() {}

  static void _S_unref(_Self*) {}

  static void _S_ref(_Self*) {}

  static void _S_free_if_unref(_Self*) {}

#   endif

  __ROPE_DEFINE_ALLOCS(_Alloc, _M_size)

    };

template<class _CharT, class _Alloc>

struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> {

public:

  __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */

                                /* The allocated size is         */

                                /* _S_rounded_up_size(size), except */

                                /* in the GC case, in which it   */

                                /* doesn't matter.               */

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Rope_RopeRep<_CharT,_Alloc>::allocator_type allocator_type;

  _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t _p_size, allocator_type __a)

    : _Rope_RopeRep<_CharT,_Alloc>(_Rope_RopeRep<_CharT,_Alloc>::_S_leaf, 0, true, _p_size, __a), 

    _M_data(__d)

  {

    _STLP_ASSERT(_p_size > 0)

    if (_S_is_basic_char_type((_CharT *)0)) {

      // already eos terminated.

      this->_M_c_string = __d;

    }

  }

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeLeaf() {}

  _Rope_RopeLeaf(const _Rope_RopeLeaf<_CharT, _Alloc>& ) {}

# endif

// The constructor assumes that d has been allocated with

  // the proper allocator and the properly padded size.

  // In contrast, the destructor deallocates the data:

# ifndef __GC

  ~_Rope_RopeLeaf() {

    if (_M_data != this->_M_c_string) {

      this->_M_free_c_string();

    }

    _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_M_data, this->_M_size._M_data, this->get_allocator());

  }

# endif

};

template<class _CharT, class _Alloc>

struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT,_Alloc> {

public:

  _Rope_RopeRep<_CharT,_Alloc>* _M_left;

  _Rope_RopeRep<_CharT,_Alloc>* _M_right;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Rope_RopeRep<_CharT,_Alloc>::allocator_type allocator_type;

  _Rope_RopeConcatenation(_Rope_RopeRep<_CharT,_Alloc>* __l,

                          _Rope_RopeRep<_CharT,_Alloc>* __r,

                          allocator_type __a)

    :   _Rope_RopeRep<_CharT,_Alloc>(

                                     _Rope_RopeRep<_CharT,_Alloc>::_S_concat, 

				     (max)(__l->_M_depth, __r->_M_depth) + 1, false,

                                     __l->_M_size._M_data + __r->_M_size._M_data, __a), _M_left(__l), _M_right(__r)

  {}

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeConcatenation() {}

  _Rope_RopeConcatenation(const _Rope_RopeConcatenation<_CharT, _Alloc>&) {}

# endif

# ifndef __GC

  ~_Rope_RopeConcatenation() {

    this->_M_free_c_string();

    _M_left->_M_unref_nonnil();

    _M_right->_M_unref_nonnil();

  }

# endif

};

template<class _CharT, class _Alloc>

struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT,_Alloc> {

public:

  char_producer<_CharT>* _M_fn;

#   ifndef __GC

  bool _M_delete_when_done; // Char_producer is owned by the

                                // rope and should be explicitly

                                // deleted when the rope becomes

                                // inaccessible.

#   else

  // In the GC case, we either register the rope for

  // finalization, or not.  Thus the field is unnecessary;

  // the information is stored in the collector data structures.

  // We do need a finalization procedure to be invoked by the

  // collector.

  static void _S_fn_finalization_proc(void * __tree, void *) {

    delete ((_Rope_RopeFunction *)__tree) -> _M_fn;

  }

#   endif

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Rope_RopeRep<_CharT,_Alloc>::allocator_type allocator_type;

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeFunction() {}

  _Rope_RopeFunction(const _Rope_RopeFunction<_CharT, _Alloc>& ) {}

# endif

  _Rope_RopeFunction(char_producer<_CharT>* __f, size_t _p_size,

                     bool __d, allocator_type __a)

    :

    _Rope_RopeRep<_CharT,_Alloc>(_Rope_RopeRep<_CharT,_Alloc>::_S_function, 0, true, _p_size, __a),

    _M_fn(__f)

#       ifndef __GC

    , _M_delete_when_done(__d)

#       endif

  {

    _STLP_ASSERT(_p_size > 0)

#       ifdef __GC

    if (__d) {

      GC_REGISTER_FINALIZER(

                            this, _Rope_RopeFunction::_S_fn_finalization_proc, 0, 0, 0);

    }

#       endif

  }

# ifndef __GC

  ~_Rope_RopeFunction() {

    this->_M_free_c_string();

    if (_M_delete_when_done) {

      delete _M_fn;

    }

  }

# endif

};

// Substring results are usually represented using just

// concatenation nodes.  But in the case of very long flat ropes

// or ropes with a functional representation that isn't practical.

// In that case, we represent the __result as a special case of

// RopeFunction, whose char_producer points back to the rope itself.

// In all cases except repeated substring operations and

// deallocation, we treat the __result as a RopeFunction.

template<class _CharT, class _Alloc>

# if  ( defined (__IBMCPP__) && (__IBMCPP__ == 500) )  // JFA 10-Aug-2000 for some reason xlC cares about the order

struct _Rope_RopeSubstring : public char_producer<_CharT> , public _Rope_RopeFunction<_CharT,_Alloc>

# else

struct _Rope_RopeSubstring : public _Rope_RopeFunction<_CharT,_Alloc>,

                             public char_producer<_CharT>

# endif

{

public:

  // XXX this whole class should be rewritten.

  typedef _Rope_RopeRep<_CharT,_Alloc> _Base;

  _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0

  size_t _M_start;

  virtual void operator()(size_t __start_pos, size_t __req_len,

                          _CharT* __buffer) {

    switch(_M_base->_M_tag) {

    case _Base::_S_function:

    case _Base::_S_substringfn:

      {

        char_producer<_CharT>* __fn =

          ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;

        _STLP_ASSERT(__start_pos + __req_len <= this->_M_size._M_data)

        _STLP_ASSERT(_M_start + this->_M_size._M_data <= _M_base->_M_size._M_data)

        (*__fn)(__start_pos + _M_start, __req_len, __buffer);

      }

      break;

    case _Base::_S_leaf:

      {

        __GC_CONST _CharT* __s =

          ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;

        uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,

                             __buffer);

      }

      break;

    default:

      _STLP_ASSERT(false)

        ;

    }

  }

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Rope_RopeRep<_CharT,_Alloc>::allocator_type allocator_type;

  _Rope_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,

                      size_t __l, allocator_type __a)

    : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a),

	_M_base(__b),

    _M_start(__s)

  {

    _STLP_ASSERT(__l > 0)

    _STLP_ASSERT(__s + __l <= __b->_M_size._M_data)

#       ifndef __GC

    _M_base->_M_ref_nonnil();

#       endif

    this->_M_tag = _Base::_S_substringfn;

  }

  virtual ~_Rope_RopeSubstring()

  { 

#       ifndef __GC

    _M_base->_M_unref_nonnil();

#       endif

  }

};

// Self-destructing pointers to Rope_rep.

// These are not conventional smart pointers.  Their

// only purpose in life is to ensure that unref is called

// on the pointer either at normal exit or if an exception

// is raised.  It is the caller's responsibility to

// adjust reference counts when these pointers are initialized

// or assigned to.  (This convention significantly reduces

// the number of potentially expensive reference count

// updates.)

#ifndef __GC

template<class _CharT, class _Alloc>

struct _Rope_self_destruct_ptr {

  _Rope_RopeRep<_CharT,_Alloc>* _M_ptr;

  ~_Rope_self_destruct_ptr() 

  { _Rope_RopeRep<_CharT,_Alloc>::_S_unref(_M_ptr); }

#   ifdef _STLP_USE_EXCEPTIONS

  _Rope_self_destruct_ptr() : _M_ptr(0) {};

#   else

  _Rope_self_destruct_ptr() {};

#   endif

  _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT,_Alloc>* __p) : _M_ptr(__p) {}

  _Rope_RopeRep<_CharT,_Alloc>& operator*() { return *_M_ptr; }

  _Rope_RopeRep<_CharT,_Alloc>* operator->() { return _M_ptr; }

  operator _Rope_RopeRep<_CharT,_Alloc>*() { return _M_ptr; }

  _Rope_self_destruct_ptr<_CharT, _Alloc>& 

  operator= (_Rope_RopeRep<_CharT,_Alloc>* __x)

  { _M_ptr = __x; return *this; }

};

#endif

// Dereferencing a nonconst iterator has to return something

// that behaves almost like a reference.  It's not possible to

// return an actual reference since assignment requires extra

// work.  And we would get into the same problems as with the

// CD2 version of basic_string.

template<class _CharT, class _Alloc>

class _Rope_char_ref_proxy {

  typedef _Rope_char_ref_proxy<_CharT, _Alloc> _Self;

  friend class rope<_CharT,_Alloc>;

  friend class _Rope_iterator<_CharT,_Alloc>;

  friend class _Rope_char_ptr_proxy<_CharT,_Alloc>;

#   ifdef __GC

  typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr;

#   else

  typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;

#   endif

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

  typedef rope<_CharT,_Alloc> _My_rope;

  size_t _M_pos;

  _CharT _M_current;

  bool _M_current_valid;

  _My_rope* _M_root;     // The whole rope.

public:

  _Rope_char_ref_proxy(_My_rope* __r, size_t __p) :

    _M_pos(__p), _M_current_valid(false), _M_root(__r) {}

  _Rope_char_ref_proxy(const _Self& __x) :

    _M_pos(__x._M_pos), _M_current_valid(false), _M_root(__x._M_root) {}

  // Don't preserve cache if the reference can outlive the

  // expression.  We claim that's not possible without calling

  // a copy constructor or generating reference to a proxy

  // reference.  We declare the latter to have undefined semantics.

  _Rope_char_ref_proxy(_My_rope* __r, size_t __p,

                       _CharT __c) :

    _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {}

  inline operator _CharT () const;

  _Self& operator= (_CharT __c);

  _Rope_char_ptr_proxy<_CharT, _Alloc> operator& () const;

  _Self& operator= (const _Self& __c) {

    return operator=((_CharT)__c); 

  }

};

#ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER

template<class _CharT, class __Alloc>

inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,

                 _Rope_char_ref_proxy <_CharT, __Alloc > __b) {

  _CharT __tmp = __a;

  __a = __b;

  __b = __tmp;

}

#else

// There is no really acceptable way to handle this.  The default

// definition of swap doesn't work for proxy references.

// It can't really be made to work, even with ugly hacks, since

// the only unusual operation it uses is the copy constructor, which

// is needed for other purposes.  We provide a macro for

// full specializations, and instantiate the most common case.

# define _ROPE_SWAP_SPECIALIZATION(_CharT, __Alloc) \

    inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, \

                     _Rope_char_ref_proxy <_CharT, __Alloc > __b) { \

        _CharT __tmp = __a; \

        __a = __b; \

        __b = __tmp; \

    }

_ROPE_SWAP_SPECIALIZATION(char,_STLP_DEFAULT_ALLOCATOR(char) )

#endif /* !_STLP_FUNCTION_TMPL_PARTIAL_ORDER */

  template<class _CharT, class _Alloc>

class _Rope_char_ptr_proxy {

  // XXX this class should be rewritten.

public:

  typedef _Rope_char_ptr_proxy<_CharT, _Alloc> _Self;

  friend class _Rope_char_ref_proxy<_CharT,_Alloc>;

  size_t _M_pos;

  rope<_CharT,_Alloc>* _M_root;     // The whole rope.

  _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) 

    : _M_pos(__x._M_pos), _M_root(__x._M_root) {}

  _Rope_char_ptr_proxy(const _Self& __x)

    : _M_pos(__x._M_pos), _M_root(__x._M_root) {}

  _Rope_char_ptr_proxy() {}

  _Rope_char_ptr_proxy(_CharT* __x) : _M_pos(0), _M_root(0) {

    _STLP_ASSERT(0 == __x)

  }

  _Self& 

  operator= (const _Self& __x) {

    _M_pos = __x._M_pos;

    _M_root = __x._M_root;

    return *this;

  }

  _Rope_char_ref_proxy<_CharT,_Alloc> operator*() const {

    return _Rope_char_ref_proxy<_CharT,_Alloc>(_M_root, _M_pos);

  }

};

// Rope iterators:

// Unlike in the C version, we cache only part of the stack

// for rope iterators, since they must be efficiently copyable.

// When we run out of cache, we have to reconstruct the iterator

// value.

// Pointers from iterators are not included in reference counts.

// Iterators are assumed to be thread private.  Ropes can

// be shared.

template<class _CharT, class _Alloc>

class _Rope_iterator_base

/*   : public random_access_iterator<_CharT, ptrdiff_t>  */

{

  friend class rope<_CharT,_Alloc>;

  typedef _Rope_iterator_base<_CharT, _Alloc> _Self;

public:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

  // Borland doesnt want this to be protected.

  //  protected:

  enum { _S_path_cache_len = 4 }; // Must be <= 9.

  enum { _S_iterator_buf_len = 15 };

  size_t _M_current_pos;

  _RopeRep* _M_root;     // The whole rope.

  size_t _M_leaf_pos;    // Starting position for current leaf

  __GC_CONST _CharT* _M_buf_start;

  // Buffer possibly

  // containing current char.

  __GC_CONST _CharT* _M_buf_ptr;

  // Pointer to current char in buffer.

  // != 0 ==> buffer valid.

  __GC_CONST _CharT* _M_buf_end;

  // One past __last valid char in buffer.

  // What follows is the path cache.  We go out of our

  // way to make this compact.

  // Path_end contains the bottom section of the path from

  // the root to the current leaf.

  const _RopeRep* _M_path_end[_S_path_cache_len];

  int _M_leaf_index;     // Last valid __pos in path_end;

  // _M_path_end[0] ... _M_path_end[leaf_index-1]

  // point to concatenation nodes.

  unsigned char _M_path_directions;

  // (path_directions >> __i) & 1 is 1

  // iff we got from _M_path_end[leaf_index - __i - 1]

  // to _M_path_end[leaf_index - __i] by going to the

  // __right. Assumes path_cache_len <= 9.

  _CharT _M_tmp_buf[_S_iterator_buf_len];

  // Short buffer for surrounding chars.

  // This is useful primarily for 

  // RopeFunctions.  We put the buffer

  // here to avoid locking in the

  // multithreaded case.

  // The cached path is generally assumed to be valid

  // only if the buffer is valid.

  static void _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x);

  // Set buffer contents given

  // path cache.

  static void _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x);

  // Set buffer contents and

  // path cache.

  static void _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x);

  // As above, but assumes path

  // cache is valid for previous posn.

  _Rope_iterator_base() {}

  _Rope_iterator_base(_RopeRep* __root, size_t __pos)

    : _M_current_pos(__pos),_M_root(__root),  _M_buf_ptr(0) {}

  void _M_incr(size_t __n);

  void _M_decr(size_t __n);

public:

  size_t index() const { return _M_current_pos; }

  _Rope_iterator_base(const _Self& __x) {

    if (0 != __x._M_buf_ptr) {

      *this = __x;

    } else {

      _M_current_pos = __x._M_current_pos;

      _M_root = __x._M_root;

      _M_buf_ptr = 0;

    }

  }

};

template<class _CharT, class _Alloc> class _Rope_iterator;

template<class _CharT, class _Alloc>

class _Rope_const_iterator : public _Rope_iterator_base<_CharT,_Alloc> {

  friend class rope<_CharT,_Alloc>;

  typedef  _Rope_const_iterator<_CharT, _Alloc> _Self;

  typedef _Rope_iterator_base<_CharT,_Alloc> _Base;

  //  protected:

public:

#   ifndef _STLP_HAS_NO_NAMESPACES

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

  // The one from the base class may not be directly visible.

#   endif

  _Rope_const_iterator(const _RopeRep* __root, size_t __pos):

    _Rope_iterator_base<_CharT,_Alloc>(

                                       __CONST_CAST(_RopeRep*,__root), __pos)

    // Only nonconst iterators modify root ref count

  {}

public:

  typedef _CharT reference;   // Really a value.  Returning a reference

                                // Would be a mess, since it would have

                                // to be included in refcount.

  typedef const _CharT* pointer;

  typedef _CharT value_type;

  typedef ptrdiff_t difference_type;

  typedef random_access_iterator_tag iterator_category;

public:

  _Rope_const_iterator() {};

  _Rope_const_iterator(const _Self& __x) :

    _Rope_iterator_base<_CharT,_Alloc>(__x) { }

  _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x): 

    _Rope_iterator_base<_CharT,_Alloc>(__x) {}

  _Rope_const_iterator(const rope<_CharT,_Alloc>& __r, size_t __pos) :

    _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos) {}

  _Self& operator= (const _Self& __x) {

    if (0 != __x._M_buf_ptr) {

      *(__STATIC_CAST(_Base*,this)) = __x;

    } else {

      this->_M_current_pos = __x._M_current_pos;

      this->_M_root = __x._M_root;

      this->_M_buf_ptr = 0;

    }

    return(*this);

  }

  reference operator*() {

    if (0 == this->_M_buf_ptr) _S_setcache(*this);

    return *(this->_M_buf_ptr);

  }

  _Self& operator++() {

    __GC_CONST _CharT* __next;

    if (0 != this->_M_buf_ptr && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end) {

      this->_M_buf_ptr = __next;

      ++this->_M_current_pos;

    } else {

      this->_M_incr(1);

    }

    return *this;

  }

  _Self& operator+=(ptrdiff_t __n) {

    if (__n >= 0) {

      this->_M_incr(__n);

    } else {

      this->_M_decr(-__n);

    }

    return *this;

  }

  _Self& operator--() {

    this->_M_decr(1);

    return *this;

  }

  _Self& operator-=(ptrdiff_t __n) {

    if (__n >= 0) {

      this->_M_decr(__n);

    } else {

      this->_M_incr(-__n);

    }

    return *this;

  }

  _Self operator++(int) {

    size_t __old_pos = this->_M_current_pos;

    this->_M_incr(1);

    return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);

    // This makes a subsequent dereference expensive.

    // Perhaps we should instead copy the iterator

    // if it has a valid cache?

  }

  _Self operator--(int) {

    size_t __old_pos = this->_M_current_pos;

    this->_M_decr(1);

    return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);

  }

  inline reference operator[](size_t __n);

};

template<class _CharT, class _Alloc>

class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> {

  friend class rope<_CharT,_Alloc>;