Data Structures – Handling Grids with Negative Indices in C#

arraycdata structures

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?

Best Answer

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.

Related Solutions

Ideal data structure for storing map data

The typical way to store geographic data is with a spatial data structure such as an R-tree (or some variant, such as R+tree, R*tree, etc.) This is how geographic data types are normally implemented in GIS-capable RDBMS. (I know both Microsoft's SQL Server 2008 and PostGIS use R-trees for the geographic types.) They meet all of the basic requirements you've described, and trivially support intersection, location, distance, and other query types.

Depending on the type of data, you may also find such things as kD-trees, quad-trees, octrees, bounding volume hierarchies (including axis-aligned bounding box trees), etc. in common use. This is actually much more commonplace in 3D games, since the size and shape of an object is more relevant to intersection queries. They're less often used for GIS than R-trees.

C# – Ideal data structure/techniques for storing generic scheduler data in C#

I don't think this is too tough. What am I missing?

using System;
using System.Collections.Generic;

public class ScheduledPerson {
    public string Name {get; set;}

    public Dictionary<string, Object> Fields {
        get { return _fields; }
        set { _fields = value; }
    }
    private Dictionary<string, Object> _fields = new Dictionary<string, Object>();

    public List<Tuple<DateTime, DateTime>> Events {
        get { return _events; }
        set { _events = value; }
    }
    private List<Tuple<DateTime, DateTime>> _events = new List<Tuple<DateTime, DateTime>>();

    public ScheduledPerson(string name){
        Name = name;
    }
}

I don't see a good way to make our ScheduledPerson classes generic, as it seems the fields can be anything. I'm storing the field values as Objects, as I see nothing that requires them to be dynamics. Just make sure all field value types have a sensible ToString() implementation.

If you want Events to be a List of DateRange or of your own Event class instead of Tuple, feel free.

It then remains for you to write a separate class to render each ScheduledPerson in a table, along with figuring out all the headers from all ScheduledPerson records. It you are dealing with ten thousand people, you'll want a better solution that has all the headers stored, but for most applications, it won't be too bad to enumerate all the Fields on all the ScheduledPersons to figure out the headers.

Related Topic