Difficulties when trying to sort a custom type array

[dco045]

Hi,

A you can see in enclosed file, I try to sort an array.
This array contains members (10 in my example but more in reality) each member is
type
'members
end type defined.

When I try to sort the array by the first member of the structure, the program crashes (see screenshots)

This appears either with interpreted or bundled version.

What's wrong ?

Regards,


Dany

[ErosOlmi]

In general Array Sort is not able to recognize array of UDT (User Defined Type) data type.
But it should not crash, just do a binary sort based of the binary data inside UDT element
In your example it should sort based on binary data strings composed by 10 bytes ("sName" string) + 4 bytes (binary representation of DWord "SValue") + 4 bytes (binary representation of Long "sCount")

I have to investigate why it crash

Thanks for reporting
Eros

[ErosOlmi]

I found the problem and solved.

But I do not like the solution I implemented because sorting an array of UDTs would require to:

make a copy of the memory allocated by the UDT
splitting into dynamic strings array
sorting array
putting back memory into the UDT


I'm searching a clever solution.
I asked into Power Basic compiler forum for some help:
https://forum.powerbasic.com/forum/user-to-user-discussions/programming/769317-sort-blocks-of-memory-of-unknown-size

[dco045]

In general Array Sort is not able to recognize array of UDT (User Defined Type) data type.
But it should not crash, just do a binary sort based of the binary data inside UDT element
In your example it should sort based on binary data strings composed by 10 bytes ("sName" string) + 4 bytes (binary representation of DWord "SValue") + 4 bytes (binary representation of Long "sCount")

I have to investigate why it crash

Thanks for reporting
Eros

Hi Eros,

This behaviour would fulfill my needs, because a previous check does not allow duplicate values in first field (string)

Regards



Dany

[ErosOlmi]

Please find attached thinCore.dll
Unzip it under the following folders:

\thinBasic\
\thinBasic\thinAir

replacing your current version

I've fixed array sort for user defined type arrays in the "slow and dirty" way I've described above

Let me know if it works

Ciao
Eros

[dco045]

Let me know if it works

Ciao
Eros

No more crash ! :cool:

It works, but :


Array Sort symbol_prg() ' empty strings first , then chars in ASCII order OK for ascending
Array Sort symbol_prg() , Descend ' give the same result. DESCEND seems to be ignored ?

I did not test asfiles option :lazy:

Non UDT array keeps sorted OK

Regards,



Dany

[ErosOlmi]

Reality is that thinBasic was not sorting at all fixed buffers (strings, UDT, ...)
So it is an area all to be constructed :oops:

I will add missing part asap ad post new Core to test.

Ciao
Eros

[primo]

now sorting array with a structure works without giving error in the newest thinbasic v 1.10.5
adapted from the above example:
we want to sort the first item in the structured array and of course we want to keep item 2 and item 3 attached to it as in the original
here 87 is still attached to 6 and 25 as before
9865

Uses "console"

Dim i As Long

Type template
sName As Long
SValue As Word
sCount As Long
End Type


Dim symbol(10) As template


symbol(1).sName = 22 symbol(1).SValue = 1 symbol(1).sCount = Rnd(1,1000)
symbol(2).sName = 18 symbol(2).SValue = 2 symbol(2).sCount = Rnd(1,1000)
symbol(3).sName = 2 symbol(3).SValue = 3 symbol(3).sCount = Rnd(1,1000)
symbol(4).sName = 6 symbol(4).SValue = 4 symbol(4).sCount = Rnd(1,1000)
symbol(5).sName = 9 symbol(5).SValue = 5 symbol(5).sCount = Rnd(1,1000)
symbol(6).sName = 87 symbol(6).SValue = 6 symbol(6).sCount = Rnd(1,1000)
symbol(7).sName = 54 symbol(7).SValue = 7 symbol(7).sCount = Rnd(1,1000)
symbol(8).sName = 33 symbol(8).SValue = 8 symbol(8).sCount = Rnd(1,1000)
symbol(9).sName = 4 symbol(9).SValue = 9 symbol(9).sCount = Rnd(1,1000)
symbol(10).sName = 5 symbol(10).SValue = 10 symbol(10).sCount = Rnd(1,1000)


