HashTable

[Enter recovery key to allow modifications] [Download all in ZIP]

Views: 52

Modified @ 2025-03-23 10:43:46

A new scripting data type.

Instructions can be found in HashTable.uc but are repeated here:

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.

HashTable_String and HashTable_Actor are provided so you can see what it should look like after the initial setup.

Note that the data type is an Object so you will have to make one using new class'HashTable_DataType'.

Note: if you know that you will have to hold a lot of items in the table, consider expanding the primes array as needed.

HashTable.uc

[RAW] [Download] 

/* 
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;
}
HashTable_Actor.uc

[RAW] [Download] 

/* 
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.
â €
Copy of HashTable.uc with value type Actor.
*/
class HashTable_Actor extends Object;
 
// -2147483648 is used for None
`define KeyNone -2147483648
 
struct Pair
{
    var int Key;
    var Actor 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, Actor 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 Actor Value, optional bool bCompact)
{
    Value = Data[GetIndex(Key)].Value;
    Remove(Key);
 
    if(bCompact) Compact();
}
 
/* Get a value, by key. */
public function Actor Get(int Key)
{
    return Data[GetIndex(Key)].Value;
}
 
/* Set a value, by key. */
public function Set(int Key, Actor 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(Actor 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_Actor 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;
}
HashTable_String.uc

[RAW] [Download] 

/* 
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.
â €
Copy of HashTable.uc with value type String.
*/
class HashTable_String extends Object;
 
// -2147483648 is used for None
`define KeyNone -2147483648
 
struct Pair
{
    var int Key;
    var String 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, String 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 String Value, optional bool bCompact)
{
    Value = Data[GetIndex(Key)].Value;
    Remove(Key);
 
    if(bCompact) Compact();
}
 
/* Get a value, by key. */
public function String Get(int Key)
{
    return Data[GetIndex(Key)].Value;
}
 
/* Set a value, by key. */
public function Set(int Key, String 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(String 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_String 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;
}