thecere · March 29, 2012 19:37
diff --git a/variants.py b/variants.py
 # -*- coding: utf-8 -*-
 try:
    from lxml import etree
 except ImportError:
    import xml.etree.ElementTree as etree
 import StringIO
 import time
 from itertools import product

 s = """
 <document ID="28173" Description="Variantenvorschau" Source_ID="9" Source_Type="3" Sort="3"
    Parent_ID="28168" OT_ID="113777" OC_ID="71706" Status="0" ClientVersionText="ABS 11.5"
    OT_SV_ClientVersion="25" SV_InternalVersion="17" ClientVersionCaption="ABS 11.5"
    NodePath="|7496||28168||28173|" readonly="false">
    <!-- asd-->
    <body>
        <topic>
            <selection variable="x" description="erste Auswahl über x">
                <item value="1" description="x war 1" operator="=">
                    <p>Variante x war 1</p>
                </item>
                <item value="2" description="x war 2" operator="=">
                    <p>Variante x war 2</p>
                </item>
            </selection>
            <selection variable="y" description="erste Auswahl über y">
                <item description="Variante 1" value="1" operator="=">
                    <p>Variante y war 1</p>
                </item>
                <item description="Variante 2" value="2" operator="=">
                    <p>Variante y war 2</p>
                    <selection variable="x" description="zweite Auswahl über x">
                        <item description="Variante 1" value="5" operator="=">
                            <p>Variante y war 2 und x war 5</p>
                        </item>
                        <item description="Variante 2" value="6" operator="=">
                            <p>Variante y war 2 und x war 6</p>
                            <selection variable="z"
                                description="erste Auswahl über
                                    z">
                                <item description="Variante 1" value="23" operator="=">
                                    <p>Variante y war 2 und x war 6 und z war 23</p>
                                </item>
                                <default>
                                    <p>Variante y war 2 und x war 6 und z war NICHT 23</p>
                                </default>
                            </selection>
                        </item>
                    </selection>
                </item>
            </selection>
        </topic>
    </body>
 </document>
 """
 #~ s = open('t:/example.xml').read()
 #~ s = open('t:/fhapolice.xml').read()
 s = open('r:/reduced.xml').read()

 cmltree = etree.parse(StringIO.StringIO(s))

 class Node(object):
    COUNT = 0
    def __init__(self, parent=None, lines=None, level=None, sourceline=None, element=None):
        self.children = [] # Node() instances
        self.parent = parent
        self.sourceline = sourceline
        self.element = element
        
        if level is None:
            self.level = parent.level + 1 if parent is not None else 0
        else:
            self.level = level
            
        if parent is not None:
            parent.children.append(self)
        
        self.lines = lines if lines is not None else []
        
        Node.COUNT += 1
    
    def indent(self, i):
        return ' ' * (self.level + (0 if i == 0 else 1)) * 4
            
    def toCode(self, limit=None):
        lines = []
        # this one
        for i, line in enumerate(self.lines[:limit]):
            lines.append(self.indent(i) + line)
        # the chilren
        for node in self.children:
            lines.append(node.toCode(limit=limit))
        return '\n'.join(lines)
    
    def __repr__(self):
        return ': '.join([str(self.__class__.__name__)] + self.lines[:1])
    
    def getUniqueVars(self):
        uniqueVars = set()
        def _traverse(node):
            for child in node.children:
                if isinstance(child, IfNode) and child.condname != 'else':
                    
                    uniqueVars.add(child.varname)
                _traverse(child)
        _traverse(self)
        return uniqueVars
        
 class IfNode(Node):
    IFCOUNT = 0
    def __init__(self, condname, varname=None, operator=None, value=None, **kwargs):
        IfNode.IFCOUNT += 1
        _ = lambda s: (' %s' % s) if s else ''
        lines = ['%s%s%s%s:' % (condname, _(varname), _(operator), _(value)), 
                 'print "IF-NODE %s"' % IfNode.IFCOUNT]
        super(IfNode, self).__init__(lines=lines, **kwargs)
        
        self.condname = condname
        self.varname = varname
        self.operator = operator
        self.value = value
    
    
 class BranchNode(Node):
    def indent(self, i):
        return ' ' * (self.level + 1) * 4
    
    def __init__(self, parent, **kwargs):
        level = parent.level
        #~ lines = ['print "BRANCH"']
        lines = None
        super(BranchNode, self).__init__(parent=parent, level=level, lines=lines, **kwargs)
    
    #~ def getChoices(self):
        #~ if self.children[-1].condname == 'else':

    
    
 def construct(parent, node):
    for child in parent.findall('*'):
        
        if child.tag == 'selection':
            branch_node = BranchNode(node, sourceline=child.sourceline, element=child)
            varname = child.attrib['variable']
            items = child.findall('item')
            for i, item in enumerate(items):
                operator = item.attrib['operator']
                value = item.attrib.get('value', '')
                condname = 'if' if i == 0 else 'elif'
                operator = '==' if operator == '=' else operator
                
                child_node = IfNode(condname, varname, operator, value, parent=branch_node, sourceline=item.sourceline, element=item)
                construct(item, child_node)
            
            default = child.find('default')
            if default is not None:
                child_node = IfNode(condname='else', parent=branch_node, sourceline=default.sourceline, element=default)
                construct(item, child_node)
            #~ else:
                #~ IfNode(condname='else', parent=branch_node)
        else:
            construct(child, node)

   
 root_node = Node()
 construct(cmltree.getroot(), root_node)


 def checkFeasability(ifnodes):
    res = True    
    conds = {}
    for ifnode in ifnodes:
        if ifnode.operator == '==':
            if conds.get(ifnode.varname, ifnode.value) != ifnode.value:
                res = False
                break
            else:
                conds[ifnode.varname] = ifnode.value
    return res

 CACHE = {}    
 def analyse(levelnode):
    ''' return list of variants, a single variant is a list of IfNodes '''
    #~ print levelnode.level, levelnode, levelnode.sourceline
    
    if len(levelnode.children) == 0:
        assert isinstance(levelnode, IfNode)
        # its an IfNode without sub branches
        return [[levelnode]]
    
    variants_on_level = []
    childrenGroups = [branch.children for branch in levelnode.children]
    #~ print childrenGroups
    for children in product(*childrenGroups):
        variants = []
        # collect sub variants list for the current combination of ifnodes
        for ifchild in children:
            childvariants = CACHE.get(ifchild)
            if childvariants is None:
                CACHE[ifchild] = childvariants = analyse(ifchild)
            #~ print len(childvariants)
            variants.append(childvariants)
        
        j = 0
        # build combinations of sub variants 
        # thats the or-releation between BranchNodes at the same level
        for j, child_variant_combination in enumerate(product(*variants)):
            flattened = [levelnode] if isinstance(levelnode, IfNode) else []
            for ifnodes in child_variant_combination:
                flattened.extend(ifnodes)
            
            if checkFeasability(flattened):
                variants_on_level.append(flattened)
        
    
    return variants_on_level

 print root_node

 #~ for c in root_node.children[11:]:
    #~ c.element.getparent().remove(c.element)
 #~ open('r:/reduced.xml', 'w').write(etree.tostring(cmltree, pretty_print=True, encoding='utf-8', method='xml'))


 #~ root_node.children = root_node.children[:12]
 jj = 1
 for bn in root_node.children:
    print len(bn.children)
    jj *= len(bn.children)
 print jj

 #~ import sys; sys.exit()

 uniqueVars = root_node.getUniqueVars()
 print 'Num Unique Vars: %s' % len(uniqueVars)
 for uv in sorted(uniqueVars):
    print uv

 t = time.time()
 #~ _vlsdebug()
 variants = analyse(root_node)
 print 'count unfiltered variants: %s\n' % len(variants)
 print time.time() - t
 #~ for i,v in enumerate(variants, 1):
    #~ print i, v
    

 #~ print 'Python Repr:'
 #~ print root_node.toCode(2)
 #~ print
	# -- coding: utf-8 --
	try:
	from lxml import etree
	except ImportError:
	import xml.etree.ElementTree as etree
	import StringIO
	import time
	from itertools import product

	s = """
	<document ID="28173" Description="Variantenvorschau" Source_ID="9" Source_Type="3" Sort="3"
	Parent_ID="28168" OT_ID="113777" OC_ID="71706" Status="0" ClientVersionText="ABS 11.5"
	OT_SV_ClientVersion="25" SV_InternalVersion="17" ClientVersionCaption="ABS 11.5"
	NodePath="\|7496\|\|28168\|\|28173\|" readonly="false">
	<!-- asd-->
	<body>
	<topic>
	<selection variable="x" description="erste Auswahl über x">
	<item value="1" description="x war 1" operator="=">
	<p>Variante x war 1</p>
	</item>
	<item value="2" description="x war 2" operator="=">
	<p>Variante x war 2</p>
	</item>
	</selection>
	<selection variable="y" description="erste Auswahl über y">
	<item description="Variante 1" value="1" operator="=">
	<p>Variante y war 1</p>
	</item>
	<item description="Variante 2" value="2" operator="=">
	<p>Variante y war 2</p>
	<selection variable="x" description="zweite Auswahl über x">
	<item description="Variante 1" value="5" operator="=">
	<p>Variante y war 2 und x war 5</p>
	</item>
	<item description="Variante 2" value="6" operator="=">
	<p>Variante y war 2 und x war 6</p>
	<selection variable="z"
	description="erste Auswahl über
	z">
	<item description="Variante 1" value="23" operator="=">
	<p>Variante y war 2 und x war 6 und z war 23</p>
	</item>
	<default>
	<p>Variante y war 2 und x war 6 und z war NICHT 23</p>
	</default>
	</selection>
	</item>
	</selection>
	</item>
	</selection>
	</topic>
	</body>
	</document>
	"""
	#~ s = open('t:/example.xml').read()
	#~ s = open('t:/fhapolice.xml').read()
	s = open('r:/reduced.xml').read()

	cmltree = etree.parse(StringIO.StringIO(s))

	class Node(object):
	COUNT = 0
	def __init__(self, parent=None, lines=None, level=None, sourceline=None, element=None):
	self.children = [] # Node() instances
	self.parent = parent
	self.sourceline = sourceline
	self.element = element

	if level is None:
	self.level = parent.level + 1 if parent is not None else 0
	else:
	self.level = level

	if parent is not None:
	parent.children.append(self)

	self.lines = lines if lines is not None else []

	Node.COUNT += 1

	def indent(self, i):
	return ' ' * (self.level + (0 if i == 0 else 1)) * 4

	def toCode(self, limit=None):
	lines = []
	# this one
	for i, line in enumerate(self.lines[:limit]):
	lines.append(self.indent(i) + line)
	# the chilren
	for node in self.children:
	lines.append(node.toCode(limit=limit))
	return '\n'.join(lines)

	def __repr__(self):
	return ': '.join([str(self.__class__.__name__)] + self.lines[:1])

	def getUniqueVars(self):
	uniqueVars = set()
	def _traverse(node):
	for child in node.children:
	if isinstance(child, IfNode) and child.condname != 'else':

	uniqueVars.add(child.varname)
	_traverse(child)
	_traverse(self)
	return uniqueVars

	class IfNode(Node):
	IFCOUNT = 0
	def __init__(self, condname, varname=None, operator=None, value=None, **kwargs):
	IfNode.IFCOUNT += 1
	_ = lambda s: (' %s' % s) if s else ''
	lines = ['%s%s%s%s:' % (condname, _(varname), _(operator), _(value)),
	'print "IF-NODE %s"' % IfNode.IFCOUNT]
	super(IfNode, self).__init__(lines=lines, **kwargs)

	self.condname = condname
	self.varname = varname
	self.operator = operator
	self.value = value


	class BranchNode(Node):
	def indent(self, i):
	return ' ' * (self.level + 1) * 4

	def __init__(self, parent, **kwargs):
	level = parent.level
	#~ lines = ['print "BRANCH"']
	lines = None
	super(BranchNode, self).__init__(parent=parent, level=level, lines=lines, **kwargs)

	#~ def getChoices(self):
	#~ if self.children[-1].condname == 'else':



	def construct(parent, node):
	for child in parent.findall('*'):

	if child.tag == 'selection':
	branch_node = BranchNode(node, sourceline=child.sourceline, element=child)
	varname = child.attrib['variable']
	items = child.findall('item')
	for i, item in enumerate(items):
	operator = item.attrib['operator']
	value = item.attrib.get('value', '')
	condname = 'if' if i == 0 else 'elif'
	operator = '==' if operator == '=' else operator

	child_node = IfNode(condname, varname, operator, value, parent=branch_node, sourceline=item.sourceline, element=item)
	construct(item, child_node)

	default = child.find('default')
	if default is not None:
	child_node = IfNode(condname='else', parent=branch_node, sourceline=default.sourceline, element=default)
	construct(item, child_node)
	#~ else:
	#~ IfNode(condname='else', parent=branch_node)
	else:
	construct(child, node)


	root_node = Node()
	construct(cmltree.getroot(), root_node)


	def checkFeasability(ifnodes):
	res = True
	conds = {}
	for ifnode in ifnodes:
	if ifnode.operator == '==':
	if conds.get(ifnode.varname, ifnode.value) != ifnode.value:
	res = False
	break
	else:
	conds[ifnode.varname] = ifnode.value
	return res

	CACHE = {}
	def analyse(levelnode):
	''' return list of variants, a single variant is a list of IfNodes '''
	#~ print levelnode.level, levelnode, levelnode.sourceline

	if len(levelnode.children) == 0:
	assert isinstance(levelnode, IfNode)
	# its an IfNode without sub branches
	return [[levelnode]]

	variants_on_level = []
	childrenGroups = [branch.children for branch in levelnode.children]
	#~ print childrenGroups
	for children in product(*childrenGroups):
	variants = []
	# collect sub variants list for the current combination of ifnodes
	for ifchild in children:
	childvariants = CACHE.get(ifchild)
	if childvariants is None:
	CACHE[ifchild] = childvariants = analyse(ifchild)
	#~ print len(childvariants)
	variants.append(childvariants)

	j = 0
	# build combinations of sub variants
	# thats the or-releation between BranchNodes at the same level
	for j, child_variant_combination in enumerate(product(*variants)):
	flattened = [levelnode] if isinstance(levelnode, IfNode) else []
	for ifnodes in child_variant_combination:
	flattened.extend(ifnodes)

	if checkFeasability(flattened):
	variants_on_level.append(flattened)


	return variants_on_level

	print root_node

	#~ for c in root_node.children[11:]:
	#~ c.element.getparent().remove(c.element)
	#~ open('r:/reduced.xml', 'w').write(etree.tostring(cmltree, pretty_print=True, encoding='utf-8', method='xml'))


	#~ root_node.children = root_node.children[:12]
	jj = 1
	for bn in root_node.children:
	print len(bn.children)
	jj *= len(bn.children)
	print jj

	#~ import sys; sys.exit()

	uniqueVars = root_node.getUniqueVars()
	print 'Num Unique Vars: %s' % len(uniqueVars)
	for uv in sorted(uniqueVars):
	print uv

	t = time.time()
	#~ _vlsdebug()
	variants = analyse(root_node)
	print 'count unfiltered variants: %s\n' % len(variants)
	print time.time() - t
	#~ for i,v in enumerate(variants, 1):
	#~ print i, v


	#~ print 'Python Repr:'
	#~ print root_node.toCode(2)
	#~ print