// xstring internal header (from <string>)
#ifndef _XSTRING_
#define _XSTRING_

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(level, E)
#endif
#pragma info(restore)

#if __IBMCPP__ < 400
#error This file to be used only with IBM VisualAge C++ v4 and later compilers.
#endif /* __IBMCPP__ */

#pragma namemangling(ansi)

   /********************************************************************/
   /*  <xstring> header file                                           */
   /*                                                                  */
   /*  VisualAge C++, Version 4.0                                      */
   /*    Licensed Material - Property of IBM                           */
   /*                                                                  */
   /*  5801-AAR and Other Materials                                    */
   /*                                                                  */
   /*  (c) Copyright IBM Corp 1991, 1998. All rights reserved.         */
   /*                                                                  */
   /*                                                                  */
   /*  Licensed Materials.                                             */
   /*                                                                  */
   /*  Dinkum C++ Library                                              */
   /*  Copyright (c) 1998.  Licensed to IBM Corp. and its suppliers.   */
   /*                                                                  */
   /********************************************************************/

#include <xmemory>
_STD_BEGIN
		// CLASS _String_base
class _String_base {
public:
	void _Xlen() const;
	void _Xran() const;
	};


		// TEMPLATE CLASS _String_val
template<class _Ty, class _A>
	class _String_val : public _String_base {
protected:
	_String_val(_A _Al = _A())
		: _Alval(_Al) {}
	typedef typename _A::template
		rebind<_Ty>::other _Alty;
	_Alty _Alval;
	};

		// TEMPLATE CLASS basic_string
