[!] Interface-orientierte LinkedLists für PB 4.0

Fragen und Bugreports zur PureBasic 4.0-Beta.
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8809
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

[!] Interface-orientierte LinkedLists für PB 4.0

Beitrag von NicTheQuick »

Mit Kommentaren und Beispiel am Ende. Es werden alle Befehle
unterstützt, die auch von den nativen LinkedLists unterstützt werden.
Das Handling ist nur ein kleines bisschen komplizierter, aber dennoch
leicht verständlich.

Praktisch zum Bau von TreeLinkedLists oder ähnlichem. Vielleicht bastel
ich ja auch noch ein Interface für TreeLinkedLists. Das hier hat ja auch
nur knapp 4 Stunden gebraucht.

Code: Alles auswählen

Structure ntqLLE_Struc
  *NextElement.ntqLLE_Struc
  *PrevElement.ntqLLE_Struc
  ;Data
EndStructure

Structure ntqLL_Struc
  VTable.l
  
  *ActElement.ntqLLE_Struc
  *FirstElement.ntqLLE_Struc
  *LastElement.ntqLLE_Struc
  Count.l
  Act.l
  Size.l
EndStructure

Interface ntqLL
  Kill()
  
  AddElement()
  InsertElement()
  DeleteElement()
  
  FirstElement()
  LastElement()
  IsNext()
  NextElement()
  IsPrevious()
  PreviousElement()
  
  ListIndex()
  CountList()
  ChangeElement(*Element)
  SelectElement(Element.l)
  SwapElements(*Element1.ntqLLE_Struc, *Element2.ntqLLE_Struc)
  
  GetPointer()
  ResetList()
  ClearList()
EndInterface

;Löscht die Liste aus dem Speicher
Procedure ntqLL_Kill(*LL.ntqLL_Struc)
  Protected *t
  If *LL\FirstElement
    *t = *LL\FirstElement
    Repeat
      *LL\ActElement = *t
      *t = *LL\ActElement\NextElement
      FreeMemory(*LL\ActElement)
    Until *t = 0
    FreeMemory(*LL)
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

;Wenn Liste leer, wird ein neues Element erstellt
;Wenn kein aktuelles Element, wird ein neues Element am Ende eingefügt
;Wenn aktuelles Element..
;   ..das letzte ist, wird ein neues Element am Ende eingefügt
;   ..mittendrin ist, wird ein neues Element nach dem aktuellen eingefügt
Procedure ntqLL_AddElement(*LL.ntqLL_Struc)
  Protected *LLE.ntqLLE_Struc
  
  *LLE = AllocateMemory(SizeOf(ntqLLE_Struc) + *LL\Size)
  If *LLE = 0 : ProcedureReturn #False : EndIf
  
  If *LL\Count = 0 ; Liste leer
    *LL\FirstElement = *LLE
    *LL\LastElement = *LLE
    *LL\Count = 1
    *LL\Act = 1
  ElseIf *LL\ActElement = 0 ; kein aktuelles Element
    *LL\LastElement\NextElement = *LLE
    *LLE\PrevElement = *LL\LastElement
    *LL\LastElement = *LLE
    *LL\Count + 1
    *LL\Act = *LL\Count
  ElseIf *LL\ActElement\NextElement = 0 ; Wenn aktuelles Element das letzte ist
    *LL\ActElement\NextElement = *LLE
    *LLE\PrevElement = *LL\ActElement
    *LL\LastElement = *LLE
    *LL\Count + 1
    *LL\Act = *LL\Count
  Else ; Wenn aktuelles Element mittendrin ist
    *LLE\NextElement = *LL\ActElement\NextElement
    *LLE\PrevElement = *LL\ActElement
    *LL\ActElement\NextElement\PrevElement = *LLE
    *LL\ActElement\NextElement = *LLE
    *LL\Count + 1
    If *LL\Act > -1 : *LL\Act + 1 : EndIf
  EndIf
  
  *LL\ActElement = *LLE
  ProcedureReturn *LLE + SizeOf(ntqLLE_Struc)
EndProcedure
;Wenn Liste leer, wird ein neues Element erstellt
;Wenn kein aktuelles Element, wird ein neues Element am Anfang eingefügt
;Wenn aktuelles Element..
;   ..das erste ist, wird ein neues Element am Anfang eingefügt
;   ..mittendrin ist, wird ein neues Element vor dem aktuellen eingefügt
Procedure ntqLL_InsertElement(*LL.ntqLL_Struc)
  Protected *LLE.ntqLLE_Struc
  
  *LLE = AllocateMemory(SizeOf(ntqLLE_Struc) + *LL\Size)
  If *LLE = 0 : ProcedureReturn #False : EndIf
  
  If *LL\Count = 0 ; Liste leer
    *LL\FirstElement = *LLE
    *LL\LastElement = *LLE
    *LL\Count = 1
    *LL\Act = 1
  ElseIf *LL\ActElement = 0 ; kein aktuelles Element
    *LL\FirstElement\PrevElement = *LLE
    *LLE\NextElement = *LL\FirstElement
    *LL\FirstElement = *LLE
    *LL\Count + 1
    *LL\Act = *LL\Count
  ElseIf *LL\ActElement\PrevElement = 0 ; Wenn aktuelles Element das erste ist
    *LL\FirstElement\PrevElement = *LLE
    *LLE\NextElement = *LL\FirstElement
    *LL\FirstElement = *LLE
    *LL\Count + 1
    *LL\Act = *LL\Count
  Else ; Wenn aktuelles Element mittendrin ist
    *LLE\NextElement = *LL\ActElement
    *LLE\PrevElement = *LL\ActElement\PrevElement
    *LL\ActElement\PrevElement\NextElement = *LLE
    *LL\ActElement\PrevElement = *LLE
    *LL\Count + 1
  EndIf
  
  *LL\ActElement = *LLE
  ProcedureReturn *LLE + SizeOf(ntqLLE_Struc)
EndProcedure
;Wenn aktuelles Element gelöscht wird..
;   ..und es das erste und letzte war, ist kein Element mehr aktuell
;   ..und es das erste war, ist das nächste Element das aktuelle
;   ..und es das letzte war, ist das vorherige Element das aktuelle
;   ..und es mittendrin war, ist das nächste Element das aktuelle
Procedure ntqLL_DeleteElement(*LL.ntqLL_Struc)
  If *LL\ActElement = 0 ; kein aktuelles Element
    ProcedureReturn #False
  ElseIf *LL\Count = 1 ; erstes und letztes Element
    FreeMemory(*LL\ActElement)
    *LL\Act = 0
    *LL\FirstElement = 0
    *LL\LastElement = 0
    *LL\ActElement = 0
  ElseIf *LL\ActElement\PrevElement = 0 ; erstes Element
    *LL\FirstElement = *LL\ActElement\NextElement
    *LL\FirstElement\PrevElement = 0
    FreeMemory(*LL\ActElement)
    *LL\ActElement = *LL\FirstElement
    *LL\Act = 1
  ElseIf *LL\ActElement\NextElement = 0 ; letztes Element
    *LL\LastElement = *LL\ActElement\PrevElement
    *LL\LastElement\NextElement = 0
    FreeMemory(*LL\ActElement)
    *LL\ActElement = *LL\LastElement
    *LL\Act = *LL\Count - 1
  Else
    *LL\ActElement\PrevElement\NextElement = *LL\ActElement\NextElement
    *LL\ActElement\NextElement\PrevElement = *LL\ActElement\PrevElement
    FreeMemory(*LL\ActElement)
  EndIf
  
  *LL\Count - 1
  ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
EndProcedure

