/*

 * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). 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_BASE_H

#  include <stl/_function_base.h>

#endif

#ifndef _STLP_INTERNAL_NUMERIC_H

#  include <stl/_numeric.h>

#endif

#ifndef _STLP_INTERNAL_HASH_FUN_H

#  include <stl/_hash_fun.h>

#endif

#ifndef _STLP_CHAR_TRAITS_H

#  include <stl/char_traits.h>

#endif

#ifndef _STLP_INTERNAL_THREADS_H

#  include <stl/_threads.h>

#endif

#ifdef _STLP_SGI_THREADS

#  include <mutex.h>

#endif

#ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE

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

_STLP_MOVE_TO_PRIV_NAMESPACE

// Some helpers, so we can use the power algorithm 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>(); }

_STLP_MOVE_TO_STD_NAMESPACE

// Store an eos

template <class _CharT>

inline void _S_construct_null_aux(_CharT *__p, const __true_type&)

{ *__p = 0; }

template <class _CharT>

inline void _S_construct_null_aux(_CharT *__p, const __false_type&)

{ _STLP_STD::_Construct(__p); }

template <class _CharT>

inline void _S_construct_null(_CharT *__p) {

  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;

  _S_construct_null_aux(__p, _Char_Is_Integral());

}

// char_producers are logically functions that generate a section of

// a string.  These can be converted 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(const 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(const 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 {

#if !defined (_STLP_MEMBER_TEMPLATES)

public:

  //Without member templates we have to use run-time parameterization.

  // The symmetry with char_producer is accidental and temporary.

  virtual ~_Rope_char_consumer() {}

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

#endif

};

//

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

//

template<class _CharT, class _Alloc>

struct _Rope_RopeRep

  : public _Refcount_Base

{

  typedef _Rope_RopeRep<_CharT, _Alloc> _Self;

public:

  //

  // GAB: 11/09/05

  //

  // "__ROPE_DEPTH_SIZE" is set to one more then the "__ROPE_MAX_DEPTH".

  // This was originally just an addition of "__ROPE_MAX_DEPTH + 1"

  // but this addition causes the sunpro compiler to complain about

  // multiple declarations during the initialization of "_S_min_len".

  // Changed to be a fixed value and the sunpro compiler appears to

  // be happy???

  //

#  define __ROPE_MAX_DEPTH  45

#  define __ROPE_DEPTH_SIZE 46 // __ROPE_MAX_DEPTH + 1

  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;

  _CharT* _STLP_VOLATILE _M_c_string;

  _STLP_PRIV _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, unsigned char __d, bool __b, size_t _p_size,

                allocator_type __a) :

    _Refcount_Base(1),

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

  { }

  typedef typename _AreSameUnCVTypes<_CharT, char>::_Ret _IsChar;

# ifdef _STLP_HAS_WCHAR_T

  typedef typename _AreSameUnCVTypes<_CharT, wchar_t>::_Ret _IsWCharT;

# else

  typedef __false_type _IsWCharT;

# endif

  typedef typename _Lor2<_IsChar, _IsWCharT>::_Ret _IsBasicCharType;

#if 0

  /* Please tell why this code is necessary if you uncomment it.

   * Problem with it is that rope implementation expect that _S_rounded_up_size(n)

   * returns a size > n in order to store the terminating null charater. When

   * instanciation type is not a char or wchar_t this is not guaranty resulting in

   * memory overrun.

   */

  static size_t _S_rounded_up_size_aux(size_t __n, __true_type const& /*_IsBasicCharType*/) {

    // Allow slop for in-place expansion.

    return (__n + _S_alloc_granularity) & ~(_S_alloc_granularity - 1);

  }

  static size_t _S_rounded_up_size_aux(size_t __n, __false_type const& /*_IsBasicCharType*/) {

    // Allow slop for in-place expansion.

    return (__n + _S_alloc_granularity - 1) & ~(_S_alloc_granularity - 1);

  }

#endif

  // fbp : moved from RopeLeaf

  static size_t _S_rounded_up_size(size_t __n)

  //{ return _S_rounded_up_size_aux(__n, _IsBasicCharType()); }

  { return (__n + _S_alloc_granularity) & ~(_S_alloc_granularity - 1); }

  static void _S_free_string( _CharT* __s, size_t __len,

                             allocator_type __a) {

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

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

#   ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE

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

  void _M_free_c_string();

  void _M_free_tree();

  // Deallocate t. Assumes t is not 0.

  void _M_unref_nonnil() {

    if (_M_decr() == 0) _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();

  //}

};

template<class _CharT, class _Alloc>

struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> {

public:

  _CharT* _M_data; /* Not necessarily 0 terminated. */

                                /* The allocated size is         */

                                /* _S_rounded_up_size(size), except */

                                /* in the GC case, in which it   */

                                /* doesn't matter.               */

private:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

  typedef typename _RopeRep::_IsBasicCharType _IsBasicCharType;

  void _M_init(__true_type const& /*_IsBasicCharType*/) {

    this->_M_c_string = _M_data;

  }

  void _M_init(__false_type const& /*_IsBasicCharType*/) {}

public:

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _RopeRep::allocator_type allocator_type;

  _Rope_RopeLeaf( _CharT* __d, size_t _p_size, allocator_type __a)

    : _Rope_RopeRep<_CharT,_Alloc>(_RopeRep::_S_leaf, 0, true, _p_size, __a),

      _M_data(__d) {

    _STLP_ASSERT(_p_size > 0)

    _M_init(_IsBasicCharType());

  }

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeLeaf() {}

  _Rope_RopeLeaf(const _Rope_RopeLeaf<_CharT, _Alloc>& ) {}

# endif

// The constructor assumes that d has been allocated with

  // the proper allocator and the properly padded size.

  // In contrast, the destructor deallocates the data:

  ~_Rope_RopeLeaf() {

    if (_M_data != this->_M_c_string) {

      this->_M_free_c_string();

    }

    _RopeRep::_S_free_string(_M_data, this->_M_size._M_data, this->get_allocator());

  }

};

template<class _CharT, class _Alloc>

struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT, _Alloc> {

private:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

public:

  _RopeRep* _M_left;

  _RopeRep* _M_right;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _RopeRep::allocator_type allocator_type;

  _Rope_RopeConcatenation(_RopeRep* __l, _RopeRep* __r, allocator_type __a)

    : _Rope_RopeRep<_CharT,_Alloc>(_RopeRep::_S_concat,

                                   (max)(__l->_M_depth, __r->_M_depth) + 1, false,

                                   __l->_M_size._M_data + __r->_M_size._M_data, __a), _M_left(__l), _M_right(__r)

  {}

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeConcatenation() {}

  _Rope_RopeConcatenation(const _Rope_RopeConcatenation<_CharT, _Alloc>&) {}

# endif

  ~_Rope_RopeConcatenation() {

    this->_M_free_c_string();

    _M_left->_M_unref_nonnil();

    _M_right->_M_unref_nonnil();

  }

};

template <class _CharT, class _Alloc>

struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT, _Alloc> {

private:

  typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

public:

  char_producer<_CharT>* _M_fn;

  /*

   * Char_producer is owned by the

   * rope and should be explicitly

   * deleted when the rope becomes

   * inaccessible.

   */

  bool _M_delete_when_done;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)

  typedef typename _Rope_RopeRep<_CharT,_Alloc>::allocator_type allocator_type;

# ifdef _STLP_NO_ARROW_OPERATOR

  _Rope_RopeFunction() {}