[jawsscripts] Re: JAWS Sorting Library
- From: Andrew Hart <ahart@xxxxxxxxxxxxx>
- To: jawsscripts@xxxxxxxxxxxxx
- Date: Wed, 04 Apr 2012 16:52:19 -0300
I think Optional has been available ever since ByRef. I don't recall
when they were introduced but it was a good few years ago.
On 4/04/2012 2:18 PM, Jim Bauer wrote:
> 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
>
>
>
__________�
View the list's information and change your settings at
//www.freelists.org/list/jawsscripts
Other related posts:
