# Implementation of module {raster_splitrivers}
# Last edited on 2021-07-29 06:34:59 by jstolfi

import block
import path
import path_hp
import move
import move_parms
import contact
import path_example
import raster
import block_example

import hacks
import rn

def doit(OPHS, ydir, Delta, Gamma):
  debug = False
  nph_old = len(OPHS)
  
  xdir = ( +ydir[1], -ydir[0] )
  
  # Separate fillers by group, with each group still sorted by scanline order:
  GRS_old, ngr_old = path_hp.separate_paths_by_group(OPHS)
  
  # Scan orig groups, splitting as requested:
  ngr_new = 0
  nph_new = 0
  for OPHS_gr in GRS_old:
    if OPHS_gr != None and len(OPHS_gr) > 0:
      # Split group into scanlines, preserving order:
      ystep, yphase = raster.get_spacing_and_phase(OPHS_gr, xdir, ydir)
      ngr_new = split_group_by_size(OPHS_gr, ngr_new, max_lines, xdir, ydir, ystep, yphase)
      nph_new += len(OPHS_gr)
  assert nph_new == nph_old
  return ngr_new
  # ----------------------------------------------------------------------
      
# INTERNAL PROCEDURES

def split_rasters_at_forks(OPHS, ngr):
  # Used by {split_at_forks}. Splits the rasters in {OPHS} into groups
  # at forks. Assumes that {ngr} groups have been created, and renumbers
  # the new groups starting at {ngr}. Returns the updated group count
  # {ngr}.

  OPHS_top = set()  # Top elements of still-incomplete new groups.

  # Each element of the set {OPHS_top} is the highest element (in the
  # {ydir} direction), among the elements processed so far, in some new
  # group that has not been completed yet.
  # 
  # Every element in that new group has exactly one contact on its upper
  # side (but not necessarily to an element of the input list {OPHS}).  
  # Every element in that new group, except the first one, has
  # exactly one contact on its lower side, to the element below it in the
  # same new group.
  
  ngr_new = ngr

  # Process the filler elements in of {OPHS} in order, assumed to
  # be lowest to highest in the {ydir} direction:
  for oph in OPHS:
    oph_added = try_adding_to_open_group(oph, OPHS_top)
    if oph_added == None:
      # Could not add {oph} to any existing new group.  
      # Create another new group just for it:
      path_hp.set_group(oph, ngr_new)
      ngr_new += 1
      OPHS_top.add(oph)

    # Check if the new sub-group is complete:
    CTS_hi = path_hp.get_contacts(oph, 1) # Contacts on upper edge of {oph}.
    if len(CTS_hi) != 1:
      # The new sub-group is complete:
      OPHS_top.remove(oph)

  # At this point new groups that are still open must have a single upper contact 
  # with elements in other old groups. Ignore them.

  return ngr_new
  # ----------------------------------------------------------------------

def try_adding_to_open_group(oph, OPHS_top):
  # Used by {split_rasters_at_forks}. 
  # Tries to add the path {oph} to one of the open groups whose
  # top elements are in {OPHS_top}. If it succeeds, replaces that top
  # element by {oph} and returns it. Otherwise, returns {None}.
  
  debug = True
  name_oph = path.get_name(oph)

  CTS_lo = path_hp.get_contacts(oph, 0) # Contacts on lower edge of {oph}.
  nct_lo = len(CTS_lo)
  if nct_lo != 1:
    # Element {oph} has no low-side contacts, or more than one such contact  
    # Cannot add to any existing group, no matter what those contacts are:
    if debug: sys.stderr.write("  raster %s has %d down-contacts, break\n" % (name_oph,nct_lo))
    return None
  else:
    # Element {oph} has only one low-side contact.  See if it matches 
    # any of the high-side contacts of the still open new groups:
    ct_lo = CTS_lo[0]
    name_ct_lo = contact.get_name(ct_lo)
    if debug: sys.stderr.write("  raster %s down contact is %s ..." % (name_oph,name_ct_lo))
    for oph_top in OPHS_top:
      # Consider adding {oph} to the open group of {oph_top}:
      CTS_top_hi = path_hp.get_contacts(oph_top, 1)
      nct_top_hi = len(CTS_top_hi)
      assert nct_top_hi == 1
      ct_top_hi = CTS_top_hi[0]
      name_ct_top_hi = contact.get_name(ct_top_hi)
      if debug: sys.stderr.write(" %s" % name_ct_top_hi)
      if ct_lo == ct_top_hi:
        # Contacts match. Add to new group:
        if debug: sys.stderr.write(" matched!\n")
        path_hp.set_group(oph, path_hp.get_group(oph_top))
        OPHS_top.remove(oph_top)
        OPHS_top.add(oph)
        return oph
    
    # Not continuation of any open group. Assume that the contact {ct_lo}
    # is with a path of some other old group:
    if debug: sys.stderr.write(" no match.\n")
    return None
  # ......................................................................

def split_group_by_size(OPHS, ngr, max_lines, xdir, ydir, ystep, yphase):
  # The input {OPHS} must be a list of raster flll elements.
  # Splits it into sub-groups consisting of at most {max_lines}
  # scanlines each.  Assumes that group indices {0..ngr-1} have been
  # assigned, and renumbers the new groups starting at {ngr}
  # Returns the updated number of groups {ngr}.
  
  debug = False
  nph_old = len(OPHS)

  SCS = raster.separate_by_scanline(OPHS, xdir, ydir, ystep, yphase)
  nsc_old = len(SCS) # Number of scanlines in group
  if debug: sys.stderr.write("  splitting group with %d scanlines (%d rasters): " % (nsc_old,nph_old))

  ngr_old = ngr
  ngr_new = ngr
  if nsc_old > 0:
    nph_new = 0      # Raster elements processed.
    nsc_new = 0      # Number of scanlines processed.
    isc = 0          # Index of next scanline to process.
    while isc < nsc_old > 0:
      nsc_rm = nsc_old - isc # Number of scanlines left to split
      # Decide number of subgroups {ngr_rm} in remaining scanlines:
      ngr_rm = (nsc_rm + max_lines - 1)//max_lines
      # Decide number of scanlines {nsc_gr} in next group:
      nsc_gr = int(floor(nsc_rm/ngr_rm + 0.5))
      assert nsc_gr <= max_lines
      if debug: sys.stderr.write(" %d (" % nsc_gr)

      # Unite scanlines in next chunk:
      isc_lim = min(nsc_old, isc + nsc_gr)
      while isc < isc_lim:
        # Assign fillers in scanline to group {ngr_new}:
        if debug: sys.stderr.write(" [%d:%d: " % (isc,len(SCS[isc])))
        for iph in SCS[isc]:
          oph = OPHS[iph]
          path_hp.set_group(oph, ngr_new)
          nph_new += 1
          if debug: sys.stderr.write("%s," % path.get_name(oph))
        if debug: sys.stderr.write("]")
        isc += 1
        nsc_new += 1
      if debug: sys.stderr.write(")")
      # One more new group defined:
      ngr_new += 1
      # Discount the scanlines processed:
      nsc_rm = nsc_rm - nsc_gr
  if debug: sys.stderr.write("\n")
  ngr_plus = ngr_new - ngr_old
  if debug: 
    sys.stderr.write("group was split into %d groups %d..%d" % (ngr_plus,ngr_old,ngr_new-1))
    sys.stderr.write(" (%d paths in %d scanlines)" % (nph_new, nsc_new))
  assert nsc_new == nsc_old
  assert nph_new == nph_old
  return ngr_new
  # ----------------------------------------------------------------------