OrderedTable.avt

/*
    Реализация среды исполнения языка программирования
    Объектно-ориентированный продвинутый векторный транслятор

    Copyright © 2021, 2024, 2026 Малик Разработчик

    Это свободная программа: вы можете перераспространять ее и/или изменять
    ее на условиях Меньшей Стандартной общественной лицензии GNU в том виде,
    в каком она была опубликована Фондом свободного программного обеспечения;
    либо версии 3 лицензии, либо (по вашему выбору) любой более поздней версии.

    Эта программа распространяется в надежде, что она будет полезной,
    но БЕЗО ВСЯКИХ ГАРАНТИЙ; даже без неявной гарантии ТОВАРНОГО ВИДА
    или ПРИГОДНОСТИ ДЛЯ ОПРЕДЕЛЕННЫХ ЦЕЛЕЙ. Подробнее см. в Меньшей Стандартной
    общественной лицензии GNU.

    Вы должны были получить копию Меньшей Стандартной общественной лицензии GNU
    вместе с этой программой. Если это не так, см.
    <https://www.gnu.org/licenses/>.
*/

package platform.independent.util;

import avt.lang.array.*;
import avt.lang.math.*;
import platform.independent.streamformat.*;

public class OrderedTable(Object, MutableDataHolder, DataHolder, Measureable, ObjectArray)
{
    private int fldLength;
    private Entry[] fldTable;
    private Object[] fldKeys;

    public () {
        fldTable = new Entry[0x3f];
        fldKeys = new Object[0x3f];
    }

    public void clear() {
        Object[] data = fldTable;
        Array.fill(data, 0, data.length, null);
        data = fldKeys;
        Array.fill(data, 0, fldLength, null);
        fldLength = 0;
    }

    public boolean isEmpty() { return fldLength <= 0; }

    public boolean contains(Object key) {
        if(key == null) return false;
        Entry[] table = fldTable;
        long2 hash = key.hashCodeAsLong2();
        int index = Entry.getIndex(hash, table.length);
        for(Entry curr = table[index]; curr != null; curr = curr.next) if(curr.hash == hash && curr.key.equals(key)) return true;
        return false;
    }

    public int length { read = fldLength }

    public Object operator [](int index) {
        if(index < 0 || index >= fldLength)
        {
            throw new ArrayIndexOutOfBoundsException(avt.lang.package.getResourceString("out-of-bounds.array-index"));
        }
        return fldKeys[index];
    }

    public void operator []=(Object key, Object value) {
        if(key == null)
        {
            throw new NullPointerException(String.format(avt.lang.package.getResourceString("null-pointer.argument"), new Object[] { "key" }));
        }
        if(value == null)
        {
            remove(key);
            return;
        }
        put(key, value);
    }

    public Object operator [](Object key) {
        if(key == null)
        {
            throw new NullPointerException(String.format(avt.lang.package.getResourceString("null-pointer.argument"), new Object[] { "key" }));
        }
        Entry[] table = fldTable;
        long2 hash = key.hashCodeAsLong2();
        int index = Entry.getIndex(hash, table.length);
        for(Entry curr = table[index]; curr != null; curr = curr.next) if(curr.hash == hash && curr.key.equals(key)) return curr.value;
        return null;
    }

    private void rehash() {
        Entry[] oldTable = fldTable;
        int oldCapacity = oldTable.length;
        int newCapacity = oldCapacity << 1 | 1;
        if(newCapacity < 0)
        {
            throw new BufferTooLargeError(avt.lang.package.getResourceString("!error.buffer-too-large"));
        }
        Entry[] newTable = new Entry[newCapacity];
        for(int oldIndex = oldCapacity; oldIndex-- > 0; ) for(Entry oldEntry = oldTable[oldIndex]; oldEntry != null; )
        {
            int newIndex = Entry.getIndex(oldEntry.hash, newCapacity);
            Entry newEntry = oldEntry;
            oldEntry = oldEntry.next;
            newEntry.next = newTable[newIndex];
            newTable[newIndex] = newEntry;
        }
        Object[] newKeys = new Object[newCapacity];
        Array.copy(fldKeys, 0, newKeys, 0, oldCapacity);
        fldTable = newTable;
        fldKeys = newKeys;
    }

    private void remove(Object key) {
        Entry[] table = fldTable;
        long2 hash = key.hashCodeAsLong2();
        int index = Entry.getIndex(hash, table.length);
        for(Entry prev = null, Entry curr = table[index]; curr != null; curr = (prev = curr).next) if(curr.hash == hash && curr.key.equals(key))
        {
            if(prev != null)
            {
                prev.next = curr.next;
            } else
            {
                table[index] = curr.next;
            }
            index = curr.index;
            Object[] keys = fldKeys;
            int length = fldLength - 1;
            Array.copy(keys, index + 1, keys, index, length - index);
            keys[length] = null;
            fldLength = length;
            break;
        }
    }

    private void put(Object key, Object value) {
        Entry[] table = fldTable;
        int capacity = table.length;
        long2 hash = key.hashCodeAsLong2();
        int index = Entry.getIndex(hash, capacity);
        for(Entry curr = table[index]; curr != null; curr = curr.next) if(curr.hash == hash && curr.key.equals(key))
        {
            curr.value = value;
            return;
        }
        int length = fldLength;
        if(length >= capacity)
        {
            rehash();
            table = fldTable;
            index = Entry.getIndex(hash, table.length);
        }
        fldKeys[length] = key;
        table[index] = new Entry(length, hash, key, value, table[index]);
        fldLength = length + 1;
    }
}

final class Entry(Object)
{
    public static int getIndex(long2 hash, int length) { return (int) Int128.remUnsigned(hash, length); }

    private int fldIndex;
    private long2 fldHash;
    private Object fldKey;
    private Object fldValue;
    private Entry fldNext;

    public (int index, long2 hash, Object key, Object value, Entry next) {
        fldIndex = index;
        fldHash = hash;
        fldKey = key;
        fldValue = value;
        fldNext = next;
    }

    public int index { read = fldIndex }

    public long2 hash { read = fldHash }

    public Object key { read = fldKey }

    public Object value { read = fldValue, write = fldValue }

    public Entry next { read = fldNext, write = fldNext }
 }