Sqids.cs

namespace Sqids;

public class SqidsOptions
{
	public string Alphabet { get; set; } = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
	public HashSet<string> BlockList { get; set; } = new() { /* TODO */ };
	public int MinLength { get; set; } = 10;
}

public class SqidsGenerator
{
	private const int _minAlphabetLength = 5;
	private readonly SqidsOptions _options;

	public const int MinValue = 0;
	public const int MaxValue = int.MaxValue;

	public SqidsGenerator() : this(new()) { }

	public SqidsGenerator(SqidsOptions options)
	{
		if (options.Alphabet.Length < _minAlphabetLength)
		{
			throw new ArgumentException("The alphabet must contain at least 5 characters.");
		}

		if (options.Alphabet.Distinct().Count() != options.Alphabet.Length)
		{
			throw new ArgumentException("The alphabet must not contain duplicate characters.");
		}

		if (options.MinLength < MinValue || options.MinLength > options.Alphabet.Length)
		{
			throw new ArgumentException($"The minimum length must be between {MinValue} and {options.Alphabet.Length}.");
		}

		var filteredBlockList = new HashSet<string>();
		foreach (string word in options.BlockList)
		{
			if (word.Length >= 3)
			{
				var intersection = word.Intersect(options.Alphabet);
				if (intersection.Count() == word.Length)
				{
					filteredBlockList.Add(word.ToLower());
				}
			}
		}

		Span<char> shuffledAlphabet = stackalloc char[options.Alphabet.Length];
		options.Alphabet.AsSpan().CopyTo(shuffledAlphabet);
		ConsistentShuffle(shuffledAlphabet);

		options.Alphabet = shuffledAlphabet.ToString();

		options.BlockList = filteredBlockList;
		_options = options;
	}

	public string Encode(params int[] numbers)
	{
		if (numbers.Length == 0)
		{
			return string.Empty;
		}

		if (numbers.Any(n => n < MinValue || n > MaxValue))
		{
			throw new ArgumentException($"Encoding supports numbers between '{MinValue}' and '{MaxValue}'.");
		}

		return EncodeNumbers(numbers);
	}

	public int[] Decode(ReadOnlySpan<char> id)
	{
		if (id.IsEmpty)
		{
			return Array.Empty<int>();
		}

		if (id.Length < _options.MinLength) // TODO: This wasn't in the reference implementation — but it makes sense to me?
		{
			return Array.Empty<int>();
		}

		foreach (char character in id)
		{
			if (!_options.Alphabet.Contains(character))
			{
				return Array.Empty<int>();
			}
		}

		var alphabet = _options.Alphabet.AsSpan();

		char prefix = id[0];
		int offset = alphabet.IndexOf(prefix);

		Span<char> alphabetTemp = stackalloc char[_options.Alphabet.Length]; // ? should be stacklloc or not?
		alphabet[offset..].CopyTo(alphabetTemp[..^offset]);
		alphabet[..offset].CopyTo(alphabetTemp[^offset..]);

		char partition = alphabetTemp[1];
		alphabetTemp = alphabetTemp[2..];
		id = id[1..];

		int partitionIndex = id.IndexOf(partition);
		if (partitionIndex > 0 && partitionIndex < id.Length - 1)
		{
			id = id[(partitionIndex + 1)..];
			ConsistentShuffle(alphabetTemp);
		}

		var result = new List<int>();
		while (id.Length > 0)
		{
			char separator = alphabetTemp[^1];

			string[] chunks = id.ToString().Split(separator); // TODO: span

			if (chunks.Length > 0)
			{
				var alphabetWithoutSeparator = alphabetTemp[..^1]; // NOTE: Exclude the last character

				var decodedNumber = ToNumber(chunks[0], alphabetWithoutSeparator);
				result.Add(decodedNumber);

				if (chunks.Length > 1)
				{
					ConsistentShuffle(alphabetTemp);
				}
			}

			id = string.Join(separator, chunks[1..]); // TODO: span
		}

		return result.ToArray();
	}

