[Gambas-user] Ordering a bi-dimensional string[]...by several columns help wanted.

[Tobias Boege]

On Sat, 01 Dec 2018, Jorge Carrión wrote:
> The problem:
> 
> I need order a bi-dimensional array by several columns following de user's
> criteria.
> 
> It is relatively simple to order a two-dimensional array for a column, not
> long ago we saw several solutions in this mail list, but what I need now is
> to sort by several columns and that each of them can be ascending or
> descending.
> 
> I confess that I have been stuck with the subject for four days, that I
> have believed more than once that I had solved it and that in the end I
> have given up doing it alone. Does anyone have any idea how to approach the
> issue before it drives me crazy?
> 

Speaking generally, *comparison-based sorting algorithms* consist of
two parts:

  1. a *comparison function*, which is given two objects to compare
     and decides if the first is less, equal to or greater than the
     second one, returning an integer < 0, = 0 or > 0, and
  2. the *sorting algorithm*, which uses the comparison function
     as a black-box to decide how to rearrange an entire array to
     be in ascending order with respect to the comparison function.

The method Object[].Sort supports this style of sorting. The algorithm
is probably standard Quicksort from the C library and the elements of
the array have to implement the special _compare method [1] implementing
the comparison function.

Without using a dedicated class for your data to define a _compare
method, I don't see how you can sort it by custom criteria. So, your
two-dimensional array must be turned into a one-dimensional array of
record objects, each representing one line in your table.

Now, I think your complicated _compare method is supposed to combine
many simpler _compare methods for the properties of the record objects
*lexicographically* into a single ordering. To do this you run, inside
the _compare method, through all the comparison functions of the data
members in the order the user specified, inverting each result if the
sorting should be descending, until you first encounter a non-zero result.
That will be the result of the comparison. If all comparisons turn out
zero, well then the two records are equal as far as the comparison
can tell, and you also return zero.

I've attached a sample project which does this. It's not a nice solution
in that it requires a static "sorting specification" variable inside
your record class, but that's the best I could come up with -- and I've
written several implementations of this table sorting over many years,
because the question keeps popping up.

The main hindrance in Gambas is that you have to implement the _compare
method inside your class, and once you did that, it's immutable. You have
to write it in a configurable way if you want to sort by user-defined
criteria. All that is not the problem, the problem is that each object
does its own comparing to other objects, so each object has to receive
your sorting specification. That either works by setting a property on
every object in your array prior to sorting which is inefficient and
creates problems when an object is inside multiple arrays, or to use a
static variable inside the class, which is what I've done here, but has
a similar problem when you want to sort multiple arrays of that type
at the same time.

Other languages where code is a first-class citizen, often allow you
to sort any array of objects by providing a code object external to the
objects, implementing a user-defined comparison function. That's a better
fit for your task. An alternative that you can explore by yourself may
be to use qsort in the C library directly with Extern to get rid of the
_compare function *inside* the Record class. qsort takes a comparison
function with two parameters, it's not bound to any object. Maybe it works.

Regards,
Tobi

[1] http://gambaswiki.org/wiki/lang/special/compare

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sort-table-0.0.1.tar.gz
Type: application/gzip
Size: 12589 bytes
Desc: not available
URL: <https://lists.gambas-basic.org/pipermail/user/attachments/20181201/ea90d553/attachment-0001.gz>