Sortierfunktion für Treestruktur

[Gruber_Hans_12345]

Gibt es ein Sortierfunktion um Elemente mit Parent und Prev schnell und gut zu sortieren?

Jedes Element hat einen eindeutigen ID
einen PrevID, der auf den vorgänger zeigt (0, wenn es das erste Element ist)
einen ParentID, der auf das Eltern Element zeigt (0 wenn es ein root Element ist)

ich bräuchte jetzt eine Funktion, mit der ich eine fix fertige Liste umsortieren kann.
und auch eventuell eine funktion, mit der ich gleich beim laden aus der DB die Liste richtig aufbauen kann (geht das überhaupt ... ? )

bin für vorschläge wo ich suchen kann dankbar

[omata]

Hier mal Beispiele für das Auslesen aus einer DB:
MsSQL,
MySQL

Eine Sortierfunktion für den Treeview könnte so aussehen...

Delphi-Quellcode:

procedure TForm.TreeViewCompare(Sender: TObject; Node1, Node2: TTreeNode;
  Data: Integer; var Compare: Integer);
begin
  if Node1.Text < Node2.Text then
    Compare:=1
  else if Node1.Text > Node2.Text then
    Compare:=-1
  else
    Compare:=0;
end;

Über Compare kann man festlegen, wie sortiert wird.
Das überhaupt sorttiert wird kann man mit TreeView.SortType festlegen.



Gruss
Thorsten

[Gruber_Hans_12345]

danke mal für die zwei tipps

allerdings brauche ich für meine Anwendung einen anderen Ansatz

Delphi-Quellcode:

type
  TItem = class
    fID : integer;
    fParentID : integer;
    fPrevID : integer;
  end;

  TItemList = class(TList)
  end;

TItemList enthält einige Objekte vom Typ TItem, und jetzt muß ich diese sortieren, bisher habe ich eine absolute quick and dirty funktion dafür, die zwar sehr schnell beim hinschreiben war, aber so häßlich ist, das ich die nicht verwenden möchte und auch hier nicht herschreiben will

[ibp]

schematisch, rekursiver ansatz

Delphi-Quellcode:

procedure loadtree(anode:ttreenode; pkey:tkey);
var
  treenode:ttreenode;
  itemnode:TItem;
begin
  sql.create;
  sql='select fID, fParentID, fPrevID, titel from bla where fParentID='+pkey+' order by 
fID';  
  while sql<>nil do
  begin
    itemnode.create;
    itemnode:=.... // hier dein nodeinfos aus der db speichern

    treeNode:=Treeview.Items.AddChildObject(aNode,titel,itemnode); 

    // kinder laden vom aktuellen knoten
    loadtree(treeNode, itemnode.fID);

    sql.next;
  end;
  sql.free;
end;

[edit=SirThornberry]Code-Tags durch Delphitags ersetzt - Mfg, SirThornberry[/edit]

[Gruber_Hans_12345]

hmmm, aber da habe ich keine sortierung dabei (achtung, ich muß mit PrevID sortieren, und habe somit keine möglichkeit die sortierung dem SQL Server zu überlasssen, und muß daher immer im nachhinein manuell sortieren)
und ich möchte auch gerne alle Daten auf einmal in einer einzigen SQL Query abfragen, und nicht für jeden Zweig eine neue SQL Anweisung machen

meine SQL Anweisung fürs laden :

Delphi-Quellcode:

   R.CheckSQL(sql, doClose);
   sql.SQL.Text   := 'SELECT ID, PARENTID, PREVID FROM TEILE WHERE AUFTRAG = :ID ORDER BY PARENTID, PREVID';
   sql.ParamByName('ID').AsInteger   := AuftragID;
   sql.Open;
   while not sql.Eof do
      AddItem.LoadFromSQL(sql, TRUE);
   if doClose then R.CloseSQL(sql);

also, das ist etwas grob vereinfacht die Sortierfunktion, wie ich die jetzt verwende ...
(ich glaub, man sieht gleich warum ich da eine andere haben möchte )

Delphi-Quellcode:

   procedure InserItems(item : TItem; listNew : TList);
   var
      i      : integer;
   begin
      // in neue Liste einfügen, und aus alter löschen
      listNew.Add(item);
      Remove(item);
      
      // erstes Child Element suchen
      for i:=0 to Count-1 do 
         if (Item[i].ParentID = itemID) and (Item[i].PrevID = 0) then begin
            InsertItems(Item[i], listNew);
            break;
         end;
      
      // Nächstes Element suchen
      for i:=0 to Count-1 do 
         if (Item[i].PrevID = itemID) then begin
            InsertItems(Item[i], listNew);
            break;
         end;
   end;
   
   listNew   := TList.Create;
   InsertItems(listNew[0], listNew);   
   Assign(listNew);
   listNew.Free;

[omata]

Hallo Hans,

da du die PrevID auch speichern willst wirst du das wohl nicht direkt aus der DB auslesen können.

Hier mal mein Vorschlag...

Delphi-Quellcode:

type
  TItem = class
    fID : integer;
    fParentID : integer;
    fPrevID : integer;
  end;

  TItemList = class(TList)
  public
    procedure TreeSort;
  end;

:
:

procedure loadFromDB
var SDS:TSimpleDataSet;
    Item:TItem;
