Rekursive Struktur iterativ abfragen

[Matze]

Hallo zusammen,

ich habe eine rekursive Struktur, ähnlich eines Verzeichnisbaums. Sie dient dazu, ein Inhaltsverzeichnis in einem Dokument anzulegen.

Die zugehörige Klasse sieht so aus. Diese enthält den kompletten Inhaltsverzeichnis-Baum:

Code:

public class TOCEntry
{
   public string Title { get; set; }
   public int PageNum { get; set; }
   public List<TOCEntry> SubEntries { get; private set; }

   public TOCEntry()
   {
      SubEntries = new List<TOCEntry>();
   }
}

Nun ist es so, dass ein Hauptkapitel ein sog. "chapter" ist und ein Unterkapitel eine "section".

Durchlaufen und anzeigen kann ich das Inhaltsverzeichnis so:

Code:

private void AddTOC()
{
   foreach (TOCEntry RootSub in TOCData.SubEntries)
   {
      Chapter chapter = new Chapter(RootSub.Title, RootSub.PageNum);
      AddRecursive(RootSub, chapter, 2);
      
      myDocument.Add(chapter);
   }
}

private void AddRecursive(TOCEntry TOCe, Section section, int level) 
{
    foreach (TOCEntry child in TOCe.SubEntries)
    { 
        Section sub = section.AddSection(20, child.Title, level); 
        AddRecursive(child, sub, level + 1); 
    }
}

Das gibt mir das Inhaltsverzeichnis auf einmal aus. Ihr müsst den Code nicht exakt verstehen, es geht nur um die Vorgehensweise.

Nun würde ich das Dokument gerne durchgehen und auf der entsprechenden Seite die Kapitel ausgeben. Grob also so:

Code:

for (i = 1; i <= PageCount; i++)
{
    // hier müsste ich irgendwie den Baum (rekursiv) durchgehen und prüfen, ob die aktuelle Seitenzahl i mit einer im Baum übereinstimmt.
    // ist das der Fall, soll der zugehörige Eintrag ausgegeben werden.
}

Und genau das ist mein Problem. Ich weiß nicht, wie ich die zugehörigen "chapter" und "section" verwalten kann, dass ich auf diese zugreifen kann.

Hier noch ein Beispiel:

Code:

Kapitel 1, Seite 1
    Kapitel 1.1, Seite 2
    Kapitel 1.2, Seite 5
Kapitel 2, Seite 7
    Kapitel 2.1, Seite 8
        Kapitel 2.1.1, Seite 9

Das könnte der Baum sein, der in der Klasse "TOCEntry" steht.

Nun soll folgendes passieren, hier mal mit if-Anweisungen verdeutlicht:

Code:

for (i = 1; i <= pageNum; i++)
{
  if (i == 1)
    chapter1 = new chapter(...);
  else if (i == 2)
    section1 = chapter1.AddSection(...);
  else if (i == 5)
    section2 = chapter1.AddSection(...);
  else if (i == 7)
    chapter2 = new chapter(...);
  else if (i == 8)
    section3 = chapter2.AddSection(...);
  else if (i == 9)
    section4 = section3.AddSection(...);
}

"..." ist dabei die zugehörige Überschrift, die in der Klasse bei "Title" steht.

Wie löst man diese "Verschachtelungen"?

Grüße, Matze

[alzaimar]

Du erstellst einen sogenannten Iterator. Das ist ein Objekt, das zu einem Zeitpunkt immer genau
1. ... ein Element der rekursiven Struktur definiert
2. ... weiss, wo's als nächsts langgeht.

Zählen würde ich nicht, sondern eher mit einem 'First/Next/EndOfData()' Schema arbeiten.

Im Prinzip ist ein Iterator eine Liste von Ebenenpositionen: Pro Ebene ein Element und jedes Element hat die Aussage: "In dieser Ebene (des Baumes) bin ich gerade an dieser Position".
Eine Position ist definiert durch den Knoten sowie den aktuell besuchten Subknoten. Die unterste Position in dieser Liste zeigt naturgemäß auf ein Blatt.
Zunächst verweisen alle Positionen auf den ersten Unterknoten, das letzte Element somit auf das Blatt ganz links (First). Ein Aufruf von 'Next' geht nun zum nächsten Blatt, bis keins mehr da ist. Dann geht's eine Ebene nach oben, dort zum nächsten Unterknoten und dieser liefert wieder das erste Blatt. usw.

Irgendwann ist der Iterator überall an der letzten Position und kann einfach nicht weiter, dann liefern 'EndOfData' den Wert True.

Somit kann man so eine Struktur einfach so durchlaufen:

Code:

TreeIterator treeIterator = new TreeIterator(MyTree);

treeIterator.First();
while (!treeIterator.EndOfData) { 
  DoSomethingWith (treeIterator.CurrentItem());
  treeIterator.Next();
  }

[Khabarakh]

Hey hey ;) ,

so ganz ist mir noch nicht klar, was das Ziel ist. Du hast einen fertigen TOCEntry-Baum und durch den rekursiven Code den homomorphen Section-Baum. Jetzt suchst du zu einer bestimmten Seitenzahl das Section-Objekt, dessen TOCEntry diese PageNum hat? Dann würde ich in AddRecursive gleich noch ein Dictionary<int, Section> mitbefüllen - deutlich einfacher, als im Nachhinein in den Bäumen herumzusuchen :) .

/add
@alzaimar: An einen Iterator, also prinzipiell die Umwandlung des Baumes in eine leichter durchsuchbare Liste, hatte ich als erstes auch gedacht, aber gerade durch das Zusammenspiel der beiden Bäume gehe ich davon aus, dass die Daten/Beziehungen direkt beim Erstellen besser eingesammelt werden können.
Was du mit 'First/Next/EndOfData()' beschreibst, entspricht übrigens IEnumerable :) . Und die Pseudo-Koroutinen-C#-Iteratoren machen die Implementierung trivial.

Code:

public void IEnumerable<TOCEntry> Flatten()
{
    yield this;
    foreach (TOCEntry child in SubEntries)
        foreach (TOCEntry item in child.Flatten())
            yield child;
}

[alzaimar]

Zitat:

Zitat von Khabarakh

Was du mit 'First/Next/EndOfData()' beschreibst, entspricht übrigens IEnumerable :)

Code:

...yield child;...

Genau :wall: der Beginn seniler Demenz macht sich so bemerkbar.

[Reinhard Kern]

Zitat:

Zitat von Matze

Nun würde ich das Dokument gerne durchgehen und auf der entsprechenden Seite die Kapitel ausgeben.

Warum? Du kannst doch genausogut die Kapitel durchgehen (was du ja schon kannst) und das jeweilige Kapitel auf allen enthaltenen Seiten eintragen.

Gruss Reinhard

[Namenloser]

Hallo Matze,

sowas habe ich vor kurzem bei meinem Brainfuck-Compiler auch gebraucht. Hat mich auch etwas Hirnschmalz und Papier gekostet - der Algorithmus, der schließlich herausgekommen ist, ist folgender (hab mal ein paar Kommentare hinzugefügt):

Delphi-Quellcode:

  TElement = class
  private
    {...}
    FParent: TElementList;
    FChildren: TElementList;
    procedure SetParent(const Value: TElementList);
  public
    {...}
    property Parent: TElementList read FParent write SetParent;
    property Children: TElementList read FChildren;
    {...}
  end;

function TBrainFuckCompiler.GetNextElement(Element: TElement): TElement;
var
  Index: integer;
begin
  Result := nil;
  if Element.Children.Count > 0 then
    // Erstes Kindelement zurückliefern, falls vorhanden
    Result := Element.Children[0]
  else while Assigned(Element.Parent) and not Assigned(Result) do
  begin
    Index := Element.Parent.IndexOf(Element);
    // Folgen auf das aktuelle Element in der gleichen Ebene noch weitere Elemente?
    if Element.Parent.Count > Index+1 then
      Result := Element.Parent.Items[Index+1];
    // Eine Ebene höher springen
    Element := Element.Parent.Parent;
  end;
end;

function TBrainFuckCompiler.GetPreviousElement(Element: TElement): TElement;
var
  Index: integer;
begin
  Result := nil;
  if Assigned(Element.Parent) then
  begin
    Index := Element.Parent.IndexOf(Element);
    if Index >= 1 then 
    begin
      // Vorgänger in gleicher Ebene
      Result := Element.Parent.Items[Index-1];
      // Von dort aus zum untersten Kind-Element vorarbeiten
      while Result.Children.Count >= 1 do
        Result := Result.Children.Last;
    end
    else 
      // eine Ebene nach oben springen
      Result := Element.Parent.Parent;
  end;
end;

Das Laufzeitverhalten ließe sich sicherlich noch verbessern, indem man IndexOf umgeht (z.B. durch Cachen des Index in den jeweilen Elementen oder durch Verwendung einer verketteten Liste).

[Khabarakh]

Wie gesagt: Das geht in jeder Sprache mit Iteratoren/Generatoren bedeutend einfacher. Zum Beispiel mit meinen vier Zeilen von oben.
Und selbst in Delphi: Wäre es nicht einfacher, den Baum in eine Liste umzuformen (Preorder Traversal), bei der man dann einen Index in/dekrementiert? Verbraucht mehr Speicher als ein Iterator, aber zumindest bei Matzes Beispiel dürfte das keine Rolle spielen :) .