Tuesday, May 31, 2011

Take me back!

After iterating the tree down, its time do go the opposite way: up!

public static IEnumerable<T> ToRoot<T>(
T item, Func<T, T> selector)
if (Equals(item, default(T))) yield break;
yield return item;

foreach (var x in ToRoot(selector(item), selector))
yield return x;

And how to use it:

static IEnumerable<int> CreateList(ProductDataSet.ProductRow row)
return ToRoot(row, x => x.ProductRowParent).Select(x => x.ProductId);

Iterate down a tree

Very often I see code like:

var list = new List<foo>();
AddRecursive(list, foo);
return list;

Nothing wrong with that except that there will be a lot of duplicate code after a while.

After some testing I was able to create an enumerator walking the tree.

public static IEnumerable<T> Recursive<T>(
T node, Func<T, IEnumerable<T>> selector)
yield return node;
var children = selector(node);
if (children == null) yield break;

foreach (var child in children.SelectMany(x => Recursive(x, selector)))
yield return child;

Let say you have this class:

public class Node {
public int Id;
public Node[] Children;

You can now find a given node using this statement

var node = Recursive(root, x => x.Children)
.FirstOrDefault(x => x.Id == 10);

Norwegian SSN validator

The Norwegian social security number consist of the birthday, then three digits with information about gender an century. The two last digits are checksums. Total 11 digits.

Can you do a validation of this using only two lines of code? Sure :D

public bool IsValid(string ssn)
var input = ssn.Select(x => x - '0').ToArray();
return (new[] {
new[] {3, 7, 6, 1, 8, 9, 4, 5, 2},
new[] {5, 4, 3, 2, 7, 6, 5, 4, 3, 2} })
.Select(x => new
Last = input[x.Length],
Check = x.Select((t, i) => input[i] * t).Sum() % 11 })
.All(z => (z.Last == (11 - z.Check) % 10)
|| (z.Last == 0 && z.Check == 0));

Specification: http://no.wikipedia.org/wiki/Fødselsnummer

Sequence inside a sequence

Is was looking at some code with smell. The method description was clear, but the implementation was not.

The code was, for a given sequence to determine if another sequence is present.

After getting some characterization tests up and running, it was time to do some refactoring.

From 38 lines of code, I was down to this:

for (;;)

public static bool Contains(List<T> x, IList<T> y)
for (int index = -1; (index = x.IndexOf(y[0], index + 1)) >= 0;)
if (x.Skip(index).Take(y.Count).SequenceEqual(y))
return true;

return false;

I thought I was done, but there was room for making this smaller. First out was to try to split up the algorithm into multiple parts


public static bool Contains(List<T> x, IList<T> y)
return FindStarts(x, y[0])
.Any(index => x.Skip(index).Take(y.Count).SequenceEqual(y));

private static IEnumerable<int> FindStarts(List<T> x, T item)
for (int index = -1; (index = x.IndexOf(item, index + 1)) >= 0; )
yield return index;

Then combine these two methods:

public static bool Contains(IEnumerable<T> x, IList<T> y)
return x.Select((value, index) => new { Value = value, Index = index })
.Where(z => z.Value.Equals(y[0]))
.Select(z => z.Index)
.Any(index => x.Skip(index).Take(y.Count).SequenceEqual(y));

Another possibility is check each element in the source sequence and drop the IndexOf(,..) logic:


public static bool Contains(IEnumerable<T> x, IList<T> y)
return Enumerable.Range(0, x.Count() - 1)
.Any(i => x.Skip(i).Take(y.Count).SequenceEqual(y));

And the final one using:


public static bool Contains(IEnumerable<T> x, IList<T> y)
return x.SkipWhile((value, index) => (value.Equals(y[0])
&& x.Skip(index).Take(y.Count).SequenceEqual(y)) == false).Any();


This blog is about the System.Linq.Enumerable class in .NET API. The Enumerable class is an extension library primary for linq queries.

There is a corresponding fan page on facebook for this blog: