Compact Graphs

#his tree only descends


# This class acts on a single array, GCOUNT# and
# uses only indices in an unsafe manner
class garray:
 def __init__(self): # upper is the ienclosing block
  self.top = object.__new__(node)  # The G instance cannot call nde.init
  self.top.count = 1
  self.top.return_val = APPENDED
  self.top.value=counter
  self.top.itext = "Top"
  self.g =[]
  self.g.append(self.top)
  # Move a block up the array
 def MOVE(self,dest,src,num) :
  print("Move from ",src, " to ",dest, " count ",num)
  h=[]
  h[0:num] = self.g[src:src+num] # copy the source segment
  self.g[src:src+num] = self.g[dest:dest+num] #move list down
  self.g[dest:dest+num]=h[0:num] # replace
 def DELETE(self,i,num) : pass

 def APPEND(self,n) :
  self.g.append(n)
 def GET(self,i) :
  return(self.g[i])

 # class node operates as a linked graph
 # Bot may descend from the to only
 # mehods accumulae counts toet direct indices into the array

# recursion control constants
APPENDED = 0
CONTINUE = 1
BLOCK = 2
ERROR = 3
DONE = 4
# graph operators allow variable arg list
def NullFun(n,id,x=None) : # complete recursion
 n.return_val = CONTINUE
 print("Null ",n.count,id)
 return(n.return_val )
def JustDotsFun(n,id,x=None) : # Testing recursion
 n.return_val = BLOCK
 print("Dots ",n.count,id)
 return(n.return_val )
def IsEqualFun(n,id,x) : # Stop when x=y
 if  n == x['target'] : n.return_val = DONE
 if n.count  >= x['target'].count : n.result_val = BLOCK # the target is not inthis block
 return(n.return_val)
def UpdateFun(n,id,x) : # Stop when x=y
 if  n == x['target'] :
  print("found ")
  n.return_val = DONE
 else :
  n.count = n.count + x['offset']
 return(n.return_val)


global G
counter =0 # for testing
class node :
# G is an array of  node pointers s
 #inseret node self as the first element in upper
 def __init__(self,upper=None,t=None): # upper is the ienclosing block
  global counter
  self.count = 1 # count itself
  self.return_val = APPENDED
  self.value=counter
  self.itext = t
# if no enclosure,  do not call APPEND to G, do not install
  G.APPEND(self)
  if upper != None : upper.enclose(self)
  else : G.top.count = G.top.count+1  # this just appends a the pit, the bottom
  if len(G.g) != G.top.count : print("Count error ",G.top.count,len(G.g) )
  counter = counter+1
 def delete(self,i) :  pass
 
 # self prepends the new block
 def enclose(self,new) : #
  i = G.top.traverse(0,UpdateFun,dict(target=self,offset=new.count,func="Update"))
  k = self.traverse(i,IsEqualFun,dict(target=new,func="IsEqual")) # locate the new block
  G.MOVE(i+1,k,new.count)
  self.count = self.count + new.count
 
 # descend from the top and collect G_index going down
 def traverse(self,id,fun,arglist=None) :
  end = id + self.count # warning here, a function call may alter node values
  if fun(self,id,arglist) != CONTINUE : return(end)
  id = id + 1 # skip the anchor
  while id  < end  and (self.return_val == CONTINUE) :
   id = G.GET(id).traverse(id,fun,arglist)
  if self.return_val == BLOCK : self.return_val = CONTINUE
  return(end)

global G
# Utility printouts for test
VALUE = lambda i : G.g[i].value
COUNT = lambda i : G.g[i].count
RESULT = lambda i : G.g[i].return_val
ITEXT = lambda i : G.g[i].itext
def who(a,b) :
 print(a.itext," with ",a.count,"  enclose ",b.itext," with count ",b.count," G count = ",len(G.g))
def peek() :
 print("Top count ",top.count," G count ",len(G.g))
 for i in range(len(G.g)) :
  print(i,COUNT(i),VALUE(i),RESULT(i),ITEXT(i))

# Some actual test code
G = garray()
top = G.top
top.itext='top'
oo = node(t ='Append1')
oo = node(t ='Append2')

x = node(top,'x')
y = node(x,'y')
z = node(top,'z')
k = node(z,'z')
m = node(z,'z')
#oo = node(top,t ='app',How=1)
#peek()

for i in range(10) :
 nn = node(top,str(i))
 print(nn.itext)
peek()
#top.traverse(0,NullFun,0)

No comments: