[jawsscripts] JAWS Sorting Library
- From: Andrew Hart <ahart@xxxxxxxxxxxxx>
- To: jawsscripts@xxxxxxxxxxxxx
- Date: Wed, 04 Apr 2012 12:21:14 -0300
Hi folks,
Recently we've been discussing sorting in JAWS. Here's a small library
of code I have written for doing fast sorting in JAWS. It may be
possible to make the code faster, but this is a good start. I'll paste
the code below, but before I do that, perhaps I'll just give a brief
explanation of how to use it.
The function that does the sorting is called HeapSort. There are two
helper functions HeapSort uses, Heapify and SiftDown. There are two
utility functions for converting from segmented strings to string arrays
and back again: SegmentedStringToArray and ArrayToSegmentedString. The
final two functions are samples that you can play with to see how it all
works: HeapsortSample1 and HeapsortSample2.
To see it working, just paste the code into a jss file, dump one or both
of the sample functions into a script, assign the script a key, compile
and try it out.
I've tried to make the code fairly generic so it can just be added to
existing scripts and used without modification. However, if you are
doing something really special, the paradigm I've used may not suffice
and you'll have to get in and hack things to fit your purpose.
So, here's how you use it. Suppose you have something you want to sort.
You first create a StringArray, say, keys, and fill it with a set of
sort keys corresponding to what you want to sort. If we use John's
project as an example, he has a large 8 column array. For the purpose
of exposition I'll call it tuneData. tuneData is, say, 2000 by 8. If
one of those columns contains the album title and we want to sort the
data by album, we would create a one-dimensional array containing the
album titles using code like
keys = New StringArray[2000]
For i = 1 To 2000
keys[i] = tuneData[i, 2] ; supposing that the album title is the
second column of tuneData
endFor
We also need to declare an IntArray to hold the result of the sort.
Var IntArray indices
Now we're ready to sort, which is done with the statement
Heapsort(keys, 2000, indices)
That's it. indices now holds the indices to keys but sorted into their
correct order. Note that Heapsort does not modify the keys array. The
indices array that it returns tells you how to arrange the items in keys
so that they are in lexicographic order. So, if you were to examine
keys[indices[1]], keys[indices[2]], keys[indicies[3]], etc., you'd find
them in order.
I haven't written a utility function for applying indices to keys,
because it depends on what it is you are sorting. For example,
rearranging a simple StringArray like keys in this example is different
from rearranging the rows of tuneData. I've left this for the
programmer to write, but here's an example of how to do it:
Var tuneDataSorted = New VariantArray[2000, 8]
For i = 1 To 2000
For j = 1 To 8
tuneDataSorted[i, j] = tuneData[indices[i], j]
EndFor
EndFor
I should probably write a couple of functions for handling stock
standard cases of sorting segmented strings and string arrays so they
can just be used as black boxes, but I haven't had time to do that as yet.
I hope this is enough info to get anyone interested started in playing
with it.
Now, here comes the code library, just after my sig. Btw, I also have
a jsd file for these scripts, since I compiled them in a sortlib.jsb and
simply invoked the Use statement to import them into my test scripts.
If anyone wants the jsd file, just let me know.
Cheers,
Andrew.
; JAWS Sorting Library
; andrew Hart (April 2012)
; *** Heap sort ***
Void Function HeapSort(StringArray keys, Int arrayLen, IntArray ByRef
indices)
Var
Int i, ; integer counter
Int nIdx ; temp Int for swapping
Let indices = new IntArray[arrayLen]
; Set up the original indices
For i = 1 to arrayLen
Let indices[i] = i
EndFor
Heapify(keys, arrayLen, indices) ; organise the array into a binary heap
Let i = arrayLen
While i>1
; swap the root node (index 1) with the last node in the heap (index i)
Let nIdx = indices[i]
Let indices[i] = indices[1]
Let indices[1] = nIdx
Let i = i - 1 ; decrement i to shrink the heap by one, removing the
last element from the heap and thus leaving it sorted
SiftDown(keys, 1, i, indices) ; sift the new root node into the
correct place in the heap, since it will most probably be in the wrong place
EndWhile
EndFunction
Void Function Heapify(StringArray heap, Int nEnd, IntArray indices)
; Organise the indices array so that when the array "heap" is ordered
according to it, we obtain a heap.
; A heap is a tree in which each node is larger than (or is ranked as
coming after) any of its children.
Var
Int nStart
Let nStart = (nEnd-2)/2 + 1 ; find the last parent node in the heap
While nStart>=1 ; while we haven't processed the root node of the tree
SiftDown(heap, nStart, nEnd, indices) ; sift the current node down the
tree until it is larger than any of its children
Let nStart = nStart-1 ; move to the next node that we haven't sifted yet
EndWhile
; That's it. The indices and heap arrays now encode a heap structure.
EndFunction
Void Function SiftDown(StringArray heap, Int nStart, Int nEnd, IntArray
indices)
Var
Int nLeftChild, ; for holding the index of the left child of the root
Int nSwap, ; for holding the swap index
Int nRoot, ; for holding the root index
Int nIdx ; temp Int for facilitating swap
If nStart<1 || nStart>nEnd Then ; trap caller stupidity so JAWS doesn't
go tropo
Return
EndIf
Let nRoot = nStart ; set the root to the start node specified by the caller
While nRoot*2<=nEnd
Let nSwap = nRoot ; initially set the swap index to the root index
nLeftChild = nRoot*2 ; get the index of the root's left child node
If StringCompare(heap[indices[nSwap]], heap[indices[nLeftChild]])<0 ;
if the root is smaller than it's left child
Let nSwap = nLeftChild ; make the left child the swap target
EndIf
If nLeftChild<nEnd then ; if the root has a right child node
If StringCompare(heap[indices[nSwap]],
heap[indices[nLeftChild+1]])<0 Then ; if the currently selected swap
target is smaller than the root's right child
Let nSwap = nLeftChild+1 ; make the right child the swap target
EndIf
EndIf
; Decide whether or not to swap
If nRoot!=nSwap Then ; if the swap target is no longer the root node
; exchange the root and swap nodes
Let nIdx = indices[nSwap]
Let indices[nSwap] = indices[nRoot]
Let indices[nRoot] = nIdx
Let nRoot = nSwap ; make the swap node the root and repeat to
continue sifting the root down the branch
Else
Return ; heap property recovered, done sifting, bail out here
EndIf
EndWhile
EndFunction
; *** Utility functions for converting back and forth between segmented
strings and string arrays ***
String Function ArrayToSegmentedString(StringArray a, Int arraylen,
String sep, optional IntArray indices)
Var
Int i,
String s
If indices[1]<1 ; if no indices array is passed in
Let indices = New IntArray[arrayLen]
For i = 1 To arrayLen
indices[i] = i
endFor
EndIf
Let s = a[indices[1]]
For i = 2 to arrayLen
Let s = s + sep + a[indices[i]]
EndFor
Return s
EndFunction
Int Function SegmentedStringToArray(String segString, String sep,
StringArray ByRef a)
Var
Int i,
Int segCount
Let segCount = StringSegmentCount(segString, sep)
Let a = New StringArray[segCount]
For i = 1 to segCount
Let a[i] = StringSegment(segString, sep, i)
EndFor
Return segCount
EndFunction
; *** Sample Code and Example Code ***
Const
testarraylen = 10000 ; number of items to sort in HeapSortSample1
Void Function HeapSortSample1()
Var
Int i, ; a counter
Int j, ; used as a counter and to hold a boolean value during testing
String s, ; a string
StringArray testarray, ; the array of sort keys
IntArray perm ; the array to hold the indices output by the sort
; Build a string containing 500 b's
Let s = ""
For j = 1 To 500
Let s = s+"b"
endFor
; Create the test array and fill it with something to sort
Let testarray = new StringArray[testarraylen] ; create an array of
testarraylen elements
; fill the test array with keys
for i = 1 To testarraylen
Let testarray[i] = IntToString(testarraylen+1-i)+s
EndFor
; Now perform the sort
SayString("starting") ; announce start
Let i = GetTickCount () ; record starting time
heapSort(testarray, testarraylen, perm) ; do the sort
SayInteger(GetTickCount()-i) ; announce the number of ticks that elapsed
during the sort. 1 tick = 1 ms
SayString("done") ; announce done
; Check to see if the perm array holds the indices sorted into
lexicographic order
Let j = 1 ; set j to True
For i = 1 To testarraylen-1
Let j = j && (StringCompare(testarray[perm[i]], testarray[perm[i+1]])<=0)
EndFor
If j Then
SayString("Sort successful")
Else
SayString("Sort failed")
EndIf
EndFunction
Void Function HeapsortSample2()
Var
String s, ; the initial segmented string to sort
String sorted, ; the resulting segmented string
Int nKeys, ; the number of keys in the keys array
StringArray keys, ; array for holding the sort keys
IntArray indices ; the sorted key indices output by Heapsort
Let s =
"dog|rat|pig|cat|bat|ant|owl|ox|tiger|elephant|fish|whale|snake|llama|frog"
; convert to a string array of sort keys
Let nKeys = SegmentedStringToArray(s, "|", keys)
HeapSort(keys, nKeys, indices) ; do the sort
Let sorted = ArrayToSegmentedString(keys, nKeys, "|", indices) ; build a
segmented string from the keys array
DlgSelectItemInList(sorted, "Animal Names", 0)
EndFunction
__________�
View the list's information and change your settings at
//www.freelists.org/list/jawsscripts
Other related posts:
