2010-09-02 8 views
7

Ich habe eine Klasse wie:Ist es möglich, schreiben eine rekursive IEnumerable <T>

class Spline 
    int ChildrenCount; 
    Spline GetChild (int index) 

class SplineCollection : IEnumerable<Spline> 
    Spline Master 

Ist es möglich, eine rekursive IEnumerable für die SplineCollection zu schreiben, wo es alle Kinder eins nach dem anderen zurück?

EDIT: So Master ist die Root-Box, und die Hierarchie seiner Kinder kann jede Tiefe sein.

EDIT: Mit dem Namen Box, glaube ich, ich verwirrte einige Leute. Es soll ein geometrisches Objekt sein, kein Container. Also ändere ich es zu Spline.

+1

Ich nehme an, Sie meinen "Nachkommen", wenn Sie "Kinder" schreiben, da die Kinder keine Rekursion benötigen. –

+0

@Job, ja du hast Recht ich meinte Nachkommen. Es ist nur so, dass in der SDK, die ich verwende, sie immer noch als Children, ChildrenRecursive bezeichnet werden, deshalb habe ich das gerade benutzt. –

Antwort

9

Dies wird eine Tiefe zuerst Traversal der Box 'Baum' tun. Sie können diese Methode dann einfach im Feld Master aufrufen, um alle rekursiven untergeordneten Elemente zurückzugeben.

public class Box 
{ 
    // ... 

    public IEnumerable<Box> GetBoxes() 
    { 
     yield return this; 

     for (int i=0; i<box.ChildrenCount; i++) 
     { 
      foreach (Box child in box.GetChild(i).GetBoxes()) 
      { 
       yield return child; 
      } 
     } 
    } 
} 
+0

Danke aber geht das durch die Kinder jeder Box.GetChild (i) auch? –

+0

Ah, jetzt macht es Sinn. Bearbeitete die Antwort. – thecoop

1
class Box 
{ 
    int ChildrenCount; 
    Box GetChild (int index){/* some implementation*/} 
    public IEnumerable<Box> Children 
    { 
    get 
    { 
     for(int i = 0; i != ChildrenCount; ++i) 
     yield return GetChild(i); 
    } 
    } 
    public IEnumerable<Box> Descendants 
    { 
    get 
    { 
     foreach(Box child in Children) 
     { 
     yield return child; 
     foreach(Box desc in child.Descendants) 
      yield return desc; 
     } 
    } 
    } 
} 

du von BoxCollection anrufen können, aber da Box bereits eine Sammlung von Boxen ist, sehe ich nicht, was BoxCollection Zweck hier ist. In diesem Fall würde die Verwendung der Box IEnumerable<Box> oder eines ihrer Nachkommen (ICollection<Box>, IList<Box>) wahrscheinlich die Nützlichkeit verbessern.

Es ist auch möglich, es eher iterativ als rekursiv zu machen, was manchmal eine bessere Leistung hat (so ziemlich zu jeder Zeit, wenn der Compiler die Rekursion nicht in interation umwandelt), aber rekursiv ist lesbarer und normalerweise mehr als performant genug.

-1

Sicher. Sie haben nicht einmal wirklich ein BoxContainer, da Kasten benötigen, durch seinen Namen, existiert als Container:

public class Box 
{ 
    private List<Box> myBoxes; 

    public IEnumerable<Box> GetAllBoxes() 
    { 
     yield return this; 
     foreach (var box in myBoxes) 
     { 
      var enumerator = box.GetAllBoxes().GetEnumerator(); 
      while(enumerator.MoveNext()) 
       yield return enumerator.Current; 
     } 
    } 
} 

Wenn Box A gehalten Boxen B und C, Feld B gehalten Boxen D und E und Feld C gehalten In Kasten F würde das Aufzählbare herauskommen A, B, D, E, C, F.

+0

Ihre 'foreach' führt effektiv zu einem Rückgabetyp von' IEnumerable > ', der nicht mit dem deklarierten Rückgabetyp übereinstimmt. Ich glaube nicht, dass das in C# kompiliert würde. In F # könntest du den zweiten "yield" in einen "yield" umwandeln und es würde gut funktionieren. –

+0

Sie sind genau richtig.Schnelle Bearbeitung, um das von der untergeordneten Box zurückgegebene IEnumerable zu durchlaufen. – KeithS

1

Ja, aber Sie müssen das rekursive Ergebnis aufzählen. Sie können es nicht einfach zurückgeben, weil der Typ nicht übereinstimmt.

IEnumerable<int> Triangle(int n) { 
    yield return n; 
    if (n > 0) 
     foreach (var e in Triangle(n - 1)) 
      yield return e; 
} 
10

Ich würde mit der manuellen Wartung eines Stapels gehen, anstatt sich auf den Call-Stack hier zu verlassen. Der Grund dafür ist, dass für jede besuchte Spline eine neue IEnumerable<Spline> erstellt werden müsste, wenn Sie den Aufruf-Stack verwenden, indem Sie rekursiv die Methode aufrufen, die die Nachkommen abruft. Das wäre ineffizient. Sie können das Traversal erheblich verbessern, indem Sie Ihren eigenen Stack verwenden.

+2

Ich wünschte, ich könnte das 10 Mal abstimmen. Das ist * so * viel effizienter als eine rekursive Lösung und erfordert nur ein paar Sekunden mehr Nachdenken. Tatsächlich könnte man dies in eine "Flatten" -Funktion verallgemeinern, um jeden rekursiven Iterator zu vereinfachen. –

Verwandte Themen