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]

JavaScript für .NET-Entwickler

Sie sind .NET-Entwickler und nun stehen Sie vor der Aufgabe, JavaScript in Ihre Arbeit einzubinden. Die Schulung vermittelt Ihnen die JavaScript Grundlagen und die Funktionen der Scriptsprache. Sie wissen, wie objektorientierte Programmierung in JavaScript funktioniert und lernen abschließend Best Practicies Fälle kennen.

C# 2017/2015/2013 Aufbau

In dieser Schulung lernen Sie fortgeschrittene Techniken im Bereich .Net C#. Dabei stehen neben den eigentlichen Techniken auch architektonische Aspekte im Mittelpunkt.

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!