/*
	Copyright (C) 2006 Christopher E. Miller
	
	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.
*/


/**
	Strings in D. This is only a pre-release; it is largely untested. Download $(LINK2 http://www.dprogramming.com/dstring04.zip, _dstring 0.4)
	Trademarks: Unicode(tm) is a trademark of Unicode, Inc.
**/
//module std.dstring;
module dstring;

import std.utf;


///
struct string
{
	/// Property: get the _length of the string.
	size_t length() // getter
	{
		return _len & LENGTH_MASK;
	}
	
	
	/// Property: get the _type of the underlying array of characters.
	TypeInfo type() // getter
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return typeid(char[]);
			case TYPE_UTF16:
				return typeid(wchar[]);
			case TYPE_UTF32:
				return typeid(dchar[]);
			default: // No type..
				return typeid(void); // ?
		}
	}
	
	
	/**
		Create a new instance of string.
		The _string passed in may be used as-is, and any string modifying functions may modify the original _string memory.
	**/
	static string opCall(char[] s)
	{
		if(s.length > MAX_LENGTH)
			errortoolong();
		
		size_t sct = TYPE_UTF8;
		
		foreach(dchar ch; s)
		{
			size_t x;
			x = smallestCharType(ch);
			if(x > sct)
			{
				sct = x;
				if(TYPE_UTF32 == x)
					break;
			}
		}
		
		string result;
		
		switch(sct)
		{
			case TYPE_UTF32:
				{
					dchar[] ds;
					ds = std.utf.toUTF32(s);
					result._dptr = ds.ptr;
					result._len = ds.length;
					result._len |= TYPE_UTF32;
				}
				break;
			
			case TYPE_UTF16:
				{
					wchar[] ws;
					ws = std.utf.toUTF16(s);
					result._wptr = ws.ptr;
					result._len = ws.length;
					result._len |= TYPE_UTF16;
				}
				break;
			
			default:
				result._cptr = s.ptr;
				result._len = s.length;
				result._len |= TYPE_UTF8;
		}
		
		return result;
	}
	
	/// ditto
	static string opCall(wchar[] s)
	{
		if(s.length > MAX_LENGTH)
			errortoolong();
		
		size_t sct = TYPE_UTF16;
		
		foreach(dchar ch; s)
		{
			size_t x;
			x = smallestCharType(ch);
			if(x > sct)
			{
				sct = x;
				//if(TYPE_UTF32 == x)
				assert(TYPE_UTF32 == x);
					break;
			}
		}
		
		string result;
		
		switch(sct)
		{
			case TYPE_UTF32:
				{
					dchar[] ds;
					ds = std.utf.toUTF32(s);
					result._dptr = ds.ptr;
					result._len = ds.length;
					result._len |= TYPE_UTF32;
				}
				break;
			
			default:
				result._wptr = s.ptr;
				result._len = s.length;
				result._len |= TYPE_UTF16;
		}
		
		return result;
	}
	
	/// ditto
	static string opCall(dchar[] s)
	{
		if(s.length > MAX_LENGTH)
			errortoolong();
		string result;
		result._dptr = s.ptr;
		result._len = s.length;
		result._len |= TYPE_UTF32;
		return result;
	}
	
	
	/// Shortcut for a null _string: string()
	static string opCall()
	{
		string result;
		return result;
	}
	
	
	/// For each character. Modifying the inout dchar in the foreach body may be done in-place or may cause reallocation.
	int opApply(int delegate(inout size_t, inout dchar) dg)
	{
		return _Tapply!(true).each(*this, dg);
	}
	
	/// ditto
	int opApply(int delegate(inout dchar) dg)
	{
		return _Tapply!(false).each(*this, dg);
	}
	
	
	/// Index of a single character.
	dchar opIndex(size_t i)
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return _cptr[0 .. this.length][i];
			case TYPE_UTF16:
				return _wptr[0 .. this.length][i];
			case TYPE_UTF32:
				return _dptr[0 .. this.length][i];
			default: // No type..
				return _cptr[0 .. this.length][i]; // ?
		}
	}
	
	
	/// Assign to a single character. This may be done in-place or may cause reallocation.
	void opIndexAssign(dchar ch, size_t i)
	{
		size_t sct;
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				sct = smallestCharType(ch);
				if(TYPE_UTF8 == sct)
				{
					_cptr[0 .. this.length][i] = ch;
				}
				else
				{
					switch(sct)
					{
						case TYPE_UTF16:
							{
								wchar[] ws;
								ws = std.utf.toUTF16(_cptr[0 .. this.length]);
								_wptr = ws.ptr;
								_len = ws.length;
								_len |= TYPE_UTF16;
								_wptr[0 .. this.length][i] = cast(wchar)ch;
							}
							break;
						case TYPE_UTF32:
							{
								dchar[] ds;
								ds = std.utf.toUTF32(_cptr[0 .. this.length]);
								_dptr = ds.ptr;
								_len = ds.length;
								_len |= TYPE_UTF32;
								_dptr[0 .. this.length][i] = ch;
							}
							break;
						default:
							assert(0);
					}
				}
				break;
			case TYPE_UTF16:
				sct = smallestCharType(ch);
				if(sct <= TYPE_UTF16)
				{
					_wptr[0 .. this.length][i] = cast(wchar)ch;
				}
				else
				{
					dchar[] ds;
					ds = std.utf.toUTF32(_wptr[0 .. this.length]);
					_dptr = ds.ptr;
					_len = ds.length;
					_len |= TYPE_UTF32;
					_dptr[0 .. this.length][i] = ch;
				}
				break;
			case TYPE_UTF32:
				_dptr[0 .. this.length][i] = ch;
				break;
			default: // No type..
				_cptr[0 .. this.length][i] = ch; // ?
		}
		//return ch;
	}
	
	
	/// Get a string slice. The returned slice refers to the original string's _string memory as with normal array slicing.
	string opSlice(size_t i1, size_t i2)
	in
	{
		assert(i2 >= i1);
	}
	body
	{
		string result;
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				{
					char[] cs;
					cs = _cptr[0 .. this.length][i1 .. i2];
					result._cptr = cs.ptr;
					result._len = cs.length;
					result._len |= TYPE_UTF8;
				}
				break;
			case TYPE_UTF16:
				{
					wchar[] ws;
					ws = _wptr[0 .. this.length][i1 .. i2];
					result._wptr = ws.ptr;
					result._len = ws.length;
					result._len |= TYPE_UTF16;
				}
				break;
			case TYPE_UTF32:
				{
					dchar[] ds;
					ds = _dptr[0 .. this.length][i1 .. i2];
					result._dptr = ds.ptr;
					result._len = ds.length;
					result._len |= TYPE_UTF32;
				}
				break;
			default: // No type..
				{
					// ?
					char[] cs;
					cs = _cptr[0 .. this.length][i1 .. i2];
					result._cptr = cs.ptr;
					result._len = cs.length;
				}
				break;
		}
		return result;
	}
	
	/+
	/// ditto
	void[] opSlice()
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return _cptr[0 .. this.length];
			case TYPE_UTF16:
				return _wptr[0 .. this.length];
			case TYPE_UTF32:
				return _dptr[0 .. this.length];
			default: // No type..
				return null;
		}
	}
	+/
	
	
	/// Assign a string to a slice. This may be done in-place or may cause reallocation.
	void opSliceAssign(string s2, size_t i1, size_t i2)
	{
		if(i1 > i2 || i2 > length)
			throw new StringException("Slice out of bounds");
		if(i2 - i1 != s2.length)
			throw new StringException("Lengths don't match for string copy");
		
		if((_len & TYPE_MASK) == (s2._len & TYPE_MASK))
		{
			_cptr[i1 .. i2] = s2._cptr[0 .. s2.length];
		}
		else if((_len & TYPE_MASK) > (s2._len & TYPE_MASK))
		{
			switch(_len & TYPE_MASK)
			{
				case TYPE_UTF16:
					switch(s2._len & TYPE_MASK)
					{
						case TYPE_UTF8:
							foreach(wchar wch; s2._cptr[0 .. s2.length])
							{
								_wptr[i1] = wch;
							}
							assert(i1 == i2);
							break;
						default: ;
					}
					break;
				case TYPE_UTF32:
					switch(s2._len & TYPE_MASK)
					{
						case TYPE_UTF8:
							foreach(wchar dch; s2._cptr[0 .. s2.length])
							{
								_dptr[i1] = dch;
							}
							assert(i1 == i2);
							break;
						case TYPE_UTF16:
							foreach(wchar dch; s2._wptr[0 .. s2.length])
							{
								_dptr[i1] = dch;
							}
							assert(i1 == i2);
							break;
						default: ;
					}
					break;
				default: ;
			}
		}
		else //if((_len & TYPE_MASK) < (s2._len & TYPE_MASK))
		{
			switch(s2._len & TYPE_MASK)
			{
				case TYPE_UTF16:
					{
						wchar[] ws;
						ws = new wchar[this.length];
						size_t iw;
						switch(_len & TYPE_MASK)
						{
							case TYPE_UTF8:
								for(iw = 0; iw != i1; iw++)
								{
									ws[iw] = cast(wchar)_cptr[iw];
								}
								ws[i1 .. i2] = s2._wptr[0 .. s2.length];
								for(iw = i2; iw != ws.length; iw++)
								{
									ws[iw] = cast(wchar)_cptr[iw];
								}
								break;
							default:
								assert(0);
						}
						_wptr = ws.ptr;
						_len = ws.length;
						_len |= TYPE_UTF16;
					}
					break;
				case TYPE_UTF32:
					{
						dchar[] ds;
						ds = new dchar[this.length];
						size_t iw;
						switch(_len & TYPE_MASK)
						{
							case TYPE_UTF8:
								for(iw = 0; iw != i1; iw++)
								{
									ds[iw] = cast(wchar)_cptr[iw];
								}
								ds[i1 .. i2] = s2._dptr[0 .. s2.length];
								for(iw = i2; iw != ds.length; iw++)
								{
									ds[iw] = cast(wchar)_cptr[iw];
								}
								break;
							case TYPE_UTF16:
								for(iw = 0; iw != i1; iw++)
								{
									ds[iw] = cast(wchar)_wptr[iw];
								}
								ds[i1 .. i2] = s2._dptr[0 .. s2.length];
								for(iw = i2; iw != ds.length; iw++)
								{
									ds[iw] = cast(wchar)_wptr[iw];
								}
								break;
							default:
								assert(0);
						}
						_dptr = ds.ptr;
						_len = ds.length;
						_len |= TYPE_UTF32;
					}
					break;
				default:
					assert(0);
			}
		}
	}
	
	
	/// Assign a repeating character to a slice. This may be done in-place or may cause reallocation.
	void opSliceAssign(dchar ch, size_t i1, size_t i2)
	{
		size_t sct;
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				sct = smallestCharType(ch);
				if(TYPE_UTF8 == sct)
				{
					_cptr[0 .. this.length][i1 .. i2] = ch;
				}
				else
				{
					switch(sct)
					{
						case TYPE_UTF16:
							{
								wchar[] ws;
								ws = std.utf.toUTF16(_cptr[0 .. this.length]);
								_wptr = ws.ptr;
								_len = ws.length;
								_len |= TYPE_UTF16;
								_wptr[0 .. this.length][i1 .. i2] = cast(wchar)ch;
							}
							break;
						case TYPE_UTF32:
							{
								dchar[] ds;
								ds = std.utf.toUTF32(_cptr[0 .. this.length]);
								_dptr = ds.ptr;
								_len = ds.length;
								_len |= TYPE_UTF32;
								_dptr[0 .. this.length][i1 .. i2] = ch;
							}
							break;
						default:
							assert(0);
					}
				}
				break;
			case TYPE_UTF16:
				sct = smallestCharType(ch);
				if(sct <= TYPE_UTF16)
				{
					_wptr[0 .. this.length][i1 .. i2] = cast(wchar)ch;
				}
				else
				{
					dchar[] ds;
					ds = std.utf.toUTF32(_wptr[0 .. this.length]);
					_dptr = ds.ptr;
					_len = ds.length;
					_len |= TYPE_UTF32;
					_dptr[0 .. this.length][i1 .. i2] = ch;
				}
				break;
			case TYPE_UTF32:
				_dptr[0 .. this.length][i1 .. i2] = ch;
				break;
			default: // No type..
				_cptr[0 .. this.length][i1 .. i2] = ch; // ?
		}
	}
	
	/// ditto
	void opSliceAssign(dchar ch)
	{
		return opSliceAssign(ch, 0, length);
	}
	
	
	/// Convert this string to a UTF-8 string of chars.
	char[] toString()
	{
		return toUTF8();
	}
	
	
	/// Concatenation; always returns a copy.
	string opCat(string s2)
	{
		return _TCat!(true).concat(*this, s2);
	}
	
	/// ditto
	string opCat(char[] s2)
	{
		return _TCat!(true).concat(*this, string(s2)); // To-do: optimize.
	}
	
	/// ditto
	string opCat(wchar[] s2)
	{
		return _TCat!(true).concat(*this, string(s2)); // To-do: optimize.
	}
	
	/// ditto
	string opCat(dchar[] s2)
	{
		return _TCat!(true).concat(*this, string(s2));
	}
	
	/+
	/// ditto
	string opCat_r(string s1)
	{
		return s1.opCat(*this);
	}
	+/
	
	/// ditto
	string opCat_r(char[] s1)
	{
		return string(_addTo(s1.dup)); // Can't use fromASCII.
	}
	
	/// ditto
	string opCat_r(wchar[] s1)
	{
		return string(_addTo(s1.dup)); // Can't use fromBMP.
	}
	
	/// ditto
	string opCat_r(dchar[] s1)
	{
		return string(_addTo(s1.dup));
	}
	
	
	/// Concatenate and assign. This may be done in-place using adjacent memory or may cause reallocation.
	string opCatAssign(string s2)
	{
		return *this = _TCat!(false).concat(*this, s2);
	}
	
	/// ditto
	string opCatAssign(char[] s2)
	{
		return *this = _TCat!(false).concat(*this, string(s2)); // To-do: optimize.
	}
	
	/// ditto
	string opCatAssign(wchar[] s2)
	{
		return *this = _TCat!(false).concat(*this, string(s2)); // To-do: optimize.
	}
	
	/// ditto
	string opCatAssign(dchar[] s2)
	{
		return *this = _TCat!(false).concat(*this, string(s2));
	}
	
	
	/**
		Create a new instance of string based on an ASCII-only _string.
		This is faster than string(s) (opCall).
		The _string passed in may be used as-is, and any string modifying functions may modify the original _string memory.
	**/
	static string fromASCII(char[] s)
	in
	{
		size_t iw;
		for(iw = 0; iw != s.length; iw++)
		{
			assert(!(s[iw] & 0x80)); // String must be within ASCII.
		}
	}
	body
	{
		if(s.length > MAX_LENGTH)
			errortoolong();
		
		string result;
		result._cptr = s.ptr;
		result._len = s.length;
		result._len |= TYPE_UTF8;
		return result;
	}
	
	/// ditto
	static string fromASCII(ubyte[] s)
	{
		return fromASCII(cast(char[])s);
	}
	
	
	/**
		Create a new instance of string based on an BMP-Unicode-only wide-character _string.
		This is faster than string(s) (opCall).
		The _string passed in may be used as-is, and any string modifying functions may modify the original _string memory.
		Information on BMP can be found at $(LINK http://en.wikipedia.org/wiki/Basic_Multilingual_Plane)
	**/
	static string fromBMP(wchar[] s)
	in
	{
		size_t iw;
		for(iw = 0; iw != s.length; iw++)
		{
			size_t idx = 0;
			std.utf.decode(s[iw .. s.length], idx);
			assert(1 == idx); // String must be within BMP.
		}
	}
	body
	{
		if(s.length > MAX_LENGTH)
			errortoolong();
		
		string result;
		result._wptr = s.ptr;
		result._len = s.length;
		result._len |= TYPE_UTF16;
		return result;
	}
	
	
	/// Convert the string to the different UTF types.
	char[] toUTF8()
	/+out(result)
	{
		std.utf.validate(result);
	}
	body+/
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return _cptr[0 .. this.length];
			case TYPE_UTF16:
				return std.utf.toUTF8(_wptr[0 .. this.length]);
			case TYPE_UTF32:
				return std.utf.toUTF8(_dptr[0 .. this.length]);
			default: // No type..
				return null;
		}
	}
	
	/// ditto
	wchar[] toUTF16()
	/+out(result)
	{
		std.utf.validate(result);
	}
	body+/
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return std.utf.toUTF16(_cptr[0 .. this.length]);
			case TYPE_UTF16:
				return _wptr[0 .. this.length];
			case TYPE_UTF32:
				return std.utf.toUTF16(_dptr[0 .. this.length]);
			default: // No type..
				return null;
		}
	}
	
	/// ditto
	dchar[] toUTF32()
	/+out(result)
	{
		std.utf.validate(result);
	}
	body+/
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return std.utf.toUTF32(_cptr[0 .. this.length]);
			case TYPE_UTF16:
				return std.utf.toUTF32(_wptr[0 .. this.length]);
			case TYPE_UTF32:
				return _dptr[0 .. this.length];
			default: // No type..
				return null;
		}
	}
	
	
	/**
		Compare this string with another. If ignoreCase is true, 'a' through 'z' are compared case insensitively.
		It is safe to _compare strings with different underlying character UTF types.
		Returns: $(UL $(LI $(B < 0) if this < s2) $(LI $(B = 0) if match) $(LI $(B > 0) if this > s2))
	**/
	int compare(string s2, bool ignoreCase = false)
	{
		switch(s2._len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return _scmp(s2._cptr[0 .. s2.length], ignoreCase, true);
			case TYPE_UTF16:
				return _scmp(s2._wptr[0 .. s2.length], ignoreCase, true);
			case TYPE_UTF32:
				return compare(s2._dptr[0 .. s2.length], ignoreCase);
			default:
				assert(!s2._len);
				if(!length)
					return 0;
				return 1;
		}
	}
	
	/// ditto
	int compare(char[] s2, bool ignoreCase = false)
	{
		return _scmp(s2, ignoreCase, false);
	}
	
	/// ditto
	int compare(wchar[] s2, bool ignoreCase = false)
	{
		return _scmp(s2, ignoreCase, false);
	}
	
	/// ditto
	int compare(dchar[] s2, bool ignoreCase = false)
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				return _TCmp!(char, dchar, false).compare(_cptr[0 .. this.length], s2, ignoreCase);
			case TYPE_UTF16:
				return _TCmp!(wchar, dchar, false).compare(_wptr[0 .. this.length], s2, ignoreCase);
			case TYPE_UTF32:
				return _TCmp!(dchar, dchar, false).compare(_dptr[0 .. this.length], s2, ignoreCase);
			default:
				assert(!_len);
				if(!s2.length)
					return 0;
				return -1;
		}
	}
	
	
	/// Find a string within this string. If ignoreCase is true, 'a' through 'z' are compared case insensitively.
	/// Returns: the starting index of the found string, or -1 if not found.
	int find(string s2, bool ignoreCase = false)
	{
		return _TFind!(typeof(s2)).find(*this, s2, ignoreCase);
	}
	
	/// ditto
	int find(char[] s2, bool ignoreCase = false)
	{
		return _TFind!(typeof(s2)).find(*this, s2, ignoreCase);
	}
	
	/// ditto
	int find(wchar[] s2, bool ignoreCase = false)
	{
		return _TFind!(typeof(s2)).find(*this, s2, ignoreCase);
	}
	
	/// ditto
	int find(dchar[] s2, bool ignoreCase = false)
	{
		return _TFind!(typeof(s2)).find(*this, s2, ignoreCase);
	}
	
	
	/// Returns: true if this string starts with, or ends with, the provided string. If ignoreCase is true, 'a' through 'z' are compared case insensitively.
	bool startsWith(string s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[0 .. s.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool startsWith(char[] s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[0 .. s.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool startsWith(wchar[] s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[0 .. s.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool startsWith(dchar[] s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[0 .. s.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool endsWith(string s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[this.length - s.length .. this.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool endsWith(char[] s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[this.length - s.length .. this.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool endsWith(wchar[] s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[this.length - s.length .. this.length].compare(s, ignoreCase);
	}
	
	/// ditto
	bool endsWith(dchar[] s, bool ignoreCase = false)
	{
		if(!s.length)
			return true;
		if(s.length > length)
			return false;
		return !(*this)[this.length - s.length .. this.length].compare(s, ignoreCase);
	}
	
	
	/// Property: get the pointer to the _string memory.
	void* ptr() // getter
	{
		return _ptr;
	}
	
	
	/// Comparison operators. It is safe to compare strings with different underlying character UTF types.
	int opEquals(string s2)
	{
		return !compare(s2, false);
	}
	
	/// ditto
	int opEquals(char[] s2)
	{
		return !compare(s2, false);
	}
	
	/// ditto
	int opEquals(wchar[] s2)
	{
		return !compare(s2, false);
	}
	
	/// ditto
	int opEquals(dchar[] s2)
	{
		return !compare(s2, false);
	}
	
	/// ditto
	int opCmp(string s2)
	{
		return compare(s2, false);
	}
	
	/// ditto
	int opCmp(char[] s2)
	{
		return compare(s2, false);
	}
	
	/// ditto
	int opCmp(wchar[] s2)
	{
		return compare(s2, false);
	}
	
	/// ditto
	int opCmp(dchar[] s2)
	{
		return compare(s2, false);
	}
	
	
	/// Reallocates this string using a smaller char type if possible. Generally only needed when slicing.
	void compact()
	{
		*this = _comp(*this, false);
	}
	
	
	/// Returns: duplicate string using new memory; compacts the returned string as necessary.
	string dup()
	{
		return _comp(*this, true);
	}
	
	
	/// Release the string memory; currently only empties the string.
	void cleanup()
	{
		_len = 0;
		_ptr = null;
	}
	
	
	/// The maximum amount of characters allowed in a string.
	const size_t MAX_LENGTH = LENGTH_MASK;
	
	
	private:
	
	size_t _len;
	union
	{
		char* _cptr;
		wchar* _wptr;
		dchar* _dptr;
		void* _ptr;
	}
	
	
	const size_t SIZE_T_BITS = size_t.sizeof * 8;
	
	
	const size_t LENGTH_MASK = (1 << (SIZE_T_BITS - 2)) - 1;
	const size_t TYPE_MASK = ~LENGTH_MASK;
	
	static assert(size_t.sizeof != 4 || string.LENGTH_MASK == 0x3FFFFFFF);
	
	
	const size_t TYPE_UTF8 = 0b01 << (SIZE_T_BITS - 2);
	const size_t TYPE_UTF16 = 0b10 << (SIZE_T_BITS - 2);
	const size_t TYPE_UTF32 = 0b11 << (SIZE_T_BITS - 2);
	
	static assert(TYPE_UTF32 > TYPE_UTF16 && TYPE_UTF16 > TYPE_UTF8);
	
	
	static size_t smallestCharType(dchar ch)
	{
		return (ch <= 0x7F) ? TYPE_UTF8 : (ch <= 0xFFFF) ? TYPE_UTF16 : TYPE_UTF32;
	}
	
	
	size_t smallestCharTypeForAll()
	{
		size_t result = 0; //TYPE_UTF8; // ?
		foreach(dchar ch; *this)
		{
			size_t x;
			x = smallestCharType(ch);
			if(x > result)
				result = x;
		}
		return result;
	}
	
	
	static void errortoolong()
	{
		throw new StringException("String length is too long");
	}
	
	
	static string _comp(string s, bool alwaysCopy)
	{
		if(!s.length)
			return string();
		size_t x;
		x = s.smallestCharTypeForAll();
		if(x == (s._len & TYPE_MASK))
		{
			if(alwaysCopy)
			{
				// Can't call s.dup - string.dup calls this.
				//if(s.length)
				{
					switch(x)
					{
						case TYPE_UTF8:
							s._cptr = s._cptr[0 .. s.length].dup.ptr;
							break;
						case TYPE_UTF16:
							s._wptr = s._wptr[0 .. s.length].dup.ptr;
							break;
						case TYPE_UTF32:
							s._dptr = s._dptr[0 .. s.length].dup.ptr;
							break;
						default:
							assert(0);
					}
				}
				/+else
				{
					s = string();
				}+/
			}
			return s;
		}
		assert(x < (s._len & TYPE_MASK));
		size_t iw;
		switch(x)
		{
			case TYPE_UTF32:
				assert(0); // Can never compact to the biggest size.
				return s;
			case TYPE_UTF16:
				{
					wchar[] ws;
					ws = new wchar[s.length];
					switch(s._len & TYPE_MASK)
					{
						case TYPE_UTF32:
							iw = 0;
							foreach(dchar ch; s._dptr[0 .. ws.length])
							{
								ws[iw++] = cast(wchar)ch;
							}
							assert(iw == ws.length);
							s._wptr = ws.ptr;
							s._len = ws.length;
							s._len |= TYPE_UTF16;
							break;
						default:
							assert(0);
					}
				}
				break;
			case TYPE_UTF8:
					char[] cs;
					cs = new char[s.length];
					switch(s._len & TYPE_MASK)
					{
						case TYPE_UTF32:
							iw = 0;
							foreach(dchar ch; s._dptr[0 .. cs.length])
							{
								cs[iw++] = cast(char)ch;
							}
							assert(iw == cs.length);
							s._cptr = cs.ptr;
							s._len = cs.length;
							s._len |= TYPE_UTF8;
							break;
						case TYPE_UTF16:
							iw = 0;
							foreach(wchar ch; s._wptr[0 .. cs.length])
							{
								cs[iw++] = cast(char)ch;
							}
							assert(iw == cs.length);
							s._cptr = cs.ptr;
							s._len = cs.length;
							s._len |= TYPE_UTF8;
							break;
						default:
							assert(0);
					}
				break;
			default:
				assert(!s.length);
				s._len = 0;
				s._ptr = null;
		}
		return s;
	}
	
	
	// Add this string onto s by appending.
	
	char[] _addTo(char[] s)
	{
		size_t thislength;
		thislength = this.length;
		if(!thislength)
			return s;
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				s ~= _cptr[0 .. thislength];
				break;
			case TYPE_UTF16:
				foreach(dchar dch; _wptr[0 .. thislength])
				{
					std.utf.encode(s, dch);
				}
				break;
			case TYPE_UTF32:
				foreach(dchar dch; _dptr[0 .. thislength])
				{
					std.utf.encode(s, dch);
				}
				break;
			default: ;
		}
		return s;
	}
	
	
	wchar[] _addTo(wchar[] s)
	{
		size_t thislength;
		thislength = this.length;
		if(!thislength)
			return s;
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				foreach(dchar dch; _cptr[0 .. thislength])
				{
					std.utf.encode(s, dch);
				}
				break;
			case TYPE_UTF16:
				s ~= _wptr[0 .. thislength];
				break;
			case TYPE_UTF32:
				foreach(dchar dch; _dptr[0 .. thislength])
				{
					std.utf.encode(s, dch);
				}
				break;
			default: ;
		}
		return s;
	}
	
	
	dchar[] _addTo(dchar[] s)
	{
		size_t thislength;
		thislength = this.length;
		if(!thislength)
			return s;
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				foreach(dchar dch; _cptr[0 .. thislength])
				{
					std.utf.encode(s, dch);
				}
				break;
			case TYPE_UTF16:
				foreach(dchar dch; _wptr[0 .. thislength])
				{
					std.utf.encode(s, dch);
				}
				break;
			case TYPE_UTF32:
				s ~= _dptr[0 .. thislength];
				break;
			default: ;
		}
		return s;
	}
	
	
	int _scmp(char[] s2,  bool ignoreCase, bool isASCII)
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				if(isASCII)
					return _TCmp!(char, char, false).compare(_cptr[0 .. this.length], s2, ignoreCase);
				return _TCmp!(char, char, true).compare(_cptr[0 .. this.length], s2, ignoreCase);
			case TYPE_UTF16:
				if(isASCII)
					return _TCmp!(wchar, char, false).compare(_wptr[0 .. this.length], s2, ignoreCase);
				return _TCmp!(wchar, char, true).compare(_wptr[0 .. this.length], s2, ignoreCase);
			case TYPE_UTF32:
				if(isASCII)
					return _TCmp!(dchar, char, false).compare(_dptr[0 .. this.length], s2, ignoreCase);
				return _TCmp!(dchar, char, true).compare(_dptr[0 .. this.length], s2, ignoreCase);
			default:
				assert(!_len);
				if(!s2.length)
					return 0;
				return -1;
		}
	}
	
	int _scmp(wchar[] s2,  bool ignoreCase, bool isBMP)
	{
		switch(_len & TYPE_MASK)
		{
			case TYPE_UTF8:
				if(isBMP)
					return _TCmp!(char, wchar, false).compare(_cptr[0 .. this.length], s2, ignoreCase);
				return _TCmp!(char, wchar, true).compare(_cptr[0 .. this.length], s2, ignoreCase);
			case TYPE_UTF16:
				if(isBMP)
					return _TCmp!(wchar, wchar, false).compare(_wptr[0 .. this.length], s2, ignoreCase);
				return _TCmp!(wchar, wchar, true).compare(_wptr[0 .. this.length], s2, ignoreCase);
			case TYPE_UTF32:
				if(isBMP)
					return _TCmp!(dchar, wchar, false).compare(_dptr[0 .. this.length], s2, ignoreCase);
				return _TCmp!(dchar, wchar, true).compare(_dptr[0 .. this.length], s2, ignoreCase);
			default:
				assert(!_len);
				if(!s2.length)
					return 0;
				return -1;
		}
	}
}

static assert(string.sizeof == size_t.sizeof * 2);


///
class StringException: Exception
{
	///
	this(char[] s)
	{
		super(s);
	}
	
	/// ditto
	this(string s)
	{
		super(s.toString());
	}
}


///
bool isAlphaNumericDiacritic(dchar ch)
{
	return ch >= '\u0300' && ch <= '\u036F';
}


///
bool isSymbolDiacritic(dchar ch)
{
	return ch >= '\u20D0' && ch <= '\u20FF';
}


/// Added to version 4.1 of the Unicode Standard.
bool isSupplimentDiacritic(dchar ch)
{
	return ch >= '\u1DC0' && ch <= '\u1DFF';
}


/// A diacritical mark, or accent mark, combining character.
/// Returns: true if isAlphaNumericDiacritic, isSymbolDiacritic or isSupplimentDiacritic.
bool isDiacritic(dchar ch)
{
	return isAlphaNumericDiacritic(ch) || isSymbolDiacritic(ch) || isSupplimentDiacritic(ch);
}


/// Half mark combining character.
bool isHalfMark(dchar ch)
{
	return ch >= '\uFE20' && ch <= '\uFE2F';
}


/// Includes all of the above diacritics and half marks.
bool isCombiningCharacter(dchar ch)
{
	return isDiacritic(ch) || isHalfMark(ch);
}


private:

template _TFind(TStr)
{
	int find(string s1, TStr s2, bool ignoreCase)
	{
		if(!s2.length)
			return 0;
		if(!s1.length)
			return -1;
		
		size_t psz;
		string ts;
		int i, max;
		
		max = s1.length - s2.length + 1;
		ts._ptr = s1._ptr;
		ts._len = s2.length | (s1._len & string.TYPE_MASK);
		switch(s1._len & string.TYPE_MASK)
		{
			case string.TYPE_UTF32: psz = dchar.sizeof; break;
			case string.TYPE_UTF16: psz = wchar.sizeof; break;
			case string.TYPE_UTF8: psz = char.sizeof; break;
			default: assert(0);
		}
		for(i = 0; i < max; i++)
		{
			if(!ts.compare(s2, ignoreCase))
				return i;
			ts._ptr += psz;
		}
		
		return -1;
	}
}


// T1 never UTF converts.
template _TCmp(T1, T2, bool UTF_CONVERT_T2)
{
	dchar nextc(T, bool UTF_CONVERT)(T[] s, inout size_t idx)
	{
		static if(is(T == char) || is(T == wchar) || is(T == dchar))
		{
			static if(UTF_CONVERT)
			{
				return decode(s, idx);
			}
			else
			{
				return cast(dchar)s[idx++];
			}
		}
		else
		{
			static assert(0);
		}
	}
	
	
	int compare(T1[] s1, T2[] s2, bool ignoreCase)
	{
		size_t max;
		max = s1.length;
		if(s2.length < max)
		{
			if(!s2.length)
				return 1;
			max = s2.length;
		}
		if(!max)
		{
			if(!s2.length)
				return 0;
			return -1;
		}
		size_t iw = 0, s1i = 0, s2i = 0;
		if(ignoreCase)
		{
			for(;;)
			{
				dchar ch1, ch2, tch1, tch2;
				tch1 = ch1 = nextc!(T1, false)(s1, s1i);
				tch2 = ch2 = nextc!(T2, UTF_CONVERT_T2)(s2, s2i);
				if(tch1 >= 'A' && tch1 <= 'Z')
					tch1 = cast(dchar)'a' + (tch1 - 'A');
				if(tch2 >= 'A' && tch2 <= 'Z')
					tch2 = cast(dchar)'a' + (tch2 - 'A');
				if(tch1 != tch2)
					return ch1 - ch2;
				if(++iw == max)
					break;
			}
		}
		else
		{
			for(;;)
			{
				dchar ch1, ch2;
				ch1 = nextc!(T1, false)(s1, s1i);
				ch2 = nextc!(T2, UTF_CONVERT_T2)(s2, s2i);
				if(ch1 != ch2)
					return ch1 - ch2;
				if(++iw == max)
					break;
			}
		}
		//return cast(int)s1.length - cast(int)s2.length;
		return (s1.length == s2.length) ? 0 : (s1.length > s2.length) ? 1 : -1;
	}
}


version = STRING_ALLOW_FOREACH_MODIFY;

template _Tapply(bool INDEX)
{
	static if(INDEX)
		alias int delegate(inout size_t, inout dchar) DgType;
	else
		alias int delegate(inout dchar) DgType;
	
	
	int each(inout string s, DgType dg)
	{
		size_t iw = 0, len;
		int result = 0;
		len = s.length;
		check_type:
		switch(s._len & string.TYPE_MASK)
		{
			case string.TYPE_UTF8:
				for(; iw < len; iw++)
				{
					size_t dgi;
					dchar dgch;
					dgi = iw;
					dgch = cast(dchar)s._cptr[iw];
					static if(INDEX)
						result = dg(dgi, dgch);
					else
						result = dg(dgch);
					version(STRING_ALLOW_FOREACH_MODIFY)
					{
						if(dgch != cast(dchar)s._cptr[iw])
						{
							s[iw] = dgch; // May cause reallocation.
							if(result)
								break;
							goto check_type;
						}
					}
					else
					{
						assert(dgch == cast(dchar)s._cptr[iw]);
					}
					if(result)
						break;
				}
				break;
			case string.TYPE_UTF16:
				for(; iw < len; iw++)
				{
					size_t dgi;
					dchar dgch;
					dgi = iw;
					dgch = cast(dchar)s._wptr[iw];
					static if(INDEX)
						result = dg(dgi, dgch);
					else
						result = dg(dgch);
					version(STRING_ALLOW_FOREACH_MODIFY)
					{
						if(dgch != cast(dchar)s._wptr[iw])
						{
							s[iw] = dgch; // May cause reallocation.
							if(result)
								break;
							goto check_type;
						}
					}
					else
					{
						assert(dgch == cast(dchar)s._wptr[iw]);
					}
					if(result)
						break;
				}
				break;
			case string.TYPE_UTF32:
				for(; iw < len; iw++)
				{
					size_t dgi;
					dchar dgch;
					dgi = iw;
					dgch = cast(dchar)s._dptr[iw];
					static if(INDEX)
						result = dg(dgi, dgch);
					else
						result = dg(dgch);
					version(STRING_ALLOW_FOREACH_MODIFY)
					{
						if(dgch != cast(dchar)s._dptr[iw])
						{
							s[iw] = dgch; // May cause reallocation.
							if(result)
								break;
							goto check_type;
						}
					}
					else
					{
						assert(dgch == cast(dchar)s._dptr[iw]);
					}
					if(result)
						break;
				}
				break;
			default: ;
		}
		return result;
	}
}


template _TCat(bool COPY)
{
	string concat(string s1, string s2)
	{
		size_t newlen;
		newlen = s1.length + s2.length;
		
		if(newlen > string.MAX_LENGTH || newlen < s1.length || newlen < s2.length)
			string.errortoolong();
		
		string result;
		
		if((s1._len & string.TYPE_MASK) == (s2._len & string.TYPE_MASK))
		{
			switch(s1._len & string.TYPE_MASK)
			{
				case string.TYPE_UTF8:
					{
						char[] cs;
						cs = array!(char).join(s1._cptr[0 .. s1.length], s2._cptr[0 .. s2.length]);
						result._cptr = cs.ptr;
						result._len = cs.length;
						result._len |= string.TYPE_UTF8;
					}
					break;
				case string.TYPE_UTF16:
					{
						wchar[] ws;
						ws = array!(wchar).join(s1._wptr[0 .. s1.length], s2._wptr[0 .. s2.length]);
						result._wptr = ws.ptr;
						result._len = ws.length;
						result._len |= string.TYPE_UTF16;
					}
					break;
				case string.TYPE_UTF32:
					{
						dchar[] ds;
						ds = array!(dchar).join(s1._dptr[0 .. s1.length], s2._dptr[0 .. s2.length]);
						result._dptr = ds.ptr;
						result._len = ds.length;
						result._len |= string.TYPE_UTF32;
					}
					break;
				default: ; // Valid; null strings.
			}
		}
		else if((s1._len & string.TYPE_MASK) > (s2._len & string.TYPE_MASK))
		{
			switch(s1._len & string.TYPE_MASK)
			{
				case string.TYPE_UTF16:
					{
						wchar[] ws;
						ws = s2._addTo(array!(wchar).get(s1._wptr[0 .. s1.length]));
						result._wptr = ws.ptr;
						result._len = ws.length;
						result._len |= string.TYPE_UTF16;
					}
					break;
				case string.TYPE_UTF32:
					{
						dchar[] ds;
						ds = s2._addTo(array!(dchar).get(s1._dptr[0 .. s1.length]));
						result._dptr = ds.ptr;
						result._len = ds.length;
						result._len |= string.TYPE_UTF32;
					}
					break;
				default:
					assert(0);
			}
		}
		else //if((s1._len & string.TYPE_MASK) < (s2._len & string.TYPE_MASK))
		{
			switch(s2._len & string.TYPE_MASK) // Note: s2's type.
			{
				case string.TYPE_UTF16:
					{
						wchar[] ws;
						ws = array!(wchar).join(s1, s2._wptr[0 .. s2.length]);
						result._wptr = ws.ptr;
						result._len = ws.length;
						result._len |= string.TYPE_UTF16;
					}
					break;
				case string.TYPE_UTF32:
					{
						dchar[] ds;
						ds = array!(dchar).join(s1, s2._dptr[0 .. s2.length]);
						result._dptr = ds.ptr;
						result._len = ds.length;
						result._len |= string.TYPE_UTF32;
					}
					break;
				default:
					assert(0);
			}
		}
		
		assert(newlen == result.length);
		return result;
	}
	
	
	// Copies or not based on COPY.
	template array(T)
	{
		T[] join(T[] s1, T[] s2)
		{
			static if(COPY)
				return s1 ~ s2;
			else
				return s1 ~= s2;
		}
		
		
		T[] join(string s1, T[] s2)
		{
			T[] result;
			result = s1._addTo(cast(T[])null); // Copies.
			result ~= s2;
			return result;
		}
		
		
		T[] get(T[] s)
		{
			static if(COPY)
				return s.dup;
			else
				return s;
		}
	}
}


debug(TEST_MAIN)
{
	void main()
	{
		printf("Exiting main.\n");
	}
}


void main () { }

unittest
{
	string s = string("foo"c);
	string t = string("Oh noes!"w);
	string u = string("% on a plne!"d);
	string v = string(string(string("WAaah! D:"c)[0..2].toUTF16() ~ "arrr! D:"w).toUTF32()); // make some chaos thingie

	assert(s.type() == typeid(typeof("foo"c)));
	assert(s.type() != typeid(typeof("Oh noes!"w)));
	assert(t.type() != typeid(typeof("% on a plne!"d)));
	assert(v.type() == u.type() );

	assert(s.startsWith("f"c));
	assert(s.startsWith("fo"w));
	assert(s.startsWith("foo"c));
	assert(!s.startsWith("fooo"c));
	assert(!s.startsWith("F"c));
	assert(s.startsWith("F"c, true));
	assert(!s.startsWith("E"c, true));
	assert(s.endsWith("o"c));
	assert(s.endsWith("oo"d));
	assert(s.endsWith("foo"c));
	assert(!s.endsWith("fooo"c));
	assert(!s.endsWith("ooo"c));
	assert(s.endsWith("O"c, true));
	assert(!s.endsWith("P"c, true));
	assert((s.dup ~ t.dup ~ u.dup ~ v.dup).startsWith(s));
	assert((s.dup ~ t.dup ~ u.dup ~ v.dup).endsWith(v));

	int i;
	s = string("The quick brown fox jumped over the lazy dog."w);
	i = s.find("Lazy"c, true);
	assert(-1 != i);
	assert(s[i .. i + 4] == "lazy"c);
	i = s.find("Lazy"c, false);
	assert(-1 == i);
	i = s.find("."c, true);
	assert(-1 != i);
	i = s.find("dog."c, true);
	assert(-1 != i);
	i = s.find(string("jumped"d), false);
	assert(-1 != i);
	
	wchar[] ws = "Arrrrr!";
	
	assert(!(s == "oof"c));
	assert(!(t == "oh nes!"w));
	assert(!(t == u));
	assert(!(t == s));
	assert(!(s == u));
	assert(string("foo"c) == s);
	assert(s == "foo"c);
	assert(ws == string(ws));
	assert(!(ws > string(ws)));
	assert(!(ws < string(ws)));
	assert(ws == string(ws)[0 .. ws.length]);
	assert(!(ws > string(ws)[0 .. ws.length]));
	assert(!(ws < string(ws)[0 .. ws.length]));
	assert(ws == string(ws).toUTF16());
	assert(ws == string(string(ws).toString()).toUTF16);
	assert(ws <= (string(ws) ~ ws));
	assert(ws >= string(ws)[0..ws.length / 2]);
	
	string s2;
	s2 = s.dup;
	assert(s.type != s2.type); // Compacted.
	assert(s == s2); // Same value.
	
	foreach ( uint i, inout dchar ch; u ) {
		t[i] = ch;
		s[s.length - i] = ch;
	}

	u ~= "\u0164" ~ "\u0020" ~ "\u9876"; // just to be funny and prevent from compacting ;)
	
	assert( t.dup().type( ) == t.type() );
	u.compact();
	v.compact();
	assert( s.type( ) != u.type( ) );
	
	assert( s.length < s.MAX_LENGTH );
	
	s = string();
	t.cleanup();
	u = string();
	v = string();

	assert(s.length == 0);
	assert(s.length == t.length);
	assert(t.length == 0);
	assert(u.length == 0);
	assert(v.length == 0);
}