stl_rope.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:98k
源码类别:

STL

开发平台:

Visual C++

  1. /*
  2.  * Copyright (c) 1997-1998
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */
  13. /* NOTE: This is an internal header file, included by other STL headers.
  14.  *   You should not attempt to use it directly.
  15.  */
  16. // rope<_CharT,_Alloc> is a sequence of _CharT.
  17. // Ropes appear to be mutable, but update operations
  18. // really copy enough of the data structure to leave the original
  19. // valid.  Thus ropes can be logically copied by just copying
  20. // a pointer value.
  21. #ifndef __SGI_STL_INTERNAL_ROPE_H
  22. # define __SGI_STL_INTERNAL_ROPE_H
  23. # ifdef __GC
  24. #   define __GC_CONST const
  25. # else
  26. #   include <stl_threads.h>
  27. #   define __GC_CONST   // constant except for deallocation
  28. # endif
  29. # ifdef __STL_SGI_THREADS
  30. #    include <mutex.h>
  31. # endif
  32. __STL_BEGIN_NAMESPACE
  33. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  34. #pragma set woff 1174
  35. #endif
  36. // The _S_eos function is used for those functions that
  37. // convert to/from C-like strings to detect the end of the string.
  38. // The end-of-C-string character.
  39. // This is what the draft standard says it should be.
  40. template <class _CharT>
  41. inline _CharT _S_eos(_CharT*) { return _CharT(); }
  42. // Test for basic character types.
  43. // For basic character types leaves having a trailing eos.
  44. template <class _CharT>
  45. inline bool _S_is_basic_char_type(_CharT*) { return false; }
  46. template <class _CharT>
  47. inline bool _S_is_one_byte_char_type(_CharT*) { return false; }
  48. inline bool _S_is_basic_char_type(char*) { return true; }
  49. inline bool _S_is_one_byte_char_type(char*) { return true; }
  50. inline bool _S_is_basic_char_type(wchar_t*) { return true; }
  51. // Store an eos iff _CharT is a basic character type.
  52. // Do not reference _S_eos if it isn't.
  53. template <class _CharT>
  54. inline void _S_cond_store_eos(_CharT&) {}
  55. inline void _S_cond_store_eos(char& __c) { __c = 0; }
  56. inline void _S_cond_store_eos(wchar_t& __c) { __c = 0; }
  57. // char_producers are logically functions that generate a section of
  58. // a string.  These can be convereted to ropes.  The resulting rope
  59. // invokes the char_producer on demand.  This allows, for example,
  60. // files to be viewed as ropes without reading the entire file.
  61. template <class _CharT>
  62. class char_producer {
  63.     public:
  64.         virtual ~char_producer() {};
  65.         virtual void operator()(size_t __start_pos, size_t __len, 
  66.                                 _CharT* __buffer) = 0;
  67.         // Buffer should really be an arbitrary output iterator.
  68.         // That way we could flatten directly into an ostream, etc.
  69.         // This is thoroughly impossible, since iterator types don't
  70.         // have runtime descriptions.
  71. };
  72. // Sequence buffers:
  73. //
  74. // Sequence must provide an append operation that appends an
  75. // array to the sequence.  Sequence buffers are useful only if
  76. // appending an entire array is cheaper than appending element by element.
  77. // This is true for many string representations.
  78. // This should  perhaps inherit from ostream<sequence::value_type>
  79. // and be implemented correspondingly, so that they can be used
  80. // for formatted.  For the sake of portability, we don't do this yet.
  81. //
  82. // For now, sequence buffers behave as output iterators.  But they also
  83. // behave a little like basic_ostringstream<sequence::value_type> and a
  84. // little like containers.
  85. template<class _Sequence, size_t _Buf_sz = 100
  86. #   if defined(__sgi) && !defined(__GNUC__)
  87. #        define __TYPEDEF_WORKAROUND
  88.          ,class _V = typename _Sequence::value_type
  89. #   endif
  90.         >
  91. // The 3rd parameter works around a common compiler bug.
  92. class sequence_buffer : public output_iterator {
  93.     public:
  94. #       ifndef __TYPEDEF_WORKAROUND
  95.             typedef typename _Sequence::value_type value_type;
  96. #       else
  97.             typedef _V value_type;
  98. #       endif
  99.     protected:
  100.         _Sequence* _M_prefix;
  101.         value_type _M_buffer[_Buf_sz];
  102.         size_t     _M_buf_count;
  103.     public:
  104.         void flush() {
  105.             _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
  106.             _M_buf_count = 0;
  107.         }
  108.         ~sequence_buffer() { flush(); }
  109.         sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}
  110.         sequence_buffer(const sequence_buffer& __x) {
  111.             _M_prefix = __x._M_prefix;
  112.             _M_buf_count = __x._M_buf_count;
  113.             copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
  114.         }
  115.         sequence_buffer(sequence_buffer& __x) {
  116.             __x.flush();
  117.             _M_prefix = __x._M_prefix;
  118.             _M_buf_count = 0;
  119.         }
  120.         sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}
  121.         sequence_buffer& operator= (sequence_buffer& __x) {
  122.             __x.flush();
  123.             _M_prefix = __x._M_prefix;
  124.             _M_buf_count = 0;
  125.             return *this;
  126.         }
  127.         sequence_buffer& operator= (const sequence_buffer& __x) {
  128.             _M_prefix = __x._M_prefix;
  129.             _M_buf_count = __x._M_buf_count;
  130.             copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
  131.             return *this;
  132.         }
  133.         void push_back(value_type __x)
  134.         {
  135.             if (_M_buf_count < _Buf_sz) {
  136.                 _M_buffer[_M_buf_count] = __x;
  137.                 ++_M_buf_count;
  138.             } else {
  139.                 flush();
  140.                 _M_buffer[0] = __x;
  141.                 _M_buf_count = 1;
  142.             }
  143.         }
  144.         void append(value_type* __s, size_t __len)
  145.         {
  146.             if (__len + _M_buf_count <= _Buf_sz) {
  147.                 size_t __i = _M_buf_count;
  148.                 size_t __j = 0;
  149.                 for (; __j < __len; __i++, __j++) {
  150.                     _M_buffer[__i] = __s[__j];
  151.                 }
  152.                 _M_buf_count += __len;
  153.             } else if (0 == _M_buf_count) {
  154.                 _M_prefix->append(__s, __s + __len);
  155.             } else {
  156.                 flush();
  157.                 append(__s, __len);
  158.             }
  159.         }
  160.         sequence_buffer& write(value_type* __s, size_t __len)
  161.         {
  162.             append(__s, __len);
  163.             return *this;
  164.         }
  165.         sequence_buffer& put(value_type __x)
  166.         {
  167.             push_back(__x);
  168.             return *this;
  169.         }
  170.         sequence_buffer& operator=(const value_type& __rhs)
  171.         {
  172.             push_back(__rhs);
  173.             return *this;
  174.         }
  175.         sequence_buffer& operator*() { return *this; }
  176.         sequence_buffer& operator++() { return *this; }
  177.         sequence_buffer& operator++(int) { return *this; }
  178. };
  179. // The following should be treated as private, at least for now.
  180. template<class _CharT>
  181. class _Rope_char_consumer {
  182.     public:
  183.         // If we had member templates, these should not be virtual.
  184.         // For now we need to use run-time parametrization where
  185.         // compile-time would do.  Hence this should all be private
  186.         // for now.
  187.         // The symmetry with char_producer is accidental and temporary.
  188.         virtual ~_Rope_char_consumer() {};
  189.         virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;
  190. };
  191. // First a lot of forward declarations.  The standard seems to require
  192. // much stricter "declaration before use" than many of the implementations
  193. // that preceded it.
  194. template<class _CharT, class _Alloc=__STL_DEFAULT_ALLOCATOR(_CharT)> class rope;
  195. template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;
  196. template<class _CharT, class _Alloc> struct _Rope_RopeLeaf;
  197. template<class _CharT, class _Alloc> struct _Rope_RopeFunction;
  198. template<class _CharT, class _Alloc> struct _Rope_RopeSubstring;
  199. template<class _CharT, class _Alloc> class _Rope_iterator;
  200. template<class _CharT, class _Alloc> class _Rope_const_iterator;
  201. template<class _CharT, class _Alloc> class _Rope_char_ref_proxy;
  202. template<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;
  203. template<class _CharT, class _Alloc>
  204. bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x,
  205.                  const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y);
  206. template<class _CharT, class _Alloc>
  207. _Rope_const_iterator<_CharT,_Alloc> operator-
  208.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  209.          ptrdiff_t __n);
  210. template<class _CharT, class _Alloc>
  211. _Rope_const_iterator<_CharT,_Alloc> operator+
  212.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  213.          ptrdiff_t __n);
  214. template<class _CharT, class _Alloc>
  215. _Rope_const_iterator<_CharT,_Alloc> operator+
  216.         (ptrdiff_t __n,
  217.          const _Rope_const_iterator<_CharT,_Alloc>& __x);
  218. template<class _CharT, class _Alloc>
  219. bool operator== 
  220.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  221.          const _Rope_const_iterator<_CharT,_Alloc>& __y);
  222. template<class _CharT, class _Alloc>
  223. bool operator< 
  224.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  225.          const _Rope_const_iterator<_CharT,_Alloc>& __y);
  226. template<class _CharT, class _Alloc>
  227. ptrdiff_t operator- 
  228.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  229.          const _Rope_const_iterator<_CharT,_Alloc>& __y);
  230. template<class _CharT, class _Alloc>
  231. _Rope_iterator<_CharT,_Alloc> operator-
  232.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  233.          ptrdiff_t __n);
  234. template<class _CharT, class _Alloc>
  235. _Rope_iterator<_CharT,_Alloc> operator+
  236.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  237.          ptrdiff_t __n);
  238. template<class _CharT, class _Alloc>
  239. _Rope_iterator<_CharT,_Alloc> operator+
  240.         (ptrdiff_t __n,
  241.          const _Rope_iterator<_CharT,_Alloc>& __x);
  242. template<class _CharT, class _Alloc>
  243. bool operator== 
  244.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  245.          const _Rope_iterator<_CharT,_Alloc>& __y);
  246. template<class _CharT, class _Alloc>
  247. bool operator< 
  248.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  249.          const _Rope_iterator<_CharT,_Alloc>& __y);
  250. template<class _CharT, class _Alloc>
  251. ptrdiff_t operator- 
  252.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  253.          const _Rope_iterator<_CharT,_Alloc>& __y);
  254. template<class _CharT, class _Alloc>
  255. rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,
  256.                                const rope<_CharT,_Alloc>& __right);
  257.         
  258. template<class _CharT, class _Alloc>
  259. rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,
  260.                                const _CharT* __right);
  261.         
  262. template<class _CharT, class _Alloc>
  263. rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,
  264.                                _CharT __right);
  265.         
  266. // Some helpers, so we can use power on ropes.
  267. // See below for why this isn't local to the implementation.
  268. // This uses a nonstandard refcount convention.
  269. // The result has refcount 0.
  270. template<class _CharT, class _Alloc>
  271. struct _Rope_Concat_fn
  272.        : public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>,
  273.                                      rope<_CharT,_Alloc> > {
  274.         rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x,
  275.                                 const rope<_CharT,_Alloc>& __y) {
  276.                     return __x + __y;
  277.         }
  278. };
  279. template <class _CharT, class _Alloc>
  280. inline
  281. rope<_CharT,_Alloc>
  282. identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
  283. {
  284.     return rope<_CharT,_Alloc>();
  285. }
  286. //
  287. // What follows should really be local to rope.  Unfortunately,
  288. // that doesn't work, since it makes it impossible to define generic
  289. // equality on rope iterators.  According to the draft standard, the
  290. // template parameters for such an equality operator cannot be inferred
  291. // from the occurence of a member class as a parameter.
  292. // (SGI compilers in fact allow this, but the __result wouldn't be
  293. // portable.)
  294. // Similarly, some of the static member functions are member functions
  295. // only to avoid polluting the global namespace, and to circumvent
  296. // restrictions on type inference for template functions.
  297. //
  298. //
  299. // The internal data structure for representing a rope.  This is
  300. // private to the implementation.  A rope is really just a pointer
  301. // to one of these.
  302. //
  303. // A few basic functions for manipulating this data structure
  304. // are members of _RopeRep.  Most of the more complex algorithms
  305. // are implemented as rope members.
  306. //
  307. // Some of the static member functions of _RopeRep have identically
  308. // named functions in rope that simply invoke the _RopeRep versions.
  309. //
  310. // A macro to introduce various allocation and deallocation functions
  311. // These need to be defined differently depending on whether or not
  312. // we are using standard conforming allocators, and whether the allocator
  313. // instances have real state.  Thus this macro is invoked repeatedly
  314. // with different definitions of __ROPE_DEFINE_ALLOC.
  315. // __ROPE_DEFINE_ALLOC(type,name) defines 
  316. //   type * name_allocate(size_t) and
  317. //   void name_deallocate(tipe *, size_t)
  318. // Both functions may or may not be static.
  319. #define __ROPE_DEFINE_ALLOCS(__a) 
  320.         __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ 
  321.         typedef _Rope_RopeConcatenation<_CharT,__a> __C; 
  322.         __ROPE_DEFINE_ALLOC(__C,_C) 
  323.         typedef _Rope_RopeLeaf<_CharT,__a> __L; 
  324.         __ROPE_DEFINE_ALLOC(__L,_L) 
  325.         typedef _Rope_RopeFunction<_CharT,__a> __F; 
  326.         __ROPE_DEFINE_ALLOC(__F,_F) 
  327.         typedef _Rope_RopeSubstring<_CharT,__a> __S; 
  328.         __ROPE_DEFINE_ALLOC(__S,_S)
  329. //  Internal rope nodes potentially store a copy of the allocator
  330. //  instance used to allocate them.  This is mostly redundant.
  331. //  But the alternative would be to pass allocator instances around
  332. //  in some form to nearly all internal functions, since any pointer
  333. //  assignment may result in a zero reference count and thus require
  334. //  deallocation.
  335. //  The _Rope_rep_base class encapsulates
  336. //  the differences between SGI-style allocators and standard-conforming
  337. //  allocators.
  338. #ifdef __STL_USE_STD_ALLOCATORS
  339. #define __STATIC_IF_SGI_ALLOC  /* not static */
  340. // Base class for ordinary allocators.
  341. template <class _CharT, class _Allocator, bool _IsStatic>
  342. class _Rope_rep_alloc_base {
  343. public:
  344.   typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
  345.           allocator_type;
  346.   allocator_type get_allocator() const { return _M_data_allocator; }
  347.   _Rope_rep_alloc_base(size_t __size, const allocator_type& __a)
  348.         : _M_size(__size), _M_data_allocator(__a) {}
  349.   size_t _M_size;       // This is here only to avoid wasting space
  350.                 // for an otherwise empty base class.
  351.   
  352. protected:
  353.     allocator_type _M_data_allocator;
  354. # define __ROPE_DEFINE_ALLOC(_Tp, __name) 
  355.         typedef typename 
  356.           _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; 
  357.         /*static*/ _Tp * __name##_allocate(size_t __n) 
  358.           { return __name##Allocator(_M_data_allocator).allocate(__n); } 
  359.         void __name##_deallocate(_Tp* __p, size_t __n) 
  360.           { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
  361.   __ROPE_DEFINE_ALLOCS(_Allocator);
  362. # undef __ROPE_DEFINE_ALLOC
  363. };
  364. // Specialization for allocators that have the property that we don't
  365. //  actually have to store an allocator object.  
  366. template <class _CharT, class _Allocator>
  367. class _Rope_rep_alloc_base<_CharT,_Allocator,true> {
  368. public:
  369.   typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
  370.           allocator_type;
  371.   allocator_type get_allocator() const { return allocator_type(); }
  372.   _Rope_rep_alloc_base(size_t __size, const allocator_type&)
  373.                 : _M_size(__size) {}
  374.   size_t _M_size;
  375.   
  376. protected:
  377. # define __ROPE_DEFINE_ALLOC(_Tp, __name) 
  378.         typedef typename 
  379.           _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; 
  380.         typedef typename 
  381.           _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; 
  382.         static _Tp* __name##_allocate(size_t __n) 
  383.                 { return __name##Alloc::allocate(__n); } 
  384.         void __name##_deallocate(_Tp *__p, size_t __n) 
  385.                 { __name##Alloc::deallocate(__p, __n); }
  386.   __ROPE_DEFINE_ALLOCS(_Allocator);
  387. # undef __ROPE_DEFINE_ALLOC
  388. };
  389. template <class _CharT, class _Alloc>
  390. struct _Rope_rep_base
  391.   : public _Rope_rep_alloc_base<_CharT,_Alloc,
  392.                                 _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
  393. {
  394.   typedef _Rope_rep_alloc_base<_CharT,_Alloc,
  395.                                _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
  396.           _Base;
  397.   typedef typename _Base::allocator_type allocator_type;
  398.   _Rope_rep_base(size_t __size, const allocator_type& __a)
  399.     : _Base(__size, __a) {}
  400. };    
  401. #else /* !__STL_USE_STD_ALLOCATORS */
  402. #define __STATIC_IF_SGI_ALLOC static
  403. template <class _CharT, class _Alloc> 
  404. class _Rope_rep_base {
  405. public:
  406.   typedef _Alloc allocator_type;
  407.   static allocator_type get_allocator() { return allocator_type(); }
  408.   _Rope_rep_base(size_t __size, const allocator_type&) : _M_size(__size) {}
  409.   size_t _M_size;
  410. protected:
  411. # define __ROPE_DEFINE_ALLOC(_Tp, __name) 
  412.         typedef simple_alloc<_Tp, _Alloc> __name##Alloc; 
  413.         static _Tp* __name##_allocate(size_t __n) 
  414.                 { return __name##Alloc::allocate(__n); } 
  415.         static void __name##_deallocate(_Tp* __p, size_t __n) 
  416.                 { __name##Alloc::deallocate(__p, __n); }
  417.   __ROPE_DEFINE_ALLOCS(_Alloc);
  418. # undef __ROPE_DEFINE_ALLOC
  419. };
  420. #endif /* __STL_USE_STD_ALLOCATORS */
  421. template<class _CharT, class _Alloc>
  422. struct _Rope_RopeRep : public _Rope_rep_base<_CharT,_Alloc>
  423. # ifndef __GC
  424.     , _Refcount_Base
  425. # endif
  426. {
  427.     public:
  428.     enum { _S_max_rope_depth = 45 };
  429.     enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
  430.     _Tag _M_tag:8;
  431.     bool _M_is_balanced:8;
  432.     unsigned char _M_depth;
  433.     __GC_CONST _CharT* _M_c_string;
  434.                         /* Flattened version of string, if needed.  */
  435.                         /* typically 0.                             */
  436.                         /* If it's not 0, then the memory is owned  */
  437.                         /* by this node.                            */
  438.                         /* In the case of a leaf, this may point to */
  439.                         /* the same memory as the data field.       */
  440.     typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
  441.                         allocator_type;
  442.     _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t __size,
  443.                   allocator_type __a)
  444.         : _Rope_rep_base<_CharT,_Alloc>(__size, __a),
  445. #         ifndef __GC
  446.           _Refcount_Base(1),
  447. #         endif
  448.           _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
  449.     { }
  450. #   ifdef __GC
  451.         void _M_incr () {}
  452. #   endif
  453. #   ifdef __STL_USE_STD_ALLOCATORS
  454.         static void _S_free_string(__GC_CONST _CharT*, size_t __len,
  455.                                    allocator_type __a);
  456. #       define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
  457. #   else
  458.         static void _S_free_string(__GC_CONST _CharT*, size_t __len);
  459. #       define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l);
  460. #   endif
  461.                         // Deallocate data section of a leaf.
  462.                         // This shouldn't be a member function.
  463.                         // But its hard to do anything else at the
  464.                         // moment, because it's templatized w.r.t.
  465.                         // an allocator.
  466.                         // Does nothing if __GC is defined.
  467. #   ifndef __GC
  468.           void _M_free_c_string();
  469.           void _M_free_tree();
  470.                         // Deallocate t. Assumes t is not 0.
  471.           void _M_unref_nonnil()
  472.           {
  473.               if (0 == _M_decr()) _M_free_tree();
  474.           }
  475.           void _M_ref_nonnil()
  476.           {
  477.               _M_incr();
  478.           }
  479.           static void _S_unref(_Rope_RopeRep* __t)
  480.           {
  481.               if (0 != __t) {
  482.                   __t->_M_unref_nonnil();
  483.               }
  484.           }
  485.           static void _S_ref(_Rope_RopeRep* __t)
  486.           {
  487.               if (0 != __t) __t->_M_incr();
  488.           }
  489.           static void _S_free_if_unref(_Rope_RopeRep* __t)
  490.           {
  491.               if (0 != __t && 0 == __t->_M_ref_count) __t->_M_free_tree();
  492.           }
  493. #   else /* __GC */
  494.           void _M_unref_nonnil() {}
  495.           void _M_ref_nonnil() {}
  496.           static void _S_unref(_Rope_RopeRep*) {}
  497.           static void _S_ref(_Rope_RopeRep*) {}
  498.           static void _S_free_if_unref(_Rope_RopeRep*) {}
  499. #   endif
  500. };
  501. template<class _CharT, class _Alloc>
  502. struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> {
  503.   public:
  504.     // Apparently needed by VC++
  505.     // The data fields of leaves are allocated with some
  506.     // extra space, to accomodate future growth and for basic
  507.     // character types, to hold a trailing eos character.
  508.     enum { _S_alloc_granularity = 8 };
  509.     static size_t _S_rounded_up_size(size_t __n) {
  510.         size_t __size_with_eos;
  511.              
  512.         if (_S_is_basic_char_type((_CharT*)0)) {
  513.             __size_with_eos = __n + 1;
  514.         } else {
  515.             __size_with_eos = __n;
  516.         }
  517. #       ifdef __GC
  518.            return __size_with_eos;
  519. #       else
  520.            // Allow slop for in-place expansion.
  521.            return (__size_with_eos + _S_alloc_granularity-1)
  522.                         &~ (_S_alloc_granularity-1);
  523. #       endif
  524.     }
  525.     __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
  526.                                 /* The allocated size is         */
  527.                                 /* _S_rounded_up_size(size), except */
  528.                                 /* in the GC case, in which it   */
  529.                                 /* doesn't matter.               */
  530.     typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
  531.                         allocator_type;
  532.     _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, allocator_type __a)
  533.         : _Rope_RopeRep<_CharT,_Alloc>(_S_leaf, 0, true, __size, __a),
  534.           _M_data(__d)
  535.         {
  536.         __stl_assert(__size > 0);
  537.         if (_S_is_basic_char_type((_CharT *)0)) {
  538.             // already eos terminated.
  539.             _M_c_string = __d;
  540.         }
  541.     }
  542.         // The constructor assumes that d has been allocated with
  543.         // the proper allocator and the properly padded size.
  544.         // In contrast, the destructor deallocates the data:
  545. # ifndef __GC
  546.     ~_Rope_RopeLeaf() {
  547.         if (_M_data != _M_c_string) {
  548.             _M_free_c_string();
  549.         }
  550.         __STL_FREE_STRING(_M_data, _M_size, get_allocator());
  551.     }
  552. # endif
  553. };
  554. template<class _CharT, class _Alloc>
  555. struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT,_Alloc> {
  556.   public:
  557.     _Rope_RopeRep<_CharT,_Alloc>* _M_left;
  558.     _Rope_RopeRep<_CharT,_Alloc>* _M_right;
  559.     typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
  560.                         allocator_type;
  561.     _Rope_RopeConcatenation(_Rope_RopeRep<_CharT,_Alloc>* __l,
  562.                              _Rope_RopeRep<_CharT,_Alloc>* __r,
  563.                              allocator_type __a)
  564.       : _Rope_RopeRep<_CharT,_Alloc>(_S_concat,
  565.                                      max(__l->_M_depth, __r->_M_depth) + 1,
  566.                                      false,
  567.                                      __l->_M_size + __r->_M_size, __a),
  568.         _M_left(__l), _M_right(__r)
  569.       {}
  570. # ifndef __GC
  571.     ~_Rope_RopeConcatenation() {
  572.         _M_free_c_string();
  573.         _M_left->_M_unref_nonnil();
  574.         _M_right->_M_unref_nonnil();
  575.     }
  576. # endif
  577. };
  578. template<class _CharT, class _Alloc>
  579. struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT,_Alloc> {
  580.   public:
  581.     char_producer<_CharT>* _M_fn;
  582. #   ifndef __GC
  583.       bool _M_delete_when_done; // Char_producer is owned by the
  584.                                 // rope and should be explicitly
  585.                                 // deleted when the rope becomes
  586.                                 // inaccessible.
  587. #   else
  588.       // In the GC case, we either register the rope for
  589.       // finalization, or not.  Thus the field is unnecessary;
  590.       // the information is stored in the collector data structures.
  591.       // We do need a finalization procedure to be invoked by the
  592.       // collector.
  593.       static void _S_fn_finalization_proc(void * __tree, void *) {
  594.         delete ((_Rope_RopeFunction *)__tree) -> _M_fn;
  595.       }
  596. #   endif
  597.     typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
  598.                                         allocator_type;
  599.     _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
  600.                         bool __d, allocator_type __a)
  601.       : _Rope_RopeRep<_CharT,_Alloc>(_S_function, 0, true, __size, __a)
  602.       , _M_fn(__f)
  603. #       ifndef __GC
  604.       , _M_delete_when_done(__d)
  605. #       endif
  606.     {
  607.         __stl_assert(__size > 0);
  608. #       ifdef __GC
  609.             if (__d) {
  610.                 GC_REGISTER_FINALIZER(
  611.                   this, _Rope_RopeFunction::_S_fn_finalization_proc, 0, 0, 0);
  612.             }
  613. #       endif
  614.     }
  615. # ifndef __GC
  616.     ~_Rope_RopeFunction() {
  617.           _M_free_c_string();
  618.           if (_M_delete_when_done) {
  619.               delete _M_fn;
  620.           }
  621.     }
  622. # endif
  623. };
  624. // Substring results are usually represented using just
  625. // concatenation nodes.  But in the case of very long flat ropes
  626. // or ropes with a functional representation that isn't practical.
  627. // In that case, we represent the __result as a special case of
  628. // RopeFunction, whose char_producer points back to the rope itself.
  629. // In all cases except repeated substring operations and
  630. // deallocation, we treat the __result as a RopeFunction.
  631. template<class _CharT, class _Alloc>
  632. struct _Rope_RopeSubstring : public _Rope_RopeFunction<_CharT,_Alloc>,
  633.                              public char_producer<_CharT> {
  634.   public:
  635.     // XXX this whole class should be rewritten.
  636.     _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
  637.     size_t _M_start;
  638.     virtual void operator()(size_t __start_pos, size_t __req_len,
  639.                             _CharT* __buffer) {
  640.         switch(_M_base->_M_tag) {
  641.             case _S_function:
  642.             case _S_substringfn:
  643.               {
  644.                 char_producer<_CharT>* __fn =
  645.                         ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
  646.                 __stl_assert(__start_pos + __req_len <= _M_size);
  647.                 __stl_assert(_M_start + _M_size <= _M_base->_M_size);
  648.                 (*__fn)(__start_pos + _M_start, __req_len, __buffer);
  649.               }
  650.               break;
  651.             case _S_leaf:
  652.               {
  653.                 __GC_CONST _CharT* __s =
  654.                         ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
  655.                 uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
  656.                                      __buffer);
  657.               }
  658.               break;
  659.             default:
  660.               __stl_assert(false);
  661.         }
  662.     }
  663.     typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
  664.         allocator_type;
  665.     _Rope_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
  666.                           size_t __l, allocator_type __a)
  667.       : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a),
  668.         char_producer<_CharT>(),
  669.         _M_base(__b),
  670.         _M_start(__s)
  671.     {
  672.         __stl_assert(__l > 0);
  673.         __stl_assert(__s + __l <= __b->_M_size);
  674. #       ifndef __GC
  675.             _M_base->_M_ref_nonnil();
  676. #       endif
  677.         _M_tag = _S_substringfn;
  678.     }
  679.     virtual ~_Rope_RopeSubstring()
  680.       { 
  681. #       ifndef __GC
  682.           _M_base->_M_unref_nonnil();
  683.           // _M_free_c_string();  -- done by parent class
  684. #       endif
  685.       }
  686. };
  687. // Self-destructing pointers to Rope_rep.
  688. // These are not conventional smart pointers.  Their
  689. // only purpose in life is to ensure that unref is called
  690. // on the pointer either at normal exit or if an exception
  691. // is raised.  It is the caller's responsibility to
  692. // adjust reference counts when these pointers are initialized
  693. // or assigned to.  (This convention significantly reduces
  694. // the number of potentially expensive reference count
  695. // updates.)
  696. #ifndef __GC
  697.   template<class _CharT, class _Alloc>
  698.   struct _Rope_self_destruct_ptr {
  699.     _Rope_RopeRep<_CharT,_Alloc>* _M_ptr;
  700.     ~_Rope_self_destruct_ptr() 
  701.       { _Rope_RopeRep<_CharT,_Alloc>::_S_unref(_M_ptr); }
  702. #   ifdef __STL_USE_EXCEPTIONS
  703.         _Rope_self_destruct_ptr() : _M_ptr(0) {};
  704. #   else
  705.         _Rope_self_destruct_ptr() {};
  706. #   endif
  707.     _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT,_Alloc>* __p) : _M_ptr(__p) {}
  708.     _Rope_RopeRep<_CharT,_Alloc>& operator*() { return *_M_ptr; }
  709.     _Rope_RopeRep<_CharT,_Alloc>* operator->() { return _M_ptr; }
  710.     operator _Rope_RopeRep<_CharT,_Alloc>*() { return _M_ptr; }
  711.     _Rope_self_destruct_ptr& operator= (_Rope_RopeRep<_CharT,_Alloc>* __x)
  712.         { _M_ptr = __x; return *this; }
  713.   };
  714. #endif
  715. // Dereferencing a nonconst iterator has to return something
  716. // that behaves almost like a reference.  It's not possible to
  717. // return an actual reference since assignment requires extra
  718. // work.  And we would get into the same problems as with the
  719. // CD2 version of basic_string.
  720. template<class _CharT, class _Alloc>
  721. class _Rope_char_ref_proxy {
  722.     friend class rope<_CharT,_Alloc>;
  723.     friend class _Rope_iterator<_CharT,_Alloc>;
  724.     friend class _Rope_char_ptr_proxy<_CharT,_Alloc>;
  725. #   ifdef __GC
  726.         typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr;
  727. #   else
  728.         typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;
  729. #   endif
  730.     typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
  731.     typedef rope<_CharT,_Alloc> _My_rope;
  732.     size_t _M_pos;
  733.     _CharT _M_current;
  734.     bool _M_current_valid;
  735.     _My_rope* _M_root;     // The whole rope.
  736.   public:
  737.     _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
  738.       :  _M_pos(__p), _M_current_valid(false), _M_root(__r) {}
  739.     _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
  740.       : _M_pos(__x._M_pos), _M_current_valid(false), _M_root(__x._M_root) {}
  741.         // Don't preserve cache if the reference can outlive the
  742.         // expression.  We claim that's not possible without calling
  743.         // a copy constructor or generating reference to a proxy
  744.         // reference.  We declare the latter to have undefined semantics.
  745.     _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
  746.       : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {}
  747.     inline operator _CharT () const;
  748.     _Rope_char_ref_proxy& operator= (_CharT __c);
  749.     _Rope_char_ptr_proxy<_CharT,_Alloc> operator& () const;
  750.     _Rope_char_ref_proxy& operator= (const _Rope_char_ref_proxy& __c) {
  751.         return operator=((_CharT)__c); 
  752.     }
  753. };
  754. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  755.     template<class _CharT, class __Alloc>
  756.     inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
  757.                      _Rope_char_ref_proxy <_CharT, __Alloc > __b) {
  758.         _CharT __tmp = __a;
  759.         __a = __b;
  760.         __b = __tmp;
  761.     }
  762. #else
  763. // There is no really acceptable way to handle this.  The default
  764. // definition of swap doesn't work for proxy references.
  765. // It can't really be made to work, even with ugly hacks, since
  766. // the only unusual operation it uses is the copy constructor, which
  767. // is needed for other purposes.  We provide a macro for
  768. // full specializations, and instantiate the most common case.
  769. # define _ROPE_SWAP_SPECIALIZATION(_CharT, __Alloc) 
  770.     inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, 
  771.                      _Rope_char_ref_proxy <_CharT, __Alloc > __b) { 
  772.         _CharT __tmp = __a; 
  773.         __a = __b; 
  774.         __b = __tmp; 
  775.     }
  776. _ROPE_SWAP_SPECIALIZATION(char,__STL_DEFAULT_ALLOCATOR(char))
  777. #endif /* !__STL_FUNCTION_TMPL_PARTIAL_ORDER */
  778. template<class _CharT, class _Alloc>
  779. class _Rope_char_ptr_proxy {
  780.     // XXX this class should be rewritten.
  781.     friend class _Rope_char_ref_proxy<_CharT,_Alloc>;
  782.     size_t _M_pos;
  783.     rope<_CharT,_Alloc>* _M_root;     // The whole rope.
  784.   public:
  785.     _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) 
  786.       : _M_pos(__x._M_pos), _M_root(__x._M_root) {}
  787.     _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
  788.       : _M_pos(__x._M_pos), _M_root(__x._M_root) {}
  789.     _Rope_char_ptr_proxy() {}
  790.     _Rope_char_ptr_proxy(_CharT* __x) : _M_root(0), _M_pos(0) {
  791.         __stl_assert(0 == __x);
  792.     }
  793.     _Rope_char_ptr_proxy& 
  794.     operator= (const _Rope_char_ptr_proxy& __x) {
  795.         _M_pos = __x._M_pos;
  796.         _M_root = __x._M_root;
  797.         return *this;
  798.     }
  799. #ifdef __STL_MEMBER_TEMPLATES
  800.     template<class _CharT2, class _Alloc2>
  801.     friend bool operator== (const _Rope_char_ptr_proxy<_CharT2,_Alloc2>& __x,
  802.                             const _Rope_char_ptr_proxy<_CharT2,_Alloc2>& __y);
  803. #else
  804.     friend bool operator==  __STL_NULL_TMPL_ARGS
  805.                 (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x,
  806.                  const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y);
  807. #endif
  808.     _Rope_char_ref_proxy<_CharT,_Alloc> operator*() const {
  809.         return _Rope_char_ref_proxy<_CharT,_Alloc>(_M_root, _M_pos);
  810.     }
  811. };
  812. // Rope iterators:
  813. // Unlike in the C version, we cache only part of the stack
  814. // for rope iterators, since they must be efficiently copyable.
  815. // When we run out of cache, we have to reconstruct the iterator
  816. // value.
  817. // Pointers from iterators are not included in reference counts.
  818. // Iterators are assumed to be thread private.  Ropes can
  819. // be shared.
  820. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  821. #pragma set woff 1375
  822. #endif
  823. template<class _CharT, class _Alloc>
  824. class _Rope_iterator_base
  825.   : public random_access_iterator<_CharT, ptrdiff_t> {
  826.     friend class rope<_CharT,_Alloc>;
  827.   public:
  828.     typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround
  829.     typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
  830.         // Borland doesnt want this to be protected.
  831.   protected:
  832.     enum { _S_path_cache_len = 4 }; // Must be <= 9.
  833.     enum { _S_iterator_buf_len = 15 };
  834.     size_t _M_current_pos;
  835.     _RopeRep* _M_root;     // The whole rope.
  836.     size_t _M_leaf_pos;    // Starting position for current leaf
  837.     __GC_CONST _CharT* _M_buf_start;
  838.                         // Buffer possibly
  839.                         // containing current char.
  840.     __GC_CONST _CharT* _M_buf_ptr;
  841.                         // Pointer to current char in buffer.
  842.                         // != 0 ==> buffer valid.
  843.     __GC_CONST _CharT* _M_buf_end;
  844.                         // One past __last valid char in buffer.
  845.     // What follows is the path cache.  We go out of our
  846.     // way to make this compact.
  847.     // Path_end contains the bottom section of the path from
  848.     // the root to the current leaf.
  849.     const _RopeRep* _M_path_end[_S_path_cache_len];
  850.     int _M_leaf_index;     // Last valid __pos in path_end;
  851.                         // _M_path_end[0] ... _M_path_end[leaf_index-1]
  852.                         // point to concatenation nodes.
  853.     unsigned char _M_path_directions;
  854.                           // (path_directions >> __i) & 1 is 1
  855.                           // iff we got from _M_path_end[leaf_index - __i - 1]
  856.                           // to _M_path_end[leaf_index - __i] by going to the
  857.                           // __right. Assumes path_cache_len <= 9.
  858.     _CharT _M_tmp_buf[_S_iterator_buf_len];
  859.                         // Short buffer for surrounding chars.
  860.                         // This is useful primarily for 
  861.                         // RopeFunctions.  We put the buffer
  862.                         // here to avoid locking in the
  863.                         // multithreaded case.
  864.     // The cached path is generally assumed to be valid
  865.     // only if the buffer is valid.
  866.     static void _S_setbuf(_Rope_iterator_base& __x);
  867.                                         // Set buffer contents given
  868.                                         // path cache.
  869.     static void _S_setcache(_Rope_iterator_base& __x);
  870.                                         // Set buffer contents and
  871.                                         // path cache.
  872.     static void _S_setcache_for_incr(_Rope_iterator_base& __x);
  873.                                         // As above, but assumes path
  874.                                         // cache is valid for previous posn.
  875.     _Rope_iterator_base() {}
  876.     _Rope_iterator_base(_RopeRep* __root, size_t __pos)
  877.       : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) {}
  878.     void _M_incr(size_t __n);
  879.     void _M_decr(size_t __n);
  880.   public:
  881.     size_t index() const { return _M_current_pos; }
  882.     _Rope_iterator_base(const _Rope_iterator_base& __x) {
  883.         if (0 != __x._M_buf_ptr) {
  884.             *this = __x;
  885.         } else {
  886.             _M_current_pos = __x._M_current_pos;
  887.             _M_root = __x._M_root;
  888.             _M_buf_ptr = 0;
  889.         }
  890.     }
  891. };
  892. template<class _CharT, class _Alloc> class _Rope_iterator;
  893. template<class _CharT, class _Alloc>
  894. class _Rope_const_iterator : public _Rope_iterator_base<_CharT,_Alloc> {
  895.     friend class rope<_CharT,_Alloc>;
  896.   protected:
  897. #   ifdef __STL_HAS_NAMESPACES
  898.       typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
  899.       // The one from the base class may not be directly visible.
  900. #   endif
  901.     _Rope_const_iterator(const _RopeRep* __root, size_t __pos):
  902.                    _Rope_iterator_base<_CharT,_Alloc>(
  903.                      const_cast<_RopeRep*>(__root), __pos)
  904.                    // Only nonconst iterators modify root ref count
  905.     {}
  906.   public:
  907.     typedef _CharT reference;   // Really a value.  Returning a reference
  908.                                 // Would be a mess, since it would have
  909.                                 // to be included in refcount.
  910.     typedef const _CharT* pointer;
  911.   public:
  912.     _Rope_const_iterator() {};
  913.     _Rope_const_iterator(const _Rope_const_iterator& __x) :
  914.                                 _Rope_iterator_base<_CharT,_Alloc>(__x) { }
  915.     _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
  916.     _Rope_const_iterator(const rope<_CharT,_Alloc>& __r, size_t __pos) :
  917.         _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) {}
  918.     _Rope_const_iterator& operator= (const _Rope_const_iterator& __x) {
  919.         if (0 != __x._M_buf_ptr) {
  920.             *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x;
  921.         } else {
  922.             _M_current_pos = __x._M_current_pos;
  923.             _M_root = __x._M_root;
  924.             _M_buf_ptr = 0;
  925.         }
  926.         return(*this);
  927.     }
  928.     reference operator*() {
  929.         if (0 == _M_buf_ptr) _S_setcache(*this);
  930.         return *_M_buf_ptr;
  931.     }
  932.     _Rope_const_iterator& operator++() {
  933.         __GC_CONST _CharT* __next;
  934.         if (0 != _M_buf_ptr && (__next = _M_buf_ptr + 1) < _M_buf_end) {
  935.             _M_buf_ptr = __next;
  936.             ++_M_current_pos;
  937.         } else {
  938.             _M_incr(1);
  939.         }
  940.         return *this;
  941.     }
  942.     _Rope_const_iterator& operator+=(ptrdiff_t __n) {
  943.         if (__n >= 0) {
  944.             _M_incr(__n);
  945.         } else {
  946.             _M_decr(-__n);
  947.         }
  948.         return *this;
  949.     }
  950.     _Rope_const_iterator& operator--() {
  951.         _M_decr(1);
  952.         return *this;
  953.     }
  954.     _Rope_const_iterator& operator-=(ptrdiff_t __n) {
  955.         if (__n >= 0) {
  956.             _M_decr(__n);
  957.         } else {
  958.             _M_incr(-__n);
  959.         }
  960.         return *this;
  961.     }
  962.     _Rope_const_iterator operator++(int) {
  963.         size_t __old_pos = _M_current_pos;
  964.         _M_incr(1);
  965.         return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos);
  966.         // This makes a subsequent dereference expensive.
  967.         // Perhaps we should instead copy the iterator
  968.         // if it has a valid cache?
  969.     }
  970.     _Rope_const_iterator operator--(int) {
  971.         size_t __old_pos = _M_current_pos;
  972.         _M_decr(1);
  973.         return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos);
  974.     }
  975. #if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
  976.     template<class _CharT2, class _Alloc2>
  977.     friend _Rope_const_iterator<_CharT2,_Alloc2> operator-
  978.         (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
  979.          ptrdiff_t __n);
  980.     template<class _CharT2, class _Alloc2>
  981.     friend _Rope_const_iterator<_CharT2,_Alloc2> operator+
  982.         (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
  983.          ptrdiff_t __n);
  984.     template<class _CharT2, class _Alloc2>
  985.     friend _Rope_const_iterator<_CharT2,_Alloc2> operator+
  986.         (ptrdiff_t __n,
  987.          const _Rope_const_iterator<_CharT2,_Alloc2>& __x);
  988. #else
  989.     friend _Rope_const_iterator<_CharT,_Alloc> operator- __STL_NULL_TMPL_ARGS
  990.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  991.          ptrdiff_t __n);
  992.     friend _Rope_const_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
  993.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  994.          ptrdiff_t __n);
  995.     friend _Rope_const_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
  996.         (ptrdiff_t __n,
  997.          const _Rope_const_iterator<_CharT,_Alloc>& __x);
  998. #endif
  999.     reference operator[](size_t __n) {
  1000.         return rope<_CharT,_Alloc>::_S_fetch(_M_root, _M_current_pos + __n);
  1001.     }
  1002. #if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
  1003.     template<class _CharT2, class _Alloc2>
  1004.     friend bool operator==
  1005.         (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
  1006.          const _Rope_const_iterator<_CharT2,_Alloc2>& __y);
  1007.     template<class _CharT2, class _Alloc2>
  1008.     friend bool operator< 
  1009.         (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
  1010.          const _Rope_const_iterator<_CharT2,_Alloc2>& __y);
  1011.     template<class _CharT2, class _Alloc2>
  1012.     friend ptrdiff_t operator-
  1013.         (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,
  1014.          const _Rope_const_iterator<_CharT2,_Alloc2>& __y);
  1015. #else
  1016.     friend bool operator== __STL_NULL_TMPL_ARGS
  1017.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  1018.          const _Rope_const_iterator<_CharT,_Alloc>& __y);
  1019.     friend bool operator< __STL_NULL_TMPL_ARGS
  1020.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  1021.          const _Rope_const_iterator<_CharT,_Alloc>& __y);
  1022.     friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
  1023.         (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  1024.          const _Rope_const_iterator<_CharT,_Alloc>& __y);
  1025. #endif
  1026. };
  1027. template<class _CharT, class _Alloc>
  1028. class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> {
  1029.     friend class rope<_CharT,_Alloc>;
  1030.   protected:
  1031.     rope<_CharT,_Alloc>* _M_root_rope;
  1032.         // root is treated as a cached version of this,
  1033.         // and is used to detect changes to the underlying
  1034.         // rope.
  1035.         // Root is included in the reference count.
  1036.         // This is necessary so that we can detect changes reliably.
  1037.         // Unfortunately, it requires careful bookkeeping for the
  1038.         // nonGC case.
  1039.     _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)
  1040.       : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr, __pos),
  1041.         _M_root_rope(__r) 
  1042.        { _RopeRep::_S_ref(_M_root); if (!(__r -> empty()))_S_setcache(*this); }
  1043.     void _M_check();
  1044.   public:
  1045.     typedef _Rope_char_ref_proxy<_CharT,_Alloc>  reference;
  1046.     typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer;
  1047.   public:
  1048.     rope<_CharT,_Alloc>& container() { return *_M_root_rope; }
  1049.     _Rope_iterator() {
  1050.         _M_root = 0;  // Needed for reference counting.
  1051.     };
  1052.     _Rope_iterator(const _Rope_iterator& __x) :
  1053.         _Rope_iterator_base<_CharT,_Alloc>(__x) {
  1054.         _M_root_rope = __x._M_root_rope;
  1055.         _RopeRep::_S_ref(_M_root);
  1056.     }
  1057.     _Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos);
  1058.     ~_Rope_iterator() {
  1059.         _RopeRep::_S_unref(_M_root);
  1060.     }
  1061.     _Rope_iterator& operator= (const _Rope_iterator& __x) {
  1062.         _RopeRep* __old = _M_root;
  1063.         _RopeRep::_S_ref(__x._M_root);
  1064.         if (0 != __x._M_buf_ptr) {
  1065.             _M_root_rope = __x._M_root_rope;
  1066.             *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x;
  1067.         } else {
  1068.             _M_current_pos = __x._M_current_pos;
  1069.             _M_root = __x._M_root;
  1070.             _M_root_rope = __x._M_root_rope;
  1071.             _M_buf_ptr = 0;
  1072.         }
  1073.         _RopeRep::_S_unref(__old);
  1074.         return(*this);
  1075.     }
  1076.     reference operator*() {
  1077.         _M_check();
  1078.         if (0 == _M_buf_ptr) {
  1079.             return _Rope_char_ref_proxy<_CharT,_Alloc>(
  1080.                _M_root_rope, _M_current_pos);
  1081.         } else {
  1082.             return _Rope_char_ref_proxy<_CharT,_Alloc>(
  1083.                _M_root_rope, _M_current_pos, *_M_buf_ptr);
  1084.         }
  1085.     }
  1086.     _Rope_iterator& operator++() {
  1087.         _M_incr(1);
  1088.         return *this;
  1089.     }
  1090.     _Rope_iterator& operator+=(ptrdiff_t __n) {
  1091.         if (__n >= 0) {
  1092.             _M_incr(__n);
  1093.         } else {
  1094.             _M_decr(-__n);
  1095.         }
  1096.         return *this;
  1097.     }
  1098.     _Rope_iterator& operator--() {
  1099.         _M_decr(1);
  1100.         return *this;
  1101.     }
  1102.     _Rope_iterator& operator-=(ptrdiff_t __n) {
  1103.         if (__n >= 0) {
  1104.             _M_decr(__n);
  1105.         } else {
  1106.             _M_incr(-__n);
  1107.         }
  1108.         return *this;
  1109.     }
  1110.     _Rope_iterator operator++(int) {
  1111.         size_t __old_pos = _M_current_pos;
  1112.         _M_incr(1);
  1113.         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
  1114.     }
  1115.     _Rope_iterator operator--(int) {
  1116.         size_t __old_pos = _M_current_pos;
  1117.         _M_decr(1);
  1118.         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
  1119.     }
  1120.     reference operator[](ptrdiff_t __n) {
  1121.         return _Rope_char_ref_proxy<_CharT,_Alloc>(
  1122.           _M_root_rope, _M_current_pos + __n);
  1123.     }
  1124. #if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
  1125.     template<class _CharT2, class _Alloc2>
  1126.     friend bool operator==
  1127.         (const _Rope_iterator<_CharT2,_Alloc2>& __x,
  1128.          const _Rope_iterator<_CharT2,_Alloc2>& __y);
  1129.     template<class _CharT2, class _Alloc2>
  1130.     friend bool operator<
  1131.         (const _Rope_iterator<_CharT2,_Alloc2>& __x,
  1132.          const _Rope_iterator<_CharT2,_Alloc2>& __y);
  1133.     template<class _CharT2, class _Alloc2>
  1134.     friend ptrdiff_t operator-
  1135.         (const _Rope_iterator<_CharT2,_Alloc2>& __x,
  1136.          const _Rope_iterator<_CharT2,_Alloc2>& __y);
  1137.     template<class _CharT2, class _Alloc2>
  1138.     friend _Rope_iterator<_CharT2,_Alloc2> operator-
  1139.         (const _Rope_iterator<_CharT2,_Alloc2>& __x,
  1140.          ptrdiff_t __n);
  1141.     template<class _CharT2, class _Alloc2>
  1142.     friend _Rope_iterator<_CharT2,_Alloc2> operator+
  1143.         (const _Rope_iterator<_CharT2,_Alloc2>& __x,
  1144.          ptrdiff_t __n);
  1145.     template<class _CharT2, class _Alloc2>
  1146.     friend _Rope_iterator<_CharT2,_Alloc2> operator+
  1147.         (ptrdiff_t __n,
  1148.          const _Rope_iterator<_CharT2,_Alloc2>& __x);
  1149. #else
  1150.     friend bool operator== __STL_NULL_TMPL_ARGS
  1151.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  1152.          const _Rope_iterator<_CharT,_Alloc>& __y);
  1153.     friend bool operator< __STL_NULL_TMPL_ARGS
  1154.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  1155.          const _Rope_iterator<_CharT,_Alloc>& __y);
  1156.     friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
  1157.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  1158.          const _Rope_iterator<_CharT,_Alloc>& __y);
  1159.     friend _Rope_iterator<_CharT,_Alloc> operator- __STL_NULL_TMPL_ARGS
  1160.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  1161.          ptrdiff_t __n);
  1162.     friend _Rope_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
  1163.         (const _Rope_iterator<_CharT,_Alloc>& __x,
  1164.          ptrdiff_t __n);
  1165.     friend _Rope_iterator<_CharT,_Alloc> operator+ __STL_NULL_TMPL_ARGS
  1166.         (ptrdiff_t __n,
  1167.          const _Rope_iterator<_CharT,_Alloc>& __x);
  1168. #endif
  1169. };
  1170. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  1171. #pragma reset woff 1375
  1172. #endif
  1173. //  The rope base class encapsulates
  1174. //  the differences between SGI-style allocators and standard-conforming
  1175. //  allocators.
  1176. #ifdef __STL_USE_STD_ALLOCATORS
  1177. // Base class for ordinary allocators.
  1178. template <class _CharT, class _Allocator, bool _IsStatic>
  1179. class _Rope_alloc_base {
  1180. public:
  1181.   typedef _Rope_RopeRep<_CharT,_Allocator> _RopeRep;
  1182.   typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
  1183.           allocator_type;
  1184.   allocator_type get_allocator() const { return _M_data_allocator; }
  1185.   _Rope_alloc_base(_RopeRep *__t, const allocator_type& __a)
  1186.         : _M_tree_ptr(__t), _M_data_allocator(__a) {}
  1187.   _Rope_alloc_base(const allocator_type& __a)
  1188.         : _M_data_allocator(__a) {}
  1189.   
  1190. protected:
  1191.   // The only data members of a rope:
  1192.     allocator_type _M_data_allocator;
  1193.     _RopeRep* _M_tree_ptr;
  1194. # define __ROPE_DEFINE_ALLOC(_Tp, __name) 
  1195.         typedef typename 
  1196.           _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; 
  1197.         _Tp* __name##_allocate(size_t __n) const 
  1198.           { return __name##Allocator(_M_data_allocator).allocate(__n); } 
  1199.         void __name##_deallocate(_Tp *__p, size_t __n) const 
  1200.                 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
  1201.   __ROPE_DEFINE_ALLOCS(_Allocator)
  1202. # undef __ROPE_DEFINE_ALLOC
  1203. };
  1204. // Specialization for allocators that have the property that we don't
  1205. //  actually have to store an allocator object.  
  1206. template <class _CharT, class _Allocator>
  1207. class _Rope_alloc_base<_CharT,_Allocator,true> {
  1208. public:
  1209.   typedef _Rope_RopeRep<_CharT,_Allocator> _RopeRep;
  1210.   typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
  1211.           allocator_type;
  1212.   allocator_type get_allocator() const { return allocator_type(); }
  1213.   _Rope_alloc_base(_RopeRep *__t, const allocator_type&)
  1214.                 : _M_tree_ptr(__t) {}
  1215.   _Rope_alloc_base(const allocator_type&) {}
  1216.   
  1217. protected:
  1218.   // The only data member of a rope:
  1219.     _RopeRep *_M_tree_ptr;
  1220. # define __ROPE_DEFINE_ALLOC(_Tp, __name) 
  1221.         typedef typename 
  1222.           _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; 
  1223.         typedef typename 
  1224.           _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; 
  1225.         static _Tp* __name##_allocate(size_t __n) 
  1226.           { return __name##Alloc::allocate(__n); } 
  1227.         static void __name##_deallocate(_Tp *__p, size_t __n) 
  1228.           { __name##Alloc::deallocate(__p, __n); }
  1229.   __ROPE_DEFINE_ALLOCS(_Allocator)
  1230. # undef __ROPE_DEFINE_ALLOC
  1231. };
  1232. template <class _CharT, class _Alloc>
  1233. struct _Rope_base 
  1234.   : public _Rope_alloc_base<_CharT,_Alloc,
  1235.                             _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
  1236. {
  1237.   typedef _Rope_alloc_base<_CharT,_Alloc,
  1238.                             _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
  1239.           _Base;
  1240.   typedef typename _Base::allocator_type allocator_type;
  1241.   typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
  1242.         // The one in _Base may not be visible due to template rules.
  1243.   _Rope_base(_RopeRep* __t, const allocator_type& __a) : _Base(__t, __a) {}
  1244.   _Rope_base(const allocator_type& __a) : _Base(__a) {}
  1245. };    
  1246. #else /* !__STL_USE_STD_ALLOCATORS */
  1247. template <class _CharT, class _Alloc> 
  1248. class _Rope_base {
  1249. public:
  1250.   typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  1251.   typedef _Alloc allocator_type;
  1252.   static allocator_type get_allocator() { return allocator_type(); }
  1253.   _Rope_base(_RopeRep * __t, const allocator_type&) : _M_tree_ptr(__t) {}
  1254.   _Rope_base(const allocator_type&) {}
  1255. protected:
  1256.   // The only data member of a rope:
  1257.     _RopeRep* _M_tree_ptr;
  1258. # define __ROPE_DEFINE_ALLOC(_Tp, __name) 
  1259.         typedef simple_alloc<_Tp, _Alloc> __name##Alloc; 
  1260.         static _Tp* __name##_allocate(size_t __n) 
  1261.                 { return __name##Alloc::allocate(__n); } 
  1262.         static void __name##_deallocate(_Tp *__p, size_t __n) 
  1263.                 { __name##Alloc::deallocate(__p, __n); }
  1264.   __ROPE_DEFINE_ALLOCS(_Alloc)
  1265. # undef __ROPE_DEFINE_ALLOC
  1266. };
  1267. #endif /* __STL_USE_STD_ALLOCATORS */
  1268. template <class _CharT, class _Alloc>
  1269. class rope : public _Rope_base<_CharT,_Alloc> {
  1270.     public:
  1271.         typedef _CharT value_type;
  1272.         typedef ptrdiff_t difference_type;
  1273.         typedef size_t size_type;
  1274.         typedef _CharT const_reference;
  1275.         typedef const _CharT* const_pointer;
  1276.         typedef _Rope_iterator<_CharT,_Alloc> iterator;
  1277.         typedef _Rope_const_iterator<_CharT,_Alloc> const_iterator;
  1278.         typedef _Rope_char_ref_proxy<_CharT,_Alloc> reference;
  1279.         typedef _Rope_char_ptr_proxy<_CharT,_Alloc> pointer;
  1280.         friend class _Rope_iterator<_CharT,_Alloc>;
  1281.         friend class _Rope_const_iterator<_CharT,_Alloc>;
  1282.         friend struct _Rope_RopeRep<_CharT,_Alloc>;
  1283.         friend class _Rope_iterator_base<_CharT,_Alloc>;
  1284.         friend class _Rope_char_ptr_proxy<_CharT,_Alloc>;
  1285.         friend class _Rope_char_ref_proxy<_CharT,_Alloc>;
  1286.         friend struct _Rope_RopeSubstring<_CharT,_Alloc>;
  1287.     protected:
  1288.         typedef _Rope_base<_CharT,_Alloc> _Base;
  1289.         typedef typename _Base::allocator_type allocator_type;
  1290. #       ifdef __STL_USE_NAMESPACES
  1291.           using _Base::_M_tree_ptr;
  1292. #       endif
  1293.         typedef __GC_CONST _CharT* _Cstrptr;
  1294.         static _CharT _S_empty_c_str[1];
  1295.         static bool _S_is0(_CharT __c) { return __c == _S_eos((_CharT*)0); }
  1296.         enum { _S_copy_max = 23 };
  1297.                 // For strings shorter than _S_copy_max, we copy to
  1298.                 // concatenate.
  1299.         typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
  1300.         typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
  1301.         typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
  1302.         typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
  1303.         typedef _Rope_RopeSubstring<_CharT,_Alloc> _RopeSubstring;
  1304.         // Retrieve a character at the indicated position.
  1305.         static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
  1306. #       ifndef __GC
  1307.             // Obtain a pointer to the character at the indicated position.
  1308.             // The pointer can be used to change the character.
  1309.             // If such a pointer cannot be produced, as is frequently the
  1310.             // case, 0 is returned instead.
  1311.             // (Returns nonzero only if all nodes in the path have a refcount
  1312.             // of 1.)
  1313.             static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
  1314. #       endif
  1315.         static bool _S_apply_to_pieces(
  1316.                                 // should be template parameter
  1317.                                 _Rope_char_consumer<_CharT>& __c,
  1318.                                 const _RopeRep* __r,
  1319.                                 size_t __begin, size_t __end);
  1320.                                 // begin and end are assumed to be in range.
  1321. #       ifndef __GC
  1322.           static void _S_unref(_RopeRep* __t)
  1323.           {
  1324.               _RopeRep::_S_unref(__t);
  1325.           }
  1326.           static void _S_ref(_RopeRep* __t)
  1327.           {
  1328.               _RopeRep::_S_ref(__t);
  1329.           }
  1330. #       else /* __GC */
  1331.           static void _S_unref(_RopeRep*) {}
  1332.           static void _S_ref(_RopeRep*) {}
  1333. #       endif
  1334. #       ifdef __GC
  1335.             typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr;
  1336. #       else
  1337.             typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;
  1338. #       endif
  1339.         // _Result is counted in refcount.
  1340.         static _RopeRep* _S_substring(_RopeRep* __base,
  1341.                                     size_t __start, size_t __endp1);
  1342.         static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
  1343.                                           const _CharT* __iter, size_t __slen);
  1344.                 // Concatenate rope and char ptr, copying __s.
  1345.                 // Should really take an arbitrary iterator.
  1346.                 // Result is counted in refcount.
  1347.         static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
  1348.                                           const _CharT* __iter, size_t __slen)
  1349.                 // As above, but one reference to __r is about to be
  1350.                 // destroyed.  Thus the pieces may be recycled if all
  1351.                 // relevent reference counts are 1.
  1352. #           ifdef __GC
  1353.                 // We can't really do anything since refcounts are unavailable.
  1354.                 { return _S_concat_char_iter(__r, __iter, __slen); }
  1355. #           else
  1356.                 ;
  1357. #           endif
  1358.         static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
  1359.                 // General concatenation on _RopeRep.  _Result
  1360.                 // has refcount of 1.  Adjusts argument refcounts.
  1361.    public:
  1362.         void apply_to_pieces( size_t __begin, size_t __end,
  1363.                               _Rope_char_consumer<_CharT>& __c) const {
  1364.             _S_apply_to_pieces(__c, _M_tree_ptr, __begin, __end);
  1365.         }
  1366.    protected:
  1367.         static size_t _S_rounded_up_size(size_t __n) {
  1368.             return _RopeLeaf::_S_rounded_up_size(__n);
  1369.         }
  1370.         static size_t _S_allocated_capacity(size_t __n) {
  1371.             if (_S_is_basic_char_type((_CharT*)0)) {
  1372.                 return _S_rounded_up_size(__n) - 1;
  1373.             } else {
  1374.                 return _S_rounded_up_size(__n);
  1375.             }
  1376.         }
  1377.                 
  1378.         // Allocate and construct a RopeLeaf using the supplied allocator
  1379.         // Takes ownership of s instead of copying.
  1380.         static _RopeLeaf* _S_new_RopeLeaf(__GC_CONST _CharT *__s,
  1381.                                           size_t __size, allocator_type __a)
  1382.         {
  1383. #           ifdef __STL_USE_STD_ALLOCATORS
  1384.               _RopeLeaf* __space = _LAllocator(__a).allocate(1);
  1385. #           else
  1386.               _RopeLeaf* __space = _L_allocate(1);
  1387. #           endif
  1388.             return new(__space) _RopeLeaf(__s, __size, __a);
  1389.         }
  1390.         static _RopeConcatenation* _S_new_RopeConcatenation(
  1391.                         _RopeRep* __left, _RopeRep* __right,
  1392.                         allocator_type __a)
  1393.         {
  1394. #           ifdef __STL_USE_STD_ALLOCATORS
  1395.               _RopeConcatenation* __space = _CAllocator(__a).allocate(1);
  1396. #           else
  1397.               _RopeConcatenation* __space = _C_allocate(1);
  1398. #           endif
  1399.             return new(__space) _RopeConcatenation(__left, __right, __a);
  1400.         }
  1401.         static _RopeFunction* _S_new_RopeFunction(char_producer<_CharT>* __f,
  1402.                 size_t __size, bool __d, allocator_type __a)
  1403.         {
  1404. #           ifdef __STL_USE_STD_ALLOCATORS
  1405.               _RopeFunction* __space = _FAllocator(__a).allocate(1);
  1406. #           else
  1407.               _RopeFunction* __space = _F_allocate(1);
  1408. #           endif
  1409.             return new(__space) _RopeFunction(__f, __size, __d, __a);
  1410.         }
  1411.         static _RopeSubstring* _S_new_RopeSubstring(
  1412.                 _Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
  1413.                 size_t __l, allocator_type __a)
  1414.         {
  1415. #           ifdef __STL_USE_STD_ALLOCATORS
  1416.               _RopeSubstring* __space = _SAllocator(__a).allocate(1);
  1417. #           else
  1418.               _RopeSubstring* __space = _S_allocate(1);
  1419. #           endif
  1420.             return new(__space) _RopeSubstring(__b, __s, __l, __a);
  1421.         }
  1422. #       ifdef __STL_USE_STD_ALLOCATORS
  1423.           static
  1424.           _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
  1425.                        size_t __size, allocator_type __a)
  1426. #         define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) 
  1427.                 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)     
  1428. #       else
  1429.           static
  1430.           _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr2(const _CharT* __s,
  1431.                                                         size_t __size)
  1432. #         define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) 
  1433.                _S_RopeLeaf_from_unowned_char_ptr2(__s, __size)
  1434. #       endif
  1435.         {
  1436.             if (0 == __size) return 0;
  1437. #           ifdef __STL_USE_STD_ALLOCATORS
  1438.               _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
  1439. #           else
  1440.               _CharT* __buf = _Data_allocate(_S_rounded_up_size(__size));
  1441.               allocator_type __a = allocator_type();
  1442. #           endif
  1443.             uninitialized_copy_n(__s, __size, __buf);
  1444.             _S_cond_store_eos(__buf[__size]);
  1445.             __STL_TRY {
  1446.               return _S_new_RopeLeaf(__buf, __size, __a);
  1447.             }
  1448.             __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__buf, __size, __a))
  1449.         }
  1450.             
  1451.         // Concatenation of nonempty strings.
  1452.         // Always builds a concatenation node.
  1453.         // Rebalances if the result is too deep.
  1454.         // Result has refcount 1.
  1455.         // Does not increment left and right ref counts even though
  1456.         // they are referenced.
  1457.         static _RopeRep*
  1458.         _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
  1459.         // Concatenation helper functions
  1460.         static _RopeLeaf*
  1461.         _S_leaf_concat_char_iter(_RopeLeaf* __r,
  1462.                                  const _CharT* __iter, size_t __slen);
  1463.                 // Concatenate by copying leaf.
  1464.                 // should take an arbitrary iterator
  1465.                 // result has refcount 1.
  1466. #       ifndef __GC
  1467.           static _RopeLeaf* _S_destr_leaf_concat_char_iter
  1468.                         (_RopeLeaf* __r, const _CharT* __iter, size_t __slen);
  1469.           // A version that potentially clobbers __r if __r->_M_ref_count == 1.
  1470. #       endif
  1471.         private:
  1472.         static size_t _S_char_ptr_len(const _CharT* __s);
  1473.                         // slightly generalized strlen
  1474.         rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
  1475.           : _Base(__t,__a) { }
  1476.         // Copy __r to the _CharT buffer.
  1477.         // Returns __buffer + __r->_M_size.
  1478.         // Assumes that buffer is uninitialized.
  1479.         static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
  1480.         // Again, with explicit starting position and length.
  1481.         // Assumes that buffer is uninitialized.
  1482.         static _CharT* _S_flatten(_RopeRep* __r,
  1483.                                   size_t __start, size_t __len,
  1484.                                   _CharT* __buffer);
  1485.         static const unsigned long 
  1486.           _S_min_len[_RopeRep::_S_max_rope_depth + 1];
  1487.         static bool _S_is_balanced(_RopeRep* __r)
  1488.                 { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
  1489.         static bool _S_is_almost_balanced(_RopeRep* __r)
  1490.                 { return (__r->_M_depth == 0 ||
  1491.                           __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
  1492.         static bool _S_is_roughly_balanced(_RopeRep* __r)
  1493.                 { return (__r->_M_depth <= 1 ||
  1494.                           __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
  1495.         // Assumes the result is not empty.
  1496.         static _RopeRep* _S_concat_and_set_balanced(_RopeRep* __left,
  1497.                                                      _RopeRep* __right)
  1498.         {
  1499.             _RopeRep* __result = _S_concat(__left, __right);
  1500.             if (_S_is_balanced(__result)) __result->_M_is_balanced = true;
  1501.             return __result;
  1502.         }
  1503.         // The basic rebalancing operation.  Logically copies the
  1504.         // rope.  The result has refcount of 1.  The client will
  1505.         // usually decrement the reference count of __r.
  1506.         // The result is within height 2 of balanced by the above
  1507.         // definition.
  1508.         static _RopeRep* _S_balance(_RopeRep* __r);
  1509.         // Add all unbalanced subtrees to the forest of balanceed trees.
  1510.         // Used only by balance.
  1511.         static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
  1512.         
  1513.         // Add __r to forest, assuming __r is already balanced.
  1514.         static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
  1515.         // Print to stdout, exposing structure
  1516.         static void _S_dump(_RopeRep* __r, int __indent = 0);
  1517.         // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
  1518.         static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
  1519.    public:
  1520.         bool empty() const { return 0 == _M_tree_ptr; }
  1521.         // Comparison member function.  This is public only for those
  1522.         // clients that need a ternary comparison.  Others
  1523.         // should use the comparison operators below.
  1524.         int compare(const rope& __y) const {
  1525.             return _S_compare(_M_tree_ptr, __y._M_tree_ptr);
  1526.         }
  1527.         rope(const _CharT* __s, const allocator_type& __a = allocator_type())
  1528.         : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
  1529.                                                  __a),__a)
  1530.         { }
  1531.         rope(const _CharT* __s, size_t __len,
  1532.              const allocator_type& __a = allocator_type())
  1533.         : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, __a), __a)
  1534.         { }
  1535.         // Should perhaps be templatized with respect to the iterator type
  1536.         // and use Sequence_buffer.  (It should perhaps use sequence_buffer
  1537.         // even now.)
  1538.         rope(const _CharT *__s, const _CharT *__e,
  1539.              const allocator_type& __a = allocator_type())
  1540.         : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, __a), __a)
  1541.         { }
  1542.         rope(const const_iterator& __s, const const_iterator& __e,
  1543.              const allocator_type& __a = allocator_type())
  1544.         : _Base(_S_substring(__s._M_root, __s._M_current_pos,
  1545.                              __e._M_current_pos), __a)
  1546.         { }
  1547.         rope(const iterator& __s, const iterator& __e,
  1548.              const allocator_type& __a = allocator_type())
  1549.         : _Base(_S_substring(__s._M_root, __s._M_current_pos,
  1550.                              __e._M_current_pos), __a)
  1551.         { }
  1552.         rope(_CharT __c, const allocator_type& __a = allocator_type())
  1553.         : _Base(__a)
  1554.         {
  1555.             _CharT* __buf = _Data_allocate(_S_rounded_up_size(1));
  1556.             construct(__buf, __c);
  1557.             __STL_TRY {
  1558.                 _M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a);
  1559.             }
  1560.             __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__buf, 1, __a))
  1561.         }
  1562.         rope(size_t __n, _CharT __c,
  1563.              const allocator_type& __a = allocator_type());
  1564.         rope(const allocator_type& __a = allocator_type())
  1565.         : _Base(0, __a) {}
  1566.         // Construct a rope from a function that can compute its members
  1567.         rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
  1568.              const allocator_type& __a = allocator_type())
  1569.             : _Base(__a)
  1570.         {
  1571.             _M_tree_ptr = (0 == __len) ?
  1572.                0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
  1573.         }
  1574.         rope(const rope& __x, const allocator_type& __a = allocator_type())
  1575.         : _Base(__x._M_tree_ptr, __a)
  1576.         {
  1577.             _S_ref(_M_tree_ptr);
  1578.         }
  1579.         ~rope()
  1580.         {
  1581.             _S_unref(_M_tree_ptr);
  1582.         }
  1583.         rope& operator=(const rope& __x)
  1584.         {
  1585.             _RopeRep* __old = _M_tree_ptr;
  1586. #           ifdef __STL_USE_STD_ALLOCATORS
  1587.               __stl_assert(get_allocator() == __x.get_allocator());
  1588. #           endif
  1589.             _M_tree_ptr = __x._M_tree_ptr;
  1590.             _S_ref(_M_tree_ptr);
  1591.             _S_unref(__old);
  1592.             return(*this);
  1593.         }
  1594.         void clear()
  1595.         {
  1596.             _S_unref(_M_tree_ptr);
  1597.             _M_tree_ptr = 0;
  1598.         }
  1599.         void push_back(_CharT __x)
  1600.         {
  1601.             _RopeRep* __old = _M_tree_ptr;
  1602.             _M_tree_ptr = _S_destr_concat_char_iter(_M_tree_ptr, &__x, 1);
  1603.             _S_unref(__old);
  1604.         }
  1605.         void pop_back()
  1606.         {
  1607.             _RopeRep* __old = _M_tree_ptr;
  1608.             _M_tree_ptr = 
  1609.               _S_substring(_M_tree_ptr, 0, _M_tree_ptr->_M_size - 1);
  1610.             _S_unref(__old);
  1611.         }
  1612.         _CharT back() const
  1613.         {
  1614.             return _S_fetch(_M_tree_ptr, _M_tree_ptr->_M_size - 1);
  1615.         }
  1616.         void push_front(_CharT __x)
  1617.         {
  1618.             _RopeRep* __old = _M_tree_ptr;
  1619.             _RopeRep* __left =
  1620.               __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, get_allocator());
  1621.             __STL_TRY {
  1622.               _M_tree_ptr = _S_concat(__left, _M_tree_ptr);
  1623.               _S_unref(__old);
  1624.               _S_unref(__left);
  1625.             }
  1626.             __STL_UNWIND(_S_unref(__left))
  1627.         }
  1628.         void pop_front()
  1629.         {
  1630.             _RopeRep* __old = _M_tree_ptr;
  1631.             _M_tree_ptr = _S_substring(_M_tree_ptr, 1, _M_tree_ptr->_M_size);
  1632.             _S_unref(__old);
  1633.         }
  1634.         _CharT front() const
  1635.         {
  1636.             return _S_fetch(_M_tree_ptr, 0);
  1637.         }
  1638.         void balance()
  1639.         {
  1640.             _RopeRep* __old = _M_tree_ptr;
  1641.             _M_tree_ptr = _S_balance(_M_tree_ptr);
  1642.             _S_unref(__old);
  1643.         }
  1644.         void copy(_CharT* __buffer) const {
  1645.             destroy(__buffer, __buffer + size());
  1646.             _S_flatten(_M_tree_ptr, __buffer);
  1647.         }
  1648.         // This is the copy function from the standard, but
  1649.         // with the arguments reordered to make it consistent with the
  1650.         // rest of the interface.
  1651.         // Note that this guaranteed not to compile if the draft standard
  1652.         // order is assumed.
  1653.         size_type copy(size_type __pos, size_type __n, _CharT* __buffer) const 
  1654.         {
  1655.             size_t __size = size();
  1656.             size_t __len = (__pos + __n > __size? __size - __pos : __n);
  1657.             destroy(__buffer, __buffer + __len);
  1658.             _S_flatten(_M_tree_ptr, __pos, __len, __buffer);
  1659.             return __len;
  1660.         }
  1661.         // Print to stdout, exposing structure.  May be useful for
  1662.         // performance debugging.
  1663.         void dump() {
  1664.             _S_dump(_M_tree_ptr);
  1665.         }
  1666.         // Convert to 0 terminated string in new allocated memory.
  1667.         // Embedded 0s in the input do not terminate the copy.
  1668.         const _CharT* c_str() const;
  1669.         // As above, but lso use the flattened representation as the
  1670.         // the new rope representation.
  1671.         const _CharT* replace_with_c_str();
  1672.         // Reclaim memory for the c_str generated flattened string.
  1673.         // Intentionally undocumented, since it's hard to say when this
  1674.         // is safe for multiple threads.
  1675.         void delete_c_str () {
  1676.             if (0 == _M_tree_ptr) return;
  1677.             if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && 
  1678.                 ((_RopeLeaf*)_M_tree_ptr)->_M_data == 
  1679.                       _M_tree_ptr->_M_c_string) {
  1680.                 // Representation shared
  1681.                 return;
  1682.             }
  1683. #           ifndef __GC
  1684.               _M_tree_ptr->_M_free_c_string();
  1685. #           endif
  1686.             _M_tree_ptr->_M_c_string = 0;
  1687.         }
  1688.         _CharT operator[] (size_type __pos) const {
  1689.             return _S_fetch(_M_tree_ptr, __pos);
  1690.         }
  1691.         _CharT at(size_type __pos) const {
  1692.            // if (__pos >= size()) throw out_of_range;  // XXX
  1693.            return (*this)[__pos];
  1694.         }
  1695.         const_iterator begin() const {
  1696.             return(const_iterator(_M_tree_ptr, 0));
  1697.         }
  1698.         // An easy way to get a const iterator from a non-const container.
  1699.         const_iterator const_begin() const {
  1700.             return(const_iterator(_M_tree_ptr, 0));
  1701.         }
  1702.         const_iterator end() const {
  1703.             return(const_iterator(_M_tree_ptr, size()));
  1704.         }
  1705.         const_iterator const_end() const {
  1706.             return(const_iterator(_M_tree_ptr, size()));
  1707.         }
  1708.         size_type size() const { 
  1709.             return(0 == _M_tree_ptr? 0 : _M_tree_ptr->_M_size);
  1710.         }
  1711.         size_type length() const {
  1712.             return size();
  1713.         }
  1714.         size_type max_size() const {
  1715.             return _S_min_len[_RopeRep::_S_max_rope_depth-1] - 1;
  1716.             //  Guarantees that the result can be sufficirntly
  1717.             //  balanced.  Longer ropes will probably still work,
  1718.             //  but it's harder to make guarantees.
  1719.         }
  1720. #     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  1721.         typedef reverse_iterator<const_iterator> const_reverse_iterator;
  1722. #     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  1723.         typedef reverse_iterator<const_iterator, value_type, const_reference,
  1724.                                  difference_type>  const_reverse_iterator;
  1725. #     endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  1726.         const_reverse_iterator rbegin() const {
  1727.             return const_reverse_iterator(end());
  1728.         }
  1729.         const_reverse_iterator const_rbegin() const {
  1730.             return const_reverse_iterator(end());
  1731.         }
  1732.         const_reverse_iterator rend() const {
  1733.             return const_reverse_iterator(begin());
  1734.         }
  1735.         const_reverse_iterator const_rend() const {
  1736.             return const_reverse_iterator(begin());
  1737.         }
  1738. #if defined(__STL_MEMBER_TEMPLATES) && defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
  1739.         template<class _CharT2, class _Alloc2>
  1740.         friend rope<_CharT2,_Alloc2>
  1741.         operator+ (const rope<_CharT2,_Alloc2>& __left,
  1742.                    const rope<_CharT2,_Alloc2>& __right);
  1743.         
  1744.         template<class _CharT2, class _Alloc2>
  1745.         friend rope<_CharT2,_Alloc2>
  1746.         operator+ (const rope<_CharT2,_Alloc2>& __left,
  1747.                    const _CharT2* __right);
  1748.         
  1749.         template<class _CharT2, class _Alloc2>
  1750.         friend rope<_CharT2,_Alloc2>
  1751.         operator+ (const rope<_CharT2,_Alloc2>& __left, _CharT2 __right);
  1752. #else
  1753.         friend rope<_CharT,_Alloc> __STD_QUALIFIER
  1754.         operator+ __STL_NULL_TMPL_ARGS (const rope<_CharT,_Alloc>& __left,
  1755.                                         const rope<_CharT,_Alloc>& __right);
  1756.         
  1757.         friend rope<_CharT,_Alloc> __STD_QUALIFIER
  1758.         operator+ __STL_NULL_TMPL_ARGS (const rope<_CharT,_Alloc>& __left,
  1759.                                         const _CharT* __right);
  1760.         
  1761.         friend rope<_CharT,_Alloc> __STD_QUALIFIER
  1762.         operator+ __STL_NULL_TMPL_ARGS (const rope<_CharT,_Alloc>& __left,
  1763.                                         _CharT __right);
  1764. #endif        
  1765.         // The symmetric cases are intentionally omitted, since they're presumed
  1766.         // to be less common, and we don't handle them as well.
  1767.         // The following should really be templatized.
  1768.         // The first argument should be an input iterator or
  1769.         // forward iterator with value_type _CharT.
  1770.         rope& append(const _CharT* __iter, size_t __n) {
  1771.             _RopeRep* __result = 
  1772.               _S_destr_concat_char_iter(_M_tree_ptr, __iter, __n);
  1773.             _S_unref(_M_tree_ptr);
  1774.             _M_tree_ptr = __result;
  1775.             return *this;
  1776.         }
  1777.         rope& append(const _CharT* __c_string) {
  1778.             size_t __len = _S_char_ptr_len(__c_string);
  1779.             append(__c_string, __len);
  1780.             return(*this);
  1781.         }
  1782.         rope& append(const _CharT* __s, const _CharT* __e) {
  1783.             _RopeRep* __result =
  1784.                 _S_destr_concat_char_iter(_M_tree_ptr, __s, __e - __s);
  1785.             _S_unref(_M_tree_ptr);
  1786.             _M_tree_ptr = __result;
  1787.             return *this;
  1788.         }
  1789.         rope& append(const_iterator __s, const_iterator __e) {
  1790.             __stl_assert(__s._M_root == __e._M_root);
  1791. #           ifdef __STL_USE_STD_ALLOCATORS
  1792.                 __stl_assert(get_allocator() == __s._M_root->get_allocator());
  1793. #           endif
  1794.             _Self_destruct_ptr __appendee(_S_substring(
  1795.               __s._M_root, __s._M_current_pos, __e._M_current_pos));
  1796.             _RopeRep* __result = 
  1797.               _S_concat(_M_tree_ptr, (_RopeRep*)__appendee);
  1798.             _S_unref(_M_tree_ptr);
  1799.             _M_tree_ptr = __result;
  1800.             return *this;
  1801.         }
  1802.         rope& append(_CharT __c) {
  1803.             _RopeRep* __result = 
  1804.               _S_destr_concat_char_iter(_M_tree_ptr, &__c, 1);
  1805.             _S_unref(_M_tree_ptr);
  1806.             _M_tree_ptr = __result;
  1807.             return *this;
  1808.         }
  1809.         rope& append() { return append(_CharT()); }  // XXX why?
  1810.         rope& append(const rope& __y) {
  1811. #           ifdef __STL_USE_STD_ALLOCATORS
  1812.               __stl_assert(__y.get_allocator() == get_allocator());
  1813. #           endif
  1814.             _RopeRep* __result = _S_concat(_M_tree_ptr, __y._M_tree_ptr);
  1815.             _S_unref(_M_tree_ptr);
  1816.             _M_tree_ptr = __result;
  1817.             return *this;
  1818.         }
  1819.         rope& append(size_t __n, _CharT __c) {
  1820.             rope<_CharT,_Alloc> __last(__n, __c);
  1821.             return append(__last);
  1822.         }
  1823.         void swap(rope& __b) {
  1824. #           ifdef __STL_USE_STD_ALLOCATORS
  1825.                 __stl_assert(get_allocator() == __b.get_allocator());
  1826. #           endif
  1827.             _RopeRep* __tmp = _M_tree_ptr;
  1828.             _M_tree_ptr = __b._M_tree_ptr;
  1829.             __b._M_tree_ptr = __tmp;
  1830.         }
  1831.     protected:
  1832.         // Result is included in refcount.
  1833.         static _RopeRep* replace(_RopeRep* __old, size_t __pos1,
  1834.                                   size_t __pos2, _RopeRep* __r) {
  1835.             if (0 == __old) { _S_ref(__r); return __r; }
  1836.             _Self_destruct_ptr __left(
  1837.               _S_substring(__old, 0, __pos1));
  1838.             _Self_destruct_ptr __right(
  1839.               _S_substring(__old, __pos2, __old->_M_size));
  1840.             _RopeRep* __result;
  1841. #           ifdef __STL_USE_STD_ALLOCATORS
  1842.                 __stl_assert(__old->get_allocator() == __r->get_allocator());
  1843. #           endif
  1844.             if (0 == __r) {
  1845.                 __result = _S_concat(__left, __right);
  1846.             } else {
  1847.                 _Self_destruct_ptr __left_result(_S_concat(__left, __r));
  1848.                 __result = _S_concat(__left_result, __right);
  1849.             }
  1850.             return __result;
  1851.         }
  1852.     public:
  1853.         void insert(size_t __p, const rope& __r) {
  1854.             _RopeRep* __result = 
  1855.               replace(_M_tree_ptr, __p, __p, __r._M_tree_ptr);
  1856. #           ifdef __STL_USE_STD_ALLOCATORS
  1857.                 __stl_assert(get_allocator() == __r.get_allocator());
  1858. #           endif
  1859.             _S_unref(_M_tree_ptr);
  1860.             _M_tree_ptr = __result;
  1861.         }
  1862.         void insert(size_t __p, size_t __n, _CharT __c) {
  1863.             rope<_CharT,_Alloc> __r(__n,__c);
  1864.             insert(__p, __r);
  1865.         }
  1866.         void insert(size_t __p, const _CharT* __i, size_t __n) {
  1867.             _Self_destruct_ptr __left(_S_substring(_M_tree_ptr, 0, __p));
  1868.             _Self_destruct_ptr __right(_S_substring(_M_tree_ptr, __p, size()));
  1869.             _Self_destruct_ptr __left_result(
  1870.               _S_concat_char_iter(__left, __i, __n));
  1871.                 // _S_ destr_concat_char_iter should be safe here.
  1872.                 // But as it stands it's probably not a win, since __left
  1873.                 // is likely to have additional references.
  1874.             _RopeRep* __result = _S_concat(__left_result, __right);
  1875.             _S_unref(_M_tree_ptr);
  1876.             _M_tree_ptr = __result;
  1877.         }
  1878.         void insert(size_t __p, const _CharT* __c_string) {
  1879.             insert(__p, __c_string, _S_char_ptr_len(__c_string));
  1880.         }
  1881.         void insert(size_t __p, _CharT __c) {
  1882.             insert(__p, &__c, 1);
  1883.         }
  1884.         void insert(size_t __p) {
  1885.             _CharT __c = _CharT();
  1886.             insert(__p, &__c, 1);
  1887.         }
  1888.         void insert(size_t __p, const _CharT* __i, const _CharT* __j) {
  1889.             rope __r(__i, __j);
  1890.             insert(__p, __r);
  1891.         }
  1892.         void insert(size_t __p, const const_iterator& __i,
  1893.                               const const_iterator& __j) {
  1894.             rope __r(__i, __j);
  1895.             insert(__p, __r);
  1896.         }
  1897.         void insert(size_t __p, const iterator& __i,
  1898.                               const iterator& __j) {
  1899.             rope __r(__i, __j);
  1900.             insert(__p, __r);
  1901.         }
  1902.         // (position, length) versions of replace operations:
  1903.         void replace(size_t __p, size_t __n, const rope& __r) {
  1904.             _RopeRep* __result = 
  1905.               replace(_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
  1906.             _S_unref(_M_tree_ptr);
  1907.             _M_tree_ptr = __result;
  1908.         }
  1909.         void replace(size_t __p, size_t __n, 
  1910.                      const _CharT* __i, size_t __i_len) {
  1911.             rope __r(__i, __i_len);
  1912.             replace(__p, __n, __r);
  1913.         }
  1914.         void replace(size_t __p, size_t __n, _CharT __c) {
  1915.             rope __r(__c);
  1916.             replace(__p, __n, __r);
  1917.         }
  1918.         void replace(size_t __p, size_t __n, const _CharT* __c_string) {
  1919.             rope __r(__c_string);
  1920.             replace(__p, __n, __r);
  1921.         }
  1922.         void replace(size_t __p, size_t __n, 
  1923.                      const _CharT* __i, const _CharT* __j) {
  1924.             rope __r(__i, __j);
  1925.             replace(__p, __n, __r);
  1926.         }
  1927.         void replace(size_t __p, size_t __n,
  1928.                      const const_iterator& __i, const const_iterator& __j) {
  1929.             rope __r(__i, __j);
  1930.             replace(__p, __n, __r);
  1931.         }
  1932.         void replace(size_t __p, size_t __n,
  1933.                      const iterator& __i, const iterator& __j) {
  1934.             rope __r(__i, __j);
  1935.             replace(__p, __n, __r);
  1936.         }
  1937.         // Single character variants:
  1938.         void replace(size_t __p, _CharT __c) {
  1939.             iterator __i(this, __p);
  1940.             *__i = __c;
  1941.         }
  1942.         void replace(size_t __p, const rope& __r) {
  1943.             replace(__p, 1, __r);
  1944.         }
  1945.         void replace(size_t __p, const _CharT* __i, size_t __i_len) {
  1946.             replace(__p, 1, __i, __i_len);
  1947.         }
  1948.         void replace(size_t __p, const _CharT* __c_string) {
  1949.             replace(__p, 1, __c_string);
  1950.         }
  1951.         void replace(size_t __p, const _CharT* __i, const _CharT* __j) {
  1952.             replace(__p, 1, __i, __j);
  1953.         }
  1954.         void replace(size_t __p, const const_iterator& __i,
  1955.                                const const_iterator& __j) {
  1956.             replace(__p, 1, __i, __j);
  1957.         }
  1958.         void replace(size_t __p, const iterator& __i,
  1959.                                const iterator& __j) {
  1960.             replace(__p, 1, __i, __j);
  1961.         }
  1962.         // Erase, (position, size) variant.
  1963.         void erase(size_t __p, size_t __n) {
  1964.             _RopeRep* __result = replace(_M_tree_ptr, __p, __p + __n, 0);
  1965.             _S_unref(_M_tree_ptr);
  1966.             _M_tree_ptr = __result;
  1967.         }
  1968.         // Erase, single character
  1969.         void erase(size_t __p) {
  1970.             erase(__p, __p + 1);
  1971.         }
  1972.         // Insert, iterator variants.  
  1973.         iterator insert(const iterator& __p, const rope& __r)
  1974.                 { insert(__p.index(), __r); return __p; }
  1975.         iterator insert(const iterator& __p, size_t __n, _CharT __c)
  1976.                 { insert(__p.index(), __n, __c); return __p; }
  1977.         iterator insert(const iterator& __p, _CharT __c) 
  1978.                 { insert(__p.index(), __c); return __p; }
  1979.         iterator insert(const iterator& __p ) 
  1980.                 { insert(__p.index()); return __p; }
  1981.         iterator insert(const iterator& __p, const _CharT* c_string) 
  1982.                 { insert(__p.index(), c_string); return __p; }
  1983.         iterator insert(const iterator& __p, const _CharT* __i, size_t __n)
  1984.                 { insert(__p.index(), __i, __n); return __p; }
  1985.         iterator insert(const iterator& __p, const _CharT* __i, 
  1986.                         const _CharT* __j)
  1987.                 { insert(__p.index(), __i, __j);  return __p; }
  1988.         iterator insert(const iterator& __p,
  1989.                         const const_iterator& __i, const const_iterator& __j)
  1990.                 { insert(__p.index(), __i, __j); return __p; }
  1991.         iterator insert(const iterator& __p,
  1992.                         const iterator& __i, const iterator& __j)
  1993.                 { insert(__p.index(), __i, __j); return __p; }
  1994.         // Replace, range variants.
  1995.         void replace(const iterator& __p, const iterator& __q,
  1996.                      const rope& __r)
  1997.                 { replace(__p.index(), __q.index() - __p.index(), __r); }
  1998.         void replace(const iterator& __p, const iterator& __q, _CharT __c)
  1999.                 { replace(__p.index(), __q.index() - __p.index(), __c); }
  2000.         void replace(const iterator& __p, const iterator& __q,
  2001.                      const _CharT* __c_string)
  2002.                 { replace(__p.index(), __q.index() - __p.index(), __c_string); }
  2003.         void replace(const iterator& __p, const iterator& __q,
  2004.                      const _CharT* __i, size_t __n)
  2005.                 { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
  2006.         void replace(const iterator& __p, const iterator& __q,
  2007.                      const _CharT* __i, const _CharT* __j)
  2008.                 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
  2009.         void replace(const iterator& __p, const iterator& __q,
  2010.                      const const_iterator& __i, const const_iterator& __j)
  2011.                 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
  2012.         void replace(const iterator& __p, const iterator& __q,
  2013.                      const iterator& __i, const iterator& __j)
  2014.                 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
  2015.         // Replace, iterator variants.
  2016.         void replace(const iterator& __p, const rope& __r)
  2017.                 { replace(__p.index(), __r); }
  2018.         void replace(const iterator& __p, _CharT __c)
  2019.                 { replace(__p.index(), __c); }
  2020.         void replace(const iterator& __p, const _CharT* __c_string)
  2021.                 { replace(__p.index(), __c_string); }
  2022.         void replace(const iterator& __p, const _CharT* __i, size_t __n)
  2023.                 { replace(__p.index(), __i, __n); }
  2024.         void replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
  2025.                 { replace(__p.index(), __i, __j); }
  2026.         void replace(const iterator& __p, const_iterator __i, 
  2027.                      const_iterator __j)
  2028.                 { replace(__p.index(), __i, __j); }
  2029.         void replace(const iterator& __p, iterator __i, iterator __j)
  2030.                 { replace(__p.index(), __i, __j); }
  2031.         // Iterator and range variants of erase
  2032.         iterator erase(const iterator& __p, const iterator& __q) {
  2033.             size_t __p_index = __p.index();
  2034.             erase(__p_index, __q.index() - __p_index);
  2035.             return iterator(this, __p_index);
  2036.         }
  2037.         iterator erase(const iterator& __p) {
  2038.             size_t __p_index = __p.index();
  2039.             erase(__p_index, 1);
  2040.             return iterator(this, __p_index);
  2041.         }
  2042.         rope substr(size_t __start, size_t __len = 1) const {
  2043.             return rope<_CharT,_Alloc>(
  2044.                         _S_substring(_M_tree_ptr, __start, __start + __len));
  2045.         }
  2046.         rope substr(iterator __start, iterator __end) const {
  2047.             return rope<_CharT,_Alloc>(
  2048.                 _S_substring(_M_tree_ptr, __start.index(), __end.index()));
  2049.         }
  2050.         
  2051.         rope substr(iterator __start) const {
  2052.             size_t __pos = __start.index();
  2053.             return rope<_CharT,_Alloc>(
  2054.                         _S_substring(_M_tree_ptr, __pos, __pos + 1));
  2055.         }
  2056.         
  2057.         rope substr(const_iterator __start, const_iterator __end) const {
  2058.             // This might eventually take advantage of the cache in the
  2059.             // iterator.
  2060.             return rope<_CharT,_Alloc>(
  2061.               _S_substring(_M_tree_ptr, __start.index(), __end.index()));
  2062.         }
  2063.         rope<_CharT,_Alloc> substr(const_iterator __start) {
  2064.             size_t __pos = __start.index();
  2065.             return rope<_CharT,_Alloc>(
  2066.               _S_substring(_M_tree_ptr, __pos, __pos + 1));
  2067.         }
  2068.         static const size_type npos;
  2069.         size_type find(_CharT __c, size_type __pos = 0) const;
  2070.         size_type find(const _CharT* __s, size_type __pos = 0) const {
  2071.             size_type __result_pos;
  2072.             const_iterator __result = search(const_begin() + __pos, const_end(),
  2073.                                            __s, __s + _S_char_ptr_len(__s));
  2074.             __result_pos = __result.index();
  2075. #           ifndef __STL_OLD_ROPE_SEMANTICS
  2076.                 if (__result_pos == size()) __result_pos = npos;
  2077. #           endif
  2078.             return __result_pos;
  2079.         }
  2080.         iterator mutable_begin() {
  2081.             return(iterator(this, 0));
  2082.         }
  2083.         iterator mutable_end() {
  2084.             return(iterator(this, size()));
  2085.         }
  2086. #     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  2087.         typedef reverse_iterator<iterator> reverse_iterator;
  2088. #     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2089.         typedef reverse_iterator<iterator, value_type, reference,
  2090.                                  difference_type>  reverse_iterator;
  2091. #     endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  2092.         reverse_iterator mutable_rbegin() {
  2093.             return reverse_iterator(mutable_end());
  2094.         }
  2095.         reverse_iterator mutable_rend() {
  2096.             return reverse_iterator(mutable_begin());
  2097.         }
  2098.         reference mutable_reference_at(size_type __pos) {
  2099.             return reference(this, __pos);
  2100.         }
  2101. #       ifdef __STD_STUFF
  2102.             reference operator[] (size_type __pos) {
  2103.                 return _char_ref_proxy(this, __pos);
  2104.             }
  2105.             reference at(size_type __pos) {
  2106.                 // if (__pos >= size()) throw out_of_range;  // XXX
  2107.                 return (*this)[__pos];
  2108.             }
  2109.             void resize(size_type __n, _CharT __c) {}
  2110.             void resize(size_type __n) {}
  2111.             void reserve(size_type __res_arg = 0) {}
  2112.             size_type capacity() const {
  2113.                 return max_size();
  2114.             }
  2115.           // Stuff below this line is dangerous because it's error prone.
  2116.           // I would really like to get rid of it.
  2117.             // copy function with funny arg ordering.
  2118.               size_type copy(_CharT* __buffer, size_type __n, 
  2119.                              size_type __pos = 0) const {
  2120.                 return copy(__pos, __n, __buffer);
  2121.               }
  2122.             iterator end() { return mutable_end(); }
  2123.             iterator begin() { return mutable_begin(); }
  2124.             reverse_iterator rend() { return mutable_rend(); }
  2125.             reverse_iterator rbegin() { return mutable_rbegin(); }
  2126. #       else
  2127.             const_iterator end() { return const_end(); }
  2128.             const_iterator begin() { return const_begin(); }
  2129.             const_reverse_iterator rend() { return const_rend(); }
  2130.   
  2131.             const_reverse_iterator rbegin() { return const_rbegin(); }
  2132. #       endif
  2133.         
  2134. };
  2135. template <class _CharT, class _Alloc>
  2136. const rope<_CharT, _Alloc>::size_type rope<_CharT, _Alloc>::npos =
  2137.                         (size_type)(-1);
  2138. template <class _CharT, class _Alloc>
  2139. inline bool operator== (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2140.                         const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2141.   return (__x._M_current_pos == __y._M_current_pos && 
  2142.           __x._M_root == __y._M_root);
  2143. }
  2144. template <class _CharT, class _Alloc>
  2145. inline bool operator< (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2146.                        const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2147.   return (__x._M_current_pos < __y._M_current_pos);
  2148. }
  2149. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  2150. template <class _CharT, class _Alloc>
  2151. inline bool operator!= (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2152.                         const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2153.   return !(__x == __y);
  2154. }
  2155. template <class _CharT, class _Alloc>
  2156. inline bool operator> (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2157.                        const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2158.   return __y < __x;
  2159. }
  2160. template <class _CharT, class _Alloc>
  2161. inline bool operator<= (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2162.                         const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2163.   return !(__y < __x);
  2164. }
  2165. template <class _CharT, class _Alloc>
  2166. inline bool operator>= (const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2167.                         const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2168.   return !(__x < __y);
  2169. }
  2170. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  2171. template <class _CharT, class _Alloc>
  2172. inline ptrdiff_t operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x,
  2173.                            const _Rope_const_iterator<_CharT,_Alloc>& __y) {
  2174.   return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos;
  2175. }
  2176. template <class _CharT, class _Alloc>
  2177. inline _Rope_const_iterator<_CharT,_Alloc>
  2178. operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n) {
  2179.   return _Rope_const_iterator<_CharT,_Alloc>(
  2180.             __x._M_root, __x._M_current_pos - __n);
  2181. }
  2182. template <class _CharT, class _Alloc>
  2183. inline _Rope_const_iterator<_CharT,_Alloc>
  2184. operator+(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n) {
  2185.   return _Rope_const_iterator<_CharT,_Alloc>(
  2186.            __x._M_root, __x._M_current_pos + __n);
  2187. }
  2188. template <class _CharT, class _Alloc>
  2189. inline _Rope_const_iterator<_CharT,_Alloc>
  2190. operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT,_Alloc>& __x) {
  2191.   return _Rope_const_iterator<_CharT,_Alloc>(
  2192.            __x._M_root, __x._M_current_pos + __n);
  2193. }
  2194. template <class _CharT, class _Alloc>
  2195. inline bool operator== (const _Rope_iterator<_CharT,_Alloc>& __x,
  2196.                         const _Rope_iterator<_CharT,_Alloc>& __y) {
  2197.   return (__x._M_current_pos == __y._M_current_pos && 
  2198.           __x._M_root_rope == __y._M_root_rope);
  2199. }
  2200. template <class _CharT, class _Alloc>
  2201. inline bool operator< (const _Rope_iterator<_CharT,_Alloc>& __x,
  2202.                        const _Rope_iterator<_CharT,_Alloc>& __y) {
  2203.   return (__x._M_current_pos < __y._M_current_pos);
  2204. }
  2205. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  2206. template <class _CharT, class _Alloc>
  2207. inline bool operator!= (const _Rope_iterator<_CharT,_Alloc>& __x,
  2208.                         const _Rope_iterator<_CharT,_Alloc>& __y) {
  2209.   return !(__x == __y);
  2210. }
  2211. template <class _CharT, class _Alloc>
  2212. inline bool operator> (const _Rope_iterator<_CharT,_Alloc>& __x,
  2213.                        const _Rope_iterator<_CharT,_Alloc>& __y) {
  2214.   return __y < __x;
  2215. }
  2216. template <class _CharT, class _Alloc>
  2217. inline bool operator<= (const _Rope_iterator<_CharT,_Alloc>& __x,
  2218.                         const _Rope_iterator<_CharT,_Alloc>& __y) {
  2219.   return !(__y < __x);
  2220. }
  2221. template <class _CharT, class _Alloc>
  2222. inline bool operator>= (const _Rope_iterator<_CharT,_Alloc>& __x,
  2223.                         const _Rope_iterator<_CharT,_Alloc>& __y) {
  2224.   return !(__x < __y);
  2225. }
  2226. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  2227. template <class _CharT, class _Alloc>
  2228. inline ptrdiff_t operator-(const _Rope_iterator<_CharT,_Alloc>& __x,
  2229.                            const _Rope_iterator<_CharT,_Alloc>& __y) {
  2230.   return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos;
  2231. }
  2232. template <class _CharT, class _Alloc>
  2233. inline _Rope_iterator<_CharT,_Alloc>
  2234. operator-(const _Rope_iterator<_CharT,_Alloc>& __x,
  2235.           ptrdiff_t __n) {
  2236.   return _Rope_iterator<_CharT,_Alloc>(
  2237.     __x._M_root_rope, __x._M_current_pos - __n);
  2238. }
  2239. template <class _CharT, class _Alloc>
  2240. inline _Rope_iterator<_CharT,_Alloc>
  2241. operator+(const _Rope_iterator<_CharT,_Alloc>& __x,
  2242.           ptrdiff_t __n) {
  2243.   return _Rope_iterator<_CharT,_Alloc>(
  2244.     __x._M_root_rope, __x._M_current_pos + __n);
  2245. }
  2246. template <class _CharT, class _Alloc>
  2247. inline _Rope_iterator<_CharT,_Alloc>
  2248. operator+(ptrdiff_t __n, const _Rope_iterator<_CharT,_Alloc>& __x) {
  2249.   return _Rope_iterator<_CharT,_Alloc>(
  2250.     __x._M_root_rope, __x._M_current_pos + __n);
  2251. }
  2252. template <class _CharT, class _Alloc>
  2253. inline
  2254. rope<_CharT,_Alloc>
  2255. operator+ (const rope<_CharT,_Alloc>& __left,
  2256.            const rope<_CharT,_Alloc>& __right)
  2257. {
  2258. #   ifdef __STL_USE_STD_ALLOCATORS
  2259.         __stl_assert(__left.get_allocator() == __right.get_allocator());
  2260. #   endif
  2261.     return rope<_CharT,_Alloc>(
  2262.       rope<_CharT,_Alloc>::_S_concat(__left._M_tree_ptr, __right._M_tree_ptr));
  2263.     // Inlining this should make it possible to keep __left and
  2264.     // __right in registers.
  2265. }
  2266. template <class _CharT, class _Alloc>
  2267. inline
  2268. rope<_CharT,_Alloc>&
  2269. operator+= (rope<_CharT,_Alloc>& __left, 
  2270.       const rope<_CharT,_Alloc>& __right)
  2271. {
  2272.     __left.append(__right);
  2273.     return __left;
  2274. }
  2275. template <class _CharT, class _Alloc>
  2276. inline
  2277. rope<_CharT,_Alloc>
  2278. operator+ (const rope<_CharT,_Alloc>& __left,
  2279.            const _CharT* __right) {
  2280.     size_t __rlen = rope<_CharT,_Alloc>::_S_char_ptr_len(__right);
  2281.     return rope<_CharT,_Alloc>(
  2282.       rope<_CharT,_Alloc>::_S_concat_char_iter(
  2283.         __left._M_tree_ptr, __right, __rlen)); 
  2284. }
  2285. template <class _CharT, class _Alloc>
  2286. inline
  2287. rope<_CharT,_Alloc>&
  2288. operator+= (rope<_CharT,_Alloc>& __left,
  2289.             const _CharT* __right) {
  2290.     __left.append(__right);
  2291.     return __left;
  2292. }
  2293. template <class _CharT, class _Alloc>
  2294. inline
  2295. rope<_CharT,_Alloc>
  2296. operator+ (const rope<_CharT,_Alloc>& __left, _CharT __right) {
  2297.     return rope<_CharT,_Alloc>(
  2298.       rope<_CharT,_Alloc>::_S_concat_char_iter(
  2299.         __left._M_tree_ptr, &__right, 1));
  2300. }
  2301. template <class _CharT, class _Alloc>
  2302. inline
  2303. rope<_CharT,_Alloc>&
  2304. operator+= (rope<_CharT,_Alloc>& __left, _CharT __right) {
  2305.     __left.append(__right);
  2306.     return __left;
  2307. }
  2308. template <class _CharT, class _Alloc>
  2309. bool
  2310. operator< (const rope<_CharT,_Alloc>& __left, 
  2311.            const rope<_CharT,_Alloc>& __right) {
  2312.     return __left.compare(__right) < 0;
  2313. }
  2314.         
  2315. template <class _CharT, class _Alloc>
  2316. bool
  2317. operator== (const rope<_CharT,_Alloc>& __left, 
  2318.             const rope<_CharT,_Alloc>& __right) {
  2319.     return __left.compare(__right) == 0;
  2320. }
  2321. template <class _CharT, class _Alloc>
  2322. inline bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x,
  2323.                         const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y) {
  2324.         return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root);
  2325. }
  2326. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  2327. template <class _CharT, class _Alloc>
  2328. inline bool
  2329. operator!= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) {
  2330.   return !(__x == __y);
  2331. }
  2332. template <class _CharT, class _Alloc>
  2333. inline bool
  2334. operator> (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) {
  2335.   return __y < __x;
  2336. }
  2337. template <class _CharT, class _Alloc>
  2338. inline bool
  2339. operator<= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) {
  2340.   return !(__y < __x);
  2341. }
  2342. template <class _CharT, class _Alloc>
  2343. inline bool
  2344. operator>= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) {
  2345.   return !(__x < __y);
  2346. }
  2347. template <class _CharT, class _Alloc>
  2348. inline bool operator!= (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x,
  2349.                         const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y) {
  2350.   return !(__x == __y);
  2351. }
  2352. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  2353. #ifdef __STL_USE_NEW_IOSTREAMS
  2354.   template<class _CharT, class _Traits, class _Alloc>
  2355.   basic_ostream<_CharT, _Traits>& operator<<
  2356.                                         (basic_ostream<_CharT, _Traits>& __o,
  2357.                                          const rope<_CharT, _Alloc>& __r);
  2358. #else
  2359.   template<class _CharT, class _Alloc>
  2360.   ostream& operator<< (ostream& __o, const rope<_CharT, _Alloc>& __r);
  2361. #endif
  2362.         
  2363. typedef rope<char> crope;
  2364. typedef rope<wchar_t> wrope;
  2365. inline crope::reference __mutable_reference_at(crope& __c, size_t __i)
  2366. {
  2367.     return __c.mutable_reference_at(__i);
  2368. }
  2369. inline wrope::reference __mutable_reference_at(wrope& __c, size_t __i)
  2370. {
  2371.     return __c.mutable_reference_at(__i);
  2372. }
  2373. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  2374. template <class _CharT, class _Alloc>
  2375. inline void swap(rope<_CharT,_Alloc>& __x, rope<_CharT,_Alloc>& __y) {
  2376.   __x.swap(__y);
  2377. }
  2378. #else
  2379. inline void swap(crope __x, crope __y) { __x.swap(__y); }
  2380. inline void swap(wrope __x, wrope __y) { __x.swap(__y); }
  2381. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  2382. // Hash functions should probably be revisited later:
  2383. __STL_TEMPLATE_NULL struct hash<crope>
  2384. {
  2385.   size_t operator()(const crope& __str) const
  2386.   {
  2387.     size_t __size = __str.size();
  2388.     if (0 == __size) return 0;
  2389.     return 13*__str[0] + 5*__str[__size - 1] + __size;
  2390.   }
  2391. };
  2392. __STL_TEMPLATE_NULL struct hash<wrope>
  2393. {
  2394.   size_t operator()(const wrope& __str) const
  2395.   {
  2396.     size_t __size = __str.size();
  2397.     if (0 == __size) return 0;
  2398.     return 13*__str[0] + 5*__str[__size - 1] + __size;
  2399.   }
  2400. };
  2401. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  2402. #pragma reset woff 1174
  2403. #endif
  2404. __STL_END_NAMESPACE
  2405. # include <ropeimpl.h>
  2406. # endif /* __SGI_STL_INTERNAL_ROPE_H */
  2407. // Local Variables:
  2408. // mode:C++
  2409. // End: