3

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?

  • 5
    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. – Robert Harvey May 27 '14 at 22:45
  • Does unknown mean unknown until creation or may expand infinitely in any direction? – Blrfl May 28 '14 at 11:53
  • Dictionary would be easy. – Austin Henley May 28 '14 at 19:52
  • @Blrfl starts small and may expand infinitely – The Secret Imbecile May 28 '14 at 23:56
3

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.

  • 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. – Dan Lyons May 28 '14 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. – Robert Harvey May 28 '14 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]. – Dan Lyons May 28 '14 at 17:47
  • @DanLyons: I'm hobbled by the fact that my IDE is on a different computer than my Internet (for security reasons). – Robert Harvey May 28 '14 at 17:48
  • Shouldn't that Activator note be removed now that the code doesn't use it? – svick May 28 '14 at 19:46
1

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) – The Secret Imbecile May 28 '14 at 23:46
  • @TheSecretImbecile, What data structure are you thinking of using for the grid? – R Sahu May 29 '14 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.