JacksonDunstan.com

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(N²). 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;
			}
		};
 
		// GetAdvanced
		Log("advance 1 from begin: " + arr.Begin().GetAdvanced(1).GetCurrent());
 
		// 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
		);
 
		// AdjacentFind
		Log("adjacents at index: " + arr.Begin().AdjacentFind(arr.End(), 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().GetAdvanced(1).GetCurrent();
		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().AdjacentFind(arr.End(), 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
adjacents at index: 4
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:

Iterators GC Alloc Profile

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!

#1 by Leucaruth on July 19th, 2016 · Reply

Thanks for your articles, they are helping me a lot.

There aren’t that many blogs with such an high level content like yours.

Regards

#2 by jackson on July 19th, 2016 · Reply

Happy to help! Please let me know if there’s anything in particular you’d like to see articles about.

Enumerables Without the Garbage: Part 5

Comments