template<class _E,
	class _Tr _TDEF(char_traits<_E>),
	class _Ax _TDEF(allocator<_E>) >
	class basic_string : public _String_val<_E, _Ax> {
public:
	typedef basic_string<_E, _Tr, _Ax> _Myt;
	typedef _String_val<_E, _Ax> _Mybase;
	typedef typename _Mybase::_Alty _A;
	typedef typename _A::size_type size_type;
	typedef typename _A::difference_type difference_type;
	typedef typename _A::pointer _Tptr;
	typedef typename _A::const_pointer _Ctptr;
	typedef _Tptr pointer;
	typedef _Ctptr const_pointer;
	typedef typename _A::reference reference;
	typedef typename _A::const_reference const_reference;
	typedef typename _A::value_type value_type;
	typedef _Ptrit<value_type, difference_type, _Tptr,
		reference, _Tptr, reference> iterator;
	typedef _Ptrit<value_type, difference_type, _Ctptr,
		const_reference, _Tptr, reference> const_iterator;
	typedef typename std::reverse_iterator<iterator>
		reverse_iterator;
	typedef typename std::reverse_iterator<const_iterator>
		const_reverse_iterator;

	basic_string()
		: _Mybase()
		{_Tidy(); }
	explicit basic_string(const _A& _Al)
		: _Mybase(_Al)
		{_Tidy(); }
	basic_string(const _Myt& _X)
		: _Mybase(_X._Alval)
		{_Tidy(), assign(_X, 0, npos); }
	basic_string(const _Myt& _X, size_type _P,
		size_type _M = npos)
		: _Mybase()
		{_Tidy(), assign(_X, _P, _M); }
	basic_string(const _Myt& _X, size_type _P, size_type _M,
		const _A& _Al)
		: _Mybase(_Al)
		{_Tidy(), assign(_X, _P, _M); }
	basic_string(const _E *_S, size_type _N)
		: _Mybase()
		{_Tidy(), assign(_S, _N); }
	basic_string(const _E *_S, size_type _N, const _A& _Al)
		: _Mybase(_Al)
		{_Tidy(), assign(_S, _N); }
	basic_string(const _E *_S)
		: _Mybase()
		{_Tidy(), assign(_S); }
	basic_string(const _E *_S, const _A& _Al)
		: _Mybase(_Al)
		{_Tidy(), assign(_S); }
	basic_string(size_type _N, _E _C)
		: _Mybase()
		{_Tidy(), assign(_N, _C); }
	basic_string(size_type _N, _E _C, const _A& _Al)
		: _Mybase(_Al)
		{_Tidy(), assign(_N, _C); }
	template<class _It>
		basic_string(_It _F, _It _L)
		: _Mybase()
		{_Construct(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		basic_string(_It _F, _It _L, const _A& _Al)
		: _Mybase(_Al)
		{_Construct(_F, _L, _Iter_cat(_F)); }
	template<class _It>
		void _Construct(_It _F, _It _L, _Int_iterator_tag)
		{_Tidy(), assign((size_type)_F, (_E)_L); }
	template<class _It>
		void _Construct(_It _F, _It _L, input_iterator_tag)
		{_Tidy();
		for (; _F != _L; ++_F)
			append((size_type)1, (_E)*_F); }
	template<class _It>
		void _Construct(_It _F, _It _L, forward_iterator_tag)
		{_Tidy();
		size_type _M = 0;
		_Distance(_F, _L, _M);
		reserve(_M);
		for (; _F != _L; ++_F)
			append((size_type)1, (_E)*_F); }
	basic_string(iterator _F, iterator _L)
		: _Mybase()
		{_Tidy();
		if (_F != _L)
			assign(&*_F, _L - _F); }
	basic_string(iterator _F, iterator _L, const _A& _Al)
		: _Mybase(_Al)
		{_Tidy();
		if (_F != _L)
			assign(&*_F, _L - _F); }
	typedef const_pointer _It;
	basic_string(_It _F, _It _L)
		: _Mybase()
		{_Tidy();
		if (_F != _L)
			assign(&*_F, _L - _F); }
	basic_string(_It _F, _It _L, const _A& _Al)
		: _Mybase(_Al)
		{_Tidy();
		if (_F != _L)
			assign(&*_F, _L - _F); }
	~basic_string()
		{_Tidy(true); }
	typedef _Tr traits_type;
	typedef _A allocator_type;
#ifdef __MULTI__
	enum _Mref {_FROZEN = 0};
#else
	enum _Mref {_FROZEN = 255};
#endif
	static const size_type npos;
	_Myt& operator=(const _Myt& _X)
		{return (assign(_X)); }
	_Myt& operator=(const _E *_S)
		{return (assign(_S)); }
	_Myt& operator=(_E _C)
		{return (assign(1, _C)); }
	_Myt& operator+=(const _Myt& _X)
		{return (append(_X)); }
	_Myt& operator+=(const _E *_S)
		{return (append(_S)); }
	_Myt& operator+=(_E _C)
		{return (append((size_type)1, _C)); }
	_Myt& append(const _Myt& _X)
		{return (append(_X, 0, npos)); }
	_Myt& append(const _Myt& _X, size_type _P, size_type _M)
		{if (_X.size() < _P)
			_String_base::_Xran();
		size_type _N = _X.size() - _P;
		if (_N < _M)
			_M = _N;
		if (npos - _Len <= _M)
			_String_base::_Xlen();
		if (0 < _M && _Grow(_N = _Len + _M))
			{_Tr::copy(_Ptr + _Len, &_X.c_str()[_P], _M);
			_Eos(_N); }
		return (*this); }
	_Myt& append(const _E *_S, size_type _M)
		{if (_Inside(_S))
			return (append(*this, _S - _Ptr, _M));
		if (npos - _Len <= _M)
			_String_base::_Xlen();
		size_type _N;
		if (0 < _M && _Grow(_N = _Len + _M))
			{_Tr::copy(_Ptr + _Len, _S, _M);
			_Eos(_N); }
		return (*this); }
	_Myt& append(const _E *_S)
		{return (append(_S, _Tr::length(_S))); }
	_Myt& append(size_type _M, _E _C)
		{if (npos - _Len <= _M)
			_String_base::_Xlen();
		size_type _N;
		if (0 < _M && _Grow(_N = _Len + _M))
			{_Tr::assign(_Ptr + _Len, _M, _C);
			_Eos(_N); }
		return (*this); }
	template<class _It>
		_Myt& append(_It _F, _It _L)
		{return (_Append(_F, _L, _Iter_cat(_F))); }
	template<class _It>
		_Myt& _Append(_It _F, _It _L, _Int_iterator_tag)
		{return (append((size_type)_F, (_E)_L)); }
	template<class _It>
		_Myt& _Append(_It _F, _It _L, input_iterator_tag)
		{return (replace(end(), end(), _F, _L)); }
	_Myt& assign(const _Myt& _X)
		{return (assign(_X, 0, npos)); }
	_Myt& assign(const _Myt& _X, size_type _P, size_type _M)
		{if (_X.size() < _P)
			_String_base::_Xran();
		size_type _N = _X.size() - _P;
		if (_M < _N)
			_N = _M;
		if (this == &_X)
			erase((size_type)(_P + _N)), erase(0, _P);
		else if (0 < _N && _N == _X.size()
			&& _Refcnt(_X.c_str()) < _FROZEN - 1
			&& _Mybase::_Alval == _X._Alval)
			{_Tidy(true);
			_Ptr = (_E *)_X.c_str();
			_Len = _X.size();
			_Res = _X.capacity();
			++_Refcnt(_Ptr); }
		else if (_Grow(_N, true))
			{_Tr::copy(_Ptr, &_X.c_str()[_P], _N);
			_Eos(_N); }
		return (*this); }
	_Myt& assign(const _E *_S, size_type _N)
		{if (_Inside(_S))
			return (assign(*this, _S - _Ptr, _N));
		if (_Grow(_N, true))
			{_Tr::copy(_Ptr, _S, _N);
			_Eos(_N); }
		return (*this); }
	_Myt& assign(const _E *_S)
		{return (assign(_S, _Tr::length(_S))); }
	_Myt& assign(size_type _N, _E _C)
		{if (_N == npos)
			_String_base::_Xlen();
		if (_Grow(_N, true))
			{_Tr::assign(_Ptr, _N, _C);
			_Eos(_N); }
		return (*this); }
	template<class _It>
		_Myt& assign(_It _F, _It _L)
		{return (_Assign(_F, _L, _Iter_cat(_F))); }
	template<class _It>
		_Myt& _Assign(_It _F, _It _L, _Int_iterator_tag)
		{return (assign((size_type)_F, (_E)_L)); }
	template<class _It>
		_Myt& _Assign(_It _F, _It _L, input_iterator_tag)
		{return (replace(begin(), end(), _F, _L)); }
	_Myt& insert(size_type _P0, const _Myt& _X)
		{return (insert(_P0, _X, 0, npos)); }
	_Myt& insert(size_type _P0, const _Myt& _X, size_type _P,
		size_type _M)
		{if (_Len < _P0 || _X.size() < _P)
			_String_base::_Xran();
		size_type _N = _X.size() - _P;
		if (_N < _M)
			_M = _N;
		if (npos - _Len <= _M)
			_String_base::_Xlen();
		if (0 < _M && _Grow(_N = _Len + _M))
			{_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0, _Len - _P0);
			if (this == &_X)
				_Tr::move(_Ptr + _P0,
					_Ptr + (_P0 < _P ? _P + _M : _P), _M);
			else
				_Tr::copy(_Ptr + _P0, &_X.c_str()[_P], _M);
			_Eos(_N); }
		return (*this); }
	_Myt& insert(size_type _P0, const _E *_S, size_type _M)
		{if (_Inside(_S))
			return (insert(_P0, *this, _S - _Ptr, _M));
		if (_Len < _P0)
			_String_base::_Xran();
		if (npos - _Len <= _M)
			_String_base::_Xlen();
		size_type _N;
		if (0 < _M && _Grow(_N = _Len + _M))
			{_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0, _Len - _P0);
			_Tr::copy(_Ptr + _P0, _S, _M);
			_Eos(_N); }
		return (*this); }
	_Myt& insert(size_type _P0, const _E *_S)
		{return (insert(_P0, _S, _Tr::length(_S))); }
	_Myt& insert(size_type _P0, size_type _M, _E _C)
		{if (_Len < _P0)
			_String_base::_Xran();
		if (npos - _Len <= _M)
			_String_base::_Xlen();
		size_type _N;
		if (0 < _M && _Grow(_N = _Len + _M))
			{_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0, _Len - _P0);
			_Tr::assign(_Ptr + _P0, _M, _C);
			_Eos(_N); }
		return (*this); }
	iterator insert(iterator _P)
		{return (insert(_P, _E())); }
	iterator insert(iterator _P, _E _C)
		{size_type _P0 = _Pdif(_P, begin());
		insert(_P0, 1, _C);
		return (begin() + _P0); }
	void insert(iterator _P, size_type _M, _E _C)
		{size_type _P0 = _Pdif(_P, begin());
		insert(_P0, _M, _C); }
	template<class _It>
		void insert(iterator _P, _It _F, _It _L)
		{_Insert(_P, _F, _L, _Iter_cat(_F)); }
	template<class _It>
		void _Insert(iterator _P, _It _F, _It _L,
			_Int_iterator_tag)
		{insert(_P, (size_type)_F, (_E)_L); }
	template<class _It>
		void _Insert(iterator _P, _It _F, _It _L,
			input_iterator_tag)
		{replace(_P, _P, _F, _L); }
	_Myt& erase(size_type _P0 = 0, size_type _M = npos)
		{if (_Len < _P0)
			_String_base::_Xran();
		if (_Len - _P0 < _M)
			_M = _Len - _P0;
		if (0 < _M)
			{_Freeze();
			_Tr::move(_Ptr + _P0, _Ptr + _P0 + _M,
				_Len - _P0 - _M);
			size_type _N = _Len - _M;
			if (_Grow(_N))
				_Eos(_N); }
		return (*this); }
	iterator erase(iterator _P)
		{size_type _M = _Pdif(_P, begin());
		erase(_M, 1);
		return (iterator(_Psum(_Ptr, _M))); }
	iterator erase(iterator _F, iterator _L)
		{size_type _M = _Pdif(_F, begin());
		erase(_M, _Pdif(_L, _F));
		return (iterator(_Psum(_Ptr, _M))); }
	void clear()
		{erase(begin(), end()); }
	_Myt& replace(size_type _P0, size_type _N0, const _Myt& _X)
		{return (replace(_P0, _N0, _X, 0, npos)); }
	_Myt& replace(size_type _P0, size_type _N0, const _Myt& _X,
		size_type _P, size_type _M)
		{if (_Len < _P0 || _X.size() < _P)
			_String_base::_Xran();
		if (_Len - _P0 < _N0)
			_N0 = _Len - _P0;
		size_type _N = _X.size() - _P;
		if (_N < _M)
			_M = _N;
		if (npos - _M <= _Len - _N0)
			_String_base::_Xlen();
		size_type _Nm = _Len - _N0 - _P0;
		_N = _Len + _M - _N0;
		if (_Len < _N)
			_Grow(_N);
		else if (0 < _M || 0 < _N0)
			_Freeze();
		if (this != &_X)
			{_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm);
			_Tr::copy(_Ptr + _P0, &_X.c_str()[_P], _M); }
		else if (_M <= _N0)
			{_Tr::move(_Ptr + _P0, _Ptr + _P, _M);
			_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm); }
		else if (_P <= _P0)
			{_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm);
			_Tr::move(_Ptr + _P0, _Ptr + _P, _M); }
		else if (_P0 + _N0 <= _P)
			{_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm);
			_Tr::move(_Ptr + _P0, _Ptr + (_P + _M - _N0), _M); }
		else
			{_Tr::move(_Ptr + _P0, _Ptr + _P, _N0);
			_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm);
			_Tr::move(_Ptr + _P0 + _N0, _Ptr + _P + _M,
				_M - _N0); }
		if (_Len < _N || _Grow(_N))
			_Eos(_N);
		return (*this); }
	_Myt& replace(size_type _P0, size_type _N0, const _E *_S,
		size_type _M)
		{if (_Inside(_S))
			return (replace(_P0, _N0, *this, _S - _Ptr, _M));
		if (_Len < _P0)
			_String_base::_Xran();
		if (_Len - _P0 < _N0)
			_N0 = _Len - _P0;
		if (npos - _M <= _Len - _N0)
			_String_base::_Xlen();
		size_type _Nm = _Len - _N0 - _P0;
		if (_M < _N0)
			{_Freeze();
			_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm); }
		size_type _N;
		if ((0 < _M || 0 < _N0) && _Grow(_N = _Len + _M - _N0))
			{if (_N0 < _M)
				_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm);
			_Tr::copy(_Ptr + _P0, _S, _M);
			_Eos(_N); }
		return (*this); }
	_Myt& replace(size_type _P0, size_type _N0, const _E *_S)
		{return (replace(_P0, _N0, _S, _Tr::length(_S))); }
	_Myt& replace(size_type _P0, size_type _N0,
		size_type _M, _E _C)
		{if (_Len < _P0)
			_String_base::_Xran();
		if (_Len - _P0 < _N0)
			_N0 = _Len - _P0;
		if (npos - _M <= _Len - _N0)
			_String_base::_Xlen();
		size_type _Nm = _Len - _N0 - _P0;
		if (_M < _N0)
			{_Freeze();
			_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm); }
		size_type _N;
		if ((0 < _M || 0 < _N0) && _Grow(_N = _Len + _M - _N0))
			{if (_N0 < _M)
				_Tr::move(_Ptr + _P0 + _M, _Ptr + _P0 + _N0, _Nm);
			_Tr::assign(_Ptr + _P0, _M, _C);
			_Eos(_N); }
		return (*this); }
	_Myt& replace(iterator _F, iterator _L, const _Myt& _X)
		{return (replace(
			_Pdif(_F, begin()), _Pdif(_L, _F), _X)); }
	_Myt& replace(iterator _F, iterator _L, const _E *_S,
		size_type _M)
		{return (replace(
			_Pdif(_F, begin()), _Pdif(_L, _F), _S, _M)); }
	_Myt& replace(iterator _F, iterator _L, const _E *_S)
		{return (replace(
			_Pdif(_F, begin()), _Pdif(_L, _F), _S)); }
	_Myt& replace(iterator _F, iterator _L,	size_type _M, _E _C)
		{return (replace(
			_Pdif(_F, begin()), _Pdif(_L, _F), _M, _C)); }
	template<class _It>
		_Myt& replace(iterator _F1, iterator _L1,
			_It _F2, _It _L2)
		{return (_Replace(_F1, _L1, _F2, _L2, _Iter_cat(_F2))); }
	template<class _It>
		_Myt& _Replace(iterator _F1, iterator _L1,
			_It _F2, _It _L2, _Int_iterator_tag)
		{return (replace(_F1, _L1, (size_type)_F2, (_E)_L2)); }
	template<class _It>
		_Myt& _Replace(iterator _F1, iterator _L1,
			_It _F2, _It _L2, input_iterator_tag)
		{_Myt _X;
		for (; _F2 != _L2; ++_F2)
			_X.append((size_type)1, (_E)*_F2);
		replace(_F1, _L1, _X);
		return (*this); }
	_Myt& replace(iterator _F1, iterator _L1,
		iterator _F2, iterator _L2)
		{if (_F2 == _L2)
			erase(_Pdif(_F1, begin()), _Pdif(_L1, _F1));
		else
			replace(_Pdif(_F1, begin()), _Pdif(_L1, _F1),
				&*_F2, _L2 - _F2);
		return (*this); }
	_Myt& replace(iterator _F1, iterator _L1,
		_It _F2, _It _L2)
		{if (_F2 == _L2)
			erase(_Pdif(_F1, begin()), _Pdif(_L1, _F1));
		else
			replace(_Pdif(_F1, begin()), _Pdif(_L1, _F1),
				&*_F2, _L2 - _F2);
		return (*this); }
	iterator begin()
		{_Freeze();
		return (iterator(_Ptr)); }
	const_iterator begin() const
		{return (const_iterator(_Ptr)); }
	iterator end()
		{_Freeze();
		return (iterator(_Psum(_Ptr, _Len))); }
	const_iterator end() const
		{return (const_iterator(_Psum(_Ptr, _Len))); }
	reverse_iterator rbegin()
		{return (reverse_iterator(end())); }
	const_reverse_iterator rbegin() const
		{return (const_reverse_iterator(end())); }
	reverse_iterator rend()
		{return (reverse_iterator(begin())); }
	const_reverse_iterator rend() const
		{return (const_reverse_iterator(begin())); }
	reference at(size_type _P0)
		{if (_Len <= _P0)
			_String_base::_Xran();
		_Freeze();
		return (_Ptr[_P0]); }
	const_reference at(size_type _P0) const
		{if (_Len <= _P0)
			_String_base::_Xran();
		return (_Ptr[_P0]); }
	reference operator[](size_type _P0)
		{if (_Len < _P0 || _Ptr == 0)
			return ((reference)*_Nullstr());
		_Freeze();
		return (_Ptr[_P0]); }
	const_reference operator[](size_type _P0) const
		{if (_Ptr == 0)
			return (*_Nullstr());
		else
			return (_Ptr[_P0]); }
	void push_back(_E _C)
		{insert(end(), _C); }
	const _E *c_str() const
		{return (_Ptr == 0 ? _Nullstr() : _Ptr); }
	const _E *data() const
		{return (c_str()); }
	size_type length() const
		{return (_Len); }
	size_type size() const
		{return (_Len); }
	size_type max_size() const
		{size_type _N = _Mybase::_Alval.max_size();
		return (_N <= 2 ? 1 : _N - 2); }
	void resize(size_type _N)
		{resize(_N, _E()); }
	void resize(size_type _N, _E _C)
		{_N <= _Len ? erase(_N) : append(_N - _Len, _C); }
	size_type capacity() const
		{return (_Res); }
	void reserve(size_type _N = 0)
		{if (_Res < _N)
			_Grow(_N); }
	bool empty() const
		{return (_Len == 0); }
	size_type copy(_E *_S, size_type _N, size_type _P0 = 0) const
		{if (_Len < _P0)
			_String_base::_Xran();
		if (_Len - _P0 < _N)
			_N = _Len - _P0;
		if (0 < _N)
			_Tr::copy(_S, _Ptr + _P0, _N);
		return (_N); }
	void swap(_Myt& _X)
		{if (_Mybase::_Alval == _X._Alval)
			{_E *_Tptr = _Ptr;
			_Ptr = _X._Ptr, _X._Ptr = _Tptr;
			size_type _Tlen = _Len;
			_Len = _X._Len, _X._Len = _Tlen;
			size_type _Tres = _Res;
			_Res = _X._Res, _X._Res = _Tres; }
		else
			{_Myt _Ts = *this; *this = _X, _X = _Ts; }}
	size_type find(const _Myt& _X, size_type _P = 0) const
		{return (find(_X.c_str(), _P, _X.size())); }
	size_type find(const _E *_S, size_type _P,
		size_type _N) const
		{if (_N == 0 && _P <= _Len)
			return (_P);
		size_type _Nm;
		if (_P < _Len && _N <= (_Nm = _Len - _P))
			{const _E *_U, *_V;
			for (_Nm -= _N - 1, _V = _Ptr + _P;
				(_U = _Tr::find(_V, _Nm, *_S)) != 0;
				_Nm -= _U - _V + 1, _V = _U + 1)
				if (_Tr::compare(_U, _S, _N) == 0)
					return (_U - _Ptr); }
		return (npos); }
	size_type find(const _E *_S, size_type _P = 0) const
		{return (find(_S, _P, _Tr::length(_S))); }
	size_type find(_E _C, size_type _P = 0) const
		{return (find((const _E *)&_C, _P, 1)); }
	size_type rfind(const _Myt& _X, size_type _P = npos) const
		{return (rfind(_X.c_str(), _P, _X.size())); }
	size_type rfind(const _E *_S, size_type _P,
		size_type _N) const
		{if (_N == 0)
			return (_P < _Len ? _P : _Len);
		if (_N <= _Len)
			for (const _E *_U = _Ptr +
				+ (_P < _Len - _N ? _P : _Len - _N); ; --_U)
				if (_Tr::eq(*_U, *_S)
					&& _Tr::compare(_U, _S, _N) == 0)
					return (_U - _Ptr);
				else if (_U == _Ptr)
					break;
		return (npos); }
	size_type rfind(const _E *_S, size_type _P = npos) const
		{return (rfind(_S, _P, _Tr::length(_S))); }
	size_type rfind(_E _C, size_type _P = npos) const
		{return (rfind((const _E *)&_C, _P, 1)); }
	size_type find_first_of(const _Myt& _X,
		size_type _P = 0) const
		{return (find_first_of(_X.c_str(), _P, _X.size())); }
	size_type find_first_of(const _E *_S, size_type _P,
		size_type _N) const
		{if (0 < _N && _P < _Len)
			{const _E *const _V = _Ptr + _Len;
			for (const _E *_U = _Ptr + _P; _U < _V; ++_U)
				if (_Tr::find(_S, _N, *_U) != 0)
					return (_U - _Ptr); }
		return (npos); }
	size_type find_first_of(const _E *_S, size_type _P = 0) const
		{return (find_first_of(_S, _P, _Tr::length(_S))); }
	size_type find_first_of(_E _C, size_type _P = 0) const
		{return (find((const _E *)&_C, _P, 1)); }
	size_type find_last_of(const _Myt& _X,
		size_type _P = npos) const
		{return (find_last_of(_X.c_str(), _P, _X.size())); }
	size_type find_last_of(const _E *_S, size_type _P,
		size_type _N) const
		{if (0 < _N && 0 < _Len)
			for (const _E *_U = _Ptr
				+ (_P < _Len ? _P : _Len - 1); ; --_U)
				if (_Tr::find(_S, _N, *_U) != 0)
					return (_U - _Ptr);
				else if (_U == _Ptr)
					break;
		return (npos); }
	size_type find_last_of(const _E *_S,
		size_type _P = npos) const
		{return (find_last_of(_S, _P, _Tr::length(_S))); }
	size_type find_last_of(_E _C, size_type _P = npos) const
		{return (rfind((const _E *)&_C, _P, 1)); }
	size_type find_first_not_of(const _Myt& _X,
		size_type _P = 0) const
		{return (find_first_not_of(_X.c_str(), _P,
			_X.size())); }
	size_type find_first_not_of(const _E *_S, size_type _P,
		size_type _N) const
		{if (_P < _Len)
			{const _E *const _V = _Ptr + _Len;
			for (const _E *_U = _Ptr + _P; _U < _V; ++_U)
				if (_Tr::find(_S, _N, *_U) == 0)
					return (_U - _Ptr); }
		return (npos); }
	size_type find_first_not_of(const _E *_S,
		size_type _P = 0) const
		{return (find_first_not_of(_S, _P, _Tr::length(_S))); }
	size_type find_first_not_of(_E _C, size_type _P = 0) const
		{return (find_first_not_of((const _E *)&_C, _P, 1)); }
	size_type find_last_not_of(const _Myt& _X,
		size_type _P = npos) const
		{return (find_last_not_of(_X.c_str(), _P, _X.size())); }
	size_type find_last_not_of(const _E *_S, size_type _P,
		 size_type _N) const
		{if (0 < _Len)
			for (const _E *_U = _Ptr
				+ (_P < _Len ? _P : _Len - 1); ; --_U)
				if (_Tr::find(_S, _N, *_U) == 0)
					return (_U - _Ptr);
				else if (_U == _Ptr)
					break;
		return (npos); }
	size_type find_last_not_of(const _E *_S,
		size_type _P = npos) const
		{return (find_last_not_of(_S, _P, _Tr::length(_S))); }
	size_type find_last_not_of(_E _C, size_type _P = npos) const
		{return (find_last_not_of((const _E *)&_C, _P, 1)); }
	_Myt substr(size_type _P = 0, size_type _M = npos) const
		{return (_Myt(*this, _P, _M)); }
	int compare(const _Myt& _X) const
		{return (compare(0, _Len, _X.c_str(), _X.size())); }
	int compare(size_type _P0, size_type _N0,
		const _Myt& _X) const
		{return (compare(_P0, _N0, _X, 0, npos)); }
	int compare(size_type _P0, size_type _N0, const _Myt& _X,
		size_type _P, size_type _M) const
		{if (_X.size() < _P)
			_String_base::_Xran();
		if (_X._Len - _P < _M)
			_M = _X._Len - _P;
		return (compare(_P0, _N0, _X.c_str() + _P, _M)); }
	int compare(const _E *_S) const
		{return (compare(0, _Len, _S, _Tr::length(_S))); }
	int compare(size_type _P0, size_type _N0, const _E *_S) const
		{return (compare(_P0, _N0, _S, _Tr::length(_S))); }
	int compare(size_type _P0, size_type _N0, const _E *_S,
		size_type _M) const
		{if (_Len < _P0)
			_String_base::_Xran();
		if (_Len - _P0 < _N0)
			_N0 = _Len - _P0;
		size_type _Ans = _N0 == 0 ? 0
			: _Tr::compare(_Psum(_Ptr, _P0), _S,
				_N0 < _M ? _N0 : _M);
		return (_Ans != 0 ? _Ans : _N0 < _M ? -1
			: _N0 == _M ? 0 : +1); }
	allocator_type get_allocator() const
		{return (_Mybase::_Alval); }
private:
	enum {_MIN_SIZE = sizeof (_E) <= 32 ? 31 : 7};
	void _Copy(size_type _N)
		{size_type _Ns = _N | _MIN_SIZE;
		if (max_size() < _Ns)
			_Ns = _N;
		_E *_S;
		_TRY_BEGIN
			_S = _Mybase::_Alval.allocate(_Ns + 2, (void *)0);
		_CATCH_ALL
			_Ns = _N;
			_S = _Mybase::_Alval.allocate(_Ns + 2, (void *)0);
		_CATCH_END
		if (0 < _Len)
			_Tr::copy(_S + 1, _Ptr, _Len);
		size_type _Olen = _Len;
		_Tidy(true);
		_Ptr = _S + 1;
		_Refcnt(_Ptr) = 0;
		_Res = _Ns;
		_Eos(_Olen); }
	void _Eos(size_type _N)
		{_Tr::assign(_Ptr[_Len = _N], _E()); }
	void _Freeze()
		{if (_Ptr != 0
			&& _Refcnt(_Ptr) != 0 && _Refcnt(_Ptr) != _FROZEN)
			_Grow(_Len);
		if (_Ptr != 0)
			_Refcnt(_Ptr) = _FROZEN; }
	bool _Grow(size_type _N, bool _Trim = false)
		{if (max_size() < _N)
			_String_base::_Xlen();
		if (_Trim)
			_Len = 0;
		else if (_N < _Len)
			_Len = _N;
		if (_Ptr != 0
			&& _Refcnt(_Ptr) != 0 && _Refcnt(_Ptr) != _FROZEN)
			if (_N == 0)
				{_Tidy(true);
				return (false); }
			else
				{_Copy(_N);
				return (true); }
		if (_N == 0)
			{if (_Trim)
				_Tidy(true);
			else if (_Ptr != 0)
				_Eos(0);
			return (false); }
		else
			{if (_Trim && (_MIN_SIZE < _Res || _Res < _N))
				{_Tidy(true);
				_Copy(_N); }
			else if (!_Trim && _Res < _N)
				_Copy(_N);
			return (true); }}
	bool _Inside(const _E *_S)
		{return (_Ptr != 0 && _Ptr <= _S && _S <= _Ptr + _Len); }
	static const _E *_Nullstr()
		{static const _E _C = _E();
		return (&_C); }
	static size_type _Pdif(const_iterator _P2,
		const_iterator _P1)
		{return (_P2.base() == 0 ? 0 : _P2 - _P1); }
	static const_pointer _Psum(const_pointer _P, size_type _N)
		{return (_P == 0 ? 0 : _P + _N); }
	static pointer _Psum(pointer _P, size_type _N)
		{return (_P == 0 ? 0 : _P + _N); }
	unsigned char& _Refcnt(const _E *_U)
		{return (((unsigned char *)_U)[-1]); }
	void _Tidy(bool _Built = false)
		{if (!_Built || _Ptr == 0)
			;
		else if (_Refcnt(_Ptr) == 0 || _Refcnt(_Ptr) == _FROZEN)
			_Mybase::_Alval.deallocate(_Ptr - 1, _Res + 2);
		else
			--_Refcnt(_Ptr);
		_Ptr = 0, _Len = 0, _Res = 0; }
	_E *_Ptr;
	size_type _Len, _Res;
	};
template<class _E, class _Tr, class _A>
	const typename basic_string<_E, _Tr, _A>::size_type
		basic_string<_E, _Tr, _A>::npos =
			(basic_string<_E, _Tr, _A>::size_type)(-1);
template<class _E, class _Tr, class _A> inline
	void swap(basic_string<_E, _Tr, _A>& _X,
		basic_string<_E, _Tr, _A>& _Y)
	{_X.swap(_Y); }
typedef basic_string<char, char_traits<char>, allocator<char> >
	string;
typedef basic_string<wchar_t, char_traits<wchar_t>,
	allocator<wchar_t> > wstring;
_STD_END

#pragma namemangling()

#pragma info(none)
#ifndef __CHKHDR__
#  pragma report(pop)
#endif
#pragma info(restore)

#endif /* _XSTRING */

/*
 * Copyright (c) 1995 by P.J. Plauger.  ALL RIGHTS RESERVED. 
 * Consult your license regarding permissions and restrictions.
V2.2:0081 */
