[jawsscripts] Re: JAWS Sorting Library
- From: "John Martyn" <johnrobertmartyn@xxxxxxxxx>
- To: <jawsscripts@xxxxxxxxxxxxx>
- Date: Wed, 4 Apr 2012 20:49:56 -0700
I am starting to understand the for loops, but I gathered the information as
row 1 would be artist, row 2 would be album, row 3 would be track name, etc.
I see that you are doing this by column, at least I think that's what you're
doing.
It isn't just sorting the array, it's also finding the unique items in the
row, or in your example by column. So you could say that each column could
be the key?
Could you also accomplish this by row?
I was actually getting the unique list in an array way bigger than it needed
it to be, then when I iterate through it, I look for the empty column to
trigger a break in the while loops.
I think it works just as fast, but when I examine for say, track names under
an artist, I would loop through the whole row. One reason I do this is
because there is something really stupid in iTunes. If you have an artist
like doors, and some artist tracks are called The Doors, with the word the
in it, it can sometimes throw this right in the middle of the artist list
depending on the album name. This is just how iTunes sorts some stuff, which
is better actually, but harder to program for. So I just loop through the
whole row looking for the instances that match. In the last function view
all tracks, it does this. I had to also be careful of vertical bars in the
genre, artist, album, and track name, which is why I run it through the
alphabetize statement to replace those characters. It only detects for
single vertical bars and doubles. Anything beyond that in a row is going to
mess up the list when it presents itself.
So what I am getting around to is being able to count for unique arrays
taking out all the duplicates and just leaving it at its monsterous size. If
I was able to resize it, could I then count without iterating through a for
or while loop?
Thanks,
John
-----Original Message-----
From: jawsscripts-bounce@xxxxxxxxxxxxx
[mailto:jawsscripts-bounce@xxxxxxxxxxxxx] On Behalf Of Andrew Hart
Sent: Wednesday, April 04, 2012 8:21 AM
To: jawsscripts@xxxxxxxxxxxxx
Subject: [jawsscripts] JAWS Sorting Library
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
__________�
View the list's information and change your settings at
//www.freelists.org/list/jawsscripts
Other related posts:
