/*
===========================================================================
Copyright (C) 2015 the OpenMoHAA team

This file is part of OpenMoHAA source code.

OpenMoHAA source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

OpenMoHAA source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with OpenMoHAA source code; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/

// con_arrayset.h: con_set with an index table

#pragma once

#include "mem_blockalloc.h"

#if defined(GAME_DLL)
#    include "../fgame/g_local.h"

#    define ARRAYSET_Alloc gi.Malloc
#    define ARRAYSET_Free  gi.Free

#elif defined(CGAME_DLL)
#    include "../cgame/cg_local.h"

#    define ARRAYSET_Alloc cgi.Malloc
#    define ARRAYSET_Free  cgi.Free

#elif defined(REF_DLL)
#    include "../renderercommon/tr_common.h"

#    define ARRAYSET_Alloc ri.Malloc
#    define ARRAYSET_Free  ri.Free

#else
#    include "qcommon.h"

#    define ARRAYSET_Alloc Z_Malloc
#    define ARRAYSET_Free  Z_Free
#endif

template<typename k, typename v>
class con_arrayset;

template<typename k, typename v>
class con_arrayset_enum;

template<typename k, typename v>
class con_arrayset_Entry
{
    friend con_arrayset<k, v>;
    friend con_arrayset_enum<k, v>;

public:
    k            key;
    v            value;
    unsigned int index;

    con_arrayset_Entry *next;

public:
    void *operator new(size_t size) { return con_arrayset<k, v>::NewEntry(size); }

    void operator delete(void *ptr) { con_arrayset<k, v>::DeleteEntry(ptr); }

    con_arrayset_Entry()
    {
        this->key   = k();
        this->value = v();

        index = 0;
        next  = NULL;
    }

#ifdef ARCHIVE_SUPPORTED
    void Archive(Archiver& arc);
#endif
};

template<typename k, typename v>
class con_arrayset
{
    friend class con_arrayset_enum<k, v>;

public:
    using Entry = con_arrayset_Entry<k, v>;

public:
    static MEM_BlockAlloc<Entry> Entry_allocator;

private:
    Entry            **table; // hashtable
    unsigned int       tableLength;
    unsigned int       threshold;
    unsigned int       count; // num of entries
    short unsigned int tableLengthIndex;
    Entry             *defaultEntry;
    Entry            **reverseTable; // the index table

protected:
    Entry *findKeyEntry(const k& key) const;
    Entry *addKeyEntry(const k& key);
    Entry *addNewKeyEntry(const k& key);

public:
    static void *NewEntry(size_t size);
    static void  DeleteEntry(void *entry);
    static void *NewTable(size_t count);
    static void  DeleteTable(void *table);

public:
    con_arrayset();
    ~con_arrayset();

#ifdef ARCHIVE_SUPPORTED
    void Archive(Archiver& arc);
#endif

    void         clear();
    void         resize(int count = 0);
    unsigned int size() const;

    unsigned int findKeyIndex(const k& key);
    unsigned int addKeyIndex(const k& key);
    unsigned int addNewKeyIndex(const k& key);
    bool         remove(const k& key);

    v& operator[](unsigned int index);
};

template<typename k, typename v>
MEM_BlockAlloc<typename con_arrayset<k, v>::Entry> con_arrayset<k, v>::Entry_allocator;

template<typename k, typename v>
void *con_arrayset<k, v>::NewEntry(size_t size)
{
    return Entry_allocator.Alloc();
}

template<typename k, typename v>
void con_arrayset<k, v>::DeleteEntry(void *entry)
{
    Entry_allocator.Free(entry);
}

template<typename k, typename v>
void *con_arrayset<k, v>::NewTable(size_t count)
{
    return ARRAYSET_Alloc(sizeof(Entry *) * (int)count);
}

template<typename k, typename v>
void con_arrayset<k, v>::DeleteTable(void *table)
{
    ARRAYSET_Free(table);
}

template<typename key, typename value>
con_arrayset<key, value>::con_arrayset()
{
    tableLength = 1;
    table       = &defaultEntry;

    threshold        = 1;
    count            = 0;
    tableLengthIndex = 0;

    defaultEntry = NULL;
    reverseTable = &this->defaultEntry;
}

template<typename key, typename value>
con_arrayset<key, value>::~con_arrayset()
{
    clear();
}

template<typename key, typename value>
void con_arrayset<key, value>::resize(int count)
{
    Entry      **oldReverseTable = reverseTable;
    Entry      **oldTable        = table;
    Entry       *e, *old;
    unsigned int index;
    unsigned int oldTableLength = tableLength;
    unsigned int i;

    if (count > 0) {
        tableLength += count;
        threshold = tableLength;
    } else {
        //threshold = ( unsigned int )( ( float )tableLength * 0.75f );
        threshold = (unsigned int)((float)tableLength * 0.75);
        if (threshold < 1) {
            threshold = 1;
        }

        tableLength += threshold;
    }

    // allocate a new table
    table = new (NewTable(tableLength)) Entry *[tableLength]();

    // rehash the table
    for (i = oldTableLength; i > 0; i--) {
        // rehash all entries from the old table
        for (e = oldTable[i - 1]; e != NULL; e = old) {
            old = e->next;

            // insert the old entry to the table hashindex
            index = HashCode<key>(e->key) % tableLength;

            e->next      = table[index];
            table[index] = e;
        }
    }

    if (oldTableLength > 1) {
        // delete the previous table
        DeleteTable(oldTable);
    }

    // allocate a bigger reverse table
    reverseTable = new (NewTable(tableLength)) Entry *[this->tableLength]();

    for (i = 0; i < oldTableLength; i++) {
        reverseTable[i] = oldReverseTable[i];
    }

    if (oldTableLength > 1) {
        DeleteTable(oldReverseTable);
    }
}

template<typename k, typename v>
unsigned int con_arrayset<k, v>::size() const
{
    return count;
}

template<typename key, typename value>
void con_arrayset<key, value>::clear()
{
    Entry       *entry = NULL;
    Entry       *next  = NULL;
    unsigned int i;

    if (tableLength > 1) {
        DeleteTable(reverseTable);
        reverseTable = &defaultEntry;
    }

    for (i = 0; i < tableLength; i++) {
        for (entry = table[i]; entry != NULL; entry = next) {
            next = entry->next;
            delete entry;
        }
    }

    if (tableLength > 1) {
        DeleteTable(table);
    }

    tableLength = 1;
    table       = &defaultEntry;

    threshold        = 1;
    count            = 0;
    tableLengthIndex = 0;

    defaultEntry = NULL;
}

template<typename k, typename v>
typename con_arrayset<k, v>::Entry *con_arrayset<k, v>::findKeyEntry(const k& key) const
{
    Entry *entry;

    entry = table[HashCode<k>(key) % tableLength];

    for (; entry != NULL; entry = entry->next) {
        if (entry->key == key) {
            return entry;
        }
    }

    return NULL;
}

template<typename k, typename v>
typename con_arrayset<k, v>::Entry *con_arrayset<k, v>::addKeyEntry(const k& key)
{
    Entry *entry;

    entry = findKeyEntry(key);

    if (entry != NULL) {
        return entry;
    } else {
        return addNewKeyEntry(key);
    }
}

template<typename k, typename v>
typename con_arrayset<k, v>::Entry *con_arrayset<k, v>::addNewKeyEntry(const k& key)
{
    Entry *entry;
    int    index;

    if (count >= threshold) {
        resize();
    }

    index = HashCode<k>(key) % tableLength;

    entry = new Entry;

    if (defaultEntry == NULL) {
        defaultEntry = entry;
        entry->next  = NULL;
    } else {
        entry->next = table[index];
    }

    reverseTable[count] = entry;
    count++;

    entry->key   = key;
    entry->index = count;
    table[index] = entry;

    return entry;
}

template<typename k, typename v>
unsigned int con_arrayset<k, v>::addKeyIndex(const k& key)
{
    Entry *entry = this->addKeyEntry(key);

    return entry->index;
}

template<typename k, typename v>
unsigned int con_arrayset<k, v>::addNewKeyIndex(const k& key)
{
    Entry *entry = this->addNewKeyEntry(key);

    return entry->index;
}

template<typename k, typename v>
unsigned int con_arrayset<k, v>::findKeyIndex(const k& key)
{
    Entry *entry = this->findKeyEntry(key);

    if (entry != NULL) {
        return entry->index;
    } else {
        return 0;
    }
}

template<typename k, typename v>
bool con_arrayset<k, v>::remove(const k& key)
{
    int i;

    for (i = 0; i < tableLength; i++) {
        if (reverseTable[i] && reverseTable[i]->key == key) {
            reverseTable[i] = NULL;
        }
    }

    return con_set<k, v>::remove(key);
}

template<typename key, typename value>
value& con_arrayset<key, value>::operator[](unsigned int index)
{
    return reverseTable[index - 1]->key;
}

template<typename key, typename value>
class con_arrayset_enum
{
    friend class con_map_enum<key, value>;

public:
    using Entry = typename con_arrayset<key, value>::Entry;

protected:
    con_arrayset<key, value> *m_Set;
    unsigned int              m_Index;
    Entry                    *m_CurrentEntry;
    Entry                    *m_NextEntry;

public:
    con_arrayset_enum();
    con_arrayset_enum(con_arrayset<key, value>& set);

    bool operator=(con_arrayset<key, value>& set);

    Entry *NextElement(void);
    Entry *CurrentElement(void);
};

template<typename key, typename value>
con_arrayset_enum<key, value>::con_arrayset_enum()
{
    m_Set          = NULL;
    m_Index        = 0;
    m_CurrentEntry = NULL;
    m_NextEntry    = NULL;
}

template<typename key, typename value>
con_arrayset_enum<key, value>::con_arrayset_enum(con_arrayset<key, value>& set)
{
    *this = set;
}

template<typename key, typename value>
bool con_arrayset_enum<key, value>::operator=(con_arrayset<key, value>& set)
{
    m_Set          = &set;
    m_Index        = m_Set->tableLength;
    m_CurrentEntry = NULL;
    m_NextEntry    = NULL;

    return true;
}

template<typename key, typename value>
typename con_arrayset_enum<key, value>::Entry *con_arrayset_enum<key, value>::CurrentElement(void)
{
    return m_CurrentEntry;
}

template<typename key, typename value>
typename con_arrayset_enum<key, value>::Entry *con_arrayset_enum<key, value>::NextElement(void)
{
    if (!m_NextEntry) {
        while (1) {
            if (!m_Index) {
                break;
            }

            m_Index--;
            m_NextEntry = m_Set->table[m_Index];

            if (m_NextEntry) {
                break;
            }
        }

        if (!m_NextEntry) {
            m_CurrentEntry = NULL;
            return NULL;
        }
    }

    m_CurrentEntry = m_NextEntry;
    m_NextEntry    = m_NextEntry->next;

    return m_CurrentEntry;
}