IanG on Tap

I recently worked on a project that included code to calculate the bounding box of a collection of rectangles. The code did more or less what you might expect – it iterated over the collection, and any time a new rectangle wasn’t contained by the current bounds, it enlarged the bounds to fit.

There was nothing wrong with this, but I knew of a cute trick that could do the job with a fraction of the code. I wasn’t being paid to replace working code with cute tricks, so I left it as it was – when it comes to production code I’m not a fan of the “If it ain’t broke, let me take a crack at it” school of coding. So I thought I’d illustrate the idea here instead.

Here’s a one-line implementation of the same logic, using the System.Windows.Rect type in WPF. (Note that this is a very simple value type, not a full UI element. It’s just 4 numbers.)

public static Rect GetBounds(IEnumerable<Rect> rects)
{
    return rects.Aggregate((currBounds, nextRect) => Rect.Union(currBounds, nextRect));
}

That’s pleasingly succinct, although possibly a little obscure if you’re not accustomed to this style of coding. Actually we can go one more notch on the obscure-and-succinct scale. This comes to the same thing:

public static Rect GetBounds(IEnumerable<Rect> rects)
{
    return rects.Aggregate(Rect.Union);
}

LINQ’s standard Aggregate method implements a mechanism often known as fold in functional programming languages. It’s a pretty simple idea: apply some sort of cumulative operation across all items in a list to build up some sort running total. In this example, LINQ’s uses the first item in the list as the starting point. (Alternatively, you can provide an explicit start value.) It passes that in to the function supplied, along with the second item. The result becomes the new running total, which is fed again into the function supplied, this time along with the third item...and so on. Each time round the aggregating function we provide gets the running total as its first argument, and the next item in the list as its second.

It’s easier to show what it does than to describe it. Here’s what that code would do if applied to an array containing five Rects:

Rect.Union(Rect.Union(Rect.Union(Rect.Union(rs[0], rs[1]), rs[2]), rs[3]), rs[4])

Or if you prefer sequential imperative code, you might like to picture it as:

Rect currBounds = rs[0];
currBounds = Rect.Union(currBounds, rs[1]);
currBounds = Rect.Union(currBounds, rs[2]);
currBounds = Rect.Union(currBounds, rs[3]);
currBounds = Rect.Union(currBounds, rs[4]);

As you can see, it’s not particularly magical. It’s nothing you couldn’t implement with a straightforward loop. (Or with tedious duplication, as here.) But it’s an idea that crops up often enough that it’s rather handy to have as general purpose function – you get to specify what you’d like to use as the cumulative operation, and LINQ does the rest for you.

Aggregate can be used to implement some common operations. For example, you can use it to sum together all the numbers in a list:

public static int Sum(IEnumerable<int> numbers)
{
    return numbers.Aggregate((currTotal, nextInt) => currTotal + nextInt);
}

Or you could use it to find the highest number in a list:

public static int Max(IEnumerable<int> numbers)
{
    return numbers.Aggregate((highest, nextInt) => Math.Max(highest, nextInt));
}

or again, since this just forwards the arguments directly to a function, we can skip the lambda and use the more terse form:

public static int Max(IEnumerable<int> numbers)
{
    return numbers.Aggregate(Math.Max);
}

Of course, you don’t need to write these two examples, because LINQ already supplies Sum and Max extension methods for you. But conceptually at least, they’re just a handy shortcut to a specialized form of aggregation.

Getting the total bounding box of all of the rectangles in a list is not so different from finding the highest number – it’s just a slightly different kind of maximum.

Not a particularly astounding idea, admittedly. I just thought it was a neat trick, and wanted to share it.