Ich möchte eine generische Hierarchie für Baumstrukturen implementieren, die später in einer implementierungsunabhängigen Weise verwendet werden kann, um generische Algorithmen über Bäume zu beschreiben.
Ich begann mit dieser Hierarchie:
%Vor%Nun möchte ich grundsätzlich das Konzept eines Teilbaums universell umsetzen können: Für jede Klasse T: BinaryTree möchte ich einen 'Klasse' Subtree (T), der die gleiche Funktionalität von T bietet (also davon abgeleitet werden muss) und auch die root () Funktionalität neu schreibt.
In etwa so:
%Vor%Nun bin ich mir bei diesem Code nicht sicher, wie ich ein Objekt vom Typ Unterbaum erstellen soll, da das Baumobjekt in irgendeiner Weise injiziert werden sollte.
Ein Ansatz besteht darin, für jede Baumklasse, die ich erstelle, eine Unterbaumklasse zu erstellen, aber das bedeutet Codeverdoppelung und schließlich das Gleiche.
Also, ein Ansatz dazu sind Mixins, die es einer generischen Klasse erlauben, von ihrem Template-Parameter abzuleiten.
Ich bin auch daran interessiert, wie eine solche Hierarchie in Haskell implementiert werden kann, da Haskell ein großartiges Typsystem hat und ich denke, es wird einfacher sein, solche Funktionalität zu injizieren.
In Haskell könnte es zum Beispiel so aussehen:
%Vor%Ich bin interessiert, ob und wie dies in einer oop-Sprache (c ++, c #, d, java) getan werden kann, da c ++ und d Mixins aus der Box liefern (und ich bin mir nicht sicher für d), und aus Neugierde mit dem Haskell-Typ-System.
Ich denke, der Ansatz durch "BinaryTree" nimmt zu viel von einer festen Struktur an und definiert unnötigerweise Ihre Schnittstelle auf nicht generische Weise. Dies macht es schwierig, Algorithmen wiederzuverwenden, wenn Ihr Baum in nicht-binäre Formen expandiert. Stattdessen müssen Sie Ihre Schnittstellen für mehrere Stile kodieren, wenn dies nicht notwendig oder nützlich ist.
Auch das Codieren mit hasLeft / hasRight-Checks bedeutet, dass jeder Zugriff ein zweistufiger Prozess ist. Das Überprüfen der Existenz einer festen Position wird keine effizienten Algorithmen bereitstellen. Stattdessen denke ich, dass Sie feststellen werden, dass das Hinzufügen einer generischen Eigenschaft, die binär links / rechts oder binär rot / schwarz oder ein Zeichenindex oder irgendetwas anderes sein kann, viel mehr Wiederverwendung Ihrer Algorithmen ermöglicht und überprüft, dass Daten nur durch diese Algorithmen gemacht werden können das braucht es (spezifische binäre Algorithmen).
Aus einer semantischen Sicht möchten Sie zuerst einige grundlegende Eigenschaften codieren und dann spezialisieren. Wenn Sie sich innerhalb eines Algorithmus an einem Knoten befinden, möchten Sie zuerst die untergeordneten Kanten finden können. Dies sollte ein Containerbereich mit Kantenstrukturen sein, mit denen Sie zu den untergeordneten Knoten navigieren können. Da es sich um einen generischen Container handeln kann, könnte er 0, 2, 5, 1 oder sogar 100 Kanten enthalten. Vielen Algorithmen ist das egal. Wenn es 0 ist, wird die Iteration über den Bereich nichts tun - keine Notwendigkeit, hasX oder hasY zu überprüfen. Für jede Kante sollten Sie in der Lage sein, den Knoten des Kindes zu erhalten und für den gewünschten Algorithmus rekursiv zu sein.
Dies ist im Grunde der Ansatz, den Boost in seiner Graph-Bibliothek verwendet, und er ermöglicht die Erweiterung von Baumalgorithmen auf Graphen, wo sie anwendbar sind, für eine noch bessere generische Wiederverwendung von Algorithmen.
Sie haben also bereits eine grundlegende Schnittstelle mit diesem
%Vor%und was auch immer Ihre Lieblingssprache von Objekt zu Objekt ist. D hat zum Beispiel eine besonders nützliche Bereichssyntax.
Sie möchten ein einfaches Tree-Objekt, das Ihnen Knoten liefert. Etwas wie
%Vor%startet Sie.
Wenn Sie nun BinaryTrees unterstützen wollen, tun Sie dies als Einschränkung für diese Schnittstelle. Beachten Sie, dass Sie keine neuen Interface-Methoden benötigen, sondern nur mehr Invarianten erzwingen müssen - dass jeder TreeNode 0, 1 oder 2 ChildEdges hat. Machen Sie einfach einen Schnittstellentyp, der diese semantische Einschränkung anzeigt:
%Vor%Und wenn Sie gerootete Bäume unterstützen möchten, fügen Sie eine Interface-Ebene mit
hinzu %Vor%fügt diese Fähigkeit hinzu.
Die Grundidee ist, dass Sie keine Schnittstellenmethoden hinzufügen müssen, um semantische Anforderungen hinzuzufügen, wenn Sie Ihre Klassen in der Hierarchie spezifischer machen. Fügen Sie nur Schnittstellenmethoden hinzu, wenn ein neues semantisches Verhalten vorliegt, auf das zugegriffen werden muss. Andernfalls - erzwinge neue Invarianten auf der generischen Schnittstelle.
Schließlich sollten Sie Knoten und Kanten mit Strukturen dekorieren, die Daten über den Knoten oder die Kante enthalten, so dass Sie Tries- und Rot-Schwarz-Bäume und all die großartigen Werkzeuge für fortgeschrittene Algorithmik erstellen können. Also wirst du
haben wollen %Vor%Da dies etwas sein soll, an dem generische Algorithmen arbeiten können, sollte die Typinformation, ob eine Eigenschaft ein Teil des Baumes ist oder nicht, generisch sein und etwas, das Algorithmen ignorieren können. Dies bringt Sie auf den Design-Track von Boost, wo diese Probleme sehr elegant gelöst wurden. Ich würde empfehlen, diese Bibliothek zu studieren, wenn Sie Ideen haben wollen, wie man eine generische Baumalgorithmus-Bibliothek erstellt.
Wenn Sie die oben genannten Richtlinien der Typ-Gleichsetzung-zu-Semantik-Beschreibungen befolgen, sollte der SubTree offensichtlich sein - es ist genau der gleiche Typ wie der Baum, aus dem er stammt! Tatsächlich sollten Sie überhaupt keinen SubTree-Typ haben. Stattdessen sollten Sie nur eine Methode des spezifischen TreeNode-Typs verwenden, mit dem Sie arbeiten
%Vor%Und wie bei Boost können Sie, wenn Sie mehr Informationen über die Fähigkeiten von Tree in seinen allgemeinen Eigenschaften codieren, neue Baumtypen mit breiteren Schnittstellenverträgen erhalten.
Da D "echte" Templates hat, keine Generics, ist es trivial, eine Template-Klasse von ihrem Template-Parameter zu übernehmen:
%Vor% Soweit es Subtree in D funktioniert, sollte so etwas funktionieren, vorausgesetzt, Sie haben auch eine Template-Klasse Node :
Allerdings, IIUC (korrigieren Sie mich, wenn ich falsch liege), T ist die Nutzlast des Baumes und könnte daher ein primitiv sein. Wenn das der Fall ist, wäre es besser, wenn Sie Subtree!(T) als T über alias this , das Untertypen ohne Vererbung erlaubt und mit Primitiven arbeitet:
Eine solche Baumschnittstelle in Haskell zu erstellen ist ... ungewöhnlich. Sowohl Node als auch Subtree sind überflüssig. Dies ist teilweise auf algebraische Typen zurückzuführen, und teilweise darauf, dass Haskell-Daten unveränderlich sind, so dass verschiedene Techniken benötigt werden, um bestimmte Dinge zu erreichen (wie das Setzen des Wurzelknotens). Es ist möglich, es zu tun, die Schnittstelle würde ungefähr wie folgt aussehen:
Dann mit einer hübschen Standard-Binärbaumdefinition:
%Vor% Da diese Schnittstelle Maybe (tree a) zurückgibt, können Sie auch left und right verwenden, um zu überprüfen, ob die Zweige vorhanden sind, anstatt separate Methoden zu verwenden.
Es ist nichts besonders falsch daran, aber ich glaube nicht, dass ich jemals jemanden gesehen habe, der diesen Ansatz tatsächlich umgesetzt hat. Die üblicheren Techniken sind entweder das Definieren von Durchquerungen in Foldable und Traversable oder das Erstellen eines Reißverschlusses . Reißverschlüsse lassen sich einfach manuell ableiten, aber es gibt mehrere generische Reißverschlüsse, z. B. Reißverschluss , pez und syz .
In C # 4 würde ich Dynamik verwenden, um dieses Ziel zu erreichen. Zum Beispiel könnten Sie versuchen, die SubtTree-Klasse wie folgt zu definieren:
%Vor%und überschreiben Sie geeignete Methoden von DynamicObject mit Methoden / Eigenschaften von tree. Weitere Informationen (und Beispielcode) finden Sie in diesem tollen Blogbeitrag über Verwenden von C # 4.0 dynamisch, um Ihren privaten Reflektionscode drastisch zu vereinfachen .
Es ist erwähnenswert, dass aufgrund der Verwendung von dynamischen Fähigkeiten und Reflektion ein geringer Leistungsaufwand sowie eine verringerte Sicherheit (da dies eine Verletzung der Kapselung beinhalten kann) eingeführt werden.
Wie Sie bereits erwähnt haben, besteht ein Ansatz darin, für jede erstellte Baumklasse eine Unterbaumklasse zu erstellen. Dies bedeutet Code-Duplizierung, aber es kann irgendwie "vermieden" werden, oder besser, automatisiert, mit Reflexion und T4. Ich habe es selbst für ein vergangenes Projekt getan und es funktioniert ganz gut!
Sie können von Oleg Synch Blog für einen Überblick über T4 starten. Hier ein gutes Beispiel für automatisch generierte Klassen: Ссылка
Sie könnten tun: -
%Vor%Ein Unterbaum ist nur ein Baum, und jeder Baum kann als Wurzelknoten dieses Baumes dargestellt werden und dann kann dieser Knoten Eigenschaften haben, die die Navigation durch den Baum ermöglichen.
Machen Sie dies zu einem generischen Node<T> und speichern Sie den Wert ebenfalls. Wenn Sie öffentliche Setter nicht mögen, machen Sie sie privat und setzen Sie sie nur in einem Konstruktor oder einigen sicheren AddLeft(...) , etc. Methoden.
Sie können auch Root loswerden und einfach die Parent -Links durchlaufen, bis Sie einen Wert von null Parent finden (oder den obersten Knoten für Ihren Teilbaumfall erreichen).