#! /usr/bin/python

# Takes a mapping and applies transformation rules until it matches one
# of the target mappings.  Uses the DijkstraShortestPath module to run
# the search algorithm.

from __future__ import generators
from HashableMap import HashableMap

def inConflict(a, b):
   """
   Determines whether any entries in mappings 'a' and 'b' are in
   conflict.  (i.e. if there is a key that is both in 'a' and 'b',
   they must both have the same value for that key)
   """
   for (key, value) in b.iteritems():
      if (a.has_key(key) and a[key] != value):
         return True
   return False

def isSuperset(a, b):
   """
   Determines whether mapping 'a' is a superset of mapping 'b'.
   Values are taken into account as well.
   """
   for (key, value) in b.iteritems():
      if (not a.has_key(key) or a[key] != value):
         return False
   return True

def targetMatches(entry, target):
   "See if an entry matches a target."
   return not inConflict(entry, target)

def triggerMatches(entry, trigger):
   """
   Given a rule's trigger, this function checks to see if the rule
   should by applied to the given entry.
   """
   return isSuperset(entry, trigger)

def applyTransform(entry, transform):
   "Apply a transform to an entry to produce a new entry."
   result = HashableMap(entry)
   result.update(transform)
   return result

def match(premises, targets, rules):
   """
   premises = [ premise, ... ]
   targets  = [ target, ... ]
   rules    = [ (pattern, transform, cost), ... ]
   """

   # Make the premises hashable
   premises = [ HashableMap(premise) for premise in premises ]

   def deriveNewEntries(entry):
      "Node derivation function (generator)"
      for (trigger, transform, transformCost) in rules:
         if (triggerMatches(entry, trigger)):
            yield(applyTransform(entry, transform), transformCost)

   # Target matching function
   def matchTarget(entry):
      for target in targets:
         if (targetMatches(entry, target)): return target
      return None

   import DijkstraShortestPath
   (node, cost, target) = DijkstraShortestPath.search(premises,
                                                      deriveNewEntries,
                                                      matchTarget)

   return target