A new Miva Script sorting function

From time to time in my work, I run into a project where I need to sort some data in memory, instead of relying on a database index to do the sorting for me. I've written a few different sorting functions over the years; and so have a lot of other people, according to this article at MivaScript.com. Recently I came up with a function that I thought was worth sharing. It has a number of useful features.

• It can sort alphabetically or numerically, ascending or descending. For numeric sorting, it can operate on positive and negative values, with or without decimal points.
• It can sort arrays of objects with named members, a structure that we use a lot in Miva Script to represent data from DB tables. It can sort these arrays on any "column" (object member), or on multiple columns.
• The function takes advantage of the object-member sorting that's built into the Miva VM, so it's quite fast. However, unlike other object-based sorts, this one does not require that the data consist only of letters, digits, and underscores. It can sort data containing any characters.
• For all of that, the function is quite small, about 50 lines of code. It seems to be reasonably fast, too. Besides using the built-in member sorting, it operates without a lot of data shuffling. It makes one pass through the source array to build an index; then it loops through the index and copies each element of the source array to the destination. Running on the shared server at TheMagicM.com, It can do a 2-column sort on a 10,000-row, 3-column table in about 5 seconds. A single-column sort on the same table takes less than a second.

The call format is:

MultiSort(source_array, colspecs, direction)

• source_array is the array to be sorted.
• colspecs is a string that specifies the columns to sort on.
• direction is a string that selects ascending or descending order.
• The return value is a copy of the source array, sorted in the desired order.

For example, suppose you have an array containing data about customers that's been read from the store's s01_Customers table; and you want to sort it in the classic phone-book order, by last name and first name. You can write a call such as:

<MvASSIGN NAME="l.sorted" VALUE="{ MultiSort(l.customers, 'bill_lname, bill_fname', '') }">

The colspecs parameter specifies the two-column sort by last name and first name of the billing address.

The function does alphabetic sorting by default. If a column contains numeric data, you indicate this by adding a suffix to the column name. For example, you may have an array of data about completed orders, and you want to sort it by the total amount purchased, with the largest orders coming first:

<MvASSIGN NAME="l.sorted" VALUE="{ MultiSort(l.orders, 'total#10', 'D') }">

In this case, the direction parameter contains a D to specify descending order (highest values first). The column name ends with a # character, followed by a number. The number specifies how many digits there are in the largest value that will be sorted. You need to enter this so that the function can pad the numbers wih leading zeroes, which is necessary to make them sort correctly. 10 digits is enough for most e-commerce applications. Note that padding is only needed to the left of the decimal point. If you want to sort some numbers that have up to 10 digits before the decimal point, and 2 digits after it, you can specify #10, not #12.

If the source array contains single values, not objects, leave the colspecs parameter empty for alphabetic sorting. For numeric sorting on an array of numbers, use a column spec that has a suffix but no name, e.g. #10 for sorting 10-digit numbers.

If the first character of the direction parameter is the letter D (upper or lower case), the function will sort in descending order. For any other value, the function will sort in ascending order. So you can use a variety of values such as ASC and DESC for SQL compatibility, or Up and Down for readability, or just empty-string and d to minimize the typing.

The source code for the function is included below. I've also written a demo/test script which you can try here. or download the source code here.

The test script runs several different types of sorts on small tables, and displays the results before and after sorting. Some of the data in the tables is random; the script will generate new data each time you refresh the page. For demo purposes, MultiSort saves the key value it computed for each array element, and displays them as an extra column in the results. Outputting the key can also be helpful for debugging.

Also, the script can optionally run some tests on larger tables, so you can try some speed tests. The larger tests are controlled by URL parameters:

• N=nnnn to run speed tests with tables of the specified size, e.g. N=1000 for 1000 rows
• Show=nnnn to display the initial data and results for the speed tests, only up to the specified number of rows

<MvFUNCTION NAME="MultiSort" PARAMETERS="array VAR, colspecs, direction" STANDARDOUTPUTLEVEL=""> <MvCOMMENT> ========== INITIALIZATION Parse the column specs and store info in l.columns. Also set the direction variable for ascending or descending ========== </MvCOMMENT> <MvIF EXPR="{ NOT len(l.colspecs) }"> <MvASSIGN NAME="l.columns[1]" VALUE=""> <MvELSE> <MvASSIGN NAME="l.colspecs" VALUE="{ miva_array_deserialize(l.colspecs) }"> <MvFOREACH ARRAY="l.colspecs" ITERATOR="l.colspec" INDEX="l.s"> <MvREFERENCE NAME="l.column" VARIABLE="{ 'l.columns[' $ l.s $ ']' }"> <MvASSIGN NAME="l.column:name" VALUE="{ trim(gettoken(l.colspec, '#', 1)) }"> <MvASSIGN NAME="l.padding" VALUE="{ gettoken(l.colspec, '#', 2) }"> <MvIF EXPR="{ len(l.padding) }"> <MvASSIGN NAME="l.column:numeric" VALUE="1"> <MvASSIGN NAME="l.column:npad" VALUE="{ trim(gettoken(l.padding, '.', 1)) + 1 }"> <MvASSIGN NAME="l.column:offset" VALUE="{ power(10, (l.column:npad - 1)) }"> </MvIF> </MvFOREACH> </MvIF> <MvIF EXPR="{ ('D' CIN l.direction) EQ 1 }"> <MvASSIGN NAME="l.where" VALUE="1"> <MvELSE> <MvASSIGN NAME="l.where" VALUE="-1"> </MvIF> <MvCOMMENT> ========== PASS 1 Loop thru the array, compute key value for each element, and store array indexes by key in l.index. Note that each member of l.index is an array, so it can handle two or more source array elements with the same key. ========== </MvCOMMENT> <MvFOREACH ARRAY="l.array" ITERATOR="l.element" INDEX="l.e"> <MvASSIGN NAME="l.key" VALUE=""> <MvFOREACH ARRAY="l.columns" ITERATOR="l.column" INDEX="l.c"> <MvIF EXPR="{ len(l.column:name) }"> <MvASSIGN NAME="l.kval" VALUE="{ miva_variable_value('l.element:' $ l.column:name) }"> <MvELSE> <MvASSIGN NAME="l.kval" VALUE="{ l.element }"> </MvIF> <MvIF EXPR="{ l.column:numeric }"> <MvASSIGN NAME="l.kval" VALUE="{ l.kval + l.column:offset }"> <MvASSIGN NAME="l.left" VALUE="{ padl(gettoken(l.kval, '.', 1), l.column:npad, '0') }"> <MvASSIGN NAME="l.right" VALUE="{ gettoken(l.kval, '.', 2) }"> <MvASSIGN NAME="l.kval" VALUE="{ l.left $ '.' $ l.right }"> </MvIF> <MvIF EXPR="{ l.c GT 1 }"> <MvASSIGN NAME="l.key" VALUE="{ l.key $ ',' }"> </MvIF> <MvASSIGN NAME="l.key" VALUE="{ l.key $ encodeattribute(l.kval) }"> </MvFOREACH> <MvCOMMENT> ========= Just for debugging & demo purposes: in tables with columns, save each element's key value as a new column ========== </MvCOMMENT> <MvIF EXPR="{ len(l.columns[1]:name) }"> <MvASSIGN NAME="l.element:__KEY_VALUE__" VALUE="{ l.key }"> </MvIF> <MvREFERENCE NAME="l.xr" VARIABLE="{ 'l.index:' $ l.key }"> <MvASSIGN NAME="l.xx" VALUE="{ miva_array_insert(l.xr, l.e, -1) }"> </MvFOREACH> <MvCOMMENT> ========== PASS 2 Loop thru l.index (sorted by Miva VM), and read index numbers for array elements. Copy each element to result array, inserting at the end for ascending sort, or at the beginning for descending sort. The inner loop handles cases of two or more records with the same key. ========== </MvCOMMENT> <MvASSIGN NAME="l.m" VALUE="{ miva_struct_members(l.index, l.members) }"> <MvFOREACH ARRAY="l.members" ITERATOR="l.mem"> <MvREFERENCE NAME="l.xm" VARIABLE="{ 'l.index:' $ l.mem }"> <MvFOREACH ARRAY="l.xm" ITERATOR="l.xme"> <MvASSIGN NAME="l.xx" VALUE="{ miva_array_insert(l.result, l.array[l.xme], l.where) }"> </MvFOREACH> </MvFOREACH> <MvFUNCRETURN VALUE="{ l.result }"> </MvFUNCTION>