非侵入式树和图类型

引言

Code Project 上已经发布了许多关于树的文章，例如 [Hajek 2004]、[Butler 2005] 和 [Chen 2006]。这些文章附带的代码库通常提供一个通用的 TreeNode<T> 类，该类封装了一个递归的一对多关系，并包装了类型为 T 的“data”对象。像这样的 TreeNode 类还将提供枚举器以及可能其他的查询方法。无疑，文章还会抱怨 .NET 在其标准集合库中缺乏通用的树类型。

其中一篇符合此描述的文章 [Hanekom 2007] 催生了 NGenerics 项目。NGenerics 提供了各种树和图结构及算法，全部在 .NET 中实现。这是一个很棒的项目，但恕我直言，它提供的只是一个参考实现。也就是说，其二进制文件不能直接从实际的数据库应用程序中使用。这个不足是由于该项目成立于 2006 年 12 月——远在 2007 年 11 月 C# 3.0 发布之前。

C# 3.0 中有哪些与可重用的树和图相关，甚至至关重要的呢？为了回答这个问题，我必须先解释为什么我从上面提到的任何文章中都从不直接使用现成的代码。简而言之就是：领域模型。

在我看来，设计数据库应用程序唯一负责任的方式就是使用领域模型。应用程序的领域模型由类组成，这些类的名称与其所建模的领域中的对应项相同（例如 Customer、Order、FarmersDaughter 等），以及这些类之间的关联。“TreeNode”描述的是一种数据结构，而不是一个“现实世界”中的对象——因此它不应该成为领域模型的一部分。

领域模型本身就可以很好地包含树结构，而无需任何第三方 TreeNode 类的帮助。它们通过使用 List 或 Set 类型来保存其“子”集合来实现。然而，一直缺乏的是一组通用的树相关操作库。直到 C# 3.0 出现之前，都没有一种直观的方法可以使这些操作可用于领域模型。

扩展方法的出现

C# 3.0 提供的用于构建通用树和图的关键要素是定义扩展方法的能力。（有关扩展方法在类库设计中的优点，请参阅 [Wagner 2009]。）使用树/图库不再必须侵入应用程序的领域模型。相反，库可以包含一个 ITreeNode 接口，供任何领域模型类实现。然后，库可以提供任意数量的扩展方法，这些方法作用于实现该接口的对象。为了演示这个想法，这是 Qnomad 的 CoreHelpers 库中的 ITreeNode<T> 版本。

public interface ITreeNode<T> : IContainer<T,T>, IContained<T,T>
  where T : ITreeNode<T>
{
}

该接口从两个基接口继承其成员，每个接口代表聚合关联中的一个角色。如果关联不是递归的，则这两个接口可以分别在不同的类上实现。另一方面，ITreeNode 结合了这两个角色。当关联是递归的时，ITreeNode 就被实现在单个类上。下面是两个基接口

public interface IContainer<TContainer, TItem>
  where TContainer : IContainer<TContainer, TItem>
  where TItem : IContained<TContainer, TItem>
{
    IList<TItem> SubItems { get; }
    bool HasSubItems { get; }
}

public interface IContained<TContainer, TItem>
  where TContainer : IContainer<TContainer, TItem>
  where TItem : IContained<TContainer, TItem>
{
    TContainer Parent { get; }
}

现在，这是库的 ITreeNodeExtensions 类中的两个方法

public static class ITreeNodeExtensions {

    /// <summary>
    /// Is this an ancestor of the given node?
    /// </summary>
    /// <param name="maybeDescendant">
    ///   A possible descendant of this node</param>
    /// <returns>Returns true if maybeDescendant, or
    ///   any of its ancestors, are equal to this node
    /// </returns>
    public static bool IsAncestorOf<T>( this ITreeNode<T> maybeAncestor,
      ITreeNode<T> maybeDescendant ) where T : ITreeNode<T> {
        if ( maybeDescendant == maybeAncestor )
            return true; //target found!
        else if ( maybeDescendant.Parent == null )
            return false; //target not found & nowhere left to look
        else //target not found, so progress towards tree root:
            return maybeAncestor.IsAncestorOf( maybeDescendant.Parent );
    }

    /// <summary>
    /// Returns an iterator that performs a breadth-first traversal of nodes.
    /// [Source: Generic Tree in C# (www.codeproject.com/KB/recipes/phSharpTree.aspx)]
    /// </summary>
    public static IEnumerable<T> BreadthFirstNodeEnumerator<T>(
      this ITreeNode<T> root ) where T : ITreeNode<T> {
        var todo = new Queue<T>();
        todo.Enqueue( (T)root );
        while ( todo.Count > 0 ) {
            T node = todo.Dequeue();
            if ( node.HasSubItems ) {
                foreach ( T child in node.SubItems )
                    todo.Enqueue( child );
            }
            yield return node;
        }
    }
}

为了让领域模型类利用这些扩展方法，它必须像下面这样实现 ITreeNode<T>

public class Category : ITreeNode<Category> {

    public Category() {
        SubCategories = new ObservableCollection<Category>();
    }

    private static Category root;
    private IList<Category> subCategories;
    private Category parentCategory;

    public static Category Root {
        get {
            if ( root == null ) {
                using ( IDatabaseManager dbMgr = App.CreateDbMgr() )
                    root = dbMgr.GetCategoryRoot();
            }
            return root;
        }
    }
    
    public IList<Category> SubCategories {
        get { return subCategories; }
        private set {
            subCategories = value;
            var sc = (INotifyCollectionChanged)subCategories;
            sc.CollectionChanged += new OneToManyAssocSync(
              this, "ParentCategory" ).UpdateManySide;
        }
    }

    public Category ParentCategory {
        get { return parentCategory; }
        set {
            Category oldParentCategory = parentCategory;
            parentCategory = value;
            OneToManyAssocSync.UpdateOneSide( this,
              oldParentCategory, parentCategory, "SubCategories" );
        }
    }
    
    public string Title { get; set; }

    #region ITreeNode Members

    Category IContained<Category, Category>.Parent {
        get { return ParentCategory; }
    }

    IList<Category> IContainer<Category, Category>.SubItems {
        get { return SubCategories; }
    }

    bool IContainer<Category, Category>.HasSubItems {
        get {
            return subCategories != null && subCategories.Count > 0;
        }
    }

    #endregion

    public override string ToString() {
        return GetType().Name + ": Title=\"" + Title + "\"";
    }
} 

因为 Category 领域类实现了 ITreeNode<Category>，客户端代码就可以进行类似以下的调用：

if ( categoryA.IsAncestorOf(categoryB) )
    ...

和

foreach ( Category c in Category.Root.BreadthFirstNodeEnumerator() )
    ...

一个真正的集合库可能会包含各种遍历顺序和种类的枚举器，以满足各种需求。这些枚举器还允许您利用 LINQ to Objects。有关示例，请参阅 [Flower 2008] 中“使用扩展方法和‘LINQ to Trees’”部分。

（如果您有兴趣使用 Category 源代码中引用的 OneToManyAssocSync 实用程序类，您也可以在 Qnomad 的 CoreHelpers 库中找到它。）

结论

随着 C# 3.0 和扩展方法的发布，将可重用的树和图类型添加到 .NET 标准集合框架的希望变得更加光明。

历史

• 2009 年 4 月 22 日：初始发布
• 2009 年 5 月 19 日：将 ITreeNode 设为泛型并更新相关代码
• 2011 年 4 月 4 日：添加了 IContainer 和 IContained 接口