stl_rope.h

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

	// Should really be templatized with respect to the iterator type
	// and use sequence_buffer.  (It should perhaps use sequence_buffer
	// even now.)
	rope(const charT *i, const charT *j)
	{
	    if (i == j) {
		tree_ptr = 0;
	    } else {
		size_t len = j - i;
		tree_ptr = RopeLeaf_from_unowned_char_ptr(i, len);
	    }
	}

	rope()
	{
	    tree_ptr = 0;
	}

	// Construct a rope from a function that can compute its members
	rope(char_producer<charT> *fn, size_t len, bool delete_fn)
	{
	    tree_ptr = RopeFunction_from_fn(fn, len, delete_fn);
	}

	rope(const rope &x)
	{
	    tree_ptr = x.tree_ptr;
	    ref(tree_ptr);
	}

	~rope()
	{
	    unref(tree_ptr);
	}

	rope& operator=(const rope& x)
	{
	    RopeBase *old = tree_ptr;
	    tree_ptr = x.tree_ptr;
	    ref(tree_ptr);
	    unref(old);
	    return(*this);
	}

	void push_back(charT x)
	{
	    RopeBase *old = tree_ptr;
	    tree_ptr = concat_char_iter(tree_ptr, &x, 1);
	    unref(old);
	}

	void pop_back()
	{
	    RopeBase *old = tree_ptr;
	    tree_ptr = substring(tree_ptr, 0, tree_ptr -> size - 1);
	    unref(old);
	}

	charT back() const
	{
	    return fetch(tree_ptr, tree_ptr -> size - 1);
	}

	void push_front(charT x)
	{
	    RopeBase *old = tree_ptr;
	    RopeBase *left;

	    left = RopeLeaf_from_unowned_char_ptr(&x, 1);
	    __STL_TRY {
	      tree_ptr = concat(left, tree_ptr);
	      unref(old);
              unref(left);
            }
	    __STL_UNWIND(unref(left))
	}

	void pop_front()
	{
	    RopeBase *old = tree_ptr;
	    tree_ptr = substring(tree_ptr, 1, tree_ptr -> size);
	    unref(old);
	}

	charT front() const
	{
	    return fetch(tree_ptr, 0);
	}

	void balance()
	{
	    RopeBase *old = tree_ptr;
	    tree_ptr = balance(tree_ptr);
	    unref(old);
	}

	void copy(charT * buffer) const {
	    destroy(buffer, buffer + size());
	    flatten(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 sz = size();
	    size_t len = (pos + n > sz? sz - pos : n);

	    destroy(buffer, buffer + len);
	    flatten(tree_ptr, pos, len, buffer);
	    return len;
	}

	// Print to stdout, exposing structure.  May be useful for
	// performance debugging.
	void dump() {
	    dump(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 == tree_ptr) return;
	    if (RopeBase::leaf == tree_ptr -> tag
		&& ((RopeLeaf *)tree_ptr) -> data == tree_ptr -> c_string) {
		// Representation shared
		return;
	    }
#	    ifndef __GC
	      tree_ptr -> free_c_string();
#	    endif
	    tree_ptr -> c_string = 0;
	}

	charT operator[] (size_type pos) const {
	    return fetch(tree_ptr, pos);
	}

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

	const_iterator begin() const {
	    return(const_iterator(tree_ptr, 0));
	}

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

	const_iterator end() const {
	    return(const_iterator(tree_ptr, size()));
	}

	const_iterator const_end() const {
	    return(const_iterator(tree_ptr, size()));
	}

	size_type size() const { 
	    return(0 == tree_ptr? 0 : tree_ptr -> size);
	}

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

	size_type max_size() const {
	    return min_len[RopeBase::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.
	}

#     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
        typedef reverse_iterator<const_iterator> const_reverse_iterator;
#     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
	typedef reverse_iterator<const_iterator, 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());
	}

	friend rope<charT,Alloc>
        operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
                                        const rope<charT,Alloc> &right);
	
	friend rope<charT,Alloc>
        operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
                                        const charT* right);
	
	friend rope<charT,Alloc>
        operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
                                        charT 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 argument should be an input iterator or
	// forward iterator with value_type charT.
	rope& append(const charT* iter, size_t n) {
	    RopeBase* result = destr_concat_char_iter(tree_ptr, iter, n);
	    unref(tree_ptr);
	    tree_ptr = result;
	    return *this;
	}

	rope& append(const charT* c_string) {
	    size_t len = char_ptr_len(c_string);
	    append(c_string, len);
	    return(*this);
	}

	rope& append(const charT* s, const charT* e) {
	    RopeBase* result =
			destr_concat_char_iter(tree_ptr, s, e - s);
	    unref(tree_ptr);
	    tree_ptr = result;
	    return *this;
	}

	rope& append(const_iterator s, const_iterator e) {
	    __stl_assert(s.root == e.root);
	    self_destruct_ptr appendee(substring(s.root, s.current_pos,
						 e.current_pos));
	    RopeBase* result = concat(tree_ptr, (RopeBase *)appendee);
	    unref(tree_ptr);
	    tree_ptr = result;
	    return *this;
	}

	rope& append(charT c) {
	    RopeBase* result = destr_concat_char_iter(tree_ptr, &c, 1);
	    unref(tree_ptr);
	    tree_ptr = result;
	    return *this;
	}

	rope& append() { return append(charT()); }

	rope& append(const rope& y) {
	    RopeBase* result = concat(tree_ptr, y.tree_ptr);
	    unref(tree_ptr);
	    tree_ptr = result;
	    return *this;
	}

	rope& append(size_t n, charT c) {
	    rope<charT,Alloc> last(n, c);
	    return append(last);
	}

	void swap(rope& b) {
	    RopeBase * tmp = tree_ptr;
	    tree_ptr = b.tree_ptr;
	    b.tree_ptr = tmp;
	}


    protected:
	// Result is included in refcount.
	static RopeBase * replace(RopeBase *old, size_t pos1,
				  size_t pos2, RopeBase *r) {
	    if (0 == old) { ref(r); return r; }
	    self_destruct_ptr left(substring(old, 0, pos1));
	    self_destruct_ptr right(substring(old, pos2, old -> size));
	    RopeBase * result;

	    if (0 == r) {
		result = concat(left, right);
	    } else {
		self_destruct_ptr left_result(concat(left, r));
		result = concat(left_result, right);
	    }
	    return result;
	}

    public:
	void insert(size_t p, const rope& r) {
	    RopeBase * result = replace(tree_ptr, p, p,
					       r.tree_ptr);
	    unref(tree_ptr);
	    tree_ptr = result;
	}

	void insert(size_t p, size_t n, charT c) {
	    rope<charT,Alloc> r(n,c);
	    insert(p, r);
	}

	void insert(size_t p, const charT * i, size_t n) {
	    self_destruct_ptr left(substring(tree_ptr, 0, p));
	    self_destruct_ptr right(substring(tree_ptr, p, size()));
	    self_destruct_ptr left_result(concat_char_iter(left, i, n));
	    RopeBase * result =
				concat(left_result, right);
	    unref(tree_ptr);
	    tree_ptr = result;
	}

	void insert(size_t p, const charT * c_string) {
	    insert(p, c_string, char_ptr_len(c_string));
	}

	void insert(size_t p, charT c) {
	    insert(p, &c, 1);
	}

	void insert(size_t p) {
	    charT c = charT();
	    insert(p, &c, 1);
	}

	void insert(size_t p, const charT *i, const charT *j) {
	    rope r(i, j);
	    insert(p, r);
	}

	void insert(size_t p, const const_iterator& i,
			      const const_iterator& j) {
	    rope r(i, j);
	    insert(p, r);
	}

	void insert(size_t p, const iterator& i,
			      const iterator& j) {
	    rope r(i, j);
	    insert(p, r);
	}

	// (position, length) versions of replace operations:

	void replace(size_t p, size_t n, const rope& r) {
	    RopeBase * result = replace(tree_ptr, p, p + n,
					       r.tree_ptr);
	    unref(tree_ptr);
	    tree_ptr = result;
	}

	void replace(size_t p, size_t n, const charT *i, size_t i_len) {
	    rope r(i, i_len);
	    replace(p, n, r);
	}

	void replace(size_t p, size_t n, charT c) {
	    rope r(c);
	    replace(p, n, r);
	}

	void replace(size_t p, size_t n, const charT *c_string) {
	    rope r(c_string);
	    replace(p, n, r);
	}

	void replace(size_t p, size_t n, const charT *i, const charT *j) {
	    rope r(i, j);
	    replace(p, n, r);
	}

	void replace(size_t p, size_t n,
		     const const_iterator& i, const const_iterator& j) {
	    rope r(i, j);
	    replace(p, n, r);
	}

	void replace(size_t p, size_t n,
		     const iterator& i, const iterator& j) {
	    rope r(i, j);
	    replace(p, n, r);
	}

	// Single character variants:
	void replace(size_t p, charT c) {
	    iterator i(this, p);
	    *i = c;
	}

	void replace(size_t p, const rope& r) {
	    replace(p, 1, r);
	}

	void replace(size_t p, const charT *i, size_t i_len) {
	    replace(p, 1, i, i_len);
	}

	void replace(size_t p, const charT *c_string) {
	    replace(p, 1, c_string);
	}

	void replace(size_t p, const charT *i, const charT *j) {
	    replace(p, 1, i, j);
	}

	void replace(size_t p, const const_iterator& i,
			       const const_iterator& j) {