Spielerei: LinkedList stark vereinfacht

Hier könnt Ihr gute, von Euch geschriebene Codes posten. Sie müssen auf jeden Fall funktionieren und sollten möglichst effizient, elegant und beispielhaft oder einfach nur cool sein.
Antworten
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8812
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

Spielerei: LinkedList stark vereinfacht

Beitrag von NicTheQuick »

Hallo Mädels! :D

Hab eben für meine neue RayTracing-Engine eine LinkedList gebraucht, die
ich dynamisch erstellen kann, die schnell ist, und nur dazu da ist, Elemente
hinten anzuhängen, aber willkürlich wieder zu löschen.
Außerdem kann man nur entweder ein(en) Byte, Character, Word, Long,
Float, Double, Quad oder String in einem Element speichern. Ich selbst
benutze die Liste um Pointer darin zu speichern.

Hier ist der Code-Schnipsel, falls es jemanden interessieren sollte:

Code: Alles auswählen

Structure RTListElement
  *_list.RTList
  *_prev.RTListElement
  *_next.RTListElement
  StructureUnion
    b.b
    c.c
    w.w
    l.l
    f.f
    q.q
    d.d
    s.s
  EndStructureUnion
EndStructure

Structure RTList
  *first.RTListElement
  *last.RTListElement
  count.l
EndStructure

Procedure RTList_Add(*RTList.RTList)
  Protected *RTListElement.RTListElement
  
  *RTListElement = AllocateMemory(SizeOf(RTListElement))
  If *RTListElement = 0 : ProcedureReturn #False : EndIf
    
  If *RTList\count
    *RTListElement\_prev  = *RTList\last
    *RTList\last\_next    = *RTListElement
    *RTList\last          = *RTListElement
  Else
    *RTList\first = *RTListElement
    *RTList\last  = *RTListElement
  EndIf
  
  *RTList\count + 1
  *RTListElement\_list = *RTList
  
  ProcedureReturn *RTListElement
EndProcedure

Procedure RTList_Del(*RTListElement.RTListElement)
  Protected *_activ
  
  If *RTListElement\_list\count = 1
    *RTListElement\_list\first = 0
    *RTListElement\_list\last = 0
    *_activ = 0
  
  ElseIf *RTListElement\_prev = 0
    *RTListElement\_next\_prev = 0
    *RTListElement\_list\first = *RTListElement\_next
    *_activ = *RTListElement\_next
  
  ElseIf *RTListElement\_next = 0
    *RTListElement\_prev\_next = 0
    *RTListElement\_list\last = *RTListElement\_prev
    *_activ = 0
  
  Else
    *RTListElement\_next\_prev = *RTListElement\_prev
    *RTListElement\_prev\_next = *RTListElement\_next
    *_activ = *RTListElement\_next
  EndIf
  
  *RTListElement\_list\count - 1
  FreeMemory(*RTListElement)
  
  ProcedureReturn *_activ
EndProcedure

Procedure RTList_Clear(*RTList.RTList)
  Protected *RTListElement.RTListElement
  
  *RTListElement = *RTList\first
  While *RTListElement
    If *RTListElement\_next
      *RTListElement = *RTListElement\_next
      FreeMemory(*RTListElement\_prev)
    Else
      FreeMemory(*RTListElement)
    EndIf
  Wend
  
  *RTList\first = 0
  *RTList\last = 0
  *RTList\count = 0
  
  ProcedureReturn 0
EndProcedure

Macro RTList_First(RTList)
  RTList\first
EndMacro

Macro RTList_Last(RTList)
  RTList\last
EndMacro

Macro RTList_Next(RTListElement)
  RTListElement\_next
EndMacro

Macro RTList_Prev(RTListElement)
  RTListElement\_prev
EndMacro

Macro RTList_Count(RTList)
  RTList\count
EndMacro

liste.RTList ;Liste erstellen
*element.RTListElement ;Pointer für Elemente erstellen

For a = 1 To 100
  *element = RTList_Add(liste)
  *element\l = a
Next

Debug RTList_Count(liste)
Debug ""

*element = RTList_First(liste)
While *element
  If *element\l % 2 = 0 Or *element\l % 3 = 0 Or *element\l % 5 = 0 Or *element\l % 7 = 0
    *element = RTList_Del(*element)
  Else
    *element = RTList_Next(*element)
  EndIf
Wend

Debug "Die Primzahlen zwischen 7 und 100"

*element = RTList_First(liste)
While *element
  Debug *element\l
  *element = RTList_Next(*element)
Wend

Debug ""
Debug RTList_Count(liste)
Nach oben
Benutzeravatar
Kiffi
Beiträge: 10714
Registriert: 08.09.2004 08:21
Wohnort: Amphibios 9

Re: Spielerei: LinkedList stark vereinfacht

Beitrag von Kiffi »

> Hab eben für meine neue RayTracing-Engine eine LinkedList gebraucht,
> die ich dynamisch erstellen kann, die schnell ist, und nur dazu da ist,
> Elemente hinten anzuhängen, aber willkürlich wieder zu löschen.

interessant. Habe ich gleich mal ausprobiert. :-)

Gehe ich recht in der Annahme, dass der Geschwindigkeitsunterschied
jedoch recht marginal ist?

Code: Alles auswählen

z1=ElapsedMilliseconds()
For a = 1 To 10000000
  *element = RTList_Add(liste)
  *element\l = a
Next
z2=ElapsedMilliseconds()

Nic = z2-z1

NewList myList.l()

z1=ElapsedMilliseconds()
For a = 1 To 10000000
  AddElement(myList())
  myList() = a
Next
z2=ElapsedMilliseconds()

Fred = z2-z1

MessageRequester("Nic", Str(Nic))
MessageRequester("Fred", Str(Fred))
Durchlauf 1: Nic 4048 / Fred 4048
Durchlauf 2: Nic 4047 / Fred 4000
Durchlauf 3: Nic 4047 / Fred 4016

Grüße ... Kiffi
a²+b²=mc²
Nach oben
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8812
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 »

Von schneller hab ich ja nichts gesagt. Nur von schnell. Und ich denke doch,
dass sie das auch ist.
Am wichtigsten ist für mich allerdings, dass man sie dynamisch erstellen
kann und theoretisch auch Bäume daraus bauen kann.

///Edit 1:
Noch ein Vorteil, den ich eben vergessen hatte:
Die LinkedList merkt sich nicht, welches gerade das aktuelle Element ist,
sondern man hat immer einen Pointer vom Typ RTListElement, der das
aktuelle Element darstellt. Von ihm aus kann man immer zum nächsten,
vorherigen, ersten oder letzten Element springen.
Das ist zum Beispiel praktisch bei Multithreading. Zwei Threads können
beliebig auf die Liste zugreifen und durcheinander Sachen auslesen. Der
einzige Punkt, an dem es zu Speicherkonflikten kommen kann, ist wenn
einer der Threads Elemente löscht oder gar die ganze Liste löscht. Selbst
beim Hinzufügen neuer Elemente sollten keine Probleme auftreten. Notfalls
kann man immer noch einen Mutex pro Liste einbauen. Ich weiß aber
nicht, wie sich das dann auf die Geschwindigkeit ausübt.

///Edit 2:
Hier ein Beispiel dazu:

Code: Alles auswählen

Procedure Thread1(*List.RTList)
  Protected *element.RTListElement, s.s
  
  *element = RTList_First(*List)
  While *element
    s = "1: " + Str(*element\l) + Chr(13) + Chr(10)
    Print(s)
    *element = RTList_Next(*element)
  Wend
EndProcedure
Procedure Thread2(*List.RTList)
  Protected *element.RTListElement, s.s
  
  *element = RTList_Last(*List)
  While *element
    s = "2: " + Str(*element\l) + Chr(13) + Chr(10)
    Print(s)
    *element = RTList_Prev(*element)
  Wend
EndProcedure

List.RTList
*element.RTListElement
For a = 1 To 100
  *element = RTList_Add(List)
  *element\l = a
Next

OpenConsole()

thread1.l = CreateThread(@Thread1(), List)
thread2.l = CreateThread(@Thread2(), List)

WaitThread(thread1)
WaitThread(thread2)

Input()
CloseConsole()
Nach oben
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8812
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 »

Ich hab ein kleines Abdät. Ich hab das ganze nämlich zum Spaß mal in eine
TreeLinkedList verwandelt.

Und wenn ich die Woche und Lust habe, bastel ich noch ein passendes
Interface dazu, dass die TLL dann auch noch mit dem TreeGadget verbindet.

Aber hier erstmal der Source.

Code: Alles auswählen

;Info: Dynamisch erstellbare TreeLinkedLists

Structure TLL
  *parent.TLLElement ;Pointer zu übergeordnetem Element
  *first.TLLElement  ;Pointer zum ersten Element in der Liste
  *last.TLLElement   ;Pointer zum letzten Element in der Liste
  count.l               ;Anzahl der Elemente in der Liste
EndStructure

Structure TLLElement
  *_list.TLL         ;Pointer zum Parent (darf nicht 0 sein)
  *_prev.TLLElement  ;Pointer zum Vorgängerelement (wenn 0, ist es das erste)
  *_next.TLLElement  ;Pointer zum Nachfolgerelement (wenn 0, ist es das letzte)
  *_node.TLL         ;Pointer zu Unterliste (wenn 0, gibt es keine)
  l.l                   ;Userdata 1 (Long)
  *d                    ;Userdata 2 (Pointer)
EndStructure

;           TLL: Liste, der ein Element hinzugefügt werden soll
;    TLLElement: Element wird aus seiner Liste ans Ende von TTL verschoben. Wenn 0, wird am Ende von TTL ein neues Element erstellt
;        Return: Element, das hinzugefügt wurde
Procedure TLL_Add(*TLL.TLL, *TLLElement.TLLElement = 0) ;Fügt ans Ende der Liste ein Element hinzu oder verschiebt ein Element ans Ende (Listenübergreifend)
  
  If *TLLElement = 0
    *TLLElement = AllocateMemory(SizeOf(TLLElement))
    If *TLLElement = 0 : ProcedureReturn #False : EndIf
  Else
    ;Erst Element aus seiner Position herausnehmen
    If *TLLElement\_prev = 0
      *TLLElement\_next\_prev = 0
      *TLLElement\_list\first = *TLLElement\_next
    
    ElseIf *TLLElement\_next = 0
      *TLLElement\_prev\_next = 0
      *TLLElement\_list\last = *TLLElement\_prev
    
    Else
      *TLLElement\_prev\_next = *TLLElement\_next
      *TLLElement\_next\_prev = *TLLElement\_prev
    EndIf
    *TLLElement\_list\count - 1  ;Aus der alten Liste abziehen
  EndIf
    
  If *TLL\last
    *TLLElement\_prev  = *TLL\last
    *TLLElement\_next  = 0
    *TLL\last\_next    = *TLLElement
    *TLL\last          = *TLLElement
  Else
    *TLL\first = *TLLElement
    *TLL\last  = *TLLElement
  EndIf
  
  *TLL\count + 1
  *TLLElement\_list = *TLL
  
  ProcedureReturn *TLLElement
EndProcedure

;           TLL: Löscht alle Elemente in der Liste samt Unterelementen, also Vorsicht bei Zirkelbeziehungen!
;        Return: Immer #True
Procedure TLL_Clear(*TLL.TLL) ;Löscht die gesamte Liste (Vorsicht bei Zirkelbeziehungen!)
  Protected *TLLElement.TLLElement
  
  *TLLElement = *TLL\first
  While *TLLElement
    If *TLLElement\_node  ;Wenn eine Unterliste existiert, rekursiv löschen
      TLL_Clear(*TLLElement\_node)
    EndIf
    If *TLLElement\_next
      *TLLElement = *TLLElement\_next
      FreeMemory(*TLLElement\_prev)
    Else
      FreeMemory(*TLLElement)
      Break
    EndIf
  Wend
  
  *TLL\first = 0
  *TLL\last = 0
  *TLL\count = 0
  
  ProcedureReturn #True
EndProcedure

;    TLLElement: Löscht das Element samt Unterelementen, also Vorsicht bei Zirkelbeziehungen!
;        Return: Nachfolgendes Element oder Null, wenn kein Element nachfolgte
Procedure TLL_Del(*TLLElement.TLLElement) ;Löscht das Element aus der Liste (Vorsicht bei Zirkelbeziehungen!)
  Protected *_activ
  
  If *TLLElement\_node
    TLL_Clear(*TLLElement\_node)
  EndIf
  
  If *TLLElement\_list\count = 1
    *TLLElement\_list\first = 0
    *TLLElement\_list\last = 0
    *_activ = 0
  
  ElseIf *TLLElement\_prev = 0
    *TLLElement\_next\_prev = 0
    *TLLElement\_list\first = *TLLElement\_next
    *_activ = *TLLElement\_next
  
  ElseIf *TLLElement\_next = 0
    *TLLElement\_prev\_next = 0
    *TLLElement\_list\last = *TLLElement\_prev
    *_activ = 0
  
  Else
    *TLLElement\_next\_prev = *TLLElement\_prev
    *TLLElement\_prev\_next = *TLLElement\_next
    *_activ = *TLLElement\_next
  EndIf
  
  *TLLElement\_list\count - 1
  FreeMemory(*TLLElement)
  
  ProcedureReturn *_activ
EndProcedure

;    TLLElement: Erstellt ein neues Element vor dem angegebenen
;        Return: Neues Element
Procedure TLL_Insert(*TLLElement.TLLElement) ;Fügt vor das angegebene Element ein neues ein
  Protected *NewTLLElement.TLLElement
  
  *NewTLLElement = AllocateMemory(SizeOf(TLLElement))
  If *NewTLLElement = 0 : ProcedureReturn #False : EndIf
  
  *NewTLLElement\_list = *TLLElement\_list
  *NewTLLElement\_prev = *TLLElement\_prev
  If *TLLElement\_prev
    *TLLElement\_prev\_next = *NewTLLElement
  Else
    *TLLElement\_list\first = *NewTLLElement
  EndIf
  *TLLElement\_prev = *NewTLLElement
  *NewTLLElement\_next = *TLLElement
  *TLLElement\_list\count + 1
  
  ProcedureReturn *NewTLLElement
EndProcedure

;MoveTLLElement: Verschiebt das Element vor TLLElement, auch aus anderer Liste heraus
;    TLLElement: Element, vor dem MoveTLLElement eingefügt werden soll
;        Return: #True, wenn erfolgreich
Procedure TLL_Move(*MoveTLLElement.TLLElement, *TLLElement.TLLElement) ;Verschiebt MoveElement vor das Element (Listenübergreifend)
  If *MoveTLLElement = *TLLElement : ProcedureReturn #False : EndIf ;ein und das selbe Element
  
  If *TLLElement
    If *MoveTLLElement = *TLLElement\_prev : ProcedureReturn #True : EndIf ;MoveElement ist schon vor dem Element
  Else
    If *MoveTLLElement\_next = 0 : ProcedureReturn #True : EndIf ;MoveElement ist schon am Ende
  EndIf
  
  ;Erst MoveElement aus seiner Position herausnehmen
  If *MoveTLLElement\_prev = 0
    *MoveTLLElement\_next\_prev = 0
    *MoveTLLElement\_list\first = *MoveTLLElement\_next
  
  ElseIf *MoveTLLElement\_next = 0
    *MoveTLLElement\_prev\_next = 0
    *MoveTLLElement\_list\last = *MoveTLLElement\_prev
  
  Else
    *MoveTLLElement\_prev\_next = *MoveTLLElement\_next
    *MoveTLLElement\_next\_prev = *MoveTLLElement\_prev
  EndIf
  *MoveTLLElement\_list\count - 1  ;Aus der alten Liste abziehen
  
  ;und dann an richtiger Stelle wieder einfügen
  If *TLLElement = 0 ;Verschiebt MoveElement ans Ende
    *MoveTLLElement\_prev = *MoveTLLElement\_list\last
    *MoveTLLElement\_list\last\_next = *MoveTLLElement
    *MoveTLLElement\_next = 0
  
  Else ;Verschiebt MoveElement vor Element
    *MoveTLLElement\_list = *TLLElement\_list
    *MoveTLLElement\_prev = *TLLElement\_prev
    If *TLLElement\_prev
      *TLLElement\_prev\_next = *MoveTLLElement
    Else
      *TLLElement\_list\first = *MoveTLLElement
    EndIf
    *TLLElement\_prev = *MoveTLLElement
    *MoveTLLElement\_next = *TLLElement
    *MoveTLLElement\_list\count + 1  ;Zur neuen Liste hinzuaddieren
  EndIf
  
  ProcedureReturn #True
EndProcedure

;    TLLElement: Element, in dem eine neue Unterliste erstellt werden soll. Wenn 0, wird eine komplett neue Liste erstellt
;        Return: Neue Liste
Procedure TLL_NewList(*TLLElement.TLLElement = 0) ;Erstellt eine Liste oder eine neue Unterliste in einem Element
  Protected *TLL.TLL
  
  If *TLLElement
    If *TLLElement\_node : ProcedureReturn *TLLElement\_node : EndIf
    
    *TLLElement\_node = AllocateMemory(SizeOf(TLL))
    If *TLLElement\_node = 0 : ProcedureReturn #False : EndIf
    
    *TLLElement\_node\Parent = *TLLElement
    
    ProcedureReturn *TLLElement\_node
  
  Else
    *TLL = AllocateMemory(SizeOf(TLL))
    If *TLL = 0 : ProcedureReturn #False : EndIf
    
    ProcedureReturn *TLL
  EndIf
EndProcedure

;           TLL: Liste
;        Return: Erstes Element der Liste. Wenn 0, ist die Liste leer
Macro TLL_First(TLL) ;Gibt das erste Element der Liste zurück
  TLL\first
EndMacro

;           TLL: Liste
;        Return: Letztes Element der Liste. Wenn 0, ist die Liste leer
Macro TLL_Last(TLL) ;Gibt das letzte Element der Liste zurück
  TLL\last
EndMacro

;    TLLElement: Element
;        Return: Nächstes Element. Wenn 0, ist es das letzte Element in seiner Liste
Macro TLL_Next(TLLElement) ;Gibt das nächste Element zurück
  TLLElement\_next
EndMacro

;    TLLElement: Element
;        Return: Vorheriges Element. Wenn 0, ist es das erste Element in seiner Liste
Macro TLL_Prev(TLLElement) ;Gibt das vorherige Element zurück
  TLLElement\_prev
EndMacro

;           TLL: Liste
;        Return: Anzahl Elemente der Liste
Macro TLL_Count(TLL) ;Gibt die Anzahl der Elemente der Liste zurück
  TLL\count
EndMacro

;    TLLElement: Element
;        Return: Liste, der das Element angehört
Macro TLL_List(TLLElement) ;Gibt den Pointer zur Liste zurück
  TLLElement\_list
EndMacro

;    TLLElement: Element
;        Return: Übergeordnetes Element. Wenn Null, gibt es keins.
Macro TLL_Parent(TLLElement) ;Gibt den Pointer zum übergeordneten Element zurück
  TLLElement\_list\Parent
EndMacro

;    TLLElement: Element
;        Return: Untergeordnete Liste. Wenn Null, gibt es keine
Macro TLL_ChildList(TLLElement)
  TLLElement\_node
EndMacro

;           TLL: Liste
;        Return: Übergeordnete Liste
Macro TLL_ParentList(TLL)
  TLL\Parent\_list
EndMacro

;    TLLElement: Element
;        Return: Erstes Unterelement, nächstes Element, Nachfolgeelement des übergeordneten Elementes oder 0
Procedure TLL_NextEx(*TLLElement.TLLElement)
  If *TLLElement\_node ;Wenn es eine Unterliste gibt...
    If *TLLElement\_node\first ;...gehe zum ersten Unterelement
      ProcedureReturn *TLLElement\_node\first
    EndIf
  EndIf
  
  While *TLLElement ;Wenn es ein Element gibt...
    If *TLLElement\_next ;...gib das nächste Element zurück, falls vorhanden,...
      ProcedureReturn *TLLElement\_next
    Else
      If *TLLElement\_list\Parent ;...springe zum übergeordneten Element,...
        *TLLElement = *TLLElement\_list\Parent
      Else ;...oder gibt 0 zurück, wenn es kein Element mehr in der Liste gibt
        ProcedureReturn 0
      EndIf
    EndIf
  Wend
  
  ProcedureReturn 0
EndProcedure
Ich hab den Source ins jaPBe-Includes-Verzeichnis geworfen.

Und hier ist auch ein Beispiel-Code:

Code: Alles auswählen

;hier wird eine zufällige Liste erstellt mit 2 Unterebenen und ausgegeben

*List.TLL = TLL_NewList()
*Element.TLLElement

;Liste füllen
Debug "Liste erstellen..."
For a = 1 To 5
  *Element = TLL_Add(*List)  ;Ein neues Element hinzufügen
  *Element\l = a  ;Wert zuweisen
  Debug *Element\l
  d = Random(2) + 1
  If d
    *List = TLL_NewList(*Element) ;Neue Unterliste erstellen
    For b = 1 To d
      *Element = TLL_Add(*List) ;Elemente hinzufügen
      *Element\l = a * 100 + b
      Debug *Element\l
      e = Random(3)
      If e
        *List = TLL_NewList(*Element)
        For c = 1 To e
          *Element = TLL_Add(*List)
          *Element\l = a * 10000 + b * 100 + c
          Debug *Element\l
        Next
        *List = TLL_ParentList(*List)
      EndIf
    Next
    *List = TLL_ParentList(*List)
  EndIf
Next

Debug ""
Debug "Liste ausgeben..."

;Liste ausgeben
*Element = TLL_First(*List)
While *Element
  Debug *Element\l
  
  *Element = TLL_NextEx(*Element)
Wend

Debug ""
Debug ""

;Zweite Liste erstellen
Define *List2.TLL, *Element2.TLLElement
*List2 = TLL_NewList()
*Element2 = TLL_Add(*List2)
*Element2\l = 999999999

;Erste Liste durchgehen und Element mit der Nummer 3 suchen
*Element = TLL_First(*List)
While *Element
  If *Element\l = 3
    Break
  EndIf
  *Element = TLL_NextEx(*Element)
Wend

;*Element aus *List herausnehmen und an *List2 anfügen
TLL_Add(*List2, *Element)

;Erste Liste durchgehen und Element mit der Nummer 4 suchen
*Element = TLL_First(*List)
While *Element
  If *Element\l = 4
    Break
  EndIf
  *Element = TLL_NextEx(*Element)
Wend

;*Element2 aus *List2 herausnehmen und vor *Element verschieben
TLL_Move(*Element2, *Element)

;Beide Liste anzeigen
;Liste ausgeben
Debug "Liste 1"
*Element = TLL_First(*List)
While *Element
  Debug *Element\l
  
  *Element = TLL_NextEx(*Element)
Wend

Debug "Liste 2"
*Element = TLL_First(*List2)
While *Element
  Debug *Element\l
  
  *Element = TLL_NextEx(*Element)
Wend
Ein Swap-Befehl kommt noch, der Listenübergreifend Elemente
austauschen kann.
Nach oben
Benutzeravatar
Vallan
Beiträge: 223
Registriert: 20.01.2006 19:34
Kontaktdaten:
Kontaktdaten von Vallan

Beitrag von Vallan »

Hört sich gut an.
ich nehme an das die genau so gut ist (oder besser) wie diene TreeLL (die war auch cool!) :allright:

PS: Raytracing Engine :o hört sich gut an...
Nach oben
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8812
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 »

Vallan hat geschrieben:Hört sich gut an.
ich nehme an das die genau so gut ist (oder besser) wie diene TreeLL (die war auch cool!) :allright:
Die neue TLL ist auf jeden Fall schneller, komfortabler und dynamischer.
Die Struktur TLLElement kann man auch beliebig erweitern, wenn man
möchte. Sonst steht standardmäßig ein Long und ein Pointer zur Verfügung.
Aber dafür ist sie ja OpenSource. :)
Vallan hat geschrieben:PS: Raytracing Engine :o hört sich gut an...
Siehe hier
Nach oben
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8812
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 »

