eic-opticks/analytic/treebuilder.py

0001 #!/usr/bin/env python
0002 #
0003 # Copyright (c) 2019 Opticks Team. All Rights Reserved.
0004 #
0005 # This file is part of Opticks
0006 # (see https://bitbucket.org/simoncblyth/opticks).
0007 #
0008 # Licensed under the Apache License, Version 2.0 (the "License");
0009 # you may not use this file except in compliance with the License.
0010 # You may obtain a copy of the License at
0011 #
0012 #   http://www.apache.org/licenses/LICENSE-2.0
0013 #
0014 # Unless required by applicable law or agreed to in writing, software
0015 # distributed under the License is distributed on an "AS IS" BASIS,
0016 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0017 # See the License for the specific language governing permissions and
0018 # limitations under the License.
0019 #
0020
0021 """
0022
0023 """
0024 import os, logging, numpy as np
0025 log = logging.getLogger(__name__)
0026
0027 from opticks.analytic.csg import CSG
0028
0029
0030 class TreeBuilder(object):
0031     @classmethod
0032     def balance(cls, tree):
0033         """
0034         Note that positivization is done inplace whereas
0035         the balanced tree is created separately
0036         """
0037         if not tree.is_positive_form():
0038             log.fatal("cannot balance tree that is not in positive form")
0039             assert 0
0040         pass
0041         ops = tree.operators_()
0042         hops = tree.operators_(minsubdepth=2)   # operators above the bileaf operators
0043
0044         if len(ops) == 1:
0045             op = ops[0]
0046             prims = tree.primitives()
0047             balanced = cls.commontree(op, prims, tree.name+"_prim_balanced" )
0048         elif len(hops) == 1:
0049             op = hops[0]
0050             bileafs = tree.subtrees_(subdepth=1)
0051             balanced = cls.bileaftree(op, bileafs, tree.name+"_bileaf_balanced" )
0052         else:
0053             log.warning("balancing trees of this structure not implemented, tree %r " % tree)
0054             tree.meta.update(err="TreeBuilder.balance fail")
0055             balanced = tree
0056         pass
0057         return balanced
0058
0059     @classmethod
0060     def bileaftree(cls, operator, bileafs, name):
0061         tb = TreeBuilder(bileafs, operator=operator, bileaf=True)
0062         root = tb.root
0063         root.name = name
0064         root.analyse()
0065         return root
0066
0067     @classmethod
0068     def commontree(cls, operator, primitives, name):
0069         """
0070         :param operator: CSG enum int
0071         :param primitives: list of CSG instances
0072         :param name:
0073         :return root: CSG instance for root node
0074         """
0075         tb = TreeBuilder(primitives, operator=operator)
0076         root = tb.root
0077         root.name = name
0078         root.analyse()
0079         return root
0080
0081     @classmethod
0082     def uniontree(cls, primitives, name):
0083         return cls.commontree(CSG.UNION, primitives, name )
0084
0085     @classmethod
0086     def intersectiontree(cls, primitives, name):
0087         return cls.commontree(CSG.INTERSECTION, primitives, name )
0088
0089
0090     def __init__(self, subs, operator=CSG.UNION, bileaf=False):
0091         """
0092         :param subs: list of CSG instance primitives or bileafs when bileaf is True
0093         """
0094         self.operator = operator
0095
0096         if not bileaf:
0097             nprim = len(list(map(lambda n:n.is_primitive, subs)))
0098             assert nprim == len(subs) and nprim > 0
0099         else:
0100             nbileaf = len(list(map(lambda n:n.is_bileaf, subs)))
0101             assert nbileaf == len(subs) and nbileaf > 0
0102             nprim = 2*nbileaf
0103             log.debug("TreeBuilder bileaf mode, nbileaf: %s nprim:%s " % (nbileaf, nprim))
0104         pass
0105         self.nprim = nprim
0106         self.subs = subs
0107
0108         # find complete binary tree height sufficient for nprim leaves
0109         #
0110         #     height: 0, 1, 2, 3,  4,  5,  6,   7,   8,   9,   10,
0111         #     tprim : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
0112         #
0113         height = -1
0114         for h in range(10):
0115             tprim = 1 << h
0116             if tprim >= nprim:
0117                 height = h
0118                 break
0119             pass
0120         pass
0121         assert height > -1
0122
0123         log.debug("TreeBuilder nprim:%d required height:%d " % (nprim, height))
0124         self.height = height
0125
0126         if not bileaf:
0127             if height == 0:
0128                 assert len(subs) == 1
0129                 root = subs[0]
0130             else:
0131                 root = self.build(height, placeholder=CSG.ZERO)
0132                 self.populate(root, subs[::-1])
0133                 self.prune(root)
0134             pass
0135         else:
0136             assert height > 0
0137             root = self.build(height-1, placeholder=CSG.ZERO)   # bileaf are 2 levels, so height - 1
0138             self.populate(root, subs[::-1])
0139             self.prune(root)
0140         pass
0141         self.root = root
0142
0143     def build(self, height, placeholder=CSG.ZERO):
0144         """
0145         Build complete binary tree with all operators the same
0146         and CSG.ZERO placeholders for elevation 0
0147         """
0148         def build_r(elevation, operator):
0149             if elevation > 1:
0150                 node = CSG(operator, name="treebuilder_midop")
0151                 node.left  = build_r(elevation-1, operator)
0152                 node.right = build_r(elevation-1, operator)
0153             else:
0154                 node = CSG(operator, name="treebuilder_bileaf")
0155                 node.left = CSG(placeholder, name="treebuilder_bileaf_left")
0156                 node.right = CSG(placeholder, name="treebuilder_bilead_right")
0157             pass
0158             return node
0159         pass
0160         root = build_r(height, self.operator )
0161         return root
0162
0163     def populate(self, root, subs):
0164         """
0165         :param root: CSG operator instance for root node
0166         :param subs: reversed list of the CSG instance primitive baubles to be hung on the tree
0167
0168         During an inorder traverse of the complete binary tree,
0169         the placeholder CSG.ZERO leaves are replaced with primitives
0170         popped off the subs list.
0171         """
0172         inorder = root.inorder_()
0173         log.debug("populate filling tree of %d nodes with %d subs " % (len(inorder),len(subs)))
0174
0175         for node in inorder:
0176             if node.is_operator:
0177                 try:
0178                     if node.left.is_zero:
0179                         node.left = subs.pop()
0180                     if node.right.is_zero:
0181                         node.right = subs.pop()
0182                     pass
0183                 except IndexError:
0184                     pass
0185                 pass
0186             pass
0187         pass
0188
0189     def prune(self, root):
0190         """
0191         Pulling leaves partnered with CSG.ZERO up to a higher elevation.
0192         """
0193         def prune_r(node):
0194             if node is None:return
0195             if node.is_operator:
0196                 prune_r(node.left)
0197                 prune_r(node.right)
0198
0199                 # postorder visit
0200                 if node.left.is_lrzero:
0201                     node.left = CSG(CSG.ZERO)
0202                 elif node.left.is_rzero:
0203                     ll = node.left.left
0204                     node.left = ll
0205                 pass
0206                 if node.right.is_lrzero:
0207                     node.right = CSG(CSG.ZERO)
0208                 elif node.right.is_rzero:
0209                     rl = node.right.left
0210                     node.right = rl
0211                 pass
0212             pass
0213         pass
0214         prune_r(root)
0215
0216
0217
0218
0219 def test_treebuilder():
0220     log.info("test_treebuilder")
0221     sprim = "sphere box cone zsphere cylinder trapezoid"
0222     primitives = map(CSG, sprim.split() + sprim.split() )
0223     nprim = len(primitives)
0224
0225     for n in range(0,nprim):
0226         tb = TreeBuilder(primitives[0:n+1])
0227         tb.root.analyse()
0228         print(tb.root.txt)
0229
0230 def test_uniontree():
0231     log.info("test_uniontree")
0232
0233     sprim = "sphere box cone zsphere cylinder trapezoid"
0234     primitives = map(CSG, sprim.split())
0235
0236     for n in range(0,len(primitives)):
0237         root = TreeBuilder.uniontree(primitives[0:n+1], name="test_uniontree")
0238         print("\n%s" % root.txt)
0239
0240
0241
0242
0243
0244 def test_balance():
0245     log.info("test_balance")
0246
0247     sprim = "sphere box cone zsphere cylinder trapezoid"
0248     primitives = map(CSG, sprim.split())
0249
0250     sp,bo,co,zs,cy,tr = primitives
0251
0252
0253     root = sp - bo - co - zs - cy - tr
0254
0255     root.analyse()
0256     #root.subdepth_()
0257
0258     print(root.txt)
0259
0260     prims = root.primitives()
0261     print("prims : %s " % repr(prims))
0262
0263     root.positivize()
0264
0265     balanced = TreeBuilder.balance(root)
0266     print(balanced.txt)
0267
0268
0269 def make_bileaf(name):
0270     outer = CSG("cylinder", name=name+"_outer")
0271     inner = CSG("cylinder", name=name+"_inner")
0272     tube = outer - inner
0273     return  tube
0274
0275 def test_balance_bileaf():
0276     log.info("test_balance_bileaf")
0277
0278     a = make_bileaf("a")
0279     b = make_bileaf("b")
0280     c = make_bileaf("c")
0281     d = make_bileaf("d")
0282     e = make_bileaf("e")
0283     f = make_bileaf("f")
0284     g = make_bileaf("g")
0285
0286     roots = []
0287     roots.append(a)
0288     roots.append(a+b)
0289     roots.append(a+b+c)
0290     roots.append(a+b+c+d)
0291     roots.append(a+b+c+d+e)
0292     roots.append(a+b+c+d+e+f)
0293     roots.append(a+b+c+d+e+f+g)
0294
0295     for root in roots:
0296         root.analyse()
0297         root.positivize()
0298
0299         print(root.txt)
0300         balanced = TreeBuilder.balance(root)
0301
0302         print(balanced.txt)
0303     pass
0304
0305
0306
0307 if __name__ == '__main__':
0308     pass
0309     logging.basicConfig(level=logging.INFO)
0310
0311     #test_treebuilder()
0312     #test_uniontree()
0313     test_balance()
0314     #test_balance_bileaf()
0315
0316