SVOdocs

Figure1.svg

postorder_traverse.exp.py

from collections import deque
import collections

class Node:
    def __init__(self, node=None):
        self.parent = node
        self.children = []
        self.value = None






def linear_tree(levels):
    root = Node()
    root.value = (0,'>')
    
    stack = [root]
    
    while len(stack):
        node = stack.pop()
        
        level,name = node.value
        
        if level < levels:
            for i in range(8):
                child_node = Node(node)
                child_name = name + '.%s' % i
                child_node.value = (level+1, child_name)
                node.children += [child_node]
                stack.append(child_node)
    return root






def postorder_traverse(node0, visitor):

    stack = [ node0 ]
    
    #///{node => completed metadata}
    finished_node_metadata = {}
    
    #///{node => completed child count}
    node_children_completed = collections.defaultdict(int)
    while len(stack):
    
        node = stack.pop()

        assert node is not None
        assert node.children is not None
        assert node not in finished_node_metadata
        
        
        if len(node.children) == 0:
        
            assert node not in node_children_completed
            
            metadata = visitor(node, [])
            finished_node_metadata[node] = metadata
            node_children_completed[node.parent] += 1
            assert node not in node_children_completed
            continue
        
        
        assert len(node.children) > 0
        
        #this node has not been visited before
        if node not in node_children_completed:
            
            node_children_completed[node] = 0
            
            #put the node back on the stack.
            stack.append(node)
            
            
            #put the children on the stack
            
            siblings = []
            for child in node.children:
                siblings.append(child)
            
            
            #put them on in reverse order; so that they are processed in order.
            stack += reversed(siblings)
            
            
            continue
        
        assert len(node.children) > 0
        assert node in node_children_completed
        assert node_children_completed[node] == len(node.children)
        
        metadatas = []
        #collect children's metadata
        # and also erase them from the map.
        for child in node.children:

            assert child not in node_children_completed
            assert child in finished_node_metadata
            
            child_metadata = finished_node_metadata[child]
            
            metadatas.append(child_metadata);
            finished_node_metadata.pop(child);
        
        
        #viit this node.
        metadata = visitor(node, metadatas);
        
        #remember the metadata result
        finished_node_metadata[node] = metadata;
        
        #let the parent know this child completed.
        if node.parent:
            node_children_completed[node.parent] += 1;
        
        #stop tracking the children's visit status.
        assert node in node_children_completed
        node_children_completed.pop(node)
        
        assert node not in node_children_completed
        
        

    
    assert node0 is not None
    assert node0.children is not None
    assert len(node_children_completed) == 0
    assert len(finished_node_metadata) == 1
    assert node0 in finished_node_metadata
    
    metadata = finished_node_metadata[node0];
    return metadata;




def print_node(node, metadatas):
    print (node.value)


root = linear_tree(3)
postorder_traverse(root, print_node)

SVODocs.md

##block_classify_split_append()

This function is a callback that is meant to be called on a preorder traversal of the SVO. It:

1. Runs on each child_descriptor_t in the tree, in pre-order.
2. Classifies which child slice, each particular child_descriptor_t fits into (space-wise).
3. Or classifies it as not fitting into any (if it's space overlaps multiple children, such as the root node).

z_preorder_traverse.exp.py

from collections import deque

class Node:
    def __init__(self, node=None):
        self.parent = node
        self.children = []
        self.value = None






def linear_tree(levels):
    root = Node()
    root.value = (0,'>')
    
    stack = [root]
    
    while len(stack):
        node = stack.pop()
        
        level,name = node.value
        
        if level < levels:
            for i in range(8):
                child_node = Node(node)
                child_name = name + '.%s' % i
                child_node.value = (level+1, child_name)
                node.children += [child_node]
                stack.append(child_node)
    return root

def z_preorder_traverse(node0, visitor):

    siblings0 = tuple([node0])
    stack = deque([siblings0])
    
    while len(stack):
        print ('len(stack):', len(stack))
        nodes = stack.popleft()
        
        for node in nodes:
            if len(node.children) > 0:
                child_siblings = tuple(node.children)
                stack.append(child_siblings)
            visitor(node)


def z_preorder_traverse1(start_node, visitor):

    stack = deque([(0,start_node)])
    
    while len(stack):
        print ('len(stack):', len(stack))
        level,node0 = stack.pop()
        
        nodes = [node0]
        
        while len(stack):
            next_level, next_node = stack.pop()
            if next_level != level:
                stack.append( (next_level, next_node) )
            nodes += [next_node]
        
        for node in nodes:
            for child_node in node.children:
                stack.append( (level+1, child_node) )
            visitor(node)

def preorder_traverse(node0, visitor):

    parent_stack = []
    node = node0
    while len(parent_stack) > 0 or node is not None:
        #print ('parent_stack:', [pnode.value for pnode in parent_stack])
        if node is not None:
            visitor(node)
            
            if len(node.children) == 0:
                node = None
            else:
                next_node = node.children[0]
                for child in node.children[1:]:
                    parent_stack.append(child)
                node = next_node
        else:
            node = parent_stack.pop()


def z_preorder_traverse2(node0, visitor):
    visitor(node0)
    
    parent_stack = []
    node = node0
    while len(parent_stack) > 0 or node is not None:
        #print ('parent_stack:', [pnode.value for pnode in parent_stack])
        if node is not None:
            for child in node.children:
                visitor(child)
            
            if len(node.children) == 0:
                node = None
            else:
                next_node = node.children[0]
                for child in node.children[1:]:
                    parent_stack.append(child)
                node = next_node
        else:
            node = parent_stack.pop()
def print_node(node):
    print (node.value)


root = linear_tree(3)
z_preorder_traverse2(root, print_node)