Module cte_forest.models

Any Model can be turned into a tree by inheriting from the abstract CTENode. By default, this model will feature a ForeignKey to self named parent, and with a related_name of children. Furthermore, it will feature a custom CTENodeManager through the CTENode.objects attribute.

Each instance of a CTENode will feature three virtual fields, by default named depth, path, and ordering; these fields are populated through a custom CTE SQL query, and contain, respectively, the depth of a node (starting with root nodes of depth one), the path (an array of primary keys, or an encoded string if the primary key type requires this), and a custom ordering key (usually starting with the DFS or BFS order key, and then extended with custom ordering specified by the concrete Model).

All parameters regarding the configuration of the tree are specified as attributes in the concrete Model inheriting from CTENode, and have the form _cte_node_*. See below for a complete listing and interpretation of each parameter.

An important caveat when using CTE queries is ordering: any CTE query which is cloned and processed through an order_by() invocation will result in the CTE ordering of the nodes to be overridden. Therefore, if you wish to maintain proper tree ordering, you must specify any custom fields to order by through the _cte_node_order_by attribute (see below). Unfortunately, it is not possible to re-create tree ordering through an order_by() invocation (see technical notes for an explanation).

In case custom ordering among siblings is desired (such as using an integer, or lexicographic order of a string name, and so on), the move() method accepts a parameter position which, if not None, is expected to be a callable that is invoked with the destination and the node currently being moved as arguments, before any modification to the parent relationship is made. Thus, the move() method delegates to this callable in order to specify or modify order-related attributes, enforce constraints, or even change the attributes of siblings (such as creating a hole in a contiguous integer total order).

CTENode

class cte_forest.models.CTENode(*args, **kwargs)

Abstract Model which implements a node in a CTE tree. This model features a mandatory foreign key to the parent node (hence to self), which, when None, indicates a root node. Multiple nodes with a None parent results in a forest, which can be constrained either with custom SQL constraints or through application logic.

It is necessary for any custom Manager of this model to inherit from CTENodeManager, as all functionality of the CTE tree is implemented in the manager.

It is possible to manipulate individual nodes when not loaded through the custom manager, or when freshly created either through the create() method or through the constructor, however, any operation which requires tree information (the depth, path, and ordering virtual fields) will not work, and any attempt to invoke such methods will result in an ImproperlyConfigured exception being raised.

Many runtime properties of nodes are specified through a set of parameters which are stored as attributes of the node class, and begin with _cte_node_. Before any of these parameters are used, the manager will attempt to load and verify them, raising an ImproperlyConfigured exception if any errors are encountered. All parameters have default values.

All QuerySet objects involving CTE nodes use the QuerySet.extra() semantics in order to specify additional SELECT, WHERE, and ORDER_BY SQL semantics, therefore, they cannot be combined through the OR operator (the | operator).

The following parameters can optionally be specified at the class level:

• _cte_node_traversal:

  A string from one of TREE_TRAVERSAL_METHODS, which specifies the default tree traversal order. If this parameters is None or TREE_TRAVERSAL_NONE, then DEFAULT_TREE_TRAVERSAL method is used (which is dfs for depth-first).

• _cte_node_order_by:

  A list of strings or tuples specifying the ordering of siblings during tree traversal (in the breadth-first method, siblings are ordered depending on their parent and not the entire set of nodes at the given depth of the tree).

  The entries in this list can be any of the model fields, much like the entries in the ordering of the model’s Meta class or the arguments of the order_by() method of QuerySet.

  These entries may also contain the virtual field depth, which cannot be used by the normal QuerySet because Django cannot recognize such virtual fields.

  In case of multiple entries, they must all be of the same database type. For VARCHAR fields, their values will be cast to TEXT, unless otherwise specified. It is possible to specify the database type into which the ordering field values are cast by providing tuples of the form (fieldname, dbtype) in the ordering sequence.

  Specifying cast types is necessary when combining different data types in the ordering sequence, such as an int and a float (casting the int into a float is probably the desired outcome in this situation). In the worst case, TEXT can be specified for all casts.

• _cte_node_delete_method:

  A string specifying the desired default deletion semantics, which may be one of DELETE_METHODS. If this parameter is missing or None or DELETE_METHOD_NONE, then the default deletion semantics DEFAULT_DELETE_METHOD will be used (which is DELETE_METHOD_PHARAOH or pharaoh for the Pharaoh deletion semantics).

