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 toself
), which, whenNone
, indicates a root node. Multiple nodes with aNone
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 fromCTENodeManager
, 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 (thedepth
,path
, andordering
virtual fields) will not work, and any attempt to invoke such methods will result in anImproperlyConfigured
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 anImproperlyConfigured
exception if any errors are encountered. All parameters have default values.All
QuerySet
objects involving CTE nodes use theQuerySet.extra()
semantics in order to specify additionalSELECT
,WHERE
, andORDER_BY
SQL semantics, therefore, they cannot be combined through theOR
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 isNone
orTREE_TRAVERSAL_NONE
, thenDEFAULT_TREE_TRAVERSAL
method is used (which isdfs
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’sMeta
class or the arguments of theorder_by()
method ofQuerySet
.These entries may also contain the virtual field
depth
, which cannot be used by the normalQuerySet
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 orNone
orDELETE_METHOD_NONE
, then the default deletion semanticsDEFAULT_DELETE_METHOD
will be used (which isDELETE_METHOD_PHARAOH
orpharaoh
for the Pharaoh deletion semantics)._cte_node_parent:
A string referencing the name of the
ForeignKey
field which implements the parent relationship, typically calledparent
and automatically inherited from this class.If this parameter is missing, and no field with the name
parent
can be found, then the firstForeignKey
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 calledparent
(specified inDEFAULT_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 isDEFAULT_TABLE_NAME
(which iscte
)._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
orordering
virtual fields (similarly to the_cte_node_order_by
parameter above).A
VARCHAR
primary key will be automatically cast toTEXT
, 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 ispath
),VIRTUAL_FIELD_DEPTH
(which isdepth
), andVIRTUAL_FIELD_ORDERING
(which isordering
).
-
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()
andCTENodeManager.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 defaultNone
).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 theCTENode
superclassdelete
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 thepath
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 theparent
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 thepath
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 theparent
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 theparent
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 isNone
).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 theparent
foreign key is updated and the position callable is called if present), a call toModel.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.
- destination – the destination node of this move,
-
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 involvingCTENode
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 customManager
, you must ensure the following three:- your
Manager
inherits fromCTENodeManager
,
2) if you override the
get_queryset()
method in order to return a customQuerySet
, then your QuerySet must also inherit fromCTENodeManager.CTEQuerySet
, and3) invoke the
_ensure_parameters()
on yourManager
at least once before using aQuerySet
which inherits fromCTENodeManager.CTEQuerySet
, unless you have supplied the necessary CTE node attributes on theCTENode
Model
in some other way.The methods
prepare_delete()
,prepare_delete_pharaoh()
,prepare_delete_grandmother()
, andprepare_delete_monarchy()
can be directly used to prepare nodes for deletion with either the default or explicitly-specified deletion semantics. TheCTENode
abstractModel
defines aCTENode.delete()
method which delegates preparation to this manager.-
ancestors
(node)¶ Returns a
QuerySet
of all ancestors of a givenCTENode
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 defaultchildren
) and a list of childrenCTENode
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 tonode_as_tree()
, which is responsible for invoking thevisitor()
andchildren()
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 defaultNone
).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.
- node – the
-
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 givenCTENode
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 fieldy
, 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 concerningCTENode
objects. This method overrides the defaultget_queryset()
method of theManager
class.Returns: a custom QuerySet
which provides the CTE functionality for all queries concerningCTENode
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 thepath
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.- node – the
-
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 theparent
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.- node – the
-
is_descendant_of
(node, subject)¶ Returns
True
if the given node is a descendant of the given subject node,False
otherwise. This method uses thepath
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.- node – the
-
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 theparent
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.- node – the
-
is_sibling_of
(node, subject)¶ Returns
True
if the given node is a sibling of the given subject node,False
otherwise. This method uses theparent
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.- node – the
-
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 destinationCTENode
(or makes it a root node if destination isNone
).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 theCTENode.parent
foreign key is updated and the position callable is called if present), a call toModel.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.
- destination – the destination node of this move,
-
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.
- node – the
-
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 isDELETE_METHOD_NONE
orNone
, then the default delete method will be used (as specified from the optional_cte_node_delete_method
).Under the
DELETE_METHOD_GRANDMOTHER
andDELETE_METHOD_MONARCHY
delete semantics, descendant nodes may be moved; in this case the optional position can be acallable
which is invoked prior to each move operation (seemove()
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 isFalse
.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.
- node – the
-
prepare_delete_grandmother
(node, position=None, save=True)¶ Prepares a given
CTENode
node for deletion, by executing theDELETE_METHOD_GRANDMOTHER
semantics. Descendant nodes, if present, will be moved; in this case the optional position can be acallable
which is invoked prior to each move operation (seemove()
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 isFalse
.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.
- node – the
-
prepare_delete_monarchy
(node, position=None, save=True)¶ Prepares a given
CTENode
node for deletion, by executing theDELETE_METHOD_MONARCHY
semantics. Descendant nodes, if present, will be moved; in this case the optional position can be acallable
which is invoked prior to each move operation (seemove()
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 isFalse
.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.
- node – the
-
prepare_delete_pharaoh
(node, position=None, save=True)¶ Prepares a given
CTENode
node for deletion, by executing theDELETE_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.
- node – the
-
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 theget()
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 rootCTENode
objects.Returns: a QuerySet
of all rootCTENode
objects.
-
siblings
(node)¶ Returns a
QuerySet
of all siblings of a givenCTENode
node.Parameters: node – a CTENode
whose siblings are required.Returns: A QuerySet
of all siblings of the given node.
- your