// RouteDoSorted.bcpl

// Routines to do an action on namees in a sorted order

// last modified by E. McCreight, June 25, 1981 4:38 PM

get "route.defs"

static [ maxitems; nitems; itemHeap; CompareFn; greatestFinishedItem ]

let SwapDoInSortOrder(type, CFn, Action) be
[

nitems = 0

MapNamees(type, Count)
maxitems = nitems
let biggestBlockLen = nil
itemHeap = Allocate(SilZone, nitems+1, lv biggestBlockLen)
if itemHeap eq empty then
[

if biggestBlockLen ls 100 then
CallSwat("Sort block too small")
itemHeap = Allocate(SilZone, biggestBlockLen)
maxitems = biggestBlockLen-1

]

CompareFn = CFn
greatestFinishedItem = empty

[
itemHeap!0 = 0
MapNamees(type, NextBatchToHeap)
let itemsInHeap = itemHeap!0

for i=itemsInHeap to 2 by -1 do
itemHeap!i = PullFromHeap(itemHeap, CompleteCompare)
for i=1 to itemsInHeap do Action(itemHeap!i)
greatestFinishedItem = itemHeap!itemsInHeap
nitems = nitems-itemsInHeap
] repeatuntil nitems eq 0

Free(SilZone, itemHeap)

]

and NextBatchToHeap(namee) be
[

if greatestFinishedItem ne empty &
CompleteCompare(namee, greatestFinishedItem) le 0 then return

if itemHeap!0 ge maxitems then // get largest next time around
[

if CompleteCompare(namee, itemHeap!1) ge 0 then return
PullFromHeap(itemHeap, CompleteCompare)

]

AddToHeap(itemHeap, namee, CompleteCompare)

]

and CompleteCompare(x, y) = valof
[

let c = CompareFn(x, y)
resultis (c ne 0)? c, (x eq y? 0, (x gr y? 1, -1))

]