rope

mingw32.rar

                // 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[_Rope_constants::_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 == this->_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(this->_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,
             const allocator_type& __a = allocator_type())
        : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, __a), __a)
        { }

        // Should perhaps be templatized with respect to the iterator type
        // and use Sequence_buffer.  (It should perhaps use sequence_buffer
        // even now.)
        rope(const _CharT *__s, const _CharT *__e,
             const allocator_type& __a = allocator_type())
        : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, __a), __a)
        { }

        rope(const const_iterator& __s, const const_iterator& __e,
             const allocator_type& __a = allocator_type())
        : _Base(_S_substring(__s._M_root, __s._M_current_pos,
                             __e._M_current_pos), __a)
        { }

        rope(const iterator& __s, const iterator& __e,
             const allocator_type& __a = allocator_type())
        : _Base(_S_substring(__s._M_root, __s._M_current_pos,
                             __e._M_current_pos), __a)
        { }

        rope(_CharT __c, const allocator_type& __a = allocator_type())
        : _Base(__a)
        {
	    _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));

            std::_Construct(__buf, __c);
            try {
                this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a);
            }
            catch(...)
	      {
		_RopeRep::__STL_FREE_STRING(__buf, 1, __a);
		__throw_exception_again;
	      }
        }

        rope(size_t __n, _CharT __c,
             const allocator_type& __a = allocator_type());

        rope(const allocator_type& __a = allocator_type())
        : _Base(0, __a) {}

        // Construct a rope from a function that can compute its members
        rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
             const allocator_type& __a = allocator_type())
            : _Base(__a)
        {
            this->_M_tree_ptr = (0 == __len) ?
               0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
        }

        rope(const rope& __x, const allocator_type& __a = allocator_type())
        : _Base(__x._M_tree_ptr, __a)
        {
            _S_ref(this->_M_tree_ptr);
        }

      ~rope() throw()
       { _S_unref(this->_M_tree_ptr); }

        rope& operator=(const rope& __x)
        {
            _RopeRep* __old = this->_M_tree_ptr;
            this->_M_tree_ptr = __x._M_tree_ptr;
            _S_ref(this->_M_tree_ptr);
            _S_unref(__old);
            return *this;
        }

        void clear()
        {
            _S_unref(this->_M_tree_ptr);
            this->_M_tree_ptr = 0;
        }

        void push_back(_CharT __x)
        {
            _RopeRep* __old = this->_M_tree_ptr;
            this->_M_tree_ptr
	      = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
            _S_unref(__old);
        }

        void pop_back()
        {
            _RopeRep* __old = this->_M_tree_ptr;
            this->_M_tree_ptr =
              _S_substring(this->_M_tree_ptr,
			   0,
			   this->_M_tree_ptr->_M_size - 1);
            _S_unref(__old);
        }

        _CharT back() const
        {
            return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1);
        }

        void push_front(_CharT __x)
        {
            _RopeRep* __old = this->_M_tree_ptr;
            _RopeRep* __left =
              __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, this->get_allocator());
            try {
              this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
              _S_unref(__old);
              _S_unref(__left);
            }
            catch(...)
	      {
		_S_unref(__left);
		__throw_exception_again;
	      }
        }

        void pop_front()
        {
            _RopeRep* __old = this->_M_tree_ptr;
            this->_M_tree_ptr
	      = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
            _S_unref(__old);
        }

        _CharT front() const
        {
            return _S_fetch(this->_M_tree_ptr, 0);
        }

        void balance()
        {
            _RopeRep* __old = this->_M_tree_ptr;
            this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
            _S_unref(__old);
        }

        void copy(_CharT* __buffer) const {
            _Destroy(__buffer, __buffer + size());
            _S_flatten(this->_M_tree_ptr, __buffer);
        }

        // This is the copy function from the standard, but
        // with the arguments reordered to make it consistent with the
        // rest of the interface.
        // Note that this guaranteed not to compile if the draft standard
        // order is assumed.
        size_type copy(size_type __pos, size_type __n, _CharT* __buffer) const
        {
            size_t __size = size();
            size_t __len = (__pos + __n > __size? __size - __pos : __n);

            _Destroy(__buffer, __buffer + __len);
            _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
            return __len;
        }

        // Print to stdout, exposing structure.  May be useful for
        // performance debugging.
        void dump() {
            _S_dump(this->_M_tree_ptr);
        }

        // Convert to 0 terminated string in new allocated memory.
        // Embedded 0s in the input do not terminate the copy.
        const _CharT* c_str() const;

        // As above, but lso use the flattened representation as the
        // the new rope representation.
        const _CharT* replace_with_c_str();

        // Reclaim memory for the c_str generated flattened string.
        // Intentionally undocumented, since it's hard to say when this
        // is safe for multiple threads.
        void delete_c_str () {
            if (0 == this->_M_tree_ptr) return;
            if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag &&
                ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
                      this->_M_tree_ptr->_M_c_string) {
                // Representation shared
                return;
            }
#           ifndef __GC
              this->_M_tree_ptr->_M_free_c_string();
#           endif
            this->_M_tree_ptr->_M_c_string = 0;
        }

        _CharT operator[] (size_type __pos) const {
            return _S_fetch(this->_M_tree_ptr, __pos);
        }

        _CharT at(size_type __pos) const {
           // if (__pos >= size()) throw out_of_range;  // XXX
           return (*this)[__pos];
        }

        const_iterator begin() const {
            return(const_iterator(this->_M_tree_ptr, 0));
        }

        // An easy way to get a const iterator from a non-const container.
        const_iterator const_begin() const {
            return(const_iterator(this->_M_tree_ptr, 0));
        }

        const_iterator end() const {
            return(const_iterator(this->_M_tree_ptr, size()));
        }

        const_iterator const_end() const {
            return(const_iterator(this->_M_tree_ptr, size()));
        }

        size_type size() const {
            return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size);
        }

        size_type length() const {
            return size();
        }

        size_type max_size() const {
            return _S_min_len[_Rope_constants::_S_max_rope_depth - 1] - 1;
            //  Guarantees that the result can be sufficirntly
            //  balanced.  Longer ropes will probably still work,
            //  but it's harder to make guarantees.
        }

        typedef reverse_iterator<const_iterator> const_reverse_iterator;

        const_reverse_iterator rbegin() const {
            return const_reverse_iterator(end());
        }

        const_reverse_iterator const_rbegin() const {
            return const_reverse_iterator(end());
        }

        const_reverse_iterator rend() const {
            return const_reverse_iterator(begin());
        }

        const_reverse_iterator const_rend() const {
            return const_reverse_iterator(begin());
        }

        template<class _CharT2, class _Alloc2>
        friend rope<_CharT2,_Alloc2>
        operator+ (const rope<_CharT2,_Alloc2>& __left,
                   const rope<_CharT2,_Alloc2>& __right);

        template<class _CharT2, class _Alloc2>
        friend rope<_CharT2,_Alloc2>
        operator+ (const rope<_CharT2,_Alloc2>& __left,
                   const _CharT2* __right);

        template<class _CharT2, class _Alloc2>
        friend rope<_CharT2,_Alloc2>
        operator+ (const rope<_CharT2,_Alloc2>& __left, _CharT2 __right);
        // The symmetric cases are intentionally omitted, since they're presumed
        // to be less common, and we don't handle them as well.

        // The following should really be templatized.
        // The first