PrintL "============ before sorting"

For i = 1 To 10
PrintL symbol(i).sName ," " , symbol(i).SValue ," " , symbol(i).sCount
Next i


Array Sort symbol, DESCEND 'ASCEND

PrintL "============ after sorting"

For i = 1 To 10
PrintL symbol(i).sName ," " , symbol(i).SValue ," " , symbol(i).sCount
Next i


Print $CRLF&"end."
WaitKey (60)


note that in Purebasic we can choose the item from the structure to sort and it is not obligatory to choose the first item of the structure, not sure if this is possible with thinbasic or Powerbasic
here we sort the structures array using its second item

Structure base
Name.l
value.l
EndStructure

Dim something.base(10)

Debug "---------- before descending sorting : --------"
For i=1 To 10
something(i)\Name.l = i
something(i)\value = Random(100, 1)
Debug Str(something(i)\Name.l)+" -- " + Str(something(i)\value)
Next

SortStructuredArray(something(), 0, OffsetOf(base\value), TypeOf(base\value))

Debug "---------- after sorting : --------"
For k=1 To 10
Debug Str(something(k)\Name.l) + " -- " + Str(something(k)\value)
Next



9866

as a side note: Just now i have found that we can write commands in thinbasic separated with space and without separating it with : as usual


Uses "Console"

Printl "Hello World 1" PrintL "Hello World 2" PrintL "Hello World 3"
PrintL
PrintL "Press a key to end program"

'---Wait for a key press
WaitKey

[Petr Schreiber]

Hi Primo,

sorting by specified UDT member would be great - and I think the syntax could be even simpler than in PureBasic, because ThinBASIC is able to determine TypeOf the element.

Looking at your code, I think you could make your life more comfy by having routines to fill and print your data.
See this tweaked version:


Uses "console"

Dim i As Long

Type template
' -- Data
sName As Long
SValue As Word
sCount As Long

' -- Functions

' Fills in all the values at once!
function init(sName as long, sValue as word, sCount as long)
me.sName = sName
me.sValue = sValue
me.sCount = sCount
end function

' Represents type as string
function to_string() as string
return strformat$("{1}{2}{3}{4}{5}", me.sName, $TAB, me.sValue, $TAB, me.sCount)
end function
End Type

Dim symbol(10) As template


'sName, sValue, sCount
symbol(1).init( 22, 1, Rnd(1,1000))
symbol(2).init( 18, 2, Rnd(1,1000))
symbol(3).init( 2, 3, Rnd(1,1000))
symbol(4).init( 6, 4, Rnd(1,1000))
symbol(5).init( 9, 5, Rnd(1,1000))
symbol(6).init( 87, 6, Rnd(1,1000))
symbol(7).init( 54, 7, Rnd(1,1000))
symbol(8).init( 33, 8, Rnd(1,1000))
symbol(9).init( 4, 9, Rnd(1,1000))
symbol(10).init( 5, 10, Rnd(1,1000))


PrintL "============ before sorting"

For i = 1 To 10
PrintL symbol(i).to_string()
Next ' <- no need to specify variable with next


Array Sort symbol, DESCEND 'ASCEND

PrintL "============ after sorting"

For i = 1 To 10
PrintL symbol(i).to_string()
Next

printl
printl "end."


WaitKey (60)

[John Spikowski]

FWIW

Script BASIC Array Sort (http://www.scriptbasic.org/forum/index.php/topic,330.0.html)

[Petr Schreiber]

Eros,

what do you think about possible new syntax:


ARRAY SORT ArrayVariable([StartIndex]) [FOR nElements] [BY member][, COLLATE UCASE] [, {ASCEND | DESCEND}] [, ASFILES]


In case of Primo's example, he could do for example:


ARRAY SORT symbol BY SValue, DESCEND


I checked the Core SDK, thanks to ability to thinBasic_GetTokenName, it is possible to get the UDT member name, and then, based on lookup to internal structures, do the magic.
Let me know, if okay, I would be happy to enjoy a little PB session working on this :)


