ropeimpl.h

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

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

/* NOTE: This is an internal header file, included by other STL headers.
 *   You should not attempt to use it directly.
 */

# include <stdio.h>     

#ifdef __STL_USE_NEW_IOSTREAMS 
# include <iostream>
#else /* __STL_USE_NEW_IOSTREAMS */
# include <iostream.h>
#endif /* __STL_USE_NEW_IOSTREAMS */

#ifdef __STL_USE_EXCEPTIONS
# include <stdexcept>
#endif

__STL_BEGIN_NAMESPACE

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

// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
// if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
// Results in a valid buf_ptr if the iterator can be legitimately
// dereferenced.
template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( 
  _Rope_iterator_base<_CharT,_Alloc>& __x)
{
    const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
    size_t __leaf_pos = __x._M_leaf_pos;
    size_t __pos = __x._M_current_pos;

    switch(__leaf->_M_tag) {
	case _RopeRep::_S_leaf:
	    __x._M_buf_start = 
	      ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data;
	    __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
	    __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
	    break;
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    {
		size_t __len = _S_iterator_buf_len;
		size_t __buf_start_pos = __leaf_pos;
		size_t __leaf_end = __leaf_pos + __leaf->_M_size;
		char_producer<_CharT>* __fn =
			((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn;

		if (__buf_start_pos + __len <= __pos) {
		    __buf_start_pos = __pos - __len/4;
		    if (__buf_start_pos + __len > __leaf_end) {
			__buf_start_pos = __leaf_end - __len;
		    }
		}
		if (__buf_start_pos + __len > __leaf_end) {
		    __len = __leaf_end - __buf_start_pos;
		}
		(*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
		__x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
		__x._M_buf_start = __x._M_tmp_buf;
		__x._M_buf_end = __x._M_tmp_buf + __len;
	    }
	    break;
	default:
	    __stl_assert(0);
    }
}

// Set path and buffer inside a rope iterator.  We assume that 
// pos and root are already set.
template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache
(_Rope_iterator_base<_CharT,_Alloc>& __x)
{
    const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
    const _RopeRep* __curr_rope;
    int __curr_depth = -1;  /* index into path    */
    size_t __curr_start_pos = 0;
    size_t __pos = __x._M_current_pos;
    unsigned char __dirns = 0; // Bit vector marking right turns in the path

    __stl_assert(__pos <= __x._M_root->_M_size);
    if (__pos >= __x._M_root->_M_size) {
	__x._M_buf_ptr = 0;
	return;
    }
    __curr_rope = __x._M_root;
    if (0 != __curr_rope->_M_c_string) {
	/* Treat the root as a leaf. */
	__x._M_buf_start = __curr_rope->_M_c_string;
	__x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
	__x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
	__x._M_path_end[0] = __curr_rope;
	__x._M_leaf_index = 0;
	__x._M_leaf_pos = 0;
	return;
    }
    for(;;) {
	++__curr_depth;
	__stl_assert(__curr_depth <= _RopeRep::_S_max_rope_depth);
	__path[__curr_depth] = __curr_rope;
	switch(__curr_rope->_M_tag) {
	  case _RopeRep::_S_leaf:
	  case _RopeRep::_S_function:
	  case _RopeRep::_S_substringfn:
	    __x._M_leaf_pos = __curr_start_pos;
	    goto done;
	  case _RopeRep::_S_concat:
	    {
		_Rope_RopeConcatenation<_CharT,_Alloc>* __c =
			(_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size;
		
		__dirns <<= 1;
		if (__pos >= __curr_start_pos + __left_len) {
		    __dirns |= 1;
		    __curr_rope = __c->_M_right;
		    __curr_start_pos += __left_len;
		} else {
		    __curr_rope = __left;
		}
	    }
	    break;
	}
    }
  done:
    // Copy last section of path into _M_path_end.
      {
	int __i = -1;
	int __j = __curr_depth + 1 - _S_path_cache_len;

	if (__j < 0) __j = 0;
	while (__j <= __curr_depth) {
	    __x._M_path_end[++__i] = __path[__j++];
	}
	__x._M_leaf_index = __i;
      }
      __x._M_path_directions = __dirns;
      _S_setbuf(__x);
}

// Specialized version of the above.  Assumes that
// the path cache is valid for the previous position.
template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr
(_Rope_iterator_base<_CharT,_Alloc>& __x)
{
    int __current_index = __x._M_leaf_index;
    const _RopeRep* __current_node = __x._M_path_end[__current_index];
    size_t __len = __current_node->_M_size;
    size_t __node_start_pos = __x._M_leaf_pos;
    unsigned char __dirns = __x._M_path_directions;
    _Rope_RopeConcatenation<_CharT,_Alloc>* __c;

    __stl_assert(__x._M_current_pos <= __x._M_root->_M_size);
    if (__x._M_current_pos - __node_start_pos < __len) {
	/* More stuff in this leaf, we just didn't cache it. */
	_S_setbuf(__x);
	return;
    }
    __stl_assert(__node_start_pos + __len == __x._M_current_pos);
    //  node_start_pos is starting position of last_node.
    while (--__current_index >= 0) {
	if (!(__dirns & 1) /* Path turned left */) 
	  break;
	__current_node = __x._M_path_end[__current_index];
	__c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
	// Otherwise we were in the right child.  Thus we should pop
	// the concatenation node.
	__node_start_pos -= __c->_M_left->_M_size;
	__dirns >>= 1;
    }
    if (__current_index < 0) {
	// We underflowed the cache. Punt.
	_S_setcache(__x);
	return;
    }
    __current_node = __x._M_path_end[__current_index];
    __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
    // current_node is a concatenation node.  We are positioned on the first
    // character in its right child.
    // node_start_pos is starting position of current_node.
    __node_start_pos += __c->_M_left->_M_size;
    __current_node = __c->_M_right;
    __x._M_path_end[++__current_index] = __current_node;
    __dirns |= 1;
    while (_RopeRep::_S_concat == __current_node->_M_tag) {
	++__current_index;
	if (_S_path_cache_len == __current_index) {
	    int __i;
	    for (__i = 0; __i < _S_path_cache_len-1; __i++) {
		__x._M_path_end[__i] = __x._M_path_end[__i+1];
	    }
	    --__current_index;
	}
	__current_node =
	    ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left;
	__x._M_path_end[__current_index] = __current_node;
	__dirns <<= 1;
	// node_start_pos is unchanged.
    }
    __x._M_leaf_index = __current_index;
    __x._M_leaf_pos = __node_start_pos;
    __x._M_path_directions = __dirns;
    _S_setbuf(__x);
}

template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
    _M_current_pos += __n;
    if (0 != _M_buf_ptr) {
        size_t __chars_left = _M_buf_end - _M_buf_ptr;
        if (__chars_left > __n) {
            _M_buf_ptr += __n;
        } else if (__chars_left == __n) {
            _M_buf_ptr += __n;
            _S_setcache_for_incr(*this);
        } else {
            _M_buf_ptr = 0;
        }
    }
}

template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
    if (0 != _M_buf_ptr) {
        size_t __chars_left = _M_buf_ptr - _M_buf_start;
        if (__chars_left >= __n) {
            _M_buf_ptr -= __n;
        } else {
            _M_buf_ptr = 0;
        }
    }
    _M_current_pos -= __n;
}

template <class _CharT, class _Alloc>
void _Rope_iterator<_CharT,_Alloc>::_M_check() {
    if (_M_root_rope->_M_tree_ptr != _M_root) {
        // _Rope was modified.  Get things fixed up.
        _RopeRep::_S_unref(_M_root);
        _M_root = _M_root_rope->_M_tree_ptr;
        _RopeRep::_S_ref(_M_root);
        _M_buf_ptr = 0;
    }
}

template <class _CharT, class _Alloc>
inline 
_Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator(
  const _Rope_iterator<_CharT,_Alloc>& __x)
: _Rope_iterator_base<_CharT,_Alloc>(__x) 
{ }

template <class _CharT, class _Alloc>
inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator(
  rope<_CharT,_Alloc>& __r, size_t __pos)
: _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), 
  _M_root_rope(&__r)
{
    _RopeRep::_S_ref(_M_root);
}

template <class _CharT, class _Alloc>
inline size_t 
rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s)
{
    const _CharT* __p = __s;

    while (!_S_is0(*__p)) { ++__p; }
    return (__p - __s);
}


