Reimplementing LINQ to Objects: Part 27 – Reverse

Time for a change of pace after the deep dive into sorting. Reversing is pretty simple… which is not to say there’s nothing to discuss, of course. What is it? Reverse only has a single, simple signature: public static IEnumerable<TSource> Reverse<TSource>(     this IEnumerable<TSource> source) The behaviour is pretty simple to describe: source cannot be null; this is validated eagerly. The operator uses deferred execution: until you start reading from the result, it won’t read anything from the input sequence As soon as you start reading from the result sequence, the input sequence is read in its entirety The result sequence … Continue reading Reimplementing LINQ to Objects: Part 27 – Reverse

Reimplementing LINQ to Objects: Part 26d – Fixing the key selectors, and yielding early

I feel I need a voice over. "Previously, on reimplementing LINQ to Objects…" Well, we’d got as far as a working implementation of OrderedEnumerable which didn’t have terrible performance – unless you had an expensive key selector. Oh, and it didn’t make use of the fact that we may only want the first few results. Executing key selectors only once Our first problem is to do with the key selectors. For various reasons (mentioned in part 26b) life is better if we execute the key selector once per input element. While we can do that with lazy evaluation, it makes … Continue reading Reimplementing LINQ to Objects: Part 26d – Fixing the key selectors, and yielding early

Reimplementing LINQ to Objects: Part 26c – Optimizing OrderedEnumerable

Part 26b left us with a working implementation of the ordering operators, with two caveats: The sort algorithm used was awful We were performing the key selection on every comparison, instead of once to start with Today’s post is just going to fix the first bullet – although I’m pretty sure that fixing the second will require changing it again completely. Choosing a sort algorithm There are lots of sort algorithms available. In our case, we need the eventual algorithm to: Work on arbitrary pair-based comparisons Be stable Go like the clappers 🙂 (Ideally) allow the first results to be … Continue reading Reimplementing LINQ to Objects: Part 26c – Optimizing OrderedEnumerable

Reimplementing LINQ to Objects: Part 26b – OrderBy{,Descending}/ThenBy{,Descending}

Last time we looked at IOrderedEnumerable<TElement> and I gave an implementation we could use in order to implement the public extension methods within LINQ. I’m still going to do that in this post, but it’s worth mentioning something else that’s coming up in another part (26d) – I’m going to revisit my OrderedEnumerable implementation. There may be trouble ahead… A comment on the previous post mentioned how my comparer executes the keySelector on each element every time it makes a comparison. I didn’t think of that as a particularly awful problem, until I thought of this sample query to rank … Continue reading Reimplementing LINQ to Objects: Part 26b – OrderBy{,Descending}/ThenBy{,Descending}

Reimplementing LINQ to Objects: Part 26a – IOrderedEnumerable

Implementing OrderBy/OrderByDescending/ThenBy/ThenByDescending isn’t too bad, once you understand how the pattern works, but that’s a slight conceptual leap. I’ll take it one step at a time, first introducing some extra infrastructure (both public and internal), then implementing it simply and slowly, and finally optimizing it somewhat. The sorting features of LINQ As a query language, it’s natural that LINQ allows you to sort sequences. Of course, collections have had the ability to sort their contents since v1.0 but LINQ is different in various ways: It expects you’ll usually want to sort via projections, rather than on a "natural" comparison of … Continue reading Reimplementing LINQ to Objects: Part 26a – IOrderedEnumerable

Reimplementing LINQ to Objects: Part 25 – ToDictionary

This one ended up being genuinely easy to implement, although with lots of tests for different situations. What is it? ToDictionary has four overloads which look remarkably similar to the ones we used for ToLookup: public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector) public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector,     Func<TSource, TElement> elementSelector) public static Dictionary<TKey, TSource> ToDictionary<TSource, TKey>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector,     IEqualityComparer<TKey> comparer)          public static Dictionary<TKey, TElement> ToDictionary<TSource, TKey, TElement>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector,     Func<TSource, TElement> … Continue reading Reimplementing LINQ to Objects: Part 25 – ToDictionary

Reimplementing LINQ to Objects: Part 24 – ToArray

This really is a simple one. So simple I might even find the energy to implement ToDictionary as well tonight… we’ll see. (EDIT: Oops. It became slightly less simple in the end, as I came up with the third implementation. Oh well.) What is it? ToArray is basically the equivalent of ToList, but producing an array instead of a list. It has a single signature: public static TSource[] ToArray<TSource>(this IEnumerable<TSource> source) Just to recap: It’s another extension method, which is useful when we want to use type inference. It uses immediate execution – nothing is deferred, and the entire sequence is … Continue reading Reimplementing LINQ to Objects: Part 24 – ToArray

Reimplementing LINQ to Objects: Part 23 – Take/Skip/TakeWhile/SkipWhile

I genuinely expected these operators to be simple. At the time of this writing, I’m onto my third implementation of SkipWhile, struggling to find code which obviously expresses what’s going on. I find it interesting how the simplest sounding operators sometimes end up being trickier to implement than one might think. What are they? Take, TakeWhile, Skip and SkipWhile form a natural group of operators. Together they are known as the partitioning operators. Here are the signatures: public static IEnumerable<TSource> Take<TSource>(     this IEnumerable<TSource> source,     int count) public static IEnumerable<TSource> TakeWhile<TSource>(     this IEnumerable<TSource> source,     Func<TSource, bool> predicate) public static IEnumerable<TSource> … Continue reading Reimplementing LINQ to Objects: Part 23 – Take/Skip/TakeWhile/SkipWhile

Reimplementing LINQ to Objects: Part 22 – GroupJoin

Another operator that was decidedly easy to implement – partly as I was able to just adapt everything from Join, including the tests. 15 minutes for tests + implementation… and no doubt considerably long writing it up. What is it? After the complexity of GroupBy, GroupJoin has a refreshingly small list of overloads: public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult>(     this IEnumerable<TOuter> outer,     IEnumerable<TInner> inner,     Func<TOuter, TKey> outerKeySelector,     Func<TInner, TKey> innerKeySelector,     Func<TOuter, IEnumerable<TInner>, TResult> resultSelector) public static IEnumerable<TResult> GroupJoin<TOuter, TInner, TKey, TResult>(     this IEnumerable<TOuter> outer,     IEnumerable<TInner> inner,     Func<TOuter, TKey> outerKeySelector,     Func<TInner, TKey> innerKeySelector, … Continue reading Reimplementing LINQ to Objects: Part 22 – GroupJoin

Reimplementing LINQ to Objects: Part 21 – GroupBy

Okay, after the brief hiatus earlier, we’re ready to group sequences. What is it? GroupBy has eight overloads, using up to four type parameters and up to five normal parameters. Those of a sensitive disposition may wish to turn away now: public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector) public static IEnumerable<IGrouping<TKey, TSource>> GroupBy<TSource, TKey>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector,     IEqualityComparer<TKey> comparer) public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(     this IEnumerable<TSource> source,     Func<TSource, TKey> keySelector,     Func<TSource, TElement> elementSelector) public static IEnumerable<IGrouping<TKey, TElement>> GroupBy<TSource, TKey, TElement>(     this IEnumerable<TSource> source,     Func<TSource, … Continue reading Reimplementing LINQ to Objects: Part 21 – GroupBy