We looked at some generic algorithm examples in the previous article, but they weren’t very generic in one respect: they all required a NativeArray<T>. What if we wanted to make them more generic so they could work on any type of collection? Today’s article shows two ways to do just that!

IIndexedCollection

Today we’ll use the Map algorithm from last time as our example generic algorithm. Here’s how it looks with NativeArray<T> required:

public static class Algorithms
{
    public interface IMapper<TFrom, TTo>
        where TFrom : struct
        where TTo : struct
    {
        TTo Map(in TFrom item);
    }
 
    public static NativeArray<TTo> Map<TFrom, TTo, TMapper>(
        this NativeArray<TFrom> input,
        NativeArray<TTo> output,
        in TMapper mapper)
        where TFrom : struct
        where TTo : struct
        where TMapper : IMapper<TFrom, TTo>
    {
        for (int i = 0; i < input.Length; ++i)
        {
            output[i] = mapper.Map(input[i]);
        }
        return output;
    }
}

The first way we’ll abstract NativeArray<T> is to create an interface that describes the functionality Map is actually using from NativeArray<T>. It’s actually just one get property and one get and set indexer:

public interface IIndexedCollection<T>
{
    int Length { get; }
    T this[int index] { get; set; }
}

Now we can change Map to use IIndexedCollection<T> instead of NativeArray<T>. In doing so, we’ll need to add new TIndexedCollectionFrom and TIndexedCollectionTo type parameters with the appropriate constraints. The body of the function remains untouched!

public static TIndexedCollectionTo Map<
    TIndexedCollectionFrom,
    TIndexedCollectionTo,
    TFrom,
    TTo,
    TMapper>(
        this TIndexedCollectionFrom input,
        TIndexedCollectionTo output,
        in TMapper mapper)
    where TIndexedCollectionFrom : IIndexedCollection<TFrom>
    where TIndexedCollectionTo : IIndexedCollection<TTo>
    where TFrom : struct
    where TTo : struct
    where TMapper : IMapper<TFrom, TTo>
{
    for (int i = 0; i < input.Length; ++i)
    {
        output[i] = mapper.Map(input[i]);
    }
    return output;
}

To use this, we’ll need the IMapper<TFrom, TTo> from last time:

struct SqrtMapper : Algorithms.IMapper<int, float>
{
    public float Map(in int item)
    {
        return math.sqrt(item);
    }
}

And we’ll need an IIndexedCollection<T> that wraps NativeArray<T>:

struct NativeArrayIndexedCollection<T> : Algorithms.IIndexedCollection<T>
    where T : struct
{
    public NativeArray<T> Array;
 
    public NativeArrayIndexedCollection(NativeArray<T> array)
    {
        Array = array;
    }
 
    public static implicit operator NativeArrayIndexedCollection<T>(
        NativeArray<T> array)
    {
        return new NativeArrayIndexedCollection<T>(array);
    }
 
    public static implicit operator NativeArray<T>(
        NativeArrayIndexedCollection<T> collection)
    {
        return collection.Array;
    }
 
    public int Length => Array.Length;
 
    public T this[int index]
    {
        get => Array[index];
        set => Array[index] = value;
    }
}

This holds a NativeArray<T> as its only field and implements the required property and indexer by simply calling the corresponding NativeArray<T> functions. The constructor and type conversion functions are just there for convenience, as we’re about to see.

The final step is to actually call Map:

NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
input[0] = 2;
input[1] = 3;
input[2] = 4;
NativeArray<float> output = new NativeArray<float>(3, Allocator.Temp);
 
new NativeArrayIndexedCollection<int>(input).Map<
    NativeArrayIndexedCollection<int>,
    NativeArrayIndexedCollection<float>,
    int,
    float,
    SqrtMapper>(
    output,
    new SqrtMapper());
 
for (int i = 0; i < output.Length; ++i)
{
    Debug.Log(output[i]); // 1.414214, 1.732051, 2
}

First, we wrap input into a NativeArrayIndexedCollection<int> by calling the constructor. Second, we have to specify all the type parameters because the C# compiler can’t infer them. Third, we don’t need to call the constructor for output because we defined an implicit conversion function and the compiler will therefore call the conversion code for us.

This uses the extension method calling style, but we can just as easily call Map explicitly`:

Algorithms.Map<
    NativeArrayIndexedCollection<int>,
    NativeArrayIndexedCollection<float>,
    int,
    float,
    SqrtMapper>(
    input,
    output,
    new SqrtMapper());

In this version, there’s no need to explicitly call the constructor for input because the implicit conversion function will do that for us. On the other hand, we need to spell out Algorithms.Map instead of just Map.

IForwardIterator

The first approach still requires a collection that can be indexed into. What if we wanted to go further and allow any collection that can be iterated through? That would be similar to how foreach works with any type of collection and would allow other native collections to be used.

To relax these restrictions, we’ll use this interface instead of IIndexedCollection<T>:

public interface IForwardIterator<T, TForwardIterator>
    : IEquatable<TForwardIterator>
    where TForwardIterator : IForwardIterator<T, TForwardIterator>
{
    T Value { get; set; }
    void Next();
}

With an IForwardIterator<T, TForwardIterator>, all we can do is get the current value instead of the value at any index. To move forward to subsequent values, we can call Next. We can also know if two iterators are equal because we implemented IEquatable<TForwardIterator>.

Rewriting Map with this interface requires more changes than just swapping IIndexedCollection<T> for IForwardIterator<T, TForwardIterator>. First, we need to take two IForwardIterator<T, TForwardIterator> parameters to specify the input. This is because we need to know where to start and where to stop because we can’t index at 0 and stop at Length - 1 now that we don’t have the ability to index or the Length property.

Second, we need to rewrite the body of the function to do away with the index-based looping strategy. Instead, we’ll call Next on inputStart until it equals inputEnd:

public static TForwardIteratorTo Map<
    TForwardIteratorFrom,
    TForwardIteratorTo,
    TFrom,
    TTo,
    TMapper>(
        this TForwardIteratorFrom inputStart,
        TForwardIteratorFrom inputEnd,
        TForwardIteratorTo output,
        in TMapper mapper)
    where TForwardIteratorFrom
        : IForwardIterator<TFrom, TForwardIteratorFrom>
    where TForwardIteratorTo : IForwardIterator<TTo, TForwardIteratorTo>
    where TFrom : struct
    where TTo : struct
    where TMapper : IMapper<TFrom, TTo>
{
    for (; !inputStart.Equals(inputEnd); inputStart.Next(), output.Next())
    {
        output.Value = mapper.Map(inputStart.Value);
    }
    return output;
}

We can keep using SqrtMapper, but we’ll need to define a NativeArrayIterator<T> in order to call Map:

struct NativeArrayIterator<T>
    : Algorithms.IForwardIterator<T, NativeArrayIterator<T>>
    where T : struct
{
    public NativeArray<T> Array;
    public int Index;
 
    public NativeArrayIterator(NativeArray<T> array, int index)
    {
        Array = array;
        Index = index;
    }
 
    public bool Equals(NativeArrayIterator<T> other) =>
        Array.Equals(other.Array) && Index == other.Index;
 
    public T Value
    {
        get => Array[Index];
        set => Array[Index] = value;
    }
 
    public void Next()
    {
        Index++;
    }
}

Again, we’re just wrapping the functionality of NativeArray<T> into a struct that implements the required interface. One key difference is that the iterator must now contain the index into the array. This is because it’s not passed into the indexer anymore and the Next function is espected to keep track of it for the next Value get call.

It’s also helpful to have a couple of extension methods to get iterators at the beginning and one-past-the-end of a NativeArray<T>. These need to be in their own static class due to C# language rules:

static class NativeArrayForwardIteratorExtensions
{
    public static NativeArrayIterator<T> Begin<T>(
        this NativeArray<T> array)
        where T : struct
    {
        return new NativeArrayIterator<T>(array, 0);
    }
 
    public static NativeArrayIterator<T> End<T>(
        this NativeArray<T> array)
        where T : struct
    {
        return new NativeArrayIterator<T>(array, array.Length);
    }
}

Finally, we can use these tools to call Map:

NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
input[0] = 2;
input[1] = 3;
input[2] = 4;
NativeArray<float> output = new NativeArray<float>(3, Allocator.Temp);
 
input.Begin().Map<
    NativeArrayIterator<int>,
    NativeArrayIterator<float>,
    int,
    float,
    SqrtMapper>(
    input.End(),
    output.Begin(),
    new SqrtMapper());
 
for (int i = 0; i < output.Length; ++i)
{
    Debug.Log(output[i]); // 1.414214, 1.732051, 2
}

We still have to pass all the type parameters because the C# compiler won’t infer their types. Again, we can explicitly call Map rather than calling it as an extension method:

Algorithms.Map<
    NativeArrayIterator<int>,
    NativeArrayIterator<float>,
    int,
    float,
    SqrtMapper>(
    input.Begin(),
    input.End(),
    output.Begin(),
    new SqrtMapper());
Conclusion

Today we’ve seen two ways to make our generic algorithms more generic. We can abstract the collection type with another use of the “interface and type parameter” combination that enables Burst compilation. We can even abstract the fact that the collection is indexed by moving the indexing into an iterator type. The results are unfortunately marred by the requirement to pass all the type parameters, but aside from this verbosity the algorithm itself is now usable across a wide range of collection types.

Note: Burst 1.2.3 on Unity 2019.3.9f1 crashes with either of these approaches. Hopefully the bug will be fixed soon.