There are many common algorithms that we use constantly: searching, filtering, mapping, and so forth. Today we’ll write a few in the Burst-friendly way as examples of how to write Burst-friendly code that’s still reusable and efficient.

###### Overview

All of today’s algorithms are very easy to write and common to use. They’re patterned after the Burst-friendly generic algorithm style explored in depth in this article, but without the complication of the jobs system. They’re generic enough to swap in different types, but not so super generic that they allow any kind of collection. These should serve as examples for how to write this style of generic algorithm, not form the bedrock of a generic algorithm library on which a game is built.

With that in mind, let’s start looking at the algorithms…

###### IndexOf

First up, let’s write an algorithm that finds the index of an element in a `NativeArray<T>`:

```public static class Algorithms
{
public static int IndexOf<T>(this NativeArray<T> array, in T item)
where T : struct, IEquatable<T>
{
for (int i = 0; i < array.Length; ++i)
{
if (array[i].Equals(item))
{
return i;
}
}
return -1;
}
}```

Even with such a simple algorithm, there are a few things to note here. First, this is an extension method because it’s `static` and its first parameter is prefixed with `this`. This makes it appear as though `NativeArray<T>` had an `IndexOf` method built right into it, but it doesn’t because this method is actually declared here and only has access to the `public` API.

Second, the elements of type `T` might actually be large and expensive to copy types. We simply don’t know when we’re writing this function whether `T` is an `int` or a `ReallyBigStruct`. To be safe, we take the `item` to search for as an `in` parameter. This means a pointer is passed to it rather than a copy and `IndexOf` isn’t allowed to modify the `T` it points to.

Lastly, we insist that `T` implements `IEquatable<T>`. This means that `T` must have a `bool Equals(T)` method. All primitives have this and it’s easy to add to any custom `struct` types. Many already have it.

Now let’s go ahead and use this algorithm:

```void UseIndexOf()
{
NativeArray<int> array = new NativeArray<int>(3, Allocator.Temp);
array = 10;
array = 10;
array = 20;

Debug.Log(array.IndexOf(10)); // 0
Debug.Log(array.IndexOf(30)); // -1
}```

Here we see that we can call `array.IndexOf(10)` instead of `Algorithms.IndexOf(array, 10)` because `IndexOf` is an extension method. We can use the latter form, but the former is more compact and allows some tricks that we’ll see later on.

It’s worth noting that there’s no call to `array.Dispose`. That’s because there’s no need to do this.

###### Filter

Now let’s make an algorithm that filters the elements of an input array into an output array. All the elements that pass a test are written to the output array. All the elements that don’t pass the test are simply skipped.

```public static class Algorithms
{
public interface IFilterPredicate<T>
where T : struct
{
bool Check(in T item);
}

public static NativeArray<T> Filter<T, TFilterPredicate>(
this NativeArray<T> input,
NativeArray<T> output,
in TFilterPredicate predicate,
out int numFiltered)
where T : struct
where TFilterPredicate : IFilterPredicate<T>
{
int destIndex = 0;
for (int i = 0; i < input.Length; ++i)
{
T cur = input[i];
if (predicate.Check(cur))
{
output[destIndex] = cur;
destIndex++;
}
}
numFiltered = destIndex;
return output;
}
}```

The core of the algorithm is very simple, but the surrounding structure is more complex. Let’s take it one bit at a time.

First, we define the `IFilterPredicate<T>` interface as a way of requiring a `bool Check(in T)` function. We can’t use the more standard .NET `Predicate<T>` type because it’s a delegate and delegates aren’t allowed in Burst-compiled code. This interface, on the other hand, can be implemented by any `struct` and that’s OK in Burst-compiled code.

Second, we define `Filter` with both `T` and `TFilterPredicate` type parameters. `Filter` actually takes a `TFilterPredicate` rather than an `IFilterPredicate<T>`. With just that, the `TFilterPredicate` would be useless to us, so we add the `where TFilterPredicate : IFilterPredicate<T>` generic constraint to ensure that `TFilterPredicate` can be used like any `IFilterPredicate<T>`.

This combination of type parameter and interface is the trick that makes the code acceptable to Burst. Just taking an `IFilterPredicate<T>` wouldn’t tell Burst what type is being passed since that could be decided at runtime. On the contrary, `TFilterPredicate` must be known at compile time and Burst therefore knows which `bool Check(in T)` function to call.

Third, we output the number of `NativeArray<T>` elements that passed through the filter in an `out` parameter. We could tell the caller this number using a return value, but we’re using the return value to return the output array instead. This allows a neat trick we’ll see later on.

Now let’s try out this algorithm:

```struct EvenPredicate : Algorithms.IFilterPredicate<int>
{
public bool Check(in int item)
{
return (item & 1) == 0;
}
}

void UseFilter()
{
NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
input = 2;
input = 3;
input = 4;
NativeArray<int> output = new NativeArray<int>(3, Allocator.Temp);

int numFiltered;
input.Filter(output, new EvenPredicate(), out numFiltered);

for (int i = 0; i < numFiltered; ++i)
{
Debug.Log(output[i]); // 2, 4
}
}```

First we needed to define `EvenPredicate` as the code that determines whether array elements pass through the filter or not. Then we can pass an instance of this struct to `Filter`. Since it has no fields, we just instantiate one whenever we need it as there’s really no cost to doing so and it keeps the number of variables down.

###### Map

Next up we have `Map`. This function converts all of the elements of an input array and writes them to an output array. Note that the types of elements in the input array don’t need to be the same types of elements in the output array.

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

Here we’ve created another interface: `IMapper<TFrom, TTo>` This has the `TTo Map(in TFrom)` method that does the mapping. In the `Map` method, we call this and pass elements of the `input` array in as the parameter, then write the return value to `output` array.

Here’s how to use `Map`:

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

void UseMap()
{
NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
input = 2;
input = 3;
input = 4;
NativeArray<float> output = new NativeArray<float>(3, Allocator.Temp);

input.Map(output, new SqrtMapper());

for (int i = 0; i < output.Length; ++i)
{
Debug.Log(output[i]); // 1.414214, 1.732051, 2
}
}```

In this example, we’re mapping from `int` to `float` by using `math.sqrt` to take the square root of every element.

###### Map and Filter

Finally, let’s combine `Map` with `Filter`. No new generic algorithms need to be created for this, so we’ll just write code to use the existing functions in `Algorithms` and the existing `SqrtMapper`:

```struct LessThanPredicate : Algorithms.IFilterPredicate<float>
{
public float N;

public bool Check(in float item)
{
return item < N;
}
}

void UseMapAndFilter()
{
NativeArray<int> input = new NativeArray<int>(3, Allocator.Temp);
input = 2;
input = 3;
input = 4;
NativeArray<float> mapped = new NativeArray<float>(3, Allocator.Temp);
NativeArray<float> filtered = new NativeArray<float>(3, Allocator.Temp);

int numFiltered;
input
.Map(mapped, new SqrtMapper())
.Filter(filtered, new LessThanPredicate { N = 2 }, out numFiltered);

for (int i = 0; i < numFiltered; ++i)
{
Debug.Log(mapped[i]);
}
}```

`LessThanPredicate` puts a twist on `IFilterPredicate` by including a threshold field: `N`. When we call `Filter`, we create a `LessThanPredicate` and pass in the threshold. When `Check` is called, this field can be used to determine whether `item` is less than the threshold.

We also finally see the use of returning `NativeArray` from the generic algorithm functions and for making them all extensions methods. The combination of these has allowed us to chain together the function calls in what’s usually considered an intuitive fashion:

```int numFiltered;
input
.Map(mapped, new SqrtMapper())
.Filter(filtered, new LessThanPredicate { N = 2 }, out numFiltered);```

If we hadn’t designed the generic functions like this, we would have instead written these calls:

```Algorithms.Map(input, mapped, new SqrtMapper());
int numFiltered = Algorithms.Filter(
mapped,
filtered,
new LessThanPredicate { N = 2 });```

This style is a little more verbose and the reader needs to scan the text a little to find the verbs `Map` and `Filter` to know what’s happening. There’s no one right way, so feel free to design with either style depending on personal tastes.

###### Conclusion

The combination of type parameters, interfaces, and generic constraints allows us to easily write Burst-compatible generic algorithms. The result is quite readable and easy to use without sacrificing any performance compared to writing the same code manually over and over. So keep your eyes open for repetitive tasks: there just might be an opportunity to reduce code duplication with a generic algorithm!