# Tools and types to handle precomputed subpaths for the HotPath heuristic.
# Last edited on 2021-02-19 14:18:56 by jstolfi

import block_IMP; from block_IMP import Block_IMP

class Block(Block_IMP):
  # An object {bc} of class {Block} represents a /block/, a collection
  # of /alternative paths/ that can be used to create some specific of
  # part the slice. If the block {bc} has {n} alternatives, the function
  # {choice(bc,ip)} below returns the alternative path with index {ip} in
  # {0..n-1}.
  #
  # In a simple example, let {P1,...,Pm} be a set {m >= 2} raster lines
  # lying on consecutive scan lines, each making significant contact only
  # with the previous and following ones; except that {P1} may have
  # contacts with zero or more than one rasters below it, and {Pm} may
  # have contacts with zero or more than one above it. We may decide that
  # those rasters are to be executed consecutively, in alternating
  # directions. There are four ways to do that: one can start from {P1} or
  # from {Pm}, and the starting raster line may be executed from left to
  # right or from right to left.  These four alternative paths are actually
  # two distinct paths {Q0} and {Q1} and their reversals. While {Q0} and
  # {Q1} have the same raster traces, they have different /connectors/ --
  # extra jumps, traces, or paths that connect one end of one raster line
  # to the startof the next one. Therefore {Q0} and {Q1} will usually
  # have different execution times and different relative covering times for 
  # external contacts.
  #
  # By joining those rasters into a block, the user is specifying that
  # exactly one of these four choices -- {Q0}, {Q1}, {rev(Q0)}, or
  # {rev(Q1)} -- should be inserted into the final tool-path, as a a
  # single stretch of consecutive moves.
  #
  # As another example, a component of the slice's contour -- such as a
  # hole or an ``island'' -- can be represented as a block of {m} paths.
  # Each path covers the same trajectory in the same direction, but starts
  # and ends at a different point. Note that in this case it is pointless
  # to consider the reversals of those {m} paths. More generally, if a
  # choice {P} for a block begins and ends at almost the same point, it is
  # pointless to include {rev(P)} as another possible choice.
  #
  # Joining several elementary paths of the input data set into blocks
  # greatly simplifies the path optimization problem, by reducing the
  # number of choices from {2^N*N!} for {N} paths to {K^M} for {M} blocks,
  # each with a geometric average of {K} choices (including reversals when
  # applicable). 
  #
  # This alternative also saves computing time by making it unnecessary to
  # recompute the cover and cooling times of contacts between traces of the
  # same alternative of a block, since their cooling times are fixed and
  # can be checked against the cooling limit {Delta} as the block is
  # created.
  #
  # On the other hand, by limiting the choices of the heuristic, this
  # optimization may prevent it from finding the optimal path. It may even
  # make the problem unsolvable, if a block is so large that doing it all
  # in one go would inevitably violate some cooling constraints elsewhere.
  # Still, if the blocks are chosen judiciously, this negative aspect may
  # be minimized. In fact, this optimization may result in a better final
  # path, because it would prevent the heuristic from finding some expensive
  # paths and stopping there.
  #
  # ASSEMBLING THE BLOCKS
  #
  # In general, one should consider joining several elements of the
  # original problem into a block only if they are close to each other
  # and mostly far from the rest of the slice; so that a good path is
  # very likely to execute them consecutively, once it starts with any
  # of them.
  #
  # For simple blocks, like sequences of adjacent scan lines or the
  # traces that make up a closed contour line, the choices that are
  # worth considering can be identified and constructed by ad-hoc
  # procedures. In more complex situations, one may have to use the
  # heuristic itself to choose the alternative paths.
  #
  # For instance, if the block is to consist of the contours of six
  # small islands arranged in a circle, somewhat distant from the rest
  # of the slice, it may be desirable to precompute some or all of the
  # {6*5/2 = 15} optimal tool-paths that trace the six contours in one
  # go, begining and ending at the outermost point of each pair of
  # contours. That pre-processing may still be better than letting each
  # island be a separate input element, and letting the heuristic
  # discover by trial and error that those contours are indeed better
  # executed consecutively and *repeadly* try to find the optimal order
  # among all the {6! = 120} possibilities.
  #
  # BLOCK PICKS
  #
  # A /block pick/ is a pair (2-tuple) {bcp = (bc, ip)} where {bc}
  # is a {Block} object, {ip} is an integer code in {i=0,1,...n-1},
  # and {n} is the number of choices.  It specfies that alternative
  # path {ip} of {bc} is to be used.
  pass

def from_paths(ophs):
  # Creates and returns a {Block} object {bc} whose alternatives are the 
  # oriented paths in the list or tuple {ophs}.  Specifically, {choice(bc,i)}
  # will be {ophs[i]} for {i=0,1,...,n-1} where {n=len(ophs)}.
  #
  # The list must have at least one path. It does not make sense for a
  # choice to be an empty path (with zero moves), or to begin or end
  # with a jump.
  #
  # Note that if a path {oph} its to be considered in its two possible
  # directions, both {oph} and {path.rev(oph)} must be included in
  # the list {ophs}.  This only makes sense if the path's initial
  # and final point are well-spaced, or there will be cooling constraints
  # between some of its traces and other blocks.
  return block_IMP.from_paths(ophs)
  
def nchoices(bc):
  # Returns the number of choices in the {Block} object {bc}.
  return block_IMP.nchoices(bc)
  
def choice(bc, ip):
  # Returns the oriented path which is the alternative of index {ip} 
  # of the block {bc}. The index {ip} must be in
  # {0..n-1} where {nel=nchoices(bc)}.
  return block_IMP.choice(bc, ip) 
  
def pick(bcp):
  # Given a block pick {bcp=(bc,ip)}, returns {choice(bc,ip)}.
  return block_IMP.pick(bcp) 
  
def unpack(bcp):
  # Given a block pick {bcp = (bc,ic)}, returns the unoriented {Block} object {bc}
  # and the choice index {c} separate results.
  #
  # It is equivalent to the unpacking assignment {bc,ic = bcp}, except that 
  # it performs some type checking.
  return block_IMP.unpack(bcp)

def bbox(bc):
  # Returns the bounding box of all choices of the {Block} object {bc},
  # as a pair of points {(plo, phi)} that its lower left and upper right
  # corners. 
  #
  # The box is the smallest axis-aligned rectangle that 
  # contains all the endpoints of all moves of all choices of {bc}.
  # Note that it does not contain the sausages of the traces or the 
  # full width of axes, dots, and arrowheads.
  return block_IMP.bbox(bc)

def has_move(bc, mv):
  # Returns {True} if and only if one of the choices of block {bc}
  # includes the move {mv}.
  return block_IMP.has_move(bc, mv)

def min_extime(bc):
  # Returns the minimum of {path.extime(oph)} for all choices {oph} of 
  # block {bc}.
  return block_IMP.min_extime(bc)

# PLOTTING

def plot(c, bc, org, waxes, axes, dots, arrows, matter):
  # Plots onto the {pyx} canvas {c} the choices of block {bc}, as a
  # a vertical stack of sub-plots. 
  #
  # Each choice is plotted with traces of a distinctive color. The whole plot is
  # shifted by {org}. The parameters {wdaxes,axes,dots,arrows,matter} are
  # as in {path.plot_standard}.
  return block_IMP.plot(c, bc, org, waxes, axes, dots, arrows, matter)
  
# DEBUGGING AND TESTING

def validate(bcp):
  # Runs some consistency checks on the block pick {bcp}.  Aborts with assert failure
  # if it detects any errors.  Also accepts a naked {Block} object.
  block_IMP.validate(bcp)

def create_test_data(parms):
  # Returns four results: a list {MS} of non-jump {Move} objects, a list
  # {PS} of oriented paths that use some of those traces, a list {CS} of
  # contacts between some of those traces, and a list {BS} of blocks whose
  # choices incude some of those moves.
  #
  # The traces will have width {parms['solid_raster_width']}.
  return block_IMP.create_test_data(parms)
 
def print_contact_table(wr, BS, CS, MS):
  # Given a list {BS} of {Block} objects and a list {CS} of {Contact}
  # objects prints a table that shows which choice of which block contains
  # each side of each contact.
  #
  # Each row of the table starts with "C{I}:{S}" to mean side {S} (0 or 1) of 
  # contact {ct = CS[I]}.  Each column is headed with "B{J}:{P}" to mean choice {P}
  # of block {bc = BS[J]}.  The entry in that row and column is the index of the
  # trace {contact.side(ct,S)} (or its reverse) among the moves of the path;
  # or "---" if the trace does not occur in that path.
  #
  # If {MS} is not {None}, it must be a list of {Move} objects. In that case,
  # for each contact side, the index {L} of the move in that list is printed
  # as "M{L}" at the start of each row.
  return block_IMP.print_contact_table(wr, BS, CS, MS)