Algorithm to check whether a set is canonical

csirmaz · Dec 29, 2022 · 020b37d · 020b37d
1 parent d805d51
commit 020b37d
Show file tree

Hide file tree

Showing 5 changed files with 100 additions and 9 deletions.
diff --git a/command.py b/command.py
@@ -5,22  5,39 @@ def __init__(self, node, before, after):
         self.node = node # a Node object`
         self.before = before # a Value object
         self.after = after # a Value object
-
 
 
     def as_string(self):
         return f"<{self.node.as_string()}, {self.before.as_string()}, {self.after.as_string()}>"
 
 
     def equals(self, other):
         """Whether the current object and another are equal"""
         return (self.node.equals(other.node) and self.before.equals(other.before) and self.after.equals(other.after))
 
 
     def is_null(self):
         """Whether this is a null command"""
         return self.before.equals(self.after)
 
 
     def is_constructor(self):
         """Whether this is a constructor command"""
         return self.after.type_greater(self.before)
 
 
     def is_destructor(self):
         """Whether this is a destructor command"""
         return self.after.type_less(self.before)
 
 
     def is_constructor_pair_with_next(self, other):
         """Whether this command forms a constructor pair with the next command, `other`"""
         return (self.is_constructor() and self.after.is_dir() and other.is_constructor() and other.before.is_empty() and self.node.is_parent_of(other.node))
 
 
     def is_destructor_pair_with_next(self, other):
         """Whether this command forms a destructor pair with the next command, `other`"""
         return (self.is_destructor() and self.after.is_empty() and other.is_destructor() and other.before.is_dir() and other.node.is_parent_of(self.node))
 
 
diff --git a/csequence.py b/csequence.py
@@ -75,19  75,60 @@ def get_canonical_set(self):
     def from_set(cls, cset):
         """Dumb function to turn a command set into a command sequence; the order of commands is not guaranteed"""
         return CSequence(list(cset.commands))
 
 
     @classmethod
     def is_set_canonical(cls, cset):
         """Check whether a set of commands is canonical. This algorithm is, apart from the ordering, is linear in the size of the set"""
         seq = cls.from_set(cset).order_by_node().commands
 
         up_pointers = [] # Stores the "up" pointers: the index of the command pointed to
         prev_node = None
         for i in range(len(seq)):
 
             this_node = seq[i].node
 
             if prev_node is not None:
                 if prev_node.equals(this_node):
                     # Not canonical as multiple commands on the same node
                     return False
             prev_node = seq[i].node
 
             if i == 0:
                 up_pointers.append(None)
                 continue
 
             up = i - 1
             while True:
                 if up is None or seq[up].node.is_ancestor_of(this_node):
                     up_pointers.append(up)
 
                     if up is not None and not (seq[up].is_constructor_pair_with_next(seq[i]) or seq[i].is_destructor_pair_with_next(seq[up])):
                         # Not canonical because closest command on an ancestor is not on a parent or they do not form a valid pair
                         return False
 
                     break
                 up = up_pointers[up]
 
         return True            
 
 
 if __name__ == '__main__':
 
     # Test code
-    c1 = Command(Node(['d1']), Value(Value.T_EMPTY, 'e'), Value(Value.T_DIR, 'D1'))
-    c2 = Command(Node(['d1', 'd2']), Value(Value.T_EMPTY, 'e'), Value(Value.T_DIR, 'D2'))
-    c2b = Command(Node(['d1', 'd2']), Value(Value.T_EMPTY, 'e'), Value(Value.T_DIR, 'D2b'))
-    c3 = Command(Node(['d1', 'd2', 'f3']), Value(Value.T_EMPTY, 'e'), Value(Value.T_FILE, 'F'))
     c1 =  Command(Node(['d1']),             Value(Value.T_EMPTY, 'e'), Value(Value.T_DIR, 'D1'))
     c2 =  Command(Node(['d1', 'd2']),       Value(Value.T_EMPTY, 'e'), Value(Value.T_DIR, 'D2'))
     c2b = Command(Node(['d1', 'd2']),       Value(Value.T_EMPTY, 'e'), Value(Value.T_DIR, 'D2b'))
     c3 =  Command(Node(['d1', 'd2', 'f3']), Value(Value.T_EMPTY, 'e'), Value(Value.T_FILE, 'F'))
     s = CSequence([c1, c2, c2b, c3])
     s2 = CSequence([c3, c2, c1, c2b])
     sc = CSequence([c1, c2b, c3])
     assert s2.order_by_node().equals(s)
     assert CSequence.from_set(s2.get_canonical_set()).order_by_node().equals(sc)
 
     assert CSequence.is_set_canonical(CSet({c1, c2, c3}))
     assert not CSequence.is_set_canonical(CSet({c2, c2b}))
     assert not CSequence.is_set_canonical(CSet({c1, c3}))
 
     print("Tests done")
 
diff --git a/cset.py b/cset.py
@@ -8,7  8,8 @@ class CSet:
     def __init__(self, commands):
         assert isinstance(commands, set)
         self.commands = commands
-
 
 
     def as_string(self):
         s = ', '.join([c.as_string() for c in self.commands])
         return "{"   s   "}"
diff --git a/node.py b/node.py
@@ -8,32  8,39 @@ class Node:
 
     def __init__(self, path):
         self.path = path
-
 
 
     def as_string(self):
         return '/'.join(self.path)
 
 
     def equals(self, other):
         """Whether the curent object is equal to another object"""
         return (self.comp(other) == 0)
 
 
     def is_ancestor_of(self, other):
         """Whether the current object is an ancestor of the other object"""
         if len(self.path) >= len(other.path):
             return False
         return (self.path == other.path[0:len(self.path)])
 
 
     def is_descendant_of(self, other):
         """Whether the current object is a descendand of another object"""
         return other.is_ancestor_of(self)
 
 
     def is_parent_of(self, other):
         """Whether the current object is the parent of another object"""
         return (self.path == other.path[0:-1])
 
 
     def get_parent(self):
         """Get an object representing the parent of the current object"""
         return Node(self.path[0:-1])
 
 
     def comp(self, other):
         """Comparison function (returning -1,0,1) following lexicographic order"""
         # The </== operators between lists should do the same, but making the logic explicit here
@@ -50,15  57,18 @@ def comp(self, other):
             if self.path[i] > other.path[i]:
                 return 1
             i  = 1
 
 
     def is_less(self, other):
         """Whether the current object is less than another following lexicographic order"""
         return (self.comp(other) == -1)
 
 
     def is_greater(self, other):
         """Whether the current object is greater than another following lexicographic order"""
         return (self.comp(other) == 1)
 
 
 if __name__ == '__main__':
 
     # Test code
@@ -69,4  79,3 @@ def is_greater(self, other):
     assert Node([]).is_parent_of(Node(['a']))
     print("Tests done")
 
-
diff --git a/value.py b/value.py
@@ -13,10  13,12 @@ class Value:
     T_EMPTY = 100
     T_FILE = 101
     T_DIR = 102
-
 
 
     def __init__(self, type_, contents):
         self.type_ = type_
         self.contents = contents
 
 
     def as_string(self):
         t = {
@@ -26,23  28,44 @@ def as_string(self):
         }
         return f"{t[self.type_]}({self.contents})"
 
 
     def is_empty(self):
         """Whether the value is an empty value"""
         return (self.type_ == self.T_EMPTY)
 
 
     def is_file(self):
         """Whether the value is a file"""
         return (self.type_ == self.T_FILE)
 
 
     def is_dir(self):
         """Whether the value is a directory"""
         return (self.type_ == self.T_DIR)
 
 
     def type_eq(self, other):
         """Whether the current and another object are type-equal"""
         return (self.type_ == other.type_)
 
 
     def type_less(self, other):
         """Whether the current object is type-less than another object"""
         return (self.type_ < other.type_)
 
 
     def type_less_eq(self, other):
         """Whether the current object is type-less-or-equal than another object"""
         return (self.type_ <= other.type_)
 
 
     def type_greater(self, other):
         return (self.type_ > other.type_)
 
 
     def type_greater_eq(self, other):
         return (self.type_ >= other.type_)
 
 
     def equals(self, other):
         """Whether the current object and another are equal"""