PureBasic Forums - English

http://www.purebasic.com
https://www.purebasic.fr/english/

ReverseList

https://www.purebasic.fr/english/viewtopic.php?t=85798

Page 1 of 1

ReverseList

Posted: Wed Nov 27, 2024 9:25 am
by AZJIO

Code: Select all

Procedure ReverseList(List lst.s())
	Protected a, z, i
	z = ListSize(lst())
; 	flag = z % 2
	flag = z & 1
	flag = (z - flag) / 2
	z - 1
	
	For i = 1 To flag
		SwapElements(lst() , SelectElement(lst(), a), SelectElement(lst(), z))
		a + 1
		z - 1
		; If a = z
		; 	Break
		; EndIf
	Next
EndProcedure

Define NewList NList.s()

For i = 1 To 15
	AddElement(NList())
	NList() = Str(i)
Next

ReverseList(NList())
ForEach NList()
	Debug NList()
Next
Edit

Code: Select all

; 	flag = z % 2
	flag = z & 1

Re: ReverseList

Posted: Wed Nov 27, 2024 9:35 am
by Quin
Clever, and it works! Thanks for sharing 8)

Re: ReverseList

Posted: Wed Nov 27, 2024 10:13 am
by Mr.L
Thank you, good Idea!
here is a version, that can handle any type of list (structured or not), and is much faster too (SelectElement is quite slow, if the List is very large).

Code: Select all