Mir fällt grad auf, dass ich den Swap-Befehl schon ewig fertig habe, ihn aber
noch nie ins Forum gepostet habe. Hier ist also nochmal der ganze Code:

Code: Alles auswählen

;Info: Dynamisch erstellbare TreeLinkedLists

Structure TLL
  *parent.TLLElement ;Pointer zu übergeordnetem Element
  *first.TLLElement  ;Pointer zum ersten Element in der Liste
  *last.TLLElement   ;Pointer zum letzten Element in der Liste
  count.l            ;Anzahl der Elemente in der Liste
EndStructure

Structure TLLElement
  *_list.TLL         ;Pointer zur zugehörenden Liste (darf nicht 0 sein)
  *_prev.TLLElement  ;Pointer zum Vorgängerelement (wenn 0, ist es das erste)
  *_next.TLLElement  ;Pointer zum Nachfolgerelement (wenn 0, ist es das letzte)
  *_node.TLL         ;Pointer zu Unterliste (wenn 0, gibt es keine)
  l.l                ;Userdata 1 (Long) (z.B. Typ der Daten an *d)
  *d                 ;Userdata 2 (Pointer) (z.B. Pointer zu Daten)
EndStructure

;           TLL: Liste, der ein Element hinzugefügt werden soll
;    TLLElement: Element wird aus seiner Liste ans Ende von TTL verschoben. Wenn 0, wird am Ende von TTL ein neues Element erstellt
;        Return: Element, das hinzugefügt wurde
Procedure TLL_Add(*TLL.TLL, *TLLElement.TLLElement = 0) ;Fügt ans Ende der Liste ein Element hinzu oder verschiebt ein Element ans Ende (Listenübergreifend)
  
  If *TLLElement = 0
    *TLLElement = AllocateMemory(SizeOf(TLLElement))
    If *TLLElement = 0 : ProcedureReturn #False : EndIf
  Else
    ;Erst Element aus seiner Position herausnehmen
    If *TLLElement\_prev = 0
      *TLLElement\_next\_prev = 0
      *TLLElement\_list\first = *TLLElement\_next
    
    ElseIf *TLLElement\_next = 0
      *TLLElement\_prev\_next = 0
      *TLLElement\_list\last = *TLLElement\_prev
    
    Else
      *TLLElement\_prev\_next = *TLLElement\_next
      *TLLElement\_next\_prev = *TLLElement\_prev
    EndIf
    *TLLElement\_list\count - 1  ;Aus der alten Liste abziehen
  EndIf
    
  If *TLL\last
    *TLLElement\_prev  = *TLL\last
    *TLLElement\_next  = 0
    *TLL\last\_next    = *TLLElement
    *TLL\last          = *TLLElement
  Else
    *TLL\first = *TLLElement
    *TLL\last  = *TLLElement
  EndIf
  
  *TLL\count + 1
  *TLLElement\_list = *TLL
  
  ProcedureReturn *TLLElement
EndProcedure

;           TLL: Löscht alle Elemente in der Liste samt Unterelementen, also Vorsicht bei Zirkelbeziehungen!
;        Return: Immer #True
Procedure TLL_Clear(*TLL.TLL) ;Löscht die gesamte Liste (Vorsicht bei Zirkelbeziehungen!)
  Protected *TLLElement.TLLElement
  
  *TLLElement = *TLL\first
  While *TLLElement
    If *TLLElement\_node  ;Wenn eine Unterliste existiert, rekursiv löschen
      TLL_Clear(*TLLElement\_node)
    EndIf
    If *TLLElement\_next
      *TLLElement = *TLLElement\_next
      FreeMemory(*TLLElement\_prev)
    Else
      FreeMemory(*TLLElement)
      Break
    EndIf
  Wend
  
  *TLL\first = 0
  *TLL\last = 0
  *TLL\count = 0
  
  ProcedureReturn #True
EndProcedure

;    TLLElement: Löscht das Element samt Unterelementen, also Vorsicht bei Zirkelbeziehungen!
;        Return: Nachfolgendes Element oder Null, wenn kein Element nachfolgte
Procedure TLL_Del(*TLLElement.TLLElement) ;Löscht das Element aus der Liste (Vorsicht bei Zirkelbeziehungen!)
  Protected *_activ
  
  If *TLLElement\_node
    TLL_Clear(*TLLElement\_node)
  EndIf
  
  If *TLLElement\_list\count = 1
    *TLLElement\_list\first = 0
    *TLLElement\_list\last = 0
    *_activ = 0
  
  ElseIf *TLLElement\_prev = 0
    *TLLElement\_next\_prev = 0
    *TLLElement\_list\first = *TLLElement\_next
    *_activ = *TLLElement\_next
  
  ElseIf *TLLElement\_next = 0
    *TLLElement\_prev\_next = 0
    *TLLElement\_list\last = *TLLElement\_prev
    *_activ = 0
  
  Else
    *TLLElement\_next\_prev = *TLLElement\_prev
    *TLLElement\_prev\_next = *TLLElement\_next
    *_activ = *TLLElement\_next
  EndIf
  
  *TLLElement\_list\count - 1
  FreeMemory(*TLLElement)
  
  ProcedureReturn *_activ
