RandomUsefulStuff/LookUpTable.java

// The code below is licensed under the WTFPL.

// Here is a copy for your convenience:

//            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
//                    Version 2, December 2004
//
// Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>
//
// Everyone is permitted to copy and distribute verbatim or modified
// copies of this license document, and changing it is allowed as long
// as the name is changed.
//
//            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
//   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
//
//  0. You just DO WHAT THE FUCK YOU WANT TO.

import java.util.ArrayList;
import java.util.List;

/**
 * <p>
 * This is a naive implementation of a look up table. Store and retrieve key
 * value pairs.
 * </p>
 *
 * <p>
 * I had no reason to implement this other than not wanting to go down a rabbit
 * hole of Java types rather than just using simple functionality.
 * </p>
 *
 * @author BodgeMaster
 *
 * @param <T> The type to be stored
 */
public class LookUpTable<T> {
    private List<T> values;
    private String[] keys;
    private boolean[] usedSlots;
    private int storedElements;

    public LookUpTable() {
        this.values = new ArrayList<T>();
        for (int i = 0; i < 10; i++) {
            values.add(null);
        }
        this.keys = new String[10];
        this.usedSlots = new boolean[] { false, false, false, false, false, false, false, false, false, false };
        this.storedElements = 0;
    }

    /**
     * Add an element
     * 
     * @param key
     * @param value
     * @throws DuplicateKeyException
     */
    public void add(String key, T value) {
        // duplicate check
        for (int i = 0; i < this.keys.length; i++) {
            if (usedSlots[i]) {
                if (keys[i].equals(key)) throw new DuplicateKeyException(key);
            }
        }

        // Make bigger arrays when running out of space
        if (this.storedElements == this.keys.length) {
            String[] keys = this.keys;
            boolean[] usedSlots = this.usedSlots;
            this.keys = new String[keys.length + 10];
            this.usedSlots = new boolean[usedSlots.length + 10];
            for (int i = 0; i < keys.length; i++) {
                this.keys[i] = keys[i];
                this.usedSlots[i] = usedSlots[i];
            }
            for (int i = 0; i < 10; i++) {
                // ensure capacity
                this.values.add(null);
            }
        }

        // Find next unused slot
        int unusedSlot = 0;
        for (int i = 0; i < this.usedSlots.length; i++) {
            if (!this.usedSlots[i]) {
                unusedSlot = i;
                break;
            }
        }

        this.keys[unusedSlot] = key;
        this.values.set(unusedSlot, value);
        usedSlots[unusedSlot] = true;
        this.storedElements++;
    }

    /**
     * Get a value by key
     * 
     * @param key
     * @return value (null if key not found)
     */
    public T get(String key) {
        for (int i = 0; i < usedSlots.length; i++) {
            if (usedSlots[i]) {
                if (keys[i].equals(key)) return values.get(i);
            }
        }
        return null;
    }

    public void set(String key, T value) {
        for (int i = 0; i < usedSlots.length; i++) {
            if (usedSlots[i]) {
                if (keys[i].equals(key)) values.set(i, value);
            }
        }
    }

    /**
     * <p>
     * Remove an element from the LUT
     * </p>
     * 
     * <p>
     * This function marks the position of key as unused. If you actually want to
     * ensure that the object is removed from the LUT, use
     * {@link LookUpTable#fullRemove(String)} instead.
     * </p>
     * 
     * @param key
     */
    public void remove(String key) {
        for (int i = 0; i < usedSlots.length; i++) {
            if (usedSlots[i]) {
                if (keys[i].equals(key)) usedSlots[i] = false;
            }
        }
        storedElements--;
    }

    /**
     * Remove an element from the LUT by actually setting it to null.
     * 
     * @param key
     */
    public void fullRemove(String key) {
        for (int i = 0; i < usedSlots.length; i++) {
            if (usedSlots[i]) {
                if (keys[i].equals(key)) {
                    values.set(i, null);
                    usedSlots[i] = false;
                }
            }
        }
        storedElements--;
    }

    public int storedElements() {
        return this.storedElements;
    }

    /**
     * Gets a key by its position in the LUT. Unused slots are ignored and do not
     * count towards the position.
     * 
     * @param index
     * @return key
     */
    public String getKey(int index) {
        int i = 0;
        int j = 0;
        while (i < index) {
            j++;
            if (usedSlots[j]) i++;
        }
        return keys[j];
    }

    public static class DuplicateKeyException extends RuntimeException {
        public DuplicateKeyException() {
            super("Tried adding an element with a duplicte key to a LookUpTable.");
        }

        public DuplicateKeyException(String key) {
            super("Tried adding an element with a duplicte key to a LookUpTable: " + key);
        }
    }
}