Iterating Multiple Lists In Order
Suppose you have two sorted lists, one holding A elements and another holding B. Both types have a common field and you want to iterate over both lists according to that common field. For example, if you have [1, 3, 5] and [2, 4, 6] then you want to get the A with 1 then the B with 2 then the A with 3 and so on. How do you do this at all? How do you do it efficiently? Read on for my answers to the puzzle!
This problem crops up surprisingly often. For example, say you have a list of Player and a list of Enemy. Both have a Health field and both lists are sorted by it. You want to iterate over both lists in Health order. An OOP textbook answer would be to make them both implement the same interface so you can have only one list, but this quickly leads to runtime type checks and casting:
interface IGameEntity { int Health { get; } } class Player : IGameEntity { public int Health { get; } public int XP { get; } } class Enemy : IGameEntity { public int Health { get; } public int WorthXP { get; } } class Game { public IGameEntity[] GameEntities { get; } } void Iterate(Game game) { foreach (var ge in game.GameEntities) { if (ge is Player) { var player = ge as Player; Debug.Log("player has " + player.XP + " XP"); } else if (ge is Enemy) { var enemy = ge as Enemy; Debug.Log("enemy is worth " + enemy.WorthXP + " XP"); } else { // now what? } } }
As you can see, the only purpose of the interface is to allow the Player and Enemy types to be in the same list. We could have done this with object just as easily since we didn’t ever actually use IGameEntity. As soon as we need to know anything more about the game entity than what is common in the interface, we resort to casting.
It’s slow and cumbersome to do all this type checking and casting, but the merging of the two lists has still more problems. Any time we want to search for an enemy we need to search through all the players too. Other operations like sorting will take longer, too. It would be much nicer if we could simply have two lists, but this leads us back to the original question: how do we iterate both of them in the order of a common field?
class Player { public int Health { get; } public int XP { get; } } class Enemy { public int Health { get; } public int WorthXP { get; } } class Game { public Player[] Players { get; } public Enemy[] Enemies { get; } } void Iterate(Game game) { // ??? }
C#’s LINQ seems like a natural place to start. It’s got powerful features for wrangling just these sorts of issues. A “join” in particular seems to suit this situation well. We can join both types by their Health properties into an anonymous type that has both a Game and Player fields as well as the common property. Here’s how that’d look:
void Iterate(Game game) { foreach (var cur in // Make anonymous objects for each player game.Players.Select(p => new { Health = p.Health, Player = p, Enemy = default(Enemy) }) // Concatenate with... .Concat( // Make anonymous objects for each enemy game.Enemies.Select(e => new { Health = e.Health, Player = default(Player), Enemy = e }) ) // Sort by health .OrderBy(x => x.Health)) { if (cur.Player != null) { Debug.Log("player has " + cur.Player.XP + " XP"); } else { Debug.Log("enemy is worth " + cur.Enemy.WorthXP + " XP"); } } }
This can be generalized to work for any two types—A and B—like so:
public static void IterateInOrderLinq<A, B, TKey>( IEnumerable<A> aList, IEnumerable<B> bList, Func<A, TKey> aKeyGetter, Func<B, TKey> bKeyGetter, Action<A> aHandler, Action<B> bHandler ) { foreach (var cur in aList .Select(a => new { Key = aKeyGetter(a), HasA = true, A = a, B = default(B) }) .Concat( bList.Select(b => new { Key = bKeyGetter(b), HasA = false, A = default(A), B = b }) ) .OrderBy(x => x.Key)) { if (cur.HasA) { aHandler(cur.A); } else { bHandler(cur.B); } } }
Then you can use it like this:
void Iterate(Game game) { IterateInOrderLinq( game.Players, game.Enemies, p => p.Health, e => e.Health, p => Debug.Log("player has " + p.XP + " XP"), e => Debug.Log("enemy is worth " + e.WorthXP + " XP") ); }
That’s much cleaner! The mess is tidily hidden in the IterateInOrderLinq function which can be reused for any two types and any properties.
If you’re OK with LINQ’s sub-par performance, especially when it comes to garbage creation and sorting cost, then this function should serve just fine. If you’d rather optimize though, let’s look at how we can do LINQ’s work manually to get the job done quicker.
If we can assume that the two lists are already sorted by the common property (i.e. Health) then our task becomes much simpler. We can iterate down one list until the value becomes larger than the iterator on the other list. We then switch lists and iterate down the other list until the value becomes larger than the iterator on the first list.
For example, consider two lists: [1, 2, 3] and [2, 3, 4]. We start on the first element of each list: 1 for the A list and 2 for the B list. Here’s how the loops proceed:
- 1 in the A list is less than or equal to 2 in the B list so we process it and move the A list’s iterator to 2
- 2 in the A list is less than or equal to 2 in the B list so we process it and move the A list’s iterator to 3
- 3 in the A list is greater than 2 in the B list so we switch to comparing the lists in the other order
- 2 in the B list is less than or equal to 3 in the A list so we process it and move the B list’s iterator to 3
- 3 in the B list is less than or equal to 3 in the A list so we process it and move the B list’s iterator to 4
- 4 in the B list is greater than 3 in the A list so we switch to comparing the lists in the other order
- 3 in the A list is less than or equal to 4 in the B list so we process it and move the A list’s iterator off the end
- The A list is done so we process the rest of B’s elements, which is just 4
The result is: A1, A2, B2, B3, A3, B4.
Implementing this is quite ugly because it involves a lot of manual manipulation of an IEnumerator<T>. It also involves substantial code duplication due to some limitation in C#’s iterator function support. Here’s the final result:
public static void IterateInOrder<A, B>( IEnumerable<A> aList, IEnumerable<B> bList, Func<A, B, int> comparison, Action<A> aHandler, Action<B> bHandler ) { using (var eA = aList.GetEnumerator()) { using (var eB = bList.GetEnumerator()) { var hasA = eA.MoveNext(); var hasB = eB.MoveNext(); while (hasA || hasB) { if (hasA) { if (hasB) { var curA = eA.Current; var curB = eB.Current; do { if (comparison(curA, curB) <= 0) { aHandler(curA); if (eA.MoveNext() == false) { hasA = false; break; } curA = eA.Current; } else { break; } } while (true); } else { do { aHandler(eA.Current); } while (eA.MoveNext()); hasA = false; } } if (hasB) { if (hasA) { var curB = eB.Current; var curA = eA.Current; do { if (-comparison(curA, curB) <= 0) { bHandler(curB); if (eB.MoveNext() == false) { hasB = false; break; } curB = eB.Current; } else { break; } } while (true); } else { do { bHandler(eB.Current); } while (eB.MoveNext()); hasB = false; } } } } } }
Thankfully, using it is just about as easy as the LINQ version:
void Iterate(Game game) { IterateInOrder( game.Players, game.Enemies, (p, e) => p.Health - e.Health, p => Debug.Log("player has " + p.XP + " XP"), e => Debug.Log("enemy is worth " + e.WorthXP + " XP") ); }
One side benefit of this version is that it doesn’t require a particular property to be shared between the types. You can compare an A and a B to each other any way you like. This version also avoids doing any sorting, guarantees that it’ll iterate each list exactly once, only allocates two IEnumerator<T> instances, and avoids extra copies if you happen to use it with a struct type. It’s just as reusable as the LINQ version and the ugly details are safely hidden away in this utility method.
If you’ve come across a similar problem to this one, I’d be interested to hear how you solved it in the comments. Also, if this is a common algorithm that has a name already assigned to it, please let me know as I’d love to check it out!
UPDATE: check out part two