_CharT* __new_data = (_CharT*)
	_Data_allocate(_S_rounded_up_size(__old_len + __len));
    _RopeLeaf* __result;
    
    uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
    uninitialized_copy_n(__iter, __len, __new_data + __old_len);
    _S_cond_store_eos(__new_data[__old_len + __len]);
    __STL_TRY {
	__result = _S_new_RopeLeaf(__new_data, __old_len + __len,
				   __r->get_allocator());
    }
    __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
					     __r->get_allocator()));
    return __result;
}

#ifndef __GC
// As above, but it's OK to clobber original if refcount is 1
template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeLeaf*
rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter
		(_RopeLeaf* __r, const _CharT* __iter, size_t __len)
{
    __stl_assert(__r->_M_ref_count >= 1);
    if (__r->_M_ref_count > 1)
      return _S_leaf_concat_char_iter(__r, __iter, __len);
    size_t __old_len = __r->_M_size;
    if (_S_allocated_capacity(__old_len) >= __old_len + __len) {
	// The space has been partially initialized for the standard
	// character types.  But that doesn't matter for those types.
	uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
	if (_S_is_basic_char_type((_CharT*)0)) {
	    _S_cond_store_eos(__r->_M_data[__old_len + __len]);
	    __stl_assert(__r->_M_c_string == __r->_M_data);
	} else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
	    __r->_M_free_c_string();
	    __r->_M_c_string = 0;
	}
	__r->_M_size = __old_len + __len;
	__stl_assert(__r->_M_ref_count == 1);
	__r->_M_ref_count = 2;
	return __r;
    } else {
	_RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
	__stl_assert(__result->_M_ref_count == 1);
	return __result;
    }
}
#endif

// Assumes left and right are not 0.
// Does not increment (nor decrement on exception) child reference counts.
// Result has ref count 1.
template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeRep*
rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right)
{
    _RopeConcatenation* __result =
      _S_new_RopeConcatenation(__left, __right, __left->get_allocator());
    size_t __depth = __result->_M_depth;
    
#   ifdef __STL_USE_STD_ALLOCATORS
      __stl_assert(__left->get_allocator() == __right->get_allocator());
#   endif
    if (__depth > 20 && (__result->_M_size < 1000 ||
			 __depth > _RopeRep::_S_max_rope_depth)) {
        _RopeRep* __balanced;
      
	__STL_TRY {
	   __balanced = _S_balance(__result);
#          ifndef __GC
	     if (__result != __balanced) {
		__stl_assert(1 == __result->_M_ref_count
			     && 1 == __balanced->_M_ref_count);
	     }
#          endif
	   __result->_M_unref_nonnil();
        }
	__STL_UNWIND((_C_deallocate(__result,1)));
		// In case of exception, we need to deallocate
		// otherwise dangling result node.  But caller
		// still owns its children.  Thus unref is
		// inappropriate.
	return __balanced;
    } else {
	return __result;
    }
}

template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter
		(_RopeRep* __r, const _CharT*__s, size_t __slen)
{
    _RopeRep* __result;
    if (0 == __slen) {
	_S_ref(__r);
	return __r;
    }
    if (0 == __r)
      return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
					      __r->get_allocator());
    if (_RopeRep::_S_leaf == __r->_M_tag && 
          __r->_M_size + __slen <= _S_copy_max) {
	__result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
#       ifndef __GC
	  __stl_assert(1 == __result->_M_ref_count);
#       endif
	return __result;
    }
    if (_RopeRep::_S_concat == __r->_M_tag
	&& _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
	_RopeLeaf* __right = 
	  (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
	if (__right->_M_size + __slen <= _S_copy_max) {
	  _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
	  _RopeRep* __nright = 
	    _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
	  __left->_M_ref_nonnil();
	  __STL_TRY {
	    __result = _S_tree_concat(__left, __nright);
          }
	  __STL_UNWIND(_S_unref(__left); _S_unref(__nright));
#         ifndef __GC
	    __stl_assert(1 == __result->_M_ref_count);
#         endif
	  return __result;
	}
    }
    _RopeRep* __nright =
      __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
    __STL_TRY {
      __r->_M_ref_nonnil();
      __result = _S_tree_concat(__r, __nright);
    }
    __STL_UNWIND(_S_unref(__r); _S_unref(__nright));
#   ifndef __GC
      __stl_assert(1 == __result->_M_ref_count);
#   endif
    return __result;
}

#ifndef __GC
template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeRep* 
rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
  _RopeRep* __r, const _CharT* __s, size_t __slen)
{
    _RopeRep* __result;
    if (0 == __r)
      return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
					      __r->get_allocator());
    size_t __count = __r->_M_ref_count;
    size_t __orig_size = __r->_M_size;
    __stl_assert(__count >= 1);
    if (__count > 1) return _S_concat_char_iter(__r, __s, __slen);
    if (0 == __slen) {
	__r->_M_ref_count = 2;      // One more than before
	return __r;
    }
    if (__orig_size + __slen <= _S_copy_max && 
          _RopeRep::_S_leaf == __r->_M_tag) {
	__result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
	return __result;
    }
    if (_RopeRep::_S_concat == __r->_M_tag) {
	_RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right);
	if (_RopeRep::_S_leaf == __right->_M_tag
	    && __right->_M_size + __slen <= _S_copy_max) {
	  _RopeRep* __new_right = 
	    _S_destr_leaf_concat_char_iter(__right, __s, __slen);
	  if (__right == __new_right) {
	      __stl_assert(__new_right->_M_ref_count == 2);
	      __new_right->_M_ref_count = 1;
	  } else {
	      __stl_assert(__new_right->_M_ref_count >= 1);
	      __right->_M_unref_nonnil();
	  }
	  __stl_assert(__r->_M_ref_count == 1);
	  __r->_M_ref_count = 2;    // One more than before.
	  ((_RopeConcatenation*)__r)->_M_right = __new_right;
	  __r->_M_size = __orig_size + __slen;
	  if (0 != __r->_M_c_string) {
	      __r->_M_free_c_string();
	      __r->_M_c_string = 0;
	  }
	  return __r;
	}
    }
    _RopeRep* __right =
      __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
    __r->_M_ref_nonnil();
    __STL_TRY {
      __result = _S_tree_concat(__r, __right);
    }
    __STL_UNWIND(_S_unref(__r); _S_unref(__right))
    __stl_assert(1 == __result->_M_ref_count);
    return __result;
}
#endif /* !__GC */

template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeRep*
rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right)
{
    if (0 == __left) {
	_S_ref(__right);
	return __right;
    }
    if (0 == __right) {
	__left->_M_ref_nonnil();
	return __left;
    }
    if (_RopeRep::_S_leaf == __right->_M_tag) {
	if (_RopeRep::_S_leaf == __left->_M_tag) {
	  if (__right->_M_size + __left->_M_size <= _S_copy_max) {
	    return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
					 ((_RopeLeaf*)__right)->_M_data,
					 __right->_M_size);
	  }
	} else if (_RopeRep::_S_concat == __left->_M_tag
		   && _RopeRep::_S_leaf ==
		      ((_RopeConcatenation*)__left)->_M_right->_M_tag) {
	  _RopeLeaf* __leftright =
		    (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 
	  if (__leftright->_M_size + __right->_M_size <= _S_copy_max) {
	    _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
	    _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
					   ((_RopeLeaf*)__right)->_M_data,
					   __right->_M_size);
	    __leftleft->_M_ref_nonnil();
	    __STL_TRY {
	      return(_S_tree_concat(__leftleft, __rest));
            }
	    __STL_UNWIND(_S_unref(__leftleft); _S_unref(__rest))
	  }
	}
    }
    __left->_M_ref_nonnil();
    __right->_M_ref_nonnil();
    __STL_TRY {
      return(_S_tree_concat(__left, __right));
    }
    __STL_UNWIND(_S_unref(__left); _S_unref(__right));
}