Macro ReverseList(list_)
	Define listIndex_ = ListSize(list_) - 1
	If listIndex_ > 0
		Define *relativeElement_ = LastElement(list_)
		If *relativeElement_
			While listIndex_ > 1 And FirstElement(list_)
				MoveElement(list_, #PB_List_Before, *relativeElement_)
				*relativeElement_ = @list_
				listIndex_ - 1
			Wend
			If LastElement(list_)
				MoveElement(list_, #PB_List_First)
			EndIf
		EndIf
	EndIf
EndMacro

Re: ReverseList

Posted: Wed Nov 27, 2024 10:44 am
by NicTheQuick
But the macro version has some side effects because it defines the variables `listIndex_` and `*relativeElement_` and `Define` also does not work as expected in Procedures. But if you know about these preconditions the macro of course is more versatile.

I didn't do a speed comparison though. I hope `MoveElement` and `SwapElement` are only pointer based operations where the content size of each element is negligible.

Re: ReverseList

Posted: Wed Nov 27, 2024 10:48 am
by HeX0R
What is the use case?
Why not:

Code: Select all

LastElement(NList())
Repeat
	Debug NList()
Until PreviousElement(NList()) = 0

Re: ReverseList

Posted: Wed Nov 27, 2024 10:53 am
by AZJIO

Code: Select all

Procedure ReverseList1(List lst.s())
	Protected a, z, i
	z = ListSize(lst())
	flag = z & 1
	flag = (z - flag) / 2
	z - 1
	
	For i = 1 To flag
		SwapElements(lst() , SelectElement(lst(), a), SelectElement(lst(), z))
		a + 1
		z - 1
	Next
EndProcedure

Procedure ReverseList2(List lst.s())
	Protected listIndex, *relativeElement
	listIndex = ListSize(lst()) - 1
	If listIndex > 0
		*relativeElement = LastElement(lst())
		If *relativeElement
			While listIndex > 1 And FirstElement(lst())
				MoveElement(lst(), #PB_List_Before, *relativeElement)
				*relativeElement = @lst()
				listIndex - 1
			Wend
			If LastElement(lst())
				MoveElement(lst(), #PB_List_First)
			EndIf
		EndIf
	EndIf
EndProcedure


Define NewList NList.s()

For i = 1 To 10000
	AddElement(NList())
	NList() = Str(i)
Next

StartTime = ElapsedMilliseconds()
ReverseList1(NList())
Debug ElapsedMilliseconds() - StartTime

StartTime = ElapsedMilliseconds()
ReverseList2(NList())
Debug ElapsedMilliseconds() - StartTime

Re: ReverseList

Posted: Wed Nov 27, 2024 11:15 am
by NicTheQuick
@AZJIO You don't use the debugger to make such speed comparisons.

But obviously the `SelectElement()` version should be slower because `SelectElement()` needs a certain amount of time to find the element at the given index.

Re: ReverseList

Posted: Wed Nov 27, 2024 11:16 am
by NicTheQuick
I tried it like this:

Code: Select all

Define NewList NList.s()

For i = 1 To 1000000
	AddElement(NList())
	NList() = Str(i)
Next

speeds.s = ""

StartTime = ElapsedMilliseconds()
ReverseList1(NList())
speeds + "1: " + Str(ElapsedMilliseconds() - StartTime) + ~" ms\n"

StartTime = ElapsedMilliseconds()
ReverseList2(NList())
speeds + "2: " + Str(ElapsedMilliseconds() - StartTime) + " ms"

MessageRequester("Speeds", speeds)
And the result is quite clear:
1: 195509 ms
2: 6 ms

Re: ReverseList

Posted: Wed Nov 27, 2024 12:44 pm
by breeze4me
Another variation of the macro version.

Code: Select all

EnableExplicit

Macro ReverseList(_list_)
  
  CompilerIf #PB_Compiler_Procedure = ""
    Define _listidx_#MacroExpandedCount, _prevElement1_#MacroExpandedCount, _prevElement2_#MacroExpandedCount, _mid_#MacroExpandedCount, _listsz_#MacroExpandedCount= ListSize(_list_)
  CompilerElse
    Protected _listidx_#MacroExpandedCount, _prevElement1_#MacroExpandedCount, _prevElement2_#MacroExpandedCount, _mid_#MacroExpandedCount, _listsz_#MacroExpandedCount = ListSize(_list_)
  CompilerEndIf
  
  If _listsz_#MacroExpandedCount > 1
    _mid_#MacroExpandedCount = (_listsz_#MacroExpandedCount - 2) / 2
    
    _prevElement1_#MacroExpandedCount = FirstElement(_list_)
    MoveElement(_list_, #PB_List_Last)
    
    _prevElement2_#MacroExpandedCount = PreviousElement(_list_)
    MoveElement(_list_, #PB_List_First)
    
    For _listidx_#MacroExpandedCount = 1 To _mid_#MacroExpandedCount
      
      ;If NextElement(_list_) = 0 : Break : EndIf
      NextElement(_list_)
      MoveElement(_list_, #PB_List_Before, _prevElement1_#MacroExpandedCount)
      _prevElement1_#MacroExpandedCount = @_list_
      
      ;If PreviousElement(_list_) = 0 : Break : EndIf
      PreviousElement(_list_)
      MoveElement(_list_, #PB_List_After, _prevElement2_#MacroExpandedCount)
      _prevElement2_#MacroExpandedCount = @_list_
      
    Next
    
  EndIf
  
EndMacro


Procedure x()
  Protected NewList NList1.s()
  Protected NewList NList2.i()
  Protected NewList NList3.i()
  Protected i
  
  Debug "In Procedure"
  For i = 1 To 11
    AddElement(NList1())
    NList1() = Str(i)
  Next
  
  ReverseList(NList1())
  
  ForEach NList1()
    Debug NList1()
  Next
  
  Debug "----------------------"
  
  For i = 1 To 4
    AddElement(NList2())
    NList2() = i
  Next
  
  ReverseList(NList2())
  
  ForEach NList2()
    Debug NList2()
  Next
  
  Debug "----------------------"
  
  For i = 1 To 2
    AddElement(NList3())
    NList3() = i
  Next
  
  ReverseList(NList3())
  
  ForEach NList3()
    Debug NList3()
  Next
  
EndProcedure



NewList NList1.s()
NewList NList2.i()
NewList NList3.i()
Define i

Debug "Main"

For i = 1 To 11
	AddElement(NList1())
	NList1() = Str(i)
Next

ReverseList(NList1())

ForEach NList1()
  Debug NList1()
Next

Debug "----------------------"

For i = 1 To 4
	AddElement(NList2())
	NList2() = i
Next

ReverseList(NList2())

ForEach NList2()
  Debug NList2()
Next

Debug "----------------------"

For i = 1 To 2
	AddElement(NList3())
	NList3() = i
Next

ReverseList(NList3())

ForEach NList3()
  Debug NList3()
Next

Debug "----------------------"

x()
A version that reuses variables that have already been defined. (Using a 'While' loop makes it a bit faster.)

Code: Select all

Macro ReverseList(_list_)
  CompilerIf #PB_Compiler_Procedure = ""
    CompilerIf Not Defined(_listsz_, #PB_Variable)
      Define _prevElement1_, _prevElement2_, _listsz_
    CompilerEndIf
  CompilerElse
    CompilerIf Not Defined(_listsz_, #PB_Variable)
      Protected _prevElement1_, _prevElement2_, _listsz_
    CompilerEndIf
  CompilerEndIf
  
  _listsz_= ListSize(_list_)
  If _listsz_ > 1
    _listsz_ = (_listsz_ - 2) / 2
    
    _prevElement1_ = FirstElement(_list_)
    MoveElement(_list_, #PB_List_Last)
    
    _prevElement2_ = PreviousElement(_list_)
    MoveElement(_list_, #PB_List_First)
    
    While _listsz_ > 0
      NextElement(_list_)
      MoveElement(_list_, #PB_List_Before, _prevElement1_)
      _prevElement1_ = @_list_
      
      PreviousElement(_list_)
      MoveElement(_list_, #PB_List_After, _prevElement2_)
      _prevElement2_ = @_list_
      
      _listsz_ - 1
    Wend
  EndIf
EndMacro
Edit:
A faster way.

Code: Select all

EnableExplicit

Macro ReverseList(_list_)
  CompilerIf #PB_Compiler_Procedure = ""
    CompilerIf Not Defined(_listsz_, #PB_Variable)
      Define _listsz_, _prevElement1_, _prevElement2_, _prevElement3_, _prevElement4_
    CompilerEndIf
  CompilerElse
    CompilerIf Not Defined(_listsz_, #PB_Variable)
      Protected _listsz_, _prevElement1_, _prevElement2_, _prevElement3_, _prevElement4_
    CompilerEndIf
  CompilerEndIf
  
  _listsz_= ListSize(_list_)
  If _listsz_ > 1
    _listsz_ = _listsz_ / 2
    
    _prevElement1_ = FirstElement(_list_)
    _prevElement2_ = NextElement(_list_)
    
    _prevElement4_ = LastElement(_list_)
    _prevElement3_ = PreviousElement(_list_)
    
    While _listsz_ > 0
      SwapElements(_list_, _prevElement1_, _prevElement4_)
      
      ChangeCurrentElement(_list_, _prevElement2_)
      _prevElement1_ = _prevElement2_
      _prevElement2_ = NextElement(_list_)
      
      ChangeCurrentElement(_list_, _prevElement3_)
      _prevElement4_ = _prevElement3_
      _prevElement3_ = PreviousElement(_list_)
      
      _listsz_ - 1
    Wend
  EndIf
EndMacro


Macro loop(_max_)
  NewList NList#_max_#.i()
  
  For i = 1 To _max_
    AddElement(NList#_max_#())
    NList#_max_#() = i
  Next
  
  ReverseList(NList#_max_#())
  
  ForEach NList#_max_#()
    Debug NList#_max_#()
  Next
  
  Debug "----------------------"
EndMacro

Procedure x()
  Protected i
  
  Debug "In Procedure"
  
  loop(1)
  loop(2)
  loop(3)
  loop(4)
  loop(5)
  loop(6)
  loop(7)
  loop(8)
  loop(9)
  loop(10)
  loop(11)
  loop(11)
  
EndProcedure

Define i
Debug "Main"

loop(1)
loop(2)
loop(3)
loop(4)
loop(5)
loop(6)
loop(7)
loop(8)
loop(9)
loop(10)
loop(11)

x()

Re: ReverseList

Posted: Wed Nov 27, 2024 1:30 pm
by BarryG
HeX0R's version works great. :)

Also, if you don't mind prefixing the list numbers with a zero, then you can do it as simply as this:

Code: Select all

Define NewList NList.s()

For i = 1 To 15
  AddElement(NList())
  NList() = RSet(Str(i),2,"0")
Next

SortList(NList(),#PB_Sort_Descending)

ForEach NList()
  Debug NList()
Next

Re: ReverseList

Posted: Wed Nov 27, 2024 3:40 pm
by AZJIO
BarryG wrote: Wed Nov 27, 2024 1:30 pm

Code: Select all

SortList(NList(),#PB_Sort_Descending)
Numbers are only for checking collisions at the beginning, at the end and in the middle.
The version from HeX0R is really too simple and there is no need to do a reversion, even if the loop is used several times. The help file also says that this allows you to use it to loop in reverse order

The fact is that when creating drawings on the canvas, they can overlap each other, so the order is important when adding, saving, dragging and redrawing.
All times are UTC+01:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited