## Friday, April 26, 2013

### Sasa.Linq.Enumerables - Extensions on IEnumerable<T>

This is the seventeenth post in my ongoing series covering the abstractions in Sasa. Previous posts:

In my opinion, the release of .NET 3.5 and LINQ to Objects was one of the greatest productivity and safety enhancements to .NET since its inception. It enabled the concise expression of highly generic algorithms depending solely on the simple notion of an iterable stream, IEnumerable<T>. You could then specify semantics for duplicates, ordering, and grouping constraints over streams with a nice query syntax or a simple first-class function syntax.

The advent of extension methods allowed such extensions to be packaged into a neat, consistent framework under System.Linq.Enumerable. Sasa.Linq.Enumerables extends the functionality for IEnumerable<T> even further.

## Sasa.Linq.Enumerables.Append

Sasa.Linq.Enumerables.Append is an extension method on IEnumerable<T> to add a single element to the end of a sequence:

IEnumerable<int> source = new[] { 2, 99, 8 };
IEnumerable<int> sourcePlusOne = source.Append(-10);
foreach (var x in sourcePlusOne)
{
Console.WriteLine(x);
}
// output:
// 2
// 99
// 8
// -10


## Sasa.Linq.Enumerables.Apply

Sasa.Linq.Enumerables.Apply is an extension on IEnumerable<T> that applies an Action<T> to every value as the stream is being iterated:

IEnumerable<int> source = new[] { 2, 99, 8 }
.Apply(Console.Write);
foreach (var x in source)
{
Console.WriteLine();
}
// output:
// 2
// 99
// 8


## Sasa.Linq.Enumerables.CompareTo

Sasa.Linq.Enumerables.CompareTo is an extension on IEnumerable<T> that performs an element-wise comparison between two streams in the same vein as the IComparable<T> interface:

IEnumerable<int> largest = new[] { 3, 99, 8 };
IEnumerable<int> larger  = new[] { 2, 99, 8 };
IEnumerable<int> smaller = new[] { 2, 98, 8 };

Console.WriteLine(largest.CompareTo(larger));
Console.WriteLine(larger.CompareTo(smaller));
Console.WriteLine(smaller.CompareTo(largest));
Console.WriteLine(smaller.CompareTo(smaller));
// output:
// 1
// 1
// -1
// 0


## Sasa.Linq.Enumerables.Consume

Sasa.Linq.Enumerables.Consume is an extension on IEnumerable<T> that consumes a whole stream in one go:

static IEnumerable<int> Foo()
{
for (int i = 0; i < 3; ++i)
{
Console.WriteLine(i);
yield return i;
}
}
...
Foo().Consume(); // consume stream and return when done

// output:
// 0
// 1
// 2


## Sasa.Linq.Enumerables.CopyTo

Sasa.Linq.Enumerables.CopyTo is an extension on IEnumerable<T> that copies elements from the stream into a pre-allocated array:

IEnumerable<int> source = new[] { 3, 99, 8, -5, 12, -999 };
int[] buffer = new int[3];
source.CopyTo(buffer, 0);
foreach (var x in buffer)
{
Console.Write("{0}, ", x);
}
// output:
// 3, 99, 8,


## Sasa.Linq.Enumerables.Difference

Sasa.Linq.Enumerables.Difference is an extension on IEnumerable<T> that produces a stream of Change<T> values indicating the changes needed to transform one stream into another:

IEnumerable<int> first = new[] { 3, 99, 8, -5, 12, -9 };
IEnumerable<int> second = new[] { 3, 99, -5, 12, 66, 234, -9 };
IEnumerable<Change<int>> diff = first.Difference(second);
foreach (var x in diff)
{
Console.WriteLine(x);
}
// output:
// -1:99
// +1:99,8
// +5:66, 234


Basically, the 'diff' stream in the above sample describes the changes you have to make to 'first' in order to transform it into the stream 'second'. This is fully described by the output which specifies a subtraction at position 1 of the value 99, an addition at position 1 of values 99 and 8, and the addition of two values at position 5 of 66 and 234.

## Sasa.Linq.Enumerables.Do

Sasa.Linq.Enumerables.Do is an extension on IEnumerable<T> that fully consumes a stream while applying a function to each element:

IEnumerable<int> source = new[] { 2, 99, 8 };
source.Do(Console.WriteLine);
// output:
// 2
// 99
// 8


## Sasa.Linq.Enumerables.Flatten

Sasa.Linq.Enumerables.Flatten is an extension on IEnumerable<T> that flattens a nested sequence:

IEnumerable<IEnumerable<int>> source = new int[][]
{
new[] { 2, 99 },
new[] { 8 }
};
IEnumerable<int> flat = source.Flatten();
flat.Do(Console.WriteLine);
// output:
// 2
// 99
// 8


This is functionally equivalent to:

IEnumerable<int> flat = source.SelectMany(x => x);

Except the C# compiler won't have to create so many delegates in all the various assemblies that flatten sequences.

## Sasa.Linq.Enumerables.Format

Sasa.Linq.Enumerables.Format is a set of extension method overloads on IEnumerable<T> that make it easy to construct a string from a sequence. Basically, you provide a sequence and a value separator, like ",", and Format will output each value in the sequence spaced with the separator:

IEnumerable<int> source = new[] { 2, 99, 8 };
string formatted = source.Format(", ");
Console.WriteLine(formatted);
// output:
// 2, 99, 8


## Sasa.Linq.Enumerables.Generate

Sasa.Linq.Enumerables.Generate is a static method used to construct sequences of values by taking a seed value and a generator function:

Func<int, Option<int>> step = x => x < 3 ? x + 1:
Option<T>.None;
IEnumerable<int> source = Enumerables.Generate(0, step);
Console.WriteLine(source.Format(", "));
// output:
// 0, 1, 2, 3


The generator function returns an Option<T>, so terminating the generator requires simply returning Option<T>.None.

## Sasa.Linq.Enumerables.Push

Sasa.Linq.Enumerables.Push is an extension on IEnumerable<T> that pushes an element to the front of an enumerable sequence:

IEnumerable<int> source = new[] { 2, 99, 8 };
Console.WriteLine(source.Push(-1).Format(","));
// output:
// -1, 2, 99, 8


## Sasa.Linq.Enumerables.ReplaceElementAt

Sasa.Linq.Enumerables.ReplaceElementAt is an extension on IEnumerable<T> that replaces the element at a specified index with a new value:

IEnumerable<int> source = new[] { 2, 99, 8 }
.ReplaceElementAt(index: 1, value: -1);
Console.WriteLine(source.Format(","));
// output:
// 2, -1, 8


## Sasa.Linq.Enumerables.Transpose

Sasa.Linq.Enumerables.Transpose is an extension on a nested sequence, IEnumerable<IEnumerable<T>> that transposes the rows and columns:

IEnumerable<IEnumerable<int>> source = new int[][]
{
new[] { 2, 99 },
new[] { 8, -10 }
};
// transpose the rows and columns
foreach (var row in source.Transpose())
{
foreach (var column in row)
{
Console.Write("{0}, ", column);
}
Console.WriteLine();
}
flat.Do(Console.WriteLine);
// output:
// 2, 8
// 99, -10


Note that this method will handle jagged sequences, but transposing twice will not necessarily recover the same sequence as the original input. All the jagged entries will be pushed to the last row.

## Sasa.Linq.Enumerables.Zip

Sasa.Linq.Enumerables.Zip is a set of extension method overloads on IEnumerable<T> that combines streams together element-wise, returning a stream of Sasa's tuples. This is known as "zipping" streams, analogously to the operation of a physical zipper where the teeth pair up one after another:

IEnumerable<int> source1 = new[] { 2, 99 };
IEnumerable<int> source2 = new[] { 8, -10 };
IEnumerable<Pair<int, int>> zipped = source1.Zip(source2);

Console.WriteLine(zipped.Format("\r\n"));
// output:
// (2, 8)
// (99, -10)


There is a zip overload for each of Sasa's tuple types, so you can zip up to 4 streams together.

## Sasa.Linq.Enumerables.ZipWith

Sasa.Linq.Enumerables.ZipWith is a set of extension method overloads on IEnumerable<T> that combines the elements of streams together element-wise using a client-specified function, returning a stream of values. This is known as "zipping" streams, analogously to the operation of a physical zipper where the teeth pair up one after another:

IEnumerable<int> source1 = new[] { 2, 99 };
IEnumerable<int> source2 = new[] { 8, -10 };
IEnumerable<Pair<int, int>> zipped =
source1.ZipWith(source2, (x,y) => Tuples.Create(x,y));

Console.WriteLine(zipped.Format("\r\n"));
// output:
// (2, 8)
// (99, -10)


Like the Enumerables.Zip extension, ZipWith is defined for zipping up to 4 streams.

## Thursday, April 25, 2013

### Sasa.IO.Streams - Convenient Stream Extensions

This is the sixteenth post in my ongoing series covering the abstractions in Sasa. Previous posts:

Streams are a pervasive component of .NET I/O, but the standard stream interface is missing a few convenient extensions, if only needed for testing and debugging purposes. Sasa.IO.Streams provides a few simple extension methods to simplify working with streams.

## Sasa.IO.Streams.CopyTo

Sasa.IO.Streams.CopyTo is a set of extension methods to copy data from one stream to another:

var source = new MemoryStream(Encoding.ASCII.GetBytes("Hello world!"));
var target = new MemoryStream();
source.CopyTo(target);
Console.WriteLine(Encoding.ASCII.GetString(target.ToArray()));
// output:
// Hello world!


There is also an overload explicitly specifying the number of bytes to copy.

## Sasa.IO.Streams.ToArray

Sasa.IO.Streams.ToArray dumps the contents of any stream into a byte[]:

// write contents to file
using (var fs = File.OpenWrite("foo.txt"))
{
fs.Write(Encoding.ASCII.GetBytes("Hello world!"));
}
// read contents from file in one go
byte[] data;
{
data = fs.ToArray();
}
Console.WriteLine(Encoding.ASCII.GetString(data));
// output:
// Hello world!


## Wednesday, April 24, 2013

### Sasa.IO.FilePath - Easy and Safe Path Manipulations

This is the fifteenth post in my ongoing series covering the abstractions in Sasa. Previous posts:

One persistent difficulty in dealing with IO in .NET is path handling. .NET exposes a platform's directory separator characters, but really this sort of thing should be automated. Furthermore, paths are considered simple strings and so concatenating fragments could leave you with a path string that goes up and down directories with no clear final result, ie. resolving the final path string is left to the OS.

This means that you can't easily reason about the constructed paths without consulting the OS, which is a relatively expensive operation. Furthermore, Path.Combine has a number of corner cases that make constructing paths non-compositional, requiring numerous argument validations to ensure a correct result.

Enter Sasa.IO.FilePath. It's a simple struct that encapsulates an underlying path string, so FilePath operations are just as efficient as your current path handling. FilePath fully resolves directory change operations where possible, so the final path string designates the path the OS will actually look up. Null or empty strings are considered references to the current directory, ie. ".". There is also a "jail" operation which ensures that a provided path cannot escape a particular sub-directory, just like the OS-level chroot jail.

I first posted about this abstraction back in 2009, but the name and implementation has changed a little since then.

## Sasa.IO.FilePath Constructor

The constructor takes an arbitrary path string, resolves all the inner directory change operations, and returns a final path:

var foo = "foo/../..";
var path1 = new FilePath(foo);
var path2 = new FilePath("bar/" + foo);
Console.WriteLine(path1);
Console.WriteLine(path2);
Console.WriteLine("root" / path2); // FilePath composition using /
// output:
// ..
// .
// root


## Sasa.IO.FilePath.Combine

The Combine method exposes the same semantics as System.IO.Path.Combine, but on FilePath instances:

var foo = new FilePath("foo/../..");
var bar = new FilePath("/bar");
Console.WriteLine(FilePath.Combine(foo, bar));
Console.WriteLine(FilePath.Combine(bar, foo));
// output:
// ..\bar
// .


## Sasa.IO.FilePath.IsParentOf

The IsParentOf method compares two paths to see if one is a subset of the other:

var foobar = new FilePath("foo/bar");
var bar = new FilePath("bar");
var foo = new FilePath("foo");
Console.WriteLine(bar.IsParentOf(foobar));
Console.WriteLine(foo.IsParentOf(foobar));
Console.WriteLine(foobar.IsParentOf(foo));
// output:
// false
// true
// false


## Sasa.IO.FilePath.Jail

The Jail methods provide a chroot-jail operation on file paths, to ensure a provided path string cannot escape a certain sub-directory:

var escape = new FilePath("../..");
var bar = new FilePath("/bar");
Console.WriteLine(FilePath.Jail(bar, escape));
// output:
// bar


## Sasa.IO.FilePath.Resolve

The real workhorse behind FilePath, Sasa.IO.FilePath.Resolve resolves all path change operations in a string and returns a simplified path string. In case you want to stick with raw string paths, you can use this method to perform path simplification:

var path1 = "foo/../..";
var path2 = "bar/" + path1;
Console.WriteLine(FilePath.Resolve(path1));
Console.WriteLine(FilePath.Resolve(path2));
Console.WriteLine(FilePath.Resolve("root/" + path2));
// output:
// ..
//
// root


## Sasa.IO.FilePath./ Operator

The division operator on file paths is a convenient shorthand for composing paths, and a shorthand for FilePath.Combine:

var foo = "foo/../..";
var path1 = new FilePath(foo);
var path2 = "bar" / path1;
Console.WriteLine(path1);
Console.WriteLine(path2);
Console.WriteLine("root" / path2);
// output:
// ..
// .
// root


## Sasa.IO.FilePath's Interfaces

• IEnumerable<string>: the sequence of path components making up a full path.
• IEquatable<FilePath>: compare two paths for equality
• IComparable<FilePath>: order two paths alphanumerically

## Tuesday, April 23, 2013

### Sasa.Operators<*> - Generic Arithmetic and Logical Operators

This is the fourteenth post in my ongoing series covering the abstractions in Sasa. Previous posts:

When writing generic code, it's pretty common to yearn for some generic arithmetic interface so you don't have to copy-paste the same function over and over to provide overloads for all the CLR's numeric types. Omitting a standard arithmetic interface was one of .NET's biggest mistakes in my opinion.

Enter Sasa.Operators<T>, Sasa.Operators<T0, T1>, and Sasa.Operators<T0, T1, T2>, which are static classes that expose delegates for all operators on any given types T, T0, T1, and T2. T must contain operator overloads for the corresponding operation to be available, or if T is a primitive type like Int32 or Double, then a delegate is dynamically generated and cached. If T does not contain operator overloads for a given operation, the corresponding delegate for that operation will be null, so you just need to check for their presence as a precondition.

# Sasa.Operators<T>

Sasa.Operators<T> provides operators over a single generic type T. In other words, any operators defined only on a single type T will be available via this generic static class, eg. addition, subtraction, multiplication, etc.

var x = Operators<int>.Add(1, 2);
Console.WriteLine(x);
// output:
// 3


## Sasa.Operators<T>.And

The Sasa.Operators<T>.And operation takes two T arguments, and returns a T argument which is the bitwise/logical 'and' of the two arguments:

var x = Operators<int>.And(1, 3);
Console.WriteLine(x);
// output:
// 1


## Sasa.Operators<T>.Decrement

The Sasa.Operators<T>.Decrement operation takes a T argument, and returns a "decremented" T argument:

var x = Operators<double>.Decrement(1.5);
Console.WriteLine(x);
// output:
// 0.5


## Sasa.Operators<T>.Divide

The Sasa.Operators<T>.Divide operation two T arguments and returns a T argument corresponding to their division:

var x = Operators<int>.Divide(6, 2);
Console.WriteLine(x);
// output:
// 3


## Sasa.Operators<T>.Equal

The Sasa.Operators<T>.Equal operation takes two T arguments and returns a bool argument corresponding to their equality:

var x = Operators<int>.Equal(6, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T>.False

The Sasa.Operators<T>.False operation takes a T argument and returns a bool based on whether the argument corresponds to that T's false value:

Console.WriteLine(Operators<bool>.False(false));
Console.WriteLine(Operators<bool>.False(true));
// output:
// true
// false


## Sasa.Operators<T>.GreaterThan

The Sasa.Operators<T>.GreaterThan operation takes two T arguments and returns a bool based on whether the first argument is greater than the second:

var x = Operators<int>.GreaterThan(1, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T>.GreaterThanOrEqual

The Sasa.Operators<T>.GreaterThanOrEqual operation takes two T arguments and returns a bool based on whether the first argument is greater than or equal to the second:

var x = Operators<int>.GreaterThanOrEqual(1, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T>.Increment

The Sasa.Operators<T>.Increment operation a T argument and returns an "incremented" T:

var x = Operators<int>.Increment(98);
Console.WriteLine(x);
// output:
// 99


## Sasa.Operators<T>.LeftShift

The Sasa.Operators<T>.LeftShift operation a T argument, followed by an Int32 argument, and returns a T "left-shifted" by the Int32:

var x = Operators<int>.LeftShift(1, 3);
Console.WriteLine(x);
// output:
// 8


## Sasa.Operators<T>.LessThan

The Sasa.Operators<T>.LessThan operation takes two T arguments and returns a bool based on whether the first argument is less than the second:

var x = Operators<int>.LessThan(1, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T>.LessThanOrEqual

The Sasa.Operators<T>.GreaterThanOrEqual operation takes two T arguments and returns a bool based on whether the first argument is less than or equal to the second:

var x = Operators<int>.LessThanOrEqual(1, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T>.Modulo

The Sasa.Operators<T>.Modulo operation takes two T arguments, and returns the modulus/remainder of dividing the two arguments:

var x = Operators<int>.Modulo(9, 2);
Console.WriteLine(x);
// output:
// 1


## Sasa.Operators<T>.Multiply

The Sasa.Operators<T>.Multiply operation takes two T arguments, and returns their multiplication:

var x = Operators<int>.Multiply(9, 2);
Console.WriteLine(x);
// output:
// 18


## Sasa.Operators<T>.Negate

The Sasa.Operators<T>.Negate operation takes a T argument, and returns its negation:

var x = Operators<int>.Negate(9);
Console.WriteLine(x);
// output:
// -9


## Sasa.Operators<T>.Not

The Sasa.Operators<T>.Not operation takes a T argument, and returns logical/bitwise not of the value:

// given twos-complement, not(-1) == 0
var x = Operators<int>.Not(-1);
Console.WriteLine(x);
// output:
// 0


## Sasa.Operators<T>.NotEqual

The Sasa.Operators<T>.NotEqual operation takes two T arguments and returns a bool argument corresponding to their inequality:

var x = Operators<int>.NotEqual(6, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T>.Or

The Sasa.Operators<T>.Or operation takes two T arguments, and returns their logical/bitwise-or:

var x = Operators<int>.Or(1, 2);
Console.WriteLine(x);
// output:
// 3


## Sasa.Operators<T>.Plus

The Sasa.Operators<T>.Plus operation takes a T argument and returns their logical/bitwise-plus of the argument:

var x = Operators<int>.Plus(-1);
Console.WriteLine(x);
// output:
// -1


## Sasa.Operators<T>.RightShift

The Sasa.Operators<T>.RightShift operation takes a T argument, followed by an Int32 argument, and returns a T "right-shifted" by the Int32:

var x = Operators<int>.RightShift(8, 3);
Console.WriteLine(x);
// output:
// 1


## Sasa.Operators<T>.Subtract

The Sasa.Operators<T>.Subtract operation takes two T arguments, and returns their subtraction:

var x = Operators<int>.Subtract(1, 3);
Console.WriteLine(x);
// output:
// -2


## Sasa.Operators<T>.True

The Sasa.Operators<T>.True operation takes a T argument and returns a bool based on whether the argument corresponds to that T's true value:

Console.WriteLine(Operators<bool>.True(true));
Console.WriteLine(Operators<bool>.True(false));
// output:
// true
// false


## Sasa.Operators<T>.Xor

The Sasa.Operators<T>.Xor operation takes two T arguments, and returns their logical/bitwise exclusive-or:

var x = Operators<int>.Xor(1, 3);
Console.WriteLine(x);
// output:
// 2


# Sasa.Operators<T0, T1>

Not all operators are defined over only a single type, some are defined over two types. Sasa.Operators<T0, T1> provides efficient access to such operators, like explicit or implicit casting from a type T0 to T1.

## Sasa.Operators<T0, T1>.Decrement

The Sasa.Operators<T0, T1>.Decrement operation takes a T0 argument, and returns a "decremented" T1 argument:

var x = Operators<double, double>.Decrement(1.5);
Console.WriteLine(x);
// output:
// 0.5


## Sasa.Operators<T0, T1>.Equal

The Sasa.Operators<T0, T1>.Equal operation takes a T0 and T1 and returns a bool argument corresponding to their equality:

var x = Operators<int, int>.Equal(6, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T0, T1>.Explicit

The Sasa.Operators<T0, T1>.Explicit operation takes a T0 and returns a T1 corresponding to an explicit cast from T0 to T1:

var x = Operators<int, float>.Explicit(6);
Console.WriteLine(x);
// output:
// 6.0


## Sasa.Operators<T0, T1>.GreaterThan

The Sasa.Operators<T0, T1>.GreaterThan operation takes a T0 and T1 and returns a bool based on whether the first argument is greater than the second:

var x = Operators<int, float>.GreaterThan(1, 2F);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T>.GreaterThanOrEqual

The Sasa.Operators<T0, T1>.GreaterThanOrEqual operation takes a T0 and T1 and returns a bool based on whether the first argument is greater than or equal to the second:

var x = Operators<int, float>.GreaterThanOrEqual(1, 2F);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T0, T1>.Implicit

The Sasa.Operators<T0, T1>.Implicit operation takes a T0 and returns a T1 corresponding to an implicit cast from T0 to T1:

var x = Operators<int, double>.Implicit(6);
Console.WriteLine(x);
// output:
// 6.0


## Sasa.Operators<T0, T1>.Increment

The Sasa.Operators<T0, T1>.Increment operation a T0 argument and returns an "incremented" T1:

var x = Operators<int>.Increment(98);
Console.WriteLine(x);
// output:
// 99


## Sasa.Operators<T0, T1>.LeftShift

The Sasa.Operators<T0, T1>.LeftShift operation a T0 argument, followed by an Int32 argument, and returns a T1 "left-shifted" by the Int32:

var x = Operators<int, int>.LeftShift(1, 3);
Console.WriteLine(x);
// output:
// 8


## Sasa.Operators<T0, T1>.Negate

The Sasa.Operators<T0, T1>.Negate operation takes a T0 argument, and returns its negation as type T1:

var x = Operators<int, int>.Negate(9);
Console.WriteLine(x);
// output:
// -9


## Sasa.Operators<T0, T1>.Not

The Sasa.Operators<T0, T1>.Not operation takes a T0 argument, and returns logical/bitwise not of the value as type T1:

// given twos-complement, not(-1) == 0
var x = Operators<int, int>.Not(-1);
Console.WriteLine(x);
// output:
// 0


## Sasa.Operators<T0, T1>.NotEqual

The Sasa.Operators<T0, T1>.NotEqual operation takes a T0 and T1 and returns a bool argument corresponding to their inequality:

var x = Operators<int, int>.NotEqual(6, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T>.Or

The Sasa.Operators<T>.Or operation takes two T arguments, and returns their logical/bitwise-or:

var x = Operators<int>.Or(1, 2);
Console.WriteLine(x);
// output:
// 3


## Sasa.Operators<T0, T1>.RightShift

The Sasa.Operators<T0, T1>.RightShift operation takes a T argument, followed by an Int32 argument, and returns a T "right-shifted" by the Int32:

var x = Operators<int>.RightShift(8, 3);
Console.WriteLine(x);
// output:
// 1


# Sasa.Operators<T0, T1, T2>

Sasa.Operators<T0, T1, T2> is the granddaddy of the operators classes, as it exposes the full generality of binary operators over 3 possible type parameters. In other words, it's possible to define an addition operator that takes a T0 and a T1 and returns a T2. Unary operators can only have two possible type parameters, so they are only available via Sasa.Operators< T0, T1>.

The addition operator Sasa.Operators<T0, T1, T2>.Add, takes arguments T0 and T1 and returns their addition as type T2:

var x = Operators<int, long, double>.Add(1, 2);
Console.WriteLine(x);
// output:
// 3.0


## Sasa.Operators<T0, T1, T2>.And

The Sasa.Operators<T0, T1, T2>.And takes arguments T0 and T1 and returns their bitwise/logical 'and' as type T2:

var x = Operators<int, uint, uint>.And(1, 3);
Console.WriteLine(x);
// output:
// 1


## Sasa.Operators<T0, T1, T2>.Divide

The Sasa.Operators<T0, T1, T2>.Divide operation takes arguments T0 and T1 and returns their division as type T2:

var x = Operators<long, int, int>.Divide(6, 2);
Console.WriteLine(x);
// output:
// 3


## Sasa.Operators<T0, T1, T2>.Equal

The Sasa.Operators<T0, T1, T2>.Equal operation takes arguments T0 and T1 and returns their equality as type T2, where T2 must implement the true/false operators:

var x = Operators<int, int, bool>.Equal(6, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T0, T1, T2>.GreaterThan

The Sasa.Operators<T0, T1, T2>.GreaterThan operation takes arguments T0 and T1 and returns their > as type T2, where T2 must implement the true/false operators:

var x = Operators<int, int, bool>.GreaterThan(1, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T0, T1, T2>.GreaterThanOrEqual

The Sasa.Operators<T0, T1, T2>.GreaterThanOrEqual operation takes arguments T0 and T1 and returns their >= as type T2, where T2 must implement the true/false operators:

var x = Operators<int, int, bool>.GreaterThanOrEqual(1, 2);
Console.WriteLine(x);
// output:
// false


## Sasa.Operators<T0, T1, T2>.LessThan

The Sasa.Operators<T0, T1, T2>.LessThan operation takes arguments T0 and T1 and returns their < as type T2, where T2 must implement the true/false operators:

var x = Operators<int, int, bool>.LessThan(1, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T0, T1, T2>.LessThanOrEqual

The Sasa.Operators<T0, T1, T2>.GreaterThanOrEqual operation takes arguments T0 and T1 and returns their <= as type T2, where T2 must implement the true/false operators:

var x = Operators<int, int, bool>.LessThanOrEqual(1, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T0, T1, T2>.Modulo

The Sasa.Operators<T0, T1, T2>.Modulo operation takes arguments T0 and T1 and returns their modulus as type T2:

var x = Operators<int, int, int>.Modulo(9, 2);
Console.WriteLine(x);
// output:
// 1


## Sasa.Operators<T0, T1, T2>.Multiply

The Sasa.Operators<T0, T1, T2>.Multiply operation takes arguments T0 and T1 and returns their multiplication as type T2:

var x = Operators<int, int, int>.Multiply(9, 2);
Console.WriteLine(x);
// output:
// 18


## Sasa.Operators<T0, T1, T2>.NotEqual

The Sasa.Operators<T0, T1, T2>.NotEqual operation takes arguments T0 and T1 and returns their inequality as type T2, where T2 must implement the true/false operators:

var x = Operators<int, int, bool>.NotEqual(6, 2);
Console.WriteLine(x);
// output:
// true


## Sasa.Operators<T0, T1, T2>.Or

The Sasa.Operators<T0, T1, T2>.Or operation takes arguments T0 and T1 and returns their logical/bitwise-or as type T2:

var x = Operators<int, uint, uint>.Or(1, 2);
Console.WriteLine(x);
// output:
// 3


## Sasa.Operators<T0, T1, T2>.Subtract

The Sasa.Operators<T0, T1, T2>.Subtract operation takes arguments T0 and T1 and returns their subtraction as type T2:

var x = Operators<int, int, int>.Subtract(1, 3);
Console.WriteLine(x);
// output:
// -2


## Sasa.Operators<T0, T1, T2>.Xor

The Sasa.Operators<T0, T1, T2>.Xor operation takes arguments T0 and T1 and returns their logical/bitwise exclusive-or as type T2:

var x = Operators<int, int, uint>.Xor(1, 3);
Console.WriteLine(x);
// output:
// 2


Most of the functions in Sasa that are defined on generic numeric types utilize these classes to avoid code duplication. For instance, Sasa.Numbers covered in a previous post, defines the UpTo extension method like so:

public static IEnumerable<T> UpTo<T>(this T start, T end, T step)
where T : IComparable<T>
{
if (start.CompareTo(end) > 0)
throw new ArgumentOutOfRangeException("start", "Must be less than or equal to parameter 'end'.");
if (step.CompareTo(default(T)) <= 0)
throw new ArgumentOutOfRangeException("step", "Must be greater than 0.");
throw new ArgumentException("T must provide an addition operator.");
for (var i = start;
i.CompareTo(end) < 0;
{
yield return i;
}
}


## Saturday, April 20, 2013

### Fast Deep Copies in C# using Sasa.Dynamics

I've briefly discussed Sasa.Dynamics in my first announcement for the upcoming Sasa v0.9.4 release. There was some confusion about what Sasa.Dynamics really is though, since the post didn't go into much detail, or wasn't explained clearly enough. In short, Sasa.Dynamics is a framework for type-safe, blazingly fast reflection.

It's useful for writing all sorts of algorithms that compute results based on the structure of types. For instance, as mentioned in the above article, Sasa.Dynamics ships with two such algorithms by default: an immutable type test, and a deep copier. Both of these algorithms are fully generic and apply to any type, and they're faster than anything you can do with standard reflection. Here's how you perform a deep copy on an object:

var copy = Type<T>.Copy(originalValue);

If you don't know anything about the type you're copying, you can just supply T = object. The more specific the static type information you provide to the copier, the faster it will be. As a small proof, here are a few benchmarks I just added to Sasa's test suite:

= Type: Int32[] =
Binary formatter:            626608 ticks
Type<object>.Copy:           152474 ticks
Type<Int32[]>.Copy:          128127 ticks

= Type: List<Int32> =
Binary formatter:           1209692 ticks
Type<object>.Copy:           767455 ticks
Type<List1>.Copy:           739828 ticks

= Type: Bar =
Binary formatter:           1066745 ticks
Type<object>.Copy:           549021 ticks
Type<Bar>.Copy:              500552 ticks

= List<Lazy<Int32>> =
Binary formatter:          22065369 ticks
Type<object>.Copy:         21339976 ticks
Type<List1>.Copy:         21090640 ticks

= Type: Int32 =
Binary formatter:            428022 ticks
Type<object>.Copy:             7050 ticks
Type<Int32>.Copy:              1435 ticks

= Type: String =
Binary formatter:            222462 ticks
Type<object>.Copy:             4895 ticks
Type<String>.Copy:             1547 ticks

= Type: String[] =
Binary formatter:          25201559 ticks
Type<object>.Copy:           234653 ticks
Type<String[]>.Copy:         185214 ticks


You can clearly see that Type<T>.Copy is sometimes many orders of magnitude faster than a roundtrip through BinaryFormatter. The benchmarks for immutable types will be particularly fast, as you can see from entries for String and Int32. This is because immutability of a type is automatically detected (via Type<T>.MaybeMutable), and such values are never copied, just returned as-is.

Of course, it's not exactly hard to beat framework serialization, but what's notable here is that I'm doing it with fully general reflection and very little optimization effort. The more type information you can provide to Type<T>, the faster it is. For instance, there's a 3x-5x difference in Int32 and String copying when we provide the statically known type T rather than object.

I've also barely scratched the surface of the optimizations that can be done. The structural induction inherent to Sasa.Dynamics means I can also easily build a trace of the operations performed for a given type T, generate a function to do it all in one step, and cache that somewhere for when I need to rerun it. Basically, it would be a small tracing JIT for any reflection-based operation.

There are still a few cases I haven't fully optimized for deep copies, but it seems to work pretty well so far.

Sasa's binary serializer is also based on Sasa.Dynamics, but that hasn't received any review or optimization effort, so while it passes many correctness tests, the performance isn't all that great. Still, if you're interested to see what a serializer based on structural induction looks like, it's a good reference.

## Thursday, April 18, 2013

### Impressions of Code Contracts

Embroiled in a few projects right now, but one gave me the chance to explore Microsoft's code contracts a little. I was initially excited about the prospect of contracts when they were first announced, hence my crude API-compatible implementation in Sasa.Contracts which allowed me to prepare my codebases for contracts. I've now had a chance to play with the real thing, so we'll see how it holds up to reality.

## Going Above and Beyond

As usual, I decided to push the boundaries and try to prove properties beyond what C# and .NET can do natively via their type systems. One common nuisance on the CLR is that you can't specify a default constructor for value types. While even code contracts can't prevent someone from creating an empty struct value, you can possibly prevent the use of such an empty value:

public struct NonNull<T>
where T : class
{
public NonNull(T value)
{
Contract.Requires(value != null);
this.value = value;
}
public T Value
{
get
{
Contract.Requires(Value != null);
return value;
}
}
}


We have here a simple class that wraps a nullable reference type. The preconditions specified on the constructor ensure that no NonNull instance can be created with an explicit null value. The only remaining possibility is to create a value via default(NonNull<T>), so contracts haven't bought us much there.

However, check out the precondition on the NonNull.Value property: before you can call the property, you have to ensure the property is itself not null. This ensures that only values of NonNull created via the provided constructor can use any value of NonNull!

Here's the failure that Visual Studio reports when it can't prove that the contracts are statically satisfied:

Mission accomplished! Through some clever application of preconditions, you can probably ensure all sorts of behavioural properties on objects you couldn't verify before, so this is fertile ground for experimentation and optimization.

## No Free Lunch

There's always a downside of course, and in this case it's the long contract check times. Visual Studio has an option to check contracts in the background after a build completes, which helps a little.

Also, there are a few limitations and bugs remaining in the MS's static checker. For instance, according to the docs, invariants declared on structs are supposedly ignored (section 6.6.1), but I discovered this isn't completely true (Microsoft Connect bug reported).

I also found another bug while testing the interface contracts, so caveat emptor!

Still, it's a promising framework and I plan to make use of it where I can to improve the reliability of my code. Sasa v0.9.4 will probably be the last release for .NET 3.5, so subsequent releases will exploit contracts as much as possible. In particular, Sasa.NonNull<T> will finally get a static analysis to ensure that property is respected!

## Sunday, April 7, 2013

### Sasa.Web.Url64 - URL-Safe Base64 Encoding

This is the thirteenth post in my ongoing series covering the abstractions in Sasa. Previous posts:

Base64 encodings are built into .NET, but the standard Base64 encoding is not safe to use in URLs. Sasa.Web.Url64 provides methods to convert to and from a URL-safe Base64 representation I refer to as Url64.

## Sasa.Web.Url64.FromUrl64

Sasa.Web.Url64.FromUrl64 is a simple extension method on strings to convert a Url64-encoded string to a byte array:

byte[] data = BitConverter.GetBytes(int.MinValue);
Console.WriteLine(data.ToUrl64());

int i = BitConverter.ToInt32(data.FromUrl64());
Console.WriteLine(i);
// output:
// aaaaGa
// -2147483648


## Sasa.Web.Url64.ToUrl64

Sasa.Web.Url64.FromUrl64 is a set of extension methods on byte arrays to convert raw bytes to a Url64-encoded string:

byte[] data = BitConverter.GetBytes(int.MinValue);
Console.WriteLine(data.ToUrl64());

int i = BitConverter.ToInt32(data.FromUrl64());
Console.WriteLine(i);
// output:
// aaaaGa
// -2147483648


## Thursday, April 4, 2013

### Sasa.Events - Type-Safe, Null-Safe, Thread-Safe Events

This is the twelfth post in my ongoing series covering the abstractions in Sasa. Previous posts:

It's well-known by now that the CLR's event model is a little broken. It requires clients using events to handle corner cases that should be handled by the runtime, particularly thread-safe event mutation and null-safe event invocation. Eric Lippert describes the issues.

Sasa.Events is a static class providing methods achieving just that. It makes mutating events/delegates thread-safe (#1 thread-safety from Eric's article), and makes invocation null-safe.

Sasa.Events.Add is a static method that takes a reference to an event type T and adds a new delegate of type T to that event in a thread-safe way without using locks. Typically, a public event declared in C# causes the C# compiler to create a hidden field of type System.Object, and to perform a lock on that object before modifying the event:

public class Foo
{
public event EventHandler SomeEvent;
}


Translates into:

public class Foo
{
EventHandler _someEvent;
object _someEventLock = new object();
public EventHandler SomeEvent
{
add { lock (_someEventLock) _someEvent += value; }
remove { lock(_someEventLoc) _someEvent -= value; }
}
}


Of course, being an immutable value, a multicast delegate doesn't need locks for mutation, we can just perform a lock-free, atomic compare-exchange in a loop until it succeeds:

public class Foo
{
EventHandler _someEvent;
public EventHandler SomeEvent
{
add { for (var e = _someEvent; e != Interlocked.CompareExchange(ref _someEvent, Func.Combine(_someEvent, value), e); e = _someEvent); }
remove { for (var e = _someEvent; e != Interlocked.CompareExchange(ref _someEvent, Func.Remove(_someEvent, value), e); e = _someEvent); }
}
}


This is both faster, and doesn't waste memory. Sasa.Events.Add performs exactly the above:

EventHandler _someEvent;
...


So instead of the shorthand event notation used in C#, just declare a delegate field and add the add/remove handlers like so:

public class Foo
{
EventHandler _someEvent;
public EventHandler SomeEvent
{
remove { Events.Remove(ref _someEvent, value); }
}
}


## Sasa.Events.Clear

Sasa.Events.Clear clears out the entire list of event handlers, and returns the original contents:

EventHandler _someEvent;
...
var x = Events.Clear(ref _someEvent);
// _someEvent is now null, and x has the original contents
x.Raise();


I often use something like the above for thread-safe, lock-free disposal patterns.

## Sasa.Events.Raise

Sasa.Events.Raise are a set of extension methods on various delegate types that provide null-safe event raising. In other words, C# developers no longer have to manually implement the following pattern:

event Action SomeEvent;
...
var someEvent = SomeEvent;
if (someEvent != null) someEvent();


Instead, they can simply call SomeEvent.Raise():

event Action SomeEvent;
event EventHandler OtherEvent;
...
SomeEvent.Raise();
OtherEvent.Raise(EventArgs.Empty);


Note that Raise is only supported for a core set of delegate types:

• All event handler delegates under System namespace
• All System.Action* delegates
• All event handler delegates under System.ComponentModel

## Sasa.Events.RaiseAny

Since not all delegate types can be included in Sasa.Events, and because delegates are typed nominally instead of structurally, we have Sasa.Events.RaiseAny, which takes an array of object parameters and performs a thread-safe dynamic runtime invocation of the event:

delegate void Foo(string arg0, int arg1);
...
event Foo FooEvent;
...
FooEvent.Raise("first arg", 3);


## Sasa.Events.Remove

The complementary operation to Sasa.Events.Add, Sasa.Events.Remove performs a type-safe, thread-safe event mutation without locks:

EventHandler _someEvent;
...
Events.Remove(ref _someEvent, (o,e) => ...);


## Tuesday, April 2, 2013

### Sasa's Core Interfaces

This is the eleventh post in my ongoing series covering the abstractions in Sasa. Previous posts:

I covered some of Sasa's core interfaces previously, but I shall provide a more thorough treatment here.

## Sasa.IValue<T>

Fundamentally, programs manipulate values. These values can often be classified into various categories depending on how they can be manipulated or computed. At the most basic level, we have a simple value represented by Sasa.IValue<T>. IValue<T> provides only a single property to access the encapsulated value:

IValue<int> x = new Immutable<int>(3);
Console.WriteLine(x.Value);
// output:
// 3


This demonstrates the use of a simple immutable value class, but the Value property need not be so simple. It can even throw exceptions in some cases. For instance, as covered in a previous article Sasa.Result<T>.Value throws InvalidOperationException if the result was an error instead of a value.

## Sasa.IRef<T>.Value

Sasa.IRef<T>.Value extends the read-only Sasa.IValue<T> with a setter for the Sasa.IRef<T>.Value property:

IRef<int> x = new Ref<int>(3);
x.Value = 999;
Console.WriteLine(x.Value);
// output:
// 999


## Sasa.IVolatile<T>.TryGetValue

Some values may or may not be present, and it's often necessary to check for the presence of a legitimate value and to obtain that value in a single step. Enter IVolatile<T>, which provides a standard interface for the common TryGetValue pattern:

IVolatile<int> withValue = new Option<int>(3);
int value;
if (withValue.TryGetValue(out value)) Console.WriteLine(value);

IVolatile<int> noValue = Option<int>.None;
if (noValue.TryGetValue(out value)) Console.WriteLine(value);

// output:
// 3


## Sasa.IResolvable<T>.HasValue

Similar to IVolatile<T>, IResolvable<T> standardizes an interface for values that may or may not be present by exporting a HasValue property:

IResolvable<int> withValue = new Option<int>(3);
if (withValue.HasValue) Console.WriteLine(withValue.Value);

IResolvable<int> noValue = Option<int>.None;
if (noValue.HasValue) Console.WriteLine(noValue.Value);

// output:
// 3


## Sasa.IOptional<T>

Sasa.IOptional<T> is an interface that implements IVolatile<T>, IResolvable<T>, and IValue<T>. It is implemented by many of the abstractions in Sasa that encapsulate values, like Sasa.Option<T> and Sasa.Result<T>.

## Sasa.IResult<T>

Sasa.IResult<T> describes values that resolve either to a value or an error. It's an abstraction that implements IOptional<T>, IVolatile<T>, IResolvable<T>, and IValue<T>, and also exports an Error property:

IResult<int> withValue = new Result<int>(3);
if (withValue.HasValue) Console.WriteLine(withValue.Value);

IResult<int> noValue = Result.Fail<int>(new ArgumentException());
if (noValue.HasValue)
Console.WriteLine(noValue.Value);
else
Console.WriteLine("Error: {0}", noValue.Error.Message);

// output:
// 3
// Error: ArgumentException ...


This interface is implemented by Sasa.Result<T> and a few other abstractions in Sasa. Sasa.Result also implements the LINQ query pattern on IResult<T> instances.

## Monday, April 1, 2013

### Sasa's Tuples

This is the tenth post in my ongoing series covering the abstractions in Sasa. Previous posts:

It's common to return multiple values from functions, and there are two common ways to do so in .NET: out parameters, and ordinary objects like structs and classes.

Unfortunately, defining a whole class just to return two or three values is often overkill. Also, out parameters have some limitations, like inability to use them in lambdas, even when it's safe to do so.

Enter tuples, which are types containing only generic parameters whose only purpose is to group some items together to address these difficulties. Sasa's ITuple interfaces [1, 2, 3, 4] define the abstract contracts satisfied by Sasa's tuple types. However, unlike .NET's newly released tuples, Sasa's implementation tuples don't use the "tuple" name. They are instead split into Pair, Triple, and Quad because I found the shared "tuple" name often confusing when auditing code. Particularly where nested generics are concerned, like enumerable sequences of tuples, it's often hard to distinguish Tuple<string,int,int> from Tuple<string,int,int,int> while refactoring.

## Sasa.ITuple<T>.First

Sasa.ITuple<T>.First is a property that permits clients to access the first item in a tuple of arbitrary size:

var x = Tuples.Create(3, "foo");
Console.WriteLine(x.First);
// output:
// 3


This property is implemented by Pair, Triple and Quad.

## Sasa.ITuple<T0, T1>.Second

Sasa.ITuple<T0, T1>.Second is a property that permits clients to access the second item in a tuple of arbitrary size:

var x = Tuples.Create(3, "foo");
Console.WriteLine(x.Second);
// output:
// foo


This property is implemented by Pair, Triple and Quad.

## Sasa.ITuple<T0, T1, T2>.Third

Sasa.ITuple<T0, T1, T2>.Third is a property that permits clients to access the third item in a tuple of arbitrary size:

var x = Tuples.Create(3, "foo", 123.4M);
Console.WriteLine(x.Third);
// output:
// 123.4


This property is implemented by Triple and Quad.

## Sasa.ITuple<T0, T1, T2>.Fourth

Sasa.ITuple<T0, T1, T2>.Fourth is a property that permits clients to access the fourth item in a tuple of arbitrary size:

var x = Tuples.Create(3, "foo", 123.4M, "hello world!");
Console.WriteLine(x.Fourth);
// output:
// hello world!


This property is implemented by Quad.

## Sasa.Tuples.Create

Sasa.Tuples.Create is a set of overloaded static methods that to conveniently create tuples exploiting C#'s type inference:

var quad = Tuples.Create(3, "foo", 123.4M, "hello world!");
var triple = Tuples.Create(3, "foo", 123.4M);
var pair = Tuples.Create(3, "foo");


## Sasa.Tuples.Keyed

Sasa.Tuples.Keyed is a static method to create a System.Collections.Generic.KeyValuePair<TKey, TValue>. It exploits C#'s type inference to make it easy to create key value pairs without having to explicitly specify all the type information:

var dict = new Dictionary<int, string>();


## Sasa.Pair<T0, T1>.Bind

Sasa.Pair<T0, T1>.Bind is a method that extracts all of a Pair's values in one step using "out" parameters. So even if you prefer out parameters to tuples, you can easily use an interface that uses Sasa's tuples:

int i;
string foo;
Tuples.Create(3, "foo")
.Bind(out i, out foo);


## Sasa.Triple<T0, T1, T2>.Bind

Sasa.Triple<T0, T1, T2>.Bind is a method that extracts all of a Triple's values in one step using "out" parameters. So even if you prefer out parameters to tuples, you can easily use an interface that uses Sasa's tuples:

int i;
string foo;
decimal d;
Tuples.Create(3, "foo", 123.4M)
.Bind(out i, out foo, out d);


Sasa.Quad<T0, T1, T2, T3>.Bind is a method that extracts all of a Quad's values in one step using "out" parameters. So even if you prefer out parameters to tuples, you can easily use an interface that uses Sasa's tuples:

int i;
string foo;
decimal d;
Tuples.Create(3, "foo", 123.4M)
.Bind(out i, out foo, out d);


## Sasa.Pair<T0, T1>.ToKeyValue

Sasa.Pair<T0, T1>.ToKeyValue is a method that converts a Pair into a KeyValuePair:

var dict = new Dictionary<int, string>();


## Closing Remarks

All of the tuple implementations implement equality, GetHashCode, and comparison overloads accounting for each encapsulated element. The tuples are also explicitly defined as fully immutable via the readonly qualifier on their fields. This means that Sasa.Dynamics.Types.MaybeMutable will return false if every generic argument is similarly immutable.

I stopped at Quad<T0, T1, T2, T3> because beyond four values you should probably be creating a specific class to encapsulate the return values, or defining your function to take a callback that creates the specific type you want, ie. in the same fashion as SelectMany.

### Prim's Minimum Spanning Tree

Taking a break from Sasa blog posts, I ran into a problem that would be nicely solved by extracting the minimum spanning tree. Turns out this is pretty simple to solve naively in C# using only IEnumerable<T>:

/// <summary>
/// Computes the minimum spanning tree.
/// </summary>
/// <param name="edges">The list of edges.</param>
/// <remarks>
/// Given a list of edges whose vertices are consecutive numbers starting
/// from 0, this extension method returns an enumerable sequence of the
/// edges describing the minimum spanning tree.
/// </remarks>
public static IEnumerable<Edge> MinSpanTree(this IEnumerable<Edge> edges)
{
var span = edges.ToList();
var count = 1 + span.Max(x => Math.Max(x.From, x.To));
edges.Sort();
var vnew = new BitArray(count);
vnew[0] = true;
for (var i = 0; i < count; ++i)
{
foreach (var x in edges)
{
if (vnew[x.From] ^ vnew[x.To])
{
yield return x;
vnew[x.From] = vnew[x.To] = true;
break;
}
}
}
}


An Edge is a simple class that encapsulates two vertex numbers and a weight represented by a double. It's also IComparable, so we can sort on it using the weight.

Prim's algorithm selects the minimum weighted edge between a vertex we have not yet accepted, and a vertex that we have accepted. We use a bit array to track the vertex numbers we've accepted, and simply search weight-sorted edge list for the first entry where one vertex is accepted, and the other is not. This is an O(V2), where V is the number of vertices. We could also contract the list after each accepted edge, but that doesn't change the overall time complexity.

A simple adjacency matrix representation using a two-dimensional array of doubles is also easily definable:

/// <summary>
/// Computes the minimum spanning tree.
/// </summary>
/// <param name="edges"></param>
/// <remarks>
/// Given an adjacency matrix describing the weighted edges, where
/// vertices are the indices of the matrix, this extension method
/// returns an enumerable sequence of the edges describing the
/// minimum spanning tree.
///
/// Vertices that have no edges between them should have
/// <see cref="double.NaN"/> or <see
/// cref="double.PositiveInfinity"/> in the corresponding
/// matrix entry.
/// </remarks>
public static IEnumerable<Edge> MinSpanTree(this double[,] edges)
{
if (edges.RowCount() != edges.ColumnCount())
throw new ArgumentException("Matrix row count must equal column count.", "edges");
// convert the adjacency matrix into a list of edges
var count = edges.RowCount();
var span = new List<Edge>(count);
for (int i = count - 1; i >= 0; --i)
{
for (int j = 0; j < i; ++j)
{
var w = edges[i, j];
if (!double.IsNaN(w) && w < double.PositiveInfinity)