stl_rope.h

本系统采用VC开发.可实现点云数据的处理,图像缩放,生成曲面.

/*
 * Copyright (c) 1997
 * 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
#   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;
};

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

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;

//
// 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
// named functions in rope that simply invoke the _RopeRep versions.
//
// A macro to introduce various allocation and deallocation functions
// These need to be defined differently depending on whether or not
// we are using standard conforming allocators, and whether the allocator
// instances have real state.  Thus this macro is invoked repeatedly
// with different definitions of __ROPE_DEFINE_ALLOC.
// __ROPE_DEFINE_ALLOC(type,name) defines 
//   type * name_allocate(size_t) and
//   void name_deallocate(tipe *, size_t)
// Both functions may or may not be static.

#define __ROPE_DEFINE_ALLOCS(__a) \
        __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
        typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
        __ROPE_DEFINE_ALLOC(__C,_C) \
        typedef _Rope_RopeLeaf<_CharT,__a> __L; \
        __ROPE_DEFINE_ALLOC(__L,_L) \
        typedef _Rope_RopeFunction<_CharT,__a> __F; \
        __ROPE_DEFINE_ALLOC(__F,_F) \
        typedef _Rope_RopeSubstring<_CharT,__a> __S; \
        __ROPE_DEFINE_ALLOC(__S,_S)

//  Internal rope nodes potentially store a copy of the allocator
//  instance used to allocate them.  This is mostly redundant.
//  But the alternative would be to pass allocator instances around
//  in some form to nearly all internal functions, since any pointer
//  assignment may result in a zero reference count and thus require
//  deallocation.
//  The _Rope_rep_base class encapsulates
//  the differences between SGI-style allocators and standard-conforming
//  allocators.

#ifdef __STL_USE_STD_ALLOCATORS

#define __STATIC_IF_SGI_ALLOC  /* not static */

// Base class for ordinary allocators.
template <class _CharT, class _Allocator, bool _IsStatic>
class _Rope_rep_alloc_base {
public:
  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return _M_data_allocator; }
  _Rope_rep_alloc_base(size_t __size, const allocator_type& __a)
        : _M_size(__size), _M_data_allocator(__a) {}
  size_t _M_size;       // This is here only to avoid wasting space
                // for an otherwise empty base class.

  
protected:
    allocator_type _M_data_allocator;

# define __ROPE_DEFINE_ALLOC(_T, __name) \
        typedef typename \
          _Alloc_traits<_T,_Allocator>::allocator_type __name##Allocator; \
        /*static*/ _T * __name##_allocate(size_t __n) \
          { return __name##Allocator(_M_data_allocator).allocate(__n); } \
        void __name##_deallocate(_T* __p, size_t __n) \
          { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
  __ROPE_DEFINE_ALLOCS(_Allocator);
# undef __ROPE_DEFINE_ALLOC
};

// Specialization for allocators that have the property that we don't
//  actually have to store an allocator object.  
template <class _CharT, class _Allocator>
class _Rope_rep_alloc_base<_CharT,_Allocator,true> {
public:
  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
          allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }
  _Rope_rep_alloc_base(size_t __size, const allocator_type&)
                : _M_size(__size) {}
  size_t _M_size;
  
protected:

# define __ROPE_DEFINE_ALLOC(_T, __name) \
        typedef typename \
          _Alloc_traits<_T,_Allocator>::_Alloc_type __name##Alloc; \
        typedef typename \
          _Alloc_traits<_T,_Allocator>::allocator_type __name##Allocator; \
        static _T* __name##_allocate(size_t __n) \
                { return __name##Alloc::allocate(__n); } \
        void __name##_deallocate(_T *__p, size_t __n) \
                { __name##Alloc::deallocate(__p, __n); }
  __ROPE_DEFINE_ALLOCS(_Allocator);
# undef __ROPE_DEFINE_ALLOC
};

template <class _CharT, class _Alloc>
struct _Rope_rep_base
  : public _Rope_rep_alloc_base<_CharT,_Alloc,
                                _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
{
  typedef _Rope_rep_alloc_base<_CharT,_Alloc,
                               _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
          _Base;
  typedef typename _Base::allocator_type allocator_type;
  _Rope_rep_base(size_t __size, const allocator_type& __a)
    : _Base(__size, __a) {}