assets/manual_img/Bildschirmfoto_2016-09-17_09-50-27.png

/*
   Basic Unicode string class for Irrlicht.
   Copyright (c) 2009-2011 John Norman

   This software is provided 'as-is', without any express or implied
   warranty. In no event will the authors be held liable for any
   damages arising from the use of this software.

   Permission is granted to anyone to use this software for any
   purpose, including commercial applications, and to alter it and
   redistribute it freely, subject to the following restrictions:

   1. The origin of this software must not be misrepresented; you
      must not claim that you wrote the original software. If you use
      this software in a product, an acknowledgment in the product
      documentation would be appreciated but is not required.

   2. Altered source versions must be plainly marked as such, and
      must not be misrepresented as being the original software.

   3. This notice may not be removed or altered from any source
      distribution.

   The original version of this class can be located at:
   http://irrlicht.suckerfreegames.com/

   John Norman
   john@suckerfreegames.com
*/

#pragma once

#if (__cplusplus > 199711L) || (_MSC_VER >= 1600) || defined(__GXX_EXPERIMENTAL_CXX0X__)
#	define USTRING_CPP0X
#	if defined(__GXX_EXPERIMENTAL_CXX0X__) && ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 5)))
#		define USTRING_CPP0X_NEWLITERALS
#	endif
#endif

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cstddef>

#ifdef _WIN32
#define __BYTE_ORDER 0
#define __LITTLE_ENDIAN 0
#define __BIG_ENDIAN 1
#elif defined(__MACH__) && defined(__APPLE__)
#include <machine/endian.h>
#elif defined(__FreeBSD__)
#include <sys/endian.h>
#else
#include <endian.h>
#endif

#ifdef USTRING_CPP0X
#	include <utility>
#endif

#ifndef USTRING_NO_STL
#	include <string>
#	include <iterator>
#	include <ostream>
#endif

#include "irrTypes.h"
#include "irrAllocator.h"
#include "irrArray.h"
#include "irrMath.h"
#include "irrString.h"
#include "path.h"

//! UTF-16 surrogate start values.
static const irr::u16 UTF16_HI_SURROGATE = 0xD800;
static const irr::u16 UTF16_LO_SURROGATE = 0xDC00;

//! Is a UTF-16 code point a surrogate?
#define UTF16_IS_SURROGATE(c)		(((c) & 0xF800) == 0xD800)
#define UTF16_IS_SURROGATE_HI(c)	(((c) & 0xFC00) == 0xD800)
#define UTF16_IS_SURROGATE_LO(c)	(((c) & 0xFC00) == 0xDC00)


namespace irr
{

	// Define our character types.
#ifdef USTRING_CPP0X_NEWLITERALS	// C++0x
	typedef char32_t uchar32_t;
	typedef char16_t uchar16_t;
	typedef char uchar8_t;
#else
	typedef u32 uchar32_t;
	typedef u16 uchar16_t;
	typedef u8 uchar8_t;
#endif

namespace core
{

namespace unicode
{

//! The unicode replacement character.  Used to replace invalid characters.
const irr::u16 UTF_REPLACEMENT_CHARACTER = 0xFFFD;

//! Convert a UTF-16 surrogate pair into a UTF-32 character.
//! \param high The high value of the pair.
//! \param low The low value of the pair.
//! \return The UTF-32 character expressed by the surrogate pair.
inline uchar32_t toUTF32(uchar16_t high, uchar16_t low)
{
	// Convert the surrogate pair into a single UTF-32 character.
	uchar32_t x = ((high & ((1 << 6) -1)) << 10) | (low & ((1 << 10) -1));
	uchar32_t wu = ((high >> 6) & ((1 << 5) - 1)) + 1;
	return (wu << 16) | x;
}

//! Swaps the endianness of a 16-bit value.
//! \return The new value.
inline uchar16_t swapEndian16(const uchar16_t& c)
{
	return ((c >> 8) & 0x00FF) | ((c << 8) & 0xFF00);
}

//! Swaps the endianness of a 32-bit value.
//! \return The new value.
inline uchar32_t swapEndian32(const uchar32_t& c)
{
	return  ((c >> 24) & 0x000000FF) |
			((c >> 8)  & 0x0000FF00) |
			((c << 8)  & 0x00FF0000) |
			((c << 24) & 0xFF000000);
}

//! The Unicode byte order mark.
const u16 BOM = 0xFEFF;

//! The size of the Unicode byte order mark in terms of the Unicode character size.
const u8 BOM_UTF8_LEN = 3;
const u8 BOM_UTF16_LEN = 1;
const u8 BOM_UTF32_LEN = 1;

//! Unicode byte order marks for file operations.
const u8 BOM_ENCODE_UTF8[3] = { 0xEF, 0xBB, 0xBF };
const u8 BOM_ENCODE_UTF16_BE[2] = { 0xFE, 0xFF };
const u8 BOM_ENCODE_UTF16_LE[2] = { 0xFF, 0xFE };
const u8 BOM_ENCODE_UTF32_BE[4] = { 0x00, 0x00, 0xFE, 0xFF };
const u8 BOM_ENCODE_UTF32_LE[4] = { 0xFF, 0xFE, 0x00, 0x00 };

//! The size in bytes of the Unicode byte marks for file operations.
const u8 BOM_ENCODE_UTF8_LEN = 3;
const u8 BOM_ENCODE_UTF16_LEN = 2;
const u8 BOM_ENCODE_UTF32_LEN = 4;

//! Unicode encoding type.
enum EUTF_ENCODE
{
	EUTFE_NONE		= 0,
	EUTFE_UTF8,
	EUTFE_UTF16,
	EUTFE_UTF16_LE,
	EUTFE_UTF16_BE,
	EUTFE_UTF32,
	EUTFE_UTF32_LE,
	EUTFE_UTF32_BE
};

//! Unicode endianness.
enum EUTF_ENDIAN
{
	EUTFEE_NATIVE	= 0,
	EUTFEE_LITTLE,
	EUTFEE_BIG
};

//! Returns the specified unicode byte order mark in a byte array.
//! The byte order mark is the first few bytes in a text file that signifies its encoding.
/** \param mode The Unicode encoding method that we want to get the byte order mark for.
		If EUTFE_UTF16 or EUTFE_UTF32 is passed, it uses the native system endianness. **/
//! \return An array that contains a byte order mark.
inline core::array<u8> getUnicodeBOM(EUTF_ENCODE mode)
{
#define COPY_ARRAY(source, size) \
	memcpy(ret.pointer(), source, size); \
	ret.set_used(size)

	core::array<u8> ret(4);
	switch (mode)
	{
		case EUTFE_UTF8:
			COPY_ARRAY(BOM_ENCODE_UTF8, BOM_ENCODE_UTF8_LEN);
			break;
		case EUTFE_UTF16:
			#ifdef __BIG_ENDIAN__
				COPY_ARRAY(BOM_ENCODE_UTF16_BE, BOM_ENCODE_UTF16_LEN);
			#else
				COPY_ARRAY(BOM_ENCODE_UTF16_LE, BOM_ENCODE_UTF16_LEN);
			#endif
			break;
		case EUTFE_UTF16_BE:
			COPY_ARRAY(BOM_ENCODE_UTF16_BE, BOM_ENCODE_UTF16_LEN);
			break;
		case EUTFE_UTF16_LE:
			COPY_ARRAY(BOM_ENCODE_UTF16_LE, BOM_ENCODE_UTF16_LEN);
			break;
		case EUTFE_UTF32:
			#ifdef __BIG_ENDIAN__
				COPY_ARRAY(BOM_ENCODE_UTF32_BE, BOM_ENCODE_UTF32_LEN);
			#else
				COPY_ARRAY(BOM_ENCODE_UTF32_LE, BOM_ENCODE_UTF32_LEN);
			#endif
			break;
		case EUTFE_UTF32_BE:
			COPY_ARRAY(BOM_ENCODE_UTF32_BE, BOM_ENCODE_UTF32_LEN);
			break;
		case EUTFE_UTF32_LE:
			COPY_ARRAY(BOM_ENCODE_UTF32_LE, BOM_ENCODE_UTF32_LEN);
			break;
		case EUTFE_NONE:
			// TODO sapier: fixed warning only,
			// don't know if something needs to be done here
			break;
	}
	return ret;

#undef COPY_ARRAY
}

//! Detects if the given data stream starts with a unicode BOM.
//! \param data The data stream to check.
//! \return The unicode BOM associated with the data stream, or EUTFE_NONE if none was found.
inline EUTF_ENCODE determineUnicodeBOM(const char* data)
{
	if (memcmp(data, BOM_ENCODE_UTF8, 3) == 0) return EUTFE_UTF8;
	if (memcmp(data, BOM_ENCODE_UTF16_BE, 2) == 0) return EUTFE_UTF16_BE;
	if (memcmp(data, BOM_ENCODE_UTF16_LE, 2) == 0) return EUTFE_UTF16_LE;
	if (memcmp(data, BOM_ENCODE_UTF32_BE, 4) == 0) return EUTFE_UTF32_BE;
	if (memcmp(data, BOM_ENCODE_UTF32_LE, 4) == 0) return EUTFE_UTF32_LE;
	return EUTFE_NONE;
}

} // end namespace unicode


//! UTF-16 string class.
template <typename TAlloc = irrAllocator<uchar16_t> >
class ustring16
{
public:

	///------------------///
	/// iterator classes ///
	///------------------///

	//! Access an element in a unicode string, allowing one to change it.
	class _ustring16_iterator_access
	{
		public:
			_ustring16_iterator_access(const ustring16<TAlloc>* s, u32 p) : ref(s), pos(p) {}

			//! Allow the class to be interpreted as a single UTF-32 character.
			operator uchar32_t() const
			{
				return _get();
			}

			//! Allow one to change the character in the unicode string.
			//! \param c The new character to use.
			//! \return Myself.
			_ustring16_iterator_access& operator=(const uchar32_t c)
			{
				_set(c);
				return *this;
			}

			//! Increments the value by 1.
			//! \return Myself.
			_ustring16_iterator_access& operator++()
			{
				_set(_get() + 1);
				return *this;
			}

			//! Increments the value by 1, returning the old value.
			//! \return A unicode character.
			uchar32_t operator++(int)
			{
				uchar32_t old = _get();
				_set(old + 1);
				return old;
			}

			//! Decrements the value by 1.
			//! \return Myself.
			_ustring16_iterator_access& operator--()
			{
				_set(_get() - 1);
				return *this;
			}

			//! Decrements the value by 1, returning the old value.
			//! \return A unicode character.
			uchar32_t operator--(int)
			{
				uchar32_t old = _get();
				_set(old - 1);
				return old;
			}

			//! Adds to the value by a specified amount.
			//! \param val The amount to add to this character.
			//! \return Myself.
			_ustring16_iterator_access& operator+=(int val)
			{
				_set(_get() + val);
				return *this;
			}

			//! Subtracts from the value by a specified amount.
			//! \param val The amount to subtract from this character.
			//! \return Myself.
			_ustring16_iterator_access& operator-=(int val)
			{
				_set(_get() - val);
				return *this;
			}

			//! Multiples the value by a specified amount.
			//! \param val The amount to multiply this character by.
			//! \return Myself.
			_ustring16_iterator_access& operator*=(int val)
			{
				_set(_get() * val);
				return *this;
			}

			//! Divides the value by a specified amount.
			//! \param val The amount to divide this character by.
			//! \return Myself.
			_ustring16_iterator_access& operator/=(int val)
			{
				_set(_get() / val);
				return *this;
			}

			//! Modulos the value by a specified amount.
			//! \param val The amount to modulo this character by.
			//! \return Myself.
			_ustring16_iterator_access& operator%=(int val)
			{
				_set(_get() % val);
				return *this;
			}

			//! Adds to the value by a specified amount.
			//! \param val The amount to add to this character.
			//! \return A unicode character.
			uchar32_t operator+(int val) const
			{
				return _get() + val;
			}

			//! Subtracts from the value by a specified amount.
			//! \param val The amount to subtract from this character.
			//! \return A unicode character.
			uchar32_t operator-(int val) const
			{
				return _get() - val;
			}

			//! Multiplies the value by a specified amount.
			//! \param val The amount to multiply this character by.
			//! \return A unicode character.
			uchar32_t operator*(int val) const
			{
				return _get() * val;
			}

			//! Divides the value by a specified amount.
			//! \param val The amount to divide this character by.
			//! \return A unicode character.
			uchar32_t operator/(int val) const
			{
				return _get() / val;
			}

			//! Modulos the value by a specified amount.
			//! \param val The amount to modulo this character by.
			//! \return A unicode character.
			uchar32_t operator%(int val) const
			{
				return _get() % val;
			}

		private:
			//! Gets a uchar32_t from our current position.
			uchar32_t _get() const
			{
				const uchar16_t* a = ref->c_str();
				if (!UTF16_IS_SURROGATE(a[pos]))
					return static_cast<uchar32_t>(a[pos]);
				else
				{
					if (pos + 1 >= ref->size_raw())
						return 0;

					return unicode::toUTF32(a[pos], a[pos + 1]);
				}
			}

			//! Sets a uchar32_t at our current position.
			void _set(uchar32_t c)
			{
				ustring16<TAlloc>* ref2 = const_cast<ustring16<TAlloc>*>(ref);
				const uchar16_t* a = ref2->c_str();
				if (c > 0xFFFF)
				{
					// c will be multibyte, so split it up into the high and low surrogate pairs.
					uchar16_t x = static_cast<uchar16_t>(c);
					uchar16_t vh = UTF16_HI_SURROGATE | ((((c >> 16) & ((1 << 5) - 1)) - 1) << 6) | (x >> 10);
					uchar16_t vl = UTF16_LO_SURROGATE | (x & ((1 << 10) - 1));

					// If the previous position was a surrogate pair, just replace them.  Else, insert the low pair.
					if (UTF16_IS_SURROGATE_HI(a[pos]) && pos + 1 != ref2->size_raw())
						ref2->replace_raw(vl, static_cast<u32>(pos) + 1);
					else ref2->insert_raw(vl, static_cast<u32>(pos) + 1);

					ref2->replace_raw(vh, static_cast<u32>(pos));
				}
				else
				{
					// c will be a single byte.
					uchar16_t vh = static_cast<uchar16_t>(c);

					// If the previous position was a surrogate pair, remove the extra byte.
					if (UTF16_IS_SURROGATE_HI(a[pos]))
						ref2->erase_raw(static_cast<u32>(pos) + 1);

					ref2->replace_raw(vh, static_cast<u32>(pos));
				}
			}

			const ustring16<TAlloc>* ref;
			u32 pos;
	};
	typedef typename ustring16<TAlloc>::_ustring16_iterator_access access;


	//! Iterator to iterate through a UTF-16 string.
#ifndef USTRING_NO_STL
	class _ustring16_const_iterator : public std::iterator<
		std::bidirectional_iterator_tag,	// iterator_category
		access,								// value_type
		ptrdiff_t,							// difference_type
		const access,						// pointer
		const access						// reference
	>
#else
	class _ustring16_const_iterator
#endif
	{
		public:
			typedef _ustring16_const_iterator _Iter;
			typedef std::iterator<std::bidirectional_iterator_tag, access, ptrdiff_t, const access, const access> _Base;
			typedef const access const_pointer;
			typedef const access const_reference;

#ifndef USTRING_NO_STL
			typedef typename _Base::value_type value_type;
			typedef typename _Base::difference_type difference_type;
			typedef typename _Base::difference_type distance_type;
			typedef typename _Base::pointer pointer;
			typedef const_reference reference;
#else
			typedef access value_type;
			typedef u32 difference_type;
			typedef u32 distance_type;
			typedef const_pointer pointer;
			typedef const_reference reference;
#endif

			//! Constructors.
			_ustring16_const_iterator(const _Iter& i) : ref(i.ref), pos(i.pos) {}
			_ustring16_const_iterator(const ustring16<TAlloc>& s) : ref(&s), pos(0) {}
			_ustring16_const_iterator(const ustring16<TAlloc>& s, const u32 p) : ref(&s), pos(0)
			{
				if (ref->size_raw() == 0 || p == 0)
					return;

				// Go to the appropriate position.
				u32 i = p;
				u32 sr = ref->size_raw();
				const uchar16_t* a = ref->c_str();
				while (i != 0 && pos < sr)
				{
					if (UTF16_IS_SURROGATE_HI(a[pos]))
						pos += 2;
					else ++pos;
					--i;
				}
			}

			//! Test for equalness.
			bool operator==(const _Iter& iter) const
			{
				if (ref == iter.ref && pos == iter.pos)
					return true;
				return false;
			}

			//! Test for unequalness.
			bool operator!=(const _Iter& iter) const
			{
				if (ref != iter.ref || pos != iter.pos)
					return true;
				return false;
			}

			//! Switch to the next full character in the string.
			_Iter& operator++()
			{	// ++iterator
				if (pos == ref->size_raw()) return *this;
				const uchar16_t* a = ref->c_str();
				if (UTF16_IS_SURROGATE_HI(a[pos]))
					pos += 2;			// TODO: check for valid low surrogate?
				else ++pos;
				if (pos > ref->size_raw()) pos = ref->size_raw();
				return *this;
			}

			//! Switch to the next full character in the string, returning the previous position.
			_Iter operator++(int)
			{	// iterator++
				_Iter _tmp(*this);
				++*this;
				return _tmp;
			}

			//! Switch to the previous full character in the string.
			_Iter& operator--()
			{	// --iterator
				if (pos == 0) return *this;
				const uchar16_t* a = ref->c_str();
				--pos;
				if (UTF16_IS_SURROGATE_LO(a[pos]) && pos != 0)	// low surrogate, go back one more.
					--pos;
				return *this;
			}

			//! Switch to the previous full character in the string, returning the previous position.
			_Iter operator--(int)
			{	// iterator--
				_Iter _tmp(*this);
				--*this;
				return _tmp;
			}

			//! Advance a specified number of full characters in the string.
			//! \return Myself.
			_Iter& operator+=(const difference_type v)
			{
				if (v == 0) return *this;
				if (v < 0) return operator-=(v * -1);

				if (pos >= ref->size_raw())
					return *this;

				// Go to the appropriate position.
				// TODO: Don't force u32 on an x64 OS.  Make it agnostic.
				u32 i = (u32)v;
				u32 sr = ref->size_raw();
				const uchar16_t* a = ref->c_str();
				while (i != 0 && pos < sr)
				{
					if (UTF16_IS_SURROGATE_HI(a[pos]))
						pos += 2;
					else ++pos;
					--i;
				}
				if (pos > sr)
					pos = sr;

				return *this;
			}

			//! Go back a specified number of full characters in the string.
			//! \return Myself.
			_Iter& operator-=(const difference_type v)
			{
				if (v == 0) return *this;
				if (v > 0) return operator+=(v * -1);

				if (pos == 0)
					return *this;

				// Go to the appropriate position.
				// TODO: Don't force u32 on an x64 OS.  Make it agnostic.
				u32 i = (u32)v;
				const uchar16_t* a = ref->c_str();
				while (i != 0 && pos != 0)
				{
					--pos;
					if (UTF16_IS_SURROGATE_LO(a[pos]) != 0 && pos != 0)
						--pos;
					--i;
				}

				return *this;
			}

			//! Return a new iterator that is a variable number of full characters forward from the current position.
			_Iter operator+(const difference_type v) const
			{
				_Iter ret(*this);
				ret += v;
				return ret;
			}

			//! Return a new iterator that is a variable number of full characters backward from the current position.
			_Iter operator-(const difference_type v) const
			{
				_Iter ret(*this);
				ret -= v;
				return ret;
			}

			//! Returns the distance between two iterators.
			difference_type operator-(const _Iter& iter) const
			{
				// Make sure we reference the same object!
				if (ref != iter.ref)
					return difference_type();

				_Iter i = iter;
				difference_type ret;

				// Walk up.
				if (pos > i.pos)
				{
					while (pos > i.pos)
					{
						++i;
						++ret;
					}
					return ret;
				}

				// Walk down.
				while (pos < i.pos)
				{
					--i;
					--ret;
				}
				return ret;
			}

			//! Accesses the full character at the iterator's position.
			const_reference operator*() const
			{
				if (pos >= ref->size_raw())
				{
					const uchar16_t* a = ref->c_str();
					u32 p = ref->size_raw();
					if (UTF16_IS_SURROGATE_LO(a[p]))
						--p;
					reference ret(ref, p);
					return ret;
				}
				const_reference ret(ref, pos);
				return ret;
			}

			//! Accesses the full character at the iterator's position.
			reference operator*()
			{
				if (pos >= ref->size_raw())
				{
					const uchar16_t* a = ref->c_str();
					u32 p = ref->size_raw();
					if (UTF16_IS_SURROGATE_LO(a[p]))
						--p;
					reference ret(ref, p);
					return ret;
				}
				reference ret(ref, pos);
				return ret;
			}

			//! Accesses the full character at the iterator's position.
			const_pointer operator->() const
			{
				return operator*();
			}

			//! Accesses the full character at the iterator's position.
			pointer operator->()
			{
				return operator*();
			}

			//! Is the iterator at the start of the string?
			bool atStart() const
			{
				return pos == 0;
			}

			//! Is the iterator at the end of the string?
			bool atEnd() const
			{
				const uchar16_t* a = ref->c_str();
				if (UTF16_IS_SURROGATE(a[pos]))
					return (pos + 1) >= ref->size_raw();
				else return pos >= ref->size_raw();
			}

			//! Moves the iterator to the start of the string.
			void toStart()
			{
				pos = 0;
			}

			//! Moves the iterator to the end of the string.
			void toEnd()
			{
				pos = ref->size_raw();
			}

			//! Returns the iterator's position.
			//! \return The iterator's position.
			u32 getPos() const
			{
				return pos;
			}

		protected:
			const ustring16<TAlloc>* ref;
			u32 pos;
	};

	//! Iterator to iterate through a UTF-16 string.
	class _ustring16_iterator : public _ustring16_const_iterator
	{
		public:
			typedef _ustring16_iterator _Iter;
			typedef _ustring16_const_iterator _Base;
			typedef typename _Base::const_pointer const_pointer;
			typedef typename _Base::const_reference const_reference;


			typedef typename _Base::value_type value_type;
			typedef typename _Base::difference_type difference_type;
			typedef typename _Base::distance_type distance_type;
			typedef access pointer;
			typedef access reference;

			using _Base::pos;
			using _Base::ref;

			//! Constructors.
			_ustring16_iterator(const _Iter& i) : _ustring16_const_iterator(i) {}
			_ustring16_iterator(const ustring16<TAlloc>& s) : _ustring16_const_iterator(s) {}
			_ustring16_iterator(const ustring16<TAlloc>& s, const u32 p) : _ustring16_const_iterator(s, p) {}

			//! Accesses the full character at the iterator's position.
			reference operator*() const
			{
				if (pos >= ref->size_raw())
				{
					const uchar16_t* a = ref->c_str();
					u32 p = ref->size_raw();
					if (UTF16_IS_SURROGATE_LO(a[p]))
						--p;
					reference ret(ref, p);
					return ret;
				}
				reference ret(ref, pos);
				return ret;
			}

			//! Accesses the full character at the iterator's position.
			reference operator*()
			{
				if (pos >= ref->size_raw())
				{
					const uchar16_t* a = ref->c_str();
					u32 p = ref->size_raw();
					if (UTF16_IS_SURROGATE_LO(a[p]))
						--p;
					reference ret(ref, p);
					return ret;
				}
				reference ret(ref, pos);
				return ret;
			}

			//! Accesses the full character at the iterator's position.
			pointer operator->() const
			{
				return operator*();
			}

			//! Accesses the full character at the iterator's position.
			pointer operator->()
			{
				return operator*();
			}
	};

	typedef typename ustring16<TAlloc>::_ustring16_iterator iterator;
	typedef typename ustring16<TAlloc>::_ustring16_const_iterator const_iterator;

	///----------------------///
	/// end iterator classes ///
	///----------------------///

	//! Default constructor
	ustring16()
	: array(0), allocated(1), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif
		array = allocator.allocate(1); // new u16[1];
		array[0] = 0x0;
	}


	//! Constructor
	ustring16(const ustring16<TAlloc>& other)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif
		*this = other;
	}


	//! Constructor from other string types
	template <class B, class A>
	ustring16(const string<B, A>& other)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif
		*this = other;
	}


#ifndef USTRING_NO_STL
	//! Constructor from std::string
	template <class B, class A, typename Alloc>
	ustring16(const std::basic_string<B, A, Alloc>& other)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif
		*this = other.c_str();
	}


	//! Constructor from iterator.
	template <typename Itr>
	ustring16(Itr first, Itr last)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif
		reserve(std::distance(first, last));
		array[used] = 0;

		for (; first != last; ++first)
			append((uchar32_t)*first);
	}
#endif


#ifndef USTRING_CPP0X_NEWLITERALS
	//! Constructor for copying a character string from a pointer.
	ustring16(const char* const c)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		loadDataStream(c, strlen(c));
		//append((uchar8_t*)c);
	}


	//! Constructor for copying a character string from a pointer with a given length.
	ustring16(const char* const c, u32 length)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		loadDataStream(c, length);
	}
#endif


	//! Constructor for copying a UTF-8 string from a pointer.
	ustring16(const uchar8_t* const c)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append(c);
	}


	//! Constructor for copying a UTF-8 string from a single char.
	ustring16(const char c)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append((uchar32_t)c);
	}


	//! Constructor for copying a UTF-8 string from a pointer with a given length.
	ustring16(const uchar8_t* const c, u32 length)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append(c, length);
	}


	//! Constructor for copying a UTF-16 string from a pointer.
	ustring16(const uchar16_t* const c)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append(c);
	}


	//! Constructor for copying a UTF-16 string from a pointer with a given length
	ustring16(const uchar16_t* const c, u32 length)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append(c, length);
	}


	//! Constructor for copying a UTF-32 string from a pointer.
	ustring16(const uchar32_t* const c)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append(c);
	}


	//! Constructor for copying a UTF-32 from a pointer with a given length.
	ustring16(const uchar32_t* const c, u32 length)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		append(c, length);
	}


	//! Constructor for copying a wchar_t string from a pointer.
	ustring16(const wchar_t* const c)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		if (sizeof(wchar_t) == 4)
			append(reinterpret_cast<const uchar32_t* const>(c));
		else if (sizeof(wchar_t) == 2)
			append(reinterpret_cast<const uchar16_t* const>(c));
		else if (sizeof(wchar_t) == 1)
			append(reinterpret_cast<const uchar8_t* const>(c));
	}


	//! Constructor for copying a wchar_t string from a pointer with a given length.
	ustring16(const wchar_t* const c, u32 length)
	: array(0), allocated(0), used(0)
	{
#if __BYTE_ORDER == __BIG_ENDIAN
		encoding = unicode::EUTFE_UTF16_BE;
#else
		encoding = unicode::EUTFE_UTF16_LE;
#endif

		if (sizeof(wchar_t) == 4)
			append(reinterpret_cast<const uchar32_t* const>(c), length);
		else if (sizeof(wchar_t) == 2)
			append(reinterpret_cast<const uchar16_t* const>(c), length);
		else if (sizeof(wchar_t) == 1)
			append(reinterpret_cast<const uchar8_t* const>(c), length);
	}


#ifdef USTRING_CPP0X
	//! Constructor for moving a ustring16
	ustring16(ustring16<TAlloc>&& other)
	: array(other.array), encoding(other.encoding), allocated(other.allocated), used(other.used)
	{
		//std::cout << "MOVE constructor" << std::endl;
		other.array = 0;
		other.allocated = 0;
		other.used = 0;
	}
#endif


	//! Destructor
	~ustring16()
	{
		allocator.deallocate(array); // delete [] array;
	}


	//! Assignment operator
	ustring16& operator=(const ustring16<TAlloc>& other)
	{
		if (this == &other)
			return *this;

		used = other.size_raw();
		if (used >= allocated)
		{
			allocator.deallocate(array); // delete [] array;
			allocated = used + 1;
			array = allocator.allocate(used + 1); //new u16[used];
		}

		const uchar16_t* p = other.c_str();
		for (u32 i=0; i<=used; ++i, ++p)
			array[i] = *p;

		array[used] = 0;

		// Validate our new UTF-16 string.
		validate();

		return *this;
	}


#ifdef USTRING_CPP0X
	//! Move assignment operator
	ustring16& operator=(ustring16<TAlloc>&& other)
	{
		if (this != &other)
		{
			//std::cout << "MOVE operator=" << std::endl;
			allocator.deallocate(array);

			array = other.array;
			allocated = other.allocated;
			encoding = other.encoding;
			used = other.used;
			other.array = 0;
			other.used = 0;
		}
		return *this;
	}
#endif


	//! Assignment operator for other string types
	template <class B, class A>
	ustring16<TAlloc>& operator=(const string<B, A>& other)
	{
		*this = other.c_str();
		return *this;
	}


	//! Assignment operator for UTF-8 strings
	ustring16<TAlloc>& operator=(const uchar8_t* const c)
	{
		if (!array)
		{
			array = allocator.allocate(1); //new u16[1];
			allocated = 1;
		}
		used = 0;
		array[used] = 0x0;
		if (!c) return *this;

		//! Append our string now.
		append(c);
		return *this;
	}


	//! Assignment operator for UTF-16 strings
	ustring16<TAlloc>& operator=(const uchar16_t* const c)
	{
		if (!array)
		{
			array = allocator.allocate(1); //new u16[1];
			allocated = 1;
		}
		used = 0;
		array[used] = 0x0;
		if (!c) return *this;

		//! Append our string now.
		append(c);
		return *this;
	}


	//! Assignment operator for UTF-32 strings
	ustring16<TAlloc>& operator=(const uchar32_t* const c)
	{
		if (!array)
		{
			array = allocator.allocate(1); //new u16[1];
			allocated = 1;
		}
		used = 0;
		array[used] = 0x0;
		if (!c) return *this;

		//! Append our string now.
		append(c);
		return *this;
	}


	//! Assignment operator for wchar_t strings.
	/** Note that this assumes that a correct unicode string is stored in the wchar_t string.
		Since wchar_t changes depending on its platform, it could either be a UTF-8, -16, or -32 string.
		This function assumes you are storing the correct unicode encoding inside the wchar_t string. **/
	ustring16<TAlloc>& operator=(const wchar_t* const c)
	{
		if (sizeof(wchar_t) == 4)
			*this = reinterpret_cast<const uchar32_t* const>(c);
		else if (sizeof(wchar_t) == 2)
			*this = reinterpret_cast<const uchar16_t* const>(c);
		else if (sizeof(wchar_t) == 1)
			*this = reinterpret_cast<const uchar8_t* const>(c);

		return *this;
	}


	//! Assignment operator for other strings.
	/** Note that this assumes that a correct unicode string is stored in the string. **/
	template <class B>
	ustring16<TAlloc>& operator=(const B* const c)
	{
		if (sizeof(B) == 4)
			*this = reinterpret_cast<const uchar32_t* const>(c);
		else if (sizeof(B) == 2)
			*this = reinterpret_cast<const uchar16_t* const>(c);
		else if (sizeof(B) == 1)
			*this = reinterpret_cast<const uchar8_t* const>(c);

		return *this;
	}


	//! Direct access operator
	access operator [](const u32 index)
	{
		_IRR_DEBUG_BREAK_IF(index>=size()) // bad index
		iterator iter(*this, index);
		return iter.operator*();
	}


	//! Direct access operator
	const access operator [](const u32 index) const
	{
		_IRR_DEBUG_BREAK_IF(index>=size()) // bad index
		const_iterator iter(*this, index);
		return iter.operator*();
	}


	//! Equality operator
	bool operator ==(const uchar16_t* const str) const
	{
		if (!str)
			return false;

		u32 i;
		for(i=0; array[i] && str[i]; ++i)
			if (array[i] != str[i])
				return false;

		return !array[i] && !str[i];
	}


	//! Equality operator
	bool operator ==(const ustring16<TAlloc>& other) const
	{
		for(u32 i=0; array[i] && other.array[i]; ++i)
			if (array[i] != other.array[i])
				return false;

		return used == other.used;
	}


	//! Is smaller comparator
	bool operator <(const ustring16<TAlloc>& other) const
	{
		for(u32 i=0; array[i] && other.array[i]; ++i)
		{
			s32 diff = array[i] - other.array[i];
			if ( diff )
				return diff < 0;
		}

		return used < other.used;
	}


	//! Inequality operator
	bool operator !=(const uchar16_t* const str) const
	{
		return !(*this == str);
	}


	//! Inequality operator
	bool operator !=(const ustring16<TAlloc>& other) const
	{
		return !(*this == other);
	}


	//! Returns the length of a ustring16 in full characters.
	//! \return Length of a ustring16 in full characters.
	u32 size() const
	{
		const_iterator i(*this, 0);
		u32 pos = 0;
		while (!i.atEnd())
		{
			++i;
			++pos;
		}
		return pos;
	}


	//! Informs if the ustring is empty or not.
	//! \return True if the ustring is empty, false if not.
	bool empty() const
	{
		return (size_raw() == 0);
	}


	//! Returns a pointer to the raw UTF-16 string data.
	//! \return pointer to C-style NUL terminated array of UTF-16 code points.
	const uchar16_t* c_str() const
	{
		return array;
	}


	//! Compares the first n characters of this string with another.
	//! \param other Other string to compare to.
	//! \param n Number of characters to compare.
	//! \return True if the n first characters of both strings are equal.
	bool equalsn(const ustring16<TAlloc>& other, u32 n) const
	{
		u32 i;
		const uchar16_t* oa = other.c_str();
		for(i=0; array[i] && oa[i] && i < n; ++i)
			if (array[i] != oa[i])
				return false;

		// if one (or both) of the strings was smaller then they
		// are only equal if they have the same length
		return (i == n) || (used == other.used);
	}


	//! Compares the first n characters of this string with another.
	//! \param str Other string to compare to.
	//! \param n Number of characters to compare.
	//! \return True if the n first characters of both strings are equal.
	bool equalsn(const uchar16_t* const str, u32 n) const
	{
		if (!str)
			return false;
		u32 i;
		for(i=0; array[i] && str[i] && i < n; ++i)
			if (array[i] != str[i])
				return false;

		// if one (or both) of the strings was smaller then they
		// are only equal if they have the same length
		return (i == n) || (array[i] == 0 && str[i] == 0);
	}


	//! Appends a character to this ustring16
	//! \param character The character to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& append(uchar32_t character)
	{
		if (used + 2 >= allocated)
			reallocate(used + 2);

		if (character > 0xFFFF)
		{
			used += 2;

			// character will be multibyte, so split it up into a surrogate pair.
			uchar16_t x = static_cast<uchar16_t>(character);
			uchar16_t vh = UTF16_HI_SURROGATE | ((((character >> 16) & ((1 << 5) - 1)) - 1) << 6) | (x >> 10);
			uchar16_t vl = UTF16_LO_SURROGATE | (x & ((1 << 10) - 1));
			array[used-2] = vh;
			array[used-1] = vl;
		}
		else
		{
			++used;
			array[used-1] = character;
		}
		array[used] = 0;

		return *this;
	}


	//! Appends a UTF-8 string to this ustring16
	//! \param other The UTF-8 string to append.
	//! \param length The length of the string to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& append(const uchar8_t* const other, u32 length=0xffffffff)
	{
		if (!other)
			return *this;

		// Determine if the string is long enough for a BOM.
		u32 len = 0;
		const uchar8_t* p = other;
		do
		{
			++len;
		} while (*p++ && len < unicode::BOM_ENCODE_UTF8_LEN);

		// Check for BOM.
		unicode::EUTF_ENCODE c_bom = unicode::EUTFE_NONE;
		if (len == unicode::BOM_ENCODE_UTF8_LEN)
		{
			if (memcmp(other, unicode::BOM_ENCODE_UTF8, unicode::BOM_ENCODE_UTF8_LEN) == 0)
				c_bom = unicode::EUTFE_UTF8;
		}

		// If a BOM was found, don't include it in the string.
		const uchar8_t* c2 = other;
		if (c_bom != unicode::EUTFE_NONE)
		{
			c2 = other + unicode::BOM_UTF8_LEN;
			length -= unicode::BOM_UTF8_LEN;
		}

		// Calculate the size of the string to read in.
		len = 0;
		p = c2;
		do
		{
			++len;
		} while(*p++ && len < length);
		if (len > length)
			len = length;

		// If we need to grow the array, do it now.
		if (used + len >= allocated)
			reallocate(used + (len * 2));
		u32 start = used;

		// Convert UTF-8 to UTF-16.
		u32 pos = start;
		for (u32 l = 0; l<len;)
		{
			++used;
			if (((c2[l] >> 6) & 0x03) == 0x02)
			{	// Invalid continuation byte.
				array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
				++l;
			}
			else if (c2[l] == 0xC0 || c2[l] == 0xC1)
			{	// Invalid byte - overlong encoding.
				array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
				++l;
			}
			else if ((c2[l] & 0xF8) == 0xF0)
			{	// 4 bytes UTF-8, 2 bytes UTF-16.
				// Check for a full string.
				if ((l + 3) >= len)
				{
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
					l += 3;
					break;
				}

				// Validate.
				bool valid = true;
				u8 l2 = 0;
				if (valid && (((c2[l+1] >> 6) & 0x03) == 0x02)) ++l2; else valid = false;
				if (valid && (((c2[l+2] >> 6) & 0x03) == 0x02)) ++l2; else valid = false;
				if (valid && (((c2[l+3] >> 6) & 0x03) == 0x02)) ++l2; else valid = false;
				if (!valid)
				{
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
					l += l2;
					continue;
				}

				// Decode.
				uchar8_t b1 = ((c2[l] & 0x7) << 2) | ((c2[l+1] >> 4) & 0x3);
				uchar8_t b2 = ((c2[l+1] & 0xF) << 4) | ((c2[l+2] >> 2) & 0xF);
				uchar8_t b3 = ((c2[l+2] & 0x3) << 6) | (c2[l+3] & 0x3F);
				uchar32_t v = b3 | ((uchar32_t)b2 << 8) | ((uchar32_t)b1 << 16);

				// Split v up into a surrogate pair.
				uchar16_t x = static_cast<uchar16_t>(v);
				uchar16_t vh = UTF16_HI_SURROGATE | ((((v >> 16) & ((1 << 5) - 1)) - 1) << 6) | (x >> 10);
				uchar16_t vl = UTF16_LO_SURROGATE | (x & ((1 << 10) - 1));

				array[pos++] = vh;
				array[pos++] = vl;
				l += 4;
				++used;		// Using two shorts this time, so increase used by 1.
			}
			else if ((c2[l] & 0xF0) == 0xE0)
			{	// 3 bytes UTF-8, 1 byte UTF-16.
				// Check for a full string.
				if ((l + 2) >= len)
				{
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
					l += 2;
					break;
				}

				// Validate.
				bool valid = true;
				u8 l2 = 0;
				if (valid && (((c2[l+1] >> 6) & 0x03) == 0x02)) ++l2; else valid = false;
				if (valid && (((c2[l+2] >> 6) & 0x03) == 0x02)) ++l2; else valid = false;
				if (!valid)
				{
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
					l += l2;
					continue;
				}

				// Decode.
				uchar8_t b1 = ((c2[l] & 0xF) << 4) | ((c2[l+1] >> 2) & 0xF);
				uchar8_t b2 = ((c2[l+1] & 0x3) << 6) | (c2[l+2] & 0x3F);
				uchar16_t ch = b2 | ((uchar16_t)b1 << 8);
				array[pos++] = ch;
				l += 3;
			}
			else if ((c2[l] & 0xE0) == 0xC0)
			{	// 2 bytes UTF-8, 1 byte UTF-16.
				// Check for a full string.
				if ((l + 1) >= len)
				{
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
					l += 1;
					break;
				}

				// Validate.
				if (((c2[l+1] >> 6) & 0x03) != 0x02)
				{
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
					++l;
					continue;
				}

				// Decode.
				uchar8_t b1 = (c2[l] >> 2) & 0x7;
				uchar8_t b2 = ((c2[l] & 0x3) << 6) | (c2[l+1] & 0x3F);
				uchar16_t ch = b2 | ((uchar16_t)b1 << 8);
				array[pos++] = ch;
				l += 2;
			}
			else
			{	// 1 byte UTF-8, 1 byte UTF-16.
				// Validate.
				if (c2[l] > 0x7F)
				{	// Values above 0xF4 are restricted and aren't used.  By now, anything above 0x7F is invalid.
					array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
				}
				else array[pos++] = static_cast<uchar16_t>(c2[l]);
				++l;
			}
		}
		array[used] = 0;

		// Validate our new UTF-16 string.
		validate();

		return *this;
	}


	//! Appends a UTF-16 string to this ustring16
	//! \param other The UTF-16 string to append.
	//! \param length The length of the string to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& append(const uchar16_t* const other, u32 length=0xffffffff)
	{
		if (!other)
			return *this;

		// Determine if the string is long enough for a BOM.
		u32 len = 0;
		const uchar16_t* p = other;
		do
		{
			++len;
		} while (*p++ && len < unicode::BOM_ENCODE_UTF16_LEN);

		// Check for the BOM to determine the string's endianness.
		unicode::EUTF_ENDIAN c_end = unicode::EUTFEE_NATIVE;
		if (memcmp(other, unicode::BOM_ENCODE_UTF16_LE, unicode::BOM_ENCODE_UTF16_LEN) == 0)
			c_end = unicode::EUTFEE_LITTLE;
		else if (memcmp(other, unicode::BOM_ENCODE_UTF16_BE, unicode::BOM_ENCODE_UTF16_LEN) == 0)
			c_end = unicode::EUTFEE_BIG;

		// If a BOM was found, don't include it in the string.
		const uchar16_t* c2 = other;
		if (c_end != unicode::EUTFEE_NATIVE)
		{
			c2 = other + unicode::BOM_UTF16_LEN;
			length -= unicode::BOM_UTF16_LEN;
		}

		// Calculate the size of the string to read in.
		len = 0;
		p = c2;
		do
		{
			++len;
		} while(*p++ && len < length);
		if (len > length)
			len = length;

		// If we need to grow the size of the array, do it now.
		if (used + len >= allocated)
			reallocate(used + (len * 2));
		u32 start = used;
		used += len;

		// Copy the string now.
		unicode::EUTF_ENDIAN m_end = getEndianness();
		for (u32 l = start; l < start + len; ++l)
		{
			array[l] = (uchar16_t)c2[l];
			if (c_end != unicode::EUTFEE_NATIVE && c_end != m_end)
				array[l] = unicode::swapEndian16(array[l]);
		}

		array[used] = 0;

		// Validate our new UTF-16 string.
		validate();
		return *this;
	}


	//! Appends a UTF-32 string to this ustring16
	//! \param other The UTF-32 string to append.
	//! \param length The length of the string to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& append(const uchar32_t* const other, u32 length=0xffffffff)
	{
		if (!other)
			return *this;

		// Check for the BOM to determine the string's endianness.
		unicode::EUTF_ENDIAN c_end = unicode::EUTFEE_NATIVE;
		if (memcmp(other, unicode::BOM_ENCODE_UTF32_LE, unicode::BOM_ENCODE_UTF32_LEN) == 0)
			c_end = unicode::EUTFEE_LITTLE;
		else if (memcmp(other, unicode::BOM_ENCODE_UTF32_BE, unicode::BOM_ENCODE_UTF32_LEN) == 0)
			c_end = unicode::EUTFEE_BIG;

		// If a BOM was found, don't include it in the string.
		const uchar32_t* c2 = other;
		if (c_end != unicode::EUTFEE_NATIVE)
		{
			c2 = other + unicode::BOM_UTF32_LEN;
			length -= unicode::BOM_UTF32_LEN;
		}

		// Calculate the size of the string to read in.
		u32 len = 0;
		const uchar32_t* p = c2;
		do
		{
			++len;
		} while(*p++ && len < length);
		if (len > length)
			len = length;

		// If we need to grow the size of the array, do it now.
		// In case all of the UTF-32 string is split into surrogate pairs, do len * 2.
		if (used + (len * 2) >= allocated)
			reallocate(used + ((len * 2) * 2));
		u32 start = used;

		// Convert UTF-32 to UTF-16.
		unicode::EUTF_ENDIAN m_end = getEndianness();
		u32 pos = start;
		for (u32 l = 0; l<len; ++l)
		{
			++used;

			uchar32_t ch = c2[l];
			if (c_end != unicode::EUTFEE_NATIVE && c_end != m_end)
				ch = unicode::swapEndian32(ch);

			if (ch > 0xFFFF)
			{
				// Split ch up into a surrogate pair as it is over 16 bits long.
				uchar16_t x = static_cast<uchar16_t>(ch);
				uchar16_t vh = UTF16_HI_SURROGATE | ((((ch >> 16) & ((1 << 5) - 1)) - 1) << 6) | (x >> 10);
				uchar16_t vl = UTF16_LO_SURROGATE | (x & ((1 << 10) - 1));
				array[pos++] = vh;
				array[pos++] = vl;
				++used;		// Using two shorts, so increased used again.
			}
			else if (ch >= 0xD800 && ch <= 0xDFFF)
			{
				// Between possible UTF-16 surrogates (invalid!)
				array[pos++] = unicode::UTF_REPLACEMENT_CHARACTER;
			}
			else array[pos++] = static_cast<uchar16_t>(ch);
		}
		array[used] = 0;

		// Validate our new UTF-16 string.
		validate();

		return *this;
	}


	//! Appends a ustring16 to this ustring16
	//! \param other The string to append to this one.
	//! \return A reference to our current string.
	ustring16<TAlloc>& append(const ustring16<TAlloc>& other)
	{
		const uchar16_t* oa = other.c_str();

		u32 len = other.size_raw();

		if (used + len >= allocated)
			reallocate(used + len);

		for (u32 l=0; l<len; ++l)
			array[used+l] = oa[l];

		used += len;
		array[used] = 0;

		return *this;
	}


	//! Appends a certain amount of characters of a ustring16 to this ustring16.
	//! \param other The string to append to this one.
	//! \param length How many characters of the other string to add to this one.
	//! \return A reference to our current string.
	ustring16<TAlloc>& append(const ustring16<TAlloc>& other, u32 length)
	{
		if (other.size() == 0)
			return *this;

		if (other.size() < length)
		{
			append(other);
			return *this;
		}

		if (used + length * 2 >= allocated)
			reallocate(used + length * 2);

		const_iterator iter(other, 0);
		u32 l = length;
		while (!iter.atEnd() && l)
		{
			uchar32_t c = *iter;
			append(c);
			++iter;
			--l;
		}

		return *this;
	}


	//! Reserves some memory.
	//! \param count The amount of characters to reserve.
	void reserve(u32 count)
	{
		if (count < allocated)
			return;

		reallocate(count);
	}


	//! Finds first occurrence of character.
	//! \param c The character to search for.
	//! \return Position where the character has been found, or -1 if not found.
	s32 findFirst(uchar32_t c) const
	{
		const_iterator i(*this, 0);

		s32 pos = 0;
		while (!i.atEnd())
		{
			uchar32_t t = *i;
			if (c == t)
				return pos;
			++pos;
			++i;
		}

		return -1;
	}

	//! Finds first occurrence of a character of a list.
	//! \param c A list of characters to find. For example if the method should find the first occurrence of 'a' or 'b', this parameter should be "ab".
	//! \param count The amount of characters in the list. Usually, this should be strlen(c).
	//! \return Position where one of the characters has been found, or -1 if not found.
	s32 findFirstChar(const uchar32_t* const c, u32 count=1) const
	{
		if (!c || !count)
			return -1;

		const_iterator i(*this, 0);

		s32 pos = 0;
		while (!i.atEnd())
		{
			uchar32_t t = *i;
			for (u32 j=0; j<count; ++j)
				if (t == c[j])
					return pos;
			++pos;
			++i;
		}

		return -1;
	}


	//! Finds first position of a character not in a given list.
	//! \param c A list of characters to NOT find. For example if the method should find the first occurrence of a character not 'a' or 'b', this parameter should be "ab".
	//! \param count The amount of characters in the list. Usually, this should be strlen(c).
	//! \return Position where the character has been found, or -1 if not found.
	s32 findFirstCharNotInList(const uchar32_t* const c, u32 count=1) const
	{
		if (!c || !count)
			return -1;

		const_iterator i(*this, 0);

		s32 pos = 0;
		while (!i.atEnd())
		{
			uchar32_t t = *i;
			u32 j;
			for (j=0; j<count; ++j)
				if (t == c[j])
					break;

			if (j==count)
				return pos;
			++pos;
			++i;
		}

		return -1;
	}

	//! Finds last position of a character not in a given list.
	//! \param c A list of characters to NOT find. For example if the method should find the first occurrence of a character not 'a' or 'b', this parameter should be "ab".
	//! \param count The amount of characters in the list. Usually, this should be strlen(c).
	//! \return Position where the character has been found, or -1 if not found.
	s32 findLastCharNotInList(const uchar32_t* const c, u32 count=1) const
	{
		if (!c || !count)
			return -1;

		const_iterator i(end());
		--i;

		s32 pos = size() - 1;
		while (!i.atStart())
		{
			uchar32_t t = *i;
			u32 j;
			for (j=0; j<count; ++j)
				if (t == c[j])
					break;

			if (j==count)
				return pos;
			--pos;
			--i;
		}

		return -1;
	}

	//! Finds next occurrence of character.
	//! \param c The character to search for.
	//! \param startPos The position in the string to start searching.
	//! \return Position where the character has been found, or -1 if not found.
	s32 findNext(uchar32_t c, u32 startPos) const
	{
		const_iterator i(*this, startPos);

		s32 pos = startPos;
		while (!i.atEnd())
		{
			uchar32_t t = *i;
			if (t == c)
				return pos;
			++pos;
			++i;
		}

		return -1;
	}


	//! Finds last occurrence of character.
	//! \param c The character to search for.
	//! \param start The start position of the reverse search ( default = -1, on end ).
	//! \return Position where the character has been found, or -1 if not found.
	s32 findLast(uchar32_t c, s32 start = -1) const
	{
		u32 s = size();
		start = core::clamp ( start < 0 ? (s32)s : start, 0, (s32)s ) - 1;

		const_iterator i(*this, start);
		u32 pos = start;
		while (!i.atStart())
		{
			uchar32_t t = *i;
			if (t == c)
				return pos;
			--pos;
			--i;
		}

		return -1;
	}

	//! Finds last occurrence of a character in a list.
	//! \param c A list of strings to find. For example if the method should find the last occurrence of 'a' or 'b', this parameter should be "ab".
	//! \param count The amount of characters in the list. Usually, this should be strlen(c).
	//! \return Position where one of the characters has been found, or -1 if not found.
	s32 findLastChar(const uchar32_t* const c, u32 count=1) const
	{
		if (!c || !count)
			return -1;

		const_iterator i(end());
		--i;

		s32 pos = size();
		while (!i.atStart())
		{
			uchar32_t t = *i;
			for (u32 j=0; j<count; ++j)
				if (t == c[j])
					return pos;
			--pos;
			--i;
		}

		return -1;
	}


	//! Finds another ustring16 in this ustring16.
	//! \param str The string to find.
	//! \param start The start position of the search.
	//! \return Positions where the ustring16 has been found, or -1 if not found.
	s32 find(const ustring16<TAlloc>& str, const u32 start = 0) const
	{
		u32 my_size = size();
		u32 their_size = str.size();

		if (their_size == 0 || my_size - start < their_size)
			return -1;

		const_iterator i(*this, start);

		s32 pos = start;
		while (!i.atEnd())
		{
			const_iterator i2(i);
			const_iterator j(str, 0);
			uchar32_t t1 = (uchar32_t)*i2;
			uchar32_t t2 = (uchar32_t)*j;
			while (t1 == t2)
			{
				++i2;
				++j;
				if (j.atEnd())
					return pos;
				t1 = (uchar32_t)*i2;
				t2 = (uchar32_t)*j;
			}
			++i;
			++pos;
		}

		return -1;
	}


	//! Finds another ustring16 in this ustring16.
	//! \param str The string to find.
	//! \param start The start position of the search.
	//! \return Positions where the string has been found, or -1 if not found.
	s32 find_raw(const ustring16<TAlloc>& str, const u32 start = 0) const
	{
		const uchar16_t* data = str.c_str();
		if (data && *data)
		{
			u32 len = 0;

			while (data[len])
				++len;

			if (len > used)
				return -1;

			for (u32 i=start; i<=used-len; ++i)
			{
				u32 j=0;

				while(data[j] && array[i+j] == data[j])
					++j;

				if (!data[j])
					return i;
			}
		}

		return -1;
	}


	//! Returns a substring.
	//! \param begin: Start of substring.
	//! \param length: Length of substring.
	//! \return A reference to our current string.
	ustring16<TAlloc> subString(u32 begin, s32 length) const
	{
		u32 len = size();
		// if start after ustring16
		// or no proper substring length
		if ((length <= 0) || (begin>=len))
			return ustring16<TAlloc>("");
		// clamp length to maximal value
		if ((length+begin) > len)
			length = len-begin;

		ustring16<TAlloc> o;
		o.reserve((length+1) * 2);

		const_iterator i(*this, begin);
		while (!i.atEnd() && length)
		{
			o.append(*i);
			++i;
			--length;
		}

		return o;
	}


	//! Appends a character to this ustring16.
	//! \param c Character to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (char c)
	{
		append((uchar32_t)c);
		return *this;
	}


	//! Appends a character to this ustring16.
	//! \param c Character to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (uchar32_t c)
	{
		append(c);
		return *this;
	}


	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (short c)
	{
		append(core::stringc(c));
		return *this;
	}


	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (unsigned short c)
	{
		append(core::stringc(c));
		return *this;
	}


#ifdef USTRING_CPP0X_NEWLITERALS
	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (int c)
	{
		append(core::stringc(c));
		return *this;
	}


	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (unsigned int c)
	{
		append(core::stringc(c));
		return *this;
	}
#endif


	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (long c)
	{
		append(core::stringc(c));
		return *this;
	}


	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (unsigned long c)
	{
		append(core::stringc(c));
		return *this;
	}


	//! Appends a number to this ustring16.
	//! \param c Number to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (double c)
	{
		append(core::stringc(c));
		return *this;
	}


	//! Appends a char ustring16 to this ustring16.
	//! \param c Char ustring16 to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (const uchar16_t* const c)
	{
		append(c);
		return *this;
	}


	//! Appends a ustring16 to this ustring16.
	//! \param other ustring16 to append.
	//! \return A reference to our current string.
	ustring16<TAlloc>& operator += (const ustring16<TAlloc>& other)
	{
		append(other);
		return *this;
	}


	//! Replaces all characters of a given type with another one.
	//! \param toReplace Character to replace.
	//! \param replaceWith Character replacing the old one.
	//! \return A reference to our current string.
	ustring16<TAlloc>& replace(uchar32_t toReplace, uchar32_t replaceWith)
	{
		iterator i(*this, 0);
		while (!i.atEnd())
		{
			typename ustring16<TAlloc>::access a = *i;
			if ((uchar32_t)a == toReplace)
				a = replaceWith;
			++i;
		}
		return *this;
	}


	//! Replaces all instances of a string with another one.
	//! \param toReplace The string to replace.
	//! \param replaceWith The string replacing the old one.
	//! \return A reference to our current string.
	ustring16<TAlloc>& replace(const ustring16<TAlloc>& toReplace, const ustring16<TAlloc>& replaceWith)
	{
		if (toReplace.size() == 0)
			return *this;

		const uchar16_t* other = toReplace.c_str();
		const uchar16_t* replace = replaceWith.c_str();
		const u32 other_size = toReplace.size_raw();
		const u32 replace_size = replaceWith.size_raw();

		// Determine the delta.  The algorithm will change depending on the delta.
		s32 delta = replace_size - other_size;

		// A character for character replace.  The string will not shrink or grow.
		if (delta == 0)
		{
			s32 pos = 0;
			while ((pos = find_raw(other, pos)) != -1)
			{
				for (u32 i = 0; i < replace_size; ++i)
					array[pos + i] = replace[i];
				++pos;
			}
			return *this;
		}

		// We are going to be removing some characters.  The string will shrink.
		if (delta < 0)
		{
			u32 i = 0;
			for (u32 pos = 0; pos <= used; ++i, ++pos)
			{
				// Is this potentially a match?
				if (array[pos] == *other)
				{
					// Check to see if we have a match.
					u32 j;
					for (j = 0; j < other_size; ++j)
					{
						if (array[pos + j] != other[j])
							break;
					}

					// If we have a match, replace characters.
					if (j == other_size)
					{
						for (j = 0; j < replace_size; ++j)
							array[i + j] = replace[j];
						i += replace_size - 1;
						pos += other_size - 1;
						continue;
					}
				}

				// No match found, just copy characters.
				array[i - 1] = array[pos];
			}
			array[i] = 0;
ofs	hex dump	ascii
0000	89 50 4e 47 0d 0a 1a 0a 00 00 00 0d 49 48 44 52 00 00 01 5d 00 00 00 c5 08 06 00 00 00 f7 ca 21	.PNG........IHDR...]...........!
0020	2d 00 00 00 04 73 42 49 54 08 08 08 08 7c 08 64 88 00 00 10 4d 49 44 41 54 78 9c ed dd 7d 90 14	-....sBIT....\|.d....MIDATx...}..
0040	75 7e c7 f1 cf 3c ec 72 22 3e 44 61 05 0a e5 41 02 21 04 8e e8 5a 2c 52 e0 25 5e ee 6a eb 0e a3	u~...<.r">Da...A.!...Z,R.%^.j...
0060	f1 d8 d2 a8 5c 08 46 6f bd c8 3d 50 3e 04 96 07 4f a4 f4 52 44 c4 4d 36 14 07 94 7a 82 05 9c 90	....\.Fo..=P>...O..RD.M6...z....
0080	02 6a eb 0e 2f a1 ac 2b 81 bb 5b 49 69 3c 82 a8 eb 52 6a 85 67 90 65 97 5d 66 a6 f3 47 33 bd d3	.j../..+..[Ii<...Rj.g.e.]f..G3..
00a0	b3 d3 c3 cc ec cc 6f 7a 66 df af aa ad fa f5 fe 7a 7b db 96 fa ec 77 be f3 eb 9e 40 75 75 b5 25	......ozf.......z{....w....@uu.%
00c0	00 80 11 c1 62 9f 00 00 f4 27 84 2e 00 18 44 e8 02 80 41 84 2e 00 18 14 4e fe c6 a7 ad 9f 15 e3	....b....'....D...A.....N.......
00e0	3c 8c 1b 35 7a 44 56 fb 73 5d 52 e3 ba 00 d9 e9 15 ba 92 74 e5 a0 01 a6 cf c3 a8 f3 ed 5d 39 fd	<..5zDV.s]R........t.........]9.
0100	1c d7 25 35 ae 0b 90 39 da 0b 00 60 10 a1 0b 00 06 11 ba 00 60 10 a1 0b 00 06 11 ba 00 60 10 a1	..%5...9...`........`........`..
0120	0b 00 06 a5 5c 32 06 ff a9 ad ad f5 9c 6b 6e 6e 36 78 26 fe c2 75 41 a9 a1 d2 05 00 83 08 5d 00	....\2.......knn6x&..uA.......].
0140	30 88 f6 82 8f a4 7b a9 dc d4 d4 e4 39 57 5f 5f ef 39 57 0e 2f b1 b9 2e 28 27 54 ba 00 60 10 a1	0.....{.....9W__.9W./...('T..`..
0160	0b 00 06 11 ba 00 60 10 3d 5d c3 72 ed 4f a6 53 0e 7d 4d ae 0b fa 0b 2a 5d 00 30 88 d0 05 00 83	......`.=].r.O.S.}M....*].0.....
0180	68 2f 14 40 21 5e 2a a7 d3 bc f3 4d d7 f6 9e b7 f7 3a e3 15 cb 97 b9 e6 16 36 b8 b7 4d e2 ba 00	h/.@!^*....M.....:.......6..M...
01a0	54 ba 00 60 14 a1 0b 00 06 11 ba 00 60 90 b1 9e ee e6 ae 9e 0f f7 db 7c f2 a4 e7 7e 5b 87 0f 37	T..`........`..........\|...~[..7
01c0	71 3a 7d 66 ba 3f b9 a6 a9 d1 73 ae ae 6e b6 6b bb 66 da 74 67 7c f6 f4 29 d7 dc dc 87 ee f7 3c	q:}f.?....s..n.k.f.tg\|..)......<
01e0	ce d6 2d db 73 3c bb 1e 5c 17 20 3d 2a 5d 00 30 88 d0 05 00 83 0a d6 5e 48 6c 27 24 ab bb fe 7a	..-.s<..\..=*].0.......^Hl'$...z
0200	ef 1f fc e2 0b d7 66 a9 b4 1b 1a 5f 5e e5 8c 9f 59 b6 c4 35 17 0a 85 9c 71 c3 e2 a5 9e c7 c8 e6	......f...._^...Y..5....q.......
0220	a5 72 a2 e4 97 ca 1d 9d 9d ce b8 fd 5c bb e7 cf 99 c0 75 01 dc a8 74 01 c0 20 42 17 00 0c 22 74	.r..........\.....u...t...B..."t
0240	01 c0 a0 bc f6 74 d3 f5 71 d3 2d 13 4b ec f1 f6 ea f7 26 f4 78 8b dd df 4d 5c 0e f5 d4 82 f9 ae	.....t..q.-.K.....&.x...M\......
0260	b9 ce 8e 0e 67 dc d0 b0 c8 f3 18 af ac 5f eb 39 57 88 fe e4 86 d7 36 79 ce e5 eb 69 5a 5c 17 20	....g........_.9W.....6y...iZ\..
0280	73 54 ba 00 60 10 a1 0b 00 06 f5 a9 bd 90 8f 76 c2 e5 b8 f6 4d 5a 4e 96 c8 74 eb e1 d8 b1 e3 9e	sT..`..........v....MZN..t......
02a0	db 55 55 43 5c 73 83 ab 86 3a e3 07 e7 cc 71 cd 2d 5c d8 e0 8c ef 98 59 fa 2f 95 b9 2e 40 7a 54	.UUC\s...:....q.-\.....Y./...@zT
02c0	ba 00 60 10 a1 0b 00 06 11 ba 00 60 50 d6 3d dd 5c fb b8 e9 f6 cb b4 c7 9b bc 5f e2 71 be 63 e0	..`........`P.=.\........._.q.c.
02e0	f6 e1 4c fb 80 c9 4f ac 4a d7 d7 4c e7 e4 89 13 ce 78 e3 e6 6d 7d 3e af 42 e1 ba 00 99 a3 d2 05	..L...O.J..L.....x..m}>.B.......
0300	00 83 08 5d 00 30 28 fb f6 42 86 2d 84 6c 96 85 e5 e3 98 c9 73 5b 33 fe ed b9 c9 f5 a5 6b f2 4b	...].0(..B.-.l......s[3......k.K
0320	ec 7b ef 9e e5 8c 5f 58 b9 3a ef bf cf 34 ae 0b 90 1e 95 2e 00 18 44 e8 02 80 41 84 2e 00 18 94	.{...._X.:...4........D...A.....
0340	75 4f 37 dd 52 ac c4 65 5b 99 f6 69 b3 91 f6 d6 e2 01 03 f2 fe fb 72 95 af 3e 63 b9 f5 2b b9 2e	uO7.R..e[..i..........r..>c..+..
0360	00 95 2e 00 18 45 e8 02 80 41 79 7d 88 79 a6 77 81 25 df 3d 96 ef e3 fb 19 2f 8d 53 e3 ba a0 bf	.....E...Ay}.y.w.%.=...../.S....
0380	a0 d2 05 00 83 08 5d 00 30 88 d0 05 00 83 f2 da d3 cd 54 39 f4 66 01 20 17 54 ba 00 60 10 a1 0b	......].0.........T9.f...T..`...
03a0	00 06 11 ba 00 60 10 a1 0b 00 06 11 ba 00 60 10 a1 0b 00 06 a5 5c 32 76 be dd fb c3 27 fb 33 ae	.....`........`......\2v....'.3.
03c0	4b 6a 5c 17 20 73 81 ea ea 6a ab d8 27 01 00 fd 05 ed 05 00 30 88 d0 05 00 83 08 5d 00 30 88 d0	Kj\..s...j..'.......0......].0..
03e0	05 00 83 08 5d 00 30 a8 d7 92 b1 4f 5b 3f 2b c6 79 18 37 6a f4 88 ac f6 e7 ba a4 c6 75 41 36 f8	....].0....O[?+.y.7j........uA6.
0400	f7 e2 b1 4e f7 ca 41 fe f9 64 dd 42 c8 75 5d 29 d7 25 35 ae 0b b2 d1 df ff bd d0 5e 00 00 83 08	...N..A..d.B.u]).%5........^....
0420	5d 00 30 a8 28 9f 1c 01 00 89 e6 b5 b5 79 ce ad 1b 39 d2 e0 99 14 1e a1 0b a0 a8 5c 81 7b e3 28	].0.(........y...9.........\.{.(
0440	69 cc 78 a9 a2 42 7a 6b a7 24 e9 e1 b6 36 5d 25 e9 c5 32 09 5f 42 17 40 d1 38 81 5b 39 40 ba 6f	i.x..Bzk.$...6]%..2._B.@.8.[9@.o
0460	9e 34 f1 ab d2 c5 6e c9 b2 a4 19 77 4a 6b 56 ca fa e2 33 7d 29 a9 a1 ad 4d cb cb 20 78 e9 e9 02	.4....n....wJkV...3})...M...x...
0480	28 be 7f 7c 5a 1a 3b 5e ea ba 20 c5 62 76 e8 06 82 52 fd 93 d2 cd e3 25 49 c7 24 3d 97 a6 0d 51	(..\|Z.;^....bv...R.....%I.$=...Q
04a0	2a a8 74 51 d2 6a 6b 6b 3d e7 9a 9b 9b 0d 9e 09 72 76 4b 8d 34 b8 4a 8a 44 7a cf 59 96 f4 ed d9	*.tQ.jkk=.......rvK.4.J.Dz.Y....
04c0	d2 4b cb 15 91 74 de f8 c9 e5 1f 95 2e 80 e2 fa b3 3f 4f 1d b8 71 c3 46 48 c3 46 28 20 3b 74 7f	.K...t...........?O..q.FH.F(.;t.
04e0	52 e2 d5 2e a1 0b a0 b8 ae 18 98 7e 3e 1a 95 fe 74 b2 3d 34 70 3a 85 46 7b 01 be 97 ae 85 d0 d4	R..........~>...t.=4p:.F{.......
0500	d4 e4 39 57 5f 5f ef 39 d7 9f 5a 0f 96 d5 fb 73 0a 02 81 40 11 ce c4 c3 c7 87 a4 11 23 ed 56 42	..9W__.9..Z....s...@........#.VB
0520	2a c1 80 f4 f9 11 49 52 44 d2 e7 e6 ce ac 20 a8 74 81 32 65 59 96 13 b8 b1 58 cc f9 8a cf f9 c6	*.....IRD.......t.2eY....X......
0540	7f 35 4b a1 34 f5 df a9 93 d2 ff fe 8f 2c d9 81 95 a6 11 51 12 08 5d a0 cc c5 c3 76 c2 84 09 9a	.5K.4........,.....Q..]....v....
0560	30 61 82 22 91 88 62 b1 98 2b 94 8b 2a 1a 95 d6 bd 24 a5 aa be 2b 2a a5 ed 9b 24 49 01 49 b1 31	0a."..b..+......$...+...$I.I.1
0580	e3 24 49 8f 96 70 5f 97 d0 05 ca 54 62 75 1b 8d f6 74 43 a3 d1 a8 53 f1 4a c5 ad 7a 9d bb cd 3e	.$I..p_....Tbu...tC...S.J..z...>
05a0	3e 24 fd f3 12 e9 42 a7 1d c2 96 25 75 76 48 ff fa bc 74 f8 0f 92 a4 f6 a9 33 15 79 74 81 74 db	>$....B....%uvH...t......3.yt.t.
05c0	ed 8a 28 fd 5d 6c 7e 46 4f 17 be 90 6b df 36 1d fa bd 3d 12 43 77 f2 64 fb 4d a9 0f 3e f8 40 92	..(.]l~FO...k.6...=.Cw.d.M..>.@.
05e0	14 0c 06 15 0c 06 8b df e7 fd f2 8c f4 fc 22 e9 aa ab ec 9b 25 4e 9d 90 a2 51 05 24 9d 1b f3 c7	..............".....%N...Q.$....
0600	ba b2 f6 1e 59 5d 17 a4 bb ee 93 7e f7 8e 24 fb 6e b5 1b 24 3d 57 42 37 4d 50 e9 02 65 2e b1 97	....Y].....~..$.n..$=WB7MP..e...
0620	9b 28 1a 8d ba aa de 62 55 bc eb 46 8e ec a9 78 63 51 e9 ec 19 e9 f8 51 29 1a 55 4c 52 d7 ad d3	.(.....bU..F...xcQ.....Q).ULR...
0640	74 d5 f7 9e 50 20 78 29 ae 2c 4b fa da 37 ec a1 ec 9b 26 4a 09 95 2e d0 4f c5 2b 5e c9 ae 7a 8b	t...P.x).,K..7....&J....O.+^..z.
0660	5d f1 26 3e d8 66 5e 5b 9b a2 92 42 92 2a 3f 3a 68 57 b8 89 be 7e 97 34 64 a8 b4 e5 55 c5 2e ed	].&>.f^[...B.*?:hW...~.4d...U...
0680	5f 2a 0f c6 21 74 61 4c 21 5a 08 e9 34 ef 7c d3 b5 bd e7 ed bd ce 78 c5 f2 65 ae b9 85 0d ee 6d	_*..!taL!Z..4.\|.......x..e.....m
06a0	14 57 3c 40 e7 b5 b5 d9 95 ef e2 f9 f6 1b 6d 3f 58 24 5d 37 c4 ae 88 27 dd 2a 4d 99 2a 7d 72 48	.W<@..........m?X$]7...'.M.}rH
06c0	5a b7 da e9 f1 fa 3d 7c 69 2f 00 f0 45 9b 21 15 57 80 5a 96 d4 f8 bc d4 9d f0 c9 0c d1 88 34 6a	Z.....=\|i/..E.!.W.Z...........4j
06e0	ac f4 f8 3f 39 df 5a e0 f3 37 d8 08 5d 00 9a 3c 79 b2 26 4e 9c e8 5a 4e e6 17 ae e0 8d 44 a4 15	...?9.Z..7..]..<y.&N..ZN.....D..
0700	4f 4b c1 84 e8 b2 2c a9 6a 98 f4 7d fb fb 67 24 3d ee e3 e0 25 74 01 38 92 2b 5e bf 84 af 2b 78	OK....,.j..}..g$=...%t.8.+^...+x
0720	63 31 a9 f5 70 ef e0 bd 61 98 f4 c3 c5 92 a4 0e 49 3f f4 69 f0 d2 d3 45 5e 99 ee db ae 69 6a f4	c1..p...a.......I?.i...E^....ij.
0740	9c ab ab 9b ed da ae 99 36 dd 19 9f 3d 7d ca 35 37 f7 a1 fb 3d 8f b3 75 cb f6 1c cf ae f4 24 2e	........6...=}.57...=..u......$.
0760	27 0b 5e 0a 35 5f 2c 27 93 1d bc ce da dc 75 ab a5 d9 73 a4 af de 66 87 70 dc b5 d7 49 e1 b0 14	'.^.5_,'......u...s...f.p...I...
0780	89 e8 9c a4 1f b5 b5 f9 ee e1 e7 54 ba 00 7a 89 57 bc 7e eb f3 ba 2a de 2d af 4a bf 7f 47 aa ac	...........T..z.W.~...*.-.J..G..
07a0	74 ef f4 e4 72 e9 9a 3f 92 24 9d 95 f4 98 cf 2a 5e 42 17 28 b0 f8 cb f4 f8 ba 58 53 5f 91 48 44	t...r..?.$.....*^B.(......XS_.HD
07c0	91 48 44 96 65 a5 5c a7 9b 4e bc c7 eb c7 3e af 2b 78 b7 6f 92 76 ef 74 b7 1a be 72 85 34 7f 91	.HD.e.\..N....>.+x.o.v.t...r.4..
07e0	74 ed 75 0a 48 ea 92 34 df 47 c1 4b 7b 01 05 d5 f8 f2 2a 67 fc cc b2 25 ae b9 50 28 e4 8c 1b 16	t.u.H..4.G.K{.....*g...%..P(....
0800	2f f5 3c 46 36 2d 84 44 c9 2d 84 8e ce 4e 67 dc 7e ae dd f3 e7 0a 21 b1 6a cc 36 00 73 15 0f c9	/.<F6-.D.-...Ng.~.....!.j.6.s...
0820	e4 db 7e b3 15 bf 9b 2d 18 0c ca b2 2c df b4 1a a4 4b 4b ca 7e bd cb fe ba 65 aa 54 37 d7 5e dd	..~....-....,....KK.~....e.T7.^.
0840	50 51 21 fd 78 a9 bd b4 ec d5 7f d7 f9 4f 3e d4 df b7 b5 69 bd 0f 5a 0d 54 ba 00 4a 96 ab ea 7d	PQ!.x........O>....i..Z.T..J...}
0860	77 bf b4 f6 45 f7 0e c1 90 f4 dd c7 a4 b1 7f a2 80 a4 ef fb a0 e2 a5 d2 05 0a 24 f1 b1 8a 91 48	w...E.....................$....H
0880	44 93 26 4d 2a f2 19 e5 26 f9 cd 35 bf bc b1 16 e7 7a 83 ed e3 43 52 b8 42 8a 5c ec d9 21 10 b0	D.&M*...&..5.....z...CR.B.\..!..
08a0	83 f7 cd 9f eb c2 81 df ea e1 b6 36 fd 2c 45 c5 5b 53 73 a7 6b 3b 10 08 68 ef de b7 f2 7e be 54	...........6.,E.[Ss.k;..h....~.T
08c0	ba 40 81 c5 43 b7 d4 f9 f5 06 0a 29 a9 e2 5d fd 5c ef 1d 2c 4b ba f7 21 7b 28 e9 91 14 15 6f fc	.@..C......)..].\..,K..!{(....o.
08e0	0f 4a a1 ff b0 50 e9 a2 cf 12 97 89 3d b5 60 be 6b ae b3 a3 c3 19 37 34 2c f2 3c c6 2b eb d7 7a	.J...P......=.`.k.....74,.<.+..z
0900	ce 15 a2 6f bb e1 b5 4d 9e 73 e5 f8 94 b1 7c 88 57 bc 07 0f 1e 74 96 93 f9 89 53 f1 fe df e7 d2	...o...M.s....\|.W....t....S.....
0920	8b 3f 91 1e 7b d2 7e 53 2d fe 07 22 16 93 6a 66 4a fb de 56 54 f2 ac 78 0b cd 7f 57 0e 28 33 5e	.?..{.~S-.."..jfJ..VT..x...W.(3^
0940	4f f9 42 fe 39 15 ef e9 93 d2 4f 1b a4 f6 73 ee 1d be f5 1d e9 af be 2d c9 ae 78 1f 2e 42 8f 97	O.B.9.....O...s........-..x..B..
0960	d0 05 0a 2c fe 72 b5 d4 1d 38 70 40 ef bf ff 7e b1 4f 23 73 17 2f 4a 4d 3f 95 ce b7 f7 7c 2a 85	...,.r...8p@...~.O#s./JM?....\|*.
0980	65 49 7f 51 2b cd aa b3 37 65 07 ef d3 06 c3 97 f6 02 f2 ea d8 b1 e3 9e db 55 55 43 5c 73 83 ab	eI.Q+...7e...............UUC\s..
09a0	86 3a e3 07 e7 cc 71 cd 2d 5c d8 e0 8c ef 98 49 0b c1 0f 42 a1 50 49 fc 01 71 2d 27 fb f2 ac f4	.:....q.-\.....I...B.PI..q-'....
09c0	c2 22 7b 1d ef 23 3f 92 86 df 64 3f bf e1 b6 e9 d2 d4 19 d2 87 7f 90 f5 6a 93 8e 5f e6 98 f9 44	."{..#?...d?............j.._...D
09e0	e8 02 05 16 0c 06 15 0e 87 75 e0 c0 01 49 e6 d6 e9 26 af 0b 9e 3a 75 6a 4e c7 69 69 69 51 45 45	.........u...I...&...:ujN.iiiQEE
0a00	85 13 ba 92 cf 3e 4d d8 83 6b 55 43 2c 66 df 3a bc e4 5f 24 2b d6 f3 bd f1 13 a5 fa 27 a4 35 2b	.....>M..kUC,f.:.._$+.......'.5+
0a20	8d 9d 97 bf ff 64 01 40 1f b8 56 35 5c bc 28 b5 7d e4 fe 00 cc 68 54 1a 36 42 7a 74 81 b1 73 a2	.....d.@..V5\.(.}....hT.6Bzt..s.
0a40	d2 05 0a 24 5e 0d c6 2b dd 78 95 58 8c 3b d2 ba bb bb 73 3e 4e bc ca 0d 87 ed b8 28 85 2a 37 91	...$^..+.x.X.;....s>N......(.*7.
0a60	ab e2 fd d9 4b d2 5f df 67 b7 17 12 ff 3f 0c bf 51 3a 73 da c8 f9 10 ba e8 b3 4c fb a3 c9 4f f2	....K._.g....?..Q:s.......L...O.
0a80	4a d7 ef 4d e7 e4 89 13 ce 78 e3 e6 6d 7d 3e 2f 13 12 fb a0 a6 7a a2 f1 b5 c1 89 6d 81 4c c5 5b	J..M.....x..m}>/.....z.....m.L.[
0aa0	0a c9 3f 5f 6a 81 1b e7 0a de ff 78 c3 be 55 f8 f6 bf ec 69 35 a4 58 77 6c 15 e8 bf 95 f6 02 50	..?_j......x..U....i5.Xwl......P
0ac0	60 81 40 40 81 40 40 a1 50 c8 e8 57 38 1c 56 38 1c 56 20 10 c8 3a 74 e3 d5 6d fc 38 7e bb 0b 2d	`.@@.@@.P..W8.V8.V...:t..m.8~..-
0ae0	17 ae 56 43 f3 36 e9 dd 7d ee 56 43 92 58 e5 00 fd a0 00 ab 1a 08 5d 00 8e 96 96 16 bd f7 de 7b	..VC.6..}.VC.X........]........{
0b00	bd 56 2a 94 7a e0 c6 b9 82 77 db eb f6 57 b8 c2 63 6f 4b 9d 92 ea f3 1c bc b4 17 90 57 b9 be a4	.V*.z....w...W..coK.........W...
0b20	4f 6e 3d dc 7b f7 2c 67 fc c2 ca d5 79 ff 7d 48 2d b9 7f 2b 95 4f e0 c6 b9 96 94 bd bb df fe ba	On=.{.,g....y.}H-..+.O..........
0b40	69 b4 34 dd fd ec 05 45 22 d2 d8 f1 ea fe e8 90 ea db da d4 94 a7 bb d7 a8 74 01 f4 aa 70 a5 9e	i.4....E"................t...p..
0b60	b6 48 b9 72 55 bd 47 5a 7b ef d0 dd 25 cd 7d 5c 1a 3d 56 dd 92 1e cd 53 c5 4b e8 02 70 55 b8 e5	.H.rU.GZ{...%.}\.=V....S.K..pU..
0b80	d0 bf cd 54 fa 8f 6b bf 74 0d be f7 84 24 29 a2 fc b4 1a 08 5d 00 fd 5a fa e0 95 d4 75 41 9a f1	...T..k.t....$).....]..Z....uA..
0ba0	75 49 52 b7 a4 7f e8 63 f0 d2 d3 85 31 f9 ea bf d2 c7 cd 8f 96 96 16 49 2a c9 bb cd f2 6d dd c8	uIR....c....1..........I*....m..
0bc0	91 ba 3d dd 0e df b8 cb 7e 62 d9 ee 1d 8a 49 fa 71 24 a2 9b d7 ac d1 b4 69 d3 14 0c 06 b5 6f df	..=.....~b....I.q$......i.....o.
0be0	3e 2d 5d ba 54 47 8f 1e bd ec ef a2 d2 05 fa a9 8a 8a 8a 7e db 56 c8 58 e2 83 72 be f6 4d e9 9b	>-].TG.............~.V.X..r..M..
0c00	77 4b 92 ee 79 e3 0d 0d 6a 69 51 4d 4d 8d a6 4c 99 a2 23 47 8e e8 d9 67 9f cd e8 c6 17 2a 5d a0	wK..y...jiQMM..L..#G...g.....*].
0c20	cc 25 3f a4 26 f1 59 0a f1 79 a9 7f 56 b8 69 05 83 f6 b3 79 07 df 60 6f 47 a3 d2 8c 3b a5 ab af	.%?.&.Y..y..V.i....y..`oG...;...
0c40	d1 8e 79 f3 f4 d6 e1 c3 9a 61 59 7a eb a6 9b b4 6a d5 2a ed df bf 5f 9d 9d 9d ba 5c ac 12 ba f0	..y......aYz....j.*..._....\....
0c60	05 5a 06 85 95 f8 21 a0 fd 61 59 58 3e 7c a5 f3 bc ac d5 2b ec 8d e5 8d f6 87 5c c6 62 d2 a4 5b	.Z....!..aYX>\|.....+......\.b..[
0c80	74 72 f2 ad 1a ff df bf d3 c0 5f bc a6 87 8f 1c d1 98 71 e3 74 f4 e8 51 45 22 11 85 43 84 2e d0	tr........_.......q.t..QE"..C...
0ca0	2f 25 df 85 16 7f 16 6e f2 6d c1 04 6e 06 f6 ee b1 3f 75 22 7e bb b0 65 69 e0 94 db a4 a1 c3 15	/%.....n.m..n....?u"~..ei.......
0cc0	5a fb a2 66 ac 5d ab f7 96 2d cb e8 ce 3f 7a ba 40 99 8a af b3 8d 3f 70 a7 b2 b2 52 95 95 95 0a	Z..f.]...-...?z.@.....?p...R....
0ce0	87 c3 0a 85 42 65 bf 0e b7 af ba 07 5d ad b5 f1 95 0d bb b6 da b7 0d 57 0e e8 d9 c1 b2 34 60 e4	....Be......]..........W.....4`.
0d00	18 fd ed 2f 7f a5 0f 77 ed d2 fa d7 5f d7 df 9d 3a 95 fa 60 09 08 5d a0 cc 25 07 2b 41 9b 99 40	.../...w...._...:..`..]..%.+A..@
0d20	f2 9b 62 db 36 4a bf de 65 f7 7a 25 5d 7d f5 20 7d 77 ce df e8 e0 b1 33 fa b7 55 ab 74 bd a4 5f	..b.6J..e.z%]}..}w.....3..U.t.._
0d40	64 70 d7 1a a1 0b 00 69 b8 d6 f1 ee de 21 6d df a4 2b 06 0e d4 03 0f dc a3 df fc e6 b7 6a fa f9	dp.....i.....!m..+...........j..
0d60	46 0d 79 e0 11 ed ce f0 36 61 42 17 e8 07 e2 ad 04 aa dc dc b8 82 f7 f7 ef e8 ce 9b ab f4 e1 e1	F.y.....6aB.....................
0d80	4f b4 61 c3 06 dd 78 e3 28 fd f2 3f 77 64 7c 2c 42 17 00 32 90 18 bc 53 66 7d 4b d3 6a 6e d1 8e	O.a...x.(..?wd\|,B..2...Sf}K.jn..
0da0	1d 9b d5 d8 f8 bc 5a 5b 5b d5 da da aa 71 e3 c6 5d f6 38 ac 5e 00 80 0c 39 c1 1b 0e 6b 8f a4 96	......Z[[....q..].8.^...9...k...
0dc0	6b ae e9 b5 4f 28 38 a0 d7 f7 12 11 ba 00 90 a5 78 f8 5e 9b 62 ee 7c 7b 57 da 9f a5 bd 00 00 06	k...O(8.........x.^.b.\|{W.......
0de0	11 ba 00 60 50 ca f6 c2 e5 ca e3 fe 8a eb 92 1a d7 05 d9 f0 eb bf 97 dd bf da 69 e4 f7 04 aa ab	...`P.....................i.....
0e00	ab 7b 7f 0c 26 00 a0 20 68 2f 00 80 41 84 2e 00 18 44 e8 02 80 41 84 2e 00 18 44 e8 02 80 41 bd	.{..&...h/..A....D...A....D...A.
0e20	96 8c 7d da fa 59 31 ce c3 b8 51 a3 47 64 b5 3f d7 25 35 ae 0b 90 9d 94 eb 74 af 1c 94 fe de e1	..}..Y1...Q.Gd.?.%5......t......
0e40	52 97 eb 3a 41 ae 4b 6a 5c 17 20 73 b4 17 00 c0 20 42 17 00 0c 22 74 01 c0 20 42 17 00 0c 22 74	R..:A.Kj\..s.....B..."t...B..."t
0e60	01 c0 20 42 17 00 0c e2 93 23 50 d2 6a 6b 6b 3d e7 9a 9b 9b 0d 9e 09 90 19 2a 5d 00 30 88 d0 05	...B.....#P.jkk=.........*].0...
0e80	00 83 68 2f c0 f7 d2 b5 10 9a 9a 9a 3c e7 ea eb eb 3d e7 68 3d a0 58 a8 74 01 c0 20 42 17 00 0c	..h/........<....=.h=.X.t...B...
0ea0	22 74 01 c0 20 7a ba f0 85 5c fb b6 e9 d0 ef 85 1f 51 e9 02 80 41 84 2e 00 18 44 7b 01 c6 14 a2	"t...z...\.......Q...A....D{....
0ec0	85 90 4e f3 ce 37 5d db 7b de de eb 8c 57 2c 5f e6 9a 5b d8 e0 de 06 0a 85 4a 17 00 0c 22 74 01	..N..7].{....W,_..[......J..."t.
0ee0	c0 20 42 17 00 0c a2 a7 8b bc 32 dd b7 5d d3 d4 e8 39 57 57 37 db b5 5d 33 6d ba 33 3e 7b fa 94	..B.......2..]...9WW7..]3m.3>{..
0f00	6b 6e ee 43 f7 7b 1e 67 eb 96 ed 39 9e 1d d0 1b 95 2e 00 18 44 e8 02 80 41 b4 17 50 50 8d 2f af	kn.C.{.g...9........D...A..PP./.
0f20	72 c6 cf 2c 5b e2 9a 0b 85 42 ce b8 61 f1 52 cf 63 64 d3 42 48 94 dc 42 e8 e8 ec 74 c6 ed e7 da	r..,[....B..a.R.cd.BH..B...t....
0f40	3d 7f 0e 28 24 2a 5d 00 30 88 d0 05 00 83 08 5d 00 30 88 9e 2e fa 2c 71 99 d8 53 0b e6 bb e6 3a	=..($*].0......].0....,q..S....:
0f60	3b 3a 9c 71 43 c3 22 cf 63 bc b2 7e ad e7 5c 21 fa b6 1b 5e db e4 39 c7 53 c6 50 48 54 ba 00 60	;:.qC.".c..~..\!...^..9.S.PHT..`
0f80	10 a1 0b 00 06 d1 5e 40 5e 1d 3b 76 dc 73 bb aa 6a 88 6b 6e 70 d5 50 67 fc e0 9c 39 ae b9 85 0b	......^@^.;v.s..j.knp.Pg...9....
0fa0	1b 9c f1 1d 33 69 21 a0 7c 50 e9 02 80 41 84 2e 00 18 44 e8 02 80 41 f4 74 d1 67 99 f6 47 93 9f	....3i!.\|P...A....D...A.t.g..G..
0fc0	e4 95 ae df 9b ce c9 13 27 9c f1 c6 cd db fa 7c 5e 80 49 54 ba 00 60 10 a1 0b 00 06 d1 5e 40 5e	........'......\|^.IT..`......^@^
0fe0	e5 fa 92 3e b9 f5 70 ef dd b3 9c f1 0b 2b 57 e7 fd f7 01 c5 42 a5 0b 00 06 11 ba 00 60 10 a1 0b	...>..p......+W.....B.......`...
1000	00 06 d1 d3 85 31 f9 ea bf d2 c7 45 29 a3 d2 05 00 83 08 5d 00 30 88 f6 02 7c 81 96 01 fa 0b 2a	.....1.....E)......].0...\|.....*
1020	5d 00 30 88 d0 05 00 83 08 5d 00 30 88 d0 05 00 83 08 5d 00 30 88 d0 05 00 83 08 5d 00 30 88 d0	].0......].0......].0......].0..
1040	05 00 83 08 5d 00 30 88 d0 05 00 83 52 de 06 7c be bd cb f4 79 94 04 ae 4b 6a 5c 17 20 73 81 ea	....].0.....R..\|....y...Kj\..s..
1060	ea 6a ab d8 27 01 00 fd 05 ed 05 00 30 88 d0 05 00 83 08 5d 00 30 88 d0 05 00 83 08 5d 00 30 e8	.j..'.......0......].0......].0.
1080	ff 01 e1 44 37 85 00 f1 be 44 00 00 00 00 49 45 4e 44 ae 42 60 82	...D7....D....IEND.B`.