eic-opticks/CSG/complete_binary_tree.py

0001 #!/usr/bin/env python
0002 """
0003 """
0004 from opticks.analytic.textgrid import TextGrid
0005
0006 def inorder_(nds):
0007     """Return inorder sequence of nodes"""
0008     inorder = []
0009     def inorder_r(n):
0010         if n is 0:return
0011         nd = nds[n-1]
0012         inorder_r(nd.l)
0013         inorder.append(nd.o)
0014         inorder_r(nd.r)
0015     pass
0016     inorder_r(1)
0017     return inorder
0018
0019
0020 # https://codegolf.stackexchange.com/questions/177271/find-the-number-of-leading-zeroes-in-a-64-bit-integer
0021 f=lambda n:-1<n<2**63and-~f(2*n|1)   # clz : count leading zeros
0022
0023 def ffs(x):
0024     """Returns the index, counting from 0, of the least significant set bit in `x`."""
0025     return (x&-x).bit_length()-1
0026
0027 def tree_height(numNodes):
0028     """
0029     #define TREE_HEIGHT(numNodes) ( __ffs((numNodes) + 1) - 2)
0030     """
0031     return ffs(numNodes+1) - 1    ## maybe __ffs is off-by-1 from above ffs
0032
0033 class Nd(object):
0034     def __init__(self, o, numNode):
0035         l = (o << 1)
0036         r = (o << 1) + 1
0037         p = o >> 1
0038         d = 63-f(o)  # tree depth
0039
0040         self.o = o
0041         self.l = 0 if l > numNode else l
0042         self.r = 0 if r > numNode else r
0043         self.p = p
0044         self.d = d
0045
0046     def __repr__(self):
0047         return "Nd  p:{p:4b}    o:{o:4b} l:{l:4b} r:{r:4b}".format(o=self.o, l=self.l, r=self.r, p=self.p)
0048
0049 def inorder_tree(numNodes):
0050     """
0051     :param numNode:
0052     :return nn: array of 1-based level-order indices returned in-order
0053
0054     [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]
0055
0056                                     1
0057                       10                          11
0058                 100       101               110         111
0059              1000 1001 1100 1101        1100 1101     1110 1111
0060
0061               8  4 9  2 10 5  11    1    12 6 13   3 14  7  15
0062
0063     """
0064     nds = []
0065     for i in range(numNodes):
0066         nd = Nd(i+1, numNodes)
0067         nds.append(nd)
0068     pass
0069     nn = inorder_(nds)
0070     pass
0071     return nn
0072
0073 def layout_tree(nds):
0074     """
0075     :param nds: array of nodes in level-order (the usual serialization order)
0076     :return tree: TextGrid laying out the repr of the nodes
0077     """
0078     nn = inorder_tree(len(nds))
0079     width = len(nds)
0080     height = tree_height(len(nds))
0081
0082     tree = TextGrid(2*(height+1), width*2 )
0083     for i,n in enumerate(nn):
0084         nd = nds[n-1]
0085         depth = 63-f(n)
0086         tree.a[depth*2, i*2] = str(nd)
0087     pass
0088     return tree
0089
0090
0091 class N(object):
0092     def __init__(self, i):
0093         self.i = i
0094     def __repr__(self):
0095         return "N{obj.i:b}".format(obj=self)
0096
0097
0098 if __name__ == '__main__':
0099     #it = inorder_tree(15)
0100     #print(it)
0101     nds = list(map(lambda i:N(i+1), range(15)))
0102     tree = layout_tree(nds)
0103     print(tree)
0104
0105