home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 January / PCWorld_2000-01_cd.bin / Software / Servis / Devc / _SETUP.4 / Group3 / stl_rope.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  63KB  |  2,113 lines
  1. /*
  2.  * Copyright (c) 1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. /* NOTE: This is an internal header file, included by other STL headers.
  15.  *   You should not attempt to use it directly.
  16.  */
  17.  
  18. #ifndef __SGI_STL_INTERNAL_ROPE_H
  19. # define __SGI_STL_INTERNAL_ROPE_H
  20.  
  21. # ifdef __GC
  22. #   define __GC_CONST const
  23. # else
  24. #   define __GC_CONST   // constant except for deallocation
  25. # endif
  26. # ifdef __STL_SGI_THREADS
  27. #    include <mutex.h>
  28. # endif
  29.  
  30. __STL_BEGIN_NAMESPACE
  31.  
  32. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  33. #pragma set woff 1174
  34. #endif
  35.  
  36. // The end-of-C-string character.
  37. // This is what the draft standard says it should be.
  38. template <class charT>
  39. inline charT __eos(charT*) { return charT(); }
  40.  
  41. // Test for basic character types.
  42. // For basic character types leaves having a trailing eos.
  43. template <class charT>
  44. inline bool __is_basic_char_type(charT *) { return false; }
  45. template <class charT>
  46. inline bool __is_one_byte_char_type(charT *) { return false; }
  47.  
  48. inline bool __is_basic_char_type(char *) { return true; }
  49. inline bool __is_one_byte_char_type(char *) { return true; }
  50. inline bool __is_basic_char_type(wchar_t *) { return true; }
  51.  
  52. // Store an eos iff charT is a basic character type.
  53. // Do not reference __eos if it isn't.
  54. template <class charT>
  55. inline void __cond_store_eos(charT&) {}
  56.  
  57. inline void __cond_store_eos(char& c) { c = 0; }
  58. inline void __cond_store_eos(wchar_t& c) { c = 0; }
  59.     
  60.  
  61. // rope<charT,Alloc> is a sequence of charT.
  62. // Ropes appear to be mutable, but update operations
  63. // really copy enough of the data structure to leave the original
  64. // valid.  Thus ropes can be logically copied by just copying
  65. // a pointer value.
  66. // The __eos function is used for those functions that
  67. // convert to/from C-like strings to detect the end of the string.
  68. // __compare is used as the character comparison function.
  69. template <class charT>
  70. class char_producer {
  71.     public:
  72.     virtual ~char_producer() {};
  73.     virtual void operator()(size_t start_pos, size_t len, charT* buffer)
  74.         = 0;
  75.     // Buffer should really be an arbitrary output iterator.
  76.     // That way we could flatten directly into an ostream, etc.
  77.     // This is thoroughly impossible, since iterator types don't
  78.     // have runtime descriptions.
  79. };
  80.  
  81. // Sequence buffers:
  82. //
  83. // Sequence must provide an append operation that appends an
  84. // array to the sequence.  Sequence buffers are useful only if
  85. // appending an entire array is cheaper than appending element by element.
  86. // This is true for many string representations.
  87. // This should  perhaps inherit from ostream<sequence::value_type>
  88. // and be implemented correspondingly, so that they can be used
  89. // for formatted.  For the sake of portability, we don't do this yet.
  90. //
  91. // For now, sequence buffers behave as output iterators.  But they also
  92. // behave a little like basic_ostringstream<sequence::value_type> and a
  93. // little like containers.
  94.  
  95. template<class sequence, size_t buf_sz = 100
  96. #   if defined(__sgi) && !defined(__GNUC__)
  97. #     define __TYPEDEF_WORKAROUND
  98.          ,class v = typename sequence::value_type
  99. #   endif
  100.         >
  101. // The 3rd parameter works around a common compiler bug.
  102. class sequence_buffer : public output_iterator {
  103.     public:
  104. #       ifndef __TYPEDEF_WORKAROUND
  105.         typedef typename sequence::value_type value_type;
  106. #    else
  107.         typedef v value_type;
  108. #    endif
  109.     protected:
  110.     sequence *prefix;
  111.     value_type buffer[buf_sz];
  112.     size_t buf_count;
  113.     public:
  114.     void flush() {
  115.         prefix->append(buffer, buffer + buf_count);
  116.         buf_count = 0;
  117.     }
  118.     ~sequence_buffer() { flush(); }
  119.     sequence_buffer() : prefix(0), buf_count(0) {}
  120.     sequence_buffer(const sequence_buffer & x) {
  121.         prefix = x.prefix;
  122.             buf_count = x.buf_count;
  123.             copy(x.buffer, x.buffer + x.buf_count, buffer);
  124.     }
  125.     sequence_buffer(sequence_buffer & x) {
  126.         x.flush();
  127.         prefix = x.prefix;
  128.         buf_count = 0;
  129.     }
  130.     sequence_buffer(sequence& s) : prefix(&s), buf_count(0) {}
  131.     sequence_buffer& operator= (sequence_buffer& x) {
  132.         x.flush();
  133.         prefix = x.prefix;
  134.         buf_count = 0;
  135.         return *this;
  136.     }
  137.     sequence_buffer& operator= (const sequence_buffer& x) {
  138.         prefix = x.prefix;
  139.         buf_count = x.buf_count;
  140.         copy(x.buffer, x.buffer + x.buf_count, buffer);
  141.         return *this;
  142.     }
  143.     void push_back(value_type x)
  144.     {
  145.         if (buf_count < buf_sz) {
  146.         buffer[buf_count] = x;
  147.         ++buf_count;
  148.         } else {
  149.         flush();
  150.         buffer[0] = x;
  151.         buf_count = 1;
  152.         }
  153.     }
  154.     void append(value_type *s, size_t len)
  155.     {
  156.         if (len + buf_count <= buf_sz) {
  157.         size_t i, j;
  158.         for (i = buf_count, j = 0; j < len; i++, j++) {
  159.             buffer[i] = s[j];
  160.         }
  161.         buf_count += len;
  162.         } else if (0 == buf_count) {
  163.         prefix->append(s, s + len);
  164.         } else {
  165.         flush();
  166.         append(s, len);
  167.         }
  168.     }
  169.     sequence_buffer& write(value_type *s, size_t len)
  170.     {
  171.         append(s, len);
  172.         return *this;
  173.     }
  174.     sequence_buffer& put(value_type x)
  175.     {
  176.         push_back(x);
  177.         return *this;
  178.     }
  179.     sequence_buffer& operator=(const value_type& rhs)
  180.     {
  181.         push_back(rhs);
  182.         return *this;
  183.     }
  184.     sequence_buffer& operator*() { return *this; }
  185.     sequence_buffer& operator++() { return *this; }
  186.     sequence_buffer& operator++(int) { return *this; }
  187. };
  188.  
  189. // The following should be treated as private, at least for now.
  190. template<class charT>
  191. class __rope_char_consumer {
  192.     public:
  193.     // If we had member templates, these should not be virtual.
  194.     // For now we need to use run-time parametrization where
  195.     // compile-time would do.  Hence this should all be private
  196.     // for now.
  197.     // The symmetry with char_producer is accidental and temporary.
  198.     virtual ~__rope_char_consumer() {};
  199.     virtual bool operator()(const charT* buffer, size_t len) = 0;
  200. };
  201.  
  202. //
  203. // What follows should really be local to rope.  Unfortunately,
  204. // that doesn't work, since it makes it impossible to define generic
  205. // equality on rope iterators.  According to the draft standard, the
  206. // template parameters for such an equality operator cannot be inferred
  207. // from the occurence of a member class as a parameter.
  208. // (SGI compilers in fact allow this, but the result wouldn't be
  209. // portable.)
  210. // Similarly, some of the static member functions are member functions
  211. // only to avoid polluting the global namespace, and to circumvent
  212. // restrictions on type inference for template functions.
  213. //
  214.  
  215. template<class CharT, class Alloc=__ALLOC> class rope;
  216. template<class CharT, class Alloc> struct __rope_RopeConcatenation;
  217. template<class CharT, class Alloc> struct __rope_RopeLeaf;
  218. template<class CharT, class Alloc> struct __rope_RopeFunction;
  219. template<class CharT, class Alloc> struct __rope_RopeSubstring;
  220. template<class CharT, class Alloc> class __rope_iterator;
  221. template<class CharT, class Alloc> class __rope_const_iterator;
  222. template<class CharT, class Alloc> class __rope_charT_ref_proxy;
  223. template<class CharT, class Alloc> class __rope_charT_ptr_proxy;
  224.  
  225. //
  226. // The internal data structure for representing a rope.  This is
  227. // private to the implementation.  A rope is really just a pointer
  228. // to one of these.
  229. //
  230. // A few basic functions for manipulating this data structure
  231. // are members of RopeBase.  Most of the more complex algorithms
  232. // are implemented as rope members.
  233. //
  234. // Some of the static member functions of RopeBase have identically
  235. // named functions in rope that simply invoke the RopeBase versions.
  236. //
  237.  
  238. template<class charT, class Alloc>
  239. struct __rope_RopeBase {
  240.     typedef rope<charT,Alloc> my_rope;
  241.     typedef simple_alloc<charT, Alloc> DataAlloc;
  242.     typedef simple_alloc<__rope_RopeConcatenation<charT,Alloc>, Alloc> CAlloc;
  243.     typedef simple_alloc<__rope_RopeLeaf<charT,Alloc>, Alloc> LAlloc;
  244.     typedef simple_alloc<__rope_RopeFunction<charT,Alloc>, Alloc> FAlloc;
  245.     typedef simple_alloc<__rope_RopeSubstring<charT,Alloc>, Alloc> SAlloc;
  246.     public:
  247.     enum { max_rope_depth = 45 };
  248.     enum {leaf, concat, substringfn, function} tag:8;
  249.     bool is_balanced:8;
  250.     unsigned char depth;
  251.     size_t size;
  252.     __GC_CONST charT * c_string;
  253.             /* Flattened version of string, if needed.  */
  254.             /* typically 0.                             */
  255.             /* If it's not 0, then the memory is owned  */
  256.             /* by this node.                            */
  257.             /* In the case of a leaf, this may point to */
  258.             /* the same memory as the data field.        */
  259. #   ifndef __GC
  260. #       if defined(__STL_WIN32THREADS)
  261.         long refcount;      // InterlockedIncrement wants a long *
  262. #    else
  263.         size_t refcount;
  264. #    endif
  265.     // We count references from rope instances
  266.     // and references from other rope nodes.  We
  267.     // do not count const_iterator references.
  268.     // Iterator references are counted so that rope modifications
  269.     // can be detected after the fact.
  270.     // Generally function results are counted, i.e.
  271.     // a pointer returned by a function is included at the
  272.     // point at which the pointer is returned.
  273.     // The recipient should decrement the count if the
  274.     // result is not needed.
  275.     // Generally function arguments are not reflected
  276.     // in the reference count.  The callee should increment
  277.     // the count before saving the argument someplace that
  278.     // will outlive the call.
  279. #   endif
  280. #   ifndef __GC
  281. #       ifdef __STL_SGI_THREADS
  282.         // Reference counting with multiple threads and no
  283.         // hardware or thread package support is pretty awful.
  284.         // Mutexes are normally too expensive.
  285.         // We'll assume a COMPARE_AND_SWAP(destp, old, new)
  286.         // operation, which might be cheaper.
  287. #           if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))
  288. #               define __add_and_fetch(l,v) add_then_test((unsigned long *)l,v)
  289. #           endif
  290.         void init_refcount_lock() {}
  291.         void incr_refcount ()
  292.         {
  293.         __add_and_fetch(&refcount, 1);
  294.         }
  295.         size_t decr_refcount ()
  296.         {
  297.         return __add_and_fetch(&refcount, (size_t)(-1));
  298.         }
  299. #       elif defined(__STL_WIN32THREADS)
  300.         void init_refcount_lock() {}
  301.             void incr_refcount ()
  302.             {
  303.                 InterlockedIncrement(&refcount);
  304.             }
  305.             size_t decr_refcount ()
  306.             {
  307.                 return InterlockedDecrement(&refcount);
  308.             }
  309. #    elif defined(__STL_PTHREADS)
  310.         // This should be portable, but performance is expected
  311.         // to be quite awful.  This really needs platform specific
  312.         // code.
  313.         pthread_mutex_t refcount_lock;
  314.         void init_refcount_lock() {
  315.         pthread_mutex_init(&refcount_lock, 0);
  316.         }
  317.         void incr_refcount ()
  318.             {   
  319.         pthread_mutex_lock(&refcount_lock);
  320.                 ++refcount;
  321.         pthread_mutex_unlock(&refcount_lock);
  322.             }
  323.             size_t decr_refcount ()
  324.             {   
  325.         size_t result;
  326.         pthread_mutex_lock(&refcount_lock);
  327.                 result = --refcount;
  328.         pthread_mutex_unlock(&refcount_lock);
  329.                 return result;
  330.             }
  331. #    else
  332.         void init_refcount_lock() {}
  333.         void incr_refcount ()
  334.         {
  335.         ++refcount;
  336.         }
  337.         size_t decr_refcount ()
  338.         {
  339.         --refcount;
  340.         return refcount;
  341.         }
  342. #       endif
  343. #   else
  344.     void incr_refcount () {}
  345. #   endif
  346.     static void free_string(charT *, size_t len);
  347.             // Deallocate data section of a leaf.
  348.             // This shouldn't be a member function.
  349.             // But its hard to do anything else at the
  350.             // moment, because it's templatized w.r.t.
  351.             // an allocator.
  352.             // Does nothing if __GC is defined.
  353. #   ifndef __GC
  354.       void free_c_string();
  355.       void free_tree();
  356.             // Deallocate t. Assumes t is not 0.
  357.       void unref_nonnil()
  358.       {
  359.           if (0 == decr_refcount()) free_tree();
  360.       }
  361.       void ref_nonnil()
  362.       {
  363.           incr_refcount();
  364.       }
  365.       static void unref(__rope_RopeBase* t)
  366.       {
  367.           if (0 != t) {
  368.           t -> unref_nonnil();
  369.           }
  370.       }
  371.       static void ref(__rope_RopeBase* t)
  372.       {
  373.           if (0 != t) t -> incr_refcount();
  374.       }
  375.       static void free_if_unref(__rope_RopeBase* t)
  376.        {
  377.           if (0 != t && 0 == t -> refcount) t -> free_tree();
  378.       }
  379. #   else /* __GC */
  380.       void unref_nonnil() {}
  381.       void ref_nonnil() {}
  382.       static void unref(__rope_RopeBase* t) {}
  383.       static void ref(__rope_RopeBase* t) {}
  384.       static void fn_finalization_proc(void * tree, void *);
  385.       static void free_if_unref(__rope_RopeBase* t) {}
  386. #   endif
  387.  
  388.     // The data fields of leaves are allocated with some
  389.     // extra space, to accomodate future growth and for basic
  390.     // character types, to hold a trailing eos character.
  391.     enum { alloc_granularity = 8 };
  392.     static size_t rounded_up_size(size_t n) {
  393.         size_t size_with_eos;
  394.          
  395.         if (__is_basic_char_type((charT *)0)) {
  396.             size_with_eos = n + 1;
  397.         } else {
  398.           size_with_eos = n;
  399.     }
  400. #       ifdef __GC
  401.           return size_with_eos;
  402. #    else
  403.        // Allow slop for in-place expansion.
  404.        return (size_with_eos + alloc_granularity-1)
  405.             &~ (alloc_granularity-1);
  406. #    endif
  407.     }
  408. };
  409.  
  410. template<class charT, class Alloc>
  411. struct __rope_RopeLeaf : public __rope_RopeBase<charT,Alloc> {
  412.   public:  // Apparently needed by VC++
  413.     __GC_CONST charT* data;     /* Not necessarily 0 terminated. */
  414.                 /* The allocated size is     */
  415.                 /* rounded_up_size(size), except */
  416.                 /* in the GC case, in which it     */
  417.                 /* doesn't matter.         */
  418. };
  419.  
  420. template<class charT, class Alloc>
  421. struct __rope_RopeConcatenation : public __rope_RopeBase<charT,Alloc> {
  422.   public:
  423.     __rope_RopeBase<charT,Alloc>* left;
  424.     __rope_RopeBase<charT,Alloc>* right;
  425. };
  426.  
  427. template<class charT, class Alloc>
  428. struct __rope_RopeFunction : public __rope_RopeBase<charT,Alloc> {
  429.   public:
  430.     char_producer<charT>* fn;
  431. #   ifndef __GC
  432.       bool delete_when_done;    // Char_producer is owned by the
  433.                 // rope and should be explicitly
  434.                 // deleted when the rope becomes
  435.                 // inaccessible.
  436. #   else
  437.       // In the GC case, we either register the rope for
  438.       // finalization, or not.  Thus the field is unnecessary;
  439.       // the information is stored in the collector data structures.
  440. #   endif
  441. };
  442. // Substring results are usually represented using just
  443. // concatenation nodes.  But in the case of very long flat ropes
  444. // or ropes with a functional representation that isn't practical.
  445. // In that case, we represent the result as a special case of
  446. // RopeFunction, whose char_producer points back to the rope itself.
  447. // In all cases except repeated substring operations and
  448. // deallocation, we treat the result as a RopeFunction.
  449. template<class charT, class Alloc>
  450. struct __rope_RopeSubstring: public __rope_RopeFunction<charT,Alloc>,
  451.                  public char_producer<charT> {
  452.   public:
  453.     __rope_RopeBase<charT,Alloc> * base;    // not 0
  454.     size_t start;
  455.     virtual ~__rope_RopeSubstring() {}
  456.     virtual void operator()(size_t start_pos, size_t req_len,
  457.                 charT *buffer) {
  458.     switch(base -> tag) {
  459.         case function:
  460.         case substringfn:
  461.           {
  462.         char_producer<charT> *fn =
  463.             ((__rope_RopeFunction<charT,Alloc> *)base) -> fn;
  464.         __stl_assert(start_pos + req_len <= size);
  465.         __stl_assert(start + size <= base -> size);
  466.         (*fn)(start_pos + start, req_len, buffer);
  467.           }
  468.           break;
  469.         case leaf:
  470.           {
  471.         __GC_CONST charT * s =
  472.             ((__rope_RopeLeaf<charT,Alloc> *)base) -> data;
  473.         uninitialized_copy_n(s + start_pos + start, req_len,
  474.                      buffer);
  475.           }
  476.           break;
  477.         default:
  478.           __stl_assert(false);
  479.     }
  480.     }
  481.     __rope_RopeSubstring(__rope_RopeBase<charT,Alloc> * b, size_t s, size_t l) :
  482.     base(b), start(s) {
  483. #       ifndef __GC
  484.         refcount = 1;
  485.         init_refcount_lock();
  486.         base -> ref_nonnil();
  487. #       endif
  488.     size = l;
  489.     tag = substringfn;
  490.     depth = 0;
  491.     c_string = 0;
  492.     fn = this;
  493.     }
  494. };
  495.  
  496.  
  497. // Self-destructing pointers to RopeBase.
  498. // These are not conventional smart pointers.  Their
  499. // only purpose in life is to ensure that unref is called
  500. // on the pointer either at normal exit or if an exception
  501. // is raised.  It is the caller's responsibility to
  502. // adjust reference counts when these pointers are initialized
  503. // or assigned to.  (This convention significantly reduces
  504. // the number of potentially expensive reference count
  505. // updates.)
  506. #ifndef __GC
  507.   template<class charT, class Alloc>
  508.   struct __rope_self_destruct_ptr {
  509.     __rope_RopeBase<charT,Alloc> * ptr;
  510.     ~__rope_self_destruct_ptr() { __rope_RopeBase<charT,Alloc>::unref(ptr); }
  511. #   ifdef __STL_USE_EXCEPTIONS
  512.     __rope_self_destruct_ptr() : ptr(0) {};
  513. #   else
  514.     __rope_self_destruct_ptr() {};
  515. #   endif
  516.     __rope_self_destruct_ptr(__rope_RopeBase<charT,Alloc> * p) : ptr(p) {}
  517.     __rope_RopeBase<charT,Alloc> & operator*() { return *ptr; }
  518.     __rope_RopeBase<charT,Alloc> * operator->() { return ptr; }
  519.     operator __rope_RopeBase<charT,Alloc> *() { return ptr; }
  520.     __rope_self_destruct_ptr & operator= (__rope_RopeBase<charT,Alloc> * x)
  521.     { ptr = x; return *this; }
  522.   };
  523. #endif
  524.  
  525. // Dereferencing a nonconst iterator has to return something
  526. // that behaves almost like a reference.  It's not possible to
  527. // return an actual reference since assignment requires extra
  528. // work.  And we would get into the same problems as with the
  529. // CD2 version of basic_string.
  530. template<class charT, class Alloc>
  531. class __rope_charT_ref_proxy {
  532.     friend class rope<charT,Alloc>;
  533.     friend class __rope_iterator<charT,Alloc>;
  534.     friend class __rope_charT_ptr_proxy<charT,Alloc>;
  535. #   ifdef __GC
  536.     typedef __rope_RopeBase<charT,Alloc> * self_destruct_ptr;
  537. #   else
  538.         typedef __rope_self_destruct_ptr<charT,Alloc> self_destruct_ptr;
  539. #   endif
  540.     typedef __rope_RopeBase<charT,Alloc> RopeBase;
  541.     typedef rope<charT,Alloc> my_rope;
  542.     size_t pos;
  543.     charT current;
  544.     bool current_valid;
  545.     my_rope * root;     // The whole rope.
  546.   public:
  547.     __rope_charT_ref_proxy(my_rope * r, size_t p) :
  548.     pos(p), root(r), current_valid(false) {}
  549.     __rope_charT_ref_proxy(my_rope * r, size_t p,
  550.             charT c) :
  551.     pos(p), root(r), current(c), current_valid(true) {}
  552.     operator charT () const;
  553.     __rope_charT_ref_proxy& operator= (charT c);
  554.     __rope_charT_ptr_proxy<charT,Alloc> operator& () const;
  555.     __rope_charT_ref_proxy& operator= (const __rope_charT_ref_proxy& c) {
  556.     return operator=((charT)c); 
  557.     }
  558. };
  559.  
  560. template<class charT, class Alloc>
  561. class __rope_charT_ptr_proxy {
  562.     friend class __rope_charT_ref_proxy<charT,Alloc>;
  563.     size_t pos;
  564.     charT current;
  565.     bool current_valid;
  566.     rope<charT,Alloc> * root;     // The whole rope.
  567.   public:
  568.     __rope_charT_ptr_proxy(const __rope_charT_ref_proxy<charT,Alloc> & x) :
  569.     pos(x.pos), root(x.root), current_valid(x.current_valid),
  570.     current(x.current) {}
  571.     __rope_charT_ptr_proxy(const __rope_charT_ptr_proxy & x) :
  572.     pos(x.pos), root(x.root), current_valid(x.current_valid),
  573.     current(x.current) {}
  574.     __rope_charT_ptr_proxy() {}
  575.     __rope_charT_ptr_proxy(charT * x) : root(0), pos(0) {
  576.     __stl_assert(0 == x);
  577.     }
  578.     __rope_charT_ptr_proxy& operator= (const __rope_charT_ptr_proxy& x) {
  579.     pos = x.pos;
  580.     current = x.current;
  581.     current_valid = x.current_valid;
  582.     root = x.root;
  583.     return *this;
  584.     }
  585.     friend bool operator== __STL_NULL_TMPL_ARGS
  586.                 (const __rope_charT_ptr_proxy<charT,Alloc> & x,
  587.                  const __rope_charT_ptr_proxy<charT,Alloc> & y);
  588.     __rope_charT_ref_proxy<charT,Alloc> operator *() const {
  589.     if (current_valid) {
  590.         return __rope_charT_ref_proxy<charT,Alloc>(root, pos, current);
  591.     } else {
  592.         return __rope_charT_ref_proxy<charT,Alloc>(root, pos);
  593.     }
  594.     }
  595. };
  596.  
  597. // Rope iterators:
  598. // Unlike in the C version, we cache only part of the stack
  599. // for rope iterators, since they must be efficiently copyable.
  600. // When we run out of cache, we have to reconstruct the iterator
  601. // value.
  602. // Pointers from iterators are not included in reference counts.
  603. // Iterators are assumed to be thread private.  Ropes can
  604. // be shared.
  605.  
  606. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  607. #pragma set woff 1375
  608. #endif
  609.  
  610. template<class charT, class Alloc>
  611. class __rope_iterator_base:
  612.   public random_access_iterator<charT, ptrdiff_t> {
  613.   friend class rope<charT, Alloc>;
  614.   public:
  615.     typedef __rope_RopeBase<charT,Alloc> RopeBase;
  616.     // Borland doesnt want this to be protected.
  617.   protected:
  618.     enum { path_cache_len = 4 }; // Must be <= 9.
  619.     enum { iterator_buf_len = 15 };
  620.     size_t current_pos;
  621.     RopeBase * root;     // The whole rope.
  622.     size_t leaf_pos;    // Starting position for current leaf
  623.     __GC_CONST charT * buf_start;
  624.             // Buffer possibly
  625.             // containing current char.
  626.     __GC_CONST charT * buf_ptr;
  627.             // Pointer to current char in buffer.
  628.             // != 0 ==> buffer valid.
  629.     __GC_CONST charT * buf_end;
  630.             // One past last valid char in buffer.
  631.     // What follows is the path cache.  We go out of our
  632.     // way to make this compact.
  633.     // Path_end contains the bottom section of the path from
  634.     // the root to the current leaf.
  635.     const RopeBase * path_end[path_cache_len];
  636.     int leaf_index;     // Last valid pos in path_end;
  637.                 // path_end[0] ... path_end[leaf_index-1]
  638.             // point to concatenation nodes.
  639.     unsigned char path_directions;
  640.               // (path_directions >> i) & 1 is 1
  641.               // iff we got from path_end[leaf_index - i - 1]
  642.               // to path_end[leaf_index - i] by going to the
  643.               // right. Assumes path_cache_len <= 9.
  644.     charT tmp_buf[iterator_buf_len];
  645.             // Short buffer for surrounding chars.
  646.             // This is useful primarily for 
  647.             // RopeFunctions.  We put the buffer
  648.             // here to avoid locking in the
  649.             // multithreaded case.
  650.     // The cached path is generally assumed to be valid
  651.     // only if the buffer is valid.
  652.     static void setbuf(__rope_iterator_base &x);
  653.                     // Set buffer contents given
  654.                     // path cache.
  655.     static void setcache(__rope_iterator_base &x);
  656.                     // Set buffer contents and
  657.                     // path cache.
  658.     static void setcache_for_incr(__rope_iterator_base &x);
  659.                     // As above, but assumes path
  660.                     // cache is valid for previous posn.
  661.     __rope_iterator_base() {}
  662.     __rope_iterator_base(RopeBase * root, size_t pos):
  663.            root(root), current_pos(pos), buf_ptr(0) {}
  664.     __rope_iterator_base(const __rope_iterator_base& x) {
  665.     if (0 != x.buf_ptr) {
  666.         *this = x;
  667.     } else {
  668.         current_pos = x.current_pos;
  669.         root = x.root;
  670.         buf_ptr = 0;
  671.     }
  672.     }
  673.     void incr(size_t n);
  674.     void decr(size_t n);
  675.   public:
  676.     size_t index() const { return current_pos; }
  677. };
  678.  
  679. template<class charT, class Alloc> class __rope_iterator;
  680.  
  681. template<class charT, class Alloc>
  682. class __rope_const_iterator : public __rope_iterator_base<charT,Alloc> {
  683.     friend class rope<charT,Alloc>;
  684.   protected:
  685.     __rope_const_iterator(const RopeBase * root, size_t pos):
  686.            __rope_iterator_base<charT,Alloc>(
  687.              const_cast<RopeBase *>(root), pos)
  688.            // Only nonconst iterators modify root ref count
  689.     {}
  690.   public:
  691.     typedef charT reference;    // Really a value.  Returning a reference
  692.                 // Would be a mess, since it would have
  693.                 // to be included in refcount.
  694.     typedef const charT* pointer;
  695.  
  696.   public:
  697.     __rope_const_iterator() {};
  698.     __rope_const_iterator(const __rope_const_iterator & x) :
  699.                 __rope_iterator_base<charT,Alloc>(x) { }
  700.     __rope_const_iterator(const __rope_iterator<charT,Alloc> & x);
  701.     __rope_const_iterator(const rope<charT,Alloc> &r, size_t pos) :
  702.     __rope_iterator_base<charT,Alloc>(r.tree_ptr, pos) {}
  703.     __rope_const_iterator& operator= (const __rope_const_iterator & x) {
  704.     if (0 != x.buf_ptr) {
  705.         *this = x;
  706.     } else {
  707.         current_pos = x.current_pos;
  708.         root = x.root;
  709.         buf_ptr = 0;
  710.     }
  711.     return(*this);
  712.     }
  713.     reference operator*() {
  714.     if (0 == buf_ptr) setcache(*this);
  715.     return *buf_ptr;
  716.     }
  717.     __rope_const_iterator& operator++() {
  718.     __GC_CONST charT * next;
  719.     if (0 != buf_ptr && (next = buf_ptr + 1) < buf_end) {
  720.         buf_ptr = next;
  721.         ++current_pos;
  722.     } else {
  723.         incr(1);
  724.     }
  725.     return *this;
  726.     }
  727.     __rope_const_iterator& operator+=(ptrdiff_t n) {
  728.     if (n >= 0) {
  729.         incr(n);
  730.     } else {
  731.         decr(-n);
  732.     }
  733.     return *this;
  734.     }
  735.     __rope_const_iterator& operator--() {
  736.     decr(1);
  737.     return *this;
  738.     }
  739.     __rope_const_iterator& operator-=(ptrdiff_t n) {
  740.     if (n >= 0) {
  741.         decr(n);
  742.     } else {
  743.         incr(-n);
  744.     }
  745.     return *this;
  746.     }
  747.     __rope_const_iterator operator++(int) {
  748.     size_t old_pos = current_pos;
  749.     incr(1);
  750.     return __rope_const_iterator<charT,Alloc>(root, old_pos);
  751.     // This makes a subsequent dereference expensive.
  752.     // Perhaps we should instead copy the iterator
  753.     // if it has a valid cache?
  754.     }
  755.     __rope_const_iterator operator--(int) {
  756.     size_t old_pos = current_pos;
  757.     decr(1);
  758.     return __rope_const_iterator<charT,Alloc>(root, old_pos);
  759.     }
  760.     friend __rope_const_iterator<charT,Alloc> operator- __STL_NULL_TMPL_ARGS
  761.     (const __rope_const_iterator<charT,Alloc> & x,
  762.      ptrdiff_t n);
  763.     friend __rope_const_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  764.     (const __rope_const_iterator<charT,Alloc> & x,
  765.      ptrdiff_t n);
  766.     friend __rope_const_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  767.     (ptrdiff_t n,
  768.      const __rope_const_iterator<charT,Alloc> & x);
  769.     reference operator[](size_t n) {
  770.     return rope<charT,Alloc>::fetch(root, current_pos + n);
  771.     }
  772.     friend bool operator== __STL_NULL_TMPL_ARGS
  773.     (const __rope_const_iterator<charT,Alloc> & x,
  774.      const __rope_const_iterator<charT,Alloc> & y);
  775.     friend bool operator< __STL_NULL_TMPL_ARGS
  776.     (const __rope_const_iterator<charT,Alloc> & x,
  777.      const __rope_const_iterator<charT,Alloc> & y);
  778.     friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
  779.     (const __rope_const_iterator<charT,Alloc> & x,
  780.      const __rope_const_iterator<charT,Alloc> & y);
  781. };
  782.  
  783. template<class charT, class Alloc>
  784. class __rope_iterator : public __rope_iterator_base<charT,Alloc> {
  785.     friend class rope<charT,Alloc>;
  786.   protected:
  787.     rope<charT,Alloc> * root_rope;
  788.     // root is treated as a cached version of this,
  789.     // and is used to detect changes to the underlying
  790.     // rope.
  791.     // Root is included in the reference count.
  792.     // This is necessary so that we can detect changes reliably.
  793.     // Unfortunately, it requires careful bookkeeping for the
  794.     // nonGC case.
  795.     __rope_iterator(rope<charT,Alloc> * r, size_t pos):
  796.          __rope_iterator_base<charT,Alloc>(r -> tree_ptr, pos),
  797.          root_rope(r) {
  798.         RopeBase::ref(root);
  799.          }
  800.     void check();
  801.   public:
  802.     typedef __rope_charT_ref_proxy<charT,Alloc>  reference;
  803.     typedef __rope_charT_ref_proxy<charT,Alloc>* pointer;
  804.  
  805.   public:
  806.     rope<charT,Alloc>& container() { return *root_rope; }
  807.     __rope_iterator() {
  808.     root = 0;  // Needed for reference counting.
  809.     };
  810.     __rope_iterator(const __rope_iterator & x) :
  811.     __rope_iterator_base<charT,Alloc>(x) {
  812.     root_rope = x.root_rope;
  813.     RopeBase::ref(root);
  814.     }
  815.     __rope_iterator(rope<charT,Alloc>& r, size_t pos);
  816.     ~__rope_iterator() {
  817.     RopeBase::unref(root);
  818.     }
  819.     __rope_iterator& operator= (const __rope_iterator & x) {
  820.     RopeBase *old = root;
  821.  
  822.     RopeBase::ref(x.root);
  823.     if (0 != x.buf_ptr) {
  824.         *this = x;
  825.     } else {
  826.         current_pos = x.current_pos;
  827.         root = x.root;
  828.         root_rope = x.root_rope;
  829.         buf_ptr = 0;
  830.     }
  831.     RopeBase::unref(old);
  832.     return(*this);
  833.     }
  834.     reference operator*() {
  835.     check();
  836.     if (0 == buf_ptr) {
  837.         return __rope_charT_ref_proxy<charT,Alloc>(root_rope, current_pos);
  838.     } else {
  839.         return __rope_charT_ref_proxy<charT,Alloc>(root_rope,
  840.                                current_pos, *buf_ptr);
  841.     }
  842.     }
  843.     __rope_iterator& operator++() {
  844.     incr(1);
  845.     return *this;
  846.     }
  847.     __rope_iterator& operator+=(difference_type n) {
  848.     if (n >= 0) {
  849.         incr(n);
  850.     } else {
  851.         decr(-n);
  852.     }
  853.     return *this;
  854.     }
  855.     __rope_iterator& operator--() {
  856.     decr(1);
  857.     return *this;
  858.     }
  859.     __rope_iterator& operator-=(difference_type n) {
  860.     if (n >= 0) {
  861.         decr(n);
  862.     } else {
  863.         incr(-n);
  864.     }
  865.     return *this;
  866.     }
  867.     __rope_iterator operator++(int) {
  868.     size_t old_pos = current_pos;
  869.     incr(1);
  870.     return __rope_iterator<charT,Alloc>(root_rope, old_pos);
  871.     }
  872.     __rope_iterator operator--(int) {
  873.     size_t old_pos = current_pos;
  874.     decr(1);
  875.     return __rope_iterator<charT,Alloc>(root_rope, old_pos);
  876.     }
  877.     reference operator[](ptrdiff_t n) {
  878.     return __rope_charT_ref_proxy<charT,Alloc>(root_rope, current_pos + n);
  879.     }
  880.     friend bool operator== __STL_NULL_TMPL_ARGS
  881.     (const __rope_iterator<charT,Alloc> & x,
  882.      const __rope_iterator<charT,Alloc> & y);
  883.     friend bool operator< __STL_NULL_TMPL_ARGS
  884.     (const __rope_iterator<charT,Alloc> & x,
  885.      const __rope_iterator<charT,Alloc> & y);
  886.     friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
  887.     (const __rope_iterator<charT,Alloc> & x,
  888.      const __rope_iterator<charT,Alloc> & y);
  889.     friend __rope_iterator<charT,Alloc> operator- __STL_NULL_TMPL_ARGS
  890.     (const __rope_iterator<charT,Alloc> & x,
  891.      ptrdiff_t n);
  892.     friend __rope_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  893.     (const __rope_iterator<charT,Alloc> & x,
  894.      ptrdiff_t n);
  895.     friend __rope_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  896.     (ptrdiff_t n,
  897.      const __rope_iterator<charT,Alloc> & x);
  898.  
  899. };
  900.  
  901. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  902. #pragma reset woff 1375
  903. #endif
  904.  
  905. template <class charT, class Alloc>
  906. class rope {
  907.     public:
  908.     typedef charT value_type;
  909.     typedef ptrdiff_t difference_type;
  910.     typedef size_t size_type;
  911.     typedef charT const_reference;
  912.     typedef const charT* const_pointer;
  913.     typedef __rope_iterator<charT,Alloc> iterator;
  914.     typedef __rope_const_iterator<charT,Alloc> const_iterator;
  915.     typedef __rope_charT_ref_proxy<charT,Alloc> reference;
  916.     typedef __rope_charT_ptr_proxy<charT,Alloc> pointer;
  917.  
  918.     friend class __rope_iterator<charT,Alloc>;
  919.     friend class __rope_const_iterator<charT,Alloc>;
  920.     friend struct __rope_RopeBase<charT,Alloc>;
  921.     friend class __rope_iterator_base<charT,Alloc>;
  922.     friend class __rope_charT_ptr_proxy<charT,Alloc>;
  923.     friend class __rope_charT_ref_proxy<charT,Alloc>;
  924.     friend struct __rope_RopeSubstring<charT,Alloc>;
  925.  
  926.     protected:
  927.     typedef __GC_CONST charT * cstrptr;
  928. #       ifdef __STL_SGI_THREADS
  929.         static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  930. #               if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))
  931.                     return (cstrptr) test_and_set((unsigned long *)p,
  932.                                  (unsigned long)q);
  933. #        else
  934.                     return (cstrptr) __test_and_set((unsigned long *)p,
  935.                                    (unsigned long)q);
  936. #        endif
  937.             }
  938. #       elif defined(__STL_WIN32THREADS)
  939.         static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  940.         return (cstrptr) InterlockedExchange((LPLONG)p, (LONG)q);
  941.         }
  942. #    elif defined(__STL_PTHREADS)
  943.         // This should be portable, but performance is expected
  944.         // to be quite awful.  This really needs platform specific
  945.         // code.
  946.         static pthread_mutex_t swap_lock;
  947.         static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  948.         pthread_mutex_lock(&swap_lock);
  949.         cstrptr result = *p;
  950.         *p = q;
  951.         pthread_mutex_unlock(&swap_lock);
  952.         return result;
  953.             }
  954. #    else
  955.         static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  956.                 cstrptr result = *p;
  957.                 *p = q;
  958.         return result;
  959.         }
  960. #       endif
  961.  
  962.     static charT empty_c_str[1];
  963.  
  964.         typedef simple_alloc<charT, Alloc> DataAlloc;
  965.         typedef simple_alloc<__rope_RopeConcatenation<charT,Alloc>, Alloc> CAlloc;
  966.         typedef simple_alloc<__rope_RopeLeaf<charT,Alloc>, Alloc> LAlloc;
  967.         typedef simple_alloc<__rope_RopeFunction<charT,Alloc>, Alloc> FAlloc;
  968.         typedef simple_alloc<__rope_RopeSubstring<charT,Alloc>, Alloc> SAlloc;
  969.     static bool is0(charT c) { return c == __eos((charT *)0); }
  970.     enum { copy_max = 23 };
  971.         // For strings shorter than copy_max, we copy to
  972.         // concatenate.
  973.  
  974.     typedef __rope_RopeBase<charT,Alloc> RopeBase;
  975.     typedef __rope_RopeConcatenation<charT,Alloc> RopeConcatenation;
  976.     typedef __rope_RopeLeaf<charT,Alloc> RopeLeaf;
  977.     typedef __rope_RopeFunction<charT,Alloc> RopeFunction;
  978.     typedef __rope_RopeSubstring<charT,Alloc> RopeSubstring;
  979.  
  980.     // The only data member of a rope:
  981.     RopeBase *tree_ptr;
  982.  
  983.     // Retrieve a character at the indicated position.
  984.     static charT fetch(RopeBase * r, size_type pos);
  985.  
  986. #    ifndef __GC
  987.         // Obtain a pointer to the character at the indicated position.
  988.         // The pointer can be used to change the character.
  989.         // If such a pointer cannot be produced, as is frequently the
  990.         // case, 0 is returned instead.
  991.         // (Returns nonzero only if all nodes in the path have a refcount
  992.         // of 1.)
  993.         static charT * fetch_ptr(RopeBase * r, size_type pos);
  994. #    endif
  995.  
  996.     static bool apply_to_pieces(
  997.                 // should be template parameter
  998.                 __rope_char_consumer<charT>& c,
  999.                 const RopeBase * r,
  1000.                 size_t begin, size_t end);
  1001.                 // begin and end are assumed to be in range.
  1002.  
  1003. #    ifndef __GC
  1004.       static void unref(RopeBase* t)
  1005.       {
  1006.           RopeBase::unref(t);
  1007.       }
  1008.       static void ref(RopeBase* t)
  1009.       {
  1010.           RopeBase::ref(t);
  1011.       }
  1012. #       else /* __GC */
  1013.       static void unref(RopeBase* t) {}
  1014.       static void ref(RopeBase* t) {}
  1015. #       endif
  1016.  
  1017.  
  1018. #       ifdef __GC
  1019.         typedef __rope_RopeBase<charT,Alloc> * self_destruct_ptr;
  1020. #       else
  1021.         typedef __rope_self_destruct_ptr<charT,Alloc> self_destruct_ptr;
  1022. #    endif
  1023.  
  1024.     // Result is counted in refcount.
  1025.     static RopeBase * substring(RopeBase * base,
  1026.                     size_t start, size_t endp1);
  1027.  
  1028.     static RopeBase * concat_char_iter(RopeBase * r,
  1029.                       const charT *iter, size_t slen);
  1030.         // Concatenate rope and char ptr, copying s.
  1031.         // Should really take an arbitrary iterator.
  1032.         // Result is counted in refcount.
  1033.     static RopeBase * destr_concat_char_iter(RopeBase * r,
  1034.                          const charT *iter, size_t slen)
  1035.         // As above, but one reference to r is about to be
  1036.         // destroyed.  Thus the pieces may be recycled if all
  1037.         // relevent reference counts are 1.
  1038. #        ifdef __GC
  1039.         // We can't really do anything since refcounts are unavailable.
  1040.         { return concat_char_iter(r, iter, slen); }
  1041. #        else
  1042.         ;
  1043. #        endif
  1044.  
  1045.     static RopeBase * concat(RopeBase *left, RopeBase *right);
  1046.         // General concatenation on RopeBase.  Result
  1047.         // has refcount of 1.  Adjusts argument refcounts.
  1048.  
  1049.    public:
  1050.     void apply_to_pieces( size_t begin, size_t end,
  1051.                   __rope_char_consumer<charT>& c) const {
  1052.         apply_to_pieces(c, tree_ptr, begin, end);
  1053.     }
  1054.  
  1055.  
  1056.    protected:
  1057.  
  1058.     static size_t rounded_up_size(size_t n) {
  1059.         return RopeBase::rounded_up_size(n);
  1060.     }
  1061.  
  1062.     static size_t allocated_capacity(size_t n) {
  1063.         if (__is_basic_char_type((charT *)0)) {
  1064.         return rounded_up_size(n) - 1;
  1065.         } else {
  1066.         return rounded_up_size(n);
  1067.         }
  1068.     }
  1069.         
  1070.     // s should really be an arbitrary input iterator.
  1071.     // Adds a trailing NULL for basic char types.
  1072.     static charT * alloc_copy(const charT *s, size_t size)
  1073.     {
  1074.         charT * result = DataAlloc::allocate(rounded_up_size(size));
  1075.  
  1076.         uninitialized_copy_n(s, size, result);
  1077.         __cond_store_eos(result[size]);
  1078.         return(result);
  1079.     }
  1080.  
  1081.     // Basic constructors for rope tree nodes.
  1082.     // These return tree nodes with a 0 reference count.
  1083.     static RopeLeaf * RopeLeaf_from_char_ptr(__GC_CONST charT *s,
  1084.                          size_t size);
  1085.         // Takes ownership of its argument.
  1086.         // Result has refcount 1.
  1087.         // In the nonGC, basic_char_type  case it assumes that s
  1088.         // is eos-terminated.
  1089.         // In the nonGC case, it was allocated from Alloc with
  1090.         // rounded_up_size(size).
  1091.  
  1092.     static RopeLeaf * RopeLeaf_from_unowned_char_ptr(const charT *s,
  1093.                                  size_t size) {
  1094.         charT * buf = alloc_copy(s, size);
  1095.             __STL_TRY {
  1096.               return RopeLeaf_from_char_ptr(buf, size);
  1097.             }
  1098.             __STL_UNWIND(RopeBase::free_string(buf, size))
  1099.     }
  1100.         
  1101.  
  1102.     // Concatenation of nonempty strings.
  1103.     // Always builds a concatenation node.
  1104.     // Rebalances if the result is too deep.
  1105.     // Result has refcount 1.
  1106.     // Does not increment left and right ref counts even though
  1107.     // they are referenced.
  1108.     static RopeBase * tree_concat(RopeBase * left, RopeBase * right);
  1109.  
  1110.     // Result has refcount 1.
  1111.     // If delete_fn is true, then fn is deleted when the rope
  1112.     // becomes inaccessible.
  1113.     static RopeFunction * RopeFunction_from_fn
  1114.             (char_producer<charT> *fn, size_t size,
  1115.              bool delete_fn);
  1116.  
  1117.     // Concatenation helper functions
  1118.     static RopeLeaf * leaf_concat_char_iter
  1119.             (RopeLeaf * r, const charT * iter, size_t slen);
  1120.         // Concatenate by copying leaf.
  1121.         // should take an arbitrary iterator
  1122.         // result has refcount 1.
  1123. #    ifndef __GC
  1124.       static RopeLeaf * destr_leaf_concat_char_iter
  1125.             (RopeLeaf * r, const charT * iter, size_t slen);
  1126.       // A version that potentially clobbers r if r -> refcount == 1.
  1127. #       endif
  1128.  
  1129.     // A helper function for exponentiating strings.
  1130.     // This uses a nonstandard refcount convention.
  1131.     // The result has refcount 0.
  1132.     struct concat_fn;
  1133.     friend struct rope<charT,Alloc>::concat_fn;
  1134.  
  1135.     struct concat_fn
  1136.         : public binary_function<rope<charT,Alloc>, rope<charT,Alloc>,
  1137.                          rope<charT,Alloc> > {
  1138.         rope operator() (const rope& x, const rope& y) {
  1139.             return x + y;
  1140.         }
  1141.     };
  1142.  
  1143.         friend rope identity_element(concat_fn) { return rope<charT,Alloc>(); }
  1144.  
  1145.     static size_t char_ptr_len(const charT * s);
  1146.             // slightly generalized strlen
  1147.  
  1148.     rope(RopeBase *t) : tree_ptr(t) { }
  1149.  
  1150.  
  1151.     // Copy r to the CharT buffer.
  1152.     // Returns buffer + r -> size.
  1153.     // Assumes that buffer is uninitialized.
  1154.     static charT * flatten(RopeBase * r, charT * buffer);
  1155.  
  1156.     // Again, with explicit starting position and length.
  1157.     // Assumes that buffer is uninitialized.
  1158.     static charT * flatten(RopeBase * r,
  1159.                    size_t start, size_t len,
  1160.                    charT * buffer);
  1161.  
  1162.     static const unsigned long min_len[RopeBase::max_rope_depth + 1];
  1163.  
  1164.     static bool is_balanced(RopeBase *r)
  1165.         { return (r -> size >= min_len[r -> depth]); }
  1166.  
  1167.     static bool is_almost_balanced(RopeBase *r)
  1168.         { return (r -> depth == 0 ||
  1169.               r -> size >= min_len[r -> depth - 1]); }
  1170.  
  1171.     static bool is_roughly_balanced(RopeBase *r)
  1172.         { return (r -> depth <= 1 ||
  1173.               r -> size >= min_len[r -> depth - 2]); }
  1174.  
  1175.     // Assumes the result is not empty.
  1176.     static RopeBase * concat_and_set_balanced(RopeBase *left,
  1177.                           RopeBase *right)
  1178.     {
  1179.         RopeBase * result = concat(left, right);
  1180.         if (is_balanced(result)) result -> is_balanced = true;
  1181.         return result;
  1182.     }
  1183.  
  1184.     // The basic rebalancing operation.  Logically copies the
  1185.     // rope.  The result has refcount of 1.  The client will
  1186.     // usually decrement the reference count of r.
  1187.     // The result isd within height 2 of balanced by the above
  1188.     // definition.
  1189.     static RopeBase * balance(RopeBase * r);
  1190.  
  1191.     // Add all unbalanced subtrees to the forest of balanceed trees.
  1192.     // Used only by balance.
  1193.     static void add_to_forest(RopeBase *r, RopeBase **forest);
  1194.     
  1195.     // Add r to forest, assuming r is already balanced.
  1196.     static void add_leaf_to_forest(RopeBase *r, RopeBase **forest);
  1197.  
  1198.     // Print to stdout, exposing structure
  1199.     static void dump(RopeBase * r, int indent = 0);
  1200.  
  1201.     // Return -1, 0, or 1 if x < y, x == y, or x > y resp.
  1202.     static int compare(const RopeBase *x, const RopeBase *y);
  1203.  
  1204.    public:
  1205.     bool empty() const { return 0 == tree_ptr; }
  1206.  
  1207.     // Comparison member function.  This is public only for those
  1208.     // clients that need a ternary comparison.  Others
  1209.     // should use the comparison operators below.
  1210.     int compare(const rope &y) const {
  1211.         return compare(tree_ptr, y.tree_ptr);
  1212.     }
  1213.  
  1214.     rope(const charT *s)
  1215.     {
  1216.         size_t len = char_ptr_len(s);
  1217.  
  1218.         if (0 == len) {
  1219.         tree_ptr = 0;
  1220.         } else {
  1221.         tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
  1222. #        ifndef __GC
  1223.           __stl_assert(1 == tree_ptr -> refcount);
  1224. #        endif
  1225.         }
  1226.     }
  1227.  
  1228.     rope(const charT *s, size_t len)
  1229.     {
  1230.         if (0 == len) {
  1231.         tree_ptr = 0;
  1232.         } else {
  1233.         tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
  1234.         }
  1235.     }
  1236.  
  1237.     rope(const charT *s, charT *e)
  1238.     {
  1239.         size_t len = e - s;
  1240.  
  1241.         if (0 == len) {
  1242.         tree_ptr = 0;
  1243.         } else {
  1244.         tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
  1245.         }
  1246.     }
  1247.  
  1248.     rope(const const_iterator& s, const const_iterator& e)
  1249.     {
  1250.         tree_ptr = substring(s.root, s.current_pos, e.current_pos);
  1251.     }
  1252.  
  1253.     rope(const iterator& s, const iterator& e)
  1254.     {
  1255.         tree_ptr = substring(s.root, s.current_pos, e.current_pos);
  1256.     }
  1257.  
  1258.     rope(charT c)
  1259.     {
  1260.         charT * buf = DataAlloc::allocate(rounded_up_size(1));
  1261.  
  1262.         construct(buf, c);
  1263.         __STL_TRY {
  1264.             tree_ptr = RopeLeaf_from_char_ptr(buf, 1);
  1265.             }
  1266.             __STL_UNWIND(RopeBase::free_string(buf, 1))
  1267.     }
  1268.  
  1269.     rope(size_t n, charT c);
  1270.  
  1271.     // Should really be templatized with respect to the iterator type
  1272.     // and use sequence_buffer.  (It should perhaps use sequence_buffer
  1273.     // even now.)
  1274.     rope(const charT *i, const charT *j)
  1275.     {
  1276.         if (i == j) {
  1277.         tree_ptr = 0;
  1278.         } else {
  1279.         size_t len = j - i;
  1280.         tree_ptr = RopeLeaf_from_unowned_char_ptr(i, len);
  1281.         }
  1282.     }
  1283.  
  1284.     rope()
  1285.     {
  1286.         tree_ptr = 0;
  1287.     }
  1288.  
  1289.     // Construct a rope from a function that can compute its members
  1290.     rope(char_producer<charT> *fn, size_t len, bool delete_fn)
  1291.     {
  1292.         tree_ptr = RopeFunction_from_fn(fn, len, delete_fn);
  1293.     }
  1294.  
  1295.     rope(const rope &x)
  1296.     {
  1297.         tree_ptr = x.tree_ptr;
  1298.         ref(tree_ptr);
  1299.     }
  1300.  
  1301.     ~rope()
  1302.     {
  1303.         unref(tree_ptr);
  1304.     }
  1305.  
  1306.     rope& operator=(const rope& x)
  1307.     {
  1308.         RopeBase *old = tree_ptr;
  1309.         tree_ptr = x.tree_ptr;
  1310.         ref(tree_ptr);
  1311.         unref(old);
  1312.         return(*this);
  1313.     }
  1314.  
  1315.     void push_back(charT x)
  1316.     {
  1317.         RopeBase *old = tree_ptr;
  1318.         tree_ptr = concat_char_iter(tree_ptr, &x, 1);
  1319.         unref(old);
  1320.     }
  1321.  
  1322.     void pop_back()
  1323.     {
  1324.         RopeBase *old = tree_ptr;
  1325.         tree_ptr = substring(tree_ptr, 0, tree_ptr -> size - 1);
  1326.         unref(old);
  1327.     }
  1328.  
  1329.     charT back() const
  1330.     {
  1331.         return fetch(tree_ptr, tree_ptr -> size - 1);
  1332.     }
  1333.  
  1334.     void push_front(charT x)
  1335.     {
  1336.         RopeBase *old = tree_ptr;
  1337.         RopeBase *left;
  1338.  
  1339.         left = RopeLeaf_from_unowned_char_ptr(&x, 1);
  1340.         __STL_TRY {
  1341.           tree_ptr = concat(left, tree_ptr);
  1342.           unref(old);
  1343.               unref(left);
  1344.             }
  1345.         __STL_UNWIND(unref(left))
  1346.     }
  1347.  
  1348.     void pop_front()
  1349.     {
  1350.         RopeBase *old = tree_ptr;
  1351.         tree_ptr = substring(tree_ptr, 1, tree_ptr -> size);
  1352.         unref(old);
  1353.     }
  1354.  
  1355.     charT front() const
  1356.     {
  1357.         return fetch(tree_ptr, 0);
  1358.     }
  1359.  
  1360.     void balance()
  1361.     {
  1362.         RopeBase *old = tree_ptr;
  1363.         tree_ptr = balance(tree_ptr);
  1364.         unref(old);
  1365.     }
  1366.  
  1367.     void copy(charT * buffer) const {
  1368.         destroy(buffer, buffer + size());
  1369.         flatten(tree_ptr, buffer);
  1370.     }
  1371.  
  1372.     // This is the copy function from the standard, but
  1373.     // with the arguments reordered to make it consistent with the
  1374.     // rest of the interface.
  1375.     // Note that this guaranteed not to compile if the draft standard
  1376.     // order is assumed.
  1377.     size_type copy(size_type pos, size_type n, charT *buffer) const {
  1378.         size_t sz = size();
  1379.         size_t len = (pos + n > sz? sz - pos : n);
  1380.  
  1381.         destroy(buffer, buffer + len);
  1382.         flatten(tree_ptr, pos, len, buffer);
  1383.         return len;
  1384.     }
  1385.  
  1386.     // Print to stdout, exposing structure.  May be useful for
  1387.     // performance debugging.
  1388.     void dump() {
  1389.         dump(tree_ptr);
  1390.     }
  1391.  
  1392.     // Convert to 0 terminated string in new allocated memory.
  1393.     // Embedded 0s in the input do not terminate the copy.
  1394.     const charT * c_str() const;
  1395.  
  1396.     // As above, but lso use the flattened representation as the
  1397.     // the new rope representation.
  1398.     const charT * replace_with_c_str();
  1399.  
  1400.     // Reclaim memory for the c_str generated flattened string.
  1401.     // Intentionally undocumented, since it's hard to say when this
  1402.     // is safe for multiple threads.
  1403.     void delete_c_str () {
  1404.         if (0 == tree_ptr) return;
  1405.         if (RopeBase::leaf == tree_ptr -> tag
  1406.         && ((RopeLeaf *)tree_ptr) -> data == tree_ptr -> c_string) {
  1407.         // Representation shared
  1408.         return;
  1409.         }
  1410. #        ifndef __GC
  1411.           tree_ptr -> free_c_string();
  1412. #        endif
  1413.         tree_ptr -> c_string = 0;
  1414.     }
  1415.  
  1416.     charT operator[] (size_type pos) const {
  1417.         return fetch(tree_ptr, pos);
  1418.     }
  1419.  
  1420.     charT at(size_type pos) const {
  1421.        // if (pos >= size()) throw out_of_range;
  1422.        return (*this)[pos];
  1423.     }
  1424.  
  1425.     const_iterator begin() const {
  1426.         return(const_iterator(tree_ptr, 0));
  1427.     }
  1428.  
  1429.     // An easy way to get a const iterator from a non-const container.
  1430.     const_iterator const_begin() const {
  1431.         return(const_iterator(tree_ptr, 0));
  1432.     }
  1433.  
  1434.     const_iterator end() const {
  1435.         return(const_iterator(tree_ptr, size()));
  1436.     }
  1437.  
  1438.     const_iterator const_end() const {
  1439.         return(const_iterator(tree_ptr, size()));
  1440.     }
  1441.  
  1442.     size_type size() const { 
  1443.         return(0 == tree_ptr? 0 : tree_ptr -> size);
  1444.     }
  1445.  
  1446.     size_type length() const {
  1447.         return size();
  1448.     }
  1449.  
  1450.     size_type max_size() const {
  1451.         return min_len[RopeBase::max_rope_depth-1] - 1;
  1452.         //  Guarantees that the result can be sufficirntly
  1453.         //  balanced.  Longer ropes will probably still work,
  1454.         //  but it's harder to make guarantees.
  1455.     }
  1456.  
  1457. #     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  1458.         typedef reverse_iterator<const_iterator> const_reverse_iterator;
  1459. #     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  1460.     typedef reverse_iterator<const_iterator, value_type, const_reference,
  1461.                  difference_type>  const_reverse_iterator;
  1462. #     endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  1463.  
  1464.     const_reverse_iterator rbegin() const {
  1465.         return const_reverse_iterator(end());
  1466.     }
  1467.  
  1468.     const_reverse_iterator const_rbegin() const {
  1469.         return const_reverse_iterator(end());
  1470.     }
  1471.  
  1472.     const_reverse_iterator rend() const {
  1473.         return const_reverse_iterator(begin());
  1474.     }
  1475.  
  1476.     const_reverse_iterator const_rend() const {
  1477.         return const_reverse_iterator(begin());
  1478.     }
  1479.  
  1480.     friend rope<charT,Alloc>
  1481.         operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
  1482.                                         const rope<charT,Alloc> &right);
  1483.     
  1484.     friend rope<charT,Alloc>
  1485.         operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
  1486.                                         const charT* right);
  1487.     
  1488.     friend rope<charT,Alloc>
  1489.         operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
  1490.                                         charT right);
  1491.     
  1492.     // The symmetric cases are intentionally omitted, since they're presumed
  1493.     // to be less common, and we don't handle them as well.
  1494.  
  1495.     // The following should really be templatized.
  1496.     // The first argument should be an input iterator or
  1497.     // forward iterator with value_type charT.
  1498.     rope& append(const charT* iter, size_t n) {
  1499.         RopeBase* result = destr_concat_char_iter(tree_ptr, iter, n);
  1500.         unref(tree_ptr);
  1501.         tree_ptr = result;
  1502.         return *this;
  1503.     }
  1504.  
  1505.     rope& append(const charT* c_string) {
  1506.         size_t len = char_ptr_len(c_string);
  1507.         append(c_string, len);
  1508.         return(*this);
  1509.     }
  1510.  
  1511.     rope& append(const charT* s, const charT* e) {
  1512.         RopeBase* result =
  1513.             destr_concat_char_iter(tree_ptr, s, e - s);
  1514.         unref(tree_ptr);
  1515.         tree_ptr = result;
  1516.         return *this;
  1517.     }
  1518.  
  1519.     rope& append(const_iterator s, const_iterator e) {
  1520.         __stl_assert(s.root == e.root);
  1521.         self_destruct_ptr appendee(substring(s.root, s.current_pos,
  1522.                          e.current_pos));
  1523.         RopeBase* result = concat(tree_ptr, (RopeBase *)appendee);
  1524.         unref(tree_ptr);
  1525.         tree_ptr = result;
  1526.         return *this;
  1527.     }
  1528.  
  1529.     rope& append(charT c) {
  1530.         RopeBase* result = destr_concat_char_iter(tree_ptr, &c, 1);
  1531.         unref(tree_ptr);
  1532.         tree_ptr = result;
  1533.         return *this;
  1534.     }
  1535.  
  1536.     rope& append() { return append(charT()); }
  1537.  
  1538.     rope& append(const rope& y) {
  1539.         RopeBase* result = concat(tree_ptr, y.tree_ptr);
  1540.         unref(tree_ptr);
  1541.         tree_ptr = result;
  1542.         return *this;
  1543.     }
  1544.  
  1545.     rope& append(size_t n, charT c) {
  1546.         rope<charT,Alloc> last(n, c);
  1547.         return append(last);
  1548.     }
  1549.  
  1550.     void swap(rope& b) {
  1551.         RopeBase * tmp = tree_ptr;
  1552.         tree_ptr = b.tree_ptr;
  1553.         b.tree_ptr = tmp;
  1554.     }
  1555.  
  1556.  
  1557.     protected:
  1558.     // Result is included in refcount.
  1559.     static RopeBase * replace(RopeBase *old, size_t pos1,
  1560.                   size_t pos2, RopeBase *r) {
  1561.         if (0 == old) { ref(r); return r; }
  1562.         self_destruct_ptr left(substring(old, 0, pos1));
  1563.         self_destruct_ptr right(substring(old, pos2, old -> size));
  1564.         RopeBase * result;
  1565.  
  1566.         if (0 == r) {
  1567.         result = concat(left, right);
  1568.         } else {
  1569.         self_destruct_ptr left_result(concat(left, r));
  1570.         result = concat(left_result, right);
  1571.         }
  1572.         return result;
  1573.     }
  1574.  
  1575.     public:
  1576.     void insert(size_t p, const rope& r) {
  1577.         RopeBase * result = replace(tree_ptr, p, p,
  1578.                            r.tree_ptr);
  1579.         unref(tree_ptr);
  1580.         tree_ptr = result;
  1581.     }
  1582.  
  1583.     void insert(size_t p, size_t n, charT c) {
  1584.         rope<charT,Alloc> r(n,c);
  1585.         insert(p, r);
  1586.     }
  1587.  
  1588.     void insert(size_t p, const charT * i, size_t n) {
  1589.         self_destruct_ptr left(substring(tree_ptr, 0, p));
  1590.         self_destruct_ptr right(substring(tree_ptr, p, size()));
  1591.         self_destruct_ptr left_result(concat_char_iter(left, i, n));
  1592.         RopeBase * result =
  1593.                 concat(left_result, right);
  1594.         unref(tree_ptr);
  1595.         tree_ptr = result;
  1596.     }
  1597.  
  1598.     void insert(size_t p, const charT * c_string) {
  1599.         insert(p, c_string, char_ptr_len(c_string));
  1600.     }
  1601.  
  1602.     void insert(size_t p, charT c) {
  1603.         insert(p, &c, 1);
  1604.     }
  1605.  
  1606.     void insert(size_t p) {
  1607.         charT c = charT();
  1608.         insert(p, &c, 1);
  1609.     }
  1610.  
  1611.     void insert(size_t p, const charT *i, const charT *j) {
  1612.         rope r(i, j);
  1613.         insert(p, r);
  1614.     }
  1615.  
  1616.     void insert(size_t p, const const_iterator& i,
  1617.                   const const_iterator& j) {
  1618.         rope r(i, j);
  1619.         insert(p, r);
  1620.     }
  1621.  
  1622.     void insert(size_t p, const iterator& i,
  1623.                   const iterator& j) {
  1624.         rope r(i, j);
  1625.         insert(p, r);
  1626.     }
  1627.  
  1628.     // (position, length) versions of replace operations:
  1629.  
  1630.     void replace(size_t p, size_t n, const rope& r) {
  1631.         RopeBase * result = replace(tree_ptr, p, p + n,
  1632.                            r.tree_ptr);
  1633.         unref(tree_ptr);
  1634.         tree_ptr = result;
  1635.     }
  1636.  
  1637.     void replace(size_t p, size_t n, const charT *i, size_t i_len) {
  1638.         rope r(i, i_len);
  1639.         replace(p, n, r);
  1640.     }
  1641.  
  1642.     void replace(size_t p, size_t n, charT c) {
  1643.         rope r(c);
  1644.         replace(p, n, r);
  1645.     }
  1646.  
  1647.     void replace(size_t p, size_t n, const charT *c_string) {
  1648.         rope r(c_string);
  1649.         replace(p, n, r);
  1650.     }
  1651.  
  1652.     void replace(size_t p, size_t n, const charT *i, const charT *j) {
  1653.         rope r(i, j);
  1654.         replace(p, n, r);
  1655.     }
  1656.  
  1657.     void replace(size_t p, size_t n,
  1658.              const const_iterator& i, const const_iterator& j) {
  1659.         rope r(i, j);
  1660.         replace(p, n, r);
  1661.     }
  1662.  
  1663.     void replace(size_t p, size_t n,
  1664.              const iterator& i, const iterator& j) {
  1665.         rope r(i, j);
  1666.         replace(p, n, r);
  1667.     }
  1668.  
  1669.     // Single character variants:
  1670.     void replace(size_t p, charT c) {
  1671.         iterator i(this, p);
  1672.         *i = c;
  1673.     }
  1674.  
  1675.     void replace(size_t p, const rope& r) {
  1676.         replace(p, 1, r);
  1677.     }
  1678.  
  1679.     void replace(size_t p, const charT *i, size_t i_len) {
  1680.         replace(p, 1, i, i_len);
  1681.     }
  1682.  
  1683.     void replace(size_t p, const charT *c_string) {
  1684.         replace(p, 1, c_string);
  1685.     }
  1686.  
  1687.     void replace(size_t p, const charT *i, const charT *j) {
  1688.         replace(p, 1, i, j);
  1689.     }
  1690.  
  1691.     void replace(size_t p, const const_iterator& i,
  1692.                    const const_iterator& j) {
  1693.         replace(p, 1, i, j);
  1694.     }
  1695.  
  1696.     void replace(size_t p, const iterator& i,
  1697.                    const iterator& j) {
  1698.         replace(p, 1, i, j);
  1699.     }
  1700.  
  1701.     // Erase, (position, size) variant.
  1702.     void erase(size_t p, size_t n) {
  1703.         RopeBase * result = replace(tree_ptr, p, p + n, 0);
  1704.         unref(tree_ptr);
  1705.         tree_ptr = result;
  1706.     }
  1707.  
  1708.     // Erase, single character
  1709.     void erase(size_t p) {
  1710.         erase(p, p + 1);
  1711.     }
  1712.  
  1713.     // Insert, iterator variants.  
  1714.     iterator insert(const iterator& p, const rope& r)
  1715.         { insert(p.index(), r); return p; }
  1716.     iterator insert(const iterator& p, size_t n, charT c)
  1717.         { insert(p.index(), n, c); return p; }
  1718.     iterator insert(const iterator& p, charT c) 
  1719.         { insert(p.index(), c); return p; }
  1720.     iterator insert(const iterator& p ) 
  1721.         { insert(p.index()); return p; }
  1722.     iterator insert(const iterator& p, const charT *c_string) 
  1723.         { insert(p.index(), c_string); return p; }
  1724.     iterator insert(const iterator& p, const charT *i, size_t n)
  1725.         { insert(p.index(), i, n); return p; }
  1726.     iterator insert(const iterator& p, const charT *i, const charT *j)
  1727.         { insert(p.index(), i, j);  return p; }
  1728.     iterator insert(const iterator& p,
  1729.             const const_iterator& i, const const_iterator& j)
  1730.         { insert(p.index(), i, j); return p; }
  1731.     iterator insert(const iterator& p,
  1732.             const iterator& i, const iterator& j)
  1733.         { insert(p.index(), i, j); return p; }
  1734.  
  1735.     // Replace, range variants.
  1736.     void replace(const iterator& p, const iterator& q,
  1737.              const rope& r)
  1738.         { replace(p.index(), q.index() - p.index(), r); }
  1739.     void replace(const iterator& p, const iterator& q, charT c)
  1740.         { replace(p.index(), q.index() - p.index(), c); }
  1741.     void replace(const iterator& p, const iterator& q,
  1742.              const charT * c_string)
  1743.         { replace(p.index(), q.index() - p.index(), c_string); }
  1744.     void replace(const iterator& p, const iterator& q,
  1745.              const charT *i, size_t n)
  1746.         { replace(p.index(), q.index() - p.index(), i, n); }
  1747.     void replace(const iterator& p, const iterator& q,
  1748.              const charT *i, const charT *j)
  1749.         { replace(p.index(), q.index() - p.index(), i, j); }
  1750.     void replace(const iterator& p, const iterator& q,
  1751.              const const_iterator& i, const const_iterator& j)
  1752.         { replace(p.index(), q.index() - p.index(), i, j); }
  1753.     void replace(const iterator& p, const iterator& q,
  1754.              const iterator& i, const iterator& j)
  1755.         { replace(p.index(), q.index() - p.index(), i, j); }
  1756.  
  1757.     // Replace, iterator variants.
  1758.     void replace(const iterator& p, const rope& r)
  1759.         { replace(p.index(), r); }
  1760.     void replace(const iterator& p, charT c)
  1761.         { replace(p.index(), c); }
  1762.     void replace(const iterator& p, const charT * c_string)
  1763.         { replace(p.index(), c_string); }
  1764.     void replace(const iterator& p, const charT *i, size_t n)
  1765.         { replace(p.index(), i, n); }
  1766.     void replace(const iterator& p, const charT *i, const charT *j)
  1767.         { replace(p.index(), i, j); }
  1768.     void replace(const iterator& p, const_iterator i, const_iterator j)
  1769.         { replace(p.index(), i, j); }
  1770.     void replace(const iterator& p, iterator i, iterator j)
  1771.         { replace(p.index(), i, j); }
  1772.  
  1773.     // Iterator and range variants of erase
  1774.     iterator erase(const iterator &p, const iterator &q) {
  1775.             size_t p_index = p.index();
  1776.             erase(p_index, q.index() - p_index);
  1777.             return iterator(this, p_index);
  1778.         }
  1779.         iterator erase(const iterator &p) {
  1780.             size_t p_index = p.index();
  1781.             erase(p_index, 1);
  1782.             return iterator(this, p_index);
  1783.         }
  1784.  
  1785.     rope substr(size_t start, size_t len = 1) const {
  1786.         return rope<charT,Alloc>(
  1787.             substring(tree_ptr, start, start + len));
  1788.     }
  1789.  
  1790.     rope substr(iterator start, iterator end) const {
  1791.         return rope<charT,Alloc>(
  1792.             substring(tree_ptr, start.index(), end.index()));
  1793.     }
  1794.     
  1795.     rope substr(iterator start) const {
  1796.         size_t pos = start.index();
  1797.         return rope<charT,Alloc>(
  1798.             substring(tree_ptr, pos, pos + 1));
  1799.     }
  1800.     
  1801.     rope substr(const_iterator start, const_iterator end) const {
  1802.         // This might eventually take advantage of the cache in the
  1803.         // iterator.
  1804.         return rope<charT,Alloc>
  1805.         (substring(tree_ptr, start.index(), end.index()));
  1806.     }
  1807.  
  1808.     rope<charT,Alloc> substr(const_iterator start) {
  1809.         size_t pos = start.index();
  1810.         return rope<charT,Alloc>(substring(tree_ptr, pos, pos + 1));
  1811.     }
  1812.  
  1813.     size_type find(charT c, size_type pos = 0) const;
  1814.     size_type find(charT *s, size_type pos = 0) const {
  1815.         const_iterator result = search(const_begin() + pos, const_end(),
  1816.                        s, s + char_ptr_len(s));
  1817.         return result.index();
  1818.     }
  1819.  
  1820.     iterator mutable_begin() {
  1821.         return(iterator(this, 0));
  1822.     }
  1823.  
  1824.     iterator mutable_end() {
  1825.         return(iterator(this, size()));
  1826.     }
  1827.  
  1828. #     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  1829.         typedef reverse_iterator<iterator> reverse_iterator;
  1830. #     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  1831.     typedef reverse_iterator<iterator, value_type, reference,
  1832.                  difference_type>  reverse_iterator;
  1833. #     endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  1834.  
  1835.     reverse_iterator mutable_rbegin() {
  1836.         return reverse_iterator(mutable_end());
  1837.     }
  1838.  
  1839.     reverse_iterator mutable_rend() {
  1840.         return reverse_iterator(mutable_begin());
  1841.     }
  1842.  
  1843.     reference mutable_reference_at(size_type pos) {
  1844.         return reference(this, pos);
  1845.     }
  1846.  
  1847. #    ifdef __STD_STUFF
  1848.         reference operator[] (size_type pos) {
  1849.         return charT_ref_proxy(this, pos);
  1850.         }
  1851.  
  1852.         reference at(size_type pos) {
  1853.         // if (pos >= size()) throw out_of_range;
  1854.         return (*this)[pos];
  1855.         }
  1856.  
  1857.         void resize(size_type n, charT c) {}
  1858.         void resize(size_type n) {}
  1859.         void reserve(size_type res_arg = 0) {}
  1860.         size_type capacity() const {
  1861.         return max_size();
  1862.         }
  1863.  
  1864.       // Stuff below this line is dangerous because it's error prone.
  1865.       // I would really like to get rid of it.
  1866.         // copy function with funny arg ordering.
  1867.           size_type copy(charT *buffer, size_type n, size_type pos = 0)
  1868.                                 const {
  1869.         return copy(pos, n, buffer);
  1870.           }
  1871.  
  1872.         iterator end() { return mutable_end(); }
  1873.  
  1874.         iterator begin() { return mutable_begin(); }
  1875.  
  1876.         reverse_iterator rend() { return mutable_rend(); }
  1877.  
  1878.         reverse_iterator rbegin() { return mutable_rbegin(); }
  1879.  
  1880. #    else
  1881.  
  1882.         const_iterator end() { return const_end(); }
  1883.  
  1884.         const_iterator begin() { return const_begin(); }
  1885.  
  1886.         const_reverse_iterator rend() { return const_rend(); }
  1887.   
  1888.         const_reverse_iterator rbegin() { return const_rbegin(); }
  1889.  
  1890. #    endif
  1891.     
  1892. };
  1893.  
  1894. template <class charT, class Alloc>
  1895. inline bool operator== (const __rope_const_iterator<charT,Alloc> & x,
  1896.             const __rope_const_iterator<charT,Alloc> & y) {
  1897.     return (x.current_pos == y.current_pos && x.root == y.root);
  1898. }
  1899.  
  1900. template <class charT, class Alloc>
  1901. inline bool operator< (const __rope_const_iterator<charT,Alloc> & x,
  1902.                const __rope_const_iterator<charT,Alloc> & y) {
  1903.     return (x.current_pos < y.current_pos);
  1904. }
  1905.  
  1906. template <class charT, class Alloc>
  1907. inline ptrdiff_t operator-(const __rope_const_iterator<charT,Alloc> & x,
  1908.                const __rope_const_iterator<charT,Alloc> & y) {
  1909.     return x.current_pos - y.current_pos;
  1910. }
  1911.  
  1912. template <class charT, class Alloc>
  1913. inline __rope_const_iterator<charT,Alloc>
  1914. operator-(const __rope_const_iterator<charT,Alloc> & x,
  1915.       ptrdiff_t n) {
  1916.     return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos - n);
  1917. }
  1918.  
  1919. template <class charT, class Alloc>
  1920. inline __rope_const_iterator<charT,Alloc>
  1921. operator+(const __rope_const_iterator<charT,Alloc> & x,
  1922.       ptrdiff_t n) {
  1923.     return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos + n);
  1924. }
  1925.  
  1926. template <class charT, class Alloc>
  1927. inline __rope_const_iterator<charT,Alloc>
  1928. operator+(ptrdiff_t n,
  1929.       const __rope_const_iterator<charT,Alloc> & x) {
  1930.     return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos + n);
  1931. }
  1932.  
  1933. template <class charT, class Alloc>
  1934. inline bool operator== (const __rope_iterator<charT,Alloc> & x,
  1935.             const __rope_iterator<charT,Alloc> & y) {
  1936.     return (x.current_pos == y.current_pos && x.root_rope == y.root_rope);
  1937. }
  1938.  
  1939. template <class charT, class Alloc>
  1940. inline bool operator< (const __rope_iterator<charT,Alloc> & x,
  1941.             const __rope_iterator<charT,Alloc> & y) {
  1942.     return (x.current_pos < y.current_pos);
  1943. }
  1944.  
  1945. template <class charT, class Alloc>
  1946. inline ptrdiff_t operator-(const __rope_iterator<charT,Alloc> & x,
  1947.                const __rope_iterator<charT,Alloc> & y) {
  1948.     return x.current_pos - y.current_pos;
  1949. }
  1950.  
  1951. template <class charT, class Alloc>
  1952. inline __rope_iterator<charT,Alloc>
  1953. operator-(const __rope_iterator<charT,Alloc> & x,
  1954.       ptrdiff_t n) {
  1955.     return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos - n);
  1956. }
  1957.  
  1958. template <class charT, class Alloc>
  1959. inline __rope_iterator<charT,Alloc>
  1960. operator+(const __rope_iterator<charT,Alloc> & x,
  1961.       ptrdiff_t n) {
  1962.     return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos + n);
  1963. }
  1964.  
  1965. template <class charT, class Alloc>
  1966. inline __rope_iterator<charT,Alloc>
  1967. operator+(ptrdiff_t n,
  1968.       const __rope_iterator<charT,Alloc> & x) {
  1969.     return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos + n);
  1970. }
  1971.  
  1972. template <class charT, class Alloc>
  1973. inline
  1974. rope<charT,Alloc>
  1975. operator+ (const rope<charT,Alloc> &left,
  1976.        const rope<charT,Alloc> &right)
  1977. {
  1978.     return rope<charT,Alloc>
  1979.         (rope<charT,Alloc>::concat(left.tree_ptr, right.tree_ptr));
  1980.     // Inlining this should make it possible to keep left and
  1981.     // right in registers.
  1982. }
  1983.  
  1984. template <class charT, class Alloc>
  1985. inline
  1986. rope<charT,Alloc>&
  1987. operator+= (rope<charT,Alloc> &left,
  1988.         const rope<charT,Alloc> &right)
  1989. {
  1990.     left.append(right);
  1991.     return left;
  1992. }
  1993.  
  1994. template <class charT, class Alloc>
  1995. inline
  1996. rope<charT,Alloc>
  1997. operator+ (const rope<charT,Alloc> &left,
  1998.        const charT* right) {
  1999.     size_t rlen = rope<charT,Alloc>::char_ptr_len(right);
  2000.     return rope<charT,Alloc>
  2001.        (rope<charT,Alloc>::concat_char_iter(left.tree_ptr, right, rlen)); 
  2002. }
  2003.  
  2004. template <class charT, class Alloc>
  2005. inline
  2006. rope<charT,Alloc>&
  2007. operator+= (rope<charT,Alloc> &left,
  2008.         const charT* right) {
  2009.     left.append(right);
  2010.     return left;
  2011. }
  2012.  
  2013. template <class charT, class Alloc>
  2014. inline
  2015. rope<charT,Alloc>
  2016. operator+ (const rope<charT,Alloc> &left, charT right) {
  2017.     return rope<charT,Alloc>
  2018.         (rope<charT,Alloc>::concat_char_iter(left.tree_ptr, &right, 1));
  2019. }
  2020.  
  2021. template <class charT, class Alloc>
  2022. inline
  2023. rope<charT,Alloc>&
  2024. operator+= (rope<charT,Alloc> &left, charT right) {
  2025.     left.append(right);
  2026.     return left;
  2027. }
  2028.  
  2029. template <class charT, class Alloc>
  2030. bool
  2031. operator< (const rope<charT,Alloc> &left, const rope<charT,Alloc> &right) {
  2032.     return left.compare(right) < 0;
  2033. }
  2034.     
  2035. template <class charT, class Alloc>
  2036. bool
  2037. operator== (const rope<charT,Alloc> &left, const rope<charT,Alloc> &right) {
  2038.     return left.compare(right) == 0;
  2039. }
  2040.  
  2041. template <class charT, class Alloc>
  2042. inline bool operator== (const __rope_charT_ptr_proxy<charT,Alloc> & x,
  2043.             const __rope_charT_ptr_proxy<charT,Alloc> & y) {
  2044.     return (x.pos == y.pos && x.root == y.root);
  2045. }
  2046.  
  2047. template<class charT, class Alloc>
  2048. ostream& operator<< (ostream& o, const rope<charT, Alloc>& r);        
  2049.     
  2050. typedef rope<char, __ALLOC> crope;
  2051. typedef rope<wchar_t, __ALLOC> wrope;
  2052.  
  2053. inline crope::reference __mutable_reference_at(crope& c, size_t i)
  2054. {
  2055.     return c.mutable_reference_at(i);
  2056. }
  2057.  
  2058. inline wrope::reference __mutable_reference_at(wrope& c, size_t i)
  2059. {
  2060.     return c.mutable_reference_at(i);
  2061. }
  2062.  
  2063. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  2064.  
  2065. template <class charT, class Alloc>
  2066. inline void swap(rope<charT, Alloc>& x, rope<charT, Alloc>& y) {
  2067.   x.swap(y);
  2068. }
  2069.  
  2070. #else
  2071.  
  2072. inline void swap(crope x, crope y) { x.swap(y); }
  2073. inline void swap(wrope x, wrope y) { x.swap(y); }
  2074.  
  2075. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  2076.  
  2077. // Hash functions should probably be revisited later:
  2078. __STL_TEMPLATE_NULL struct hash<crope>
  2079. {
  2080.   size_t operator()(const crope& str) const
  2081.   {
  2082.     size_t sz = str.size();
  2083.  
  2084.     if (0 == sz) return 0;
  2085.     return 13*str[0] + 5*str[sz - 1] + sz;
  2086.   }
  2087. };
  2088.  
  2089.  
  2090. __STL_TEMPLATE_NULL struct hash<wrope>
  2091. {
  2092.   size_t operator()(const wrope& str) const
  2093.   {
  2094.     size_t sz = str.size();
  2095.  
  2096.     if (0 == sz) return 0;
  2097.     return 13*str[0] + 5*str[sz - 1] + sz;
  2098.   }
  2099. };
  2100.  
  2101. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  2102. #pragma reset woff 1174
  2103. #endif
  2104.  
  2105. __STL_END_NAMESPACE
  2106.  
  2107. # include <ropeimpl.h>
  2108. # endif /* __SGI_STL_INTERNAL_ROPE_H */
  2109.  
  2110. // Local Variables:
  2111. // mode:C++
  2112. // End:
  2113.