template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeRep*
rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base, 
                               size_t __start, size_t __endp1)
{
    if (0 == __base) return 0;
    size_t __len = __base->_M_size;
    size_t __adj_endp1;
    const size_t __lazy_threshold = 128;
    
    if (__endp1 >= __len) {
	if (0 == __start) {
	    __base->_M_ref_nonnil();
	    return __base;
	} else {
	    __adj_endp1 = __len;
	}
    } else {
	__adj_endp1 = __endp1;
    }
    switch(__base->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __c = (_RopeConcatenation*)__base;
		_RopeRep* __left = __c->_M_left;
		_RopeRep* __right = __c->_M_right;
		size_t __left_len = __left->_M_size;
		_RopeRep* __result;

		if (__adj_endp1 <= __left_len) {
		    return _S_substring(__left, __start, __endp1);
		} else if (__start >= __left_len) {
		    return _S_substring(__right, __start - __left_len,
				  __adj_endp1 - __left_len);
		}
		_Self_destruct_ptr __left_result(
		  _S_substring(__left, __start, __left_len));
		_Self_destruct_ptr __right_result(
		  _S_substring(__right, 0, __endp1 - __left_len));
		__result = _S_concat(__left_result, __right_result);
#               ifndef __GC
		  __stl_assert(1 == __result->_M_ref_count);
#               endif
		return __result;
	    }
	case _RopeRep::_S_leaf:
	    {
		_RopeLeaf* __l = (_RopeLeaf*)__base;
		_RopeLeaf* __result;
		size_t __result_len;
		if (__start >= __adj_endp1) return 0;
		__result_len = __adj_endp1 - __start;
		if (__result_len > __lazy_threshold) goto lazy;
#               ifdef __GC
		    const _CharT* __section = __l->_M_data + __start;
		    __result = _S_new_RopeLeaf(__section, __result_len,
					  __base->get_allocator());
		    __result->_M_c_string = 0;  // Not eos terminated.
#               else
		    // We should sometimes create substring node instead.
		    __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(
					__l->_M_data + __start, __result_len,
					__base->get_allocator());
#               endif
		return __result;
	    }
	case _RopeRep::_S_substringfn:
	    // Avoid introducing multiple layers of substring nodes.
	    {
		_RopeSubstring* __old = (_RopeSubstring*)__base;
		size_t __result_len;
		if (__start >= __adj_endp1) return 0;
		__result_len = __adj_endp1 - __start;
		if (__result_len > __lazy_threshold) {
		    _RopeSubstring* __result =
			_S_new_RopeSubstring(__old->_M_base,
					  __start + __old->_M_start,
					  __adj_endp1 - __start,
					  __base->get_allocator());
		    return __result;

		} // *** else fall through: ***
	    }
	case _RopeRep::_S_function:
	    {
		_RopeFunction* __f = (_RopeFunction*)__base;
		_CharT* __section;
		size_t __result_len;
		if (__start >= __adj_endp1) return 0;
		__result_len = __adj_endp1 - __start;

		if (__result_len > __lazy_threshold) goto lazy;
		__section = (_CharT*)
			_Data_allocate(_S_rounded_up_size(__result_len));
		__STL_TRY {
		  (*(__f->_M_fn))(__start, __result_len, __section);
                }
		__STL_UNWIND(_RopeRep::__STL_FREE_STRING(
	               __section, __result_len, __base->get_allocator()));
		_S_cond_store_eos(__section[__result_len]);
		return _S_new_RopeLeaf(__section, __result_len,
				       __base->get_allocator());
	    }
    }
    /*NOTREACHED*/
    __stl_assert(false);
  lazy:
    {
	// Create substring node.
	return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
			       __base->get_allocator());
    }
}

template<class _CharT>
class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
    private:
	_CharT* _M_buf_ptr;
    public:

	_Rope_flatten_char_consumer(_CharT* __buffer) {
	    _M_buf_ptr = __buffer;
	};
	~_Rope_flatten_char_consumer() {}
	bool operator() (const _CharT* __leaf, size_t __n) {
	    uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
	    _M_buf_ptr += __n;
	    return true;
	}
};
	    
template<class _CharT>
class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> {
    private:
	_CharT _M_pattern;
    public:
	size_t _M_count;  // Number of nonmatching characters
	_Rope_find_char_char_consumer(_CharT __p) 
	  : _M_pattern(__p), _M_count(0) {}
	~_Rope_find_char_char_consumer() {}
	bool operator() (const _CharT* __leaf, size_t __n) {
	    size_t __i;
	    for (__i = 0; __i < __n; __i++) {
		if (__leaf[__i] == _M_pattern) {
		    _M_count += __i; return false;
		}
	    }
	    _M_count += __n; return true;
	}
};
	    
#ifdef __STL_USE_NEW_IOSTREAMS