Data structure for grid with negative indeces

Question

Sorry if this is an insultingly obvious concept, but it's something I haven't done before and I've been unable to find any material discussing the best way to approach it.

I'm wondering what's the best data structure for holding a 2D grid of unknown size. The grid has integer coordinates (x,y), and will have negative indices in both directions.

So, what is the best way to hold this grid? I'm programming in c# currently, so I can't have negative array indices. My initial thought was to have class with 4 separate arrays for (+x,+y),(+x,-y),(-x,+y), and (-x,-y). This seems to be a valid way to implement the grid, but it does seem like I'm over-engineering the solution, and array resizing will be a headache.

Another idea was to keep track of the center-point of the array and set that as the topological (0,0), however I would have the issue of having to do a shift to every element of the grid when repeatedly adding to the top-left of the grid, which would be similar to grid resizing though in all likelihood more frequent.

Thoughts?

Answer 1

Write a new data structure having an indexer that routes negative indexes into a different list.

public class PositiveNegativeList<T>
{
    List<T> PositiveList;
    List<T> NegativeList;

    public PositiveNegativeList()
    {
         PositiveList = new List<T>();
         NegativeList = new List<T>();
    }

    public T this[int index]
    {
        get
        {
            if (index < 0)
               return NegativeList[index * -1];
            else
               return PositiveList[index];
        }

        set
        {
            if (index < 0)
               NegativeList[index * -1] = value;
            else
               PositiveList[index] = value;
        }
    }

    public void Add(T item)
    {
        PositiveList.Add(item);
    }
}

Code now tested. Note that nothing is ever as simple as it should be; you will need an Add() method of some kind to get new items into the Lists.

Answer 2

I am going to start by assuming that you know how to create a grid with X indices 0 to xmax and Y indices 0 to ymax.

If the bounds of your indices are xlower to xupper and ylower to yupper, then you have to map indices in this range to indices in the first range.

If indices in the first range are x1 and y1, and the indices in the second range are x2 and y2, then:

x1 = x2 - xlower;
y1 = y2 - ylower;

Now you have indices that can be used in a regular grid.

This sounds so simple, I am wondering whether I missed some important details.