Sort multidimensional array

[stam]

Hi Richard,
i get the sense that you're alluding to some point about order of array elements, but i'm not sure i see it.
I see your point about the keys - but the fact is they are reordered by number, just not position. It real terms, iterating through the array with a numeric index, accessing any of the elements or displaying the array in any kind of interface item will show them in the desired order.

I used the example stack i posted above to add your code, but also display the source and destination arrays. The screenshot illustrates this as well as the actual output in the message box - which does illustrate your point i think, but this remains a correctly keyed numerically index 'array' i think? Ordered correctly by an index which can produce a rank anyway.

As to the actual sequence of the keys, how could it be otherwise with a dictionary? There isn't really an 'array' entity in LC - this would be a dictionary or hash table in most other languages i think, so the actual order isn't relevant, just the numeric index. However LC blurs the lines so much that the two are used synonymously - and in LC it's mostly an irrelevant distinction?

[SparkOut]

I think you have gathered, what I think Richard was trying to draw attention to:

that "arrays" in LiveCode are hash tables and have no internal ordering, even if the keys are numeric. There is no "first" or "last" element of a LiveCode array. (No "push" and "pop" equivalent). The only way LiveCode arrays can be ordered is by imposing a sort on the keys, then iterating that sorted list of keys to access each in turn.

[stam]

I think you have gathered, what I think Richard was trying to draw attention to

No i get that - just not sure why it's being raised as a discussion point.

If there were true arrays in LC we wouldn't need this rigamarole

[FourthWorld]

I think you have gathered, what I think Richard was trying to draw attention to

No i get that - just not sure why it's being raised as a discussion point.

If there were true arrays in LC we wouldn't need this rigamarole

One person's "ragamarole" is another person's "learning". This thread has taught me much. I can't recall a day in the 30 years I've been working with computers where I didn't learn something new. Along the way I try to pass along some of what I've learned, some days more successfully than others.

There are many types of data structures in computing, arrays among them. Arrays are most commonly found in two forms: associative and indexed. Where data structures differ doesn't mean some of them are wrong, it just means they're different. The key to using any data structure well is to understand its nature.

You likely know the details provided in this reply, but future readers who will come across this thread when learning about arrays may not. And while we don't really need to know the deep underpinnings, a passing familiarity helps us understand some important essentials for working with arrays. Feel free to skip this post if it seems wordy or uninteresting. I'm writing mostly for future readers who, like so many others over the years, will have questions about how to work with arrays in LiveCode powerfully.


Associative arrays are an immensely flexible and efficient tool for associating a label with a value. The label can be any string from 1 to 255 characters long, and the value can be just about any data, whether text, binary, or even another array. The range of uses for this structure are vast, which is why so many languages support associative arrays (going forward I'll refer to them as simply "arrays", since they're the type LC Script currently offers).

The thing that makes them so efficient for such a broad range of tasks is the very thing that often leads to confusion where their nature is not understood. They're a collection of virtual buckets, in which each contains pointers to disparate memory locations. A label is assigned to a given bucket by a hash algorithm, allowing a fairly small number of name-address lookups to be stored in a way that affords rapid access. The Wikipedia page I linked to early in this discussion covers this in more satisfying depth.

The biggest takeway is that an array isn't a contiguous bytestream, which explains why an array can't be sorted, nor even displayed, transported or stored.

That awareness leads us to understanding how the posts in this thread come together:

If we ask "How can an array be sorted?", with the awareness of an array's essential nature we might also wonder "How can an array even be displayed?"

And it turns out answer for both is the same: the code used within the UI display mechanism we've chosen.

LC provides two UI options for displaying data from an array: the Tree widget and the DataGrid.

Both walk through the elements of an array, extracting strings as they go, rendering them on screen. And both include options for sorting the rendered strings.

Neither displays an array directly, because it can't.

So when we see UI element displaying array contents, it's useful to keep in mind that what we're seeing are strings copied from parts the array, and not the array itself. And with that in mind we can appreciate that any sorting we see in a UI control is a feature of that UI control, operating only on its string copies.

This awareness helps our work in many ways:
- It helps us understand how to use the control.
- It invites us to explore the options provided by the control for sorting its string copies.
- It empowers us to craft a nearly infinite variety of custom controls for displaying array contents in any way we might need or want.
- It makes is better equipped to work with arrays in contexts outside of merely displaying them to the user.

And perhaps equally important:
- It helps us anticipate solutions where simple delimited strings may be a better fit.

No single data structure is best in all cases. Knowing the nature of each lets us choose with confidence.

This thread is a good example:

The post that started this was from someone who obtained data from an SQL query and wanted to display it in a sorted list. The only issue he had looks like a simple syntax error, likely easily fixed.

But now, with all we've covered in this thread, we might also ask another question: why is this being done in an array?

To do what the OP requested requires:
1. Call revDBQuery
2. Write a handler to convert the resulting delimited text to an array
3. Find a handler in the forums to prepend that array with an outer array of sequential integers according to a sort order
4. Use the resulting compounded array to populate the DataGrid using its array option

Or we could:
1. Call revDBQuery
2. Put the result in a field

If we need a DataGrid we can replaced #2 there with "populate the DataGrid using its text option".

This is why so many of my replies in this forum ask what the goal is. Until the OP returns to answer that, the range of possibilities afforded by LC's rich language are too vast to know the best answer for the task at hand.

As we learn our tools ever better, we can pick the best tool for the job we're facing.

Arrays are great.
Chunk expressions are great.
LiveCode is great.

Enjoy it all.

[bwmilby]

For other readers, I attach an example - arrays shown with tree view widgets, unfortunately I haven't figured out how to expand all in script so needs to be done manually (set the foldState doesn't seem to work... if you know how to expand all branches of the tree view in script do let me know!).

FoldState is an array. Easiest way to play with it is to get an array expanded like you want and then pull a copy of the foldState to examine it. Everything not listed in the array is assumed collapsed. If listed, it can be either.

[stam]

FoldState is an array. Easiest way to play with it is to get an array expanded like you want and then pull a copy of the foldState to examine it. Everything not listed in the array is assumed collapsed. If listed, it can be either.

Thanks Brian, very helpful tip - finally made sense when examining the foldState array.
Also explains why 'set foldState to false' collapses all, but setting it to true does nothing.

[bobcole]

Brian:
Yes, thank you for the tip about FoldState; I didn’t know that about Tree View widgets. That tip provides a place to start investigating the tree view display.

Richard:
Thank you for the detailed explanation of arrays! Your clear exposition puts under-the-hood details in perspective. I may have sort of know that arrays were internal to the system (pointers, hash algorithm, etc.), seeing your discussion of the two visual tools (tree views, and data grids) raises the veil of mystery that has always clouded my understanding of how to see the values in arrays. Thank you for taking the time to produce this excellent educational lesson.

I’ll pass on one tidbit that has helped me over the years. I think of arrays in terms of rows (r) and columns (c):

This is a multidimensional array - myArray[r][c]
This is a one dimensional array - myArray[r,c]

Both work in repeat loops but, so far in my scripts, I have found it easier to visualize and work with arrays in the second form.
Now, I need to spend more time with tree views and data grids.
Thanks to all for this thread.
Bob

[Thierry]

Thanks Brian, very helpful tip - finally made sense when examining the foldState array.

+1

As I wasn't aware of this widget property, I did play a bit with it,
and here is an interesting screenshot of a tree view widget on the left,
and the details of foldState in the debugger...
Be aware of extra information compared to original data:

view foldState in debugger.

Kind regards,

Thierry

[FourthWorld]

Richard:
Thank you for the detailed explanation of arrays! Your clear exposition puts under-the-hood details in perspective. I may have sort of know that arrays were internal to the system (pointers, hash algorithm, etc.), seeing your discussion of the two visual tools (tree views, and data grids) raises the veil of mystery that has always clouded my understanding of how to see the values in arrays. Thank you for taking the time to produce this excellent educational lesson.

Thank you for you kind words, Bob. It's encouraging to hear when something I write is useful.

I’ll pass on one tidbit that has helped me over the years. I think of arrays in terms of rows (r) and columns (c):

This is a multidimensional array - myArray[r][c]
This is a one dimensional array - myArray[r,c]

I sometimes use that form myself. It's actually a single-dimensional array, but with a key string that lends itself to being parsed easily for certain operations. Oddly enough, it's the form preferred by LC's built-in matrixMultply function.

I find delimited keys can sometimes perform better than deeply-nested arrays. Not enough to worry about; the best form is the one that best fits the conceptual model for the task at hand. But at least it reminds us that the bucket hash algo, efficient as it is, carries a non-zero cost.

[stam]

I’ll pass on one tidbit that has helped me over the years. I think of arrays in terms of rows (r) and columns (c):

This is a multidimensional array - myArray[r][c]
This is a one dimensional array - myArray[r,c]

I sometimes use that form myself. It's actually a single-dimensional array, but with a key string that lends itself to being parsed easily for certain operations. Oddly enough, it's the form preferred by LC's built-in matrixMultply function.

I find delimited keys can sometimes perform better than deeply-nested arrays. Not enough to worry about; the best form is the one that best fits the conceptual model for the task at hand. But at least it reminds us that the bucket hash algo, efficient as it is, carries a non-zero cost.

Genius It never crossed my mind to use a list as a key - this is definitely one to keep in mind, as there will be situations to use this!

I continue to be amazed by the depth and nuances of LiveCode and have huge appreciation for people like Richard, Klaus, Thierry, Bob and so many others that put so much hard work into both maintaining a very polite and helpful forum and who very clearly dedicate a large amount of time and effort to this.

It's yet another example of the conveniences of the language which just adds to that intangible LiveCode magic (mind you i'm still so impressed by simple things like [each] - iterating this way in other languages is so much more cumbersome...) Why aren't more people using LiveCode

[bwmilby]

Another tidbit about the tree widget is that a feature has been added to facilitate manual sort. You can specify a number of characters to trim from the beginning of the key on display. This allows you to pre-pend a sort key before the display key. (i.e. 00-First key, 01-Second key, ... where 3 characters would be trimmed)

It is kind of a hack implementation, but was the way to get the feature with the least amount of churn to the internal code of the widget. It also preserved the ability to just display any array.

I can envision a future version of the widget that would make a complete change where the array itself was a custom design and included fold state, font specs, custom icon on a node basis (inherited even). Imagine being able to have level 1 at a larger font size than level 2 (of course that does make calculations more complicated since you lose the constant height for each row). But then again, I think Trevor already implemented something that can probably do most of that anyway (DataGrid and the newer dataview_tree)

[laouris]

Guys, in the attached example I have tried all three algorithms posted above and couldn't make anyone work. I would appreciate editing the attached re-posting it if you can make any one of the three algorithms work. Just uncomment the CALL of the algorithm you wish to try out
--put sortArray(ClusterArray, "ascending", "numeric", ClusterArray["Idea_ID"]) into mySortedArray
--put sortArray_tdz(ClusterArray, "ascending", "numeric", ClusterArray["Idea_ID"]) into mySortedArray
--put sortArray2(ClusterArray, ClusterArray["Idea_ID"]) into mySortedArray

[stam]

Guys, in the attached example I have tried all three algorithms posted above and couldn't make anyone work. I would appreciate editing the attached re-posting it if you can make any one of the three algorithms work. Just uncomment the CALL of the algorithm you wish to try out
--put sortArray(ClusterArray, "ascending", "numeric", ClusterArray["Idea_ID"]) into mySortedArray
--put sortArray_tdz(ClusterArray, "ascending", "numeric", ClusterArray["Idea_ID"]) into mySortedArray
--put sortArray2(ClusterArray, ClusterArray["Idea_ID"]) into mySortedArray

Hi laouris,

sorting works... if you call it properly
My algorithm for generic sorting of both 1- and multidimensional arrays (a version of which is included in your script) is:

Code: Select all

function sortArray pArray, pDirection, pSortType, pKey, pUseSystemDate
   # PURPOSE : Returns a numerical indexed array with with the sort order requested. See notes below.
   /*
   - only pArray is mandatory, other params can be passed as ‘empty’ or “”
   - permissible values for pDirection are: ascending, descending or empty
   - permissible values for pSortType are: international, numeric, datetime, text, binary or empty
   - if pDirection is passed as “” or ‘empty’, it will default to ascending
   - if pSortType is passed as “” or ‘empty’ it will default to text
   - passing pKey as “” or empty will treat the array as a 1-dimensional array, passing the name of the key will sort it as a multidimensional array
   - passing empty pUseSystemDate will default to false / / US date format
   */
   local tNextIndex, tSortedArray, tSortText
   get the keys of pArray
   if pUseSystemDate is not empty then set the useSystemDate to pUseSystemDate
   put "sort lines of it [[pDirection]] [[pSortType]] by pArray[each]" into tSortText //1-dimensional array
   if pKey is not empty then put "[pKey]" after tSortText //multidimensional array
   do merge(tSortText)
   repeat for each line tKey in it
      add 1 to tNextIndex
      put pArray[tKey] into tSortedArray[tNextIndex]
   end repeat
   return tSortedArray
end sortArray

Please note however that pKey is the name of the key, not the key itself, ie instead of passing the parameter as ClusterArray["Idea_ID"] you should pass it as "Idea_ID", (and in any case, the actual key would have been ClusterArray[x]["idea_ID"], so what you had there was an empty value - the do merge(tSortText) statement is used to convert the text string to a variable ).

In other words the call is:

Code: Select all

 put sortArray(ClusterArray, "ascending", "numeric", "Idea_ID") into mySortedArray

You may get some interference from the inherent data grid sorting as well - to reset this to unsorted:

Code: Select all

set the dgProps["sort by column"] of group "ClustersDataGrid" to empty

To always prevent sorting on clicking on the column headers, add this to the data grid script:

Code: Select all

on SortDataGridColumn pColumn
   -- catches any attempt at sorting/changing header appearance
end SortDataGridColumn

Or instead you can just use the data grid methods for sorting...

Hope that helps,
Stam