/*

 * © Portions copyright (c) 2006-2007 Nokia Corporation.  All rights reserved.

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1999 

 * Boris Fomitchev

 *

 * This material is provided "as is", with absolutely no warranty expressed

 * or implied. Any use is at your own risk.

 *

 * Permission to use or copy this software for any purpose is hereby granted 

 * without fee, provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

/* NOTE: This is an internal header file, included by other STL headers.

 *   You should not attempt to use it directly.

 */

// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf

// if necessary.  Assumes path_end[leaf_index] and leaf_pos are correct.

// Results in a valid buf_ptr if the iterator can be legitimately

// dereferenced.

# ifndef _STLP_ROPEIMPL_H

# define _STLP_ROPEIMPL_H

#ifndef _STLP_INTERNAL_ROPE_H

# include <stl/_rope.h>

#endif

# ifndef _STLP_CSTDIO

#  include <cstdio>

# endif

#ifndef _STLP_IOSTREAM

# include <iostream>

#endif

# include <stl/_range_errors.h>

_STLP_BEGIN_NAMESPACE

# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )

# define __allocator__ _Alloc

# else

# define __allocator__ allocator_type

# endif

template<class _CharT, class _Alloc>

_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)

  : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr._M_data, __pos),

  _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); }

template<class _CharT, class _Alloc>

_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos): 

  _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos), 

  _M_root_rope(&__r) {

  _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*this);

}

template<class _CharT, class _Alloc>

void 

_Rope_RopeRep<_CharT, _Alloc>::_M_free_c_string()

{

  _CharT* __cstr = _M_c_string;

  if (0 != __cstr) {

    size_t _p_size = _M_size._M_data + 1;

    _STLP_STD::_Destroy(__cstr, __cstr + _p_size);

    _M_size.deallocate(__cstr, _p_size);

  }

}

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

	    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._M_data;

		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:

      _STLP_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

    _STLP_ASSERT(__pos <= __x._M_root->_M_size._M_data)

    if (__pos >= __x._M_root->_M_size._M_data) {

	__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._M_data;

	__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;

	_STLP_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._M_data;

		__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._M_data;

    size_t __node_start_pos = __x._M_leaf_pos;

    unsigned char __dirns = __x._M_path_directions;

    _Rope_RopeConcatenation<_CharT,_Alloc>* __c;

    _STLP_ASSERT(__x._M_current_pos <= __x._M_root->_M_size._M_data)

    if (__x._M_current_pos - __node_start_pos < __len) {

	/* More stuff in this leaf, we just didn't cache it. */

	_S_setbuf(__x);

	return;

    }

    _STLP_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._M_data;

	__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._M_data;

    __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_data != this->_M_root) {

        // _Rope was modified.  Get things fixed up.

        _RopeRep::_S_unref(this->_M_root);

        this->_M_root = _M_root_rope->_M_tree_ptr._M_data;

        _RopeRep::_S_ref(this->_M_root);

        this->_M_buf_ptr = 0;

    }

}

# ifndef _GC

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

	    {

	      typedef _Rope_RopeLeaf<_CharT,_Alloc> _Rope_RopeLeaf_T;

          _Rope_RopeLeaf_T* __l = (_Rope_RopeLeaf_T*)this;

          _STLP_STD::_Destroy(__l); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();

	      _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, _Rope_RopeLeaf_T).deallocate(__l, 1);

	        break;

	    }

	case _S_concat:

	    {

               typedef _Rope_RopeConcatenation<_CharT,_Alloc> _Rope_RopeConcatenation_T;

               _Rope_RopeConcatenation_T* __c  = (_Rope_RopeConcatenation_T*)this;

               _STLP_STD::_Destroy(__c);

               _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, 

                               _Rope_RopeConcatenation_T).deallocate(__c, 1);

	        break;

	    }

	case _S_function:

	    {

            typedef _Rope_RopeFunction<_CharT,_Alloc> _Rope_RopeFunctionT;

              _Rope_RopeFunctionT* __f = (_Rope_RopeFunctionT*)this;

              _STLP_STD::_Destroy(__f);

              _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, 

                                 _Rope_RopeFunctionT).deallocate(__f, 1);

	        break;

	    }

	case _S_substringfn:

	    {

            typedef _Rope_RopeSubstring<_CharT,_Alloc> _Rope_RopeSubstring_T;

              _Rope_RopeSubstring_T* __ss = (_Rope_RopeSubstring_T*)this;

              _STLP_STD::_Destroy(__ss);

              _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, 

                              _Rope_RopeSubstring_T).deallocate(__ss, 1);

		break;

	    }

    }

}

#endif

# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )

#   define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>

#   define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>

#   define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc>

#   define _RopeRep _Rope_RopeRep<_CharT,_Alloc>

#   define size_type size_t

# else

#   define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf

#   define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep

# endif

// Concatenate a C string onto a leaf rope by copying the rope data.

// Used for short ropes.

template <class _CharT, class _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._M_data;

    _CharT* __new_data = __r->_M_size.allocate(_S_rounded_up_size(__old_len + __len));

    _RopeLeaf* __result;

    uninitialized_copy_n(__r->_M_data, __old_len, __new_data);

    uninitialized_copy_n(__iter, __len, __new_data + __old_len);

    _S_cond_store_eos(__new_data[__old_len + __len]);

    _STLP_TRY {

	__result = _S_new_RopeLeaf(__new_data, __old_len + __len,

				   __r->get_allocator());

    }

    _STLP_UNWIND(_RopeRep::_S_free_string(__new_data, __old_len + __len,

					     __r->get_allocator()));

    return __result;

}

#ifndef __GC

// As above, but it's OK to clobber original if refcount is 1

template <class _CharT, class _Alloc>

__RopeLeaf__*

rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter

		(_RopeLeaf* __r, const _CharT* __iter, size_t __len)

{

    _STLP_ASSERT(__r->_M_ref_count >= 1)

    if (__r->_M_ref_count > 1)

      return _S_leaf_concat_char_iter(__r, __iter, __len);

    size_t __old_len = __r->_M_size._M_data;

    if (_S_allocated_capacity(__old_len) >= __old_len + __len) {

	// The space has been partially initialized for the standard

	// character types.  But that doesn't matter for those types.

	uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);

	if (_S_is_basic_char_type((_CharT*)0)) {

	    _S_cond_store_eos(__r->_M_data[__old_len + __len]);

	    _STLP_ASSERT(__r->_M_c_string == __r->_M_data)

	} else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {

	    __r->_M_free_c_string();

	    __r->_M_c_string = 0;

	}

	__r->_M_size._M_data = __old_len + __len;

	_STLP_ASSERT(__r->_M_ref_count == 1)

	__r->_M_ref_count = 2;

	return __r;

    } else {

	_RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);

	_STLP_ASSERT(__result->_M_ref_count == 1)

	return __result;

    }

}

#endif

// Assumes left and right are not 0.

// Does not increment (nor decrement on exception) child reference counts.

// Result has ref count 1.

template <class _CharT, class _Alloc>

__RopeRep__*

rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right)

{

    _RopeConcatenation* __result =

      _S_new_RopeConcatenation(__left, __right, __left->get_allocator());

    size_t __depth = __result->_M_depth;

    _STLP_ASSERT(__left->get_allocator() == __right->get_allocator())

    if (__depth > 20 && (__result->_M_size._M_data < 1000 ||

			 __depth > _RopeRep::_S_max_rope_depth)) {

        _RopeRep* __balanced;

	_STLP_TRY {

	   __balanced = _S_balance(__result);

#          ifndef __GC

	     if (__result != __balanced) {

		_STLP_ASSERT(1 == __result->_M_ref_count

			     && 1 == __balanced->_M_ref_count)

	     }

#          endif

	   __result->_M_unref_nonnil();

        }

      _STLP_UNWIND((_STLP_CREATE_ALLOCATOR(allocator_type,(allocator_type&)__left->_M_size,

                                    _RopeConcatenation).deallocate(__result,1)));

		// In case of exception, we need to deallocate

		// otherwise dangling result node.  But caller

		// still owns its children.  Thus unref is

		// inappropriate.

	return __balanced;

    } else {

	return __result;

    }

}

template <class _CharT, class _Alloc>

__RopeRep__*

rope<_CharT,_Alloc>::_S_concat_char_iter

		(_RopeRep* __r, const _CharT*__s, size_t __slen)

{

    _RopeRep* __result;

    if (0 == __slen) {

	_S_ref(__r);

	return __r;

    }

    if (0 == __r)

      return _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,

					      /* __r->get_allocator()*/ allocator_type() );

    if (_RopeRep::_S_leaf == __r->_M_tag && 

          __r->_M_size._M_data + __slen <= _S_copy_max) {

	__result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);

#       ifndef __GC

	  _STLP_ASSERT(1 == __result->_M_ref_count)

#       endif

	return __result;

    }

    if (_RopeRep::_S_concat == __r->_M_tag

	&& _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {

	_RopeLeaf* __right = 

	  (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);

	if (__right->_M_size._M_data + __slen <= _S_copy_max) {

	  _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;

	  _RopeRep* __nright = 

	    _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);

	  __left->_M_ref_nonnil();

	  _STLP_TRY {

	    __result = _S_tree_concat(__left, __nright);

          }

	  _STLP_UNWIND(_S_unref(__left); _S_unref(__nright));

#         ifndef __GC

	    _STLP_ASSERT(1 == __result->_M_ref_count)

#         endif

	  return __result;

	}

    }

    _RopeRep* __nright =

      _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());

    _STLP_TRY {

      __r->_M_ref_nonnil();

      __result = _S_tree_concat(__r, __nright);

    }

    _STLP_UNWIND(_S_unref(__r); _S_unref(__nright));

#   ifndef __GC

      _STLP_ASSERT(1 == __result->_M_ref_count)

#   endif

    return __result;

}

#ifndef __GC

template <class _CharT, class _Alloc>

__RopeRep__* 

rope<_CharT,_Alloc>::_S_destr_concat_char_iter(

  _RopeRep* __r, const _CharT* __s, size_t __slen)

{

    _RopeRep* __result;

    if (0 == __r)

      return _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,

					      /* __r-> */allocator_type());

    size_t __count = __r->_M_ref_count;

    size_t __orig_size = __r->_M_size._M_data;

    _STLP_ASSERT(__count >= 1)

    if (__count > 1) return _S_concat_char_iter(__r, __s, __slen);