stl_rope.h

粗糙集应用软件

    typedef random_access_iterator_tag iterator_category;
  public:
    rope<_CharT,_Alloc>& container() { return *_M_root_rope; }
    _Rope_iterator() {
        _M_root = 0;  // Needed for reference counting.
    };
    _Rope_iterator(const  _Self& __x) :
        _Rope_iterator_base<_CharT,_Alloc>(__x) {
        _M_root_rope = __x._M_root_rope;
        _RopeRep::_S_ref(_M_root);
    }
    _Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos): 
      _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos), 
      _M_root_rope(&__r) {
	_RopeRep::_S_ref(_M_root); if (!(__r.empty()))_S_setcache(*this);
    }
    _Self& operator= (const  _Self& __x) {
        _RopeRep* __old = _M_root;

        _RopeRep::_S_ref(__x._M_root);
        if (0 != __x._M_buf_ptr) {
            _M_root_rope = __x._M_root_rope;
            *(__STATIC_CAST(_Base*,this)) = __x;
        } else {
            _M_current_pos = __x._M_current_pos;
            _M_root = __x._M_root;
            _M_root_rope = __x._M_root_rope;
            _M_buf_ptr = 0;
        }
        _RopeRep::_S_unref(__old);
        return(*this);
    }
    reference operator*() {
        _M_check();
        if (0 == _M_buf_ptr) {
            return _Rope_char_ref_proxy<_CharT,_Alloc>(
               _M_root_rope, _M_current_pos);
        } else {
            return _Rope_char_ref_proxy<_CharT,_Alloc>(
               _M_root_rope, _M_current_pos, *_M_buf_ptr);
        }
    }
     _Self& operator++() {
        _M_incr(1);
        return *this;
    }
     _Self& operator+=(ptrdiff_t __n) {
        if (__n >= 0) {
            _M_incr(__n);
        } else {
            _M_decr(-__n);
        }
        return *this;
    }
     _Self& operator--() {
        _M_decr(1);
        return *this;
    }
     _Self& operator-=(ptrdiff_t __n) {
        if (__n >= 0) {
            _M_decr(__n);
        } else {
            _M_incr(-__n);
        }
        return *this;
    }
     _Self operator++(int) {
        size_t __old_pos = _M_current_pos;
        _M_incr(1);
        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
    }
     _Self operator--(int) {
        size_t __old_pos = _M_current_pos;
        _M_decr(1);
        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
    }
    reference operator[](ptrdiff_t __n) {
        return _Rope_char_ref_proxy<_CharT,_Alloc>(
          _M_root_rope, _M_current_pos + __n);
    }
};

#ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _CharT, class _Alloc>
inline random_access_iterator_tag
iterator_category(const _Rope_iterator<_CharT,_Alloc>&) {
  return random_access_iterator_tag();
}
template <class _CharT, class _Alloc>
inline _CharT*
value_type(const _Rope_iterator<_CharT,_Alloc>&) {
  return 0;
}
template <class _CharT, class _Alloc>
inline ptrdiff_t*
distance_type(const _Rope_iterator<_CharT,_Alloc>&) {
  return 0;
}
template <class _CharT, class _Alloc>
inline random_access_iterator_tag
iterator_category(const _Rope_const_iterator<_CharT,_Alloc>&) {
  return random_access_iterator_tag();
}
template <class _CharT, class _Alloc>
inline _CharT*
value_type(const _Rope_const_iterator<_CharT,_Alloc>&) {
  return 0;
}
template <class _CharT, class _Alloc>
inline ptrdiff_t*
distance_type(const _Rope_const_iterator<_CharT,_Alloc>&) {
  return 0;
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1375
#endif

template <class _CharT, class _Alloc>
class rope {
  typedef rope<_CharT,_Alloc> _Self;
public:
  typedef _CharT value_type;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef _CharT const_reference;
  typedef const _CharT* const_pointer;
  typedef _Rope_iterator<_CharT,_Alloc> iterator;
  typedef _Rope_const_iterator<_CharT,_Alloc> const_iterator;
  typedef _Rope_char_ref_proxy<_CharT,_Alloc> reference;
  typedef _Rope_char_ptr_proxy<_CharT,_Alloc> pointer;
  
  friend class _Rope_iterator<_CharT,_Alloc>;
  friend class _Rope_const_iterator<_CharT,_Alloc>;
  friend struct _Rope_RopeRep<_CharT,_Alloc>;
  friend class _Rope_iterator_base<_CharT,_Alloc>;
  friend class _Rope_char_ptr_proxy<_CharT,_Alloc>;
  friend class _Rope_char_ref_proxy<_CharT,_Alloc>;
  friend struct _Rope_RopeSubstring<_CharT,_Alloc>;
  
protected:
  typedef __GC_CONST _CharT* _Cstrptr;
  
  static _CharT _S_empty_c_str[1];
  
  static bool _S_is0(_CharT __c) { return __c == _S_eos((_CharT*)0); }
  enum { _S_copy_max = 23 };
  // For strings shorter than _S_copy_max, we copy to
  // concatenate.
  
public:
  typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  typedef typename _Alloc_traits<_CharT,_Alloc>::allocator_type  allocator_type;
  allocator_type get_allocator() const { return allocator_type(_M_tree_ptr); }
public:
  // The only data member of a rope:
  _STL_alloc_proxy<_RopeRep*, _CharT, allocator_type> _M_tree_ptr;

        typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
        typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
        typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
        typedef _Rope_RopeSubstring<_CharT,_Alloc> _RopeSubstring;



        // Retrieve a character at the indicated position.
        static _CharT _S_fetch(_RopeRep* __r, size_type __pos);

#       ifndef __GC
            // Obtain a pointer to the character at the indicated position.
            // The pointer can be used to change the character.
            // If such a pointer cannot be produced, as is frequently the
            // case, 0 is returned instead.
            // (Returns nonzero only if all nodes in the path have a refcount
            // of 1.)
            static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
#       endif

        static bool _S_apply_to_pieces(
                                // should be template parameter
                                _Rope_char_consumer<_CharT>& __c,
                                const _RopeRep* __r,
                                size_t __begin, size_t __end);
                                // begin and end are assumed to be in range.

#       ifndef __GC
          static void _S_unref(_RopeRep* __t)
          {
              _RopeRep::_S_unref(__t);
          }
          static void _S_ref(_RopeRep* __t)
          {
              _RopeRep::_S_ref(__t);
          }
#       else /* __GC */
          static void _S_unref(_RopeRep*) {}
          static void _S_ref(_RopeRep*) {}
#       endif


#       ifdef __GC
            typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr;
#       else
            typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr;
#       endif

        // _Result is counted in refcount.
        static _RopeRep* _S_substring(_RopeRep* __base,
                                    size_t __start, size_t __endp1);

        static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
                                          const _CharT* __iter, size_t __slen);
                // Concatenate rope and char ptr, copying __s.
                // Should really take an arbitrary iterator.
                // Result is counted in refcount.
        static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
                                          const _CharT* __iter, size_t __slen)
                // As above, but one reference to __r is about to be
                // destroyed.  Thus the pieces may be recycled if all
                // relevent reference counts are 1.
#           ifdef __GC
                // We can't really do anything since refcounts are unavailable.
                { return _S_concat_char_iter(__r, __iter, __slen); }
#           else
                ;
#           endif

        static _RopeRep* _S_concat_rep(_RopeRep* __left, _RopeRep* __right);
                // General concatenation on _RopeRep.  _Result
                // has refcount of 1.  Adjusts argument refcounts.

   public:
        void apply_to_pieces( size_t __begin, size_t __end,
                              _Rope_char_consumer<_CharT>& __c) const {
            _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __begin, __end);
        }


   protected:

        static size_t _S_rounded_up_size(size_t __n) {
            return _RopeRep::_S_rounded_up_size(__n);
        }

        static size_t _S_allocated_capacity(size_t __n) {
            if (_S_is_basic_char_type((_CharT*)0)) {
                return _S_rounded_up_size(__n) - 1;
            } else {
                return _S_rounded_up_size(__n);
            }
        }
                
        // Allocate and construct a RopeLeaf using the supplied allocator
        // Takes ownership of s instead of copying.
        static _RopeLeaf* _S_new_RopeLeaf(__GC_CONST _CharT *__s,
                                          size_t _p_size, allocator_type __a)
        {
	  _RopeLeaf* __space = __stl_alloc_create(__a, 
					       (_RopeLeaf*)0).allocate(1,(const void*)0);
	  __STL_TRY {
	    __STL_PLACEMENT_NEW(__space) _RopeLeaf(__s, _p_size, __a);
	  }
	  __STL_UNWIND(__stl_alloc_create(__a, 
					  (_RopeLeaf*)0).deallocate(__space, 1))
	  return __space;
        }

        static _RopeConcatenation* _S_new_RopeConcatenation(
                        _RopeRep* __left, _RopeRep* __right,
                        allocator_type __a)
        {
	  _RopeConcatenation* __space = __stl_alloc_create(__a,
							(_RopeConcatenation*)0).allocate(1,(const void*)0);
	  return __STL_PLACEMENT_NEW(__space) _RopeConcatenation(__left, __right, __a);
        }

        static _RopeFunction* _S_new_RopeFunction(char_producer<_CharT>* __f,
                size_t _p_size, bool __d, allocator_type __a)
        {
	  _RopeFunction* __space = __stl_alloc_create(__a, 
			     (_RopeFunction*)0).allocate(1,(const void*)0);
	  return __STL_PLACEMENT_NEW(__space) _RopeFunction(__f, _p_size, __d, __a);
        }

        static _RopeSubstring* _S_new_RopeSubstring(
                _Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
                size_t __l, allocator_type __a)
        {
	  _RopeSubstring* __space = __stl_alloc_create(__a, 
			     (_RopeSubstring*)0).allocate(1,(const void*)0);
	  return __STL_PLACEMENT_NEW(__space) _RopeSubstring(__b, __s, __l, __a);
        }

#         define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _p_size, __a) \
                _S_RopeLeaf_from_unowned_char_ptr(__s, _p_size, __a)     

          static
          _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
                       size_t _p_size, allocator_type __a)
        {
            if (0 == _p_size) return 0;
#ifdef __STL_MEMBER_TEMPLATE_CLASSES
	    _CharT* __buf = __a.allocate(_S_rounded_up_size(_p_size));
#else
	    _CharT* __buf = __stl_alloc_rebind(__a, (_CharT*)0).allocate(_S_rounded_up_size(_p_size));
#endif
	    uninitialized_copy_n(__s, _p_size, __buf);
	    _S_cond_store_eos(__buf[_p_size]);

            __STL_TRY {
              return _S_new_RopeLeaf(__buf, _p_size, __a);
            }
            __STL_UNWIND(_RopeRep::_S_free_string(__buf, _p_size, __a))
            
# if defined (__STL_THROW_RETURN_BUG)
	      return 0;
# endif
        }
            

        // Concatenation of nonempty strings.
        // Always builds a concatenation node.
        // Rebalances if the result is too deep.
        // Result has refcount 1.
        // Does not increment left and right ref counts even though
        // they are referenced.
        static _RopeRep*
        _S_tree_concat(_RopeRep* __left, _RopeRep* __right);

        // Concatenation helper functions
        static _RopeLeaf*
        _S_leaf_concat_char_iter(_RopeLeaf* __r,
                                 const _CharT* __iter, size_t __slen);
                // Concatenate by copying leaf.
                // should take an arbitrary iterator
                // result has refcount 1.
#       ifndef __GC
          static _RopeLeaf* _S_destr_leaf_concat_char_iter
                        (_RopeLeaf* __r, const _CharT* __iter, size_t __slen);
          // A version that potentially clobbers __r if __r->_M_ref_count == 1.
#       endif


	// A helper function for exponentiating strings.
	// This uses a nonstandard refcount convention.
	// The result has refcount 0.
	friend struct _Rope_Concat_fn<_CharT,_Alloc>;
        typedef _Rope_Concat_fn<_CharT,_Alloc> _Concat_fn;

        private:
        static size_t _S_char_ptr_len(const _CharT* __s) {
	  const _CharT* __p = __s;