Exprimierenden Rekursion in LINQ
https://stackoverflow.com/questions/732281
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin ein LINQ-Anbieter zu einer hierarchischen Datenquelle zu schreiben. Ich finde es am einfachsten meine API zu entwerfen durch Beispiele Schreiben zeigen, wie ich es verwendet werden soll, und dann diese Anwendungsfälle Codierung zu unterstützen.
Eine Sache, Ich habe Probleme mit ist eine einfache / wiederverwendbar / elegante Art und Weise „tiefe Abfrage“ oder Rekursion in einer LINQ-Anweisung zum Ausdruck bringen. Mit anderen Worten, was ist der beste Weg, zu unterscheiden zwischen:
from item in immediate-descendants-of-current-node where ... select item
Vergleich:
from item in all-descendants-of-current-node where ... select item
( Bearbeiten. Sie keines dieser Beispiele beachten Sie oben notwendigerweise die Struktur der Abfrage reflektieren Ich möchte Ich interessiere mich für jeder gute Möglichkeit Rekursion / Tiefe auszudrücken )
Bitte beachten ich frage nicht, wie eine solche Anbieter zu implementieren, oder wie meine IQueryable oder IEnumerable in einer Weise, dass Rekursion erlaubt zu schreiben. Ich bin vom Standpunkt einer Person fragen, die LINQ-Abfrage zu schreiben und meinen Provider nutzen - was ist eine intuitive Art und Weise für sie zum Ausdruck bringen, ob sie wollen oder nicht Rekursion
Die Datenstruktur ähnelt ein typisches Dateisystem: ein Ordner eine Sammlung von Unterordner enthalten kann, und ein Ordner kann auch eine Sammlung von Elementen enthalten. So stellt myFolder.Folders alle Ordner, die unmittelbare Kinder myFolder sind, und myFolder.Items enthält alle Elemente sofort innerhalb myFolder. Hier ist ein einfaches Beispiel für eine Website Hierachie, ähnlich wie ein Dateisystem mit Ordnern und Seiten:
(F)Products
(F)Light Trucks
(F)Z150
(I)Pictures
(I)Specs
(I)Reviews
(F)Z250
(I)Pictures
(I)Specs
(I)Reviews
(F)Z350
(I)Pictures
(I)Specs
(I)Reviews
(I)Splash Page
(F)Heavy Trucks
(F)Consumer Vehicles
(I)Overview
Wenn ich schreiben:
from item in lightTrucks.Items where item.Title == "Pictures" select item
Was ist die intuitive Art und Weise eine Absicht zum Ausdruck bringt, dass die Abfrage alle Elemente unterhalb Licht Trucks bekommen, oder nur die unmittelbar welche? Die am wenigsten aufdringlich, niedrigste Reibung Art und Weise zwischen den beiden Absichten zu unterscheiden?
Mein Ziel # 1 ist in der Lage sein, diesen LINQ-Anbieter zu übergeben an anderen Entwicklern, die ein durchschnittliches Verständnis von LINQ haben und es ihnen ermöglichen, sowohl rekursive und Listenabfragen zu schreiben, ohne ihnen ein Tutorial geben rekursive lambdas auf dem Schreiben. Bei einer Nutzung, das gut aussieht, kann ich den Anbieter gegen das codieren.
Zusätzliche Klarstellung: (ich wirklich diese bei der Kommunikation am saugen!) - Dieser LINQ-Anbieter an einem externes System ist, ist es nicht einfach, ein Objekt Diagramm zu Fuß, noch in diesem speziellen Fall hat eine rekursive Ausdruck übersetzt eigentlich in jede Art von echten rekursive Aktivität unter der Haube. Nur muß einen Weg zwischen einer „tiefen“ Abfrage und einem „flachen“ zu unterscheiden.
Also, was denken Sie, ist der beste Weg, um es auszudrücken? Oder ist es eine Standardmethode, sie auszudrücken, dass ich auf verpasste?
Lösung
Linq-toXml behandelt diese in Ordnung, da ein XElement.Elements ist () /. Nodes () Betrieb sofort Kinder zu bekommen, und ein XElement.Descendents () / DescendentNodes () -Operationen alle Abkömmlinge zu erhalten. Würden Sie das als Beispiel in Betracht ziehen?
Linq-to-XML-Verhalten Zusammengefasst ... Die Navigationsfunktionen entsprechen jeweils eine Achse Typen in XPath ( http://www.w3schools.com/xpath/xpath_axes.asp ). Wenn das Navigationsfunktionselemente auswählt, wird die Achse Name verwendet. Wenn die Navigationsfunktion Knoten auswählt, wird der Achsnamens mit Knoten angehängt verwendet.
Zum Beispiel gibt es Funktionen Nachkommen () und DescendantsNode () entsprechen XPath Nachkommen Achse, entweder eine Rückkehr oder eine XElement XNode.
Der Ausnahmefall ist nicht überraschend der am häufigsten verwendete Fall der Kinder Achse. In XPath ist dies die verwendete Achse, wenn keine Achse angegeben ist. Dazu sind die Linq-to-xml Navigationsfunktionen nicht Kinder () und ChildrenNodes (), sondern Elemente () und Knoten ().
XElement ist ein Subtyp von XNode. XNode die gehören Dinge wie HTML-Tags, sondern auch HTML-Kommentare, CDATA oder Text. XElements sind eine Art von XNode, sondern beziehen sich speziell auf HTML-Tags. XElements daher einen Tag-Namen haben, und die Navigationsfunktionen unterstützen.
Nun ist es nicht so einfach zu Kettennavigations in Linq-to-XML als es XPath ist. Das Problem ist, dass Navigationsfunktionen Sammlung Objekte zurück, während die Navigationsfunktionen auf nicht-Sammlungen angewandt werden. Betrachten Sie den XPath-Ausdruck, der eine Tabelle Tag als unmittelbares Kind wählt dann jeder Nachkomme Tabellendaten-Tag. Ich denke, das aussehen würde wie „./children::table/descendants::td“ oder „./table/descendants::td“
Mit IEnumerable <> :: Select () erlaubt es, die Navigationsfunktionen auf einer Sammlung zu nennen. Das entspricht dem oben sieht so etwas wie .elements ( "table"). Select (T => T.Descendants ( "td"))
Andere Tipps
Nun, das erste, was zu beachten ist, dass tatsächlich, Lambda-Ausdrücke rekursiv sein kann. Nein im Ernst! Es ist nicht einfach zu tun, und sicher zu lesen ist nicht einfach - Heck, die meist LINQ-Anbieter (mit Ausnahme von LINQ-to-Objects, die viel einfacher ist) nur einen Hustenanfall hat Blick auf es ... aber es ist möglich . Sehen Sie hier für die volle, blutig Details (Warnung - Gehirn-Schmerz ist wahrscheinlich)
. Allerdings !! Das wird wahrscheinlich nicht viel ... für einen praktischen Ansatz helfen, ich auf dem Weg aussehen würde XElement etc macht es ... Hinweis: Sie können einen Teil der Rekursion mit einem Queue<T> oder Stack<T> entfernen:
using System;
using System.Collections.Generic;
static class Program {
static void Main() {
Node a = new Node("a"), b = new Node("b") { Children = {a}},
c = new Node("c") { Children = {b}};
foreach (Node node in c.Descendents()) {
Console.WriteLine(node.Name);
}
}
}
class Node { // very simplified; no sanity checking etc
public string Name { get; private set; }
public List<Node> Children { get; private set; }
public Node(string name) {
Name = name;
Children = new List<Node>();
}
}
static class NodeExtensions {
public static IEnumerable<Node> Descendents(this Node node) {
if (node == null) throw new ArgumentNullException("node");
if(node.Children.Count > 0) {
foreach (Node child in node.Children) {
yield return child;
foreach (Node desc in Descendents(child)) {
yield return desc;
}
}
}
}
}
Eine Alternative etwas wie SelectDeep zu schreiben sei (SelectMany für einzelne Ebene zu imitieren):
public static class EnumerableExtensions
{
public static IEnumerable<T> SelectDeep<T>(
this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
foreach (T item in source)
{
yield return item;
foreach (T subItem in SelectDeep(selector(item),selector))
{
yield return subItem;
}
}
}
}
public static class NodeExtensions
{
public static IEnumerable<Node> Descendents(this Node node)
{
if (node == null) throw new ArgumentNullException("node");
return node.Children.SelectDeep(n => n.Children);
}
}
Noch einmal, ich habe diese Rekursion zu vermeiden, nicht optimiert, aber es könnte leicht genug getan werden.
würde ich gehen mit ihm in einer solchen Art und Weise zur Durchführung der Kontrolle darüber haben, wie tief will ich auch abzufragen.
So etwas Nachkommen () würde Nachkommen durch alle Ebenen abrufen, während Nachkommen (0) sofort Kinder abrufen würde, Nachkommen (1) würden Kinder und Enkel bekommen und so weiter ...
Ich möchte nur zwei Funktionen implementieren, um klar zwischen den beiden Optionen (Kinder gegen FullDecendants) oder eine Überlastung GetChildren (bool returnDecendants) zu unterscheiden. Jeder kann IEnumerable implementieren, so wäre es nur eine Frage der sein, welche Funktion sie gehen in ihre LINQ-Anweisung.
Sie möchten vielleicht eine (Erweiterung) Methode wie FlattenRecusively für Ihre Art implementieren.
from item in list.FlattenRecusively() where ... select item
Rex, haben Sie geöffnet sicherlich eine interessante Diskussion, aber Sie scheinen alle Möglichkeiten beseitigt zu haben - das heißt, Sie scheinen beide ablehnen (1) mit dem Verbraucher rekursiven Logik schreiben, und (2) mit der Knotenklasse aussetzen Beziehungen von mehr als ein Grad.
Oder haben Sie vielleicht nicht ganz ausgeschlossen (2). Ich kann von einem mehr Ansatz denken, das fast so ausdrucksstark wie der GetDescendents Methode (oder Eigenschaft), aber vielleicht nicht ganz so ‚gewichtige‘ (abhängig von der Form des Baumes) ...
from item in AllItems where item.Parent == currentNode select item
und
from item in AllItems where item.Ancestors.Contains(currentNode) select item
ich müsste mit Frank zustimmen. haben Sie einen Blick auf, wie LINQ-to-XML verarbeitet diese Szenarien.
In der Tat, würde ich die LINQ-to-XML-Implementierung vollständig, emulieren, aber es für jeden Datentyp ändern. Warum das Rad neu zu erfinden Recht?
Sind Sie in Ordnung mit dem Heben schwerer Lasten in Ihrem Objekt zu tun? (Es ist nicht einmal so schwer)
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace LinqRecursion
{
class Program
{
static void Main(string[] args)
{
Person mom = new Person() { Name = "Karen" };
Person me = new Person(mom) { Name = "Matt" };
Person youngerBrother = new Person(mom) { Name = "Robbie" };
Person olderBrother = new Person(mom) { Name = "Kevin" };
Person nephew1 = new Person(olderBrother) { Name = "Seth" };
Person nephew2 = new Person(olderBrother) { Name = "Bradon" };
Person olderSister = new Person(mom) { Name = "Michelle" };
Console.WriteLine("\tAll");
// All
//Karen 0
//Matt 1
//Robbie 2
//Kevin 3
//Seth 4
//Bradon 5
//Michelle 6
foreach (var item in mom)
Console.WriteLine(item);
Console.WriteLine("\r\n\tOdds");
// Odds
//Matt 1
//Kevin 3
//Bradon 5
var odds = mom.Where(p => p.ID % 2 == 1);
foreach (var item in odds)
Console.WriteLine(item);
Console.WriteLine("\r\n\tEvens");
// Evens
//Karen 0
//Robbie 2
//Seth 4
//Michelle 6
var evens = mom.Where(p => p.ID % 2 == 0);
foreach (var item in evens)
Console.WriteLine(item);
Console.ReadLine();
}
}
public class Person : IEnumerable<Person>
{
private static int _idRoot;
public Person() {
_id = _idRoot++;
}
public Person(Person parent) : this()
{
Parent = parent;
parent.Children.Add(this);
}
private int _id;
public int ID { get { return _id; } }
public string Name { get; set; }
public Person Parent { get; private set; }
private List<Person> _children;
public List<Person> Children
{
get
{
if (_children == null)
_children = new List<Person>();
return _children;
}
}
public override string ToString()
{
return Name + " " + _id.ToString();
}
#region IEnumerable<Person> Members
public IEnumerator<Person> GetEnumerator()
{
yield return this;
foreach (var child in this.Children)
foreach (var item in child)
yield return item;
}
#endregion
#region IEnumerable Members
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
}
}
Ich würde einfach eine Erweiterungsmethode verwenden, den Baum zu durchqueren.
Oh, Moment mal, ich tue die bereits ! :)
