Hello.
I haven’t seen such a handler here already, and I think it should be a tad faster, than concatenating two list, and running quickSort over the new list, since the list is sorted up front.
I have snagged Nigel Garveys binarySearchForClosestMatch match handler in order to do so. And StefanK’s orderdInsert handler, because that handler is what made me make binaryOrderedInsert. StefanK’s handler, should be used as long as there are less than 16 items in the list or so.
on orderedInsert(_list, _itemToInsert)
-- http://macscripter.net/viewtopic.php?pid=178428
-- StefanK
set end of _list to _itemToInsert
set i to count _list
repeat while i > 1 and _itemToInsert < item (i - 1) of _list
set item i of _list to item (i - 1) of _list
set i to i - 1
end repeat
set item i of _list to _itemToInsert
return i -- position of new item
end orderedInsert
on binarySearchForClosestMatch(theList, theKey)
# Based on:
# http://macscripter.net/viewtopic.php?id=41483
# by: Nigel Garvey
script o
property lst : theList
end script
set l to 1
set R to (count theList)
repeat while (R > l + 1)
set m to (l + R) div 2
if (item m of o's lst < theKey) then
set l to m
else
set R to m
end if
end repeat
if class of theKey is integer or class of theKey is real then
if (theKey - (item l of o's lst) > (item R of o's lst) - theKey) then
return R
else
return l
end if
else if class of theKey is string then
if theKey ≤ item l of o's lst then
return l
else if theKey ≤ item R of o's lst then
return R
else
return (R + 1)
end if
end if
end binarySearchForClosestMatch
on binaryOrderedInsert(theList, newItem)
-- http://macscripter.net/viewtopic.php?pid=178453#p178453
script o
property lst : theList
end script
set ix to my binarySearchForClosestMatch(o's lst, newItem)
if ix is 1 then
if newItem < item 1 of o's lst then
set nl to {newItem} & o's lst
else
set nl to {item 1 of o's lst} & {newItem} & items 2 thru -1 of o's lst
end if
else if ix < (count o's lst) then
if newItem < item ix of o's lst then
set nl to items 1 thru (ix - 1) of o's lst & {newItem} & items ix thru -1 of o's lst
else
set nl to items 1 thru ix of o's lst & {newItem} & items (ix + 1) thru -1 of o's lst
end if
else
if newItem < item -1 of o's lst then
set nl to items 1 thru -2 of o's lst & {newItem} & {item -1 of o's lst}
else
set nl to o's lst & {newItem}
end if
end if
return nl
end binaryOrderedInsert
Edit
I have removed a bug, which was testing for class = number, when the correct is to test for class = integer or class = real.
Thanks to Nigel Garvey.
Edit2
There was a another bug here as well, when concatenating the list when the new item, was bigger than the last item in the list.
You can get a perceived speed advantage, if the data lends itself to it, as time consumption for sorting, are acquired each time something is inserted, if using something like a priortiy queue, which a user won’t perceive as easily as one big list being sorted, which may become noticeable, as the sorting may stall a script or applet for some small amount of time, without the user fully understanding what is happening behind the scenes.