#!/usr/bin/env python # FCGlob - FCtree # Author: Don Miner # Date: December 26, 2006 # # This is the FCTree data structure which stores the FCGlob file contexts in # tree form. # # Also, all common operations that are done on FCTrees are contained as member # functions of the FCTree object, such as matchpathcon. EQUAL = 0 SUBSET = 1 SUPERSET = 2 DISJOINT = 3 AMBIGUOUS = 4 INSTERSECT = (EQUAL, SUBSET, SUPERSET, AMBIGUOUS) class FCTree: """This is the set data structure to be used with fcglobs. An edge A->B appears in this tree if the following hold true for objects A and B: A is a superset of B A and B are not the same set There does not exist a set X in the graph such that: A is a superset of X and B is a subset of X This orders the nodes in the tree from most specific at the leaves to least specific at the root. To output a file_contexts style linear representation, simpy "print" the object: print MyFCTree """ class FCNode: def __init__(self, item, children = None): if children == None: children = [] self.item = item self.children = children def __init__(self, set_cmp): """Creates a new Tree. set_cmp is the comparison function used to compare two items. set_cmp(a,b) should return: 0 if the two sets are equal 1 if a is a subset of b 2 if a is a superset of b 3 if a and b are disjoint 4 otherwise """ # The root node is a dummy node. # It must be an empty node because it may be the case that there is no # single context which is a superset of everything. Thus, the "children" # of this place-holder node are the roots of this tree. self.root = self.FCNode(None) # set_cmp is used to determine the set relationships between two objects self.set_cmp = set_cmp def __str__(self): """Prints out the tree with an in-order traversal.""" to_print = self.root.children[:] next_level = [] out_str = "" while len(to_print) > 0: tmp = to_print.pop() out_str += str(tmp.item) + "\n" next_level += tmp.children if len(to_print) == 0: to_print = next_level next_level = [] out_str += "\n" return out_str def insert(self, item, cur_node = None): """Inserts a node containing item into the tree at the proper position.""" # cur_node is used as a helper for the recursion. A user is expected to # simply call this function with just item as a parameter if cur_node == None: # Start the search at the root node cur_node = self.root for i in range(len(cur_node.children)): child = cur_node.children[i] relation = self.set_cmp(item, child.item) if relation == DISJOINT: continue if relation == SUBSET: # Follow, continue down this path return self.insert(item, child) if relation == SUPERSET: # We are the subset of our parent and the superset of this child, # we now become the parent of this child # Replace the child's place in the children list of the parent # with this cur_node.children[i] = self.FCNode(item, [child]) # Also, some other children of cur_node may be subsets to_remove = [] for j in range(i+1, len(cur_node.children)): if self.set_cmp(item, cur_node.children[j].item) == SUPERSET: cur_node.children[i].children.append(cur_node.children[j]) to_remove.append(j) # Remove these children from cur_node since they are now the new ones' to_remove.reverse() for idx in to_remove: del cur_node.children[idx] return if relation == AMBIGUOUS or relation == EQUAL: # TODO put an FCGlob exception here # equal also means ambiguous while inserting print 'Oops! Ambiguousness! Not inserting', item, "vs.", child.item return # If we couldn't do anything with its children, we are a child of it cur_node.children.append(self.FCNode(item)) re def matchpathcon(self, item, cur_node = None): """Performs a matchpathcon on a single file. This set must be a SINGLE item, it can only be a subset, disjoint from or equal to another item in the tree """ # cur_node is used as a helper for the recursion. A user is expected to # simply call this function with just item as a parameter if cur_node == None: cur_node = self.root for i in range(len(cur_node.children)): child = cur_node.children[i] relation = self.set_cmp(item, child.item) if relation == DISJOINT: continue if relation == SUBSET: # Follow, continue down this path return self.matchpathcon(item, child) if relation == EQUAL: # We have found an exact match return child.item if relation == SUPERSET or relation == AMBIGUOUS: # These are invalid states for a singular element print item, 'is an invalid string to be searching \ for in matchpathcon (does it have wildcards?)' continue # Otherwise, this is the last node to be the superset of the one # we are trying to find return cur_n def print_graphviz(self, cur_node = None): """Performs a matchpathcon on a single file. This set must be a SINGLE item, it can only be a subset, disjoint from or equal to another item in the tree""" if cur_node == None: cur_node = self.root out_str = """ digraph file_contexts { \t size="6,6"; \t node [color=lightblue2, style=filled]; """ else: out_str = "" for child in cur_node.children: if cur_node.item != None: out_str += '\t"' + str(cur_node.item) + '" -> "' + str(child.item) + '";\n' out_str += self.print_graphviz(child) if cur_node.item == None: out_str += '}\n' return out_str # Test driver if False: # Effectively commented out the driver #if __name__ == '__main__': from sets import Set sets = [Set('abcdef'), Set('ab'), Set('cd'), \ Set('f'), Set('g'), Set('h'), Set('hab'), Set('i'), \ Set('cdef'), Set('abcdefghijklmnop'), Set('abcdefg') ] def set_cmp(a, b): if a == b: return 0 if a.issubset(b): return 1 if a.issuperset(b): return 2 if len(a.intersection(b)) == 0: return 3 return 4 t = FCTree(set_cmp) [ t.insert(s) for s in sets ] print t print t.matchpathcon(Set('a')) print t.matchpathcon(Set('d')) print t.matchpathcon(Set('z')) print t.matchpathcon(Set('e')) print t.print_graphviz() print "This is a test driver for FCTree!"