# Data structure for grid with negative indeces

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?

• Is the grid sparse or dense? If it's sparse, use a dictionary with the XY coordinate pair as a key; see stackoverflow.com/questions/11837139/…. If it's dense, write a new data structure having an indexer that routes negative indexes into a different list. Commented May 27, 2014 at 22:45
• Does unknown mean unknown until creation or may expand infinitely in any direction? Commented May 28, 2014 at 11:53
• Dictionary would be easy. Commented May 28, 2014 at 19:52
• @Blrfl starts small and may expand infinitely Commented May 28, 2014 at 23:56

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;
}
}

{
}
}
``````

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.

• There's no need to use Activator. It is perfectly valid to use `new List<T>();` within the constructor. The casts are unnecessary as well. Commented May 28, 2014 at 17:41
• @DanLyons: Are you sure? I don't think that compiles; the `List<T>` constructor expects a declared type, like `string`. I do think you're right about the casts, though. Commented May 28, 2014 at 17:42
• Yeah, the declared type is coming from the type parameter on the class definition. I tossed it into a quick console project to confirm. The only change I had to make was replacing `this(int index)` with `this[int index]`. Commented May 28, 2014 at 17:47
• @DanLyons: I'm hobbled by the fact that my IDE is on a different computer than my Internet (for security reasons). Commented May 28, 2014 at 17:48
• Shouldn't that `Activator` note be removed now that the code doesn't use it? Commented May 28, 2014 at 19:46

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.

• Thanks for your response. The grid is expected to be expanded during runtime. Using this solution would mean that adding to the "top left" of the grid would require that the grid be both shifted and less frequently expanded also. Do you think that a multiple grid approach would be better? (no shift required) Commented May 28, 2014 at 23:46
• @TheSecretImbecile, What data structure are you thinking of using for the grid? Commented May 29, 2014 at 23:21