/*

 * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). 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_BASE_H

#  include <stl/_function_base.h>

#endif

#ifndef _STLP_INTERNAL_NUMERIC_H

#  include <stl/_numeric.h>

#endif

#ifndef _STLP_INTERNAL_HASH_FUN_H

#  include <stl/_hash_fun.h>

#endif

#ifndef _STLP_CHAR_TRAITS_H

#  include <stl/char_traits.h>

#endif

#ifndef _STLP_INTERNAL_THREADS_H

#  include <stl/_threads.h>

#endif

#ifdef _STLP_SGI_THREADS

#  include <mutex.h>

#endif

#ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE

#  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;

_STLP_MOVE_TO_PRIV_NAMESPACE

// Some helpers, so we can use the power algorithm 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>(); }

_STLP_MOVE_TO_STD_NAMESPACE

// Store an eos

template <class _CharT>

inline void _S_construct_null_aux(_CharT *__p, const __true_type&)

{ *__p = 0; }

template <class _CharT>

inline void _S_construct_null_aux(_CharT *__p, const __false_type&)

{ _STLP_STD::_Construct(__p); }

template <class _CharT>

inline void _S_construct_null(_CharT *__p) {

  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;

  _S_construct_null_aux(__p, _Char_Is_Integral());

}

// char_producers are logically functions that generate a section of

// a string.  These can be converted 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(const 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(const 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 {

#if !defined (_STLP_MEMBER_TEMPLATES)

public:

  //Without member templates we have to use run-time parameterization.

  // The symmetry with char_producer is accidental and temporary.

  virtual ~_Rope_char_consumer() {}

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

#endif

};

//

// 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.

//

template<class _CharT, class _Alloc>

struct _Rope_RopeRep

  : public _Refcount_Base

{

  typedef _Rope_RopeRep<_CharT, _Alloc> _Self;

public:

  //

  // GAB: 11/09/05

  //

  // "__ROPE_DEPTH_SIZE" is set to one more then the "__ROPE_MAX_DEPTH".

  // This was originally just an addition of "__ROPE_MAX_DEPTH + 1"

  // but this addition causes the sunpro compiler to complain about

  // multiple declarations during the initialization of "_S_min_len".

  // Changed to be a fixed value and the sunpro compiler appears to

  // be happy???

  //

#  define __ROPE_MAX_DEPTH  45

#  define __ROPE_DEPTH_SIZE 46 // __ROPE_MAX_DEPTH + 1

  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;

  _CharT* _STLP_VOLATILE _M_c_string;

  _STLP_PRIV _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, unsigned char __d, bool __b, size_t _p_size,

                allocator_type __a) :

    _Refcount_Base(1),

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

  { }

  typedef typename _AreSameUnCVTypes<_CharT, char>::_Ret _IsChar;

# ifdef _STLP_HAS_WCHAR_T

  typedef typename _AreSameUnCVTypes<_CharT, wchar_t>::_Ret _IsWCharT;

# else

  typedef __false_type _IsWCharT;

# endif

  typedef typename _Lor2<_IsChar, _IsWCharT>::_Ret _IsBasicCharType;

#if 0

  /* Please tell why this code is necessary if you uncomment it.

   * Problem with it is that rope implementation expect that _S_rounded_up_size(n)

   * returns a size > n in order to store the terminating null charater. When

   * instanciation type is not a char or wchar_t this is not guaranty resulting in

   * memory overrun.

   */

  static size_t _S_rounded_up_size_aux(size_t __n, __true_type const& /*_IsBasicCharType*/) {

    // Allow slop for in-place expansion.

    return (__n + _S_alloc_granularity) & ~(_S_alloc_granularity - 1);

  }

  static size_t _S_rounded_up_size_aux(size_t __n, __false_type const& /*_IsBasicCharType*/) {

    // Allow slop for in-place expansion.

    return (__n + _S_alloc_granularity - 1) & ~(_S_alloc_granularity - 1);

  }

