home *** CD-ROM | disk | FTP | other *** search
/ Beginning C++ Through Gam…rogramming (2nd Edition) / BCGP2E.ISO / bloodshed / devcpp-4.9.9.2_setup.exe / rope < prev    next >
Text File  |  2005-01-29  |  90KB  |  2,495 lines

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