/*

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

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1997

 * Moscow Center for SPARC Technology

 *

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

 */

// rope<_CharT,_Alloc> is a sequence of _CharT.

// Ropes appear to be mutable, but update operations

// really copy enough of the data structure to leave the original

// valid.  Thus ropes can be logically copied by just copying

// a pointer value.

#ifndef _STLP_INTERNAL_ROPE_H

# define _STLP_INTERNAL_ROPE_H

# ifndef _STLP_INTERNAL_ALGOBASE_H

#  include <stl/_algobase.h>

# endif

# ifndef _STLP_IOSFWD

#  include <iosfwd>

# endif

# ifndef _STLP_INTERNAL_ALLOC_H

#  include <stl/_alloc.h>

# endif

# ifndef _STLP_INTERNAL_ITERATOR_H

#  include <stl/_iterator.h>

# endif

# ifndef _STLP_INTERNAL_ALGO_H

#  include <stl/_algo.h>

# endif

# ifndef _STLP_INTERNAL_FUNCTION_H

#  include <stl/_function.h>

# endif

# ifndef _STLP_INTERNAL_NUMERIC_H

#  include <stl/_numeric.h>

# endif

# ifndef _STLP_INTERNAL_HASH_FUN_H

#  include <stl/_hash_fun.h>

# endif

# ifdef __GC

#   define __GC_CONST const

# else

# include <stl/_threads.h>

#   define __GC_CONST   // constant except for deallocation

# endif

# ifdef _STLP_SGI_THREADS

#    include <mutex.h>

# endif

#ifdef _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM 

#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) (_Alloc_traits<_Tp,__atype>::create_allocator(__a)) 

#elif defined(__MRC__)||defined(__SC__) 

#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) __stl_alloc_create<_Tp,__atype>(__a,(_Tp*)0) 

#else 

#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) __stl_alloc_create(__a,(_Tp*)0) 

#endif 

_STLP_BEGIN_NAMESPACE

// First a lot of forward declarations.  The standard seems to require

// much stricter "declaration before use" than many of the implementations

// that preceded it.

template<class _CharT, _STLP_DEFAULT_ALLOCATOR_SELECT(_CharT) > class rope;

template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;

template<class _CharT, class _Alloc> struct _Rope_RopeRep;

template<class _CharT, class _Alloc> struct _Rope_RopeLeaf;

template<class _CharT, class _Alloc> struct _Rope_RopeFunction;

template<class _CharT, class _Alloc> struct _Rope_RopeSubstring;

template<class _CharT, class _Alloc> class _Rope_iterator;

template<class _CharT, class _Alloc> class _Rope_const_iterator;

template<class _CharT, class _Alloc> class _Rope_char_ref_proxy;

template<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;

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

template<class _CharT, class _Alloc>

struct _Rope_Concat_fn

  : public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>,

  rope<_CharT,_Alloc> > {

  rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x,

                                  const rope<_CharT,_Alloc>& __y) {

    return __x + __y;

  }

};

template <class _CharT, class _Alloc>

inline

rope<_CharT,_Alloc>

__identity_element(_Rope_Concat_fn<_CharT, _Alloc>)

{

  return rope<_CharT,_Alloc>();

}

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

template <class _CharT>

inline _CharT _S_eos(_CharT*) { return _CharT(); }

// fbp : some compilers fail to zero-initialize builtins ;(

inline const char _S_eos(const char*) { return 0; }

# ifdef _STLP_HAS_WCHAR_T

inline const wchar_t _S_eos(const wchar_t*) { return 0; }

# endif

// Test for basic character types.

// For basic character types leaves having a trailing eos.

template <class _CharT>

inline bool _S_is_basic_char_type(_CharT*) { return false; }

template <class _CharT>

inline bool _S_is_one_byte_char_type(_CharT*) { return false; }

inline bool _S_is_basic_char_type(char*) { return true; }

inline bool _S_is_one_byte_char_type(char*) { return true; }

# ifdef _STLP_HAS_WCHAR_T

inline bool _S_is_basic_char_type(wchar_t*) { return true; }

# endif

// Store an eos iff _CharT is a basic character type.

// Do not reference _S_eos if it isn't.

template <class _CharT>

inline void _S_cond_store_eos(_CharT&) {}

inline void _S_cond_store_eos(char& __c) { __c = 0; }

# ifdef _STLP_HAS_WCHAR_T

inline void _S_cond_store_eos(wchar_t& __c) { __c = 0; }

# endif

// char_producers are logically functions that generate a section of

// a string.  These can be convereted to ropes.  The resulting rope

// invokes the char_producer on demand.  This allows, for example,

// files to be viewed as ropes without reading the entire file.

template <class _CharT>

class char_producer {

public:

  virtual ~char_producer() {};

  virtual void operator()(size_t __start_pos, size_t __len, 

                          _CharT* __buffer) = 0;

  // Buffer should really be an arbitrary output iterator.

  // That way we could flatten directly into an ostream, etc.

  // This is thoroughly impossible, since iterator types don't

  // have runtime descriptions.

};

// Sequence buffers:

//

// Sequence must provide an append operation that appends an

// array to the sequence.  Sequence buffers are useful only if

// appending an entire array is cheaper than appending element by element.

// This is true for many string representations.

// This should  perhaps inherit from ostream<sequence::value_type>

// and be implemented correspondingly, so that they can be used

// for formatted.  For the sake of portability, we don't do this yet.

//

// For now, sequence buffers behave as output iterators.  But they also

// behave a little like basic_ostringstream<sequence::value_type> and a

// little like containers.

template<class _Sequence

# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \

       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))

, size_t _Buf_sz = 100

#   if defined(__sgi) && !defined(__GNUC__)

#	 define __TYPEDEF_WORKAROUND

,class _V = typename _Sequence::value_type

#   endif /* __sgi */

# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */

>

// The 3rd parameter works around a common compiler bug.

class sequence_buffer : public iterator <output_iterator_tag, void, void, void, void> {

public:

#       ifndef __TYPEDEF_WORKAROUND

  typedef typename _Sequence::value_type value_type;

  typedef sequence_buffer<_Sequence

# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \

       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))

  , _Buf_sz

  > _Self;

# else /* _STLP_NON_TYPE_TMPL_PARAM_BUG */

  > _Self;

  enum { _Buf_sz = 100}; 

# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */

  // # endif

#	else /* __TYPEDEF_WORKAROUND */

  typedef _V value_type;

  typedef sequence_buffer<_Sequence, _Buf_sz, _V> _Self;

#	endif /* __TYPEDEF_WORKAROUND */

protected:

  _Sequence* _M_prefix;

  value_type _M_buffer[_Buf_sz];

  size_t     _M_buf_count;

public:

  void flush() {

    _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);

    _M_buf_count = 0;

  }

  ~sequence_buffer() { flush(); }

  sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}

  sequence_buffer(const _Self& __x) {

    _M_prefix = __x._M_prefix;

    _M_buf_count = __x._M_buf_count;

    copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);

  }

  sequence_buffer(_Self& __x) {

    __x.flush();

    _M_prefix = __x._M_prefix;

    _M_buf_count = 0;

  }

  sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}

  _Self& operator= (_Self& __x) {

    __x.flush();

    _M_prefix = __x._M_prefix;

    _M_buf_count = 0;

    return *this;

  }

  _Self& operator= (const _Self& __x) {

    _M_prefix = __x._M_prefix;

    _M_buf_count = __x._M_buf_count;

    copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);

    return *this;

  }

  void push_back(value_type __x)

  {

    if (_M_buf_count < _Buf_sz) {

      _M_buffer[_M_buf_count] = __x;

      ++_M_buf_count;

    } else {

      flush();

      _M_buffer[0] = __x;

      _M_buf_count = 1;

    }

  }

  void append(value_type* __s, size_t __len)

  {

    if (__len + _M_buf_count <= _Buf_sz) {

      size_t __i = _M_buf_count;

      size_t __j = 0;

      for (; __j < __len; __i++, __j++) {

        _M_buffer[__i] = __s[__j];

      }

      _M_buf_count += __len;

    } else if (0 == _M_buf_count) {

      _M_prefix->append(__s, __s + __len);

    } else {

      flush();

      append(__s, __len);

    }

  }

  _Self& write(value_type* __s, size_t __len)

  {

    append(__s, __len);

    return *this;

  }

  _Self& put(value_type __x)

  {

    push_back(__x);

    return *this;

  }

  _Self& operator=(const value_type& __rhs)

  {

    push_back(__rhs);

    return *this;

  }

  _Self& operator*() { return *this; }

  _Self& operator++() { return *this; }

  _Self& operator++(int) { return *this; }

};

// The following should be treated as private, at least for now.

template<class _CharT>

class _Rope_char_consumer {

public:

  // If we had member templates, these should not be virtual.

  // For now we need to use run-time parametrization where

  // compile-time would do.  _Hence this should all be private

  // for now.

  // The symmetry with char_producer is accidental and temporary.

  virtual ~_Rope_char_consumer() {};

  virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;

};

//

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

//

//

// The internal data structure for representing a rope.  This is

// private to the implementation.  A rope is really just a pointer

// to one of these.

//

// A few basic functions for manipulating this data structure

// are members of _RopeRep.  Most of the more complex algorithms

// are implemented as rope members.

//

// Some of the static member functions of _RopeRep have identically

// named functions in rope that simply invoke the _RopeRep versions.

//

// A macro to introduce various allocation and deallocation functions

// These need to be defined differently depending on whether or not

// we are using standard conforming allocators, and whether the allocator

// instances have real state.  Thus this macro is invoked repeatedly

// with different definitions of __ROPE_DEFINE_ALLOC.

#if defined (_STLP_MEMBER_TEMPLATE_CLASSES)

# define __ROPE_DEFINE_ALLOC(_Tp, __name, _M_proxy) \

        typedef typename \

          _Alloc_traits<_Tp,_Alloc>::allocator_type __name##Allocator;

#define __ROPE_DEFINE_ALLOCS(__a, _M_proxy) \

        __ROPE_DEFINE_ALLOC(_CharT,_Data, _M_proxy) /* character data */ \

        typedef _Rope_RopeConcatenation<_CharT,__a> __C; \

        __ROPE_DEFINE_ALLOC(__C,_C, _M_proxy) \

        typedef _Rope_RopeLeaf<_CharT,__a> __L; \

        __ROPE_DEFINE_ALLOC(__L,_L, _M_proxy) \

        typedef _Rope_RopeFunction<_CharT,__a> __F; \

        __ROPE_DEFINE_ALLOC(__F,_F, _M_proxy) \

        typedef _Rope_RopeSubstring<_CharT,__a> __S; \

        __ROPE_DEFINE_ALLOC(__S,_S,_M_proxy)

#else

#define __ROPE_DEFINE_ALLOC(_Tp, __name, _M_proxy) 

#define __ROPE_DEFINE_ALLOCS(__a, _M_proxy)

#endif

template<class _CharT, class _Alloc>

struct _Rope_RopeRep

# ifndef __GC

  : public _Refcount_Base

# endif

{

  typedef _Rope_RopeRep<_CharT, _Alloc> _Self;

public:

#  define __ROPE_MAX_DEPTH  45

#  define __ROPE_DEPTH_SIZE 46

  enum { _S_max_rope_depth = __ROPE_MAX_DEPTH };

  enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};

  // Apparently needed by VC++

  // The data fields of leaves are allocated with some

  // extra space, to accomodate future growth and for basic

  // character types, to hold a trailing eos character.

  enum { _S_alloc_granularity = 8 };

  _Tag _M_tag:8;

  bool _M_is_balanced:8;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Alloc_traits<_CharT,_Alloc>::allocator_type

  allocator_type;

  allocator_type get_allocator() const { return allocator_type(_M_size);  }

  unsigned char _M_depth;

  __GC_CONST _CharT* _M_c_string;

  _STLP_alloc_proxy<size_t, _CharT, allocator_type> _M_size;

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeRep() : _Refcount_Base(1), _M_size(allocator_type(), 0) {}

# endif

  /* Flattened version of string, if needed.  */

  /* typically 0.                             */

  /* If it's not 0, then the memory is owned  */

  /* by this node.                            */

  /* In the case of a leaf, this may point to */

  /* the same memory as the data field.       */

  _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t _p_size,

                allocator_type __a) :

#         ifndef __GC

    _Refcount_Base(1),

#	  endif

    _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0), _M_size(__a, _p_size)

  { }

#   ifdef __GC

  void _M_incr () {}

#   endif

  // fbp : moved from RopeLeaf

  static size_t _S_rounded_up_size(size_t __n) {

    size_t __size_with_eos;

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

      __size_with_eos = __n + 1;

    } else {

      __size_with_eos = __n;

    }

#       ifdef __GC

    return __size_with_eos;

#       else

    // Allow slop for in-place expansion.

    return (__size_with_eos + _S_alloc_granularity-1)

      &~ (_S_alloc_granularity-1);

#       endif

  }

  static void _S_free_string(__GC_CONST _CharT* __s, size_t __len,

                             allocator_type __a) {

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

      _STLP_STD::_Destroy(__s, __s + __len);

    }

    //  This has to be a static member, so this gets a bit messy

#   ifdef _STLP_USE_NESTED_TCLASS_THROUGHT_TPARAM

    __a.deallocate(__s, _S_rounded_up_size(__len));		//*ty 03/24/2001 - restored not to use __stl_alloc_rebind() since it is not defined under _STLP_MEMBER_TEMPLATE_CLASSES

#   else

    __stl_alloc_rebind (__a, (_CharT*)0).deallocate(__s, _S_rounded_up_size(__len));

#   endif

  }

  // Deallocate data section of a leaf.

  // This shouldn't be a member function.

  // But its hard to do anything else at the

  // moment, because it's templatized w.r.t.

  // an allocator.

  // Does nothing if __GC is defined.

#   ifndef __GC

  void _M_free_c_string();

  void _M_free_tree();

  // Deallocate t. Assumes t is not 0.

  void _M_unref_nonnil()

  {

    _M_decr(); if (!_M_ref_count) _M_free_tree();

  }

  void _M_ref_nonnil()

  {

    _M_incr();

  }

  static void _S_unref(_Self* __t)

  {

    if (0 != __t) {

      __t->_M_unref_nonnil();

    }

  }

  static void _S_ref(_Self* __t)

  {

    if (0 != __t) __t->_M_incr();

  }

  static void _S_free_if_unref(_Self* __t)

  {

    if (0 != __t && 0 == __t->_M_ref_count) __t->_M_free_tree();

  }

#   else /* __GC */

  void _M_unref_nonnil() {}

  void _M_ref_nonnil() {}

  static void _S_unref(_Self*) {}

  static void _S_ref(_Self*) {}

  static void _S_free_if_unref(_Self*) {}

#   endif

  __ROPE_DEFINE_ALLOCS(_Alloc, _M_size)

    };

template<class _CharT, class _Alloc>