stl_rope.h

著名的SGI的STL lib源码.(C++范型类编成,没有合适的分类,但是放到数据结构类别中也绝对适合)

	    replace(p, 1, i, j);
	}

	void replace(size_t p, const iterator& i,
			       const iterator& j) {
	    replace(p, 1, i, j);
	}

	// Erase, (position, size) variant.
	void erase(size_t p, size_t n) {
	    RopeBase * result = replace(tree_ptr, p, p + n, 0);
	    unref(tree_ptr);
	    tree_ptr = result;
	}

	// Erase, single character
	void erase(size_t p) {
	    erase(p, p + 1);
	}

	// Insert, iterator variants.  
	iterator insert(const iterator& p, const rope& r)
		{ insert(p.index(), r); return p; }
	iterator insert(const iterator& p, size_t n, charT c)
		{ insert(p.index(), n, c); return p; }
	iterator insert(const iterator& p, charT c) 
		{ insert(p.index(), c); return p; }
	iterator insert(const iterator& p ) 
		{ insert(p.index()); return p; }
	iterator insert(const iterator& p, const charT *c_string) 
		{ insert(p.index(), c_string); return p; }
	iterator insert(const iterator& p, const charT *i, size_t n)
		{ insert(p.index(), i, n); return p; }
	iterator insert(const iterator& p, const charT *i, const charT *j)
		{ insert(p.index(), i, j);  return p; }
	iterator insert(const iterator& p,
			const const_iterator& i, const const_iterator& j)
		{ insert(p.index(), i, j); return p; }
	iterator insert(const iterator& p,
			const iterator& i, const iterator& j)
		{ insert(p.index(), i, j); return p; }

	// Replace, range variants.
	void replace(const iterator& p, const iterator& q,
		     const rope& r)
		{ replace(p.index(), q.index() - p.index(), r); }
	void replace(const iterator& p, const iterator& q, charT c)
		{ replace(p.index(), q.index() - p.index(), c); }
	void replace(const iterator& p, const iterator& q,
		     const charT * c_string)
		{ replace(p.index(), q.index() - p.index(), c_string); }
	void replace(const iterator& p, const iterator& q,
		     const charT *i, size_t n)
		{ replace(p.index(), q.index() - p.index(), i, n); }
	void replace(const iterator& p, const iterator& q,
		     const charT *i, const charT *j)
		{ replace(p.index(), q.index() - p.index(), i, j); }
	void replace(const iterator& p, const iterator& q,
		     const const_iterator& i, const const_iterator& j)
		{ replace(p.index(), q.index() - p.index(), i, j); }
	void replace(const iterator& p, const iterator& q,
		     const iterator& i, const iterator& j)
		{ replace(p.index(), q.index() - p.index(), i, j); }

	// Replace, iterator variants.
	void replace(const iterator& p, const rope& r)
		{ replace(p.index(), r); }
	void replace(const iterator& p, charT c)
		{ replace(p.index(), c); }
	void replace(const iterator& p, const charT * c_string)
		{ replace(p.index(), c_string); }
	void replace(const iterator& p, const charT *i, size_t n)
		{ replace(p.index(), i, n); }
	void replace(const iterator& p, const charT *i, const charT *j)
		{ replace(p.index(), i, j); }
	void replace(const iterator& p, const_iterator i, const_iterator j)
		{ replace(p.index(), i, j); }
	void replace(const iterator& p, iterator i, iterator j)
		{ replace(p.index(), i, j); }

	// Iterator and range variants of erase
	iterator erase(const iterator &p, const iterator &q) {
            size_t p_index = p.index();
            erase(p_index, q.index() - p_index);
            return iterator(this, p_index);
        }
        iterator erase(const iterator &p) {
            size_t p_index = p.index();
            erase(p_index, 1);
            return iterator(this, p_index);
        }

	rope substr(size_t start, size_t len = 1) const {
	    return rope<charT,Alloc>(
			substring(tree_ptr, start, start + len));
	}

	rope substr(iterator start, iterator end) const {
	    return rope<charT,Alloc>(
			substring(tree_ptr, start.index(), end.index()));
	}
	
	rope substr(iterator start) const {
	    size_t pos = start.index();
	    return rope<charT,Alloc>(
			substring(tree_ptr, pos, pos + 1));
	}
	
	rope substr(const_iterator start, const_iterator end) const {
	    // This might eventually take advantage of the cache in the
	    // iterator.
	    return rope<charT,Alloc>
		(substring(tree_ptr, start.index(), end.index()));
	}

	rope<charT,Alloc> substr(const_iterator start) {
	    size_t pos = start.index();
	    return rope<charT,Alloc>(substring(tree_ptr, pos, pos + 1));
	}

	size_type find(charT c, size_type pos = 0) const;
	size_type find(charT *s, size_type pos = 0) const {
	    const_iterator result = search(const_begin() + pos, const_end(),
					   s, s + char_ptr_len(s));
	    return result.index();
	}

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

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

#     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());
	}

	reference mutable_reference_at(size_type pos) {
	    return reference(this, pos);
	}

#	ifdef __STD_STUFF
	    reference operator[] (size_type pos) {
		return charT_ref_proxy(this, pos);
	    }

	    reference at(size_type pos) {
		// if (pos >= size()) throw out_of_range;
		return (*this)[pos];
	    }

	    void resize(size_type n, charT c) {}
	    void resize(size_type n) {}
	    void reserve(size_type res_arg = 0) {}
	    size_type 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_type copy(charT *buffer, size_type n, size_type pos = 0)
								const {
		return copy(pos, n, buffer);
	      }

	    iterator end() { return mutable_end(); }

	    iterator begin() { return mutable_begin(); }

	    reverse_iterator rend() { return mutable_rend(); }

	    reverse_iterator rbegin() { return mutable_rbegin(); }

#	else

	    const_iterator end() { return const_end(); }

	    const_iterator begin() { return const_begin(); }

	    const_reverse_iterator rend() { return const_rend(); }
  
	    const_reverse_iterator rbegin() { return const_rbegin(); }

#	endif
	
};

template <class charT, class Alloc>
inline bool operator== (const __rope_const_iterator<charT,Alloc> & x,
			const __rope_const_iterator<charT,Alloc> & y) {
	return (x.current_pos == y.current_pos && x.root == y.root);
}

template <class charT, class Alloc>
inline bool operator< (const __rope_const_iterator<charT,Alloc> & x,
		       const __rope_const_iterator<charT,Alloc> & y) {
	return (x.current_pos < y.current_pos);
}

template <class charT, class Alloc>
inline ptrdiff_t operator-(const __rope_const_iterator<charT,Alloc> & x,
			   const __rope_const_iterator<charT,Alloc> & y) {
	return x.current_pos - y.current_pos;
}

template <class charT, class Alloc>
inline __rope_const_iterator<charT,Alloc>
operator-(const __rope_const_iterator<charT,Alloc> & x,
	  ptrdiff_t n) {
	return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos - n);
}

template <class charT, class Alloc>
inline __rope_const_iterator<charT,Alloc>
operator+(const __rope_const_iterator<charT,Alloc> & x,
	  ptrdiff_t n) {
	return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos + n);
}

template <class charT, class Alloc>
inline __rope_const_iterator<charT,Alloc>
operator+(ptrdiff_t n,
	  const __rope_const_iterator<charT,Alloc> & x) {
	return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos + n);
}

template <class charT, class Alloc>
inline bool operator== (const __rope_iterator<charT,Alloc> & x,
			const __rope_iterator<charT,Alloc> & y) {
	return (x.current_pos == y.current_pos && x.root_rope == y.root_rope);
}

template <class charT, class Alloc>
inline bool operator< (const __rope_iterator<charT,Alloc> & x,
			const __rope_iterator<charT,Alloc> & y) {
	return (x.current_pos < y.current_pos);
}

template <class charT, class Alloc>
inline ptrdiff_t operator-(const __rope_iterator<charT,Alloc> & x,
			   const __rope_iterator<charT,Alloc> & y) {
	return x.current_pos - y.current_pos;
}

template <class charT, class Alloc>
inline __rope_iterator<charT,Alloc>
operator-(const __rope_iterator<charT,Alloc> & x,
	  ptrdiff_t n) {
	return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos - n);
}

template <class charT, class Alloc>
inline __rope_iterator<charT,Alloc>
operator+(const __rope_iterator<charT,Alloc> & x,
	  ptrdiff_t n) {
	return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos + n);
}

template <class charT, class Alloc>
inline __rope_iterator<charT,Alloc>
operator+(ptrdiff_t n,
	  const __rope_iterator<charT,Alloc> & x) {
	return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos + n);
}

template <class charT, class Alloc>
inline
rope<charT,Alloc>
operator+ (const rope<charT,Alloc> &left,
	   const rope<charT,Alloc> &right)
{
    return rope<charT,Alloc>
		(rope<charT,Alloc>::concat(left.tree_ptr, right.tree_ptr));
    // Inlining this should make it possible to keep left and
    // right in registers.
}

template <class charT, class Alloc>
inline
rope<charT,Alloc>&
operator+= (rope<charT,Alloc> &left,
	    const rope<charT,Alloc> &right)
{
    left.append(right);
    return left;
}

template <class charT, class Alloc>
inline
rope<charT,Alloc>
operator+ (const rope<charT,Alloc> &left,
	   const charT* right) {
    size_t rlen = rope<charT,Alloc>::char_ptr_len(right);
    return rope<charT,Alloc>
	   (rope<charT,Alloc>::concat_char_iter(left.tree_ptr, right, rlen)); 
}

template <class charT, class Alloc>
inline
rope<charT,Alloc>&
operator+= (rope<charT,Alloc> &left,
	    const charT* right) {
    left.append(right);
    return left;
}

template <class charT, class Alloc>
inline
rope<charT,Alloc>
operator+ (const rope<charT,Alloc> &left, charT right) {
    return rope<charT,Alloc>
		(rope<charT,Alloc>::concat_char_iter(left.tree_ptr, &right, 1));
}

template <class charT, class Alloc>
inline
rope<charT,Alloc>&
operator+= (rope<charT,Alloc> &left, charT right) {
    left.append(right);
    return left;
}

template <class charT, class Alloc>
bool
operator< (const rope<charT,Alloc> &left, const rope<charT,Alloc> &right) {
    return left.compare(right) < 0;
}
	
template <class charT, class Alloc>
bool
operator== (const rope<charT,Alloc> &left, const rope<charT,Alloc> &right) {
    return left.compare(right) == 0;
}

template <class charT, class Alloc>
inline bool operator== (const __rope_charT_ptr_proxy<charT,Alloc> & x,
			const __rope_charT_ptr_proxy<charT,Alloc> & y) {
	return (x.pos == y.pos && x.root == y.root);
}

template<class charT, class Alloc>
ostream& operator<< (ostream& o, const rope<charT, Alloc>& r);        
	
typedef rope<char, __ALLOC> crope;
typedef rope<wchar_t, __ALLOC> wrope;

inline crope::reference __mutable_reference_at(crope& c, size_t i)
{
    return c.mutable_reference_at(i);
}

inline wrope::reference __mutable_reference_at(wrope& c, size_t i)
{
    return c.mutable_reference_at(i);
}

#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER

template <class charT, class Alloc>
inline void swap(rope<charT, Alloc>& x, rope<charT, Alloc>& y) {
  x.swap(y);
}

#else

inline void swap(crope x, crope y) { x.swap(y); }
inline void swap(wrope x, wrope y) { x.swap(y); }

#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */

// Hash functions should probably be revisited later:
__STL_TEMPLATE_NULL struct hash<crope>
{
  size_t operator()(const crope& str) const
  {
    size_t sz = str.size();

    if (0 == sz) return 0;
    return 13*str[0] + 5*str[sz - 1] + sz;
  }
};


__STL_TEMPLATE_NULL struct hash<wrope>
{
  size_t operator()(const wrope& str) const
  {
    size_t sz = str.size();

    if (0 == sz) return 0;
    return 13*str[0] + 5*str[sz - 1] + sz;
  }
};

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

__STL_END_NAMESPACE

# include <ropeimpl.h>
# endif /* __SGI_STL_INTERNAL_ROPE_H */

// Local Variables:
// mode:C++
// End: