2
\$\begingroup\$

I'm trying to keep a list of (Minecraft style) blocks in 3D space. The world loads at the origin (0, 0, 0) and blocks may be added in any direction including at negative indices.

In order to support this I wrote a custom data structure which supports getting and setting like this:

ThreeDimensionalList[0, 0, 0]

I'm not sure what I've written is the best approach but since the blocks/items can be added at any time it makes sense to me to keep them in a list, even when most of the items are null.

The data structure should support quick enumeration and location of items and null items should be used where the item hasn't been set. I'm fairly sure there's a much nicer way to express the same concept. Here's what I have.

using System;
using System.Collections;
using System.Collections.Generic;
using JetBrains.Annotations;

public class ThreeDimensionalList<T> : IEnumerable<T> where T : class
{
    private readonly InfiniteList<InfiniteList<InfiniteList<T>>> content;

    [CanBeNull]
    public T this[int x, int y, int z]
    {
        get
        {
            var row = content[x];

            var column = row?[y];

            return column?[z];
        }
        set
        {
            var xList = content[x];

            if (xList == null)
            {
                content[x] = new InfiniteList<InfiniteList<T>>();
                xList = content[x];
            }

            var yList = xList[y];

            if (yList == null)
            {
                xList[y] = new InfiniteList<T>();
                yList = xList[y];
            }

            yList[z] = value;
        }
    }

    public ThreeDimensionalList()
    {
        content = new InfiniteList<InfiniteList<InfiniteList<T>>>();
    }


    public IEnumerator<T> GetEnumerator()
    {
        foreach (var xList in content)
        {
            if (xList == null)
            {
                continue;
            }

            foreach (var yList in xList)
            {
                if (yList == null)
                {
                    continue;
                }

                foreach (var zItem in yList)
                {
                    yield return zItem;
                }
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class InfiniteList<T> : IEnumerable<T> where T : class
{
    private readonly List<T> positive;
    private readonly List<T> negative;

    [CanBeNull]
    public T this[int index]
    {
        get
        {
            if (index >= positive.Count)
            {
                return null;
            }

            if (index < 0 && Math.Abs(index) > negative.Count)
            {
                return null;
            }

            if (index >= 0)
            {
                return positive[index];
            }

            return negative[Math.Abs(index) - 1];
        }
        set
        {
            var list = index >= 0 ? positive : negative;
            var targetIndex = index >= 0 ? index : Math.Abs(index) - 1;

            PlaceItemAtIndex(list, targetIndex, value);
        }
    }

    public InfiniteList()
    {
        positive = new List<T>();
        negative = new List<T>();
    }

    private void PlaceItemAtIndex(List<T> list, int index, T item)
    {
        if (list.Count > index)
        {
            list[index] = item;
            return;
        }

        var missingCount = index - (list.Count - 1);

        for (int i = 0; i < missingCount; i++)
        {
            list.Add(null);
        }

        list[index] = item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        if (negative.Count > 0)
        {
            for (int i = negative.Count - 1; i >= 0; i--)
            {
                yield return negative[i];
            }
        }

        for (int i = 0; i < positive.Count; i++)
        {
            yield return positive[i];
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}
\$\endgroup\$
2
\$\begingroup\$

Suggestions

There are a few things you can improve.

  • start by not calling it a List because it isn't one but a Collection. A list has a different interface and should be confused
  • internally you can use a helper method List(int index) to get the actual list you need to work with so that you don't have to check the same condition everywhere
  • PlaceItemAtIndex should be simply called Add
  • to add empty elements you can use Enumerable.Repeat and remove even more ifs
  • to get items you can use ElementAtOrDefault
  • the where T : class constraint is not necessary, use default(T) instead so that you can work with all types
  • there's a bug in GetEnumerator because it'll return the 0 item for the negative list >= 0 which is actually in the positive list.

Example:

public class InfiniteCollection<T> : IEnumerable<T>
{
    private readonly List<T> positive;
    private readonly List<T> negative;

    public InfiniteCollection()
    {
        positive = new List<T>();
        negative = new List<T>();
    }

    public T this[int index]
    {
        get => List(index).ElementAtOrDefault(Math.Abs(index));
        set => Add(value, index);
    }

    private List<T> List(int index) => index < 0 ? negative : positive;

    private void Add(T item, int index)
    {
        var list = List(index);
        var missingCount = Math.Abs(index) - (list.Count - 1);
        list.AddRange(Enumerable.Repeat(default(T), missingCount));
        list[Math.Abs(index)] = item;
        return;
    }

    public IEnumerator<T> GetEnumerator()
    {
        for (var i = negative.Count - 1; i > 0; i--)
        {
            yield return negative[i];
        }

        for (var i = 0; i < positive.Count; i++)
        {
            yield return positive[i];
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Alternative

If you can live without the empty or dummy elements then you can replace the InfiniteCollection with SortedDictionary which

Represents a collection of key/value pairs that are sorted on the key.

This will allow you to iterate over the items in the index order.

If you can use C# 7, your Collection3D can be made really nice and clean.

public class Collection3D<T> : IEnumerable<T> 
{
    private readonly SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, T>>> xdic;

    public Collection3D()
    {
        xdic = new SortedDictionary<int, SortedDictionary<int, SortedDictionary<int, T>>>();
    }

    public T this[int x, int y, int z]
    {
        get
        {
            return 
                xdic.TryGetValue(x, out var ydic) &&
                ydic.TryGetValue(y, out var zdic) &&
                zdic.TryGetValue(z, out var value) 
                    ? value 
                    : default(T);           
        }
        set
        {
            if (!xdic.TryGetValue(x, out var ydic)) 
            {
                xdic[x] = (ydic = new SortedDictionary<int, SortedDictionary<int, T>>());
            }

            if (!ydic.TryGetValue(y, out var zdic))
            {
                ydic[y]= (zdic = new SortedDictionary<int, T>());
            }

            zdic[x] = value;
        }
    }

    public IEnumerator<T> GetEnumerator()
    {           
        foreach (var ydic in xdic.Values)
        {
            foreach (var zdic in ydic.Values)
            {
                foreach (var value in zdic.Values)
                {
                    yield return value;
                }
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Example:

var sdic = new Collection3D<string>();
sdic[0, 1, -2] = "foo";
sdic[0, 2, -2] = "baz";
sdic[1, -3, 3] = "bar";
sdic.Dump();

Result:

foo
baz
bar
\$\endgroup\$
  • 1
    \$\begingroup\$ Wasn't there supposed to be something like out var in C# 7? \$\endgroup\$ – Tamoghna Chowdhury May 28 '17 at 8:51
  • \$\begingroup\$ Also, wild you like to add anything about other representations? Odd-even indexing for handling negative indices, and emulating a multidimensional list by doing index manipulation on a single list (probably a bit more efficient?) \$\endgroup\$ – Tamoghna Chowdhury May 28 '17 at 8:53
  • \$\begingroup\$ @TamoghnaChowdhury out var - oh, I'm puzzled, how could I have missed that one? I didn't know it ;-) as to the other question I'm afraid don't know what you mean. \$\endgroup\$ – t3chb0t May 28 '17 at 9:00
  • \$\begingroup\$ Would you like to put in out var in the TryGetValue calls? That should help with the horribly verbose and redundant type specifiers. As for the other question, that was just a reference to a general technique used with multidimensional arrays for improving cache locality (the OP intends for the code to be used in a game, and for that performance is a concern). \$\endgroup\$ – Tamoghna Chowdhury May 28 '17 at 9:59
  • 2
    \$\begingroup\$ @TamoghnaChowdhury you cannot use index manipulation on a single list/array here because it's not a multidimensional array but a jagged one, the jumps are not equal and with dictionaries it shouldn't matter. On the other hand there is no longer any noticable and measurable difference in accessing multidimensional and jagged arrays. This bug has been fixed. \$\endgroup\$ – t3chb0t May 28 '17 at 10:05

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.