Guest User

Untitled

a guest
Feb 26th, 2012
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python
  2. #coding: utf-8
  3.  
  4. OR_OP  = 1
  5. AND_OP = 2
  6. NOT_OP = 3
  7.  
  8. class NotAcceptableException(Exception): pass
  9.  
  10. class Operand:
  11.     name = ""
  12.     inverted = False
  13.  
  14.     def __eq__(self, other):
  15.         return self._str_ == other._str_
  16.  
  17.     def __hash__(self):
  18.         return self._hash_
  19.  
  20.     def __init__(self, name, inverted = False):
  21.         assert(not name.startswith('!'))
  22.         self.name = name
  23.         self.inverted = inverted
  24.         self.__gen_data__()
  25.  
  26.     def __gen_data__(self):
  27.         self._str_  = self.__str__()
  28.         self._hash_ = self._str_.__hash__()
  29.  
  30.     def invert(self):
  31.         self.inverted = not self.inverted
  32.         self.__gen_data__()
  33.  
  34.     def __str__(self):
  35.         if self.inverted:
  36.             return "!" + self.name
  37.         else:
  38.             return self.name
  39.  
  40.     def __repr__(self):
  41.         return self._str_
  42.  
  43. # --------------------------------------------
  44. # AND operation functions
  45. # --------------------------------------------
  46.  
  47. # v is possible under cond ?
  48. def is_acceptable(v, cond):
  49.     if type(cond) == list:
  50.         return all(map(lambda x: is_acceptable(v, x), cond))
  51.  
  52.     elif type(cond) == set:
  53.         return all(map(lambda x: is_acceptable(v, x), cond))
  54.  
  55.     else:
  56.         if v.name != cond.name or v.inverted == cond.inverted:
  57.             return True
  58.         else:
  59.             raise NotAcceptableException()
  60.  
  61. # (ow = one way) are src conditions possible under dst ?
  62. def is_ow_acceptable(src, dst):
  63.     if type(src) == list:
  64.         return all(map(lambda x: is_ow_acceptable(x, dst), src))
  65.  
  66.     elif type(src) == set:
  67.         return all(map(lambda x: is_ow_acceptable(x, dst), src))
  68.  
  69.     else:
  70.         return is_acceptable(src, dst)
  71.  
  72. # (tw = two way) are c1 and c2 possible simultaneously
  73. def is_tw_acceptable(c1, c2):
  74.     if c1 == None or c2 == None:
  75.         return False
  76.  
  77.     ac2 = is_ow_acceptable(c1, c2)
  78.     ac1 = is_ow_acceptable(c2, c1)
  79.     return ac1 and ac2
  80.  
  81. # --------------------------------------------
  82. # Common operation functions
  83. # --------------------------------------------
  84.  
  85. # considers the different branches and may output a more compact one
  86. # TODO: actually code the important part :P
  87. def clean_branch_list(bl):
  88.     l = []
  89.     for i in xrange(len(bl)):
  90.         bi = bl[i]
  91.  
  92.         already_contained = False
  93.         to_delete = []
  94.  
  95.         le = len(l)
  96.         for j in xrange(len(l)):
  97.             bj = l[j]
  98.  
  99.             if bi.issubset(bj):
  100.                 if bj == bi:
  101.                     to_delete.append(j)
  102.                 else:
  103.                     already_contained = True
  104.  
  105.             elif bi.issuperset(bj):
  106.                 already_contained = True
  107.  
  108.         if not already_contained:
  109.             l.append(bi)
  110.  
  111.         offset = 0
  112.         for d in to_delete:
  113.             l.pop(d - offset)
  114.             offset += 1
  115.  
  116.     return l
  117.  
  118. # outputs the (con1 or con2) branch list
  119. def rewrite_constraints_or(con1, con2):
  120.  
  121.     if type(con1) == set:
  122.         con1 = [con1]
  123.  
  124.     if type(con2) == set:
  125.         con2 = [con2]
  126.  
  127.     # Null operands?
  128.     if con1 == None:
  129.         if con2 == None:
  130.             return None
  131.         return con2
  132.  
  133.     elif con2 == None:
  134.         return con1
  135.  
  136.     return clean_branch_list(con1 + con2)
  137.  
  138.  
  139. # outputs the (con1 and con2) branch list
  140. def rewrite_constraints_and(c1, c2):
  141.     if type(c1) == set:
  142.         c1 = [c1]
  143.     elif c1 == None:
  144.         c1 = []
  145.  
  146.     if type(c2) == set:
  147.         c2 = [c2]
  148.     elif c2 == None:
  149.         c2 = []
  150.  
  151.     sets = []
  152.  
  153.     # Some optimization would be great here!! :P
  154.     for x in c1:
  155.         for y in c2:
  156.             try:
  157.                 if is_tw_acceptable(x, y):
  158.                     sets.append(x | y)
  159.  
  160.             except NotAcceptableException:
  161.                 pass
  162.  
  163.     if len(sets) == 0:
  164.         return None
  165.     else:
  166.         return sets
  167.  
  168.  
  169. # Obtains recursively the solution branches of a operation
  170. def get_solutions(operand, inverted = False):
  171.     if type(operand) == str:
  172.         op = Operand(operand)
  173.         if inverted:
  174.             op.invert()
  175.         return [set([op])]
  176.  
  177.     if not (type(operand) in (tuple, list)):
  178.         raise Exception("Error: %s" % operand)
  179.  
  180.     if len(operand) == 2:
  181.         op, op1 = operand
  182.         sol = get_solutions(op1, not inverted)
  183.  
  184.         if op == NOT_OP:
  185.             return sol
  186.         raise Exception("%i operand doesn't apply to one operand (%s)" % (op,
  187.                                                                        operand))
  188.  
  189.     else:
  190.         try:
  191.             op, op1, op2 = operand
  192.         except:
  193.             print "\x1b[0;91mOperation error"
  194.             print len(operand)
  195.             print operand, "\x1b[0m"
  196.             raise Exception()
  197.  
  198.         sol1 = get_solutions(op1, inverted)
  199.         sol2 = get_solutions(op2, inverted)
  200.  
  201.         if not inverted:
  202.             if   op == OR_OP:
  203.                 return rewrite_constraints_or(sol1, sol2)
  204.  
  205.             elif op == AND_OP:
  206.                 return rewrite_constraints_and(sol1, sol2)
  207.  
  208.         else:
  209.             if   op == OR_OP:
  210.                 return rewrite_constraints_and(sol1, sol2)
  211.  
  212.             elif op == AND_OP:
  213.                 return rewrite_constraints_or(sol1, sol2)
  214.            
  215.  
  216.         raise Exception("%i operand doesn't apply to two operands" % op)
  217.  
  218. # TODO: Update this part
  219. def get_solution_string(s):
  220.     if type(s) == list:
  221.         return ', '.join(map(get_solution_string, s))
  222.  
  223.     elif type(s) == set:
  224.         return ', '.join(map(get_solution_string, s))
  225.  
  226.     else:
  227.         return str(s)
  228.  
  229. # Pretty prints the solution branches
  230. def print_solutions(sols):
  231.     if sols == None:
  232.         print "It's impossible!"
  233.         return
  234.  
  235.     for s in sols:
  236.         print get_solution_string(s)
  237.  
  238.     print '%i solution(s)' % len(sols)
RAW Paste Data