Feedback

C# - TreeEnumerator

Veröffentlicht von am 02.11.2015
(0 Bewertungen)
Die Klasse TreeEnumerable enthält Erweiterungsmethoden welche es erlauben die Elemente von hierarchischen Objektstrukturen linear (als IEnumerable<T>) zu durchlaufen.

Die Elemente können dabei entweder "depth first" oder "breadth first" durchlaufen werden.
GFU-Schulungen  [Anzeige]

VB.NET Einführung

Die Schulung zeigt Ihnen, wie Sie einfache, benutzerorientierte Programme, die auf Datenbanken zugreifen, in VB.NET eigenständig entwickeln. 

VB.NET Komplett

Sie stehen vo der Aufgabe, individuelle Anwendungen für Windows zu schreiben. Hier ist VB.NET die optimale Sprache. Sie erlernt sich recht leicht und passt sich komplett in die .NET Umgebung von Microsoft ein. Nach der Schulung entwickeln Sie anwenderfreundliche Programme in VB.NET . Mit den objektorientierten Modellen in VB.NET erzeugen Sie außerdem wiederverwendbare Komponenten.

using System;
using System.Collections.Generic;
  /// <summary>
  ///   Provides a set of static extension methods, which supports simple iteration
  ///   over a graph stuctures.
  /// </summary>
  public static class TreeEnumerable
  {
    #region BreadthFirst

    /// <summary>
    ///   Linearizes the specified graph, traversing it breadth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a breadth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> BreadthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                         Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      Queue<TNode> queue = new Queue<TNode>(256);

      foreach (TNode node in nodes)
      {
        queue.Enqueue(node);
      }

      return BreadthFirst(queue, getSubNodes);
    }

    private static IEnumerable<TNode> BreadthFirst<TNode>(Queue<TNode> queue,
                                                          Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      TNode node;

      while (queue.Count > 0)
      {
        node = queue.Dequeue();

        if (node == null)
        {
          yield break;
        }

        foreach (TNode subNode in getSubNodes(node))
        {
          queue.Enqueue(subNode);
        }

        yield return node;
      }
    }

    #endregion

    #region BreadthFirst (repeat Nodes)

    /// <summary>
    ///   Linearizes the specified graph, traversing it breadth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <param name="repeatNodes">
    ///   A value that determines if nodes are being traversed repeated.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a breadth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> BreadthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                         Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                         Boolean repeatNodes)
    {
      HashSet<TNode> passedNodes = new HashSet<TNode>();
      Queue<TNode> queue = new Queue<TNode>(256);

      if (repeatNodes)
      {
        return nodes.BreadthFirst(getSubNodes);
      }

      foreach (TNode node in nodes)
      {
        if (passedNodes.Contains(node))
        {
          continue;
        }

        passedNodes.Add(node);

        queue.Enqueue(node);
      }

      return BreadthFirst(queue, getSubNodes, passedNodes);
    }

    private static IEnumerable<TNode> BreadthFirst<TNode>(Queue<TNode> queue,
                                                          Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                          HashSet<TNode> passedNodes)
    {
      TNode node;

      while (queue.Count > 0)
      {
        node = queue.Dequeue();

        if (node == null)
        {
          yield break;
        }

        foreach (TNode subNode in getSubNodes(node))
        {
          if (passedNodes.Contains(subNode))
          {
            continue;
          }

          passedNodes.Add(subNode);

          queue.Enqueue(subNode);
        }

        yield return node;
      }
    }

    #endregion
  

    #region DepthFirst

    /// <summary>
    ///   Linearizes the specified graph, traversing it depth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="node">
    ///   A node that represents the root element of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> DepthFirst<TNode>(TNode node, Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      return new[] { node }.DepthFirst(getSubNodes);
    }

    /// <summary>
    ///   Linearizes the specified graph, traversing it depth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                       Func<TNode, IEnumerable<TNode>> getSubNodes)
    {
      foreach (TNode node in nodes)
      {
        yield return node;

        foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes))
        {
          yield return subNode;
        }
      }
    }

    #endregion

    #region DepthFirst (repeat Nodes)

    /// <summary>
    ///   Linearizes the specified graph, traversing it depth-first.
    /// </summary>
    /// <typeparam name="TNode">
    ///   The type of the nodes.
    /// </typeparam>
    /// <param name="nodes">
    ///   A collection of nodes which are representing the root elements of the graph.
    /// </param>
    /// <param name="getSubNodes">
    ///   A function that defines how to get the sub notes for each node.
    /// </param>
    /// <param name="repeatNodes">
    ///   A value that determines if nodes are being traversed repeated.
    /// </param>
    /// <returns>
    ///   An IEnumerable(Of TNode) that contains elements from the graph in a depth-first linearized sequence.
    /// </returns>
    public static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                       Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                       Boolean repeatNodes)
    {
      if (repeatNodes)
      {
        return nodes.DepthFirst(getSubNodes);
      }

      return nodes.DepthFirst(getSubNodes, new HashSet<TNode>());
    }

    private static IEnumerable<TNode> DepthFirst<TNode>(this IEnumerable<TNode> nodes,
                                                        Func<TNode, IEnumerable<TNode>> getSubNodes,
                                                        HashSet<TNode> passedNodes)
    {
      foreach (TNode node in nodes)
      {
        if (passedNodes.Contains(node))
        {
          continue;
        }

        passedNodes.Add(node);

        yield return node;

        foreach (TNode subNode in getSubNodes(node).DepthFirst(getSubNodes, passedNodes))
        {
          yield return subNode;
        }
      }
    }

    #endregion
  }
Abgelegt unter LINQ, Baumstruktur.

1 Kommentare zum Snippet

Tachyon schrieb am 02.11.2015:
Usage:

// class Item { public Item[] Items { get; set; } }
var allItemsDepthFirst = items.DepthFirst(i => i.Items);
var allItemsBreadthFirst = items.BreadthFirst(i => i.Items);
 

Logge dich ein, um hier zu kommentieren!