• _cte_node_parent:

  A string referencing the name of the ForeignKey field which implements the parent relationship, typically called parent and automatically inherited from this class.

  If this parameter is missing, and no field with the name parent can be found, then the first ForeignKey which relates to this model will be used as the parent relationship field.

• _cte_node_children:

  A string referencing the related_name attribute of the ForeignKey field which implements the parent relationship, typically called parent (specified in DEFAULT_CHILDREN_NAME) and automatically inherited from this class.

• _cte_node_table:

  The name of the temporary table to use with the WITH CTE SQL statement when compiling queries involving nodes. By default this is DEFAULT_TABLE_NAME (which is cte).

• _cte_node_primary_key_type:

  A string representing the database type of the primary key, if the primary key is a non-standard type, and must be cast in order to be used in the path or ordering virtual fields (similarly to the _cte_node_order_by parameter above).

  A VARCHAR primary key will be automatically cast to TEXT, unless explicitly specified otherwise through this parameter.

• _cte_node_path, _cte_node_depth, _cte_node_ordering:

  Strings specifying the attribute names of the virtual fields containing the path, depth, and ordering prefix of each node, by default, respectively, VIRTUAL_FIELD_PATH (which is path), VIRTUAL_FIELD_DEPTH (which is depth), and VIRTUAL_FIELD_ORDERING (which is ordering).

ancestors()

Returns a QuerySet of all ancestors of this node.

Returns:A QuerySet of all ancestors of this node.

as_tree(visitor=None, children=None)

Recursively traverses each tree (starting from each root) in order to generate a dictionary-based tree structure of the entire forest. Each level of the forest/tree is a list of nodes, and each node consists of a dictionary representation, where the entry children (by default) consists of a list of dictionary representations of its children.

See CTENodeManager.as_tree() and CTENodeManager.node_as_tree() for details on how this method works, as well as its expected arguments.

Parameters:

• visitor – optional function responsible for generating the dictionary representation of a node.
• children – optional function responsible for generating a children key and list for a node.

Returns:

a dictionary representation of the structure of the forest.

attribute_path(attribute, missing=None, visitor=None)

Generates a list of values of the attribute of all ancestors of this node (as well as the node itself). If a value is None, then the optional value of missing is used (by default None).

By default, the getattr(node, attribute, None) or missing mechanism is used to obtain the value of the attribute for each node. This can be overridden by supplying a custom visitor function, which expects as arguments the node and the attribute, and should return an appropriate value for the required attribute.

Parameters:

• attribute – the name of the attribute.
• missing – optional value to use when attribute value is None.
• visitor – optional function responsible for obtaining the attribute value from a node.

Returns:

a list of values of the required attribute of the ancestor path of this node.

clean()

Prevents cycles in the tree.

delete(method=None, position=None, save=True)

Prepares the tree for deletion according to the deletion semantics specified for the CTENode Model, and then delegates to the CTENode superclass delete method.

Default deletion method and position callable can be overridden by being supplied as arguments to this method.

Parameters:

• method – optionally a particular deletion method, overriding the default method specified for this model.
• position – optional callable to invoke prior to each move operation, should the delete method require any moves.
• save – optional flag indicating whether this model’s save() method should be invoked after each move operation, should the delete method require any moves.

descendants()

Returns a QuerySet of all descendants of this node.

Returns:A QuerySet of all descendants of this node.

is_ancestor_of(subject)

Returns True if the node is an ancestor of the given subject node, False otherwise. This method uses the path virtual field, and so does not perform any query.

Parameters:subject – the CTENode for which to determine whether one of its ancestors is this node. Returns:True if this node is an ancestor of subject, False otherwise.

is_branch()

Returns True if this node is a branch (has at least one child), False otherwise.

Returns:True if this node is a branch, False otherwise.

is_child_of(subject)

Returns True if this node is a child of the given subject node, False otherwise. This method used the parent field, and so does not perform any query.

Parameters:subject – the CTENode for which to determine whether one of its children is this node. Returns:True if this node is a child of subject, False otherwise.

is_descendant_of(subject)

Returns True if the node is a descendant of the given subject node, False otherwise. This method uses the path virtual field, and so does not perform any query.

Parameters:subject – the CTENode for which to determine whether one of its descendants is this node. Returns:True if this node is a descendant of subject, False otherwise.

is_leaf()

Returns True if this node is a leaf (has no children), False otherwise.