begin
  SDS:=TSimpleDataSet.Create(Self);
  try
    SDS.Connection:=...
    SDS.DataSet.CommandText:=
      'SELECT id, parentid, previd'#13 +
      'FROM treetable'#13 +
      'ORDER BY parentid, previd';

    SDS.Open;
    while not SDS.Eof do begin
      Item:=TItem.Create;
      Item.fID:=SDS.FieldByName('id').AsInteger;
      Item.fParentID:=SDS.FieldByName('parentid').AsInteger;
      Item.fPrevID:=SDS.FieldByName('previd').AsInteger;
      ItemList.Add(Item);
      SDS.Next;
    end;
    SDS.Close;
    ItemList.TreeSort;
  finally
    SDS.free;
  end;
end;

function CompareNames(Item1, Item2: Pointer): Integer;
var ItemA, ItemB:TItem;
begin
  ItemA:=TItem(Item1);
  ItemB:=TItem(Item2);
  if ItemA.fParentID > ItemB.fParentID then
    Result:=1
  else if ItemA.fParentID < ItemB.fParentID then
    Result:=-1
  else begin
    if ItemA.fID > ItemB.fID then
      Result:=1
    else if ItemA.fID < ItemB.fID then
      Result:=-1
    else
      Result:=0;
  end;
end;

procedure TItemList.TreeSort;
begin
  Self.Sort(@CompareNames);
end;

Edit: Mir fällt gerade auf, dass ich leider nicht verstehe was du eigentlich willst. Für mich ist deine Beschreibung leider nicht eindeutig genug. Was ist den die PrevID? Ich dachte das wäre die ID von dem Node vor dem aktuellen Node. Nur warum steht der in der DB? Ist das nicht redundant? Wie wäre es mit ID, ParentID, Reihenfolge..., ich bin verwirrt. Vielleicht hilft dir ja mein Beispiel trotzdem irgendwie weiter.

Gruss
Thorsten

[marabu]

Guten Morgen Hans,

natürlich kann man Baumstrukturen sortieren - keine Frage. Dazu müssen aber Sortierkriterien her und PREV_ID gefällt mir da gar nicht, da Schlüsselwerte in der Regel nie für eine Sortierung geeignet sind. Das liegt daran, dass Schlüssel informationsfrei sein sollen. Nicht einmal deren Erzeugungsreihenfolge, welche sich oft im Schlüsselwert speigelt, darf auf fachlicher Ebene herangezogen werden.

Eigentlich musst du nur tiefer schauen: Wenn die Verkettung deiner Daten über PREV_ID vom Benutzer nicht willkürlich vorgenommen wird, sondern erst nach Betrachtung eines bestimmten Feldwertes, dann hast du dein Kriterium. Und ist es doch ein Willkürakt, dann kannst du den Wunsch des Benutzers einfach in einem zusätzlichen Steuerfeld SEQ mitführen. In einer relationalen Datenbank werden Datensätze nicht verkettet um eine Ordnung herzustellen. Das macht man ausnahmslos über die ORDER BY Klausel.

Um deine hierarchischen Daten nach den Regeln der Kunst zu speichern, kannst du spezielle Tabellen (Stichwort [dp]selbstrekursiv*[/dp]) verwenden. Ich habe vor längerer Zeit einmal etwas zu diesem Thema geschrieben, was damals wohl nicht so hilfreich war. Vielleicht hilft es dir: klick

Schönes Wochenende

[Gruber_Hans_12345]

hi

so, versuche es noch einmal zu klären ...

ich habe hier einen Tree, den der User aufbaut, dieser Tree kann bis zu einigen tausend Einträge enthalten.
Die Schlüsselwerte jedes Eintrags sind :
ID ... der eindeutige Index des Eintrages
ParentID ... der ID des Elternelementes
PrevID ... der ID des Vorgänger

ich speichere deshalb PrevID und keine Reihenfolge, da ich wenn der User zB. den letzten Eintrag im Tree ganz nach oben schiebt, oder einfach ganz oben einen neuen Eintrag hinzufügt) ich maximal 2 SQL UPDATES machen muß (diese Elemente müssen dann auch auf andere PC geschickt werden, damit diese sich diese zwei Elemente synchronisieren können)


Das das ganze damit schwierig wird zum sortieren ist mir schon klar, aber den nachteil, das sich bei jeder kleinen Änderung immer alle Elemente in dem Zweig neu speichern muß ist mir zu groß

@omata: mit einer einfachen CustomSort Funktion wird es wohl nicht gehen, da ID ja die Reihenfolge Beschreibt, wie die Elemente angelegt worden sind und nicht die Reihenfolge wie der User diese verschoben hat.
Aber ja, prevID ist die ID vom Vorgänger, das stimmt, ist aber nicht redundant, die diese ja sonst nirgends gespeichert ist, die Reihenfolge von ID wäre nur dann richtig, wenn der User immer nur am schluß neue Elemente anfügt, und nicht in der mitte oder am anfang oder gar per drag und Drop elemente verschiebt.

[ibp]

dann bekommst du aber nie die verschobene reihenfolge wieder hin oder verstehe ich da was falsch?

also ich bervorzuge ebenfalls marabus rekursiven ansatz, siehe oben. bei einer meiner anwendungen ist das so realisiert und ebenfalls natürlich ein sort-feld. klar man muss dann eben wenn die sortierung beibehalten werden soll dieses auch in der db nachführen.
weiterhin kann man beim rekursiven ansatz ja cuh noch eine tiefe mitgeben, das hat den vorteil, beim baumöffnen wird dann immer nur die jeweilige nächste ebene geladen. das macht natürlich nur dann sinn, wenn der user nicht den ganzen baum braucht.