Commits

Pierre Carbonnelle committed c0a8088

order of clauses for function definition is significant --> use OrderedSet for pred. clauses

Comments (0)

Files changed (2)

pyDatalog/pyEngine.py

             o.comparison = words[1] if 1 < len(words) else '' # for f[X]<Y
 
             o.db = {}
-            o.clauses = set([])
+            o.clauses = util.OrderedSet([]) #TODO just use a list. (retract clause is rare)
             # one index per term. An index is a dictionary of sets
             o.index = [{} for i in range(int(o.arity))]
             o.prim = None
 '''
 Created on 28 mars 2013
 
-source : http://anandology.com/blog/using-iterators-and-generators/
+source : 
+    http://anandology.com/blog/using-iterators-and-generators/
+    OrderedSet: http://code.activestate.com/recipes/576694/
 '''
 
+import collections
+
 class DatalogError(Exception):
     def __init__(self, value, lineno, function):
         self.value = value
     def next(self):
         self.i += 1
         return self.i
+
+class OrderedSet(collections.MutableSet):
+
+    def __init__(self, iterable=None):
+        self.end = end = [] 
+        end += [None, end, end]         # sentinel node for doubly linked list
+        self.map = {}                   # key --> [key, prev, next]
+        if iterable is not None:
+            self |= iterable
+
+    def __len__(self):
+        return len(self.map)
+
+    def __contains__(self, key):
+        return key in self.map
+
+    def add(self, key):
+        if key not in self.map:
+            end = self.end
+            curr = end[1]
+            curr[2] = end[1] = self.map[key] = [key, curr, end]
+
+    def discard(self, key):
+        if key in self.map:        
+            key, prev, next = self.map.pop(key)
+            prev[2] = next
+            next[1] = prev
+
+    def __iter__(self):
+        end = self.end
+        curr = end[2]
+        while curr is not end:
+            yield curr[0]
+            curr = curr[2]
+
+    def __reversed__(self):
+        end = self.end
+        curr = end[1]
+        while curr is not end:
+            yield curr[0]
+            curr = curr[1]
+
+    def pop(self, last=True):
+        if not self:
+            raise KeyError('set is empty')
+        key = self.end[1][0] if last else self.end[2][0]
+        self.discard(key)
+        return key
+
+    def __repr__(self):
+        if not self:
+            return '%s()' % (self.__class__.__name__,)
+        return '%s(%r)' % (self.__class__.__name__, list(self))
+
+    def __eq__(self, other):
+        if isinstance(other, OrderedSet):
+            return len(self) == len(other) and list(self) == list(other)
+        return set(self) == set(other)