;Wechselt zum ersten Element in der Liste
Procedure ntqLL_FirstElement(*LL.ntqLL_Struc)
  *LL\Act = 1
  *LL\ActElement = *LL\FirstElement
  ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
EndProcedure
;Wechselt zum letzten Element in der Liste
Procedure ntqLL_LastElement(*LL.ntqLL_Struc)
  *LL\Act = *LL\Count
  *LL\ActElement = *LL\LastELement
  ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
EndProcedure
;Gibt den Pointer zum nächsten Element oder Null, wenn keins existiert
Procedure ntqLL_IsNext(*LL.ntqLL_Struc)
  If *LL\ActElement
    If *LL\ActElement\NextElement
      ProcedureReturn *LL\ActElement\NextElement + SizeOf(ntqLLE_Struc)
    EndIf
  Else
    ProcedureReturn *LL\FirstElement
  EndIf
  ProcedureReturn 0
EndProcedure
;Gibt den Pointer zum vorhergehenden Element oder Null, wenn keins existiert
Procedure ntqLL_IsPrevious(*LL.ntqLL_Struc)
  If *LL\ActElement
    If *LL\ActElement\PrevElement
      ProcedureReturn *LL\ActElement\PrevElement + SizeOf(ntqLLE_Struc)
    EndIf
  EndIf
  ProcedureReturn 0
EndProcedure
;Wechselt zum nächsten Element, falls eins existiert
Procedure ntqLL_NextElement(*LL.ntqLL_Struc)
  If *LL\ActElement = 0
    *LL\ActElement = *LL\FirstElement
    *LL\Act = 1
  ElseIf *LL\ActElement\NextElement
    *LL\ActElement = *LL\ActElement\NextElement
    If *LL\Act <> -1 : *LL\Act + 1 : EndIf
  EndIf
  
  ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
EndProcedure
;Wechselt zum vorhergehenden Element
Procedure ntqLL_PreviousElement(*LL.ntqLL_Struc)
  If *LL\ActElement = 0
    *LL\ActElement = 0
    *LL\Act = 0
  ElseIf *LL\ActElement\PrevElement
    *LL\ActElement = *LL\ActElement\PrevElement
    If *LL\Act <> -1 : *LL\Act - 1 : EndIf
  EndIf
  
  ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
EndProcedure

;Gibt die Position in der Liste zurück
Procedure ntqLL_ListIndex(*LL.ntqLL_Struc)
  Protected *t.ntqLLE_Struc
  If *LL\Act = -1
    *LL\Act = 1
    *t = *LL\FirstElement
    While *t <> *LL\ActElement
      *t = *t\NextElement
      *LL\Act + 1
    Wend
  EndIf
  ProcedureReturn *LL\Act
EndProcedure
;Gibt die Anzahl der Element in der Liste zurück
Procedure ntqLL_CountList(*LL.ntqLL_Struc)
  ProcedureReturn *LL\Count
EndProcedure
;Ändert das aktuelle Element per Pointer
Procedure ntqLL_ChangeElement(*LL.ntqLL_Struc, *Element)
  If *Element
    *LL\ActElement = *Element - SizeOf(ntqLLE_Struc)
    *LL\Act = -1
    ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
  EndIf
EndProcedure
;Ändert das aktuelle Element per Index
Procedure ntqLL_SelectElement(*LL.ntqLL_Struc, Element.l)
  If Element = 0
    *LL\ActElement = 0
    *LL\Act = 0
    ProcedureReturn 0
  ElseIf Element <= *LL\Count And Element > 0
    *LL\ActElement = *LL\FirstElement
    *LL\Act = 1
    While *LL\Act < Element
      *LL\ActElement = *LL\ActElement\NextElement
      *LL\Act + 1
    Wend
    ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
  EndIf