EndProcedure

;    TLLElement: Erstellt ein neues Element vor dem angegebenen
;        Return: Neues Element
Procedure TLL_Insert(*TLLElement.TLLElement) ;Fügt vor das angegebene Element ein neues ein
  Protected *NewTLLElement.TLLElement
  
  *NewTLLElement = AllocateMemory(SizeOf(TLLElement))
  If *NewTLLElement = 0 : ProcedureReturn #False : EndIf
  
  *NewTLLElement\_list = *TLLElement\_list
  *NewTLLElement\_prev = *TLLElement\_prev
  If *TLLElement\_prev
    *TLLElement\_prev\_next = *NewTLLElement
  Else
    *TLLElement\_list\first = *NewTLLElement
  EndIf
  *TLLElement\_prev = *NewTLLElement
  *NewTLLElement\_next = *TLLElement
  *TLLElement\_list\count + 1
  
  ProcedureReturn *NewTLLElement
EndProcedure

;MoveTLLElement: Verschiebt das Element vor TLLElement oder ans Ende der Liste, wenn TLLElement = 0, auch aus anderer Liste heraus
;    TLLElement: Element, vor dem MoveTLLElement eingefügt werden soll
;        Return: #True, wenn erfolgreich
Procedure TLL_Move(*MoveTLLElement.TLLElement, *TLLElement.TLLElement) ;Verschiebt MoveElement vor das Element (Listenübergreifend)
  If *MoveTLLElement = *TLLElement : ProcedureReturn #False : EndIf ;ein und das selbe Element
  
  If *TLLElement
    If *MoveTLLElement = *TLLElement\_prev : ProcedureReturn #True : EndIf ;MoveElement ist schon vor dem Element
  Else
    If *MoveTLLElement\_next = 0 : ProcedureReturn #True : EndIf ;MoveElement ist schon am Ende
  EndIf
  
  ;Erst MoveElement aus seiner Position herausnehmen
  If *MoveTLLElement\_prev = 0
    *MoveTLLElement\_next\_prev = 0
    *MoveTLLElement\_list\first = *MoveTLLElement\_next
  
  ElseIf *MoveTLLElement\_next = 0
    *MoveTLLElement\_prev\_next = 0
    *MoveTLLElement\_list\last = *MoveTLLElement\_prev
  
  Else
    *MoveTLLElement\_prev\_next = *MoveTLLElement\_next
    *MoveTLLElement\_next\_prev = *MoveTLLElement\_prev
  EndIf
  *MoveTLLElement\_list\count - 1  ;Aus der alten Liste abziehen
  
  ;und dann an richtiger Stelle wieder einfügen
  If *TLLElement = 0 ;Verschiebt MoveElement ans Ende
    *MoveTLLElement\_prev = *MoveTLLElement\_list\last
    *MoveTLLElement\_list\last\_next = *MoveTLLElement
    *MoveTLLElement\_next = 0
  
  Else ;Verschiebt MoveElement vor Element
    *MoveTLLElement\_list = *TLLElement\_list
    *MoveTLLElement\_prev = *TLLElement\_prev
    If *TLLElement\_prev
      *TLLElement\_prev\_next = *MoveTLLElement
    Else
      *TLLElement\_list\first = *MoveTLLElement
    EndIf
    *TLLElement\_prev = *MoveTLLElement
    *MoveTLLElement\_next = *TLLElement
    *MoveTLLElement\_list\count + 1  ;Zur neuen Liste hinzuaddieren
  EndIf
  
  ProcedureReturn #True
EndProcedure

;   TLLElement1: Erstes Element
;   TLLElement2: Zweites Element
;        Return: #True, wenn Elemente ausgetauscht wurden
Procedure TLL_Swap(*TLLElement1.TLLElement, *TLLElement2.TLLElement)
  Protected *_next.TLLElement = *TLLElement1\_next, *_list.TLL = *TLLElement1\_list
  
  If *TLLElement1 = *TLLElement2 : ProcedureReturn #False : EndIf
  
  If TLL_Move(*TLLElement1, *TLLElement2)
    If *_next
      ProcedureReturn TLL_Move(*TLLElement2, *_next)
    Else
      ProcedureReturn TLL_Add(*TLLElement2, *_list)
    EndIf
  EndIf
  
  ProcedureReturn #False
EndProcedure

