Help - Working with Coordinate Lists

I’m trying to work with a given list of 10 two-item lists, or a list of coordinates if you will. For instance:

``````set list1 to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}

``````

If you plot these with the Cartesian system, you get this:

What I want a script to be able to do is create the following from the previous list, or another given list of adjacent coordinates:

``````set list 2 to {{{-2, 0}, {-1, 0}, {0, 0}}, {{-2, -1}, {-1, -1}, {0, -1}}, {{-3, -2}, {-2, -2}, {-1, -2}, {0, -2}}}
``````

list2 contains the same coordinates as list1 except they are categorized by their Y value, in descending order, then again by their X value in ascending order.

So I want the script to find the coordinate with the largest Y value, then put it and all coordinates with the same Y value in a list, ordered from their smallest X value to their largest X value. Then the script finds the next highest Y value and repeats the process. At the end, the script puts all those lists into one overarching list, in descending Y value order.

I made a stab at this but I couldn’t do it. Here’s what I got, but it doesn’t work. If anyone has any ideas or tips, I would be exceedingly grateful.

``````--A list of 10 adjacent X/Y coordinates
set list1 to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}

--placeholder for largest item 2 (Y value) among the coordinates in list1
set yMargin to ""

--For new lists
set list2 to {}
set list3 to {}

--returns a new list made from the fromList, excluding items it finds in the toList
on updateListItems(fromList, toList)
set newList to {}
repeat with i in fromList
if i is not toList then
copy i to end of newList
end if
end repeat
return newList
end updateListItems

--sets yMargin to the highest item 2 (Y value) of the items in list1
repeat with i in list1
set yValue to (item 2 of i)
if yMargin is "" then
set yMargin to yValue
else if yValue is greater than yMargin then
set yMargin to yValue
end if
end repeat

--all coordinates in list1 whose item 2 is equal to yMargin are copied into list2
repeat with i in list1
if (item 2 of i) is yMargin then
copy i to end of list2
end if
end repeat

--all items that are now in list2 are deleted from list1
set list1 to updateListItems(list1, list2)

--reorders items in list2 by putting them into list3 in order of smallest X value to largest X value
repeat (count list2) times

--the smallest item 1 (X value) among the coordinates in list2
set xMargin to ""

repeat with i in list2
set xValue to (item 1 of i)

if xMargin is "" then
set xMargin to xValue
set leastX to i
else if xValue is less than xMargin then
set xMargin to xValue
set leastX to i
end if

end repeat

copy leastX to end of list3
--remove items copied to list3 from list2
set list2 to updateListItems(list2, list3)
end repeat

return list3
``````

Model: MacBook Pro 15"
AppleScript: AppleScript 2.3.1
Browser: Safari 537.74.9
Operating System: Mac OS X (10.8)

Hi.

Here’s one approach: sort the coordinates into the required order, then group them into equal-Y lists.

``````-- A customisable sort handler.
on CustomInsertionSort(theList, l, r, customiser)
script o
property comparer : me
property slave : me
property lst : theList

on isrt(l, r)
set u to item l of o's lst
repeat with j from (l + 1) to r
set v to item j of o's lst
if (comparer's isGreater(u, v)) then
set here to l
set item j of o's lst to u
repeat with i from (j - 2) to l by -1
tell item i of o's lst
if (comparer's isGreater(it, v)) then
set item (i + 1) of o's lst to it
else
set here to i + 1
exit repeat
end if
end tell
end repeat
set item here of o's lst to v
slave's shift(here, j)
else
set u to v
end if
end repeat
end isrt

on isGreater(a, b)
(a > b)
end isGreater

on shift(a, b)
end shift
end script

set listLen to (count theList)
if (listLen > 1) then
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (l > r) then set {l, r} to {r, l}

if (customiser's class is record) then set {comparer:o's comparer, slave:o's slave} to (customiser & {comparer:o, slave:o})

o's isrt(l, r)
end if

return -- nothing.
end CustomInsertionSort

-- A "plug-in" to customise the sort handler's comparisons.
-- This one causes coordinate pairs to be reverse-sorted on Y with forward subsorts on X.
-- Pair a is "greater than" (ie. should go after) pair b if (a's Y = b's Y and a's X > b's X) or (b's Y > a's Y).
script YdescXasc
on isGreater(a, b)
set {Xa, Ya} to a
set {Xb, Yb} to b
if (Ya = Yb) then return (Xa > Xb)
return (Yb > Ya)
end isGreater
end script

set list1 to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}

-- Sort a copy of list1, the coordinate pairs sorted Y descending with ascending subsorts on x.
copy list1 to list1Sorted
CustomInsertionSort(list1Sorted, 1, -1, {comparer:YdescXasc})

-- Create list2 with the now-ordered coordinates grouped into lists with equal Ys.
set list2 to {}
set end of list2 to {beginning of list1Sorted}
set currentY to end of end of result
repeat with i from 2 to (count list1Sorted)
set theseCoords to item i of list1Sorted
set thisY to end of theseCoords
if (thisY = currentY) then
set end of end of list2 to theseCoords
else
set end of list2 to {theseCoords}
set currentY to thisY
end if
end repeat

list2
--> {{{-2, 0}, {-1, 0}, {0, 0}}, {{-2, -1}, {-1, -1}, {0, -1}}, {{-3, -2}, {-2, -2}, {-1, -2}, {0, -2}}}
``````

Thank you so much. That is a fantastic script. I just wish I could really understand how it works. haha. Just goes to show how much more there is to Applescript than what I know. Again, thanks a million.

For your purposes, you don’t need to understand the sort handler’s internal workings ” only everything else in the script. But I should perhaps have explained these two lines:

The sort actually arranges the items in the list passed to it, so it’s set to work on a duplicate here in case you still need the original in its original order.

The parameters mean: “Sort items 1 thru -1 of list1Sorted, using the isGreater() handler in the script object YdescXasc to compare them.” The last parameter’s a record in order to be able to differentiate between a script object with a comparison handler and another kind which the sort can also use.

The isGreater() handler in this case tells the sort that one Y coordinate is greater than the other if in fact it’s the other way round, which is how the reverse sort is obtained. If the two Ys are the same, it’s the normal comparison of the two X’s which determines which pair of coordinates is the “greater”.

Hi, Nigel. Since they’re so different, I’ll share my sorting method. I haven’t compared them at all for efficiency, but mine is shorter and perhaps easier to follow.

``````
set theList to {{0, 0}, {-1, 0}, {-2, 0}, {-2, -1}, {-1, -1}, {0, -1}, {0, -2}, {-1, -2}, {-2, -2}, {-3, -2}}
sort(sort(theList, 1, "ascending"), 2, "descending")

(*
Although the example lists are in pairs, the handler can work with any quantity, dependent on the positionIndex.

This example features two handler calls: the passed list (including the returned value of the first call”"theInstances"), the sort position within the list, and the numeric course.
*)

-----------------------------------------------------------------------------------------------------------------------------------------------

on sort(target, positionIndex, direction)
--BOOKEND (finds extreme ranges and limits to unique integers)
set Maximal to 0
set Minimal to 0
set permissible to {}
repeat with numbr from 1 to count target
tell target's item numbr's item positionIndex
if permissible does not contain it then set permissible's end to it
if it > Maximal then set Maximal to it
if it < Minimal then set Minimal to it
end tell
end repeat
(*
example first pass result:
minimal = -3
maximal = 0
permissible =  {0, -1, -2, -3} --apparent order is only coincidental to this example; it has yet to be arranged
*)

--ARRANGE (puts permitted values into numeric order)
set newOrder to {}
repeat with numbr from Minimal to Maximal --highly disparate ranges (gargantuan numbers) may retard this, because iteration
if numbr is in permissible then set newOrder's end to numbr --expands the range between endpoints
end repeat
if not direction = "ascending" then set newOrder to newOrder's reverse --accomodates course changes
(*
on 1st run, newOrder = {-3, -2, -1, 0}
*)

--INSTANTIATE (cross-references numbers in the reordered list against the original, realizing them into an instance list)
set theInstances to {}
repeat with numbr from 1 to count newOrder
repeat with value from 1 to count target
if target's item value's item positionIndex is newOrder's item numbr then set theInstances's end to target's item value
end repeat
end repeat
theInstances --example first pass result: {{-3, -2}, {-2, 0}, {-2, -1}, {-2, -2}, {-1, 0}, {-1, -1}, {-1, -2}, {0, 0}, {0, -1}, {0, -2}}
end sort

``````

edited for commenting

Hi Marc.

I don’t recognise your algorithm, but it certainly does the job here. On my machine, using my own script timer, it sorts the given list in 1.0E-3 seconds (about a thousandth of a second), which isn’t very much. Mine, including the preceding ‘copy’ line, times in at 0.0 seconds (too short to measure), which is only slightly less.

Yours is obviously hard-coded to sort lists of lists on items with numerical values and the efficiency of the “arrange” section depends on those values being close together. If, for instance, you append a coordinate {1000000, -1000000} to the end of theList, my sort still takes 0.0 seconds (including the preceding ‘copy’) whereas yours now takes 8.831 seconds, on average.

Mine’s hard to understand because I’ve simply pulled it out of my library of sorts and it contains quite a lot of code which isn’t directly relevant to the immediate problem. Its core (the contained isrt() handler) is an insertion sort, which is an ideal algorithm with short lists. This customisable version doesn’t compare list items itself, but passes them to the isGreater() handler in the supplied script object (YdescXasc in my script), which uses its own criteria to determine whether or not the item on the left should go after the item on the right. The same sort code can thus handle practically anything, given a suitable comparison plug-in. If no such script object’s supplied, the sort uses its own built-in isGreater() handler to do straight comparisons of the items. The calls to a shift() handler are for sorting other lists in parallel and aren’t relevant here.