changeset 10:0a24625b33fa

checkNew improving, reverse pass failing
author Henry S. Thompson <ht@inf.ed.ac.uk>
date Sat, 14 Mar 2020 19:13:23 +0000
parents 28a7b0e992cb
children 1b9daa849b0f
files nono.py
diffstat 1 files changed, 65 insertions(+), 35 deletions(-) [+]
line wrap: on
line diff
--- a/nono.py	Wed Mar 11 22:06:04 2020 +0000
+++ b/nono.py	Sat Mar 14 19:13:23 2020 +0000
@@ -76,26 +76,35 @@
       if self.onepass(self.margin0,self.marginN+1,scratch,runs.copy()):
         wins+=1
     dprint(wins, scratch)
-    newSeq=False
-    inSeq=False
+    maybeSeq=None
+    inSeq=None
     for i in range(self.n):
       if scratch[i]==wins:
         # If blobby in _every_ pass, then must be a blob
-        if inSeq:
-          newSeq=False
-        else:
-          inSeq=True
-          newSeq=True
+        if inSeq is None:
+          inSeq=i if maybeSeq is None else maybeSeq
+          dprint('s1',inSeq)
+          maybeSeq=None
         if self[i].val is None:
-          self.newBlob(i,newSeq)
+          self.newBlob(i,True)         # Check cross-vector
         elif self[i].val is True:
           # already there
           pass
         else:
           print("Shouldn't happen: attempt to blob where x already present! %s at %s"%(self,i),file=sys.stderr)
           exit(101)
-      else:
-        inSeq=newSeq=False
+      elif inSeq is not None:
+        if self[i].val is not True:
+          inSeq=None
+          maybeSeq=None
+          dprint('s2',i-1)
+          self.checkNew(i-1)
+      elif self[i].val is True and maybeSeq is None:
+        dprint('s3',i)
+        maybeSeq=i
+    dprint('s4',inSeq,i)
+    if inSeq is not None:
+      self.checkNew(i)
 
   def onepass(self,i0,iBound,scratch,stack):
     """note that stack is not a simple run, but one with _negative_ numbers between
@@ -184,12 +193,13 @@
     c=self.runs.count(l)
     if c==0:
       # not big enough yet
-      dprint('n0')
+      dprint('x0')
       return
     if self.runs[0]==l:
       # is it safely left marginal, i.e. no blobs or big enough gaps before us?
       if self.marginal(range(self.margin0,s),l):
         changed=True
+        dprint('n1')
         # mark our margins
         for i in range(self.margin0+1,s):
           if self[i].val is None:
@@ -197,14 +207,19 @@
         if f<self.marginN-1:
           if self[f+1].val is None:
             self[f+1].setVal(False)
-            if f<self.marginN-2 and self[f+2].val is True:
-              dprint('n1')
-              self.checkNew(f+2) # I think@@
         self.found0(f) # pull in the start margin at least to f+2
+        if f<self.marginN-2 and self[f+2].val is True:
+          dprint('n1a')
+          self.checkNew(f+2) # I think@@
+      else:
+        dprint('x1a')
+    else:
+      dprint('x1b')
     if self.runs[-1]==l:
       # is it safely _right_ marginal, i.e. no blobs or big enough gaps _after_ us?
       if self.marginal(range(self.marginN-1,f,-1),l):
         changed=True
+        dprint('n2')
         # mark our margins
         for i in range(self.marginN-1,f,-1):
           if self[i].val is None:
@@ -212,10 +227,14 @@
         if s>self.margin0+1:
           if self[s-1].val is None:
             self[s-1].setVal(False)
-            if s>self.margin0+2 and self[s-2].val is True:
-              dprint('n2')
-              self.checkNew(s-2) # I think@@
         self.foundN(s) # pull in the finish margin at least to s-2
+        if s>self.margin0+2 and self[s-2].val is True:
+          dprint('n2a')
+          self.checkNew(s-2) # I think@@
+      else:
+        dprint('x2a')
+    else:
+      dprint('x2b')
     if changed:
       self.resetAllRuns()
 
@@ -223,6 +242,7 @@
     g=0 # length of a gap
     for i in rng:
       if self[i].val is True:
+        dprint('mx0')
         return False
       if self[i].val is False:
         g=0
@@ -230,6 +250,7 @@
         # None
         g+=1
         if g==l:
+          dprint('mx1')
           return False
     return True
 
@@ -266,7 +287,7 @@
     return ((self.fmt%(' '.join(str(r) for r in self.runs)))+
             Vector.__str__(self))
 
-  def updateHeader(self,maxWidth=None,r=None,pre=None):
+  def updateHeader(self,*,maxWidth=None,r=None,pre=None):
     if maxWidth is None:
       # update
       if pre:
@@ -283,12 +304,10 @@
       self.infix=""
       self.suffix=""
 
-  def newBlob(self,x,newSeq):
+  def newBlob(self,x,crossCheck=False):
     self[x].setVal(True)
-    self[x].column.checkNew(self.y)
-    if newSeq:
-      # We don't always check ourself, to avoid unnecessary duplication...
-      self.checkNew(x)
+    if crossCheck:
+      self[x].column.checkNew(self.y)
 
 class Column(Vector):
   def __init__(self,n,m,runs,pos):
@@ -296,18 +315,29 @@
     self.x=pos
     self.height=self.myPrintSize()
 
-  def updateHeader(self,maxHeight):
-    self.maxHeight=maxHeight
-    self.fmt="%s%%s"%(' '*(maxHeight - self.height))
-    header=('-'.join(str(c) for c in self.runs))
-    self.header=self.fmt%header # pad to same 'height'
+  def updateHeader(self,*,maxHeight=None,r=None,pre=None):
+    if maxHeight is None:
+      # update
+      if pre:
+        self.infix+=(RedFmt%r)+" "
+      else:
+        # post
+        self.suffix=" "+RedFmt%r+self.suffix
+      self.fmt="%s%s%%s%s"%(self.prespace,self.infix,self.suffix)
+    else:
+      # init
+      self.maxHeight=maxHeight
+      self.infix=""
+      self.suffix=""
+      header=('-'.join(str(c) for c in self.runs))
+      self.prespace=' '*(maxHeight - self.height) # pad to same 'height'
+      self.fmt="%s%%s"%self.prespace
+      self.header=self.fmt%header
 
-  def newBlob(self,y,newSeq):
+  def newBlob(self,y,crossCheck=False):
     self[y].setVal(True)
-    self[y].row.checkNew(self.x)
-    if newSeq:
-      # We don't always check ourself, to avoid unnecessary duplication...
-      self.checkNew(y)
+    if crossCheck:
+      self[y].row.checkNew(self.x)
 
 class Cell:
   def __init__(self,row,y,column,x):
@@ -352,11 +382,11 @@
     self.columns=cc=[Column(n,self,runsPerCol[i],i) for i in range(n)]
     self.maxCRheight=maxCRheight=max(col.height for col in cc)
     for c in cc:
-      c.updateHeader(maxCRheight)
+      c.updateHeader(maxHeight=maxCRheight)
     self.rows=rr=[Row(n,self,runsPerRow[i],i) for i in range(n)]
     maxRRwidth=max(row.width for row in rr)
     for r in rr:
-      r.updateHeader(maxRRwidth)
+      r.updateHeader(maxWidth=maxRRwidth)
     self.rowfmt="%s|%%s|"%(' '*maxRRwidth)
     for x in range(n):
       for y in range(n):