	// Private Helpers:
	private string EncodeNumbers(int[] numbers, bool partitioned = false)
	{
		var alphabet = _options.Alphabet.AsSpan();

		int offset = (numbers.Length + (numbers.Select((n, i) =>
			_options.Alphabet[n % _options.Alphabet.Length] + i).Sum())) % _options.Alphabet.Length;

		Span<char> alphabetTemp = stackalloc char[alphabet.Length]; // todo: should be stacklloc or not?
		alphabet[offset..].CopyTo(alphabetTemp[..^offset]);
		alphabet[..offset].CopyTo(alphabetTemp[^offset..]);

		char prefix = alphabetTemp[0];
		char partition = alphabetTemp[1];
		alphabetTemp = alphabetTemp[2..];

		var builder = new StringBuilder(); // todo: pool a la Hashids.net?
		builder.Append(prefix);

		for (int i = 0; i < numbers.Length; i++)
		{
			int number = numbers[i];

			var alphabetWithoutSeparator = alphabetTemp[..^1];
			string encodedNumber = ToId(number, alphabetWithoutSeparator);
			builder.Append(encodedNumber);

			if (i < numbers.Length - 1) // NOTE: If not the last
			{
				char separator = alphabetTemp[^1]; // NOTE: Exclude the last character

				if (partitioned && i == 0)
				{
					builder.Append(partition);
				}
				else
				{
					builder.Append(separator);
				}

				ConsistentShuffle(alphabetTemp);
			}
		}

		string result = builder.ToString(); // todo: preferably don't `ToString()` this early

		if (result.Length < _options.MinLength)
		{
			if (!partitioned)
			{
				var newNumbers = new int[numbers.Length + 1];
				newNumbers[0] = 0;
				numbers.CopyTo(newNumbers, 1);
				result = EncodeNumbers(newNumbers, partitioned: true);
			}

			if (result.Length < _options.MinLength)
			{
				var LeftToMeetMinLength = _options.MinLength - result.Length;
				var paddingFromAlphabet = alphabetTemp[..LeftToMeetMinLength];
				builder.Insert(1, paddingFromAlphabet);
				result = builder.ToString();
			}
		}

		if (IsBlockedId(result))
		{
			int[] newNumbers = numbers;
			if (partitioned)
			{
				if (numbers[0] + 1 > MaxValue)
				{
					throw new ArgumentOutOfRangeException("Ran out of range checking against the blocklist.");
				}
				else
				{
					newNumbers[0] += 1;
				}
			}
			else
			{
				newNumbers = new int[numbers.Length + 1];
				newNumbers[0] = 0;
				numbers.CopyTo(newNumbers, 1);
			}

			result = EncodeNumbers(newNumbers, true);
		}

		return result;
	}

	private bool IsBlockedId(string id)
	{
		// return _options.BlockList
		// 	.Where(word => word.Length <= id.Length)
		// 	.Any(word =>
		// 		((id.Length <= 3 || word.Length <= 3) && id.Equals(word, StringComparison.OrdinalIgnoreCase)) ||

		// 		id.Contains(word, StringComparison.OrdinalIgnoreCase)
		// 	);
		foreach (string word in _options.BlockList)
		{
			if (word.Length > id.Length)
				continue;

			if ((id.Length <= 3 || word.Length <= 3) && id.Equals(word, StringComparison.OrdinalIgnoreCase))
			{
				return true;
			}
			else if (word.Any(char.IsDigit) && (id.StartsWith(word, StringComparison.OrdinalIgnoreCase) || id.EndsWith(word, StringComparison.OrdinalIgnoreCase)))
			{
				return true;
			}
			else if (id.Contains(word, StringComparison.OrdinalIgnoreCase))
			{
				return true;
			}
		}

		return false;
	}

	/// <summary>
	/// Shuffles a span of characters in place.
	/// The shuffle produces consistent results.
	/// </summary>
	private static void ConsistentShuffle(Span<char> alphabet)
	{
		for (int i = 0, j = alphabet.Length - 1; j > 0; i++, j--)
		{
			int r = (i * j + alphabet[i] + alphabet[j]) % alphabet.Length;
			(alphabet[i], alphabet[r]) = (alphabet[r], alphabet[i]);
		}
	}

	private static string ToId(int num, ReadOnlySpan<char> alphabet)
	{
		var id = new StringBuilder();
		int result = num;

		do
		{
			id.Insert(0, alphabet[result % alphabet.Length]);
			result = result / alphabet.Length;
		} while (result > 0);

		return id.ToString(); // todo: don't create string possibly?
	}

	private static int ToNumber(string id, ReadOnlySpan<char> alphabet)
	{
		int result = 0;
		for (int i = 0; i < id.Length; i++)
		{
			char character = id[i];
			result = result * alphabet.Length + alphabet.IndexOf(character);
		}
		return result;
	}
}