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]

Visual Studio Team Foundation Server 2017/2015 (TFS) für Projektmitglieder - Kompakt

Nach Teilnahme an dieser Schulung sind Ihnen die Grundlagen von ALM geläufig. Sie planen und steuern Projekte effizient mit dem Visual Studio Team Foundation Server.

C# Komplett

Sie kennen sich in objektorientierter Programmierung aus. Sie schreiben C++ oder Java? Und nun stehen Sie vor der Aufgabe, in C# Anwendungen zu erstellen. Das C# Komplett-Seminar verschafft Ihnen umfassende Programmierkenntnisse in dieser Sprache. Nach der Schulung entwickeln Sie selbständig Anwendungen mit C#. Sie kennen die Datentypen und Klassenbibliotheken der objektorientierten Programmiersprache C#. Der Komplettkurs setzt bei den Grundlagen von C# ein. Sie arbeiten mit Variablen und konvertieren Typen. Multithreading, Delegates, Generics sind nach dem Seminar für Sie kein Geheimnis mehr.

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!