This week we continue with iterators to get the functionality of `IEnumerable` without the nasty garbage creation. This week the little iterator library gets support for sorting and binary searching. Read on for the details!

The “sorting” and “binary search” categories again come courtesy of C++’s <algorithm> header. They have the normal functions you probably expect, but also a lot of lesser-used tools. Here’s sorting:

• `Sort`: sort a range
• `StableSort`: sort while preserving relative order when there are ties
• `PartialSort`: sort up to a point
• `PartialSortCopy`: copy the smallest values to another range
• `IsSorted`: check if a range is sorted
• `IsSortedUntil`: get the point where a range stops being sorted
• `NthElement`: make the N-th element sorted properly with lesser values placed before and greater values placed after

And here are the binary search functions. Keep in mind that these all require a sorted range.

• `LowerBound`: find the first element greater than or equal to a value
• `UpperBound`: find the first element greater than a value
• `EqualRange`: find a sub-range of equal values in a range
• `BinarySearch`: find a value

There are a couple of caveats to mention regarding the implementation for this week. First, `StableSort` is implemented with an insertion sort which can be as slow as `O(N2)`. There are faster stable sorts such as merge sort, but none that I could find in time that don’t require creating garbage for temporary space.

Second, I implemented `PartialSort` and `NthElement` by simply sorting the whole range. That’s obviously slower than it could otherwise be, but at least it doesn’t create any garbage.

Third, I’ve omitted `PartialSortCopy` since I don’t currently know of an efficient way to implement it in all cases without creating any garbage.

If you know of a way around any of these issues, please let me know in the comments!

Now we’ll build again on the test app from the previous articles in this series. This shows the usage of each of the above functions, demonstrates their correctness, and proves that none of this creates any garbage whatsoever. If you’ve read all the previous articles then you might want to start reading at the `Sort` function.

```using System;
using System.Linq;

using UnityEngine;

public class TestScript : MonoBehaviour
{
private static readonly System.Random random = new System.Random();
private static readonly int[] defaultArr = { 1, 2, 2, 3 };
private static readonly int[] arr = defaultArr.ToArray();
private static readonly int[] arr2 = new int[arr.Length];
private static readonly int[] arr3 = new int[arr.Length];
private static readonly Func<int, int, bool> AreIntsEqual = (a, b) => a == b;
private static readonly Func<int, bool> IsIntEven = i => i % 2 == 0;
private static readonly Func<int, bool> IsIntEqualTo2 = i => i == 2;
private static readonly Func<int, bool> IsIntLessThanOrEqualTo2 = i => i <= 2;
private static readonly Func<int, bool> IsIntGreaterThan0 = i => i > 0;
private static readonly Func<int, bool> IsIntGreaterThan10 = i => i > 10;
private static readonly Func<int, int> DoubleInt = i => i * 2;
private static readonly Func<int, int, int> MultiplyInts = (a, b) => a * b;
private static readonly Func<int, int, bool> IsIntGreaterThanInt = (a, b) => a > b;
private static readonly Func<int, int, bool> IsIntLessThanInt = (a, b) => a < b;
private static readonly Action<int> NoOp = i => { };
private static readonly Func<int, int> RandomIntLessThan = max => random.Next(max);
private static int[] OneThreeThreeFour = { 1, 3, 3, 4 };
private static int[] OneThreeTwoFour = { 1, 3, 2, 4 };
private static int[] ThreeThreeOneTwo = { 3, 3, 1, 2 };
private static int[] ThreeTwoOneTwo = { 3, 2, 1, 2 };
private static int[] TwoThree = { 2, 3 };

void Start()
{
GcTest();
Debug.Log(Test());
}

string Test()
{
var log = "";
Action<string> Log = msg => log += msg + "\n";
Func<int[], string> ArrayToString = a => "[" + string.Join(
", ",
a.Select(i => i.ToString()).ToArray()
) + "]";
Action ResetArrays = () => {
for (var i = 0; i < arr.Length; ++i)
{
arr[i] = defaultArr[i];
arr2[i] = 0;
arr3[i] = 0;
}
};

// Distance
Log("distance from first to last: " + arr.Begin().Distance(arr.End()));

// AllOf
Log("all even?: " + arr.Begin().AllOf(arr.End(), IsIntEven));
Log("all positive?: " + arr.Begin().AllOf(arr.End(), IsIntGreaterThan0));

// AnyOf
Log("any > 10?: " + arr.Begin().AnyOf(arr.End(), IsIntGreaterThan10));
Log("any == 2?: " + arr.Begin().AnyOf(arr.End(), IsIntEqualTo2));

// NoneOf
Log("none == 2?: " + arr.Begin().NoneOf(arr.End(), IsIntEqualTo2));
Log("none > 10?: " + arr.Begin().NoneOf(arr.End(), IsIntGreaterThan10));

// ForEach
log += "foreach: ";
arr.Begin().ForEach(arr.End(), i => log += i + " ");
log += "\n";

// Find
Log("find 2 at index: " + arr.Begin().Find(arr.End(), 2, AreIntsEqual).Index);

// FindIf
Log("first even at index: " + arr.Begin().FindIf(arr.End(), IsIntEven).Index);

// FindIfNot
Log("first not even at index: " + arr.Begin().FindIfNot(arr.End(), IsIntEven).Index);

// FindEnd
Log(
"end of [2,3] at index: "
+ arr.Begin().FindEnd(
arr.End(),
arr.IteratorAt(1),
arr.IteratorAt(2),
AreIntsEqual
).Index
);

// FindFirstOf
Log(
"first of [2,3] at index: "
+ arr.Begin().FindFirstOf(
arr.End(),
arr.IteratorAt(1),
arr.IteratorAt(2),
AreIntsEqual
).Index
);

// Count
Log("count 2s: " + arr.Begin().Count(arr.End(), 2, AreIntsEqual));

// CountIf
Log("count evens: " + arr.Begin().CountIf(arr.End(), IsIntEven));

// Mismatch
ArrayIterator<int> mm1;
ArrayIterator<int> mm2;
arr.Begin().Mismatch(
arr.End(),
new[] { 1, 3, 3, 4 }.Begin(),
AreIntsEqual,
out mm1,
out mm2
);
Log("mismatch with [1, 3, 3, 4] at: " + mm1.GetCurrent() + ", " + mm2.GetCurrent());

// Equal
Log(
"equal [1, 3, 2, 3]? "
+ arr.Begin().Equal(arr.End(), new[] { 1, 3, 2, 3 }.Begin(), AreIntsEqual)
);
Log(
"equal [1, 2, 2, 3]? "
+ arr.Begin().Equal(arr.End(), new[] { 1, 2, 2, 3 }.Begin(), AreIntsEqual)
);

// IsPermutation
Log(
"is permutation of [3, 3, 1, 2]? "
+ arr.Begin().IsPermutation(arr.End(), new[] { 3, 3, 1, 2 }.Begin(), AreIntsEqual)
);
Log(
"is permutation of [3, 2, 1, 2]? "
+ arr.Begin().IsPermutation(arr.End(), new[] { 3, 2, 1, 2 }.Begin(), AreIntsEqual)
);

// Search
var sub = new[] { 2, 3 };
Log(
"search found [2, 3] at index: "
+ arr.Begin().Search(arr.End(), sub.Begin(), sub.End(), AreIntsEqual).Index
);

// SearchN
Log(
"search 2 2s found at index: "
+ arr.Begin().SearchN(arr.End(), 2, 2, AreIntsEqual).Index
);

// Copy
ResetArrays();
Log(
"copy first two returns iterator at index "
+ arr.Begin().Copy(arr.IteratorAt(2), arr2.Begin()).Index
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// CopyN
ResetArrays();
Log(
"copyN first three returns iterator at index "
+ arr.Begin().CopyN(3, arr2.Begin()).Index
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// CopyIf
ResetArrays();
Log(
"copy evens returns iterator at index "
+ arr.Begin().CopyIf(arr.End(), arr2.Begin(), IsIntEven).Index
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// CopyBackward
ResetArrays();
Log(
"copy backward middle two returns iterator at index "
+ arr.IteratorAt(1).CopyBackward(arr.IteratorAt(3), arr2.End()).Index
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// SwapRanges
ResetArrays();
Log(
"swap middle two returns iterator at index "
+ arr.IteratorAt(1).SwapRanges(arr.IteratorAt(3), arr2.IteratorAt(1)).Index
+ ", arr now: "
+ ArrayToString(arr)
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// Swap
ResetArrays();
var itA = arr.IteratorAt(0);
var itB = arr.IteratorAt(1);
itA.Swap(itB);
Log("swap iterator at index 0 with iterator at index 1, arr now: " + ArrayToString(arr));

// Transform
ResetArrays();
Log(
"transform by doubling returns index "
+ arr.Begin().Transform(arr.End(), arr.Begin(), DoubleInt).Index
+ ", arr now: "
+ ArrayToString(arr)
);

// Transform
ResetArrays();
Log(
"transform by multiplying with self returns index "
+ arr.Begin().Transform(arr.End(), arr.Begin(), arr.Begin(), MultiplyInts).Index
+ ", arr now: "
+ ArrayToString(arr)
);

// ReplaceIf
ResetArrays();
arr.Begin().ReplaceIf(arr.End(), IsIntEqualTo2, 20);
Log("replace 2 with 20 " + ArrayToString(arr));

// ReplaceCopyIf
ResetArrays();
Log(
"replace evens with 200 returns iterator at index "
+ arr.Begin().ReplaceCopyIf(arr.End(), arr.Begin(), IsIntEven, 200).Index
+ ", arr now: "
+ ArrayToString(arr)
);

// Unique
ResetArrays();
Log(
"unique returns index "
+ arr.Begin().Unique(arr.End(), AreIntsEqual).Index
+ ", arr now: "
+ ArrayToString(arr)
);

// UniqueCopy
ResetArrays();
Log(
"unique copy returns index "
+ arr.Begin().UniqueCopy(arr.End(), arr2.Begin(), AreIntsEqual).Index
+ ", arr now: "
+ ArrayToString(arr)
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// Reverse
ResetArrays();
arr.Begin().Reverse(arr.End());
Log("reverse: " + ArrayToString(arr));

// ReverseCopy
ResetArrays();
Log(
"reverse copy returns index: "
+ arr.Begin().ReverseCopy(arr.End(), arr2.Begin()).Index
+ ", arr now: "
+ ArrayToString(arr)
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// Rotate
ResetArrays();
arr.Begin().Rotate(arr.IteratorAt(2), arr.End());
Log("rotate around second 2, arr now: " + ArrayToString(arr));

// RotateCopy
ResetArrays();
Log(
"rotate copy around second 2 returns index: "
+ arr.Begin().RotateCopy(arr.IteratorAt(2), arr.End(), arr2.Begin()).Index
+ ", arr now: "
+ ArrayToString(arr)
+ ", arr2 now: "
+ ArrayToString(arr2)
);

// RandomShuffle
ResetArrays();
arr.Begin().RandomShuffle(arr.End(), RandomIntLessThan);
arr.Begin().Copy(arr.End(), arr2.Begin());
arr2.Begin().RandomShuffle(arr2.End(), RandomIntLessThan);
Log("some random shuffles: " + ArrayToString(arr) + ", " + ArrayToString(arr2));

// IsPartitioned
ResetArrays();
Log(
"arr is partitioned by odd/even? "
+ arr.Begin().IsPartitioned(arr.End(), IsIntEven)
+ ", by <= 2? "
+ arr.Begin().IsPartitioned(arr.End(), IsIntLessThanOrEqualTo2)
);

// Partition
ResetArrays();
Log(
"partition by odd/even returns index: "
+ arr.Begin().Partition(arr.End(), IsIntEven).Index
+ ", arr now: "
+ ArrayToString(arr)
);

// PartitionCopy
ResetArrays();
ArrayIterator<int> outResultTrue;
ArrayIterator<int> outResultFalse;
arr.Begin().PartitionCopy(
arr.End(),
arr2.Begin(),
arr3.Begin(),
IsIntEven,
out outResultTrue,
out outResultFalse
);
Log(
"partition copy by odd/even returns indexes: "
+ outResultTrue.Index
+ ", "
+ outResultFalse.Index
+ ", arr now: "
+ ArrayToString(arr)
+ ", arr2 now: "
+ ArrayToString(arr2)
+ ", arr3 now: "
+ ArrayToString(arr3)
);

// PartitionPoint
ResetArrays();
Log(
"partition point for <= 2 returns index: "
+ arr.Begin().PartitionPoint(arr.End(), IsIntLessThanOrEqualTo2).Index
);

// Sort
ResetArrays();
arr.Begin().Sort(arr.End(), IsIntGreaterThanInt);
Log("sorted backwards: " + ArrayToString(arr));

// StableSort
ResetArrays();
arr.Begin().StableSort(arr.End(), IsIntGreaterThanInt);
Log("stable sorted backwards: " + ArrayToString(arr));

// PartialSort
ResetArrays();
arr.Begin().PartialSort(arr.IteratorAt(2), arr.End(), IsIntGreaterThanInt);
Log("partial sorted backwards up to index 2: " + ArrayToString(arr));

// IsSorted
ResetArrays();
Log("is array sorted: " + arr.Begin().IsSorted(arr.End(), IsIntLessThanInt));

// IsSorted
ResetArrays();
Log(
ArrayToString(OneThreeTwoFour)
+ " is sorted until: "
+ OneThreeTwoFour.Begin().IsSortedUntil(OneThreeTwoFour.End(), IsIntLessThanInt).Index
);

// NthElement
ResetArrays();
OneThreeTwoFour.Begin().Copy(OneThreeTwoFour.End(), arr.Begin());
arr.Begin().NthElement(arr.IteratorAt(2), arr.End(), IsIntLessThanInt);
Log(
"NthElement 2 on "
+ ArrayToString(OneThreeTwoFour)
+ ": "
+ ArrayToString(arr)
);

// LowerBound
ResetArrays();
Log(
"lower bound of 2 at index: "
+ arr.Begin().LowerBound(arr.End(), 2, IsIntLessThanInt).Index
);

// UpperBound
ResetArrays();
Log(
"upper bound of 2 at index: "
+ arr.Begin().UpperBound(arr.End(), 2, IsIntLessThanInt).Index
);

// EqualRange
ResetArrays();
ArrayIterator<int> equalRangeLower;
ArrayIterator<int> equalRangeUpper;
arr.Begin().EqualRange(
arr.End(),
2,
IsIntLessThanInt,
out equalRangeLower,
out equalRangeUpper
);
Log(
"equal range of 2 from index "
+ equalRangeLower.Index
+ " to "
+ equalRangeUpper.Index
);

// BinarySearch
ResetArrays();
Log("binary search finds 2? " + arr.Begin().BinarySearch(arr.End(), 2, IsIntLessThanInt));
Log("binary search finds 9? " + arr.Begin().BinarySearch(arr.End(), 9, IsIntLessThanInt));

return log;
}

void GcTest()
{
arr.Begin().Distance(arr.End());
arr.Begin().AllOf(arr.End(), IsIntEven);
arr.Begin().AllOf(arr.End(), IsIntGreaterThan0);
arr.Begin().AnyOf(arr.End(), IsIntGreaterThan10);
arr.Begin().AnyOf(arr.End(), IsIntEqualTo2);
arr.Begin().NoneOf(arr.End(), IsIntEqualTo2);
arr.Begin().NoneOf(arr.End(), IsIntGreaterThan10);
arr.Begin().ForEach(arr.End(), NoOp);
arr.Begin().Find(arr.End(), 2, AreIntsEqual);
arr.Begin().FindIf(arr.End(), IsIntEven);
arr.Begin().FindIfNot(arr.End(), IsIntEven);
arr.Begin().FindEnd(
arr.End(),
arr.IteratorAt(1),
arr.IteratorAt(2),
AreIntsEqual
);
arr.Begin().FindFirstOf(
arr.End(),
arr.IteratorAt(1),
arr.IteratorAt(2),
AreIntsEqual
);
arr.Begin().Count(arr.End(), 2, AreIntsEqual);
arr.Begin().CountIf(arr.End(), IsIntEven);
ArrayIterator<int> mm1;
ArrayIterator<int> mm2;
arr.Begin().Mismatch(
arr.End(),
OneThreeThreeFour.Begin(),
AreIntsEqual,
out mm1,
out mm2
);
arr.Begin().IsPermutation(arr.End(), ThreeThreeOneTwo.Begin(), AreIntsEqual);
arr.Begin().IsPermutation(arr.End(), ThreeTwoOneTwo.Begin(), AreIntsEqual);
arr.Begin().Search(arr.End(), TwoThree.Begin(), TwoThree.End(), AreIntsEqual);
arr.Begin().SearchN(arr.End(), 2, 2, AreIntsEqual);
arr.Begin().Copy(arr.IteratorAt(2), arr2.Begin());
arr.Begin().CopyN(3, arr2.Begin());
arr.Begin().CopyIf(arr.End(), arr2.Begin(), IsIntEven);
arr.IteratorAt(1).CopyBackward(arr.IteratorAt(3), arr2.End());
arr.IteratorAt(1).SwapRanges(arr.IteratorAt(3), arr2.IteratorAt(1));
var itA = arr.IteratorAt(0);
var itB = arr.IteratorAt(1);
itA.Swap(itB);
arr.Begin().Transform(arr.End(), arr.Begin(), DoubleInt);
arr.Begin().Transform(arr.End(), arr.Begin(), arr.Begin(), MultiplyInts);
arr.Begin().ReplaceIf(arr.End(), IsIntEqualTo2, 20);
arr.Begin().ReplaceCopyIf(arr.End(), arr.Begin(), IsIntEven, 200);
arr.Begin().Unique(arr.End(), AreIntsEqual);
arr.Begin().UniqueCopy(arr.End(), arr2.Begin(), AreIntsEqual);
arr.Begin().Reverse(arr.End());
arr.Begin().ReverseCopy(arr.End(), arr2.Begin());
arr.Begin().Rotate(arr.IteratorAt(2), arr.End());
arr.Begin().RotateCopy(arr.IteratorAt(2), arr.End(), arr2.Begin());
arr.Begin().RandomShuffle(arr.End(), RandomIntLessThan);
arr.Begin().Copy(arr.End(), arr2.Begin());
arr2.Begin().RandomShuffle(arr2.End(), RandomIntLessThan);
arr.Begin().IsPartitioned(arr.End(), IsIntEven);
arr.Begin().IsPartitioned(arr.End(), IsIntLessThanOrEqualTo2);
arr.Begin().Partition(arr.End(), IsIntEven);
ArrayIterator<int> outResultTrue;
ArrayIterator<int> outResultFalse;
arr.Begin().PartitionCopy(
arr.End(),
arr2.Begin(),
arr3.Begin(),
IsIntEven,
out outResultTrue,
out outResultFalse
);
arr.Begin().PartitionPoint(arr.End(), IsIntLessThanOrEqualTo2);
arr.Begin().Sort(arr.End(), IsIntGreaterThanInt);
arr.Begin().StableSort(arr.End(), IsIntGreaterThanInt);
arr.Begin().PartialSort(arr.IteratorAt(2), arr.End(), IsIntGreaterThanInt);
arr.Begin().IsSorted(arr.End(), IsIntLessThanInt);
OneThreeTwoFour.Begin().IsSortedUntil(OneThreeTwoFour.End(), IsIntLessThanInt);
OneThreeTwoFour.Begin().Copy(OneThreeTwoFour.End(), arr.Begin());
arr.Begin().NthElement(arr.IteratorAt(2), arr.End(), IsIntLessThanInt);
arr.Begin().LowerBound(arr.End(), 2, IsIntLessThanInt);
arr.Begin().UpperBound(arr.End(), 2, IsIntLessThanInt);
ArrayIterator<int> equalRangeLower;
ArrayIterator<int> equalRangeUpper;
arr.Begin().EqualRange(
arr.End(),
2,
IsIntLessThanInt,
out equalRangeLower,
out equalRangeUpper
);
arr.Begin().BinarySearch(arr.End(), 2, IsIntLessThanInt);
arr.Begin().BinarySearch(arr.End(), 9, IsIntLessThanInt);
}
}```

