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.#endifclass _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;  }#endiftemplate <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_trope<_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 != chartemplate <class _CharT, class _Alloc>voidrope<_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 longrope<_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>voidrope<_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>voidrope<_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;	}    }