#endif

  // fbp : moved from RopeLeaf

  static size_t _S_rounded_up_size(size_t __n)

  //{ return _S_rounded_up_size_aux(__n, _IsBasicCharType()); }

  { return (__n + _S_alloc_granularity) & ~(_S_alloc_granularity - 1); }

  static void _S_free_string( _CharT* __s, size_t __len,

                             allocator_type __a) {

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

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

#   ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE

    __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.

  void _M_free_c_string();

  void _M_free_tree();

  // Deallocate t. Assumes t is not 0.

  void _M_unref_nonnil() {

    if (_M_decr() == 0) _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();

  //}

};

template<class _CharT, class _Alloc>

struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> {

public:

  _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.               */

private:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

  typedef typename _RopeRep::_IsBasicCharType _IsBasicCharType;

  void _M_init(__true_type const& /*_IsBasicCharType*/) {

    this->_M_c_string = _M_data;

  }

  void _M_init(__false_type const& /*_IsBasicCharType*/) {}

public:

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _RopeRep::allocator_type allocator_type;

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

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

      _M_data(__d) {

    _STLP_ASSERT(_p_size > 0)

    _M_init(_IsBasicCharType());

  }

# 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:

  ~_Rope_RopeLeaf() {

    if (_M_data != this->_M_c_string) {

      this->_M_free_c_string();

    }

    _RopeRep::_S_free_string(_M_data, this->_M_size._M_data, this->get_allocator());

  }

};

template<class _CharT, class _Alloc>

struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT, _Alloc> {

private:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

public:

  _RopeRep* _M_left;

  _RopeRep* _M_right;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _RopeRep::allocator_type allocator_type;

  _Rope_RopeConcatenation(_RopeRep* __l, _RopeRep* __r, allocator_type __a)

    : _Rope_RopeRep<_CharT,_Alloc>(_RopeRep::_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

  ~_Rope_RopeConcatenation() {

    this->_M_free_c_string();

    _M_left->_M_unref_nonnil();

    _M_right->_M_unref_nonnil();

  }

};

template <class _CharT, class _Alloc>

struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT, _Alloc> {

private:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

public:

  char_producer<_CharT>* _M_fn;

  /*

   * Char_producer is owned by the

   * rope and should be explicitly

   * deleted when the rope becomes

   * inaccessible.

   */

  bool _M_delete_when_done;

  _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>(_RopeRep::_S_function, 0, true, _p_size, __a), _M_fn(__f)

    , _M_delete_when_done(__d)

  { _STLP_ASSERT(_p_size > 0) }

  ~_Rope_RopeFunction() {

    this->_M_free_c_string();

    if (_M_delete_when_done) {

      delete _M_fn;

    }

  }

};

/*

 * 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>

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

public:

  // XXX this whole class should be rewritten.

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

  _RopeRep *_M_base;      // not 0

  size_t _M_start;

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

                                _CharT* __buffer) {

    typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;

    typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;

    switch (_M_base->_M_tag) {

    case _RopeRep::_S_function:

    case _RopeRep::_S_substringfn:

      {

        char_producer<_CharT>* __fn =

          __STATIC_CAST(_RopeFunction*, _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 _RopeRep::_S_leaf:

      {

        _CharT* __s =

          __STATIC_CAST(_RopeLeaf*, _M_base)->_M_data;

        _STLP_PRIV __ucopy_n(__s + __start_pos + _M_start, __req_len, __buffer);

      }

      break;

    default:

      _STLP_ASSERT(false)

        ;

    }

  }

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _RopeRep::allocator_type allocator_type;

  _Rope_RopeSubstring(_RopeRep* __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)

    _M_base->_M_ref_nonnil();

    this->_M_tag = _RopeRep::_S_substringfn;

  }

  virtual ~_Rope_RopeSubstring()

  { _M_base->_M_unref_nonnil(); }

};

/*

 * 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.)

 */

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; }

};

/*

 * 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>;

  typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;

  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) )

# ifndef _STLP_NO_WCHAR_T

_ROPE_SWAP_SPECIALIZATION(wchar_t,_STLP_DEFAULT_ALLOCATOR(wchar_t) )

# endif

#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;

  typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcat;

public:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

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

  enum { _S_iterator_buf_len = 15 };

  size_t _M_current_pos;

  // The whole rope.

  _RopeRep* _M_root;

  // Starting position for current leaf

  size_t _M_leaf_pos;

  // Buffer possibly containing current char.

  _CharT* _M_buf_start;

  // Pointer to current char in buffer, != 0 ==> buffer valid.

  _CharT* _M_buf_ptr;

  // One past __last valid char in buffer.

  _CharT* _M_buf_end;

  // 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.

  struct {

#  if defined (__BORLANDC__) && (__BORLANDC__ < 0x560)

    _RopeRep const*_M_data[4];

#  else

    _RopeRep const*_M_data[_S_path_cache_len];

#  endif

  } _M_path_end;

  // Last valid __pos in path_end;

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

  // point to concatenation nodes.

  int _M_leaf_index;

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

  // if 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.

  unsigned char _M_path_directions;

  // 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.

  struct {

#  if defined (__BORLANDC__) && (__BORLANDC__ < 0x560)

    _CharT _M_data[15];

#  else

    _CharT _M_data[_S_iterator_buf_len];

#  endif

  } _M_tmp_buf;

  // Set buffer contents given path cache.

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

  // Set buffer contents and path cache.

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

  // As above, but assumes path cache is valid for previous posn.

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

  _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; }

private:

  void _M_copy_buf(const _Self& __x) {

    _M_tmp_buf = __x._M_tmp_buf;

    if (__x._M_buf_start == __x._M_tmp_buf._M_data) {

      _M_buf_start = _M_tmp_buf._M_data;

      _M_buf_end = _M_buf_start + (__x._M_buf_end - __x._M_buf_start);

      _M_buf_ptr = _M_buf_start + (__x._M_buf_ptr - __x._M_buf_start);

    } else {

      _M_buf_end = __x._M_buf_end;

    }

  }

public:

  _Rope_iterator_base(const _Self& __x) : 

      _M_current_pos(__x._M_current_pos),

      _M_root(__x._M_root),

      _M_leaf_pos( __x._M_leaf_pos ),

      _M_buf_start(__x._M_buf_start),

      _M_buf_ptr(__x._M_buf_ptr),

      _M_path_end(__x._M_path_end),

      _M_leaf_index(__x._M_leaf_index),

      _M_path_directions(__x._M_path_directions)

      {

        if (0 != __x._M_buf_ptr) {

          _M_copy_buf(__x);

        }

      }

  _Self& operator = (const _Self& __x)

      {

        _M_current_pos = __x._M_current_pos;

        _M_root = __x._M_root;

        _M_buf_start = __x._M_buf_start;

        _M_buf_ptr = __x._M_buf_ptr;

        _M_path_end = __x._M_path_end;

        _M_leaf_index = __x._M_leaf_index;

        _M_path_directions = __x._M_path_directions;

        _M_leaf_pos = __x._M_leaf_pos;

        if (0 != __x._M_buf_ptr) {

          _M_copy_buf(__x);

        }

        return *this;

      }

};

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) {

    _Base::operator=(__x);

    return *this;

  }

  reference operator*() {

    if (0 == this->_M_buf_ptr)

#if !defined (__DMC__)

      _Rope_iterator_base<_CharT, _Alloc>::_S_setcache(*this);

#else

    { _Rope_iterator_base<_CharT, _Alloc>* __x = this; _S_setcache(*__x); }

#endif

    return *(this->_M_buf_ptr);

  }

  _Self& operator++() {

    _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>;

  typedef _Rope_iterator<_CharT, _Alloc> _Self;

  typedef _Rope_iterator_base<_CharT,_Alloc> _Base;

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

public:

  rope<_CharT,_Alloc>* _M_root_rope;

  // root is treated as a cached version of this,

  // and is used to detect changes to the underlying

  // rope.

  // Root is included in the reference count.

  // This is necessary so that we can detect changes reliably.

  // Unfortunately, it requires careful bookkeeping for the

  // nonGC case.

  _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos);

  void _M_check();

public:

  typedef _Rope_char_ref_proxy<_CharT,_Alloc>  reference;

  typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer;

  typedef _CharT value_type;

  typedef ptrdiff_t difference_type;

  typedef random_access_iterator_tag iterator_category;

public:

  ~_Rope_iterator() {  //*TY 5/6/00 - added dtor to balance reference count

    _RopeRep::_S_unref(this->_M_root);

  }

  rope<_CharT,_Alloc>& container() { return *_M_root_rope; }

  _Rope_iterator() {

    this->_M_root = 0;  // Needed for reference counting.

  }

  _Rope_iterator(const  _Self& __x) :

    _Rope_iterator_base<_CharT,_Alloc>(__x) {

    _M_root_rope = __x._M_root_rope;

    _RopeRep::_S_ref(this->_M_root);

  }

  _Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos);

  _Self& operator= (const  _Self& __x) {