EndProcedure
;Tauscht zwei durch Pointer gegebene Elemente
Procedure ntqLL_SwapElements(*LL.ntqLL_Struc, *Element1.ntqLLE_Struc, *Element2.ntqLLE_Struc)
  *Element1 - SizeOf(ntqLLE_Struc)
  *Element2 - SizeOf(ntqLLE_Struc)
  *Element1\PrevElement\NextElement = *Element2
  *Element1\NextElement\PrevElement = *Element2
  *Element2\PrevElement\NextElement = *Element1
  *Element2\NextElement\PrevElement = *Element1
  Swap *Element1\NextElement, *Element2\NextElement
  Swap *Element1\PrevElement, *Element2\PrevElement
EndProcedure

;Gibt den Pointer zum aktuellen Element zurück
Procedure ntqLL_GetPointer(*LL.ntqLL_Struc)
  If *LL\ActElement
    ProcedureReturn *LL\ActElement + SizeOf(ntqLLE_Struc)
  EndIf
  ProcedureReturn 0
EndProcedure
;Setzt das aktuelle Element zurück vor das erste
Procedure ntqLL_ResetList(*LL.ntqLL_Struc)
  *LL\ActElement = 0
  *LL\Act = 0
EndProcedure
;Löscht alle Element der Liste
Procedure ntqLL_ClearList(*LL.ntqLL_Struc)
  Protected *t
  If *LL\FirstElement
    *t = *LL\FirstElement
    Repeat
      *LL\ActElement = *t
      *t = *LL\ActElement\NextElement
      FreeMemory(*LL\ActElement)
    Until *t = 0
    *LL\Act = 0
    *LL\Count = 0
    *LL\ActElement = 0
    *LL\FirstElement = 0
    *LL\LastElement = 0
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

DataSection
  ntqLL_Procs:
    Data.l @ntqLL_Kill(), @ntqLL_AddElement(), @ntqLL_InsertElement(), @ntqLL_DeleteElement()
    Data.l @ntqLL_FirstElement(), @ntqLL_LastElement(), @ntqLL_IsNext(), @ntqLL_NextElement(), @ntqLL_IsPrevious(), @ntqLL_PreviousElement()
    Data.l @ntqLL_ListIndex(), @ntqLL_CountList(), @ntqLL_ChangeElement(), @ntqLL_SelectElement(), @ntqLL_SwapElements()
    Data.l @ntqLL_GetPointer(), @ntqLL_ResetList(), @ntqLL_ClearList()
EndDataSection

Procedure ntqLL_Create(Size.l)
  Protected *LL.ntqLL_Struc
  
  *LL = AllocateMemory(SizeOf(ntqLL_Struc))
  If *LL = 0 : ProcedureReturn #False : EndIf
  
  *LL\ActElement = 0
  *LL\FirstElement = 0
  *LL\LastElement = 0
  *LL\Count = 0
  *LL\Act = 0
  *LL\Size = Size
  
  *LL\VTable = ?ntqLL_Procs
  
  ProcedureReturn *LL
EndProcedure

*LinkedList.ntqLL = ntqLL_Create(SizeOf(LONG))
*Value.Long

Debug "Liste:"
For a.l = 1 To 10
  *Value = *LinkedList\AddElement()
  *Value\l = a * 5
  Debug *Value\l
Next

Debug "Viertes Element:"
*Value = *LinkedList\SelectElement(4)
Debug *Value\l
*Value2 = *LinkedList\SelectElement(8)

*LinkedList\SwapElements(*Value, *Value2)

Debug "Anzahl Elemente:"
Debug *LinkedList\CountList()
Debug "Aktuelles Element:"
Debug *LinkedList\ListIndex()

Debug "Liste jetzt:"
*LinkedList\ResetList()
While *LinkedList\IsNext()
  *Value = *LinkedList\NextElement()
  Debug *Value\l
Wend
Fehler bitte melden!
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8809
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Beitrag von NicTheQuick »

Na? Kanns denn überhaupt jemand gebrauchen?

