template<class _CharT, class _Traits>
  // Here _CharT is both the stream and rope character type.
#else
  template<class _CharT>
  // Here _CharT is the rope character type.  Unlike in the
  // above case, we somewhat handle the case in which it doesn't
  // match the stream character type, i.e. char.
#endif
class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> {
    private:
#       ifdef __STL_USE_NEW_IOSTREAMS
	  typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
#	else
	  typedef ostream _Insert_ostream;
#	endif
	_Insert_ostream& _M_o;
    public:
	_Rope_insert_char_consumer(_Insert_ostream& __writer) 
	  : _M_o(__writer) {};
	~_Rope_insert_char_consumer() { };
		// Caller is presumed to own the ostream
	bool operator() (const _CharT* __leaf, size_t __n);
		// Returns true to continue traversal.
};
	    
#ifdef __STL_USE_NEW_IOSTREAMS
  template<class _CharT, class _Traits>
  bool _Rope_insert_char_consumer<_CharT, _Traits>::operator()
                                        (const _CharT* __leaf, size_t __n)
  {
    size_t __i;
    //  We assume that formatting is set up correctly for each element.
    for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
    return true;
  }

#else
  template<class _CharT>
  bool _Rope_insert_char_consumer<_CharT>::operator()
					(const _CharT* __leaf, size_t __n)
  {
    size_t __i;
    //  We assume that formatting is set up correctly for each element.
    for (__i = 0; __i < __n; __i++) _M_o << __leaf[__i];
    return true;
  }


  __STL_TEMPLATE_NULL
  inline bool _Rope_insert_char_consumer<char>::operator()
					(const char* __leaf, size_t __n)
  {
    size_t __i;
    for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
    return true;
  }
#endif

template <class _CharT, class _Alloc>
bool rope<_CharT, _Alloc>::_S_apply_to_pieces(
				_Rope_char_consumer<_CharT>& __c,
				const _RopeRep* __r,
				size_t __begin, size_t __end)
{
    if (0 == __r) return true;
    switch(__r->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __conc = (_RopeConcatenation*)__r;
		_RopeRep* __left =  __conc->_M_left;
		size_t __left_len = __left->_M_size;
		if (__begin < __left_len) {
		    size_t __left_end = min(__left_len, __end);
		    if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
			return false;
		}
		if (__end > __left_len) {
		    _RopeRep* __right =  __conc->_M_right;
		    size_t __right_start = max(__left_len, __begin);
		    if (!_S_apply_to_pieces(__c, __right,
					 __right_start - __left_len,
					 __end - __left_len)) {
			return false;
		    }
		}
	    }
	    return true;
	case _RopeRep::_S_leaf:
	    {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		return __c(__l->_M_data + __begin, __end - __begin);
	    }
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    {
		_RopeFunction* __f = (_RopeFunction*)__r;
		size_t __len = __end - __begin;
		bool __result;
		_CharT* __buffer =
		  (_CharT*)alloc::allocate(__len * sizeof(_CharT));
		__STL_TRY {
		  (*(__f->_M_fn))(__begin, __len, __buffer);
		  __result = __c(__buffer, __len);
                  alloc::deallocate(__buffer, __len * sizeof(_CharT));
                }
		__STL_UNWIND((alloc::deallocate(__buffer,
						__len * sizeof(_CharT))))
		return __result;
	    }
	default:
	    __stl_assert(false);
	    /*NOTREACHED*/
	    return false;
    }
}

#ifdef __STL_USE_NEW_IOSTREAMS
  template<class _CharT, class _Traits>
  inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
#else
  inline void _Rope_fill(ostream& __o, size_t __n)
#endif
{
    char __f = __o.fill();
    size_t __i;

    for (__i = 0; __i < __n; __i++) __o.put(__f);
}
    

template <class _CharT> inline bool _Rope_is_simple(_CharT*) { return false; }
inline bool _Rope_is_simple(char*) { return true; }
inline bool _Rope_is_simple(wchar_t*) { return true; }

#ifdef __STL_USE_NEW_IOSTREAMS
  template<class _CharT, class _Traits, class _Alloc>
  basic_ostream<_CharT, _Traits>& operator<<
					(basic_ostream<_CharT, _Traits>& __o,
					 const rope<_CharT, _Alloc>& __r)
#else
  template<class _CharT, class _Alloc>
  ostream& operator<< (ostream& __o, const rope<_CharT, _Alloc>& __r)
#endif
{
    size_t __w = __o.width();
    bool __left = bool(__o.flags() & ios::left);
    size_t __pad_len;
    size_t __rope_len = __r.size();
#   ifdef __STL_USE_NEW_IOSTREAMS
      _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
#   else
      _Rope_insert_char_consumer<_CharT> __c(__o);
#   endif
    bool __is_simple = _Rope_is_simple((_CharT*)0);
    
    if (__rope_len < __w) {
	__pad_len = __w - __rope_len;
    } else {
	__pad_len = 0;
    }
    if (!__is_simple) __o.width(__w/__rope_len);
    __STL_TRY {
      if (__is_simple && !__left && __pad_len > 0) {
	_Rope_fill(__o, __pad_len);
      }
      __r.apply_to_pieces(0, __r.size(), __c);
      if (__is_simple && __left && __pad_len > 0) {
	_Rope_fill(__o, __pad_len);
      }
      if (!__is_simple)
        __o.width(__w);
    }
    __STL_UNWIND(if (!__is_simple) __o.width(__w))
    return __o;
}

template <class _CharT, class _Alloc>
_CharT*
rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r,
				 size_t __start, size_t __len,
				 _CharT* __buffer)
{
    _Rope_flatten_char_consumer<_CharT> __c(__buffer);
    _S_apply_to_pieces(__c, __r, __start, __start + __len);
    return(__buffer + __len);
}

template <class _CharT, class _Alloc>
size_t
rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const
{
    _Rope_find_char_char_consumer<_CharT> __c(__pattern);
    _S_apply_to_pieces(__c, _M_tree_ptr, __start, size());
    size_type __result_pos = __start + __c._M_count;
#   ifndef __STL_OLD_ROPE_SEMANTICS
	if (__result_pos == size()) __result_pos = npos;
#   endif
    return __result_pos;
}

template <class _CharT, class _Alloc>
_CharT*
rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer)
{
    if (0 == __r) return __buffer;
    switch(__r->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		_RopeRep* __right = __c->_M_right;
		_CharT* __rest = _S_flatten(__left, __buffer);
		return _S_flatten(__right, __rest);
	    }
	case _RopeRep::_S_leaf:
	    {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
	    }
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    // We dont yet do anything with substring nodes.
	    // This needs to be fixed before ropefiles will work well.
	    {
		_RopeFunction* __f = (_RopeFunction*)__r;
		(*(__f->_M_fn))(0, __f->_M_size, __buffer);
		return __buffer + __f->_M_size;
	    }
	default:
	    __stl_assert(false);
	    /*NOTREACHED*/
	    return 0;
    }
}


// This needs work for _CharT != char
template <class _CharT, class _Alloc>
void
rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent)
{
    for (int __i = 0; __i < __indent; __i++) putchar(' ');
    if (0 == __r) {
	printf("NULL\n"); return;
    }
    if (_RopeRep::_S_concat == __r->_M_tag) {
	_RopeConcatenation* __c = (_RopeConcatenation*)__r;
	_RopeRep* __left = __c->_M_left;
	_RopeRep* __right = __c->_M_right;

#       ifdef __GC
	  printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
	    __r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not");
#       else
	  printf("Concatenation %p (rc = %ld, depth = %d, "
	           "len = %ld, %s balanced)\n",
		 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
		 __r->_M_is_balanced? "" : "not");
#       endif
	_S_dump(__left, __indent + 2);
	_S_dump(__right, __indent + 2);
	return;
    } else {
	char* __kind;

	switch (__r->_M_tag) {
	    case _RopeRep::_S_leaf:
		__kind = "Leaf";
		break;
	    case _RopeRep::_S_function:
		__kind = "Function";
		break;
	    case _RopeRep::_S_substringfn:
		__kind = "Function representing substring";
		break;
	    default:
		__kind = "(corrupted kind field!)";
	}
#       ifdef __GC
	  printf("%s %p (depth = %d, len = %ld) ",
		 __kind, __r, __r->_M_depth, __r->_M_size);
#       else
	  printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
		 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
#       endif
	if (_S_is_one_byte_char_type((_CharT*)0)) {
	    const int __max_len = 40;
	    _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
	    _CharT __buffer[__max_len + 1];
	    bool __too_big = __r->_M_size > __prefix->_M_size;

	    _S_flatten(__prefix, __buffer);
	    __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); 
	    printf("%s%s\n", 
	           (char*)__buffer, __too_big? "...\n" : "\n");
	} else {
	    printf("\n");
	}
    }
}

template <class _CharT, class _Alloc>
const unsigned long
rope<_CharT,_Alloc>::_S_min_len[
  _Rope_RopeRep<_CharT,_Alloc>::_S_max_rope_depth + 1] = {
/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
/* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
/* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
/* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
/* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
/* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
/* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
/* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
/* 45 */2971215073u };
// These are Fibonacci numbers < 2**32.

template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeRep*
rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r)
{
    _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1];
    _RopeRep* __result = 0;
    int __i;
    // Invariant:
    // The concatenation of forest in descending order is equal to __r.
    // __forest[__i]._M_size >= _S_min_len[__i]
    // __forest[__i]._M_depth = __i
    // References from forest are included in refcount.

    for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) 
      __forest[__i] = 0;
    __STL_TRY {
      _S_add_to_forest(__r, __forest);
      for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) 
        if (0 != __forest[__i]) {
#	ifndef __GC
	  _Self_destruct_ptr __old(__result);
#	endif
	  __result = _S_concat(__forest[__i], __result);
	__forest[__i]->_M_unref_nonnil();
#	if !defined(__GC) && defined(__STL_USE_EXCEPTIONS)
	  __forest[__i] = 0;
#	endif
      }
    }
    __STL_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; __i++)
		 _S_unref(__forest[__i]))
    if (__result->_M_depth > _RopeRep::_S_max_rope_depth) {
#     ifdef __STL_USE_EXCEPTIONS
	__STL_THROW(length_error("rope too long"));
#     else
	abort();
#     endif
    }
    return(__result);
}


template <class _CharT, class _Alloc>
void
rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
{
    if (__r->_M_is_balanced) {
	_S_add_leaf_to_forest(__r, __forest);
	return;
    }
    __stl_assert(__r->_M_tag == _RopeRep::_S_concat);
    {
	_RopeConcatenation* __c = (_RopeConcatenation*)__r;

	_S_add_to_forest(__c->_M_left, __forest);
	_S_add_to_forest(__c->_M_right, __forest);
    }
}


template <class _CharT, class _Alloc>
void
rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
{
    _RopeRep* __insertee;   		// included in refcount
    _RopeRep* __too_tiny = 0;    	// included in refcount
    int __i;  				// forest[0..__i-1] is empty
    size_t __s = __r->_M_size;

    for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
	if (0 != __forest[__i]) {
#	    ifndef __GC
	      _Self_destruct_ptr __old(__too_tiny);
#	    endif
	    __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
	    __forest[__i]->_M_unref_nonnil();
	    __forest[__i] = 0;
	}
    }