/* 
A Hashtable stores key-value pairs and provides O(1) lookup time.
⠀
Implementation based on: https://learn.microsoft.com/en-us/previous-versions/ms379571(v=vs.80) (HashTable in C# 2.0)
Some functions are based on TMap<> as it appears in Unreal 4 & 5.
⠀
Value can be made any type by making a copy of this class and search and replacing "ValueType" with the type you want. (and deleting the ValueType dummy struct)
Note: ValueType must have a valid == operator.
After making the copy, replace HashTable types in this class with whatever you called your new class. (This is used for functions such as Append, which take in a HashTable as a parameter.)
⠀
THIS FILE IS A TEMPLATE AND WILL (PROBABLY) NOT COMPILE, SO DO NOT PUT IT IN YOUR CLASSES FOLDER.
*/
class HashTable extends Object;

// -2147483648 is used for None
`define KeyNone -2147483648

struct ValueType{};

struct Pair
{
    var int Key;
    var ValueType Value;

    structdefaultproperties
    {
        Key = `KeyNone;
    }
};

var private Array<Pair> Data;
var private const float LoadFactor;
var private int TableLength; // Number of elements
var private int LengthIndex; // Index in primes for current buffer length

var private const int Primes[303];

/* Add a new key-value pair to the table. */
public function Add(int Key, ValueType Value)
{
    local Pair p;

    if(Key == `KeyNone)
    {
        Print("Cannot use "$String(`KeyNone)$" as a key!");
        return;
    }

    if(ContainsKey(Key))
    {
        Print("Key is already in use!");
        return;
    }

    if(float(TableLength + 1) / float(Data.Length) >= LoadFactor)
    {
        Reserve(Data.Length * 2, true /* bIsBufferLength */);
    }

    p.Key = Key;
    p.Value = Value;

    Data[GetIndex(Key)] = p;
    TableLength++;
}

/* 
Remove a key-value pair from the table, by key. 
bCompact: whether to compact the buffer after removing this element
*/
public function Remove(int Key, optional bool bCompact)
{
    Data[GetIndex(Key)].Key = `KeyNone;
    TableLength--;

    if(bCompact) Compact();
}

/* 
Removes a key-value pair from the table, by key, while providing a copy of the value of the removed pair. 
bCompact: whether to compact the buffer after removing this element.
*/
public function RemoveAndCopyValue(int Key, out ValueType Value, optional bool bCompact)
{
    Value = Data[GetIndex(Key)].Value;
    Remove(Key);

    if(bCompact) Compact();
}

/* Get a value, by key. */
public function ValueType Get(int Key)
{
    return Data[GetIndex(Key)].Value;
}

/* Set a value, by key. */
public function Set(int Key, ValueType Value)
{
    if(!ContainsKey(Key))
    {
        Print("That key isn't used anywhere in the hashtable!");
        return;
    }

    Data[GetIndex(Key)].Value = Value;
}

/* Get the amount of elements in the table */
public function int Length()
{
    return TableLength;
}

/* Get the amount of slots in the table */
public function int BufferLength()
{
    return Primes[LengthIndex];
}

/* Check whether the table contains a key. */
public function bool ContainsKey(int Key)
{
    return Data[GetIndex(Key)].Key == Key;
}

// Expensive!!
// Finds a key by its associated value.
// Returns `KeyNone if no matching value was found
public function int FindKey(ValueType Value)
{
    local int i;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KeyNone) continue;
        
        if(Data[i].Value == Value) return Data[i].Key;
    }
    return `KeyNone;
}

// Expensive!!
// Returns an array of all elements
// Keep in mind that it is not guaranteed for this to be in the order you added the elements in. 
public function Array<Pair> ToArray()
{
    local int i;
    local Array<Pair> Output;
    local Pair p;

    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KeyNone) continue;

        p.Key = Data[i].Key;
        p.Value = Data[i].Value;
        Output.AddItem(p);
    }

    return Output;
}

/*
Ensure the table atleast has space for x elements without having to resize. 
bIsBufferLength: Nearest prime to NumElements will be directly used as the new length of the buffer, not how many slots are available without resizing. Used internally.
*/
public function Reserve(int NumElements, optional bool bIsBufferLength)
{
    local int MinimumLength, i;

    MinimumLength = FCeil(float(NumElements) * (1.f / LoadFactor));

    if(MinimumLength <= Data.Length) return;

    for(i = LengthIndex; i < ArrayCount(Primes); i++)
    {
        if(Primes[i] >= (bIsBufferLength ? NumElements : MinimumLength))
        {
            UpdateLength(Primes[i]);
            LengthIndex = i;
            return;
        }
    }

    Print("Failed to accommodate wanted number of elements ("$String(NumElements)$")!");
}

/* 
Removes all elements.
Slack: nearest prime to this will indicate how large the buffer will be after removing all elements
*/
public function Empty(optional int Slack = 0)
{
    Data.Length = 0;
    TableLength = 0;
    LengthIndex = 0;
    // Guarantee atleast 2 slots
    Data.Length = Primes[0];

    Reserve(Slack, true);
}

/* 
Adds another hashtable's contents to this hashtable.
Only identical hashtable types may be appended.
bEmptyTableB: Whether to Empty() TableB after it has been appended. (TRUE by default)
*/
public function Append(HashTable TableB, optional bool bEmptyTableB = true)
{
    local Array<Pair> Elements;
    local int i;

    Elements = TableB.ToArray();

    Reserve(Length() + Elements.Length);

    for(i = 0; i < Elements.Length; i++)
    {
        Add(Elements[i].Key, Elements[i].Value);
    }

    if(bEmptyTableB) TableB.Empty();
}

/* Shrink the hashtable down to the minimum number of buffer slots before a resize is needed. */
public function Compact()
{
    local int MinimumLength, i;
    MinimumLength = FCeil(float(Length()) * (1.f / LoadFactor));

    for(i = 0; i < arraycount(Primes); i++)
    {
        if(Primes[i] >= MinimumLength)
        {
            UpdateLength(Primes[i]);
            LengthIndex = i;
            return;
        }
    }
    
}

private function UpdateLength(int NewLength)
{
    local Array<Pair> NewData;
    local int i, FoundKey, k;
    k = 1;
    FoundKey = `KeyNone;
    NewData.Length = NewLength;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KeyNone) continue;

        k = 1;

        // Can't use GetIndex here because its a different buffer so we use this slightly modified version instead
        while(k <= 32)
        {
            FoundKey = NewData[Hash(Data[i].Key, k) % NewData.Length].Key;

            if(FoundKey == `KeyNone || FoundKey == Data[i].Key)
            {
                NewData[Hash(Data[i].Key, k) % NewData.Length] = Data[i];
                break;
            }

            k++;
        }
    }

    Print("Length updated! ("$String(Data.Length)$" -> "$String(NewLength)$")");

    Data = NewData;
}

private function int Hash(int Key, int k)
{
    return Key + k * (1 + (((Key >> 5) + 1) % (Data.Length - 1)));
}

// Handles collisions by rehashing. See above function.
private function int GetIndex(int Key)
{
    local int FoundKey, k;
    FoundKey = `KeyNone;
    k = 1;

    while(k <= 32)
    {
        FoundKey = Data[Hash(Key, k) % Data.Length].Key;

        if(FoundKey == `KeyNone || FoundKey == Key)
        {
            return Hash(Key, k) % Data.Length;
        }

        k++;
    }
}

private static final function Print(const string msg)
{
    local WorldInfo wi;
    wi = class'WorldInfo'.static.GetWorldInfo();
    if (wi != None)
    {
        if (wi.GetALocalPlayerController() != None)
            wi.GetALocalPlayerController().TeamMessage(None, msg, 'Event', 6);
        else
            wi.Game.Broadcast(wi, msg);
    }
}

defaultproperties
{
    LoadFactor = 0.72;
    Data.Add(());
    Data.Add(());
    LengthIndex = 0;

    Primes[0] = 2;
    Primes[1] = 3;
    Primes[2] = 5;
    Primes[3] = 7;
    Primes[4] = 11;
    Primes[5] = 13;
    Primes[6] = 17;
    Primes[7] = 19;
    Primes[8] = 23;
    Primes[9] = 29;
    Primes[10] = 31;
    Primes[11] = 37;
    Primes[12] = 41;
    Primes[13] = 43;
    Primes[14] = 47;
    Primes[15] = 53;
    Primes[16] = 59;
    Primes[17] = 61;
    Primes[18] = 67;
    Primes[19] = 71;
    Primes[20] = 73;
    Primes[21] = 79;
    Primes[22] = 83;
    Primes[23] = 89;
    Primes[24] = 97;
    Primes[25] = 101;
    Primes[26] = 103;
    Primes[27] = 107;
    Primes[28] = 109;
    Primes[29] = 113;
    Primes[30] = 127;
    Primes[31] = 131;
    Primes[32] = 137;
    Primes[33] = 139;
    Primes[34] = 149;
    Primes[35] = 151;
    Primes[36] = 157;
    Primes[37] = 163;
    Primes[38] = 167;
    Primes[39] = 173;
    Primes[40] = 179;
    Primes[41] = 181;
    Primes[42] = 191;
    Primes[43] = 193;
    Primes[44] = 197;
    Primes[45] = 199;
    Primes[46] = 211;
    Primes[47] = 223;
    Primes[48] = 227;
    Primes[49] = 229;
    Primes[50] = 233;
    Primes[51] = 239;
    Primes[52] = 241;
    Primes[53] = 251;
    Primes[54] = 257;
    Primes[55] = 263;
    Primes[56] = 269;
    Primes[57] = 271;
    Primes[58] = 277;
    Primes[59] = 281;
    Primes[60] = 283;
    Primes[61] = 293;
    Primes[62] = 307;
    Primes[63] = 311;
    Primes[64] = 313;
    Primes[65] = 317;
    Primes[66] = 331;
    Primes[67] = 337;
    Primes[68] = 347;
    Primes[69] = 349;
    Primes[70] = 353;
    Primes[71] = 359;
    Primes[72] = 367;
    Primes[73] = 373;
    Primes[74] = 379;
    Primes[75] = 383;
    Primes[76] = 389;
    Primes[77] = 397;
    Primes[78] = 401;
    Primes[79] = 409;
    Primes[80] = 419;
    Primes[81] = 421;
    Primes[82] = 431;
    Primes[83] = 433;
    Primes[84] = 439;
    Primes[85] = 443;
    Primes[86] = 449;
    Primes[87] = 457;
    Primes[88] = 461;
    Primes[89] = 463;
    Primes[90] = 467;
    Primes[91] = 479;
    Primes[92] = 487;
    Primes[93] = 491;
    Primes[94] = 499;
    Primes[95] = 503;
    Primes[96] = 509;
    Primes[97] = 521;
    Primes[98] = 523;
    Primes[99] = 541;
    Primes[100] = 547;
    Primes[101] = 557;
    Primes[102] = 563;
    Primes[103] = 569;
    Primes[104] = 571;
    Primes[105] = 577;
    Primes[106] = 587;
    Primes[107] = 593;
    Primes[108] = 599;
    Primes[109] = 601;
    Primes[110] = 607;
    Primes[111] = 613;
    Primes[112] = 617;
    Primes[113] = 619;
    Primes[114] = 631;
    Primes[115] = 641;
    Primes[116] = 643;
    Primes[117] = 647;
    Primes[118] = 653;
    Primes[119] = 659;
    Primes[120] = 661;
    Primes[121] = 673;
    Primes[122] = 677;
    Primes[123] = 683;
    Primes[124] = 691;
    Primes[125] = 701;
    Primes[126] = 709;
    Primes[127] = 719;
    Primes[128] = 727;
    Primes[129] = 733;
    Primes[130] = 739;
    Primes[131] = 743;
    Primes[132] = 751;
    Primes[133] = 757;
    Primes[134] = 761;
    Primes[135] = 769;
    Primes[136] = 773;
    Primes[137] = 787;
    Primes[138] = 797;
    Primes[139] = 809;
    Primes[140] = 811;
    Primes[141] = 821;
    Primes[142] = 823;
    Primes[143] = 827;
    Primes[144] = 829;
    Primes[145] = 839;
    Primes[146] = 853;
    Primes[147] = 857;
    Primes[148] = 859;
    Primes[149] = 863;
    Primes[150] = 877;
    Primes[151] = 881;
    Primes[152] = 883;
    Primes[153] = 887;
    Primes[154] = 907;
    Primes[155] = 911;
    Primes[156] = 919;
    Primes[157] = 929;
    Primes[158] = 937;
    Primes[159] = 941;
    Primes[160] = 947;
    Primes[161] = 953;
    Primes[162] = 967;
    Primes[163] = 971;
    Primes[164] = 977;
    Primes[165] = 983;
    Primes[166] = 991;
    Primes[167] = 997;
    Primes[168] = 1009;
    Primes[169] = 1013;
    Primes[170] = 1019;
    Primes[171] = 1021;
    Primes[172] = 1031;
    Primes[173] = 1033;
    Primes[174] = 1039;
    Primes[175] = 1049;
    Primes[176] = 1051;
    Primes[177] = 1061;
    Primes[178] = 1063;
    Primes[179] = 1069;
    Primes[180] = 1087;
    Primes[181] = 1091;
    Primes[182] = 1093;
    Primes[183] = 1097;
    Primes[184] = 1103;
    Primes[185] = 1109;
    Primes[186] = 1117;
    Primes[187] = 1123;
    Primes[188] = 1129;
    Primes[189] = 1151;
    Primes[190] = 1153;
    Primes[191] = 1163;
    Primes[192] = 1171;
    Primes[193] = 1181;
    Primes[194] = 1187;
    Primes[195] = 1193;
    Primes[196] = 1201;
    Primes[197] = 1213;
    Primes[198] = 1217;
    Primes[199] = 1223;
    Primes[200] = 1229;
    Primes[201] = 1231;
    Primes[202] = 1237;
    Primes[203] = 1249;
    Primes[204] = 1259;
    Primes[205] = 1277;
    Primes[206] = 1279;
    Primes[207] = 1283;
    Primes[208] = 1289;
    Primes[209] = 1291;
    Primes[210] = 1297;
    Primes[211] = 1301;
    Primes[212] = 1303;
    Primes[213] = 1307;
    Primes[214] = 1319;
    Primes[215] = 1321;
    Primes[216] = 1327;
    Primes[217] = 1361;
    Primes[218] = 1367;
    Primes[219] = 1373;
    Primes[220] = 1381;
    Primes[221] = 1399;
    Primes[222] = 1409;
    Primes[223] = 1423;
    Primes[224] = 1427;
    Primes[225] = 1429;
    Primes[226] = 1433;
    Primes[227] = 1439;
    Primes[228] = 1447;
    Primes[229] = 1451;
    Primes[230] = 1453;
    Primes[231] = 1459;
    Primes[232] = 1471;
    Primes[233] = 1481;
    Primes[234] = 1483;
    Primes[235] = 1487;
    Primes[236] = 1489;
    Primes[237] = 1493;
    Primes[238] = 1499;
    Primes[239] = 1511;
    Primes[240] = 1523;
    Primes[241] = 1531;
    Primes[242] = 1543;
    Primes[243] = 1549;
    Primes[244] = 1553;
    Primes[245] = 1559;
    Primes[246] = 1567;
    Primes[247] = 1571;
    Primes[248] = 1579;
    Primes[249] = 1583;
    Primes[250] = 1597;
    Primes[251] = 1601;
    Primes[252] = 1607;
    Primes[253] = 1609;
    Primes[254] = 1613;
    Primes[255] = 1619;
    Primes[256] = 1621;
    Primes[257] = 1627;
    Primes[258] = 1637;
    Primes[259] = 1657;
    Primes[260] = 1663;
    Primes[261] = 1667;
    Primes[262] = 1669;
    Primes[263] = 1693;
    Primes[264] = 1697;
    Primes[265] = 1699;
    Primes[266] = 1709;
    Primes[267] = 1721;
    Primes[268] = 1723;
    Primes[269] = 1733;
    Primes[270] = 1741;
    Primes[271] = 1747;
    Primes[272] = 1753;
    Primes[273] = 1759;
    Primes[274] = 1777;
    Primes[275] = 1783;
    Primes[276] = 1787;
    Primes[277] = 1789;
    Primes[278] = 1801;
    Primes[279] = 1811;
    Primes[280] = 1823;
    Primes[281] = 1831;
    Primes[282] = 1847;
    Primes[283] = 1861;
    Primes[284] = 1867;
    Primes[285] = 1871;
    Primes[286] = 1873;
    Primes[287] = 1877;
    Primes[288] = 1879;
    Primes[289] = 1889;
    Primes[290] = 1901;
    Primes[291] = 1907;
    Primes[292] = 1913;
    Primes[293] = 1931;
    Primes[294] = 1933;
    Primes[295] = 1949;
    Primes[296] = 1951;
    Primes[297] = 1973;
    Primes[298] = 1979;
    Primes[299] = 1987;
    Primes[300] = 1993;
    Primes[301] = 1997;
    Primes[302] = 1999;
}