using UnityEngine;
using System.Collections.Generic;

// For fast string lookups by prefix.
public class Index
{
    // Stores this sorted list in a manner for quick access (which a Trie was not).
    public Index(string[] entries, int mininumWordLength)
    {
        List<char> bufferTemp = new List<char>(8000); // Reserve space to avoid extra allocs

        // So we can quickly jump to something based on the first letter.
        charToOffset = new Dictionary<char, short>();
        charToEntryIndexStart = new Dictionary<char, int>();

        // Buffer is organized like this for each letter:
        // [chars in common][offset to next][series of unique chars]
        // Index into entries is implied by how far we've come.

        string previousString = string.Empty;
        List<string> curatedEntries = new List<string>(entries.Length);
        for (int i = 0; i < entries.Length; i++)
        {
            if (entries[i].Length >= mininumWordLength)
            {
                Debug.Assert(entries[i] == entries[i].ToLowerInvariant());
                string name = entries[i];

                if (!charToOffset.ContainsKey(name[0]))
                {
                    Debug.Assert(CharsInCommon(previousString, name) == 0); // Everything should always be lower case.
                    charToOffset[name[0]] = (short)bufferTemp.Count;
                    charToEntryIndexStart[name[0]] = curatedEntries.Count;
                }

                short charsInCommon = CharsInCommon(previousString, name);
                bufferTemp.Add((char)charsInCommon);
                bufferTemp.Add((char)(name.Length - charsInCommon));
                bufferTemp.AddRange(name.Substring(charsInCommon));

                previousString = name;
                curatedEntries.Add(entries[i]);
            }
        }

        Debug.Log("s is " + charToOffset['s']);
        Debug.Log("t is " + charToOffset['t']);

        buffer = bufferTemp.ToArray();
        this.entries = curatedEntries.ToArray();
    }

    private char[] buffer;
    private Dictionary<char, short> charToOffset;
    private Dictionary<char, int> charToEntryIndexStart;
    private string[] entries;
    
    private char[] workerCharInCommon = new char[100];
    public void GetResultsFromPrefix(string prefix, List<string> results)
    {
        results.Clear();
        int maxLengthToSearch = prefix.Length;
        short sOffset;
        // Jump to the right spot
        if (prefix.Length == 0)
        {
            // Just put all in:
            results.AddRange(entries);
        }
        else if (charToOffset.TryGetValue(char.ToLowerInvariant(prefix[0]), out sOffset))
        {
            int offset = sOffset;
            int pokeIndex = charToEntryIndexStart[char.ToLowerInvariant(prefix[0])];

            while (offset < buffer.Length)
            {
                int charsInCommon = buffer[offset++];
                int nextOffsetOffset = buffer[offset++];
                int nextOffset = offset + nextOffsetOffset;

                // Copy chars to our worker
                // We can probably optimize this out, but it means it easier if we have chars in common
                // so we don't need to backtrack
                // REVIEW OPTIMIZE: Never bother copying more than maxLengthToSearch chars
                int maxToCopyOver = maxLengthToSearch - charsInCommon; // Yes, could be negative.
                for (int i = 0; i < maxToCopyOver; i++)
                {
                    workerCharInCommon[charsInCommon + i] = buffer[offset + i];
                }

                // OPTIMIZE: Don't need to search up to chars in common? Hmm, maybe not
                int maxLength = Mathf.Min(maxLengthToSearch, nextOffsetOffset + charsInCommon);
                int charPos = 0;
                for (; (charPos < maxLength) && (char.ToLowerInvariant(prefix[charPos]) == workerCharInCommon[charPos]); charPos++)
                {
                }
                if (charPos >= maxLength)
                {
                    // It's a match!
                    results.Add(entries[pokeIndex]);
                }
                else if (charPos == 0)
                {
                    // Break out if zero matches (means we're no longer in the right letter)
                    break;
                }

                pokeIndex++;
                offset = nextOffset;
            }
        }
    }

    private short CharsInCommon(string previous, string now)
    {
        short lengths = (short)Mathf.Min(previous.Length, now.Length);
        for (short i = 0; i < lengths; i++)
        {
            if (previous[i] != now[i])
            {
                return i;
            }
        }
        return lengths;
    }
}