PureBoard

Verfasst: **03.08.2007 20:05**

Angeregt druch >diesen< Thread hab ich mal eine universell einsetzbare Routine geschrieben mit der man die Reihenfolge einer LinkedList umdrehen kann.
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

Und hier mal eine kleine Demonstration dazu:

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

Wenn's jemand gebrauchen kann oder Feedback dazu abgeben möchte: Comments are welcome.

Gruß, PureLust.

Verfasst: **04.08.2007 00:57**

Hi,

Code sieht super aus wird wohl auch so funktionieren, daher hab ich ihn mir mal kopiert und für künftige Projekte vorgemerkt.

Gruß
Scarabol

PureBoard

FlipLinkedList() - Umdrehen der Reihenfolge einer LinkedList

FlipLinkedList() - Umdrehen der Reihenfolge einer LinkedList