a class for storing a tree graph primarily used for filter constructs in the orm a single internal node in the tree graph a node should be viewed as a connection the root with the children being either leaf nodes or other node instances standard connector type clients usually won t use this at all and subclasses will usually override the value construct a new node if no connector is given use the default self children children if children else self connector connector or self default self negated negated classmethod def createcls childrennone connectornone negatedfalse obj nodechildren connector or cls default negated obj class cls return obj def strself template not s s if self negated else s s return template self connector joinstrc for c in self children def reprself return s s self class name self def copyself obj self createconnectorself connector negatedself negated obj children self children don t as init via create does return obj copy copy def deepcopyself memodict obj self createconnectorself connector negatedself negated obj children copy deepcopyself children memodict return obj def lenself return whether or not this node has children return boolself children def containsself other combine this tree and the data represented by data using the connector conntype the combine is done by squashing the node other away if possible this tree self will never be pushed to a child node of the combined tree nor will the connector or negated properties change return a node which can be used in place of data regardless if the node other got squashed or not we can squash the other node s children directly into this node we are just doing abcd abcd here with the addition that if the length of the other node is 1 the connector doesn t matter however for the lenself 1 case we don t want to do the squashing as it would alter self connector we could use perhaps additional logic here to see if some children could be used for pushdown here negate the sense of the root connector self negated not self negated a single internal node in the tree graph a node should be viewed as a connection the root with the children being either leaf nodes or other node instances standard connector type clients usually won t use this at all and subclasses will usually override the value construct a new node if no connector is given use the default create a new instance using node instead of __init__ as some subclasses e g django db models query_utils q may implement a custom __init__ with a signature that conflicts with the one defined in node __init__ don t as __init__ via create does return the number of children this node has return whether or not this node has children return true if other is a direct child of this instance combine this tree and the data represented by data using the connector conn_type the combine is done by squashing the node other away if possible this tree self will never be pushed to a child node of the combined tree nor will the connector or negated properties change return a node which can be used in place of data regardless if the node other got squashed or not we can squash the other node s children directly into this node we are just doing ab cd abcd here with the addition that if the length of the other node is 1 the connector doesn t matter however for the len self 1 case we don t want to do the squashing as it would alter self connector we could use perhaps additional logic here to see if some children could be used for pushdown here negate the sense of the root connector
import copy

from django.utils.hashable import make_hashable


class Node:
    

    
    
    default = "DEFAULT"

    def __init__(self, children=None, connector=None, negated=False):
        
        self.children = children[:] if children else []
        self.connector = connector or self.default
        self.negated = negated

    @classmethod
    def create(cls, children=None, connector=None, negated=False):
        
        obj = Node(children, connector or cls.default, negated)
        obj.__class__ = cls
        return obj

    def __str__(self):
        template = "(NOT (%s: %s))" if self.negated else "(%s: %s)"
        return template % (self.connector, ", ".join(str(c) for c in self.children))

    def __repr__(self):
        return "<%s: %s>" % (self.__class__.__name__, self)

    def __copy__(self):
        obj = self.create(connector=self.connector, negated=self.negated)
        obj.children = self.children  
        return obj

    copy = __copy__

    def __deepcopy__(self, memodict):
        obj = self.create(connector=self.connector, negated=self.negated)
        obj.children = copy.deepcopy(self.children, memodict)
        return obj

    def __len__(self):
        
        return len(self.children)

    def __bool__(self):
        
        return bool(self.children)

    def __contains__(self, other):
        
        return other in self.children

    def __eq__(self, other):
        return (
            self.__class__ == other.__class__
            and self.connector == other.connector
            and self.negated == other.negated
            and self.children == other.children
        )

    def __hash__(self):
        return hash(
            (
                self.__class__,
                self.connector,
                self.negated,
                *make_hashable(self.children),
            )
        )

    def add(self, data, conn_type):
        
        if self.connector != conn_type:
            obj = self.copy()
            self.connector = conn_type
            self.children = [obj, data]
            return data
        elif (
            isinstance(data, Node)
            and not data.negated
            and (data.connector == conn_type or len(data) == 1)
        ):
            
            
            
            
            
            self.children.extend(data.children)
            return self
        else:
            
            
            self.children.append(data)
            return data

    def negate(self):
        
        self.negated = not self.negated