/* ============= User Params ============= */
// Note: put a space at the end of these if you're experiencing compiler errors

/* Name your class! */
`define CLASS_NAME HashTableV2 

/* if this isnt int, turn KEY_CUSTOM on */
`define KEYTYPE IntVector 

// If you know your key > 8 bytes, turn this on.
`define PASS_KEY_REFERENCED TRUE

// Whether you want to pass keys by reference on user functions such as Add().
`define PASS_KEY_REFERENCED_USER TRUE

/* If your key is NOT an int, you will need to write a hashing function for your key type in GetHash(), and turn this on. See below. */
`define KEY_CUSTOM TRUE

`define VALUETYPE int 

// Whether you want to pass values by reference on the functions Set(), Add() and FindKey().
`define PASS_VALUE_REFERENCED_USER TRUE

/* Trades performance for safety. Setting this to false will make validity checks not run on certain user accessible functions. Default is TRUE in editor and FALSE in cooked */
`define SAFE `if(`isdefined(IS_PUBLIC_MODDING_TOOLS)) TRUE `else FALSE `endif

/* ============= Non-user macros ============= */

// -2147483648 is used for None
`define KEY_NONE `if(`KEY_CUSTOM) class'`CLASS_NAME'.default.DefaultKeyValue `else -2147483648 `endif
`define KEYTYPE_ARG `if(`PASS_KEY_REFERENCED) const out `endif `KEYTYPE
`define KEYTYPE_ARG_USER `if(`PASS_KEY_REFERENCED_USER) const out `endif `KEYTYPE
`define VALUETYPE_ARG_USER `if(`PASS_VALUE_REFERENCED_USER) const out `endif `VALUETYPE

// Creates a hash for a pair of two ints. Can be chained.
`define HashPair(A, B) (((`A << 19)|(`A >> 13)) ^ `B)

class `CLASS_NAME  extends Object
    hidecategories(Object);

struct immutable IntVector extends IntPoint
{
    var() int Z;

    structdefaultproperties
    {
        X = -2147483648;
        Y = -2147483648;
        Z = -2147483648;
    }
};

struct Pair
{
    var() `KEYTYPE  Key;
    var() `VALUETYPE  Value;

    structdefaultproperties
    {
        `if(`KEY_CUSTOM) `else Key = `KEY_NONE `endif
    }
};

var private Array<Pair> Data;
var private const float LoadFactor;
var private int TableLength; // Number of real elements

`if(`KEY_CUSTOM)
var private const `KEYTYPE DefaultKeyValue;
`endif

`if(`KEY_CUSTOM)
// You can write your own hashing function here.
public final function int GetHash(`KEYTYPE_ARG  Key)
{
    return `HashPair(Key.X, `HashPair(Key.Y, Key.Z));
}
`endif

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

    `if(`SAFE)
    if(Key == `KEY_NONE)
    {
        Print("Cannot use KEY_NONE as a key!");
        return;
    }

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

    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(`KEYTYPE_ARG_USER  Key, optional bool bCompact)
{
    Data[GetIndex(Key)].Key = `KEY_NONE;
    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(`KEYTYPE_ARG_USER  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(`KEYTYPE_ARG_USER  Key)
{
    return Data[GetIndex(Key)].Value;
}

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

    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 Data.Length;
}

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

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

// 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 == `KEY_NONE) 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;

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

    if(MinimumLength <= Data.Length) return;

    UpdateLength(ClosestPrime(MinimumLength));
}

/* 
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;
    // Guarantee atleast 2 slots
    Data.Length = 2;

    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(`CLASS_NAME  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;

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

    UpdateLength(ClosestPrime(MinimumLength));
}

private function UpdateLength(int NewLength)
{
    local Array<Pair> NewData;
    local int i, k;
    local `KEYTYPE FoundKey;
    k = 1;
    FoundKey = `KEY_NONE;
    NewData.Length = NewLength;
    for(i = 0; i < Data.Length; i++)
    {
        if(Data[i].Key == `KEY_NONE) 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[HashPassByValue(Data[i].Key, k) % NewData.Length].Key;

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

            k++;
        }
    }

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

    Data = NewData;
}

private function int Hash(`KEYTYPE_ARG  Key, int k)
{
    return `if(`KEY_CUSTOM) GetHash(Key) `else Key `endif + k * (1 + (((`if(`KEY_CUSTOM) GetHash(Key) `else Key `endif >> 5) + 1) % (Data.Length - 1)));
}

/* Copy of Hash, never passes by reference because of the "not allowed to pass a dynamic array element as the value for an out parameter" rule. Only used in UpdateLength. */
private function int HashPassByValue(`KEYTYPE  Key, int k)
{
    return `if(`KEY_CUSTOM) GetHash(Key) `else Key `endif + k * (1 + (((`if(`KEY_CUSTOM) GetHash(Key) `else Key `endif >> 5) + 1) % (Data.Length - 1)));
}

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

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

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

        k++;
    }
}

// returns n if n is prime or the next prime if n is composite
// If you've made a faster implementation of this let me know because I'd gladly include it.
private function int ClosestPrime(int n)
{
    local int x;

    if(n == 2) return n;

    n = n|1; // guarantee n to be odd

    x = n;
    while(!IsPrime(x))
        x += 2;

    return x;
}

// Rabin-miller isnt feasible because of integer overflow, so use trial division instead.
private function bool IsPrime(int n)
{
    local int p, max;

    // Skip this because we make it odd in NextPrime().
    //if(n % 2 == 0) return false;

    max = Sqrt(n);

    // it's already not divisible by 2 so there's no point checking even numbers.
    for(p = 3; p <= max; p += 2)
    {
        if(n % p == 0) return false;
    }

    return true;
}

`if(`SAFE)
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);
    }
}
`endif

defaultproperties
{
    LoadFactor = 0.72;
    Data.Add(());
    Data.Add(());
}