Here’s the output of this test app:

```advance 1 from begin: 2
distance from first to last: 4
all even?: False
all positive?: True
any > 10?: False
any == 2?: True
none == 2?: False
none > 10?: True
foreach: 1 2 3 4
find 2 at index: 1
first even at index: 1
first not even at index: 0
end of [2,3] at index: 1
first of [2,3] at index: 1
count 2s: 1
count evens: 2
mismatch with [1, 3, 3, 4] at: 2, 3
equal [1, 3, 2, 3]? False
equal [1, 2, 2, 3]? False
is permutation of [3, 3, 1, 2]? False
is permutation of [3, 2, 1, 2]? False
search found [2, 3] at index: 1
search 2 2s found at index: 4
copy first two returns iterator at index 2, arr2 now: [1, 2, 0, 0]
copyN first three returns iterator at index 3, arr2 now: [1, 2, 2, 0]
copy evens returns iterator at index 2, arr2 now: [2, 2, 0, 0]
copy backward middle two returns iterator at index 2, arr2 now: [0, 0, 2, 2]
swap middle two returns iterator at index 3, arr now: [1, 0, 0, 3], arr2 now: [0, 2, 2, 0]
swap iterator at index 0 with iterator at index 1, arr now: [2, 1, 2, 3]
transform by doubling returns index 4, arr now: [2, 4, 4, 6]
transform by multiplying with self returns index 4, arr now: [1, 4, 4, 9]
replace 2 with 20 [1, 20, 20, 3]
replace evens with 200 returns iterator at index 4, arr now: [1, 200, 200, 3]
unique returns index 3, arr now: [1, 2, 3, 3]
unique copy returns index 3, arr now: [1, 2, 2, 3], arr2 now: [1, 2, 3, 0]
reverse: [3, 2, 2, 1]
reverse copy returns index: 4, arr now: [1, 2, 2, 3], arr2 now: [3, 2, 2, 1]
rotate around second 2, arr now: [2, 3, 1, 2]
rotate copy around second 2 returns index: 4, arr now: [1, 2, 2, 3], arr2 now: [2, 3, 1, 2]
some random shuffles: [2, 3, 2, 1], [3, 2, 1, 2]
arr is partitioned by odd/even? False, by <= 2? True
partition by odd/even returns index: 2, arr now: [2, 2, 1, 3]
partition copy by odd/even returns indexes: 2, 2, arr now: [1, 2, 2, 3], arr2 now: [2, 2, 0, 0], arr3 now: [1, 3, 0, 0]
partition point for <= 2 returns index: 2
sorted backwards: [3, 2, 2, 1]
stable sorted backwards: [3, 2, 2, 1]
partial sorted backwards up to index 2: [3, 2, 2, 1]
is array sorted: True
[1, 3, 2, 4] is sorted until: 2
NthElement 2 on [1, 3, 2, 4]: [1, 2, 3, 4]
lower bound of 2 at index: 1
upper bound of 2 at index: 3
equal range of 2 from index 1 to 3
binary search finds 2? True
binary search finds 9? False```

Finally, here’s a screenshot of the `GcTest` function in Unity’s profiler in “deep” mode to prove that none of this creates any garbage whatsoever:

Check out the GitHub project for the `Iterator.cs` file that implements all of this. If you’ve got any questions about the iterator library or any suggestions on how to make it better, let me know in the comments!

Update: check out part six!