Da hierbei nicht der Inhalt der LinkedList-Einträge sondern nur die Zeiger auf das nächste/vorhergehende Elemente getauscht wird sollte sie recht performant sein.
Sie ist so gestalltet, dass es möglich ist eine x-beliebige LinkedList umzudrehen - egal von welchem Typ oder ob strukturiert oder nicht.
Als Parameter wird die Adresse eines Elements der LinkedList benötigt (@myLinkedList()) - welches ist dabei egal.
Weiterhin wird noch die Größe der Struktur benötigt.
Diese kann wie üblich durch SizeOF() ermittelt werden:
- SizeOf(BYTE)
- SizeOf(LONG)
- SizeOf(STRING)
- SizeOf(MyStructure)
Hier mal die Prozedur als Include ("FlipLinkedList_Include.pbi"):
Code: Alles auswählen
; ###############################################################################
; ### Procedure : FlipLinkedList() ###
; ### Date : 03.08.2007 ###
; ### Author : Albert Cremers (alias PureLust) ###
; ### PB-Version : 4.x (testet - should work on older versions as well) ###
; ### OS : Windows (tested), Lunix, Max OSX (should work as well) ###
; ### Forum-Thread : http://www.purebasic.fr/german/viewtopic.php?t=13816 ###
; ### ###
; ### With this Routine you can flip the order of a LinkedList(). ###
; ### Because it just changes the Next/Prev-Pointer instead of the whole ###
; ### content of the list it should be quite performant. ###
; ### ###
; ### It works with any kind of LinkedList and it doesn't matter if it's ###
; ### structured or not. ###
; ### ###
; ### Parameters: ###
; ### ###
; ### - *PointerToLinkedListElement : a Pointer to a valid Element of the ###
; ### LinkedList whose order should be ###
; ### flipped. ###
; ### e.g.: @myLinkedList() ###
; ### ###
; ### - SizeOfLinkedListStruckture : the size of the LinkedList-Structure ###
; ### e.g.: SizeOf(LONG) ###
; ### SizeOf(STRING ###
; ### SizeOf(YourStructure) ###
; ### ###
; ### It includes some error-handling which it notifies through the ###
; ### Debug-window. ###
; ### ###
; ### Results: ###
; ### It results the number of Elements which where flipped. ###
; ### This number should be equal to CountList(). ###
; ### if an error occurs, the result will be "-1". ###
; ### ###
; ### Example: ###
; ### ###
; ### NewList MyLinkedList.w() ###
; ### .... ###
; ### FlipLinkedList(@MyLinkedList(), SizeOf(WORD)) ###
; ### ###
; ###############################################################################
Procedure.l FlipLinkedList(*PointerToLinkedListElement, SizeOfLinkedListStruckture)
Structure LinkedListHeader
Next.l
Prev.l
EndStructure
Protected Buffer, Counter, Error = #False
Protected *AktElement.LinkedListHeader = *PointerToLinkedListElement-8
Protected *FirstElement.LinkedListHeader
Protected *LastElement.LinkedListHeader
Protected *Dummy.LinkedListHeader
If SizeOfLinkedListStruckture > 0
Buffer = AllocateMemory(SizeOfLinkedListStruckture)
If Not Buffer
Debug "FlipLinkedList Error !!! Could not allocate Memory for LinkedList-Structure ("+Str(SizeOfLinkedListStruckture)+" Bytes)."
ProcedureReturn -1
EndIf
Else
Debug "FlipLinkedList Error !!! Illegal Size of LinkedList-Structure ("+Str(SizeOfLinkedListStruckture)+" Bytes)."
ProcedureReturn -1
EndIf
; ############################################################################
; ### First make sure, that it's a valid Pointer to a LinkedList-Element ###
; ############################################################################
If *AktElement\Next
*Dummy = *AktElement\Next
If *Dummy\Prev <> *AktElement : Error = #True : EndIf
ElseIf *AktElement\Prev
*Dummy = *AktElement\Prev
If *Dummy\Next <> *AktElement : Error = #True : EndIf
Else
Debug "FlipLinkedList Error !!! Given Parameter was either not a valid Pointer to a LL-Element or LL was empty !!!"
FreeMemory(Buffer)
ProcedureReturn 0
EndIf
If Error
Debug "FlipLinkedList Error !!! Given Parameter was not a valid Pointer to a LinkedList-Element !!!"
FreeMemory(Buffer)
ProcedureReturn -1
EndIf
; ######################################################
; ### Now find the first Element of the LinkedList ###
; ######################################################
While *AktElement\Prev
*AktElement = *AktElement\Prev
Wend
*FirstElement = *AktElement
; #######################################################################
; ### Now run through the LinkedList and swap all Next/Prev-Pointer ###
; #######################################################################
*AktElement = *AktElement\Next
While *AktElement\Next
*Dummy = *AktElement\Next
*AktElement\Next = *AktElement\Prev
*AktElement\Prev = *Dummy
*AktElement = *Dummy
Counter + 1
Wend
; #####################################
; ### Now swap First/Last Element ###
; ##################################################################################
; ### Because I don't know how to tell PB where the first/last Element is, ###
; ### I leave them as they are and swap the content of the 2 Elements instead. ###
; ##################################################################################
CopyMemory(*FirstElement+8, Buffer , SizeOfLinkedListStruckture)
CopyMemory(*AktElement +8, *FirstElement+8, SizeOfLinkedListStruckture)
CopyMemory(Buffer , *AktElement +8, SizeOfLinkedListStruckture)
FreeMemory(Buffer)
*Dummy = *FirstElement\Next ; \
*FirstElement\Next = *AktElement\Prev ; } Swap Next/Prev of First/Last Element
*AktElement\Prev = *Dummy ; /
*Dummy\Next = *AktElement ; Set Next-Pointer of the now next-to-last Element to the last Element
*AktElement\Prev = *FirstElement ; Set Prev-Pointer of the now 2nd Element to the first Element
ProcedureReturn Counter + 2
EndProcedure
Code: Alles auswählen
EnableExplicit
XIncludeFile #PB_Compiler_Home + "Includes\FlipLinkedList_Include.pbi"
NewList Numbers.POINT()
Define k, flipped
For k=1 To 10
AddElement(Numbers())
Numbers()\x = k
Next
ForEach Numbers()
Debug Numbers()\x
Next
flipped = FlipLinkedList(@Numbers(), SizeOf(POINT))
Debug ""
Debug Str(flipped) + " Elements flipped"
Debug ""
ForEach Numbers()
Debug Numbers()\x
Next
Gruß, PureLust.
