# Implementation of module {trafo}.
# Last edited on 2021-09-24 19:47:21 by stolfi

import trafo
import sys

class Trafo_IMP:
  # An opaque class. users must sublass {trafo.Trafo} to get anything useful.
   
  def __init__(self,name):
    assert name != None, "name cannot be {None}"
    self.name = name
  
def get_name(T):
  if T == None:
    return "None"
  elif isinstance(T, trafo.Trafo):
    return T.name
  else:
    kinv, TL = unpack(T)
    if len(TL) == 0:
      x = "None"; 
      kinv = +1 # Inverse of {None} is {None}.
    elif len(TL) == 1:
      x = get_name(TL[0]);
    else:
      x = "" 
      sep = "("
      for Tk in TL:
        x = x + sep + get_name(Tk)
        sep = " "
      x = x + ")"
    if kinv < 0:
      if x[-1] == "'": 
        x = x[0:-1]
      else:
        x = x + "'"
    return x
  # ----------------------------------------------------------------------

def set_name(T, name):
  assert T != None, "cant' change name of {None}"
  if isinstance(T, trafo.Trafo):
    T.name = name
  else:
    kinv, TL = unpack(T)
    assert len(TL) == 1, "can't set the name of this trafo"
    x = name
    if kinv < 0:
      if x[-1] == "'": 
        x = x[0:-1]
      else:
        x = x + "'"
      set_name(TL[0], x);
  # ----------------------------------------------------------------------
 
def unpack(T):
  if T == None:
    return +1, ()
  elif isinstance(T, trafo.Trafo):
    return +1, (T,)
  else:
    assert type(T) is tuple, "{T} is neither {Trafo} obj nor tuple"
    assert len(T) >= 1, "length of {T} tuple is 0"
    kinv = T[0]
    assert type(kinv) is int
    assert kinv == +1 or kinv == -1
    TL = T[1:]
    return kinv, TL
  # ----------------------------------------------------------------------

def identity():
  return None
  # ----------------------------------------------------------------------
  
def is_identity(T):
  if T == None: return True
  if isinstance(T, trafo.Trafo): return False # Cannot tell.
  assert type(T) is tuple, "invalid trafo type"
  m = len(T)
  assert m > 0, "trafo cannot be empty tuple"
  if m == 1: return True # Composition of zero factors.
  if m == 2 and T[1] == None: return True # Redundant rep of identity.
  return False # Give up.
  # ----------------------------------------------------------------------

def inv(T):
  if T == None:
    return None
  elif isinstance(T, trafo.Trafo):
    return (-1, T)
  else:
    assert type(T) is tuple, "invalid trafo type"
    m = len(T)
    assert m > 0, "trafo cannot be empty tuple"
    if m == 1: return None
    kinv = T[0]
    assert type(kinv) is int and (kinv == +1 or kinv == -1), "invalid trafo inversion bit"
    if m == 2:
      if kinv > 0:
        return inv(T[1])
      else:
        return T[1]
    return (-kinv,) + T[1:]
  # ----------------------------------------------------------------------

def compose(TL):
  assert type(TL) is list or type(TL) is tuple, "{TL} must be list or tuple of trafos"
  TLnew = []
  for Tj in TL:
    if not is_identity(Tj): 
      TLnew += flatten(Tj)
  TLnew = reduce(TLnew)
  m = len(TLnew)
  if m == 0:
    return None
  elif m == 1:
    return TLnew[0]
  else:
    T = tuple([+1] + TLnew)
    return T
  # ----------------------------------------------------------------------

def simplify(T):
  if T == None: return None
  if isinstance(T, trafo.Trafo): return T  
  TL = reduce(flatten(T))
  if len(TL) == 0:
    return None
  elif len(TL) == 1:
    return TL[0]
  else:
    return tuple([+1] + TL)
  # ----------------------------------------------------------------------
  
def flatten(T):
  if T == None:
    return []
  elif isinstance(T, trafo.Trafo):
    return [T]
  else: 
    kinv, TL = unpack(T)
    if kinv == -1: TL = list(reversed(TL))
    Tnew = []
    for Tk in TL:
      if Tk == None:
        pass
      elif isinstance(Tk, trafo.Trafo):
        if kinv == -1:
          Tnew.append((-1,Tk))
        else:
          Tnew.append(Tk)
      else:
        if kinv == +1:
          TLk = flatten(Tk)
        elif kinv == -1:
          TLk = flatten(inv(Tk))
        Tnew = Tnew + TLk
    # sys.stderr.write("  T = %s\n  TL = %s\n  Tnew = %s\n" % (str(T), str(TL), str(Tnew)))
    return Tnew
  # ----------------------------------------------------------------------
      
def reduce(TL):
  Tnew = [] 
  n = 0 # Effective length of {Tnew}.
  for Tk in TL:
    if n > 0:
      T_prev = Tnew[n-1]
      Tcomb = reduce_pair(T_prev, Tk)
      if Tcomb == None:
        # Canceled:
        n = n-1
        pass
      elif isinstance(Tcomb, trafo.Trafo):
        # Reduced to a single Trafo object:
        Tnew[n-1] = Tcomb
      else:
        assert type(Tcomb) is tuple
        m = len(Tcomb)
        assert m >= 1, "bad condensation result"
        if m == 1:
          # Weird identity:
          n = n-1
          pass
        elif m == 2:
          # Condensed to one {Trafo} object:
          assert isinstance(Tcomb[1], trafo.Trafo), "bad condensation result"
          if Tcomb[0] == +1:
            Tnew[n-1] = Tcomb[1]
          elif Tcomb[0] == -1
            Tnew[n-1] = Tcomb
          else
            assert False, "bad condensation result"
        else:
          # Failed to combine:
          assert Tcomb = (+1 T_prev Tk), "bad condensation result"
          # Add element to {Tnew}:
          if n == len(Tnew):
            Tnew.append(Tk)
          else:
            Tnew[n] = Tk
          n = n + 1
              

    # At this point the first {n} elems of {Tnew} 
    # are the tentative result, and include no cancelling elems.
    # Check whether {Tk} cancels the last element:
    cancel = False
    if n > 0:
      T_prev = Tnew[n-1]
      sys.stderr.write("Tnew[%d] = %s\n" % (n-1, str(T_prev)))
      assert T_prev != None
      if isinstance(T_prev, trafo.Trafo):
        kinv_prev, Tobj_prev = +1, T_prev
      else:
        assert type(T_prev) is tuple and len(T_prev) == 2, "prog bug"
        kinv_prev, Tobj_prev = T_prev
        assert kinv_prev == -1, "prog bug"
        assert isinstance(Tobj_prev, trafo.Trafo)
  
      assert Tk != None, "list is not flat"
      if isinstance(Tk, trafo.Trafo):
        kinv_this, Tobj_this = +1, Tk
      else:
        assert type(Tk) is tuple and len(Tk) == 2, "list is not flat"
        kinv_this, Tobj_this = Tk
        assert kinv_this == -1, "list is not flat"
        assert isinstance(Tobj_this, trafo.Trafo)

      cancel = (Tobj_prev == Tobj_this and kinv_prev*kinv_this < 0)

    if cancel:
      # Element cancels the previous one:
      assert n > 0
      n = n-1
    else:
      # Add element to {Tnew}:
      if n == len(Tnew):
        Tnew.append(Tk)
      else:
        Tnew[n] = Tk
      n = n+1
  # Trim the list:
  return Tnew[0:n]
  # ----------------------------------------------------------------------