//RouteSort.bcpl

// Code for sorting and heaping and binary searching

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

get "route.defs"

//----------------------------------------------------------------
//B i n a r y S e a r c h R o u t i n e
//----------------------------------------------------------------
let BinSearch(value, minIn, minOut, CompareWithIndex) = valof

[ // returns the index of the first argument to CompareWithIndex
// between minIn and minOut that is greater than or equal to
// value. Assumes CompareWithIndex(value, minOut)<0; never
// checks this. Assumes if i<j then for all values of x,
// CompareWithIndex(x, i)>=CompareWithIndex(x, j).

while minIn ls minOut do
[

let mid = (minIn+minOut) rshift 1 // never =minOut
let c = CompareWithIndex(value, mid)
test c gr 0
ifsominIn = mid+1
ifnottest c ls 0

ifsominOut = mid
ifnotresultis mid

]

resultis minIn

]

//----------------------------------------------------------------
//H e a p R o u t i n e s
//----------------------------------------------------------------
and AddToHeap(heap, item, Compare) be
[

let sonPtr = heap!0+1
heap!0 = sonPtr
let fatherPtr = sonPtr rshift 1
while fatherPtr gr 0 & Compare(heap!fatherPtr, item) ls 0 do
[

heap!sonPtr = heap!fatherPtr
sonPtr = fatherPtr
fatherPtr = fatherPtr rshift 1

]
heap!sonPtr = item

]

and PullFromHeap(heap, Compare) = valof
[

if heap!0 le 0 then CallSwat("Pull from empty heap")
let result = heap!1
let testItem = heap!(heap!0)
heap!0 = heap!0-1

let fatherPtr = 1
let sonPtr = 2
while sonPtr le heap!0 do
[

if sonPtr ls heap!0 &
Compare(heap!(sonPtr+1), heap!sonPtr) gr 0 then
sonPtr = sonPtr+1
if Compare(testItem, heap!sonPtr) ge 0 then break
heap!fatherPtr = heap!sonPtr
fatherPtr = sonPtr
sonPtr = fatherPtr+fatherPtr

]
heap!fatherPtr = testItem
resultis result

]
//----------------------------------------------------------------
//S o r t R o u t i n e
//----------------------------------------------------------------
and Sort(heap, Compare) be
[

let len = heap!0
heap!0 = 0
for i=1 to len do AddToHeap(heap, heap!i, Compare)
for i=len to 2 by -1 do heap!i = PullFromHeap(heap, Compare)
heap!0 = len

]