{
#	ifndef __GC
	  _Self_destruct_ptr __old(__too_tiny);
#	endif
	__insertee = _S_concat_and_set_balanced(__too_tiny, __r);
    }
    // Too_tiny dead, and no longer included in refcount.
    // Insertee is live and included.
    __stl_assert(_S_is_almost_balanced(__insertee));
    __stl_assert(__insertee->_M_depth <= __r->_M_depth + 1);
    for (;; ++__i) {
	if (0 != __forest[__i]) {
#	    ifndef __GC
	      _Self_destruct_ptr __old(__insertee);
#	    endif
	    __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
	    __forest[__i]->_M_unref_nonnil();
	    __forest[__i] = 0;
	    __stl_assert(_S_is_almost_balanced(__insertee));
	}
	__stl_assert(_S_min_len[__i] <= __insertee->_M_size);
	__stl_assert(__forest[__i] == 0);
	if (__i == _RopeRep::_S_max_rope_depth || 
	      __insertee->_M_size < _S_min_len[__i+1]) {
	    __forest[__i] = __insertee;
	    // refcount is OK since __insertee is now dead.
	    return;
	}
    }
}

template <class _CharT, class _Alloc>
_CharT
rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i)
{
    __GC_CONST _CharT* __cstr = __r->_M_c_string;

    __stl_assert(__i < __r->_M_size);
    if (0 != __cstr) return __cstr[__i]; 
    for(;;) {
      switch(__r->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size;

		if (__i >= __left_len) {
		    __i -= __left_len;
		    __r = __c->_M_right;
		} else {
		    __r = __left;
		}
	    }
	    break;
	case _RopeRep::_S_leaf:
	    {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		return __l->_M_data[__i];
	    }
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    {
		_RopeFunction* __f = (_RopeFunction*)__r;
		_CharT __result;

		(*(__f->_M_fn))(__i, 1, &__result);
		return __result;
	    }
      }
    }
}

# ifndef __GC
// Return a uniquely referenced character slot for the given
// position, or 0 if that's not possible.
template <class _CharT, class _Alloc>
_CharT*
rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
{
    _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
    size_t __csptr = 0;

    for(;;) {
      if (__r->_M_ref_count > 1) return 0;
      switch(__r->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size;

		if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
		if (__i >= __left_len) {
		    __i -= __left_len;
		    __r = __c->_M_right;
		} else {
		    __r = __left;
		}
	    }
	    break;
	case _RopeRep::_S_leaf:
	    {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
		    __clrstack[__csptr++] = __l;
		while (__csptr > 0) {
		    -- __csptr;
		    _RopeRep* __d = __clrstack[__csptr];
		    __d->_M_free_c_string();
		    __d->_M_c_string = 0;
		}
		return __l->_M_data + __i;
	    }
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    return 0;
      }
    }
}
# endif /* __GC */

// The following could be implemented trivially using
// lexicographical_compare_3way.
// We do a little more work to avoid dealing with rope iterators for
// flat strings.
template <class _CharT, class _Alloc>
int
rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left, 
                                 const _RopeRep* __right)
{
    size_t __left_len;
    size_t __right_len;

    if (0 == __right) return 0 != __left;
    if (0 == __left) return -1;
    __left_len = __left->_M_size;
    __right_len = __right->_M_size;
    if (_RopeRep::_S_leaf == __left->_M_tag) {
	_RopeLeaf* __l = (_RopeLeaf*) __left;
	if (_RopeRep::_S_leaf == __right->_M_tag) {
	    _RopeLeaf* __r = (_RopeLeaf*) __right;
	    return lexicographical_compare_3way(
			__l->_M_data, __l->_M_data + __left_len,
			__r->_M_data, __r->_M_data + __right_len);
	} else {
	    const_iterator __rstart(__right, 0);
	    const_iterator __rend(__right, __right_len);
	    return lexicographical_compare_3way(
			__l->_M_data, __l->_M_data + __left_len,
			__rstart, __rend);
	}
    } else {
	const_iterator __lstart(__left, 0);
	const_iterator __lend(__left, __left_len);
	if (_RopeRep::_S_leaf == __right->_M_tag) {
	    _RopeLeaf* __r = (_RopeLeaf*) __right;
	    return lexicographical_compare_3way(
				   __lstart, __lend,
				   __r->_M_data, __r->_M_data + __right_len);
	} else {
	    const_iterator __rstart(__right, 0);
	    const_iterator __rend(__right, __right_len);
	    return lexicographical_compare_3way(
				   __lstart, __lend,
				   __rstart, __rend);
	}
    }
}

// Assignment to reference proxies.
template <class _CharT, class _Alloc>
_Rope_char_ref_proxy<_CharT, _Alloc>&
_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
    _RopeRep* __old = _M_root->_M_tree_ptr;
#   ifndef __GC
	// First check for the case in which everything is uniquely
	// referenced.  In that case we can do this destructively.
	_CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
	if (0 != __ptr) {
	    *__ptr = __c;
	    return *this;
	}
#   endif
    _Self_destruct_ptr __left(
      _My_rope::_S_substring(__old, 0, _M_pos));
    _Self_destruct_ptr __right(
      _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size));
    _Self_destruct_ptr __result_left(
      _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));

#   ifndef __GC
      __stl_assert(__left == __result_left || 1 == __result_left->_M_ref_count);
#   endif
    _RopeRep* __result =
		_My_rope::_S_concat(__result_left, __right);
#   ifndef __GC
      __stl_assert(1 <= __result->_M_ref_count);
      _RopeRep::_S_unref(__old);
#   endif
    _M_root->_M_tree_ptr = __result;
    return *this;
}

template <class _CharT, class _Alloc>
inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const
{
    if (_M_current_valid) {
	return _M_current;
    } else {
        return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
    }
}
template <class _CharT, class _Alloc>
_Rope_char_ptr_proxy<_CharT, _Alloc>
_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
    return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
}

template <class _CharT, class _Alloc>
rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c,
			   const allocator_type& __a)
: _Base(__a)
{
    rope<_CharT,_Alloc> __result;
    const size_t __exponentiate_threshold = 32;
    size_t __exponent;
    size_t __rest;
    _CharT* __rest_buffer;
    _RopeRep* __remainder;
    rope<_CharT,_Alloc> __remainder_rope;

    if (0 == __n)
      return;
    
    __exponent = __n / __exponentiate_threshold;
    __rest = __n % __exponentiate_threshold;
    if (0 == __rest) {
	__remainder = 0;
    } else {
	__rest_buffer = _Data_allocate(_S_rounded_up_size(__rest));
	uninitialized_fill_n(__rest_buffer, __rest, __c);
	_S_cond_store_eos(__rest_buffer[__rest]);
	__STL_TRY {
	    __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a);
        }
	__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a))
    }
    __remainder_rope._M_tree_ptr = __remainder;
    if (__exponent != 0) {
	_CharT* __base_buffer =
	  _Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
	_RopeLeaf* __base_leaf;
	rope __base_rope;
	uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
	_S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
	__STL_TRY {
          __base_leaf = _S_new_RopeLeaf(__base_buffer,
                                        __exponentiate_threshold, __a);
        }
	__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__base_buffer, 
	                                         __exponentiate_threshold, __a))
	__base_rope._M_tree_ptr = __base_leaf;
 	if (1 == __exponent) {
	  __result = __base_rope;
#         ifndef __GC
	    __stl_assert(2 == __result._M_tree_ptr->_M_ref_count);
		// One each for base_rope and __result
#         endif
	} else {
	  __result = power(__base_rope, __exponent,
			   _Rope_Concat_fn<_CharT,_Alloc>());
	}
	if (0 != __remainder) {
	  __result += __remainder_rope;
	}
    } else {
	__result = __remainder_rope;
    }
    _M_tree_ptr = __result._M_tree_ptr;
    _M_tree_ptr->_M_ref_nonnil();
}

template<class _CharT, class _Alloc>
  _CharT rope<_CharT,_Alloc>::_S_empty_c_str[1];

template<class _CharT, class _Alloc>
const _CharT* rope<_CharT,_Alloc>::c_str() const {
    if (0 == _M_tree_ptr) {
        _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
					     // but probably fast.
        return _S_empty_c_str;
    }
    __GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string;
    if (0 != __old_c_string) return(__old_c_string);
    size_t __s = size();
    _CharT* __result = _Data_allocate(__s + 1);
    _S_flatten(_M_tree_ptr, __result);
    __result[__s] = _S_eos((_CharT*)0);
#   ifdef __GC
	_M_tree_ptr->_M_c_string = __result;
#   else
      if ((__old_c_string = (__GC_CONST _CharT*)
             _Atomic_swap((unsigned long *)(&(_M_tree_ptr->_M_c_string)),
			  (unsigned long)__result)) != 0) {
	// It must have been added in the interim.  Hence it had to have been
	// separately allocated.  Deallocate the old copy, since we just
	// replaced it.
	destroy(__old_c_string, __old_c_string + __s + 1);
	_Data_deallocate(__old_c_string, __s + 1);
      }
#   endif
    return(__result);
}

template<class _CharT, class _Alloc>
const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
    if (0 == _M_tree_ptr) {
        _S_empty_c_str[0] = _S_eos((_CharT*)0);
        return _S_empty_c_str;
    }
    __GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string;
    if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && 0 != __old_c_string) {
	return(__old_c_string);
    }
    size_t __s = size();
    _CharT* __result = _Data_allocate(_S_rounded_up_size(__s));
    _S_flatten(_M_tree_ptr, __result);
    __result[__s] = _S_eos((_CharT*)0);
    _M_tree_ptr->_M_unref_nonnil();
    _M_tree_ptr = _S_new_RopeLeaf(__result, __s, get_allocator());
    return(__result);
}

// Algorithm specializations.  More should be added.

#ifndef _MSC_VER
// I couldn't get this to work with VC++
template<class _CharT,class _Alloc>
void
_Rope_rotate(_Rope_iterator<_CharT,_Alloc> __first,
              _Rope_iterator<_CharT,_Alloc> __middle,
              _Rope_iterator<_CharT,_Alloc> __last)
{
    __stl_assert(__first.container() == __middle.container()
                 && __middle.container() == __last.container());
    rope<_CharT,_Alloc>& __r(__first.container());
    rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
    rope<_CharT,_Alloc> __suffix = 
      __r.substr(__last.index(), __r.size() - __last.index());
    rope<_CharT,_Alloc> __part1 = 
      __r.substr(__middle.index(), __last.index() - __middle.index());
    rope<_CharT,_Alloc> __part2 = 
      __r.substr(__first.index(), __middle.index() - __first.index());
    __r = __prefix;
    __r += __part1;
    __r += __part2;
    __r += __suffix;
}

#if !defined(__GNUC__)
// Appears to confuse g++
inline void rotate(_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __first,
                   _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __middle,
                   _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __last) {
    _Rope_rotate(__first, __middle, __last);
}
#endif

# if 0
// Probably not useful for several reasons:
// - for SGIs 7.1 compiler and probably some others,
//   this forces lots of rope<wchar_t, ...> instantiations, creating a
//   code bloat and compile time problem.  (Fixed in 7.2.)
// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
//   for unicode strings.  Unsigned short may be a better character
//   type.
inline void rotate(
		_Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first,
                _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle,
                _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last) {
    _Rope_rotate(__first, __middle, __last);
}
# endif
#endif /* _MSC_VER */

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif

__STL_END_NAMESPACE

// Local Variables:
// mode:C++
// End: