stl_rope.h

TSP问题的一个类库 有源代码和stl

  typedef _Alloc allocator_type;
  static allocator_type get_allocator() { return allocator_type(); }
  _Rope_base(_RopeRep * __t, const allocator_type&) : _M_tree_ptr(__t) {}
  _Rope_base(const allocator_type&) {}

protected:
  // The only data member of a rope:
    _RopeRep* _M_tree_ptr;

# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
        typedef simple_alloc<_Tp, _Alloc> __name##Alloc; \
        static _Tp* __name##_allocate(size_t __n) \
                { return __name##Alloc::allocate(__n); } \
        static void __name##_deallocate(_Tp *__p, size_t __n) \
                { __name##Alloc::deallocate(__p, __n); }
  __ROPE_DEFINE_ALLOCS(_Alloc)
# undef __ROPE_DEFINE_ALLOC
};

#endif /* __STL_USE_STD_ALLOCATORS */


template <class _CharT, class _Alloc>
class rope : public _Rope_base<_CharT,_Alloc> {
    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 _Rope_base<_CharT,_Alloc> _Base;
        typedef typename _Base::allocator_type allocator_type;
#       ifdef __STL_USE_NAMESPACES
          using _Base::_M_tree_ptr;
#       endif
        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.

        typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;
        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(_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, __begin, __end);
        }


   protected:

        static size_t _S_rounded_up_size(size_t __n) {
            return _RopeLeaf::_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 __size, allocator_type __a)
        {
#           ifdef __STL_USE_STD_ALLOCATORS
              _RopeLeaf* __space = _LAllocator(__a).allocate(1);
#           else
              _RopeLeaf* __space = _L_allocate(1);
#           endif
            return new(__space) _RopeLeaf(__s, __size, __a);
        }

        static _RopeConcatenation* _S_new_RopeConcatenation(
                        _RopeRep* __left, _RopeRep* __right,
                        allocator_type __a)
        {
#           ifdef __STL_USE_STD_ALLOCATORS
              _RopeConcatenation* __space = _CAllocator(__a).allocate(1);
#           else
              _RopeConcatenation* __space = _C_allocate(1);
#           endif
            return new(__space) _RopeConcatenation(__left, __right, __a);
        }

        static _RopeFunction* _S_new_RopeFunction(char_producer<_CharT>* __f,
                size_t __size, bool __d, allocator_type __a)
        {
#           ifdef __STL_USE_STD_ALLOCATORS
              _RopeFunction* __space = _FAllocator(__a).allocate(1);
#           else
              _RopeFunction* __space = _F_allocate(1);
#           endif
            return new(__space) _RopeFunction(__f, __size, __d, __a);
        }

        static _RopeSubstring* _S_new_RopeSubstring(
                _Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
                size_t __l, allocator_type __a)
        {
#           ifdef __STL_USE_STD_ALLOCATORS
              _RopeSubstring* __space = _SAllocator(__a).allocate(1);
#           else
              _RopeSubstring* __space = _S_allocate(1);
#           endif
            return new(__space) _RopeSubstring(__b, __s, __l, __a);
        }

#       ifdef __STL_USE_STD_ALLOCATORS
          static
          _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
                       size_t __size, allocator_type __a)
#         define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
                _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)     
#       else
          static
          _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr2(const _CharT* __s,
                                                        size_t __size)
#         define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
               _S_RopeLeaf_from_unowned_char_ptr2(__s, __size)
#       endif
        {
            if (0 == __size) return 0;
#           ifdef __STL_USE_STD_ALLOCATORS
              _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
#           else
              _CharT* __buf = _Data_allocate(_S_rounded_up_size(__size));
              allocator_type __a = allocator_type();
#           endif

            uninitialized_copy_n(__s, __size, __buf);
            _S_cond_store_eos(__buf[__size]);
            __STL_TRY {
              return _S_new_RopeLeaf(__buf, __size, __a);
            }
            __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__buf, __size, __a))
        }
            

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

	private:

        static size_t _S_char_ptr_len(const _CharT* __s);
                        // slightly generalized strlen

        rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
          : _Base(__t,__a) { }


        // Copy __r to the _CharT buffer.
        // Returns __buffer + __r->_M_size.
        // Assumes that buffer is uninitialized.
        static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);

        // Again, with explicit starting position and length.
        // Assumes that buffer is uninitialized.
        static _CharT* _S_flatten(_RopeRep* __r,
                                  size_t __start, size_t __len,
                                  _CharT* __buffer);

        static const unsigned long 
          _S_min_len[_RopeRep::_S_max_rope_depth + 1];

        static bool _S_is_balanced(_RopeRep* __r)
                { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }

        static bool _S_is_almost_balanced(_RopeRep* __r)
                { return (__r->_M_depth == 0 ||
                          __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }

        static bool _S_is_roughly_balanced(_RopeRep* __r)
                { return (__r->_M_depth <= 1 ||
                          __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }

        // Assumes the result is not empty.
        static _RopeRep* _S_concat_and_set_balanced(_RopeRep* __left,
                                                     _RopeRep* __right)
        {
            _RopeRep* __result = _S_concat(__left, __right);
            if (_S_is_balanced(__result)) __result->_M_is_balanced = true;
            return __result;
        }

        // The basic rebalancing operation.  Logically copies the
        // rope.  The result has refcount of 1.  The client will
        // usually decrement the reference count of __r.
        // The result is within height 2 of balanced by the above
        // definition.
        static _RopeRep* _S_balance(_RopeRep* __r);

        // Add all unbalanced subtrees to the forest of balanceed trees.
        // Used only by balance.
        static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
        
        // Add __r to forest, assuming __r is already balanced.
        static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);

        // Print to stdout, exposing structure
        static void _S_dump(_RopeRep* __r, int __indent = 0);

        // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
        static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);

   public:
        bool empty() const { return 0 == _M_tree_ptr; }

        // Comparison member function.  This is public only for those
        // clients that need a ternary comparison.  Others
        // should use the comparison operators below.
        int compare(const rope& __y) const {
            return _S_compare(_M_tree_ptr, __y._M_tree_ptr);
        }

        rope(const _CharT* __s, const allocator_type& __a = allocator_type())
        : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
                                                 __a),__a)
        { }

        rope(const _CharT* __s, size_t __len,