Resizing Arrays for Speed

Question

So, I am writing a Befunge Interpreter in Java. I have almost all of it down, except I can't figure out a good solution to the problem of Funge Space. Currently I'm using the style stated in the Befunge 93 specs, which is a 80x25 array to hold the code.

In Funge, though, I'm supposed to have an "infinite" array of code (or 4,294,967,296 x 4,294,967,296, which is -2,147,483,648 to 2,147,483,648 in both dimensions), but obviously it's never a good idea to have that much space allocated. But as well as this, it doesn't seem like a good idea to create a new array and copy every character into it every time the program steps out of bounds. Is there a solution to this problem that I'm missing?

So basically, my problem is that I need to somehow expand the array every time I reach out of bounds, or use some sort of other data structure. Any suggestions?

Funge 98 specs

Also, by the way, I still have never figure out how to pronounce Befunge or Funge, I always just say it like "Bee-funj" and "funj"

Answer 1

Without having read the specs (no - I mean, just NO!): A 4,294,967,296 x 4,294,967,296 array is obviously a highly theoretical construct, and only a tiny fraction of these "array entries" can and will ever be used.

Apart from that: Regardless of whether you use an array or any other collection, you'll have a problem with indexing: Array indices can only be int values, but 4,294,967,296 is twice as large as Integer.MAX_VALUE (there are no unsigned ints in Java).

However, one way of representing such an "infinitely large" sparse 2D array would be a map that maps pairs of long values (the x and y coordinates) to the array entries. Roughly like this:

import java.util.HashMap;
import java.util.Map;

interface Space<T> 
{
    void set(long x, long y, T value);
    T get(long x, long y);
}

class DefaultSpace<T> implements Space<T>
{
    private final Map<LongPair, T> map = new HashMap<LongPair, T>();

    @Override
    public void set(long x, long y, T value)
    {
        LongPair key = new LongPair(x,y);
        if (value == null)
        {
            map.remove(key);
        }
        else
        {
            map.put(key, value);
        }
    }

    @Override
    public T get(long x, long y)
    {
        return map.get(new LongPair(x,y));
    }
}


class LongPair
{
    private final long x;
    private final long y;

    LongPair(long x, long y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString()
    {
        return "("+x+","+y+")";
    }

    @Override
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result + (int) (x ^ (x >>> 32));
        result = prime * result + (int) (y ^ (y >>> 32));
        return result;
    }

    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        LongPair other = (LongPair) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }

}