//routeCombin.bcpl

// Combinatorial wire router

//last edited by Dave Rumph, November 27, 1984 4:43 PM
//fixed net length computation bug that resulted in lengths one segment too short
//last edited by McCreight, July 27, 1981 4:59 PM

get "route.defs"

static
[ n
Perm
X
Y
clusterBaseVec
forceFirstNodeToEnd

exhaustThresh = 7

TrialPerm
bestTotalNetLength

randomInitialized = false
]


let CombinRoute() be

[
bestTotalNetLength = infinity
let tP = Allocate(swapZone, n+1)
TrialPerm = tP
let cbv = vec 3

cbv!0 = 1 // number of clusters
cbv!1 = 1 // base of first cluster

if clusterBaseVec ne empty then cbv = clusterBaseVec

let clusterNumber = cbv!0

for i=1 to n do TrialPerm!i = i

// This combinatorial algorithm results in a true
//optimum but is prohibitively expensive for large nets.
//The idea is that there are two vectors X and Y holding the
//X and Y co-ordinates of a set of nodes (1...n), and a vector
//TrialPerm (1...n) containing a permutation of the integers 1...n.
//These integers are arranged in "clusters", which intra-permute but
//cannot inter-permute.

// Unfortunately, recursive calling to essentially unlimited depth
// can overflow our rather small stack, and it seems difficult
// to talk Bcpl into doing its stack in a free storage zone. Therefore we
// simulate the recursion with vectors. clusterTop contains the depth
// of the recursion, and the goal in the outer loop is to diminish jStk!clusterTop,
// which is the difference between clusterTop and the element to be exchanged with it
// in the trial permutation TrialPerm.

let netLengthSoFarStk = Allocate(swapZone, n+1)
let clusterNumberStk = Allocate(swapZone, n+1)
let jStk = Allocate(swapZone, n+1)
let netLengthSoFar = 0

jStk!n = (forceFirstNodeToEnd & (clusterBaseVec eq empty))? 0, // special case
n-cbv!clusterNumber // normal case

let ct,j = nil,nil

let clusterTop = n
while clusterTop le n do
[
if jStk!clusterTop ls 0 then
[ // this level finished. We must guarantee that TrialPerm!clusterTop..
// TrialPerm!1 have the values they had when clusterTop was last
// decremented to its present value.

ct = TrialPerm!clusterTop
for k=clusterTop to cbv!clusterNumber+1 by -1 do
TrialPerm!k = TrialPerm!(k-1)
TrialPerm!(cbv!clusterNumber) = ct

netLengthSoFar = netLengthSoFarStk!clusterTop
clusterNumber = clusterNumberStk!clusterTop
clusterTop = clusterTop+1
loop
]

// exchange a pair at this level

ct = TrialPerm!clusterTop
j = cbv!clusterNumber+jStk!clusterTop
TrialPerm!clusterTop = TrialPerm!j
TrialPerm!j = ct

jStk!clusterTop = jStk!clusterTop-1

let newNetLengthSoFar = (clusterTop ge n)? 0,
netLengthSoFar+
ArcLength(TrialPerm!clusterTop, TrialPerm!(clusterTop+1))

if newNetLengthSoFar ge bestTotalNetLength then loop

// finish this path or go deeper to next level

test clusterTop eq 2
ifso
[
let tnl = newNetLengthSoFar+ArcLength(TrialPerm!1,TrialPerm!2)
if tnl ls bestTotalNetLength then RecordBetterNet(tnl)
loop
]
ifnot
[
clusterTop = clusterTop-1
clusterNumberStk!clusterTop = clusterNumber
netLengthSoFarStk!clusterTop = netLengthSoFar

while clusterTop ls cbv!clusterNumber do clusterNumber = clusterNumber-1

jStk!clusterTop = clusterTop-cbv!clusterNumber
netLengthSoFar = newNetLengthSoFar
]
]

if forceFirstNodeToEnd & clusterBaseVec eq empty & Perm!n ne 1 do
CallSwat("Wrong node at end")

Free(swapZone, jStk)
Free(swapZone, netLengthSoFarStk)
Free(swapZone, clusterNumberStk)
Free(swapZone, tP)
]




and RecordBetterNet(length) be

[ bestTotalNetLength = length
MoveBlock(lv (Perm!1), lv (TrialPerm!1), n)
]



// Function to decide whether a net has any external connections

and HasExternalConnections(net) = valof
[

let pin = net>>net.pinList
while @pin ne mark do
[

let icinst,pinNo = nil,pin
FindIcinst(lv icinst, lv pinNo)
if Icclass(icinst)>>icclass.isConnector then resultis true
pin = @pin

]
resultis false

]