[jawsscripts] Re: JAWS Sorting Library
- From: "Jim Bauer" <holdsworthfan@xxxxxx>
- To: <jawsscripts@xxxxxxxxxxxxx>
- Date: Wed, 4 Apr 2012 12:18:48 -0500
This is interesting indeed. How long has "optional" been available?
On Wed, Apr 04, 2012 at 10:21:14, Andrew Hart wrote:
>
> 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|fro
> g"
> ; 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
__________�
View the list's information and change your settings at
//www.freelists.org/list/jawsscripts
Other related posts:
