Back from a brief break, we pick up this week by finishing up the “modifying sequence operations” with some gems like RandomShuffle and go through the “partitions” category with functions like Partition and IsPartitioned. These are all solid algorithms with a lot of potential uses, so read on to see how to use them with iterators and for the source code that implements them!

Again we continue through C++’s <algorithm> header. Last week we’d gotten through the first half of the “modifying sequence operations” functions with the likes of Swap and ReplaceIf. This week we’ll finish off those functions with these:

  • Unique: remove duplicate elements
  • UniqueCopy: copy unique elements to another range
  • Reverse: reverse the elements in a range
  • ReverseCopy: reverse a range into another range
  • Rotate: rotate the elements of a range so that a mid point comes first
  • RotateCopy: rotate into another range
  • RandomShuffle: randomly shuffle the elements in a range

Note that I’ve omitted the shuffle function as I don’t know of a good way to get an even distribution of integers within a range with C# in Unity. If you do, let me know in the comments and I’ll add the function.

We’ll also go through the functions in the “partitions” category this week. These all utilize a function that defines the partition. For example, it could be function that tests is a number is even, a string isn’t empty, or a player is still alive. With a function like this we can do a lot of powerful things. Here are the available functions:

  • IsPartitioned: check if a range is already partitioned
  • Partition: partition a range so that all passing values are before failing values
  • PartitionCopy: partition into another range
  • PartitionPoint: get an iterator at the partition point

Note that I’ve omitted stable_partition for now as it’s quite complex. I’ll likely return to it later, but if you want to contribute an implementation then feel free to send me a pull request in the GitHub project.

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 Unique 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 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[] 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;
			}
		};
		Log("advance 1 from begin: " + arr.Begin().GetAdvanced(1).GetCurrent());
		Log("distance from first to last: " + arr.Begin().Distance(arr.End()));
		Log("all even?: " + arr.Begin().AllOf(arr.End(), IsIntEven));
		Log("all positive?: " + arr.Begin().AllOf(arr.End(), IsIntGreaterThan0));
		Log("any > 10?: " + arr.Begin().AnyOf(arr.End(), IsIntGreaterThan10));
		Log("any == 2?: " + arr.Begin().AnyOf(arr.End(), IsIntEqualTo2));
		Log("none == 2?: " + arr.Begin().NoneOf(arr.End(), IsIntEqualTo2));
		Log("none > 10?: " + arr.Begin().NoneOf(arr.End(), IsIntGreaterThan10));
		log += "foreach: ";
		arr.Begin().ForEach(arr.End(), i => log += i + " ");
		log += "\n";
		Log("find 2 at index: " + arr.Begin().Find(arr.End(), 2, AreIntsEqual).Index);
		Log("first even at index: " + arr.Begin().FindIf(arr.End(), IsIntEven).Index);
		Log("first not even at index: " + arr.Begin().FindIfNot(arr.End(), IsIntEven).Index);
		Log(
			"end of [2,3] at index: "
			+ arr.Begin().FindEnd(
				arr.End(),
				arr.IteratorAt(1),
				arr.IteratorAt(2),
				AreIntsEqual
			).Index
		);
		Log(
			"first of [2,3] at index: "
			+ arr.Begin().FindFirstOf(
				arr.End(),
				arr.IteratorAt(1),
				arr.IteratorAt(2),
				AreIntsEqual
			).Index
		);
		Log(
			"adjacents at index: "
			+ arr.Begin().AdjacentFind(arr.End(), AreIntsEqual).Index
		);
		Log("count 2s: " + arr.Begin().Count(arr.End(), 2, AreIntsEqual));
		Log("count evens: " + arr.Begin().CountIf(arr.End(), IsIntEven));
		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()
		);
		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)
		);
		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)
		);
		var sub = new[] { 2, 3 };
		Log(
			"search found [2, 3] at index: "
			+ arr.Begin().Search(arr.End(), sub.Begin(), sub.End(), AreIntsEqual).Index
		);
		Log(
			"search 2 2s found at index: "
			+ arr.Begin().SearchN(arr.End(), 2, 2, AreIntsEqual).Index
		);
		ResetArrays();
		Log(
			"copy first two returns iterator at index "
			+ arr.Begin().Copy(arr.IteratorAt(2), arr2.Begin()).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"copyN first three returns iterator at index "
			+ arr.Begin().CopyN(3, arr2.Begin()).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"copy evens returns iterator at index "
			+ arr.Begin().CopyIf(arr.End(), arr2.Begin(), IsIntEven).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		Log(
			"copy backward middle two returns iterator at index "
			+ arr.IteratorAt(1).CopyBackward(arr.IteratorAt(3), arr2.End()).Index
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		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)
		);
		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));
		ResetArrays();
		Log(
			"transform by doubling returns index "
			+ arr.Begin().Transform(arr.End(), arr.Begin(), DoubleInt).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		ResetArrays();
		Log(
			"transform by multiplying with self returns index "
			+ arr.Begin().Transform(arr.End(), arr.Begin(), arr.Begin(), MultiplyInts).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		ResetArrays();
		arr.Begin().ReplaceIf(arr.End(), IsIntEqualTo2, 20);
		Log("replace 2 with 20 " + ArrayToString(arr));
		ResetArrays();
		Log(
			"replace evens with 200 returns iterator at index "
			+ arr.Begin().ReplaceCopyIf(arr.End(), arr.Begin(), IsIntEven, 200).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		ResetArrays();
		Log(
			"unique returns index "
			+ arr.Begin().Unique(arr.End(), AreIntsEqual).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		ResetArrays();
		Log(
			"unique copy returns index "
			+ arr.Begin().UniqueCopy(arr.End(), arr2.Begin(), AreIntsEqual).Index
			+ ", arr now: "
			+ ArrayToString(arr)
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		arr.Begin().Reverse(arr.End());
		Log("reverse: " + ArrayToString(arr));
		ResetArrays();
		Log(
			"reverse copy returns index: "
			+ arr.Begin().ReverseCopy(arr.End(), arr2.Begin()).Index
			+ ", arr now: "
			+ ArrayToString(arr)
			+ ", arr2 now: "
			+ ArrayToString(arr2)
		);
		ResetArrays();
		arr.Begin().Rotate(arr.IteratorAt(2), arr.End());
		Log("rotate around second 2, arr now: " + ArrayToString(arr));
		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)
		);
		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));
		ResetArrays();
		Log(
			"arr is partitioned by odd/even? "
			+ arr.Begin().IsPartitioned(arr.End(), IsIntEven)
			+ ", by <= 2? "
			+ arr.Begin().IsPartitioned(arr.End(), IsIntLessThanOrEqualTo2)
		);
		ResetArrays();
		Log(
			"partition by odd/even returns index: "
			+ arr.Begin().Partition(arr.End(), IsIntEven).Index
			+ ", arr now: "
			+ ArrayToString(arr)
		);
		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)
		);
		ResetArrays();
		Log(
			"partition point for <= 2 returns index: "
			+ arr.Begin().PartitionPoint(arr.End(), IsIntLessThanOrEqualTo2).Index
		);
		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);
	}
}

Here’s the output of this test app:

advance 1 from begin: 200
distance from first to last: 4
all even?: True
all positive?: True
any > 10?: True
any == 2?: False
none == 2?: True
none > 10?: False
foreach: 200 200 200 200 
find 2 at index: 4
first even at index: 0
first not even at index: 4
end of [2,3] at index: 3
first of [2,3] at index: 0
adjacents at index: 0
count 2s: 0
count evens: 4
mismatch with [1, 3, 3, 4] at: 200, 1
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: 4
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: [3, 1, 2, 2], [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

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!

Continue on to part five!