;    TLLElement: Element, in dem eine neue Unterliste erstellt werden soll. Wenn 0, wird eine komplett neue Liste erstellt
;        Return: Neue Liste
Procedure TLL_NewList(*TLLElement.TLLElement = 0) ;Erstellt eine Liste oder eine neue Unterliste in einem Element
  Protected *TLL.TLL
  
  If *TLLElement
    If *TLLElement\_node : ProcedureReturn *TLLElement\_node : EndIf
    
    *TLLElement\_node = AllocateMemory(SizeOf(TLL))
    If *TLLElement\_node = 0 : ProcedureReturn #False : EndIf
    
    *TLLElement\_node\Parent = *TLLElement
    
    ProcedureReturn *TLLElement\_node
  
  Else
    *TLL = AllocateMemory(SizeOf(TLL))
    If *TLL = 0 : ProcedureReturn #False : EndIf
    
    ProcedureReturn *TLL
  EndIf
EndProcedure

;           TLL: Liste
;        Return: Erstes Element der Liste. Wenn 0, ist die Liste leer
Macro TLL_First(TLL) ;Gibt das erste Element der Liste zurück
  TLL\first
EndMacro

;           TLL: Liste
;        Return: Letztes Element der Liste. Wenn 0, ist die Liste leer
Macro TLL_Last(TLL) ;Gibt das letzte Element der Liste zurück
  TLL\last
EndMacro

;    TLLElement: Element
;        Return: Nächstes Element. Wenn 0, ist es das letzte Element in seiner Liste
Macro TLL_Next(TLLElement) ;Gibt das nächste Element zurück
  TLLElement\_next
EndMacro

;    TLLElement: Element
;        Return: Vorheriges Element. Wenn 0, ist es das erste Element in seiner Liste
Macro TLL_Prev(TLLElement) ;Gibt das vorherige Element zurück
  TLLElement\_prev
EndMacro

;           TLL: Liste
;        Return: Anzahl Elemente der Liste
Macro TLL_Count(TLL) ;Gibt die Anzahl der Elemente der Liste zurück
  TLL\count
EndMacro

;    TLLElement: Element
;        Return: Liste, der das Element angehört
Macro TLL_List(TLLElement) ;Gibt den Pointer zur Liste zurück
  TLLElement\_list
EndMacro

;    TLLElement: Element
;        Return: Übergeordnetes Element. Wenn Null, gibt es keins.
Macro TLL_Parent(TLLElement) ;Gibt den Pointer zum übergeordneten Element zurück
  TLLElement\_list\Parent
EndMacro

;    TLLElement: Element
;        Return: Untergeordnete Liste. Wenn Null, gibt es keine
Macro TLL_ChildList(TLLElement)
  TLLElement\_node
EndMacro

;           TLL: Liste
;        Return: Übergeordnete Liste
Macro TLL_ParentList(TLL)
  TLL\Parent\_list
EndMacro

;    TLLElement: Element
;        Return: Erstes Unterelement, nächstes Element, Nachfolgeelement des übergeordneten Elementes oder 0
Procedure TLL_NextEx(*TLLElement.TLLElement)
  If *TLLElement\_node ;Wenn es eine Unterliste gibt...
    If *TLLElement\_node\first ;...gehe zum ersten Unterelement
      ProcedureReturn *TLLElement\_node\first
    EndIf
  EndIf
  
  While *TLLElement ;Wenn es ein Element gibt...
    If *TLLElement\_next ;...gib das nächste Element zurück, falls vorhanden,...
      ProcedureReturn *TLLElement\_next
    Else
      If *TLLElement\_list\Parent ;...springe zum übergeordneten Element,...
        *TLLElement = *TLLElement\_list\Parent
      Else ;...oder gibt 0 zurück, wenn es kein Element mehr in der Liste gibt
        ProcedureReturn 0
      EndIf
    EndIf
  Wend
  
  ProcedureReturn 0
EndProcedure
Nach oben
Benutzeravatar
milan1612
Beiträge: 810
Registriert: 15.04.2007 17:58

Beitrag von milan1612 »

Du liebst Pointer, oder? :mrgreen:
Bin nur noch sehr selten hier, bitte nur noch per PN kontaktieren
Nach oben
Kaeru Gaman
Beiträge: 17389
Registriert: 10.11.2004 03:22

Beitrag von Kaeru Gaman »

pointers are vital!
Der Narr denkt er sei ein weiser Mann.
Der Weise weiß, dass er ein Narr ist.
Nach oben
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8812
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 »

milan1612 hat geschrieben:Du liebst Pointer, oder? :mrgreen:
Und wie! :mrgreen:
Du solltest mal mein aktuelles Projekt sehen. :lol:
Bei... ähm... 3210 Zeilen Code kommt schon was zusammen. Aber die
TreeLL brauch ich da gar nicht. :lol:
Nach oben
Antworten

Zurück zu „Code, Tipps und Tricks“