Speichern von Baumstrukturen

[Chewie]

Ich bin gerade am Überlegen, wie ich am besten eine Baumstruktur(Verzeichnisstruktur mit ein paar anderen Daten) speichern soll. Eine rekursive XML-Speicherung ist zwar recht angenehm zu proggen, aber frisst mir zuviel Speicherplatz.
Deshalb ist es wohl das beste, die Daten als Records in einer typisierten Datei zu speichern. Jedoch fehlt mir noch etwas die Idee, wie ich das am besten anstelle, sprich, wie die Daten da am schnellsten rein- und rauskommen.

Hat einer einen Tipp oder eine Idee?

[negaH]

Wenn du nur mit Records arbeiten willst, also jeder Record gleiche Größe, ist es am sinnvollsten den Level der Node in den Record aufzunehmen. Der Level ist die Anzahl der übergeordneten Parent Nodes bis zur Root. Durch deine Iterierfunktion für den Baum, kannste dann den Level ziemlich einfach mitführen.

Beim Laden eines solchen Baumes ist der erste Record ja die Root mit Level = 0. Beim Laden des nächsten Records kannste dessen Level mit dem aktuellen Level überprüfen. Ist er +1 größer als der aktuelle Level bedeutet dies das es eine Childnode zur aktuell geladenen Node sein muß. Ist der Level = dem aktuellen Level so ist es ein paralell liegende Node. Sollte der Level keliner als der aktuelle Level sein so musst du ausgehende von der aktellen Node einfach aktueller Level - Level Schritt im Baum nach oben gehen.

Gruß Hagen

[Chewie]

Danke, ich werd mir den Vorschlag mal durch den Kopf gehen lassen.
Es ist zwar möglich, dass ich zwei verschiedene Recordtypen brauche, aber das kann ich entweder durch Unions lösen oder dadurch, dass ich am Anfang die Größe des Records reinschreibe.

[negaH]

Obiger Vorschlag setzt vorraus das deine Baumstruktur in jeder Node die Parentnode speichert, also die Node in der die Node selber eingelinkt ist. Dies ist aber auch allgm. üblich.

Gruß Hagen

[Chewie]

So, ich bin jetzt zu dem Schluss gekommen, dass es eigentlich keine Rolle spielt, in welcher Reihenfolge die Records in die Datei geschrieben werden. Denn egal wie ich sie reinschreibe, auslesen kann ich sie sowieso nur von vorne bis nach hinten, da jedes Element unterschiedlich groß sein kann. Und wegen der Geschwindigkeit ist das auch schnuppe, die Datei muss ja schließlich sowieso ganz gelesen werden.

Jetzt habe ich mich entschieden, die Speicherung der Baumstruktur in eine eigene Klasse zu verlegen, die dann völlig unabhängig von der Klasse sein soll, in der ich die Daten eigentlich speichern muss. Also keine Methode SaveToFile() in der dann die einzelnen Items gespeichert werden.
Die Klasse soll universell verwendbar sein, da es ja immer mal wieder vorkommen kann, dass man eine Baumstruktur speichern muss.
Deshalb hab ich mir folgendes überlegt:

Ich bastele mir eine abstrakte Klasse, die die Methoden enthält, um auf Parent- und Child-Nodes sowie die zu speichernden Daten zuzugreifen. Das hab ich mir etwa so gedacht:

Delphi-Quellcode:

TTFNode = class
  private
    function GetData: TTFDataStruc; virtual; abstract;
    function GetChildren: TTFNodes; virtual; abstract;
    function GetParent; TTFNode; virtual; abstract;
  end;

TTFDataStruc sieht dabei so aus:

Delphi-Quellcode:

TTFDataStruc = packed record
    PData: Pointer;
    Size: Word;
  end;

Man kann also beliebige Daten speichern (65kb sollten genügen).

Eine Klasse, von der jetzt eine Baumstruktur gespeichert werden soll, müsste nun von TTFNode abgleitet sein und die abstrakten Methoden ersetzen. Nun übergebe ich einen Zeiger auf dieses Objekt an eine SaveToFile-Methode von meiner TTreeFile-Klasse (die Klasse, die die Verwaltung der Datei übernimmt) und es kann losgehen.
Soweit so gut.
Allerdings habe ich die ganze Zeit das Gefühl, als würde ich es mir unnötig schwer machen und es eine viel leichtere und vor allem flexiblere Lösung gibt, aber ich komm nicht drauf.
Wenn es keine geben sollte, dann macht das auch nichts, dann betrachtet diesen Post als Liebesbekundung an abstrakte Methoden.

[negaH]

Hi,

Da ich selber schon so was gecodet habe will ich dir erklären wie ich es gemacht habe.
Die Grundbedingungen waren exakt die gleichen wie bei dir
- Node Klassen die für eigene Daten abgeleitet werden
- Node Klassen durften nicht von TComponent aber von TPersistent abgeleitet werden
- Nodes sollten sich per Delphi TComponent Streamingsystem speichern

Besonders der letzte Punkt war enorm wichtig, da ich wollte das man keienrlei explizite Sources programmieren sollte um published Properties zu speichern doer zu laden. Denoch sollte man über DefineProperties() eigene Speicher/Lade Methoden wie bei TComponent gewohnt programmieren können.

Somit sieht es verkürzt so aus:

Delphi-Quellcode:

type
  TNode = class(TPersistent)
  private
    FParent: TNode;
    FChilds: TList;
    FText: String;
    function GetCount: Integer; // FChilds.Count
    function GetChildren(Index: Integer): TNode; // FChilds[Index] 
  protected
    procedure AssignTo(Source: TPersistent); override;
  public
    function ForEach(Callback: TNodeForeachFunc; Reverse: Boolean): TNode; 
    function Attach(Index: Integer; Node: TNode; Absolute: Boolean): TNode;    
    procedure SaveToStream(Stream: TStream); virtual;
    class function LoadFromStream(Node: TNode; Stream: TStream): TNode; virtual;
    property Count: Integer read GetCount;
    property Children[Index: Integer]: TNode read GetChildren; default;
    property Parent: TNode read FParent write SetParent;
    property Index: Integer read GetIndex;
  published
    property Text: String read FText write SetText;
  end;

  TMyTestNode = class(TNode)
  private
    FData: String;
    FValue: Integer;
    FMemory: TMemoryStream;
  protected
    procedure DefineProerties(Filer: TFiler); override;
  public
    property Memory: TMemoryStream read FMemory;
  published
    property Data: String read FData write FData;
    property Value: Integer read FValue write FValue default 12;
  end;

Eine TNode sieht also abstrahiert so wie oben aus.
Wichtig war mir das eben das Delphi Streaming System dafür benutzt wurde um
- eigene Properties mit DefineProperty/DefineBinaryPropery zu ermöglichen. In TMyTestNode würde die benutzt werden um FMemory zu speichern
- alle published Properties ohne zusätzlichen Code in Streams zu speichern, eben Delphi like.
- .Assign() und .AssignTo() benutzt werden um per temp. Streams und Delphis Streaming Nodes zuweisbar zu machen. D.h. Assign() und Assignto() von TNode wurden so implementiert das sie über .SaveToStream() und .LoadToStream() Nodes sich zu weisen. Dadurch muß bei Nachfahren von Tnode niemals mehr irgendwelche .Assign() Methoden überschrieben werden um eigene TNode Felder zuzuweisen. All das wird implizit durch .Assign()/.Assignto() über .SaveToStream()/.LoadFromStream() erledigt.
- trotzdem sollten die Nodes von Tpersistent abgeleitet sein, die im Delphi Streaming System NICHT ohne TComponent Kontainer benutzt werden können. Genau darin bestand die Schwierigkeit, denn TPersistent's können nur gespeuchert werden wenn sie als publishded Property einer TComponent benutzt werden. Ich erfand dann die Lösung indem TNode.SaveToStream() eine versteckte TNodeComponent helper Klasse benutzte. D.h. zu jeder Node im Baum wird temporär eine TNodeComponent erzeugt die eine published Property benutzte die die eigentlich TNode enthält. Somit konnt man auf die Vorzüge des Delphi Streamingssystems aufbauen. Eine Grundbedingung dabei war natürlich das meine TNodes schon in Delphi 1 bis heute in Delphi 7 ohne Änderungen funktionieren sollten, und auch tue'n.

Gruß hagen

[Chewie]

Hm, Streaming von Komponenten ist absolutes Neuland für mich, aber wenn ich damit ohne zusätzllichen Code Properties abspeichern und wieder laden kann und ich sogar auswählen kann, welche, dann klingt das gut genug, um mich mal damit zu beschäftigen.
Allerdings ginge dann der Vorzug drauf, die Klasse auch in nonVCL-Projekten verwenden zu können (Klar, verwenden kann ich sie schon, aber das wäre kontraproduktiv).

[negaH]

Dies musst du entscheiden. Grundsätzlich würde nur das Delphi Streaming System benutzt, also nur die wichtigsten Teile aus Classes.pas. Man könnte es auch selber coden, mit hilfe von TypInfo.pas, und hätte somit einen erhöhten Overhead der Speichrung von Daten. Auf alle Fälle, ob mit oder ohne VCL, ist dieser Weg viel effizienter als die XML-Nodes (die absoluter Shit sind).
Bedenke auch das der Weg über die VCL, wesentlich größerer Streams erzeugt. D.h. solche Nodes im VCL like Stream benötigen mehr Speicher, da sie ja auch den Property Typ + Name + Wert speichern.
Allerdings, gerade bei komplexeren Datenstrukturen haben sich diese Nodes enorm bewährt. Nur an Hand deren Deklaration können sie in Streams gespeichert werden. Dies ist dann auch noch Typ und Werte sicher. Neue "Versionen" der gleichen Nodes, durch Erweiterungen mit neuen Eigenschaften machen schon gespeicherte Nodes nicht inkompatibel. D.h. es ist während der Entwicklungszeit der Nodes immer möglich sie zu erweitern (so lange man keine einmal deklarierten Properties löscht).

Der Weg über feste TNodes die per Zeiger ihre Daten enthalten ist unelegant und inflexibel. Besser ist es dann gleich die TNode als Nachfahre als erweiterbares Datenobject zu betrachten.

Ich will noch erwähnen das zu meinen TNodes noch Controls existieren die z.B. den TTreeView ersetzen. Da jedes Delphi TObject auch Messages als dynamische Methoden empfangen kann, habe ich meine TNodes damit erweitert. Dies bedeutet das ein Nodebaum der einen TNodeGrid zugewiesen wurde, selber für dessen Darstellung, Bedienung und Datenhaltung verantwortlich ist. Durch üebrschreiben verschiedener Messages in den eigenen TNodes kann man also deren Darstellung und Ineraktion im GUI Control bestimmen.

Auf www.dinosGmbh.de findest du ein paar ScreenShots meiner kommerziellen Programme die fast alle TNodes benutzen.

Gruß Hagen

[Chewie]

Hm, die Erweiterbarkeit der Node-Daten kann ich auch dadurch gewährleisten, dass jeder Datenrecord einen gemeinsamen Header enthält, der u.a. Versionsnummer und Größe, daneben natürlich noch Parentnode und Verschachtelungsebene, beinhaltet. Je nach Version sind die Records dann unterschiedlich aufgebaut.
Also mit anderen Worten: Ich glaub zwar schon, dass das mit dem Streaming-System schön komfortabel und flexibel funktioniert, aber da es für mich totales Neuland ist und ich trotz deiner ausführlichen Erklärungen (Danke!) nicht so wirklich den Vorteil sehen kann, versuch ich es lieber mit meiner Variante.
Aber das Komponenten-Streaming-System werd ich mir dennoch mal zu Gemüte führen!

[Chewie]

Ich hab in den letzten paar Wochen nur wenig dran gemacht, aber jetzt hab ich ein Problem, das sehr seltsam ist.

Ich speichere die Daten jetzt typisiert, ich hab zwar noch nicht überprüft, ob die richtigen Daten in der richtigen Reihenfolge gespeichert werden, aber ich prüfe, ob Größe der Datei = Anzahl der gefundenen Dateien * Größe des Records. Das klappt, da (noch) die Datengröße statisch ist.
Jetzt passiert etwas Merkwürdiges: Wenn ich den Algo testweise auf ein kleines Verzeichnis (rund 100 Dateien und Ordner) anwende, ist die Datei so groß wie erwartet. Wende ich ihn jedoch auf größere Verzeichnisse an, ist die Datei größer als erwartet, es wurden also mehr Daten von Dateien eingetragen, als Dateien da sind . Findet jemand den Fehler?

Die Dateien werden so eingelesen:

Delphi-Quellcode:

function TFiles.ReadFiles(Volume: String): Integer;
begin
  //Variablen vorbereiten
  FFileList := nil;
  SetLength(FFileList, flInitialLength);
  FFileListHighPos := -1;
  FRootNode.Free;
  FRootNode := TFileNode.Create;

  //Suchvorgang starten
  Result := RecurseProc(Volume, nil);
end;

Wobei RecurseProc so aussieht:

Delphi-Quellcode:

function TFiles.RecurseProc(Path: String; Node: TFileNode): Integer;
var
  SearchRec: TSearchRec;
  noFile: Boolean;
const
  Mask = '*.*';  //die zur Dateisuche verwendete Maske (*.* für alle Dateien)
begin
  Result := 0;

  //sicherstellen, dass Pfad mit Backlash endet
  if (Path[Length(Path)] <> '\') and (Path[Length(Path)] <> '/') then
    Path := Path + '\';

  if Node = nil then Node := FRootNode;  //Standard-Rootnode setzen

  if FindFirst(Path + Mask, faAnyFile, SearchRec) <> 0 then Exit;

  //Suchschleife läuft als Endlosschleife, da vor UND nach Abbruchbedingung Code
  //ausgeführt werden muss
  while True do
  begin
    //prüfen auf Self- und Parent-Referenz
    if (SearchRec.Name <> '.') and (SearchRec.Name <> '..') then
      noFile := False
    else
      noFile := True;

    if not noFile then
    begin
      //falls Ordner gefunden wurde:
      //- Zeiger auf erste ChildNode erstellen
      //- weiter mit Dateien in diesem Ordner
      if SearchRec.Attr and faDirectory = faDirectory then
      begin
        Node.FFirstChild := TFileNode.Create;
        Result := Result + RecurseProc(Path + SearchRec.Name, Node.FFirstChild);
      end;

      //Datenrecord über Dateieintrag füllen
      Node.FData.FullPath := Path + SearchRec.Name;
      Node.FData.AbsIndex := FFileListHighPos + 1;
      Node.FData.Size := SearchRec.Size;

      //sicherstellen, dass das Array groß genug ist
      EnsureListSize;

      //Eintrag in Array eintragen
      Inc(FFileListHighPos);
      FFileList[FFileListHighPos] := Node;

      Inc(Result);
    end;

    //nächstes Element suchen und prüfen auf Abbruchbedingung
    if FindNext(SearchRec) <> 0 then Break;

    if not noFile then
    begin
      //nur wenn ein nächstes Element vorhanden ist wird der Zeiger auf das nächste
      //Element gesetzt
      Node.FNext := TFileNode.Create;
      Node := Node.FNext;
    end;
  end;
  FindClose(SearchRec);
end;

Die Dateien werden so gespeichert:

Delphi-Quellcode:

class procedure TTreeFile.SaveToFile(RootNode: TTFNode; Filename: String);
var
  FilePos: Integer;
  
  procedure AddToStream(TFStream: TFileStream; Level: Word; TFNode: TTFNode);
  var
    Size: Word;
  begin
    //1. Schritt: Speichern der RootNode
    Size := TFNode.GetData.Size;
    TFStream.Position := FilePos;
    TFStream.Write(Level, 2);
    TFStream.Write(Size, 2);
    TFStream.Write(TFNode.GetData.PData^, Size);
    FilePos := TFStream.Position;

    //2. Schritt: evtl. Aufruf mit dem ersten Kind
    if TFNode.HasChildren then
    begin
      AddToStream(TFStream, Level + 1, TFNode.GetFirstChild);
    end;

    //3. Schritt: evtl. Aufruf mit dem nächsten Bruder
    if TFNode.HasBrethren then
    begin
      AddToStream(TFStream, Level, TFNode.GetNext);
    end;
  end; 

var
  TFStream: TFileStream;
begin
  TFStream := TFileStream.Create(Filename, fmCreate or fmShareDenyNone);
  try
    FilePos := 0;
    AddToStream(TFStream, 0, RootNode);
  finally
    TFStream.Free;
  end;
end;

Wär super, wenn mir jemand helfen könnte, da ich in dem Code keinen Fehler mehr entdecke (Speziell die Save-Prozedur ist interessant, denn die ReadFiles-Methode scheint soweit richtig zu sein.