Yesterday I got aware on a sorting algorithm I did not know of sofar -- sleepsort -- and twittered about it:
I was really impressed and thought how to make it run on DataPower. There is no "sleep" or "delay" function among the DataPower extension functions for XSLT/XQuery/JSONiq besides the <dp:url-open> timeout trick (for development purposes only!). So I looked at GatewayScript and remembered my previous posting on GatewayScript timers, and this posting shows how to do sleepsort based on GatewayScript timers, but some tricks are needed.
The first problem that needed to be solved was how to pass an argument to a (anonymous) timeout function -- that was solved easily via some googleing, just pass arg1 [, arg2, ...] after the timeout value (in milliseconds) in setTimeout().
Next problem specifically to setTimeout solution for sleepsort was how to output the result [by session.output.write()] after the last timeout has fired. My first solution was to setup an additional timeout longer than all values to be sorted, but without knowing the maximum value that was difficult, and not nice.
The next idea was better, making use of the fact that only the last session.output.write() wins in sending the response back, just define two timeouts for each number to be sorted:
- timeout at x millisecond for number x, and timeout function appending x to result array when timeout fires
- timeout at x+1 millisecond writing the (current) result to session.output
OK, now we have 2N timeouts for sorting N numbers, but the final result gets written last and therefore returned.
Here you can see that it really works:
Of course there is the problem that sorting might not be correct if too many numbers get sorted and race condifions between timeouts might occur. Interestingly sorting 20000 numbers works always fine in GatewayScript(!).
I did pipeing the output of sleepsort.js into sleepsort.check.js in order to find occurences of incorrect sortings:
While sleepsort is not really a good sorting algorithm, sleepsort.js shows some interesting techniques on how to work with setTimeout() and session.output.