Returns:True if this node is a leaf, False otherwise.

is_parent_of(subject)

Returns True if this node is the parent of the given subject node, False otherwise. This method uses the parent field, and so does not perform any query.

Parameters:subject – the CTENode for which to determine whether its parent is this node. Returns:True if this node is the parent of subject, False otherwise.

is_sibling_of(subject)

Returns True if this node is a sibling of the given subject node, False otherwise. This method uses the parent field, and so does not perform any query.

Parameters:subject – the CTENode for which to determine whether one of its siblings is this node. Returns:True if this node is a sibling of subject, False otherwise.

move(destination=None, position=None, save=False)

Moves this node and places it as a child node of the destination CTENode (or makes it a root node if destination is None).

Optionally, position can be a callable which is invoked prior to placement of the node with this node and the destination node as the sole two arguments; this can be useful in implementing specific sibling ordering semantics.

Optionally, if save is True, after the move operation completes (after the parent foreign key is updated and the position callable is called if present), a call to Model.save() is made.

Parameters:

• destination – the destination node of this move, None denoting that the node will become a root node.
• position – optional callable invoked prior to placement for purposes of custom sibling ordering semantics.
• save – optional flag indicating whether this model’s save() method should be invoked after the move.

Returns:

this node.

root()

Returns the CTENode which is the root of the tree in which this node participates.

siblings()

Returns a QuerySet of all siblings of this node.

Returns:A QuerySet of all siblings of this node.

CTENodeManager

class cte_forest.models.CTENodeManager

Custom Manager which ensures all queries involving CTENode objects are processed by the custom SQL compiler. Additionally, provides tree traversal queries for obtaining node children, siblings, ancestors, descendants, and roots.

If your Model inherits from CTENode and use your own custom Manager, you must ensure the following three:

1. your Manager inherits from CTENodeManager,

2) if you override the get_queryset() method in order to return a custom QuerySet, then your QuerySet must also inherit from CTENodeManager.CTEQuerySet, and

3) invoke the _ensure_parameters() on your Manager at least once before using a QuerySet which inherits from CTENodeManager.CTEQuerySet, unless you have supplied the necessary CTE node attributes on the CTENode Model in some other way.

The methods prepare_delete(), prepare_delete_pharaoh(), prepare_delete_grandmother(), and prepare_delete_monarchy() can be directly used to prepare nodes for deletion with either the default or explicitly-specified deletion semantics. The CTENode abstract Model defines a CTENode.delete() method which delegates preparation to this manager.

ancestors(node)

Returns a QuerySet of all ancestors of a given CTENode node.

Parameters:node – A CTENode whose ancestors are required. Returns:A QuerySet of all ancestors of the given node.

as_tree(visitor=None, children=None)

Recursively traverses each tree (starting from each root) in order to generate a dictionary-based tree structure of the entire forest. Each level of the forest/tree is a list of nodes, and each node consists of a dictionary representation, where the entry children (by default) consists of a list of dictionary representations of its children.

Optionally, a visitor callback can be used, which is responsible for generating a dictionary representation of a given CTENode. By default, the _default_node_visitor() is used which generates a dictionary with the current node as well as structural properties. See _default_node_visitor() for the appropriate signature of this callback.

Optionally, a children callback can be used, which is responsible for determining which CTENode`s are children of each visited :class:`CTENode, resulting in a key (by default children) and a list of children CTENode objects, which are then included in the dictionary representation of the currently-visited node. See _default_node_children() for the appropriate signature of this callback.

For each node visited, the CTENode.as_tree() method is invoked along with the optional visitor and children arguments. This method, if not overridden, will delegate to node_as_tree(), which is responsible for invoking the visitor() and children() methods, as well as updating the dictionary representation of the node with the representation of the children nodes.

Parameters:

• visitor – optional function responsible for generating the dictionary representation of a node.
• children – optional function responsible for generating a children key and list for a node.

Returns:

a dictionary representation of the structure of the forest.

attribute_path(node, attribute, missing=None, visitor=<function CTENodeManager.<lambda>>)

Generates a list of values of the attribute of all ancestors of the given node (as well as the node itself). If a value is None, then the optional value of missing is used (by default None).

By default, the getattr(node, attribute, None) or missing mechanism is used to obtain the value of the attribute for each node. This can be overridden by supplying a custom visitor function, which expects as arguments the node and the attribute, and should return an appropriate value for the required attribute.

Parameters:

• node – the CTENode for which to generate the attribute path.
• attribute – the name of the attribute.
• missing – optional value to use when attribute value is None.
• visitor – optional function responsible for obtaining the attribute value from a node.

Returns:

a list of values of the required attribute of the ancestor path of the given node.

branches()

Returns a QuerySet of all branch nodes (nodes with at least one child).

Returns:A QuerySet of all leaf nodes (nodes with at least one child).

descendants(node)

Returns a QuerySet with all descendants for a given CTENode node.

Parameters:node – the CTENode whose descendants are required. Returns:A QuerySet with all descendants of the given node.

drilldown(attributes, path)

Recursively descends the tree/forest (starting from each root node) in order to find a CTENode which corresponds to the given path. The path is expected to be an iterable of tuples, called path components, consisting of attribute values with which to filter through the QuerySet API. The name of the attribute to which each value corresponds is specified in attributes, which is expected to conform to Django’s QuerySet API for the filter semantics. Each value in the path component tuple will be mapped to its corresponding attribute name before being passed to the filter method.

For example, if the node model features the integer field x and the boolean field y, we can drill down in the following way:

drilldown((‘x__gte’, ‘y’),[(35, True), (37, False)])

The simplest form of drilldown is to match with equality on a single attribute, such as name, as in the following example:

drilldown((‘name’,), [(‘path’,), (‘to’,), (‘my’,), (‘node’,)])

Don’t forget the trailing comma if specifying singleton tuples! If you need very simple, one-attribute path components, it is suggested you extend the manager with your own convenience method; the above will, for instance, become:

def drilldown_by_name(self, path):

return self.drilldown((‘name’,),

[(component,) for component in path])

Failure to find the required node results in a DoesNotExist exception being raised.

An empty path will result in the first root node being returned (if at least one root node exists).

get_queryset()

Returns a custom QuerySet which provides the CTE functionality for all queries concerning CTENode objects. This method overrides the default get_queryset() method of the Manager class.

Returns:a custom QuerySet which provides the CTE functionality for all queries concerning CTENode objects.

is_ancestor_of(node, subject)

Returns True if the given node is an ancestor of the given subject node, False otherwise. This method uses the path virtual field, and so does not perform any query.

Parameters:

• node – the CTENode' for which to determine whether it is an ancestor of the `subject.
• subject – the CTENode for which to determine whether one of its ancestors is the node.

Returns:

True if node is an ancestor of subject, False otherwise.

is_branch(node)

Returns True if the given node is a branch (has at least one child), False otherwise.

Parameters:node – the CTENode for which to determine whether it is a branch. Returns:True if node is a branch, False otherwise.

is_child_of(node, subject)

Returns True if the given node is a child of the given subject node, False otherwise. This method used the parent field, and so does not perform any query.

Parameters:

• node – the CTENode' for which to determine whether it is a child of the `subject.
• subject – the CTENode for which to determine whether one of its children is the node.

Returns:

True if node is a child of subject, False otherwise.

is_descendant_of(node, subject)

Returns True if the given node is a descendant of the given subject node, False otherwise. This method uses the path virtual field, and so does not perform any query.

Parameters:

• node – the CTENode' for which to determine whether it is a descendant of the `subject.
• subject – the CTENode for which to determine whether one of its descendants is the node.

Returns:

True if node is a descendant of subject, False otherwise.

is_leaf(node)

Returns True if the given node is a leaf (has no children), False otherwise.

Parameters:node – the CTENode for which to determine whether it is a leaf. Returns:True if node is a leaf, False otherwise.

is_parent_of(node, subject)

Returns True if the given node is the parent of the given subject node, False otherwise. This method uses the parent field, and so does not perform any query.

Parameters:

• node – the CTENode' for which to determine whether it is a parent of the `subject.
• subject – the CTENode for which to determine whether its parent is the node.

Returns:

True if node is the parent of subject, False otherwise.

is_sibling_of(node, subject)

Returns True if the given node is a sibling of the given subject node, False otherwise. This method uses the parent field, and so does not perform any query.

Parameters:

• node – the CTENode' for which to determine whether it is a sibling of the `subject.
• subject – the CTENode for which to determine whether one of its siblings is the node.

Returns:

True if node is a sibling of subject, False otherwise.

leaves()

Returns a QuerySet of all leaf nodes (nodes with no children).

Returns:A QuerySet of all leaf nodes (nodes with no children).

move(node, destination, position=None, save=False)

Moves the given CTENode node and places it as a child node of the destination CTENode (or makes it a root node if destination is None).

Optionally, position can be a callable which is invoked prior to placement of the node with the node and the destination node as the sole two arguments; this can be useful in implementing specific sibling ordering semantics.

Optionally, if save is True, after the move operation completes (after the CTENode.parent foreign key is updated and the position callable is called if present), a call to Model.save() is made.

Parameters:

• destination – the destination node of this move, None denoting that the node will become a root node.
• position – optional callable invoked prior to placement for purposes of custom sibling ordering semantics.
• save – optional flag indicating whether this model’s save() method should be invoked after the move.

Returns:

this node.

node_as_tree(node, visitor=<function CTENodeManager.<lambda>>, children=<function CTENodeManager.<lambda>>)

Visits a CTENode node and delegates to the (optional) visitor callback, as well as the (optional) children callback, in order to generate a dictionary representation of the node along with its children nodes.

Parameters:

• node – the CTENode for which to generate the representation.
• visitor – optional function responsible for generating the dictionary representation of the node.
• children – optional function responsible for generating a children key and list for the node.

Returns:

a dictionary representation of the structure of the node and its descendant tree.

prepare_delete(node, method, position=None, save=True)

Prepares a given CTENode node for deletion, by executing the required deletion semantics (Pharaoh, Grandmother, or Monarchy).

The method argument can be one of the valid DELETE_METHODS choices. If it is DELETE_METHOD_NONE or None, then the default delete method will be used (as specified from the optional _cte_node_delete_method).

Under the DELETE_METHOD_GRANDMOTHER and DELETE_METHOD_MONARCHY delete semantics, descendant nodes may be moved; in this case the optional position can be a callable which is invoked prior to each move operation (see move() for details).

Furthermore, by default, after each move operation, sub-tree nodes which were moved will be saved through a call to Model.save() unless save is False.

This method delegates move operations to move().

Parameters:

• node – the CTENode to prepare for deletion.
• method – optionally, a delete method to use.
• position – optionally, a callable to invoke prior to each move operation.
• save – flag indicating whether to save after each move operation, True by default.

prepare_delete_grandmother(node, position=None, save=True)

Prepares a given CTENode node for deletion, by executing the DELETE_METHOD_GRANDMOTHER semantics. Descendant nodes, if present, will be moved; in this case the optional position can be a callable which is invoked prior to each move operation (see move() for details).

By default, after each move operation, sub-tree nodes which were moved will be saved through a call to Model.save() unless save is False.

This method delegates move operations to move().

Parameters:

• node – the CTENode to prepare for deletion.
• position – optionally, a callable to invoke prior to each move operation.
• save – flag indicating whether to save after each move operation, True by default.

prepare_delete_monarchy(node, position=None, save=True)

Prepares a given CTENode node for deletion, by executing the DELETE_METHOD_MONARCHY semantics. Descendant nodes, if present, will be moved; in this case the optional position can be a callable which is invoked prior to each move operation (see move() for details).

By default, after each move operation, sub-tree nodes which were moved will be saved through a call to Model.save() unless save is False.

This method delegates move operations to move().

Parameters:

• node – the CTENode to prepare for deletion.
• position – optionally, a callable to invoke prior to each move operation.
• save – flag indicating whether to save after each move operation, True by default.

prepare_delete_pharaoh(node, position=None, save=True)

Prepares a given CTENode node for deletion, by executing the DELETE_METHOD_PHARAOH semantics.

This method does not perform any sub-tree reorganization, and hence no move operation, so the position and save arguments are ignored; they are present for regularity purposes with the rest of the deletion preparation methods.

Parameters:

• node – the CTENode to prepare for deletion.
• position – this is ignored, but present for regularity.
• save – this is ignored, but present for regularity.

root(node)

Returns the CTENode which is the root of the tree in which the given node participates (or node if it is a root node). This method functions through the get() method.

Parameters:node – A CTENode whose root is required. Returns:A CTENode which is the root of the tree in which the given node participates (or the given node if it is a root node).

roots()

Returns a QuerySet of all root CTENode objects.

Returns:a QuerySet of all root CTENode objects.

siblings(node)

Returns a QuerySet of all siblings of a given CTENode node.

Parameters:node – a CTENode whose siblings are required. Returns:A QuerySet of all siblings of the given node.