Petr

[primo]

Thanks Petr and John for the examples.
i don't know that we can add functions inside Type.. End Type . filling data in this way is concise and consumes less space and it looks neater.

[ErosOlmi]

FWIW

Script BASIC Array Sort (http://www.scriptbasic.org/forum/index.php/topic,330.0.html)

Have you read the request, John, and what we are talking about here?

You always mention Script Basic, and I'm happy to compare different languages and how different languages have solved the same problem.
But at least remain on the subject: your link is just a generic array sort and not a sort of an UDT by one of the UDT elements.

:onthequiet::onthequiet:

[ErosOlmi]

I have to find a general way to sort any UDT by any UDT field.
But so far I didn't find a way but ... quite close.

In the meantime you can develop your own script function and adapt it to your needs like in the following example.
See template_QSort function and change as needed. You just need to change 4 lines if you need to sort by another UDT field.



Uses "console"

Dim i As Long

Type template
' -- Data
sName As Long
SValue As Word
sCount As Long

' -- Functions

' Fills in all the values at once!
function init(sName as long, sValue as word, sCount as long)
me.sName = sName
me.sValue = sValue
me.sCount = sCount
end function

' Represents type as string
function to_string() as string
return strformat$("{1}{2}{3}{4}{5}", me.sName, $TAB, me.sValue, $TAB, me.sCount)
end function





End Type



function template_QSort(byref t1() as template, firstIndex as long, lastIndex as long)
local low as long
local high as long
local pivotValue as dword '<---Same type as the UDT element to sort by
local tTemp as template

low = firstIndex
high = lastIndex
pivotValue = T1((firstIndex + lastIndex) / 2).sValue '---Change .sValue to any UDT element

Repeat

While T1(low).sValue < pivotValue '---Change .sValue to any UDT element
low += 1
Wend

While T1(high).sValue > pivotValue '---Change .sValue to any UDT element
high -= 1
Wend

If low <= high then
'---SWAP
tTemp = T1(low)
T1(low) = T1(high)
T1(high) = tTemp
'---


low += 1
high -= 1
End If

Until low > high

If firstIndex < high then
template_QSort(T1, firstIndex, high)
EndIf

If low < lastIndex then
template_QSort(T1, low, lastIndex)
End If
End function






Dim symbol(10) As template


'sName, sValue, sCount
symbol(1).init( 22, 1, Rnd(1,1000))
symbol(2).init( 18, 2, Rnd(1,1000))
symbol(3).init( 2, 3, Rnd(1,1000))
symbol(4).init( 6, 4, Rnd(1,1000))
symbol(5).init( 9, 5, Rnd(1,1000))
symbol(6).init( 87, 6, Rnd(1,1000))
symbol(7).init( 54, 7, Rnd(1,1000))
symbol(8).init( 33, 8, Rnd(1,1000))
symbol(9).init( 4, 9, Rnd(1,1000))
symbol(10).init( 5, 10, Rnd(1,1000))


PrintL "============ before sorting"

For i = 1 To 10
PrintL symbol(i).to_string()
Next ' <- no need to specify variable with next


Array Sort symbol, DESCEND 'ASCEND

PrintL "============ after sorting"

For i = 1 To 10
PrintL symbol(i).to_string()
Next

'[breakpoint] Quick Sort
template_QSort(symbol, 1, ubound(symbol))
PrintL
printl "After Quick Sort by .sValue"
For i = 1 To 10
PrintL symbol(i).to_string()
Next


printl "end."


WaitKey (60)

[John Spikowski]

You always mention Script Basic, and I'm happy to compare different languages and how different languages have solved the same problem.
But at least remain on the subject: your link is just a generic array sort and not a sort of an UDT by one of the UDT elements.

Hi Eros,

The only reason for the SB reference was to show how an array can be sorted using BASIC code rather than depending on the language.

I will try to be more respectful of this being the thinBasic forum.

[ErosOlmi]

It is OK John.
Sorry but today I had a bad (working) day and I over reacted at first :oops:

[primo]

Thanks Eros, impressive solution, i have replaced in template_QSort() the sValue by the third member sCount as you said, and it sorted the structured array using the third member
9867
for the users: you need the latest alpha release 1.10.5.0

[ErosOlmi]

Eros,

what do you think about possible new syntax:


ARRAY SORT ArrayVariable([StartIndex]) [FOR nElements] [BY member][, COLLATE UCASE] [, {ASCEND | DESCEND}] [, ASFILES]


In case of Primo's example, he could do for example:


ARRAY SORT symbol BY SValue, DESCEND


I checked the Core SDK, thanks to ability to thinBasic_GetTokenName, it is possible to get the UDT member name, and then, based on lookup to internal structures, do the magic.
Let me know, if okay, I would be happy to enjoy a little PB session working on this :)


Petr

:D thanks Petr.
I think I have the master idea on how to do this but I need the time.

In the meantime I've posted a possible script solution that should not be so slow even with some thousands records to sort.

[ReneMiner]

My two cents for this:
I remember that i did such thing already to sort udts by their subelements when they were displayed in some table and the user clicked the header...

It was a bit of code because for speed reasons i used a separate sorting-function for every primitive type (byte, long, dword, single, double, string etc.) to sort.
Core-functions like UdtElement_Offset were my secret little helpers...
Anyway there was one thing that i had overseen and it caused me Errors: if the subelement to sort was an array itself, example foo(123).x(45)...
Dynamic subarrays were not implemented at this time but it would make a sense to sort them by countOf(foo(index).x) instead to complain an error.
Fixed subarrays i can not imagine how to sort - - - maybe peek$ and then sort it? Does it make sense?

Anyway, if using UI-module we could fill our data into some invisible listview-control and abuse its sorting-abilities - does it have them or do i confuse something here ? -
just have a column for every elements index...
;)

[John Spikowski]

Anyway, if using UI-module we could fill our data into some invisible listview-control and abuse its sorting-abilities - does it have them or do i confuse something here ? -
just have a column for every elements index...


Remember the Word Count Challange from the past?

I used the OS sort command line utility to do my sorting of lists. Cheating but it worked great.

Welcome back to the forum!

[ReneMiner]

Another thought:
If the subelement to sort is an udt...


Type tVec3d
X as Double
Y as Double
Z as Double
End Type

Type t3Dpoint
Pos as tVec3d
Color as Long
'... more ...
End Type

Dim myPoint(123) as t3dPoint



Lets say we would sort the points from left to right ( myPoint().pos.x) it would be a little tricky to use a standard sorting routine...

We could use the sorting-powers of dictionary-module, use the value to sort as dictionary-data, probably has to be formatted, like
String sData = Format(myPoint(index).Pos.x, "0.000000")
and the key for the dictionary-slot would be the actual varptr, also formatted to contain no null:
String sKey = Hex$(Varptr(myPoint(index)))

Fill a dictionary with myPoint().Pos.x, let it sort and then order the real array according to the dictionary-keys that hold all pointers in new order now...

Another, very flexible approach for numeric data to sort:

Create String-array like


String toSort(123) ' same number of elements
For i = 1 to CountOf(myPoint)
toSort(i) = Format$(myPoint(i).Pos.X, "#.######") & Memory_Get(varptr(myPoint(i)), SizeOf(myPoint))
...


• put the element-data to sort by in front, should be formatted to same length if numeric
• sort this string-array with regular array sort
• truncate the leading bytes of every string again
• make the string-array to become one string containing all data
• poke$ (memory_set) it at the varptr(myPoint(1))
• done

If subelement to sort by would be a String we had to fill the leading bytes with $Spc to have it all same length before we sort

[ReneMiner]

Ha, found it. Look there

http://www.thinbasic.com/community/showthread.php?12628-Array-Sort-once-more&p=92487&viewfull=1#post92487

Requires a tracefile. Hmmm, what was that?
Eros implemented a while ago some tracing-directive to test our thinbasic-scripts. It will tell us how many times a function was called and how much time was used to execute every function in order to optimize our script-code.