MNRope.h

Go to the documentation of this file.

/*
 * 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.
 *
 * Heavily modified by KOM/Darmstadt University of Technology, 2000
 */

#ifndef ROPE_H
#define ROPE_H

#include <config.h>

#define ITERATORS

#include <sys/types.h>
#include <assert.h>
#include <stdlib.h>
#include "mnstream.h"

// 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.
inline uchar_t _S_eos(uchar_t*) { return 0; }

// Store an eos iff _CharT is a basic character type.
// Do not reference _S_eos if it isn't.
inline void _S_cond_store_eos(uchar_t& __c) { __c = 0; }

#include "MNRopeCharProducer.h"
#include "MNRopeCharConsumer.h"

// First a lot of forward declarations.  The standard seems to require
// much stricter "declaration before use" than many of the implementations
// that preceded it.
#include "MNSelfDestrPtr.h"
#include "MNRopeLeaf.h"
#include "MNRopeFunction.h"
#include "MNRopeSubstring.h"
#include "MNRopeConcat.h"

#ifdef ITERATORS
#include "MNRopeIterator.h"
#include "MNRopeConstIterator.h"
#endif /* ITERATORS */

#include "MNPtrProxy.h"
#include "MNRefProxy.h"

MNRope operator+ (const MNRope& __left, const MNRope& __right);
        
MNRope operator+ (const MNRope& __left, const uchar_t* __right);
        
MNRope operator+ (const MNRope& __left, uchar_t __right);
        
#ifdef USE_STL_POWER
// Two 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.
struct _Rope_Concat_fn
    : public binary_function<rope, rope, rope >
{
    rope operator() (const rope& __x, const rope& __y)
    {
        return __x + __y;
    }
};

inline rope identity_element(_Rope_Concat_fn)
{
    return rope();
}
#endif /* USE_STL_POWER */


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



class MNRope
{
    MNRopeRep *_M_tree_ptr;

public:
    typedef uchar_t value_type;
    typedef ptrdiff_t difference_type;
    typedef uchar_t const_reference;
    typedef const uchar_t* const_pointer;
    typedef MNRefProxy reference;
    typedef MNPtrProxy pointer;

    friend struct MNRopeRep;
    friend class  MNPtrProxy;
    friend class  MNRefProxy;
    friend struct MNRopeSubstring;
    friend class  MNRopeIterator;
    friend class  MNRopeConstIterator;
    friend class  MNRopeIteratorBase;


protected:
    typedef  uchar_t* _Cstrptr;

    static uchar_t _S_empty_c_str[1];

    static bool _S_is0(uchar_t __c) { return __c == _S_eos((uchar_t*)0); }

    enum { _S_copy_max = 23 };

    static uchar_t _S_fetch(MNRopeRep* __r, size_t __pos);

    static uchar_t* _S_fetch_ptr(MNRopeRep* __r, size_t __pos);

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

        static void _S_unref(MNRopeRep* __t)
        {
              MNRopeRep::_S_unref(__t);
        }
        static void _S_ref(MNRopeRep* __t)
        {
              MNRopeRep::_S_ref(__t);
        }


    static MNRopeRep* _S_substring( MNRopeRep* __base,
                                    size_t __start,
                                    size_t __endp1 );

    static MNRopeRep* _S_concat_char_iter( MNRopeRep* __r,
                                           const uchar_t* __iter,
                                           size_t __slen );

    static MNRopeRep* _S_destr_concat_char_iter( MNRopeRep* __r,
                                                 const uchar_t* __iter,
                                                 size_t __slen );

    static MNRopeRep* _S_concat( MNRopeRep* __left,
                                 MNRopeRep* __right );

public:
        void apply_to_pieces( size_t __begin, size_t __end,
                              MNRopeCharConsumer& __c) const {
            _S_apply_to_pieces(__c, _M_tree_ptr, __begin, __end);
        }


protected:

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

        static size_t _S_allocated_capacity(size_t __n) {
            return _S_rounded_up_size(__n) - 1;
        }
                
        // Allocate and construct a RopeLeaf using the supplied allocator
        // Takes ownership of s instead of copying.
        static MNRopeLeaf* _S_newMNRopeLeaf( uchar_t *__s,
                                          size_t __size)
        {
            return new MNRopeLeaf(__s, __size);
        }

        static MNRopeConcat* _S_newMNRopeConcat(
                        MNRopeRep* __left, MNRopeRep* __right)
        {
            return new MNRopeConcat(__left, __right);
        }

        static MNRopeFunction* _S_newMNRopeFunction(MNRopeCharProducer* __f,
                size_t __size, bool __d)
        {
            return new MNRopeFunction(__f, __size, __d);
        }

        static MNRopeSubstring* _S_newMNRopeSubstring(
                MNRopeRep* __b, size_t __s,
                size_t __l)
        {
            return new MNRopeSubstring(__b, __s, __l);
        }

#         define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size) \
                _SMNRopeLeaf_from_unowned_char_ptr(__s, __size)     

        static
          MNRopeLeaf* _SMNRopeLeaf_from_unowned_char_ptr(const uchar_t *__s,
                       size_t __size)
        {
            if (0 == __size) return 0;
              uchar_t* __buf = (uchar_t*)malloc(_S_rounded_up_size(__size));

            uninitialized_copy_n(__s, __size, __buf);
            _S_cond_store_eos(__buf[__size]);
            return _S_newMNRopeLeaf(__buf, __size);
        }
            

        static MNRopeRep*
        _S_tree_concat(MNRopeRep* __left, MNRopeRep* __right);

        static MNRopeLeaf*
        _S_leaf_concat_char_iter(MNRopeLeaf* __r,
                                 const uchar_t* __iter, size_t __slen);

        static MNRopeLeaf* _S_destr_leaf_concat_char_iter
                        (MNRopeLeaf* __r, const uchar_t* __iter, size_t __slen);
        // A version that potentially clobbers __r if __r->_M_ref_count == 1.

private:

    static size_t _S_char_ptr_len(const uchar_t* __s);


    static uchar_t* _S_flatten(MNRopeRep* __r, uchar_t* __buffer);

    static uchar_t* _S_flatten(MNRopeRep* __r,
                             size_t __start, size_t __len,
                             uchar_t* __buffer);

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

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

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

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

    static MNRopeRep* _S_concat_and_set_balanced(MNRopeRep* __left,
                                                     MNRopeRep* __right)
    {
            MNRopeRep* __result = _S_concat(__left, __right);
            if (_S_is_balanced(__result)) __result->_M_is_balanced = true;
            return __result;
    }

    static MNRopeRep* _S_balance(MNRopeRep* __r);

    static void _S_add_to_forest(MNRopeRep*__r, MNRopeRep** __forest);
        
    static void _S_add_leaf_to_forest(MNRopeRep* __r, MNRopeRep** __forest);

    static void _S_dump(MNRopeRep* __r, int __indent = 0);

    static int _S_compare(const MNRopeRep* __x, const MNRopeRep* __y);

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

    int compare(const MNRope& __y) const
    {
        return _S_compare(_M_tree_ptr, __y._M_tree_ptr);
    }

    MNRope(const uchar_t* __s)
    {
        _M_tree_ptr =
            __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s));
    }

    MNRope(const uchar_t* __s, size_t __len)
    {
        _M_tree_ptr = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len);
    }

    MNRope(const uchar_t *__s, const uchar_t *__e)
    {
        _M_tree_ptr = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s);
    }

    MNRope(uchar_t __c)
    {
        assert( _S_rounded_up_size(1) >= 2 );

        uchar_t* __buf = (uchar_t*)malloc(_S_rounded_up_size(1));
        __buf[0] = __c;
        __buf[1] = 0;

        _M_tree_ptr = _S_newMNRopeLeaf(__buf, 1);
    }

    MNRope(size_t __n, uchar_t __c);

    MNRope()
    {
        _M_tree_ptr = NULL;
    }

    MNRope(MNRopeCharProducer *__fn, size_t __len, bool __delete_fn)
    {
        _M_tree_ptr = (0 == __len)
                    ? 0 : _S_newMNRopeFunction(__fn, __len, __delete_fn);
    }

    MNRope(const MNRope& __x)
    {
        _M_tree_ptr = __x._M_tree_ptr;
        _S_ref(_M_tree_ptr);
    }

    MNRope(MNRopeRep* __t)
    {
        _M_tree_ptr = __t;
    }

    ~MNRope()
    {
        _S_unref(_M_tree_ptr);
    }

        MNRope& operator=(const MNRope& __x)
        {
            MNRopeRep* __old = _M_tree_ptr;
            _M_tree_ptr = __x._M_tree_ptr;
            _S_ref(_M_tree_ptr);
            _S_unref(__old);
            return(*this);
        }

        void clear()
        {
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = 0;
        }

        void push_back(uchar_t __x)
        {
            MNRopeRep* __old = _M_tree_ptr;
            _M_tree_ptr = _S_destr_concat_char_iter(_M_tree_ptr, &__x, 1);
            _S_unref(__old);
        }

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

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

        void push_front(uchar_t __x)
        {
            MNRopeRep* __old = _M_tree_ptr;
            MNRopeRep* __left = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1);
            _M_tree_ptr = _S_concat(__left, _M_tree_ptr);
            _S_unref(__old);
            _S_unref(__left);
        }

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

        uchar_t front() const
        {
            return _S_fetch(_M_tree_ptr, 0);
        }

        void balance()
        {
            MNRopeRep* __old = _M_tree_ptr;
            _M_tree_ptr = _S_balance(_M_tree_ptr);
            _S_unref(__old);
        }

        void copy(uchar_t* __buffer) const {
            destroy(__buffer, __buffer + size());
            _S_flatten(_M_tree_ptr, __buffer);
        }

        size_t copy(size_t __pos, size_t __n, uchar_t* __buffer) const 
        {
            size_t __size = size();
            size_t __len = (__pos + __n > __size? __size - __pos : __n);

            destroy(__buffer, __buffer + __len);
            _S_flatten(_M_tree_ptr, __pos, __len, __buffer);
            return __len;
        }

        void dump() {
            _S_dump(_M_tree_ptr);
        }

        const uchar_t* c_str() const;

        const uchar_t* replace_with_c_str();

        void delete_c_str () {
            if (0 == _M_tree_ptr) return;
            if (MNRopeRep::_S_leaf == _M_tree_ptr->_M_tag && 
                ((MNRopeLeaf*)_M_tree_ptr)->_M_data == 
                      _M_tree_ptr->_M_c_string) {
                // Representation shared
                return;
            }
            _M_tree_ptr->_M_free_c_string();
            _M_tree_ptr->_M_c_string = 0;
        }

        uchar_t operator[] (size_t __pos) const {
            return _S_fetch(_M_tree_ptr, __pos);
        }

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

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

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

        size_t max_size() const {
            return _S_min_len[MNRopeRep::_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.
        }

        friend MNRope
        operator+ (const MNRope& __left,
                   const MNRope& __right);
        
        friend MNRope
        operator+ (const MNRope& __left,
                   const uchar_t* __right);
        
        friend MNRope
        operator+ (const MNRope& __left, uchar_t __right);

        MNRope& append(const uchar_t* __iter, size_t __n) {
            MNRopeRep* __result = 
              _S_destr_concat_char_iter(_M_tree_ptr, __iter, __n);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
            return *this;
        }

        MNRope& append(const uchar_t* __c_string) {
            size_t __len = _S_char_ptr_len(__c_string);
            append(__c_string, __len);
            return(*this);
        }

        MNRope& append(const uchar_t* __s, const uchar_t* __e) {
            MNRopeRep* __result =
                _S_destr_concat_char_iter(_M_tree_ptr, __s, __e - __s);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
            return *this;
        }

        MNRope& append(uchar_t __c) {
            MNRopeRep* __result = 
              _S_destr_concat_char_iter(_M_tree_ptr, &__c, 1);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
            return *this;
        }

        MNRope& append() { return append((uchar_t)0); }  // XXX why?

        MNRope& append(const MNRope& __y) {
            MNRopeRep* __result = _S_concat(_M_tree_ptr, __y._M_tree_ptr);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
            return *this;
        }

        MNRope& append(size_t __n, uchar_t __c) {
            MNRope __last(__n, __c);
            return append(__last);
        }

        void swap(MNRope& __b) {
            MNRopeRep* __tmp = _M_tree_ptr;
            _M_tree_ptr = __b._M_tree_ptr;
            __b._M_tree_ptr = __tmp;
        }


protected:
        static MNRopeRep* replace(MNRopeRep* __old, size_t __pos1,
                                  size_t __pos2, MNRopeRep* __r) {
            if (0 == __old) { _S_ref(__r); return __r; }
            MNSelfDestrPtr __left(
              _S_substring(__old, 0, __pos1));
            MNSelfDestrPtr __right(
              _S_substring(__old, __pos2, __old->_M_size));
            MNRopeRep* __result;

            if (0 == __r) {
                __result = _S_concat(__left, __right);
            } else {
                MNSelfDestrPtr __left_result(_S_concat(__left, __r));
                __result = _S_concat(__left_result, __right);
            }
            return __result;
        }

public:
        void insert(size_t __p, const MNRope& __r) {
            MNRopeRep* __result = 
              replace(_M_tree_ptr, __p, __p, __r._M_tree_ptr);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
        }

        void insert(size_t __p, size_t __n, uchar_t __c) {
            MNRope __r(__n,__c);
            insert(__p, __r);
        }

        void insert(size_t __p, const uchar_t* __i, size_t __n) {
            MNSelfDestrPtr __left(_S_substring(_M_tree_ptr, 0, __p));
            MNSelfDestrPtr __right(_S_substring(_M_tree_ptr, __p, size()));
            MNSelfDestrPtr __left_result(
              _S_concat_char_iter(__left, __i, __n));
                // _S_ destr_concat_char_iter should be safe here.
                // But as it stands it's probably not a win, since __left
                // is likely to have additional references.
            MNRopeRep* __result = _S_concat(__left_result, __right);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
        }

        void insert(size_t __p, const uchar_t* __c_string) {
            insert(__p, __c_string, _S_char_ptr_len(__c_string));
        }

        void insert(size_t __p, uchar_t __c) {
            insert(__p, &__c, 1);
        }

        void insert(size_t __p) {
            uchar_t __c = (uchar_t)0;
            insert(__p, &__c, 1);
        }

        void insert(size_t __p, const uchar_t* __i, const uchar_t* __j) {
            MNRope __r(__i, __j);
            insert(__p, __r);
        }


        void replace(size_t __p, size_t __n, const MNRope& __r) {
            MNRopeRep* __result = 
              replace(_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
        }

        void replace(size_t __p, size_t __n, 
                     const uchar_t* __i, size_t __i_len) {
            MNRope __r(__i, __i_len);
            replace(__p, __n, __r);
        }

        void replace(size_t __p, size_t __n, uchar_t __c) {
            MNRope __r(__c);
            replace(__p, __n, __r);
        }

        void replace(size_t __p, size_t __n, const uchar_t* __c_string) {
            MNRope __r(__c_string);
            replace(__p, __n, __r);
        }

        void replace(size_t __p, size_t __n, 
                     const uchar_t* __i, const uchar_t* __j) {
            MNRope __r(__i, __j);
            replace(__p, __n, __r);
        }


        void replace(size_t __p, const MNRope& __r) {
            replace(__p, 1, __r);
        }

        void replace(size_t __p, const uchar_t* __i, size_t __i_len) {
            replace(__p, 1, __i, __i_len);
        }

        void replace(size_t __p, const uchar_t* __c_string) {
            replace(__p, 1, __c_string);
        }

        void replace(size_t __p, const uchar_t* __i, const uchar_t* __j) {
            replace(__p, 1, __i, __j);
        }

        void erase(size_t __p, size_t __n) {
            MNRopeRep* __result = replace(_M_tree_ptr, __p, __p + __n, 0);
            _S_unref(_M_tree_ptr);
            _M_tree_ptr = __result;
        }

        void erase(size_t __p) {
            erase(__p, __p + 1);
        }

        MNRope substr(size_t __start, size_t __len = 1) const {
            return MNRope(
                        _S_substring(_M_tree_ptr, __start, __start + __len));
        }

    static const size_t npos;

    size_t find(uchar_t __c, size_t __pos = 0) const;

    reference mutable_reference_at(size_t __pos)
    {
        return reference(this, __pos);
    }

#ifdef __STD_STUFF
    reference operator[] (size_t __pos)
    {
        return _char_ref_proxy(this, __pos);
    }

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

    void resize(size_t __n, uchar_t __c)
    {}

    void resize(size_t __n)
    {}

    void reserve(size_t __res_arg = 0)
    {}

    size_t capacity() const
    {
        return max_size();
    }

    // Stuff below this line is dangerous because it's error prone.
    // I would really like to get rid of it.
    // copy function with funny arg ordering.
    size_t copy(uchar_t* __buffer, size_t __n, 
                   size_t __pos = 0) const
    {
        return copy(__pos, __n, __buffer);
    }
#endif

#ifdef ITERATORS
public:
    MNRope(const MNRopeConstIterator& __s, const MNRopeConstIterator& __e)
    {
        _M_tree_ptr = _S_substring(__s._M_root,
                                   __s._M_current_pos,
                                   __e._M_current_pos);
    }

    MNRope(const MNRopeIterator& __s, const MNRopeIterator& __e)
    {
        _M_tree_ptr = _S_substring(__s._M_root,
                                   __s._M_current_pos,
                                   __e._M_current_pos);
    }

    MNRopeConstIterator begin() const
    {
        return(MNRopeConstIterator(_M_tree_ptr, 0));
    }

    MNRopeConstIterator const_begin() const
    {
        return(MNRopeConstIterator(_M_tree_ptr, 0));
    }

    MNRopeConstIterator end() const
    {
        return(MNRopeConstIterator(_M_tree_ptr, size()));
    }

    MNRopeConstIterator const_end() const
    {
        return(MNRopeConstIterator(_M_tree_ptr, size()));
    }

#ifdef REVERSE_ITERATORS
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    typedef reverse_iterator<MNRopeConstIterator> const_reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    typedef reverse_iterator<MNRopeConstIterator, value_type, const_reference,
                             difference_type>  const_reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 

    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());
    }
#endif /* REVERSE_ITERATORS */

    MNRope& append(MNRopeConstIterator __s, MNRopeConstIterator __e)
    {
        assert(__s._M_root == __e._M_root);
        MNSelfDestrPtr __appendee(_S_substring(
            __s._M_root, __s._M_current_pos, __e._M_current_pos));
        MNRopeRep* __result = 
            _S_concat(_M_tree_ptr, (MNRopeRep*)__appendee);
        _S_unref(_M_tree_ptr);
        _M_tree_ptr = __result;
        return *this;
    }

    void insert(size_t __p, const MNRopeConstIterator& __i,
                const MNRopeConstIterator& __j)
    {
        MNRope __r(__i, __j);
        insert(__p, __r);
    }

    void insert(size_t __p, const MNRopeIterator& __i,
                const MNRopeIterator& __j)
    {
        MNRope __r(__i, __j);
        insert(__p, __r);
    }

    void replace(size_t __p, size_t __n,
                 const MNRopeConstIterator& __i, const MNRopeConstIterator& __j)
    {
        MNRope __r(__i, __j);
        replace(__p, __n, __r);
    }

    void replace(size_t __p, size_t __n,
                 const MNRopeIterator& __i, const MNRopeIterator& __j)
    {
        MNRope __r(__i, __j);
        replace(__p, __n, __r);
    }


    void replace(size_t __p, uchar_t __c)
    {
        MNRopeIterator __i(this, __p);
        *__i = __c;
    }

    void replace(size_t __p, const MNRopeConstIterator& __i,
                               const MNRopeConstIterator& __j)
    {
        replace(__p, 1, __i, __j);
    }

    void replace(size_t __p, const MNRopeIterator& __i,
                               const MNRopeIterator& __j)
    {
        replace(__p, 1, __i, __j);
    }


    MNRopeIterator insert(const MNRopeIterator& __p, const MNRope& __r)
        { insert(__p.index(), __r); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p, size_t __n, uchar_t __c)
        { insert(__p.index(), __n, __c); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p, uchar_t __c) 
        { insert(__p.index(), __c); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p ) 
        { insert(__p.index()); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p, const uchar_t* c_string) 
        { insert(__p.index(), c_string); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p, const uchar_t* __i, size_t __n)
        { insert(__p.index(), __i, __n); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p, const uchar_t* __i, 
                const uchar_t* __j)
        { insert(__p.index(), __i, __j);  return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p,
                const MNRopeConstIterator& __i, const MNRopeConstIterator& __j)
        { insert(__p.index(), __i, __j); return __p; }
    MNRopeIterator insert(const MNRopeIterator& __p,
                const MNRopeIterator& __i, const MNRopeIterator& __j)
        { insert(__p.index(), __i, __j); return __p; }


    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q,
                 const MNRope& __r)
        { replace(__p.index(), __q.index() - __p.index(), __r); }
    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q, uchar_t __c)
        { replace(__p.index(), __q.index() - __p.index(), __c); }
    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q,
                 const uchar_t* __c_string)
        { replace(__p.index(), __q.index() - __p.index(), __c_string); }
    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q,
                 const uchar_t* __i, size_t __n)
        { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q,
                 const uchar_t* __i, const uchar_t* __j)
        { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q,
                 const MNRopeConstIterator& __i, const MNRopeConstIterator& __j)
        { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
    void replace(const MNRopeIterator& __p, const MNRopeIterator& __q,
                 const MNRopeIterator& __i, const MNRopeIterator& __j)
        { replace(__p.index(), __q.index() - __p.index(), __i, __j); }


    void replace(const MNRopeIterator& __p, const MNRope& __r)
        { replace(__p.index(), __r); }
    void replace(const MNRopeIterator& __p, uchar_t __c)
        { replace(__p.index(), __c); }
    void replace(const MNRopeIterator& __p, const uchar_t* __c_string)
        { replace(__p.index(), __c_string); }
    void replace(const MNRopeIterator& __p, const uchar_t* __i, size_t __n)
        { replace(__p.index(), __i, __n); }
    void replace(const MNRopeIterator& __p, const uchar_t* __i, const uchar_t* __j)
        { replace(__p.index(), __i, __j); }
    void replace(const MNRopeIterator& __p, MNRopeConstIterator __i, 
                     MNRopeConstIterator __j)
        { replace(__p.index(), __i, __j); }
    void replace(const MNRopeIterator& __p, MNRopeIterator __i, MNRopeIterator __j)
        { replace(__p.index(), __i, __j); }


    MNRopeIterator erase(const MNRopeIterator& __p, const MNRopeIterator& __q)
    {
        size_t __p_index = __p.index();
        erase(__p_index, __q.index() - __p_index);
        return MNRopeIterator(this, __p_index);
    }

    MNRopeIterator erase(const MNRopeIterator& __p)
    {
        size_t __p_index = __p.index();
        erase(__p_index, 1);
        return MNRopeIterator(this, __p_index);
    }


    MNRope substr(MNRopeIterator __start, MNRopeIterator __end) const
    {
        return MNRope(
                _S_substring(_M_tree_ptr, __start.index(), __end.index()));
    }
        
    MNRope substr(MNRopeIterator __start) const
    {
        size_t __pos = __start.index();
        return MNRope( _S_substring(_M_tree_ptr, __pos, __pos + 1));
    }
        
    MNRope substr(MNRopeConstIterator __start, MNRopeConstIterator __end) const
    {
        // This might eventually take advantage of the cache in the
        // iterator.
        return MNRope(
              _S_substring(_M_tree_ptr, __start.index(), __end.index()));
    }

    MNRope substr(MNRopeConstIterator __start)
    {
        size_t __pos = __start.index();
        return MNRope( _S_substring(_M_tree_ptr, __pos, __pos + 1));
    }

    size_t find(const uchar_t* __s, size_t __pos = 0) const
    {
        size_t __result_pos;
        MNRopeConstIterator __result = search(const_begin() + __pos,
                                         const_end(),
                                         __s,
                                         __s + _S_char_ptr_len(__s));
        __result_pos = __result.index();
#ifndef __STL_OLD_ROPE_SEMANTICS
        if (__result_pos == size()) __result_pos = npos;
#endif
        return __result_pos;
    }

    MNRopeIterator mutable_begin()
    {
        return(MNRopeIterator(this, 0));
    }

    MNRopeIterator mutable_end()
    {
        return(MNRopeIterator(this, size()));
    }

#ifdef REVERSE_ITERATORS
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    typedef reverse_iterator<iterator, value_type, reference,
                                 difference_type>  reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 

    reverse_iterator mutable_rbegin()
    {
        return reverse_iterator(mutable_end());
    }

    reverse_iterator mutable_rend()
    {
        return reverse_iterator(mutable_begin());
    }
#endif /* REVERSE_ITERATORS */

#ifdef __STD_STUFF
    iterator end() { return mutable_end(); }
    iterator begin() { return mutable_begin(); }
#ifdef REVERSE_ITERATORS
    reverse_iterator rend() { return mutable_rend(); }
    reverse_iterator rbegin() { return mutable_rbegin(); }
#endif /* REVERSE_ITERATORS */
#else
    MNRopeConstIterator end() { return const_end(); }
    MNRopeConstIterator begin() { return const_begin(); }
#ifdef REVERSE_ITERATORS
    const_reverse_iterator rend() { return const_rend(); }
    const_reverse_iterator rbegin() { return const_rbegin(); }
#endif /* REVERSE_ITERATORS */
#endif

#endif /* ITERATORS */
};

inline
MNRope
operator+ (const MNRope& __left,
           const MNRope& __right)
{
    return MNRope(
      MNRope::_S_concat(__left._M_tree_ptr, __right._M_tree_ptr));
    // Inlining this should make it possible to keep __left and
    // __right in registers.
}

inline
MNRope&
operator+= (MNRope& __left, 
      const MNRope& __right)
{
    __left.append(__right);
    return __left;
}

inline MNRope
operator+ (const MNRope& __left,
           const uchar_t* __right) {
    size_t __rlen = MNRope::_S_char_ptr_len(__right);
    return MNRope(
      MNRope::_S_concat_char_iter(
        __left._M_tree_ptr, __right, __rlen)); 
}

inline MNRope&
operator+= (MNRope& __left,
            const uchar_t* __right) {
    __left.append(__right);
    return __left;
}

inline MNRope
operator+ (const MNRope& __left, uchar_t __right) {
    return MNRope(
      MNRope::_S_concat_char_iter(
        __left._M_tree_ptr, &__right, 1));
}

inline MNRope&
operator+= (MNRope& __left, uchar_t __right) {
    __left.append(__right);
    return __left;
}

inline bool
operator< (const MNRope& __left, 
           const MNRope& __right) {
    return __left.compare(__right) < 0;
}
        
inline bool
operator== (const MNRope& __left, 
            const MNRope& __right) {
    return __left.compare(__right) == 0;
}

#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER

inline bool
operator!= (const MNRope& __x, const MNRope& __y) {
  return !(__x == __y);
}

inline bool
operator> (const MNRope& __x, const MNRope& __y) {
  return __y < __x;
}

inline bool
operator<= (const MNRope& __x, const MNRope& __y) {
  return !(__y < __x);
}

inline bool
operator>= (const MNRope& __x, const MNRope& __y) {
  return !(__x < __y);
}

#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */

ostream& operator<< (ostream& __o, const MNRope& __r);

inline void swap(MNRope& __x, MNRope& __y) {
  __x.swap(__y);
}


# endif /* ROPE_H */

---