stl_rope.h

粗糙集应用软件

/*
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1997
 * Moscow Center for SPARC Technology
 *
 * Copyright (c) 1999 
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted 
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

/* 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

# ifndef __SGI_STL_INTERNAL_ALGOBASE_H
#  include <stl_algobase.h>
# endif

# ifndef __STLPORT_IOSFWD
#  include <iosfwd>
# endif

# ifndef __SGI_STL_INTERNAL_ALLOC_H
#  include <stl_alloc.h>
# endif

# ifndef __SGI_STL_INTERNAL_ITERATOR_H
#  include <stl_iterator.h>
# endif

# ifndef __SGI_STL_INTERNAL_ALGO_H
#  include <stl_algo.h>
# endif

# ifndef __SGI_STL_INTERNAL_FUNCTION_H
#  include <stl_function.h>
# endif

# ifndef __SGI_STL_INTERNAL_NUMERIC_H
#  include <stl_numeric.h>
# endif

# ifndef __SGI_STL_INTERNAL_HASH_FUN_H
#  include <stl_hash_fun.h>
# endif

# 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

// 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, __STL_DEFAULT_ALLOCATOR_SELECT(_CharT) > class rope;
template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;
template<class _CharT, class _Alloc> struct _Rope_RopeRep;
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;

// # if 0
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,
                               __STL_SIMPLE_TYPE(_CharT) __right);
// #endif

// 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>
inline
rope<_CharT,_Alloc>
identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
{
    return rope<_CharT,_Alloc>();
}

// 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(); }

// fbp : some compilers fail to zero-initialize builtins ;(
inline char _S_eos(const char*) { return 0; }
# ifdef __STL_HAS_WCHAR_T
inline wchar_t _S_eos(const wchar_t*) { return 0; }
# endif

// 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; }
# ifdef __STL_HAS_WCHAR_T
inline bool _S_is_basic_char_type(wchar_t*) { return true; }
# endif

// 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; }
# ifdef __STL_HAS_WCHAR_T
inline void _S_cond_store_eos(wchar_t& __c) { __c = 0; }
# endif

// 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
# if !(defined (__STL_NON_TYPE_TMPL_PARAM_BUG) || \
       defined ( __STL_NO_DEFAULT_NON_TYPE_PARAM ))
, size_t _Buf_sz = 100
#   if defined(__sgi) && !defined(__GNUC__)
#	 define __TYPEDEF_WORKAROUND
         ,class _V = typename _Sequence::value_type
#   endif /* __sgi */
# endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
        >
// 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;
    typedef sequence_buffer<_Sequence
# if !(defined (__STL_NON_TYPE_TMPL_PARAM_BUG) || \
       defined ( __STL_NO_DEFAULT_NON_TYPE_PARAM ))
        , _Buf_sz
    > _Self;
# else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
	> _Self;
  enum { _Buf_sz = 100}; 
# endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */
// # endif
#	else /* __TYPEDEF_WORKAROUND */
  typedef _V value_type;
  typedef sequence_buffer<_Sequence, _Buf_sz, _V> _Self;
#	endif /* __TYPEDEF_WORKAROUND */
    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 _Self& __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(_Self& __x) {
            __x.flush();
            _M_prefix = __x._M_prefix;
            _M_buf_count = 0;
        }
        sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}
        _Self& operator= (_Self& __x) {
            __x.flush();
            _M_prefix = __x._M_prefix;
            _M_buf_count = 0;
            return *this;
        }
        _Self& operator= (const _Self& __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);
            }
        }