# Implementation of the module {hotpath}.
# Last edited on 2021-02-19 15:52:39 by jstolfi

import hotpath
import block
import path
import contact
import move
import hacks
import rn
import sys
from math import sqrt, sin, cos, log, exp, floor, ceil, inf, nan, pi

def best_path(o, BS, CS, Delta, maxcalls, parms):
  describe_input(sys.stderr, o, BS, CS, Delta, maxcalls, parms)
  Q = path.make_empty(o)
  Qbest, ncalls = best_path_aux \
    ( Q, BS, CS, Delta, maxcalls, 
      Q_maxtc = 0, ncalls = 0, lev = 0, 
      Qbest = None, parms = parms
    )
  sys.stderr.write("made %d recursive calls to {best_path_aux}\n" % ncalls)
  if Qbest == None:
    sys.stderr.write("{best_path} failed to find a valid tool-path\n")
  else:
    assert contact.max_tcool(Qbest, CS) <= Delta
    # Report contact coverage and cooling times:
    sys.stderr.write("coverage times and cooling time of each contact\n")
    for k in range(len(CS)):
      ct = CS[k]
      sys.stderr.write("CS[%03d] (" % k) 
      tcs = contact.covtimes(Qbest, ct)
      for i in range(2):
        sys.stderr.write(" "+ ("   .   " if tcs[i] == None else ("%7.3f" % tcs[i])))
      tcool = contact.tcool(Qbest, ct)
      sys.stderr.write(" ) " + ("   .   " if tcool == None else ("%7.3f" % tcool)))
      sys.stderr.write("\n")
  return Qbest
  
def best_path_aux(Q, BSR, CSR, Delta, maxcalls, Q_maxtc, ncalls, lev, Qbest, parms):
  # Like {best_path}, but considers only paths that begin with the path
  # {Q}, which will be a {path.Path} object. 
  #
  # The set {BSR} must be what remains of the original block set {BS}
  # after removing all blocks already incorporated in {Q}. The set {CSR}
  # must be the contacts of the original set {CS} that are still
  # relevant: that is, which have at least one side that is a move of a
  # block in {BSR}.
  #
  # The parameter {Q_maxtc} must be the {contact.max_tcool(Q,CS')} where
  # {CS'=CS\setminus CRS} are the contacts from the original {CS} that
  # had both sides covered by {Q} (and hence are no longer in {CSR}).
  #
  # The parameter {ncalls} is the number of times this procedure has been
  # entered before the current call. 
  #
  # The parameter {lev} is the depth of recursion. It is how many blocks
  # were removed from the original set {BS} and added to the path {Q}.
  #
  # The parameter {Qbest} is the best valid path found so far, or {None}
  # if no path has been found yet.
  #
  # The parameters {maxcalls,Delta,parms} are as in {best_path}.
  #
  # The procedure returns two results: [0] the best valid path found so
  # far, or {None} if it could not find any such path; and [1] the given
  # number {ncalls} plus the count of all recursive calls made by this
  # call (at least 1). If the procedure can't find a better path than
  # {Qbest}, it returns {Qbest}.
  
  # We made one more call:
  ncalls += 1
  Q_extime = path.extime(Q)     # Time already taken by {t}
  if ncalls < 1000 or (ncalls % 10000) == 1:
    sys.stderr.write("%sncalls = %d Q_maxtc = %.3f Q_extime = %.3f\n" % ("."*lev, ncalls,Q_maxtc, path.extime(Q)))
    
  # Is {Q} the beginning of a valid path? 
  if predtcool(Q, Q_maxtc, BSR, CSR, parms) > Delta:
    # No -- Not worth continuing, return what we got so far:
    return Qbest, ncalls
    
  # Coud {Q} be extended to a path better than {Qbest}?
  mex = rest_min_extime(BSR) # Minimum time needed to excute the remaing blocks.
  if Qbest != None and Q_extime + mex >= path.extime(Qbest):
    # No -- Not worth continuing, return what we got so far:
    return Qbest, ncalls
    
  # Is Q a full path?
  if len(BSR) == 0:
    # If we got here, it must be valid:
    assert len(CSR) == 0
    # If we got here, it must be better than {Qbest}:
    assert Qbest == None or Q_extime < path.extime(Qbest)
    sys.stderr.write("!! found a better path")
    sys.stderr.write(" ncalls = %d max_tcool = %.3f extime = %.3f\n"  % (ncalls,Q_maxtc,Q_extime))
    Qbest = Q
    return Qbest, ncalls
  
  # Did we do enough work?
  if Qbest != None and maxcalls != None and ncalls >= maxcalls: 
    return Qbest, ncalls
    
  # Try to extend {Q} with each of the blocks in {BSR}, in all possible choices:
  BCPS = candidates(BSR, path.pfin(Q), CSR) # Sorted in "most promising first" order
  for bcp in BCPS:
    bc, ip = block.unpack(bcp)
    P = block.choice(bc, ip)# Get the candidate path.
    use_jumps = False
    Qplus = path.concat((Q, P), use_jumps, parms) # Extend the tentative path.
    Qplus_maxtc = max(Q_maxtc, contact.max_tcool(Qplus, CSR))
    BSminus = remove_block(BSR, bc)
    CSminus = remove_contacts(CSR, Q, bcp)
    Qbest, ncalls = best_path_aux \
      ( Qplus, BSminus, CSminus, Delta, maxcalls, 
        Q_maxtc = Qplus_maxtc, ncalls = ncalls, lev = lev+1, 
        Qbest = Qbest, parms = parms
      )
    # Did we do enough work:
    if Qbest != None and maxcalls != None and ncalls > maxcalls:
      return Qbest, ncalls
  # We tried all possible extensions of {Q}:
  return Qbest, ncalls
    
def remove_block(BSR, bc):
  # The parameter {BSR} must be a list or tuple of {Block} objects,
  # and {bc} must one of its elements.
  #
  # Returns a copy of the block set {BSR} minus the block {bc}. Does not change {BSR}.
  assert type(BSR) is list or type(BSR) is tuple
  assert isinstance(bc, block.Block)
  BSminus = tuple(bcx for bcx in BSR if bcx != bc)
  assert len(BSminus) == len(BSR) - 1
  return BSminus

def remove_contacts(CSR, Q, bcp):
  # The parameter {CSR} must be a tuple or list of contacts, {Q} must be a 
  # {Path} object, and {bcp = (bc,ip)} must be a block pick.
  #
  # Removes from the contact set {CSR} all contacts that will become
  # irrelevant once the path {Q} is extended by the oriented
  # path {P=block.choice(bc,ip)}.
  
  assert type(CSR) is list or type(CSR) is tuple
  CSminus = tuple(ctx for ctx in CSR if not exclude_contact(ctx, Q, bcp))
  return CSminus

def exclude_contact(ct, Q, bcp):
  # The parameter {ct} must be a {Contact} object, {Q} must be a 
  # {Path} object, and {bcp = (bc,ip)} must be a block pick.
  #
  # Returns {True} iff the contact {ct} will become
  # irrelevant once the path {Q} is extended by the oriented
  # path {P=block.choice(bc,ip)}.
  #
  # That is the case if {ct} is covered on both sides by traces
  # from {Q} or {P}, or if it involves any trace from any other 
  # alternative of {bc} that is not a trace of {P}.
  assert isinstance(ct, contact.Contact)
  assert isinstance(Q, path.Path)
  bc, ip = block.unpack(bcp)
  P = block.choice(bc, ip)
  nsc = 0 # Number of sides of {ct} covered by traces from {P} or {Q}.
  side = [ None, None ] # {side[0..nsides-1]} are those traces.
  for oph in Q, P:
    for k in range(path.nelems(oph)):
      omvk = path.elem(oph, k)
      mvk, drk = move.unpack(omvk)
      if mvk == contact.side(ct,0) or mvk == contact.side(ct,1):
        assert not move.is_jump(mvk)
        assert nsc < 2
        side[nsc] = mvk
        nsc = nsc + 1
  if nsc == 2: 
    # Contact will be closed once {P} is added to {Q}.
    return True
    
  # Now check if the any uncovered side of {ct} is on other choices of {bc}:
  assert nsc <= 1
  nch = block.nchoices(bc)
  for jp in range(nch):
    if jp != ip:
      och = block.choice(bc, jp) # A different alternative of {bc}
      for k in range(path.nelems(oph)):
        omvk = path.elem(oph, k)
        mvk, drk = move.unpack(omvk)
        # Check if move {mvk} is a side of the contact, but is not in {P}.
        if mvk == contact.side(ct,0) or mvk == contact.side(ct,1):
          assert not move.is_jump(mvk)
          if nsc == 0 or mvk != side[0]:
            # This contact will disappear once the choices of {bc} other than {P} are excluded:
            return True

  # The contact will still be relevant:
  return False

def predtcool(Q, Q_maxtc, BSR, CSR, parms):
  # The procedure receives the current tentative path {Q}, the maximum
  # cooling time {Q_maxtc} of all the originsl contacts that are closed
  # by it, the list {BSR} of the blocks that have not yet been included
  # in it, and the list {CSR} of contacts that are still relevant for
  # {BSR}. It returns a float {tm) such that
  # {contact.max_tcool(Qex,CS,parms) >= tm} for every path {Qex} that is
  # an extension of {Q} with some choice from every block in {BSR}, in
  # any orders; where {CS} is the original set of contacts.
  #
  # Assumes that {Q_maxtc} is {contact.max_tcool(Q, CS \setminus CSR)}.
  # Estimate the worst cooling time for active contacts:
  maxtc_active = path.extime(Q) - contact.min_tcov(Q, CSR)
  return max(Q_maxtc, maxtc_active)
  
def block_pini_dist(p, bcp):
  # Returns the distance from point {p} and the nearest endpoint of the
  # path that is the block pick {bcp}.
  bc, ip = block.unpack(bcp)
  oph = block.choice(bc, ip)
  dmin = min(rn.dist(p, path.pini(oph)), rn.dist(p, path.pfin(oph)))
  return dmin

def candidates(BSR, p, CSR):
  # Given the list {BSR} of blocks that have not been incorporated yet in
  # {Q}, the final point {p} of {Q}, and the list of still-relevant
  # contacts {CSR}, returns the list {BCPS} of candidates for the next
  # element to be added to {Q}. That is alist of block picks, containing
  # all possible picks from all blocks of {BSR}, sorted by priority order.
  
  def opdist(bcp):
    bc, ip = block.unpack(bcp)
    oph = block.choice(bc, ip)
    d = rn.dist(p, path.pini(oph))
    return d

  KS = []
  for bc in BSR:
    np = block.nchoices(bc)
    for ip in range(np):
      bcp = (bc, ip)
      KS.append(bcp)
  KS.sort(key=opdist)
  return tuple(KS)
  
def rest_min_extime(BSR):
  # Given the list{BSR} of blocks that have not been yet included in the
  # tentative tool-path, returns an estimate of the minimum time needed to
  # execute them, even if the best alternative could be chosen in each
  # block.
  mex = 0
  for bc in BSR:
    mex += block.min_extime(bc)
  return mex

def blocks_min_starttime(p, BSR, parms):
  # Given a point {p} and the list {BSR} of blocks that have not been yet
  # included in the tentative tool-path, returns the minimum time needed
  # to jump to the nearest starting point of any choice of any of those
  # blocks.
  dmin = +inf
  for bc in BSR:
    for ip in range(block.nchoices(bc)):
      oph = block.choice(bc, ip)
      di = rn.dist(p, path.pini(oph))
      if di < dmin: dmin = di
  assert dmin != +inf
  tmin = move.nozzle_travel_time(dmin, True, None, parms)
  return tmin
  # ----------------------------------------------------------------------

def blocks_min_max_tcool(CSR,BSR,parms):
  # Given a list of contacts {CSR} and a list of blocks {BSR}, returns a
  # lower bound to the value of {contact.max_tcool(P,CSR)} for any path {P}
  # built from those blocks.
  #
  # The list {CSR} must contain only relevant contacts, that have at least 
  # one side covered by one of blocks of {BSR}.
  #
  # For each contact {ct} of {CSR}, it finds the two blocks {bc0} and {bc1}
  # of {BSR} that include the sides of {ct}. They must both exist, be
  # unique, and distinct. Computes a min cooling time {tcm(ct)} assuming
  # that the best possible choices {ph0,ph1} of those blocks that contain
  # the sides of {ct} are added in sequence to the tool-path. Ignores any
  # choice of either block that does not contain those sides, assuming
  # that the contact {ct} will become irrelevant if that choice is
  # selected for the tool-path.
  #
  # Then it returns the maximum of {tcm(ct)} among all contacts {ct} of {CSR}.
  # If {CSR} is empty, returns 0.
  tcmax = 0
  for ct in CSR:
    tcmin = contact.blocks_min_tcool(BSR, ct, parms)
    assert tcmin < +inf, "some side of a contact is not covered by {BSR}"
    if tcmin > tcmax: tcmax = tcmin
  return tcmax
  # ----------------------------------------------------------------------
      
def blocks_avg_choices(BS):
  # Returns the geometric average of the number of choices 
  # of the blocks in the list {BS}.
  slog = 0
  for bc in BS:
    np = block.nchoices(bc)
    assert np >=1
    slog += log(np)
  avg = exp(slog/len(BS))
  return avg

def describe_input(wr, o, BS, CS, Delta, maxcalls, parms):
  # Prints main attributes of the {best_path} input data to 
  # file {wr} in human-readable form.

  wr.write("contact x block table:\n")
  wr.write("\n")
  block.print_contact_table(sys.stderr, BS, CS, None)
  wr.write("\n")

  wr.write("number of blocks = %d\n" % len(BS))
  wr.write("average choices per block = %.3f\n" % blocks_avg_choices(BS))
  wr.write("lower bound to execution time = %.3f s\n" % (blocks_min_starttime(o,BS,parms) + rest_min_extime(BS)))
  wr.write("number of contacts = %d\n" % len(CS))
  minmaxtc = blocks_min_max_tcool(CS,BS,parms)
  wr.write("lower bound to max cooling time = %.3f s\n" % minmaxtc)
  if Delta == +inf:
    wr.write("no limit on cooling time\n")
  else:
    wr.write("max allowed cooling time = %.3f s\n" % Delta)
  assert minmaxtc <= Delta, "** oops - {Delta} is too small for {CS,BS}"
  if maxcalls == None:
    wr.write("no limit on number of calls\n")
  else:
    wr.write("max allowed calls = %d\n" % maxcalls)
  return
  # ----------------------------------------------------------------------