String<T>

// System.String — System.Core (decompiled from Larva HIR)

import System.Runtime.InteropServices;

into namespace System
{
	public final class String<T : [u8, u16, u32]> : IHashable<String<T>>, IComparable<String<T>>, IToString
	{
		/// Up to this many units, a loop copies or compares faster than a call into the runtime.
		const i32 Short = 24;

		/// The hash, once computed (0: not yet).
		u64 hash;

		/// The code units, kept in the object itself (one allocation per string).
		fixed T[] units;

		/// `count` units from `from[at]` into `to[offset]` (the ranges already checked): one copy in memory.
		static Move(String<T> to, i32 offset, String<T> from, i32 at, i32 count)
		{
			if (count <= 24)
			{
				loop (i32 i = 0..count)
					to.units[offset + i] = from.units[at + i];
			}
			else
			{
				unsafe
				{
					Memory.Copy((u8*)&to.units[offset], (u8*)&from.units[at], (i64)count * (i64)sizeof(T));
				}
			}
		}

		/// `count` units from the array `from[at]` into `to[offset]` (the ranges already checked).
		static MoveIn(String<T> to, i32 offset, T[] from, i32 at, i32 count)
		{
			if (count <= 24)
			{
				loop (i32 i = 0..count)
					to.units[offset + i] = from[at + i];
			}
			else
			{
				unsafe
				{
					Memory.Copy((u8*)&to.units[offset], (u8*)&from[at], (i64)count * (i64)sizeof(T));
				}
			}
		}

		/// Whether `part` is at `start` (the range already checked): a plain loop, small enough to inline where it is asked at every position.
		MatchesAt(i32 start, String<T> part) : bool
		{
			i32 count = part.units.Length;
			loop (i32 i = 0..count)
			{
				if (units[start + i] != part.units[i])
					return false;
			}
			return true;
		}

		static IsSpace(T unit) : bool => unit == (T)32 || unit == (T)9 || unit == (T)10 || unit == (T)13;

		static Empty() : String<T> => new String<T>(0);

		/// `length` units from `start`, the range already checked.
		Slice(i32 start, i32 length) : String<T>
		{
			String<T> copy = new String<T>(length);
			Move(copy, 0, this, start, length);
			return copy;
		}

		internal:
			/// The decimal digits of `magnitude`, after a '-' when `negative`, written straight into a new string (what the
			/// integers' ToString gives: no array of digits first).
			static Decimal(u64 magnitude, bool negative) : str
			{
				i32 count = 1;
				u64 rest = magnitude;
				loop (rest >= 10)
				{
					rest = rest / 10;
					count++;
				}
				i32 length = negative ? count + 1 : count;
				str text = new str(length);
				if (negative)
					text.units[0] = 45;
				i32 at = length;
				do
				{
					at--;
					text.units[at] = (u8)(48 + magnitude % 10);
					magnitude = magnitude / 10;
				}
				loop (magnitude > 0);
				return text;
			}

		public:
			/// A string of `length` zero units, filled by the method that made it.
			new(i32 length) : fixed(length)
			{
			}

			/// A string of a copy of the code units.
			new(T[] codeUnits) : fixed(codeUnits.Length)
			{
				MoveIn(this, 0, codeUnits, 0, codeUnits.Length);
			}

			/// A string of a copy of `count` code units of `codeUnits` from `start`.
			new(T[] codeUnits, i32 start, i32 count) : fixed(count < 0 ? 0 : count)
			{
				if (start < 0 || count < 0 || start > codeUnits.Length - count)
					throw new ArgumentError("String: the range is outside the array");
				MoveIn(this, 0, codeUnits, start, count);
			}

			/// The code unit at `index`.
			At(i32 index) : T => units[index];

			/// The same code units as `other`.
			Equals(String<T> other) : bool
			{
				i32 count = units.Length;
				if (other.units.Length != count)
					return false;
				if (count == 0 || hash != 0 && other.hash != 0 && hash != other.hash)
					return count == 0;
				if (count <= 24)
				{
					loop (i32 i = 0..count)
					{
						if (units[i] != other.units[i])
							return false;
					}
					return true;
				}
				unsafe
				{
					return Memory.Compare((u8*)&units[0], (u8*)&other.units[0], (i64)count * (i64)sizeof(T)) == 0;
				}
			}

			/// FNV-1a over the code units (computed once: strings do not change).
			override Hash() : u64
			{
				if (hash != 0)
					return hash;
				u64 h = 14695981039346656037;
				loop (i32 i = 0..units.Length)
				{
					h = h ^ (u64)units[i];
					h = h * 1099511628211;
				}
				hash = h | 1;
				return hash;
			}

			/// Code unit order: -1, 0 or 1 (in UTF-8 and UTF-32 that is code point order).
			CompareTo(String<T> other) : i32
			{
				i32 mine = units.Length;
				i32 theirs = other.units.Length;
				i32 common = mine < theirs ? mine : theirs;
				loop (i32 i = 0..common)
				{
					if (units[i] != other.units[i])
						return units[i] < other.units[i] ? -1 : 1;
				}
				return mine < theirs ? -1 : mine > theirs ? 1 : 0;
			}

			/// The text in UTF-8.
			override ToString() : str => ToUtf8();

			/// The text from `start` to the end.
			Substring(i32 start) : String<T> => Substring(start, units.Length - start);

			/// `length` code units from `start`.
			Substring(i32 start, i32 length) : String<T>
			{
				if (start < 0 || length < 0 || start > units.Length - length)
					throw new ArgumentError("Substring: the range is outside the string");
				return Slice(start, length);
			}

			/// Where `unit` first appears, or -1.
			IndexOf(T unit) : i32
			{
				loop (i32 i = 0..units.Length)
				{
					if (units[i] == unit)
						return i;
				}
				return -1;
			}

			/// Where `part` first appears, or -1.
			IndexOf(String<T> part) : i32
			{
				loop (i32 i = 0..units.Length - part.units.Length + 1)
				{
					if (MatchesAt(i, part))
						return i;
				}
				return -1;
			}

			Contains(String<T> part) : bool => IndexOf(part) >= 0;

			StartsWith(String<T> prefix) : bool => prefix.units.Length <= units.Length && MatchesAt(0, prefix);

			EndsWith(String<T> suffix) : bool
			{
				return suffix.units.Length <= units.Length && MatchesAt(units.Length - suffix.units.Length, suffix);
			}

			/// ASCII letters in upper case.
			ToUpper() : String<T>
			{
				String<T> copy = new String<T>(units.Length);
				loop (i32 i = 0..units.Length)
				{
					T unit = units[i];
					copy.units[i] = unit >= (T)97 && unit <= (T)122 ? unit - (T)32 : unit;
				}
				return copy;
			}

			/// ASCII letters in lower case.
			ToLower() : String<T>
			{
				String<T> copy = new String<T>(units.Length);
				loop (i32 i = 0..units.Length)
				{
					T unit = units[i];
					copy.units[i] = unit >= (T)65 && unit <= (T)90 ? unit + (T)32 : unit;
				}
				return copy;
			}

			/// Without the spaces, tabs and line breaks at both ends.
			Trim() : String<T>
			{
				i32 start = 0;
				i32 end = units.Length;
				loop (start < end && IsSpace(units[start]))
					start++;
				loop (end > start && IsSpace(units[end - 1]))
					end--;
				return start == 0 && end == units.Length ? this : Slice(start, end - start);
			}

			/// The pieces between each `separator`.
			Split(T separator) : List<String<T>>
			{
				List<String<T>> pieces = new List<String<T>>(Count(separator) + 1);
				i32 start = 0;
				loop (i32 i = 0..units.Length)
				{
					if (units[i] == separator)
					{
						pieces.Add(Slice(start, i - start));
						start = i + 1;
					}
				}
				pieces.Add(Slice(start, units.Length - start));
				return pieces;
			}

			/// Every `old` replaced by `replacement`.
			Replace(String<T> old, String<T> replacement) : String<T>
			{
				i32 width = old.units.Length;
				if (width == 0)
					return this;
				i32 found = 0;
				i32 i = 0;
				loop (i + width <= units.Length)
				{
					if (MatchesAt(i, old))
					{
						found++;
						i += width;
					}
					else
						i++;
				}
				if (found == 0)
					return this;
				i32 with = replacement.units.Length;
				String<T> result = new String<T>(units.Length + found * (with - width));
				i32 at = 0;
				i = 0;
				loop (i < units.Length)
				{
					if (i + width <= units.Length && MatchesAt(i, old))
					{
						Move(result, at, replacement, 0, with);
						at += with;
						i += width;
					}
					else
					{
						result.units[at] = units[i];
						at++;
						i++;
					}
				}
				return result;
			}

			/// `a` followed by `b` (what `a + b` does).
			static Concat(String<T> a, String<T> b) : String<T>
			{
				i32 left = a.units.Length;
				i32 right = b.units.Length;
				if (left == 0)
					return b;
				if (right == 0)
					return a;
				String<T> joined = new String<T>(left + right);
				Move(joined, 0, a, 0, left);
				Move(joined, left, b, 0, right);
				return joined;
			}

			/// The pieces with `separator` between them.
			static Join(String<T> separator, List<String<T>> pieces) : String<T>
			{
				i32 total = 0;
				loop (i32 i = 0..pieces.Count)
					total += pieces[i].units.Length;
				i32 gap = separator.units.Length;
				if (pieces.Count > 1)
					total += gap * (pieces.Count - 1);
				String<T> joined = new String<T>(total);
				i32 at = 0;
				loop (i32 i = 0..pieces.Count)
				{
					if (i > 0)
					{
						Move(joined, at, separator, 0, gap);
						at += gap;
					}
					String<T> piece = pieces[i];
					Move(joined, at, piece, 0, piece.units.Length);
					at += piece.units.Length;
				}
				return joined;
			}

			/// Where `unit` last appears, or -1.
			LastIndexOf(T unit) : i32
			{
				i32 i = units.Length - 1;
				loop (i >= 0)
				{
					if (units[i] == unit)
						return i;
					i--;
				}
				return -1;
			}

			/// At least `width` units: spaces (or `pad`) before the text.
			PadLeft(i32 width) : String<T> => PadLeft(width, (T)32);

			PadLeft(i32 width, T pad) : String<T>
			{
				if (width <= units.Length)
					return this;
				String<T> padded = new String<T>(width);
				i32 before = width - units.Length;
				loop (i32 i = 0..before)
					padded.units[i] = pad;
				Move(padded, before, this, 0, units.Length);
				return padded;
			}

			/// At least `width` units: spaces (or `pad`) after the text.
			PadRight(i32 width) : String<T> => PadRight(width, (T)32);

			PadRight(i32 width, T pad) : String<T>
			{
				if (width <= units.Length)
					return this;
				String<T> padded = new String<T>(width);
				Move(padded, 0, this, 0, units.Length);
				loop (i32 i = units.Length..width)
					padded.units[i] = pad;
				return padded;
			}

			/// The text `times` times.
			Repeat(i32 times) : String<T>
			{
				if (times <= 0)
					return Empty();
				i32 n = units.Length;
				String<T> repeated = new String<T>(n * times);
				loop (i32 t = 0..times)
					Move(repeated, t * n, this, 0, n);
				return repeated;
			}

			/// `text` put in at `index`.
			Insert(i32 index, String<T> text) : String<T> => Concat(Concat(Substring(0, index), text), Substring(index));

			/// Without `count` units from `start`.
			Remove(i32 start, i32 count) : String<T> => Concat(Substring(0, start), Substring(start + count));

			/// A copy of the code units.
			ToCharArray() : T[]
			{
				T[] copy = new T[units.Length];
				CopyTo(0, copy, 0, units.Length);
				return copy;
			}

			/// `count` code units from `start` into `target` at `at`.
			CopyTo(i32 start, T[] target, i32 at, i32 count)
			{
				if (start < 0 || count < 0 || at < 0 || start > units.Length - count || at > target.Length - count)
					throw new ArgumentError("CopyTo: the range is outside the string or the array");
				if (count <= 24)
				{
					loop (i32 i = 0..count)
						target[at + i] = units[start + i];
				}
				else
				{
					unsafe
					{
						Memory.Copy((u8*)&target[at], (u8*)&units[start], (i64)count * (i64)sizeof(T));
					}
				}
			}

			/// How many times `unit` appears.
			Count(T unit) : i32
			{
				i32 found = 0;
				loop (i32 i = 0..units.Length)
				{
					if (units[i] == unit)
						found++;
				}
				return found;
			}

			/// The pieces between each `separator` (a string).
			Split(String<T> separator) : List<String<T>>
			{
				i32 width = separator.units.Length;
				List<String<T>> pieces = new List<String<T>>();
				if (width == 0)
				{
					pieces.Add(this);
					return pieces;
				}
				i32 start = 0;
				i32 i = 0;
				loop (i + width <= units.Length)
				{
					if (MatchesAt(i, separator))
					{
						pieces.Add(Slice(start, i - start));
						i += width;
						start = i;
					}
					else
					{
						i++;
					}
				}
				pieces.Add(Slice(start, units.Length - start));
				return pieces;
			}

			/// The lines of the text (split at line feeds; a carriage return before one is dropped).
			Lines() : List<String<T>>
			{
				List<String<T>> lines = new List<String<T>>();
				i32 start = 0;
				loop (i32 i = 0..units.Length)
				{
					if (units[i] == (T)10)
					{
						i32 end = i > start && units[i - 1] == (T)13 ? i - 1 : i;
						lines.Add(Slice(start, end - start));
						start = i + 1;
					}
				}
				if (start < units.Length)
					lines.Add(Slice(start, units.Length - start));
				return lines;
			}

			/// A string of a copy of `codeUnits`.
			static FromUnits(T[] codeUnits) : String<T> => new String<T>(codeUnits);

			static IsNullOrEmpty(String<T>? text) : bool
			{
				if (text is String<T> value)
					return value.Length == 0;
				return true;
			}

			/// Ordinal order: -1, 0 or 1.
			static Compare(String<T> a, String<T> b) : i32 => a.CompareTo(b);

			/// `loop (T unit in text)`.
			Iterator() : StringIterator<T> => new StringIterator<T>(this);

			/// A copy of the code units (the string keeps its own, in place).
			Units() : T[] => ToCharArray();

			/// The Unicode code points (malformed sequences become U+FFFD).
			CodePoints() : u32[] => Unicode.Decode(Units());

			/// How many code points the text has.
			CodePointCount() : i32 => Unicode.Decode(Units()).Length;

			/// The text in UTF-8 (`str`).
			ToUtf8() : str
			{
				if (sizeof(T) == 1 && (any)this is str same)
					return same;
				return new str(Unicode.Encode<u8>(Unicode.Decode(Units())));
			}

			/// The text in UTF-16.
			ToUtf16() : String<u16>
			{
				if (sizeof(T) == 2)
				{
					String<u16> same = new String<u16>(units.Length);
					unsafe
					{
						if (units.Length > 0)
							Memory.Copy((u8*)&same.units[0], (u8*)&units[0], (i64)units.Length * 2);
					}
					return same;
				}
				return new String<u16>(Unicode.Encode<u16>(Unicode.Decode(Units())));
			}

			/// The text in UTF-32 (one unit per code point).
			ToUtf32() : String<u32> => new String<u32>(Unicode.Decode(Units()));

			/// How many code units (bytes in a str).
			i32 Length
			{
				get => units.Length;
			}

			bool IsEmpty
			{
				get => units.Length == 0;
			}
	}
}