/* * Copyright (c) 1997-1998 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Silicon Graphics makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. *//* NOTE: This is an internal header file, included by other STL headers. *   You should not attempt to use it directly. */// rope<_CharT,_Alloc> is a sequence of _CharT.// Ropes appear to be mutable, but update operations// really copy enough of the data structure to leave the original// valid.  Thus ropes can be logically copied by just copying// a pointer value.#ifndef __SGI_STL_INTERNAL_ROPE_H# define __SGI_STL_INTERNAL_ROPE_H# ifdef __GC#   define __GC_CONST const# else#   include <stl_threads.h>#   define __GC_CONST   // constant except for deallocation# endif# ifdef __STL_SGI_THREADS#    include <mutex.h># endif__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)#pragma set woff 1174#endif// The _S_eos function is used for those functions that// convert to/from C-like strings to detect the end of the string.// The end-of-C-string character.// This is what the draft standard says it should be.template <class _CharT>inline _CharT _S_eos(_CharT*) { return _CharT(); }// Test for basic character types.// For basic character types leaves having a trailing eos.template <class _CharT>inline bool _S_is_basic_char_type(_CharT*) { return false; }template <class _CharT>inline bool _S_is_one_byte_char_type(_CharT*) { return false; }inline bool _S_is_basic_char_type(char*) { return true; }inline bool _S_is_one_byte_char_type(char*) { return true; }inline bool _S_is_basic_char_type(wchar_t*) { return true; }// Store an eos iff _CharT is a basic character type.// Do not reference _S_eos if it isn't.template <class _CharT>inline void _S_cond_store_eos(_CharT&) {}inline void _S_cond_store_eos(char& __c) { __c = 0; }inline void _S_cond_store_eos(wchar_t& __c) { __c = 0; }// char_producers are logically functions that generate a section of// a string.  These can be convereted to ropes.  The resulting rope// invokes the char_producer on demand.  This allows, for example,// files to be viewed as ropes without reading the entire file.template <class _CharT>class char_producer {    public:        virtual ~char_producer() {};        virtual void operator()(size_t __start_pos, size_t __len,                                 _CharT* __buffer) = 0;        // Buffer should really be an arbitrary output iterator.        // That way we could flatten directly into an ostream, etc.        // This is thoroughly impossible, since iterator types don't        // have runtime descriptions.};// Sequence buffers://// Sequence must provide an append operation that appends an// array to the sequence.  Sequence buffers are useful only if// appending an entire array is cheaper than appending element by element.// This is true for many string representations.// This should  perhaps inherit from ostream<sequence::value_type>// and be implemented correspondingly, so that they can be used// for formatted.  For the sake of portability, we don't do this yet.//// For now, sequence buffers behave as output iterators.  But they also// behave a little like basic_ostringstream<sequence::value_type> and a// little like containers.template<class _Sequence, size_t _Buf_sz = 100#   if defined(__sgi) && !defined(__GNUC__)#        define __TYPEDEF_WORKAROUND         ,class _V = typename _Sequence::value_type#   endif        >// The 3rd parameter works around a common compiler bug.class sequence_buffer : public output_iterator {    public:#       ifndef __TYPEDEF_WORKAROUND            typedef typename _Sequence::value_type value_type;#       else            typedef _V value_type;#       endif    protected:        _Sequence* _M_prefix;        value_type _M_buffer[_Buf_sz];        size_t     _M_buf_count;    public:        void flush() {            _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);            _M_buf_count = 0;        }        ~sequence_buffer() { flush(); }        sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}        sequence_buffer(const sequence_buffer& __x) {            _M_prefix = __x._M_prefix;            _M_buf_count = __x._M_buf_count;            copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);        }        sequence_buffer(sequence_buffer& __x) {            __x.flush();            _M_prefix = __x._M_prefix;            _M_buf_count = 0;        }        sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}        sequence_buffer& operator= (sequence_buffer& __x) {            __x.flush();            _M_prefix = __x._M_prefix;            _M_buf_count = 0;            return *this;        }        sequence_buffer& operator= (const sequence_buffer& __x) {            _M_prefix = __x._M_prefix;            _M_buf_count = __x._M_buf_count;            copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);            return *this;        }        void push_back(value_type __x)        {            if (_M_buf_count < _Buf_sz) {                _M_buffer[_M_buf_count] = __x;                ++_M_buf_count;            } else {                flush();                _M_buffer[0] = __x;                _M_buf_count = 1;            }        }        void append(value_type* __s, size_t __len)        {            if (__len + _M_buf_count <= _Buf_sz) {                size_t __i = _M_buf_count;                size_t __j = 0;                for (; __j < __len; __i++, __j++) {                    _M_buffer[__i] = __s[__j];                }                _M_buf_count += __len;            } else if (0 == _M_buf_count) {                _M_prefix->append(__s, __s + __len);            } else {                flush();                append(__s, __len);            }        }        sequence_buffer& write(value_type* __s, size_t __len)        {            append(__s, __len);            return *this;        }        sequence_buffer& put(value_type __x)        {            push_back(__x);            return *this;        }        sequence_buffer& operator=(const value_type& __rhs)        {            push_back(__rhs);            return *this;        }        sequence_buffer& operator*() { return *this; }        sequence_buffer& operator++() { return *this; }        sequence_buffer& operator++(int) { return *this; }};// The following should be treated as private, at least for now.template<class _CharT>class _Rope_char_consumer {    public:        // If we had member templates, these should not be virtual.        // For now we need to use run-time parametrization where        // compile-time would do.  Hence this should all be private        // for now.        // The symmetry with char_producer is accidental and temporary.        virtual ~_Rope_char_consumer() {};        virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;};// First a lot of forward declarations.  The standard seems to require// much stricter "declaration before use" than many of the implementations// that preceded it.template<class _CharT, class _Alloc=__STL_DEFAULT_ALLOCATOR(_CharT)> class rope;template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;template<class _CharT, class _Alloc> struct _Rope_RopeLeaf;template<class _CharT, class _Alloc> struct _Rope_RopeFunction;template<class _CharT, class _Alloc> struct _Rope_RopeSubstring;template<class _CharT, class _Alloc> class _Rope_iterator;template<class _CharT, class _Alloc> class _Rope_const_iterator;template<class _CharT, class _Alloc> class _Rope_char_ref_proxy;template<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;template<class _CharT, class _Alloc>bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x,                 const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>_Rope_const_iterator<_CharT,_Alloc> operator-        (const _Rope_const_iterator<_CharT,_Alloc>& __x,         ptrdiff_t __n);template<class _CharT, class _Alloc>_Rope_const_iterator<_CharT,_Alloc> operator+        (const _Rope_const_iterator<_CharT,_Alloc>& __x,         ptrdiff_t __n);template<class _CharT, class _Alloc>_Rope_const_iterator<_CharT,_Alloc> operator+        (ptrdiff_t __n,         const _Rope_const_iterator<_CharT,_Alloc>& __x);template<class _CharT, class _Alloc>bool operator==         (const _Rope_const_iterator<_CharT,_Alloc>& __x,         const _Rope_const_iterator<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>bool operator<         (const _Rope_const_iterator<_CharT,_Alloc>& __x,         const _Rope_const_iterator<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>ptrdiff_t operator-         (const _Rope_const_iterator<_CharT,_Alloc>& __x,         const _Rope_const_iterator<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>_Rope_iterator<_CharT,_Alloc> operator-        (const _Rope_iterator<_CharT,_Alloc>& __x,         ptrdiff_t __n);template<class _CharT, class _Alloc>_Rope_iterator<_CharT,_Alloc> operator+        (const _Rope_iterator<_CharT,_Alloc>& __x,         ptrdiff_t __n);template<class _CharT, class _Alloc>_Rope_iterator<_CharT,_Alloc> operator+        (ptrdiff_t __n,         const _Rope_iterator<_CharT,_Alloc>& __x);template<class _CharT, class _Alloc>bool operator==         (const _Rope_iterator<_CharT,_Alloc>& __x,         const _Rope_iterator<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>bool operator<         (const _Rope_iterator<_CharT,_Alloc>& __x,         const _Rope_iterator<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>ptrdiff_t operator-         (const _Rope_iterator<_CharT,_Alloc>& __x,         const _Rope_iterator<_CharT,_Alloc>& __y);template<class _CharT, class _Alloc>rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,                               const rope<_CharT,_Alloc>& __right);        template<class _CharT, class _Alloc>rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,                               const _CharT* __right);        template<class _CharT, class _Alloc>rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,                               _CharT __right);        // Some helpers, so we can use power on ropes.// See below for why this isn't local to the implementation.// This uses a nonstandard refcount convention.// The result has refcount 0.template<class _CharT, class _Alloc>struct _Rope_Concat_fn       : public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>,                                     rope<_CharT,_Alloc> > {        rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x,				const rope<_CharT,_Alloc>& __y) {                    return __x + __y;        }};template <class _CharT, class _Alloc>inlinerope<_CharT,_Alloc>identity_element(_Rope_Concat_fn<_CharT, _Alloc>){    return rope<_CharT,_Alloc>();}//// What follows should really be local to rope.  Unfortunately,// that doesn't work, since it makes it impossible to define generic// equality on rope iterators.  According to the draft standard, the// template parameters for such an equality operator cannot be inferred// from the occurence of a member class as a parameter.// (SGI compilers in fact allow this, but the __result wouldn't be// portable.)// Similarly, some of the static member functions are member functions// only to avoid polluting the global namespace, and to circumvent// restrictions on type inference for template functions.////// The internal data structure for representing a rope.  This is// private to the implementation.  A rope is really just a pointer// to one of these.//// A few basic functions for manipulating this data structure// are members of _RopeRep.  Most of the more complex algorithms// are implemented as rope members.//// Some of the static member functions of _RopeRep have identically