#ifndef __GC

template <class _CharT, class _Alloc>
inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string()
{
    _CharT* __cstr = _M_c_string;
    if (0 != __cstr) {
	size_t __size = _M_size + 1;
	destroy(__cstr, __cstr + __size);
	_Data_deallocate(__cstr, __size);
    }
}


template <class _CharT, class _Alloc>
#ifdef __STL_USE_STD_ALLOCATORS
  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,
							   size_t __n,
						           allocator_type __a)
#else
  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,
							   size_t __n)
#endif
{
    if (!_S_is_basic_char_type((_CharT*)0)) {
	destroy(__s, __s + __n);
    }
//  This has to be a static member, so this gets a bit messy
#   ifdef __STL_USE_STD_ALLOCATORS
        __a.deallocate(
	    __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));
#   else
	_Data_deallocate(
	    __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));
#   endif
}


//  There are several reasons for not doing this with virtual destructors
//  and a class specific delete operator:
//  - A class specific delete operator can't easily get access to
//    allocator instances if we need them.
//  - Any virtual function would need a 4 or byte vtable pointer;
//    this only requires a one byte tag per object.
template <class _CharT, class _Alloc>
void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree()
{
    switch(_M_tag) {
	case _S_leaf:
	    {
	        _Rope_RopeLeaf<_CharT,_Alloc>* __l
			= (_Rope_RopeLeaf<_CharT,_Alloc>*)this;
	        __l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
	        _L_deallocate(__l, 1);
	        break;
	    }
	case _S_concat:
	    {
	        _Rope_RopeConcatenation<_CharT,_Alloc>* __c
		    = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this;
	        __c->_Rope_RopeConcatenation<_CharT,_Alloc>::
		       ~_Rope_RopeConcatenation();
	        _C_deallocate(__c, 1);
	        break;
	    }
	case _S_function:
	    {
	        _Rope_RopeFunction<_CharT,_Alloc>* __f
		    = (_Rope_RopeFunction<_CharT,_Alloc>*)this;
	        __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction();
	        _F_deallocate(__f, 1);
	        break;
	    }
	case _S_substringfn:
	    {
	        _Rope_RopeSubstring<_CharT,_Alloc>* __ss =
			(_Rope_RopeSubstring<_CharT,_Alloc>*)this;
		__ss->_Rope_RopeSubstring<_CharT,_Alloc>::
		        ~_Rope_RopeSubstring();
		_S_deallocate(__ss, 1);
		break;
	    }
    }
}
#else

template <class _CharT, class _Alloc>
#ifdef __STL_USE_STD_ALLOCATORS
  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
		(const _CharT*, size_t, allocator_type)
#else
  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
		(const _CharT*, size_t)
#endif
{}

#endif


// Concatenate a C string onto a leaf rope by copying the rope data.
// Used for short ropes.
template <class _CharT, class _Alloc>
rope<_CharT,_Alloc>::_RopeLeaf*
rope<_CharT,_Alloc>::_S_leaf_concat_char_iter
		(_RopeLeaf* __r, const _CharT* __iter, size_t __len)
{
    size_t __old_len = __r->_M_size;