# Base class for all operators class operator: # Return a set of variables, defined by this operator def defined_vars(self): return set() class OpTreeNode: def __init__(self,op,left_child=None,right_child=None): self.op = op self.left_child = left_child self.right_child = right_child self.parent = None # Convert a linear plan (with no joins) to a list of nodes def as_list(self): if self.right_child: raise "Converting a tree to a list" return [self] + (self.left_child.as_list() if self.left_child else []) # Convert a linear plan (with no joins) to a reversed list of nodes def as_list_reversed(self): res = self.as_list() res.reverse() return res # Iterate over all children via inorder traversal def visit(self): yield self if self.left_child: for x in self.left_child.visit(): yield x if self.right_child: for x in self.right_child.visit(): yield x # Compute the set of variables, defined in this subplan def defined_vars(self): vars = set() if self.left_child: vars = self.left_child.defined_vars() if self.right_child: vars = vars.union( self.right_child.defined_vars() ) return vars.union( self.op.defined_vars() ) # Compute a set of variables that are used above this operator def used_vars_above(self): vars = set() node = self.parent while node: vars = vars.union( node.op.used_vars() ) node = node.parent return vars # Compute all the parents in the plan def compute_parents(self): if self.left_child: self.left_child.parent = self self.left_child.compute_parents() if self.right_child: self.right_child.parent = self self.right_child.compute_parents() # Replace this subplan with another one: def replace(self,other): self.op = other.op self.left_child = other.left_child self.right_child = other.right_child # Execute this subtree def execute(self, table, prior_lcs, prior_globs): if self.right_child: return self.op.execute(table, prior_lcs, prior_globs, self.left_child, self.right_child) else: if self.left_child: table = self.left_child.execute(table, prior_lcs, prior_globs) return self.op.execute(table, prior_lcs, prior_globs) # return a string representation of the plan def __repr__(self): return self.string_repr(0) # return a string representation of the plan def string_repr(self,nTabs): res = " " * nTabs res += repr(self.op) if self.right_child: res += "\n" if self.left_child: res += self.left_child.string_repr(nTabs+1) else: res += " " * (nTabs+1) + "None" res += "\n" res += self.right_child.string_repr(nTabs+1) elif self.left_child: res += "\n" res += self.left_child.string_repr(nTabs+1) return res def plan_from_list(l): l2 = list(l) l2.reverse() res = None for x in l2: res = OpTreeNode(x,res) return res