Für ein Problem gibt es häufig viele Lösungen.Für kaum ein Arbeitsfeld gilt das so sehr wie für die Informatik, wo es häufig dutzende konkurrierender Ansätze gibt. Ein Beispiel dafür, wie mannigfaltig das Spektrum an Lösungen sein kann, zeigte sich kürzlich in einem Projekt, als es darum ging ein Kreuzprodukts über einen selbstgeschriebenen Datentypen zu erzeugen. Für dieses spezielle Kreuzprodukt gilt das aus der Mathematik bekannte Kommutativgesetz (a*b = b*a). D.h. für eine Kombination aus zwei Objekten dieses Typs ist es gleich, ob man ein Paar (InstanzA, InstanzB) oder das “umgekehrte” Paar (InstanzB, InstanzA) vor sich hat.

Mittels Linq ist es ein Leichtes, ein solches Kreuzprodukt zu berechnen:

var crossProduct = from b1 in blocks
                  from b2 in blocks
                  where b1.Id != b2.Id &&
                          b1.Length + b2.Length <= parameters.MaximumSizeInMeters &&
                          b1.Weight + b2.Weight <= parameters.MaximumWeightInTons
                  select new { Block1 = b1, Block2 = b2 };

Allerdings erhält man hierdurch beide Paare (A,B) und (B,A). Es böte sich an dieser Stelle an, mit einem Aufruf der Extension-Methode Distinct(), alle Duplikate herauszufiltern.

Diese Methode funktioniert zwar prinzipiell mit anonymen Datentypen (also den Objekten, die ich mittels new {Block1, Block2} erzeuge). Es gibt jedoch keinen (direkten) Weg, der Abfrage beizubringen, dass die Reihenfolge der Elemente eines Paares in diesem Fall keine Rolle spielt.

Für die Methode Distinct() gibt es aber eine Überladung, die einen Parameter vom Typ IEqualityComparer<T> erwartet. Implementierungen dieses Interface werden verwendet um Objekte auf Gleichheit zu prüfen und funktionieren analog zum Überschreiben der Methoden Equals() und GetHashCode(). Der Vorteil ist, dass man diese Comparer jederzeit austauschen kann, wohingegen Änderungen an den überschriebenen Methoden immer mit Vorsicht zu genießen sind, weil schnell unerwartete Seiteneffekte auftreten.

Doch zunächst einmal braucht man eine Implementierung von IEqualityComparer<T>, der man on-the-fly Vergleichs- und Hashfunktion mitgeben kann. Diese Implementierung heißt LambdaEqualityComparer:

public class LambdaEqualityComparer<T> : EqualityComparer<T>
{
   private readonly Func<T, T, bool> equals;
   private readonly Func<T, int> hash;

   public LambdaEqualityComparer(Func<T, T, bool> equals)
       : this(equals, obj => obj.GetHashCode())
   {
   }

   public LambdaEqualityComparer(Func<T, T, bool> equals, Func<T, int> hash)
   {
       if (equals == null) throw new ArgumentNullException("equals");
       if (hash == null) throw new ArgumentNullException("hash");

       this.equals = equals;
       this.hash = hash;
   }

   public override bool Equals(T x, T y)
   {
       if (x == null) throw new ArgumentNullException("x");
       if (y == null) throw new ArgumentNullException("y");

       return equals(x, y);
   }

   public override int GetHashCode(T obj)
   {
       if (obj == null) throw new ArgumentNullException("obj");

       return hash(obj);
   }
}

Und um diesen für anonyme Typen verwenden zu können kommt ein weiteres Feature aus .NET3.0 zum Einsatz: Extension-Methoden.

public static class EnumerableExtensions
{
   public static IEnumerable<T> Distinct<T>(this IEnumerable<T> items,
       Func<T, T, bool> equals, Func<T, int> hash)
   {
       if (items == null) throw new ArgumentNullException("items");
       if (equals == null) throw new ArgumentNullException("equals");
       if (hash == null) throw new ArgumentNullException("hash");

       return items.Distinct(new LambdaEqualityComparer<T>(equals, hash));
   }
}

Damit kann man folgende Abfrage definieren, die das Kreuzprodukt mit lediglich einem Repräsentanten jeder Kombinationsmöglichkeit liefert:

var crossProduct = (from b1 in blocks
                   from b2 in blocks
                   where b1.Id != b2.Id &&
                           b1.Length + b2.Length <= parameters.MaximumSizeInMeters &&
                           b1.Weight + b2.Weight <= parameters.MaximumWeightInTons
                   select new { Block1 = b1, Block2 = b2 })

                   .Distinct((x, y) =>
                                       {
                                           if (x.Block1.Id == y.Block1.Id && x.Block2.Id == y.Block2.Id)
                                               return true;

                                           if (x.Block1.Id == y.Block2.Id && x.Block2.Id == y.Block1.Id)
                                               return true;

                                           return false;
                                       },
                                                  
                               x => x.Block1.Id.GetHashCode() ^ x.Block2.Id.GetHashCode());

Diese Lösung verwendet einige Bausteine aus dem .NET 3.x Feature-Set und zeigt durchaus eindrucksvoll, wie mächtig diese Funktionen sein können. Allerdings leidet durch die Verschachtelung der Abfragen für das eigentliche Kreuzprodukt und der Vergleichslogik die Lesbarkeit sehr stark. Eine sehr viel leichter zu durchschauende Lösung würde entstehen, wenn man den Comparer durch ein simples new() erzeugen, und als Parameter verwenden könnte. Dafür müsste man allerdings auf die Verwendung von anonymen Typen verzichten. Eine solche Lösung sähe dann folgendermaßen aus:

[DebuggerDisplay("{Block1.Id} {Block2.Id}")]
public class BlockPair
{
   public Block Block1 { get; set; }
   public Block Block2 { get; set; }
} 

Steht statt eines anonymen Typen ein deklarierter .NET-Datentyp zur Verfügung, so kann auch der Comparer durch eine spezifische, dafür aber einfachere, Implementierung ersetzt werden.

public class CompareCrossProduct : IEqualityComparer<BlockPair>
{
   public bool Equals(BlockPair x, BlockPair y)
   {
       if (x.Block1.Id == y.Block1.Id && x.Block2.Id == y.Block2.Id)
           return true;

       if (x.Block1.Id == y.Block2.Id && x.Block2.Id == y.Block1.Id)
           return true;

       return false;
   }

   public int GetHashCode(BlockPair x)
   {
       return x.Block1.Id.GetHashCode() ^ x.Block2.Id.GetHashCode();
   }
} 

Und so erhält man wieder eine deskriptive Abfrage, die man nicht erst gedanklich kompilieren muss, um sie zu verstehen:

var crossProduct = (from b1 in blocks
                   from b2 in blocks
                   where b1.Id != b2.Id &&
                         b1.Length + b2.Length <= parameters.MaximumBlockSizeInMeters &&
                         b1.Weight + b2.Weight <= parameters.MaximumBlockWeightInTons
                   select new BlockPair { Block1 = b1, Block2 = b2 })
                  .Distinct(new CompareCrossProduct());

Einen Pferdefuß haben allerdings beide Lösungen noch. Durch den Vergleich b1.Id != b2.Id handelt es sich immer um eine Abfrage mit quadratischer Komplexität O(n²). Mit dieser Überlegung im Hinterkopf ergibt sich noch eine dritte Lösung. Durch zwei ineinander geschachtelte Schleifen kann man die die Prüfung der Paarungen geschickt umgehen.

List<Block> blockList = new List<Block>(blocks);
List<BlockPair> crossProduct = new List<BlockPair>();

for (int i = 0; i < blockList.Count; i++)
{
   for (int j = i + 1; j < blockList.Count; j++)
   {
       Block b1 = blockList[i];
       Block b2 = blockList[j];

       if (b1.Length + b2.Length <= parameters.MaximumSizeInMeters &&
           b1.Weight + b2.Weight <= parameters.MaximumWeightInTons)
       {
           crossProduct.Add(new BlockPair { Block1 = b1, Block2 = b2 });
       }
   }
} 

Keine Lambdas, kein Linq. Technologisch vollkommen unaufgeregt. Und doch funktioniert dieser Ansatz mindestens genauso gut, wie die beiden vorherigen. Die innere Schleife beginnt eine Position hinter dem aktuellen Laufindex der äußeren zu zählen. Dadurch kommen keine Permutationen bei der Kombination zustande und man kann zwei Instanzen des Datentyps, die die vorgegebenen Rahmenbedingungen einhalten, ganz einfach miteinander verknüpfen.

Wie man deutlich sieht erlauben neue Technologien dem Entwickler erhöhten Freiraum bei der Umsetzung von Anforderungen. Viele Aufgaben lassen sich komfortabler und schneller lösen. Doch wie so häufig gilt auch hier, dass man genau abwägen muss, ob eine technologisch machbare Lösung zugleich auch eine für das Projekt vorteilhafte ist.