Non-intrusive Tree & Graph Types
Автор: Adrian Alexander
Источник:
CodeProject
Introduction
Several articles about trees have already been published on Code Project, such as [Hajek 2004], [Butler 2005], and [Chen 2006]. The code library attached to such an article usually provides a generic TreeNode<T> class that encapsulates a recursive one-to-many relationship and wraps a "data" object of type T. A TreeNode class like this will also provide enumerators and perhaps other query methods. Undoubtedly, the article will also bemoan .NET's lack of a general-purpose tree type in its standard collections library.
One such article [Hanekom 2007] that fits this description led to the NGenerics project. NGenerics provides a variety of tree and graph structures and algorithms, all implemented in .NET. It's a great project but, in my opinion, what it provides is a reference implementation. That is, its binaries are not directly usable from a real database application. The deficiency is due to the project's founding in December 2006 — long before the release of C# 3.0 in November 2007.
What about C# 3.0 is relevant, even essential, to reusable trees and graphs? To answer that question, I must first explain why I never find myself using code out-of-the-box from any of the above-mentioned articles. The short answer is simply: The Domain-Model.
The one and only responsible way to architect database applications, IMHO, involves using a domain-model. An application's domain-model consists of classes named after their counterparts in the domain being modelled (e.g. Customer, Order, FarmersDaughter, etc.) and associations between those classes. "TreeNode" describes a data-structure rather than a "real-world" object — thus it should not be part of a domain-model.
Domain-models include tree structures just fine, without help from any third-party's TreeNode class. They do so by using a List or Set type to hold their "children" collection. What has been lacking, however, is a library of general tree-related operations. An intuitive way of making such operations available for use with domain-models didn't exist until C# 3.0 came along.
Advent of Extension Methods
The essential ingredient for cooking up generalised trees and graphs, that C# 3.0 provides, is the ability to define Extension Methods. (For a succinct overview of Extension Methods' merit points for class library design, see [Wagner 2009].) Utilising a tree/graph library no longer must intrude upon the application's domain-model. Instead, the library can contain an ITreeNode interface for any domain-model class to implement. Any number of extension methods are then provided by the library, that operate on objects that implement the interface. In order to demonstrate this idea, here is the version of ITreeNode<T> from Qnomad's CoreHelpers library:
This interface inherits its members from two base interfaces, each of which represents a role in a aggregative association. These two interfaces can be implemented individually on different classes if the association is not recursive. ITreeNode, on the other hand, combines the two roles. When the association is recursive, then ITreeNode is implemented on a single class. Here are the two base interfaces:
Now here are two methods in the library's ITreeNodeExtensions class:
In order for a domain-model class to take advantage of those extension methods, it must implement ITreeNode<T> like this one does:
Because the Category domain class implements ITreeNode
and:
A real collections library would likely include numerous enumerators of various traversal orders and kinds, to fulfill a variety of needs. Such enumerators also allow you to take advantage of LINQ to Objects. See the "Using Extension Methods and 'LINQ to Trees'" section of [Flower 2008] for examples of this.
(If you are interested in using the OneToManyAssocSync utility class referenced in Category's source code, you can find it, too, in Qnomad's CoreHelpers library.)
Conclusion
With the release of C# 3.0 and Extension methods, the hope becomes brighter for adding reusable tree and graph types to the standard .NET collections framework.