Oder ist jemand an einr neuen ebenfalls Interface-orientierten
TreeLinkedList interessiert?
Benutzeravatar
freedimension
Admin
Beiträge: 1987
Registriert: 08.09.2004 13:19
Wohnort: Ludwigsburg
Kontaktdaten:

Beitrag von freedimension »

Nicht so ungeduldig hier! Hab den PB-Compiler noch nicht in mein Gehirn gebrannt :mrgreen:
Beginne jeden Tag als ob es Absicht wäre!
Bild
BILDblog
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8809
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Beitrag von NicTheQuick »

Komisch, ich dachte, ich hätte es gestern morgen schon reingestellt. /:->

Tja, manchmal vergeht die Zeit eben langsamer als man denkt. <)
Benutzeravatar
Batze
Beiträge: 1492
Registriert: 03.06.2005 21:58
Wohnort: Berlin
Kontaktdaten:

Beitrag von Batze »

Wie hab ich mir denn so eine TreeLL vorzustellen?
Hier sind meine Codes (aber die Seite geht gerade nicht):
http://www.basicpure.de.vu
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8809
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Beitrag von NicTheQuick »

Anscheinend kennst du meine alte TreeLL nicht.

Also das ist eigentlich ganz einfach:
Eine TreeLinkedList funktioniert so wie eine normale LinkedList, bloß kann
man zu jedem Element ein oder mehrere neue(s) Child-Element(e)
erstellen. An jedes Child-Element kann man dann auch wieder eine neue
Child-Liste anknüpfen.

Hier ein kleines Beispiel. Oben siehst du den Baum mit Rekursion und
Nummer der Elements in Parent- bzw. Child-Liste und im Ganzen. Unten
ist der Code, mit dem man die Liste erstellen werden kann. Die Zahlen
hinter den einzelnen Codezeilen gehören zu dem Baumdiagramm, damit
du siehst, wo du dich jetzt im Baum befindest, wenn du den Befehl
aufgerufen hast.

Code: Alles auswählen

Baum                            Rekursion   Element
 |-  1. Element                 1           1
 |-  2. Element                 1           2
 |       |-  1. Element         2           3
 |       |-  2. Element         2           4
 |       |-  3. Element         2           5
 |       |       |-  1. Element 3           6
 |       |       |-  2. Element 3           7
 |       |       |-  3. Element 3           8
 |       |-  4. Element         2           9
 |               |-  1. Element 3           10
 |-  3. Element                 1           11
 |-  4. Element                 1           12
 
 *TreeLL.ntqTLL = ntqTLL_Create()
 
 *TreeLL\AddElement()           1           1
 *TreeLL\AddElement()           1           2
 *TreeLL\AddChild()             2           3
 *TreeLL\AddElement()           2           4
 *TreeLL\AddElement()           2           5
 *TreeLL\AddChild()             3           6
 *TreeLL\AddElement()           3           7
 *TreeLL\AddElement()           3           8
 *TreeLL\Parent()               2           5
 *TreeLL\AddElement()           2           9
 *TreeLL\AddChild()             3           10
 *TreeLL\Parent()               2           9
 *TreeLL\Parent()               1           2
 *TreeLL\AddElement()           1           11
 *TreeLL\AddElement()           1           12
Benubi
Beiträge: 187
Registriert: 22.10.2004 17:51
Wohnort: Berlin, Wedding

Beitrag von Benubi »

Hi Nic,

ich hoffe Du hast nichts dagegen wenn ich mich zu wort melde, wenn doch, dann hast du erstmal Pech gehabt ...

1. ich habe es nicht getestet - denn ich habe schon ca. 3x ein "List-Interface" bzw. "Tree-Interface" geschrieben, dass zu 100% ohne PB-Listen zurrecht kommt (das soll nicht heissen, dass sie in jeder hinsicht besser seien).

2. sicherlich wird jemand verwendung dafür haben; ich benutzte auch meine LL-Interfaces, da wo ich LLs dynamisch erstellen muss ...
Jetzt ist es zwar auch in PB4.0 von Haus aus möglich dynamisch LLs zu erstellen, aber mit Interfaces und Objekten kann ich ordentlicher umgehen, und ich nehme an in die richtung kann man deinen Vorschlag auch deuten...

3. ich kann mir nur vorstellen, dass bei SwapElements Fehler auftreten könnten. D.h. ich habe es nicht getestet, nur habe ich bei eigenen experimenten festgestellt, dass "endlosschleiffen" in listen entstehen können:

A folgt auf B, oder B folgt auf A (keine Elemente dazwischen).

Ich habe hier in meinen interfaces dumme if´s eingebaut, damit das abgefangen wird (ist wohl schlechter "stil" von mir... wer weiss)


4. Verbesserungsvorschläge:

a) Ich nehme an die "GetPointer" - Methode bedeutet einen Pointer zum aktuellen element zu bekommen. Ich würde das nur umbennen in "GetCurrent()" oder "CurrentElement()".

b) Eine hocheffektive unfehlbare Sort-Funktion (daran bin ich bisher immer gescheitert ;-) ) einbauen.


Nochmal zur SwapElements -Methode von deinem Interface: Du benutzt dort den neuen Befehl "Swap": werden jetzt nur die ersten 2 Longs aus dem Element (*prev_ / *next_ element) geswapt, oder tauschst du damit die Struktur ?
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8809
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Beitrag von NicTheQuick »

zu 1.:
Hast du die Sources davon irgendwo? Die möchte ich mir auch mal
ansehen.

zu 2.:
In PB 4.0 ist dies eben nicht möglich. Man kann nur sowas hier machen:

Code: Alles auswählen

NewList *Pointer.LONG()
Aber man kann keine LinkedList dynamisch erstellen, denn sonst würde
ich das hier auch gar nicht machen.

zu 3.:
Danke wegen dem SwapElements. Tatsächlich müsste da ein Fehler
passieren, wenn man mit dem ersten oder letzten Element tauschen
würde. Zumindest würde dann FirstElement und LastElement nicht mehr
korrekt funktionieren. Da muss ich dann wohl noch ein paar Ifs einbauen.

zu 4.:
a) Da hast du Recht. Ich werde den Befehl umbenennen. So wird er wohl
verständlicher werden.

b) Stimmt, das ist eine gute Idee. Das mache ich dann per [c]OffsetOf()[/c]
-Befehl und Konstante à la [c]#ntqLL_String[/c], [c]#ntqLL_Long[/c] oder
so ähnlich.

zum Letzten:
Ich tausche nicht die Struktur, sondern biege nur die Pointer um. So ist es
sschließlich schneller und einfacher zu handeln.


Ansonsten vielen Dank für die Bemerkungen. Ich mag konstruktive Kritik. :allright:
Benutzeravatar
Batze
Beiträge: 1492
Registriert: 03.06.2005 21:58
Wohnort: Berlin
Kontaktdaten:

Beitrag von Batze »

Mir fällt gerade auf, genau das (dynamisch erstellte LL) brauch ich für mein neustes Projekt. :shock:
Hier sind meine Codes (aber die Seite geht gerade nicht):
http://www.basicpure.de.vu
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8809
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 64 GB DDR4-3200
Ubuntu 24.04.2 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken

Beitrag von NicTheQuick »

Also das mit dem QuickSort ist komplizierter als ich dachte.

Sogar die Beispiele auf PureArea sortieren falsch. Und als ich das C-
Beispiel von Wikipedia portiert hatte, hat es die Liste auch mehr gemischt
als sortiert.

Vielleicht bleibe ich doch erstmal beim BubbleSort.

Aber mal abwarten...
Jetzt geh ich erstmal schlafen... Puh... :freak:
Gesperrt