Re: Record sorting routine
Re: Record sorting routine
- Subject: Re: Record sorting routine
- From: has <email@hidden>
- Date: Sun, 9 Feb 2003 21:47:32 +0000
Jerry Podhajsky wrote:
I have a list of records that I'd like to sort by a date field contained
in all the records. I'm trying to roll my own with Applescript, but
have come up short and very confused.
Does anyone have a basic Applescript routine (I'm trying to avoid an
OSAX, so that I can see the code and maybe learn something) that takes a
list of records and sorts them by a specified field in the record?
</lurk>
Here's what I've been using. It can sort on multiple fields, and will
easily do what you want. Don't recommend trying to learn from it
though; it's complicated, contains a bunch of optimisations that make
it faster at the expense of legibility - not a good place to start.
If you really want to learn up on algorithms, find yourself a book
containing a good introduction to the subject and read that instead.
======================================================================
-------
-- PRIVATE
on _eval(theList, evalObj)
-- convert each item of list to a {val, item} sublist, where
-- val is the value from item to be compared in _sort()
script k
property lst : theList's items
end script
repeat with i from 1 to count of theList
get k's lst's item i
set k's lst's item i to {evalObj's eval(result), result}
end repeat
return k's lst
end _eval
on _reeval(theList, evalObj)
-- change the val in each {val, item} sublist
script k
property lst : theList
end script
repeat with i from 1 to count of theList
set k's lst's item i's first item to evalObj's eval(k's lst's
[NO-BREAK]item i's second item)
end repeat
return k's lst
end _reeval
on _uneval(theList)
-- convert list of {val, item} sublists back to list of items
script k
property lst : theList
end script
repeat with i from 1 to count of theList
set k's lst's item i to k's lst's item i's last item
end repeat
return k's lst
end _uneval
--
on _sort(lst, evalList)
script k -- speed kludge
property sourceList : lst
property lessList : {}
property sameList : {}
property moreList : {}
end script
set listLength to (count of k's sourceList)
-- take middle item of list as pivot
set midpoint to (listLength + 1) div 2
set pivotItem to k's sourceList's item midpoint
set k's sameList's end to pivotItem
set pivotVal to pivotItem's first item
-- process items on either side of pivot
repeat with x from 1 to (midpoint - 1)
set itm1 to k's sourceList's item x
set val to itm1's first item
if val = pivotVal then
set k's sameList's beginning to itm1
else if val < pivotVal then
set k's lessList's end to itm1
else
set k's moreList's end to itm1
end if
set itm2 to k's sourceList's item -x
set val to itm2's first item
if val = pivotVal then
set k's sameList's end to itm2
else if val < pivotVal then
set k's lessList's end to itm2
else
set k's moreList's end to itm2
end if
end repeat
if listLength mod 2 is 0 then
set itm to k's sourceList's item -midpoint
set val to itm's first item
if val = pivotVal then
set k's sameList's end to itm
else if val < pivotVal then
set k's lessList's end to itm
else
set k's moreList's end to itm
end if
end if
-- subsort
if ((count of k's lessList) > 1) then
set k's lessList to _sort(k's lessList, evalList)
end if
if ((count of k's sameList) > 1) and ((count of evalList) > 0) then
_reeval(k's sameList, evalList's first item)
set k's sameList to _sort(result, evalList's rest)
end if
if ((count of k's moreList) > 1) then
set k's moreList to _sort(k's moreList, evalList)
end if
return k's lessList & k's sameList & k's moreList
end _sort
on _sortList(theList, evaluatorsList)
if theList's class is not list then error "Not a list." number
[NO-BREAK]-1704
if evaluatorsList's class is not list then set evaluatorsList to
[NO-BREAK]{evaluatorsList}
if ((count of theList) > 1) then
_eval(theList, evaluatorsList's first item)
_sort(result, evaluatorsList's rest)
return _uneval(result)
else
return theList
end if
end _sortList
-------
--PUBLIC
on sortList(theList)
-- your basic list sort, e.g. sortList({1, 3, 8, 2}) --> {1, 2, 3,
[NO-BREAK]8}
try
script SimpleEval
on eval(val)
return val
end eval
return _sortList(theList, {SimpleEval})
end script
on error eMsg number eNum
error "An error occurred in sortList: " & eMsg number eNum
end try
end sortList
on sortListOfLists(theList, indexList)
-- sort a list of sublists, given a list of sublist indexes to
[NO-BREAK]sort on;
-- e.g. sortListOfLists(lst, {3, 2}) will sort lst's sublists
[NO-BREAK]first by their
-- third item and then by their second
try
if indexList's class is not list then set indexList to
[NO-BREAK]{indexList}
if indexList is not {} then
copy indexList to evaluatorsList
repeat with itm in evaluatorsList
script EvalIndex
property _idx : itm's contents
on eval(subLst)
return subLst's item _idx
end eval
end script
set itm's contents to EvalIndex
end repeat
_sortList(theList, evaluatorsList)
else
return theList
end if
on error eMsg number eNum
error "An error occurred in sortListOfLists: " & eMsg number
[NO-BREAK]eNum
end try
end sortListOfLists
on sortListUsingEvaluators(theList, evaluatorsList)
-- sort a list of complex items (e.g. lists or records)
-- evaluatorsList is a list of evaluator objects;
-- each evaluator object is a script object containing an
[NO-BREAK]eval(itm) handler
-- that returns the value to be compared (number, text, date;
[NO-BREAK]basically
-- anything that responds to =<> operators)
try
return _sortList(theList, evaluatorsList)
on error eMsg number eNum
error "An error occurred in sortListUsingEvaluators: " & eMsg
[NO-BREAK]number eNum
end try
end sortListUsingEvaluators
-------
-- TEST 1
log sortList({1, 3, 8, 2})
-- TEST 2
set lst to {{4, 1}, {3, 2}, {4, 0}, {4, 2}, {0, 5}, {4, 1}, {3, 0},
[NO-BREAK]{1, 7}}
log sortListOfLists(lst, {1, 2})
-- TEST 3
script EvalMyDate
on eval(theRecord)
return myDate of theRecord -- (your code here)
end eval
end script
set lst to {{myDate:date "Tuesday, February 4, 2003 12:00:00 am"},
[NO-BREAK]{myDate:date "Monday, February 3, 2003 12:00:00 am"},
[NO-BREAK]{myDate:date "Saturday, February 1, 2003 12:00:00 am"},
[NO-BREAK]{myDate:date "Sunday, February 2, 2003 12:00:00 am"}}
log sortListUsingEvaluators(lst, EvalMyDate)
-- TEST 4
script EvalA
on eval(rec)
return rec's a -- (your code here)
end eval
end script
script EvalB
on eval(rec)
return rec's b -- (your code here)
end eval
end script
set lst to {{a:1, b:3}, {a:5, b:2}, {a:5, b:1}}
log sortListUsingEvaluators(lst, {EvalA, EvalB})
======================================================================
Some day I might get around to testing, documenting and shoving it in
a proper library. One problem is that it's based on a quicksort
algorithm, which is prone to stack overflow errors on very large
lists due to its recursive nature. A good, optimised heap sort might
be a better choice, but I'm not up enough on algorithms to write one.
(The best I've done is a Shell sort, which was noticably slower than
the quicksort.) You pays your money and takes your chances. HTH.
has
<lurk>
p.s. folks, updated the website - lots of fun, flaky new toys to play
with, if you're interested:
--
http://www.barple.pwp.blueyonder.co.uk -- The Little Page of AppleScripts
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.