Questions on the dynamic array sort

[Candy M.]

I'm in the process of implementing the dynamic array sort.

Currently in our applications we have what we call a browse list that is populated by a QBF.   All the records are selected and sorted and placed in
an array.   We show the browse list in a display array, which the user can navigate.   If the user chooses to sort the list (by clicking on a column), then we examine the dom tree for sortType and sortColumn to see how it was sorted and then will sort the program array by the column that was chosen after the display array is exited.   The user can still navigate through the list in forward/backward buttons in the navigation section of the toolbar, so we need the program array to be pretty close to the visual order.

So, I'm thinking that we can use the ON SORT trigger and when a column is clicked, then sort the program array use the dynamic array sort by what was chosen visually.

1) If I sort the program array within the DISPLAY ARRAY, will that be okay?   If not, I could exit DISPLAY ARRAY and just re-enter it
2) If a subsequent column is chosen to be sorted, is the ordering kept in the visual sort? And is the ordering kept in the dynamic array sort when I call that in the ON SORT trigger.  Is the sort "stable" (see https://en.wikipedia.org/wiki/Sorting_algorithm)?   I see that subsequent calls to the dynamic array sort are cumulative and I'm want to see if the user keeps clicking columns to sort and then a dynamic array sort is performed, the visible order and program array order will be close to being in sync.

Thanks, hope that made sense.

Candy

[Reuben B.]

Candy,

I think what you really want to be using is the methods that map between the visual and actual order of the array ...

http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/c_fgl_ClassDialog_visualToArrayIndex.html
http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/c_fgl_ClassDialog_arrayToVisualIndex.html

... using those then you don't need to do all the extra sort steps you are attempting, and can keep the 4gl array as it is.

For education purposes, you should also be aware of  some of the comments in http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/c_fgl_dialog_ON_SORT.html and are aware of the difference in the ON SORT block between a non-paged and paged DISPLAY ARRAY.  In a non-paged array you should only be doing post-sort tasks in the ON SORT block, the sort has been done, whilst in a paged array you are responsible for the sort.

Also with regards your comment "then we examine the dom tree for sortType and sortColumn", that information is available in ui.Dialog methods
http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/c_fgl_ClassDialog_getSortKey.html
http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/c_fgl_ClassDialog_isSortReverse.html

Finally with regards sort being stable, when using built-in sort, ties are broken by the index value of the array.  When using the arr.sort method, ties are broken by the current order, no record is kept of the original array order i.e you can't do the equivalent of 'Reset to Default'.  So to mimic the built-in sort, you would need to add an additional array member containing the original sort index, and always call the .sort method first on that column before calling the .sort method for the desired column.

Reuben

[Candy M.]

Thanks Reuben.

We do need to do the sort as the user can close the form and still scroll through the program array using buttons in the navigation part of the toolbar.   So there is no longer a link to the dialog since it has been closed.

We have programmed a sort and have been using it for several years but it is too slow.   We would actually like to have the dynamic sort back ported to version 2.50 as it
is much faster than ours, but support said that probably would not happen.

I think I understand your last paragraph.

For a sort to be "stable", the relative order of items with equal keys remain unchanged by the sorting process.  So is the dynamic array sort stable?

Thanks,
Candy

Candy

[Reuben B.]

We do need to do the sort as the user can close the form and still scroll through the program array using buttons in the navigation part of the toolbar.   So there is no longer a link to the dialog since it has been closed.

you can always use the methods that map the visual and actual order to make a copy of the mapping as you exit the array

Code (genero) Select Expand


CALL map_v2a.clear()
CALL map_a2v.clear()
FOR i = 1 TO arr.getLength()
   LET map_v2a[i] = DIALOG.visualToArrayIndex("scr", i)
   LET map_a2v[i] = DIALOG.arrayToVisualIndex("scr",i)
END FOR

and then either reference that or use that as the basis for your sort.  You could even store the result above in a phantom column and use the .sort() method on the phantom column.

So is the dynamic array sort stable?

If it wasn't then

Code (genero) Select Expand

CALL a.sort("C",false)
CALL a.sort("B",false)
CALL a.sort("A",false)

wouldn't be the equivalent of ORDER BY a,b,c

Reuben

[Rene S.]

Hello,
quick answer: yes, the sort algorithm is stable: if two or more elements are equal (according to the compare) then the original order remains.

Example: an array of person is sorted by name. When sorting by gender, then any group remains sorted by name. How it's done?  We are using the qsort algorithm. qsort calls a comparator function. This function compares two elements, returns -1 for less than, 0 for equal, 1 for greater than. Our implementation of the comparator never returns 0: if two elements are equal, then the difference of the original index will be returned. More literally: a "ORDER BY criteria" behaves like "ORDER BY index, criteria"  where index is the array index before sorting.

Rene

[Sebastien F.]

Candy,

Just a thought:

Did you consider to re-fill the program array in the expected order, by re-executing the SQL query with an ORDER BY based on the sort columns?

Is that too slow compared to your original sorting code?

Seb

[Rene S.]

Replace this

a "ORDER BY criteria" behaves like "ORDER BY index, criteria"  where index is the array index before sorting.

by
a "ORDER BY criteria" behaves like "ORDER BY criteria, index"  where index is the array index before sorting.

[Candy M.]

Thank you Rene, that is the answer I was looking for.

Sebastien, our sort will sort according to what the user chooses.   It would be probably be easier for me to program another sort rather that execute the SQL, plus some of the elements of the array could be calculated values.   We use this sort in several places in our code.

Further questions:
1)  Is it ok to call the sort while in the display array in the ON SORT clause?
2)  Should I be storing the array index in the array and then sort by the index if the user does Reset Sort Order?
3)  Could you possibly port it to 2.50?  The current versions we are maintaining are 2.50, 3.00, and 3.10.   We are upgrading customers to 3.10 as they get new servers but we still have customers on Centos 5 so the highest version they can go is 2.50.   I only ask since the sort first appeared in 2.51.   I'm not sure what 2.51 is as we don't even see it on our download product page.   I'll need to use pre-processor in order to move forward with the new sort to take account of the different versions.

Thanks for everyone's help.
Candy 

[Keith Y.]

Hello Candy,

This may not be what you are looking for but here is how we implemented screen/internal sorting for result sets.

NOTE: This is being done under 3.00 so may not be helpful for your 2.50 implementations? 

Our company also uses a QBF and results set (internal array) that our users wanted to have the sort match what they were doing in the results screen.   They wanted the Next/Previous functions to match how the results screen was sorted when they returned from the results screen.

A few things we came across when doing the implementation.
1. The ON SORT is called first thing before any action is taken from user.   This is handy as you can grab the "personal" sort setting the user has for the result screen.  We use this later to match the internal array to the user's specific setting so the first time user displays results we can sort the internal array to match their personal sort setting.
2.  We found doing array.sort() in the ON SORT gave very strange results as the internal array is not attached to the "screen" array.    The "screen" array is not cumulative and is "reset" to beginning each time user selects a new field to sort by.   Doing the array.sort() each time user changed sort field really caused strange results.   Also when the user reset sort fields to "defaults" there was no way to detect that and reset the internal array.
3.  Our internal array index did not keep up well with the screen index so user did not "always" get the result they were expecting doing NEXT/PREVIOUS.
4.  We found that the user could sort the results screen by several fields but it only had to match  the internal array at the point user "selected" a row.   So we only sort our internal array to match the screen array when a user makes a selection.   This eliminates doing the internal sort until and if it is really needed.

We tried a few different attempts and came up with the code below.  This implementation is not cumulative but it does keep the user results sort the same as the internal array.

This is a stripped down version with only the pieces needed to have the internal array match the results screen.

################################################################################
FUNCTION do_pick_list()
################################################################################
DEFINE
    lv_sort_key           STRING,
    lv_issort                INTEGER
#
    DISPLAY ARRAY ga_results TO tbl_results.*
        ATTRIBUTE (UNBUFFERED)
#
        BEFORE DISPLAY
            CALL DIALOG.setCurrentRow("tbl_results", gv_current_ix)                     This is how we make sure the results screen pops up on the row that matches the
                                                                                                                        internal arrays row.
#                                                                                                                      We use the "gv_current_ix" to do retrieve on current/next/previous row.
        ON SORT
            LET lv_sort_key = DIALOG.getSortKey("tbl_results")                               This gets the "users" current sort column – Note: ON SORT fires when the display       
                                                                                                                       array  is executed as wells as when user clicks on
            LET lv_issort   = DIALOG.isSortReverse("tbl_results")                              another column to sort.   The lv_issort call gets direction of sort column
                                                                                                                   (Ascending/descending)
            CALL DIALOG.setCurrentRow("tbl_results", ARR_CURR())                    We are doing this to "keep" the user at the same row.   NOTE: this call may not be needed?
#
        ON ACTION cancel
            EXIT DISPLAY
#
        ON ACTION accept
            IF DIALOG.arrayToVisualIndex("tbl_results",                                           This condition is checking that user actually checked on an array row versus just
                                                                                                                          clicking on the ok button.  (We force user to use
               DIALOG.getCurrentRow("tbl_results"))    != 0 THEN                                 cancel button to leave results screen if they do not want to make a selection).
                LET gv_chosen     = TRUE
                LET gv_current_ix =                                                                            This call sets the internal array index to the screen positon index.
                    DIALOG.arrayToVisualIndex("tbl_results",
                    DIALOG.getCurrentRow("tbl_results"))
#
                IF LENGTH(lv_sort_key) != 0 THEN                                                      If user has the results sort by a fields and direction we sort the internal array to
                                                                                                                          match the screen array.
                    CALL ga_results.sort(lv_sort_key, lv_issort)
                END IF
#
                EXIT DISPLAY
            END IF
    END DISPLAY
# do_pick_list

Ending Note – the "lv_sort_key" name (which comes from the results form field name) has to match the field name in the array to sort.   We caused ourselves a bit of time figuring that one out.   It should not have but it did.   You can use a conditional (if/case) to map the screen field name to the array name.   We went with making sure our "result" forms and internal array field names were the same to keep the code small in the function above.   We use the same function over (generic) and opening different "results" screens forms.



1) If I sort the program array within the DISPLAY ARRAY, will that be okay?   If not, I could exit DISPLAY ARRAY and just re-enter it
From our experience (unless things have changed in new versions) sorting array in the ON SORT has issues as screen array is separate from internal array.   Exiting the display array and re-entering could be a way to implement a "cumulative" sort on the screen array.   A few things we encountered is ON SORT is called when DISPLAY ARRAY is "opened" (fires like before input, before display etc.).   The first time DISPLAY ARRAY is called you would want to get the sort information, exit the loop , sort the internal array to match user screen setting and go back into the DISPLAY ARRAY loop.  However, each time after the first "loop" exit you would not want to exit the display array until the second ON SORT hit.   I believe you will be in an infinite loop if you exit on each entry of ON SORT?  Another issue is when user selects "reset sort order" there is no way to detect that and reset internal array back to the original. (losing this feature may not be an issue for your implementation versus benefit of having cumulative screen sort?).

I am looking forward to hearing input/experiences from what you and others have implemented.  Always looking at ways to improve our code.

Thanks
Keith

[Sebastien F.]

Candy,

Sebastien, our sort will sort according to what the user chooses.

Yes, sure, and I see no problem to collect the selected columns from ON SORT, and then build the SELECT / ORDER BY from it, to fill a new array...

It would probably be easier for me to program another sort rather that execute the SQL...

I wonder... I am not sure that programming your own sort (plus some tricks in DISPLAY ARRAY?) is easier than re-executing a SELECT to re-filll an array.
You may consider to fill an array of primary keys only, if you implement a navigation feature with first/next/prev/last actions, that displays one record at a time.
Then re-execute another SELECT * FROM tab WHERE pkey = curr_pkey_in_array, to get fresh data from the DB server...

.... plus some of the elements of the array could be calculated values.

If these calculated values can be computed in the SELECT, you can also sort by these calculated columns.
Consider using SQL views if the query is complex.

We use this sort in several places in our code.

This is why you should consider the simplest solution, instead of blowing up your code at several places.

Seb

[Candy M.]

Hello Keith,

Thank you so much for your time and effort to post a long response.   I really appreciate that.

Our company also uses a QBF and results set (internal array) that our users wanted to have the sort match what they were doing in the results screen.   They wanted the Next/Previous functions to match how the results screen was sorted when they returned from the results screen.

That is the same situation we have.

Going back and looking what we have done and discussing with our team, we are not as concerned with keeping a cumulative sort, so after leaving the display array, we will execute the sort on the last column that was chosen.   Then, when the user presses the Next/Previous buttons it will be accurate.   If the user is switching back and forth between the browselist, we do even perform a sort if the user cancels out of the browselist form.   The current record will then be visible for editing or viewing and the user could press Previous/Next at that point.

It really hasn't come to our thought to choose the method of executing the sql again.   That surfaces many other issues as a possible need to parse the SQL query again.   Also, we keep a database of our forms.   On the forms for many of our maintenance routines, I would say at least 75 percent of them, we have database table that has the columns we actually want to be in the browse list.   So our array name is generic as well as the column names, so it would be more coding involved to figure that out.

Everything has worked fine except that my sort is slow on large list of rows.   So if we fix that, everything should be fine.   We are trying to maintain same code source for 2.50, 3.00 and 3.10.    Trying to add the pre-processor commands may cause many things to break as we haven't used them in a while, so I'm going to see if I can improve the sort I have, then that would work in all 3 versions.   We are also exploring with support migrating our 2.50 to 2.51, but that may not be a good idea as it doesn't appear to be maintained.   If it looks too difficult for me to rewrite the sort, then I'll look at the preprocessor route again.

Thanks for everyone's input!
Candy

[Reuben B.]

Candy,

To answer the following ...

Code (genero) Select Expand

I'm not sure what 2.51 is

Going back a few years, Genero Mobile was released between 2.50 and 3.00.  2.51 was the release of the FGL product with the additional syntax required for Genero Mobile.

Also with regards to the following

Could you possibly port it to 2.50? 

The answer will be No, because then the version will not be 2.50 any more.   

http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/c_fgl_Migrate_to_all_pcode.html

Code compiled using a X.Y (M.FF) compiler can be run using any other X.Y (M.FF) runner.

So if hypothetically we took the last 2.50 Maintenance release, 2.50.34 and changed the compiler and runner so that 2.50.35 implemented the array.sort syntax then you would be in a position where code compiled with the hypothetical 2.50.35 compiler would not run with the 2.50.34 runner as the 2.50.34 runner would not recognise the array.sort instruction.   

Hence why the FGL needed for Genero Mobile is 2.51, as it included the new syntax http://4js.com/online_documentation/fjs-fgl-manual-html/#fgl-topics/fgl_whatsnew_251.html required for Genero Mobile, as well as I think some new syntax that was finished and ready such as the array.sort() method.

This principal is what allows you to safely upgrade maintenance releases without requiring a recompile.

It is very very very unlikely that any new syntax will ever be back-ported to an older version.  If it was, it would require a version number increase e.g. 2.51->2.52, 3.00->3.01 and you would have to a do a recompile and distribution of your compiled objects i.e a similar amount of work anyway as if you upgraded to the latest FGL version.  So you would be better advised looking forward and upgrading to the latest FGL version, rather than looking backwards and trying to get functionality added to a nearly 5 years old version.

Reuben

[Reuben B.]

Keith,

Do you want to elaborate on

Also when the user reset sort fields to "defaults" there was no way to detect that and reset the internal array.

I interpreted that to mean ON SORT was not triggered when the user clicked on 'Reset to Defaults' or 'Reset Sort Order', which I could see that that might be something we might miss,  but a quick test suggests that we do cover that possibility and ON SORT is triggered when they are clicked.

Reuben

[Reuben B.]

Candy,

I created the following example https://github.com/FourjsGenero/ex_browseviewsort which is my interpretation of problem you are trying to solve, and how you can use ON SORT, array.sort(), DIALOG. arrayToVisualIndex() to apply the build-in sort from a DISPLAY ARRAY to the 4gl array

Reuben

[Keith Y.]

Hello Reuben,

Quote
Also when the user reset sort fields to "defaults" there was no way to detect that and reset the internal array.

I interpreted that to mean ON SORT was not triggered when the user clicked on 'Reset to Defaults' or 'Reset Sort Order', which I could see that that might be something we might miss,  but a quick test suggests that we do cover that possibility and ON SORT is triggered when they are clicked.


In reference to the Quote and your response, this was around attempting to have the screen sort be cumulative by exiting the DISPLAY ARRAY each time ON SORT is triggered after the initial entry.   The ON SORT fires each time sort field is changed or reset.  My reference is that you do not know that user has chosen to reset the sort order to the default versus they just selected another column to sort by.   Example,  default sort order is column 1,  ON SORT is trigger first time DISPLAY ARRAY is hit so exit from DISPLAY ARRAY and order internal array to match user setting and reenter DISPLAY ARAAY.  Do not exit from ON SORT after this initial exit until user selects a column to sort by.  User now selects column 2.  exits loop to sort internal array for column, renters display array,  user selects another column 3 to sort by, exits loop to sort internal array, renters display array, etc,  By exiting loop and reentering each time gives the screen sort the effect of being cumulative.  The issue doing this is when the user clicks on "Reset Sort Order" it "looks" the same to ON SORT as just sorting by another column so array is not really reset to initial sort order it just orders "cumulatively" on this column.   This is what I mean by no way to detect the "reset" versus just another column being selected for cumulative ordering.   
As an aside, there is a feature request for being able to select multiple fields to sort by for display arrays (cumulative) FGL-01477.  There is also an old forum thread "Shocked by ARRAY sort behavior" that is about INPUT ARRAY but hits on DISPLAY ARRAY as well.