graphtage.multiset

A module for representing an edit on a multiset.

This is used by graphtage.MultiSetNode and graphtage.DictNode, since the latter is a multiset containg graphtage.KeyValuePairNode objects.

multiset classes

MultiSetEdit

class graphtage.multiset.MultiSetEdit(from_node: SequenceNode, to_node: SequenceNode, from_set: HashableCounter[TreeNode], to_set: HashableCounter[TreeNode], auto_match_keys: bool = True)

Bases: SequenceEdit

An edit matching one unordered collection of items to another.

It works by using a graphtage.matching.WeightedBipartiteMatcher to find the minimum cost matching from the elements of one collection to the elements of the other.

__init__(from_node: SequenceNode, to_node: SequenceNode, from_set: HashableCounter[TreeNode], to_set: HashableCounter[TreeNode], auto_match_keys: bool = True)

Initializes the edit.

Parameters:
  • from_node – Any sequence node from which to match.

  • to_node – Any sequence node to which to match.

  • from_set – The set of nodes from which to match. These should typically be children of from_node, but this is neither checked nor enforced.

  • to_set – The set of nodes to which to match. These should typically be children of to_node, but this is neither checked nor enforced.

  • auto_match_keys – If True, any graphtage.KeyValuePairNode`s in :obj:`from_set that have keys equal to graphtage.KeyValuePairNode`s in :obj:`to_set will automatically be matched. Setting this to False will require a significant amount more computation for larger dictionaries.

__iter__() Iterator[Edit]

Returns an iterator over this edit’s sub-edits.

Returns:

The result of AbstractCompoundEdit.edits()

Return type:

Iterator[Edit]

__lt__(other)

Tests whether the bounds of this edit are less than the bounds of other.

_debug_tighten_bounds() bool

Adds debugging assertions when tightening bounds; for debugging only

bounds() Range

Returns the bounds of this edit.

This defaults to the bounds provided when this AbstractEdit was constructed. If an upper bound was not provided to the constructor, the upper bound defaults to:

self.from_node.total_size + self.to_node.total_size + 1
Returns:

A range bounding the cost of this edit.

Return type:

Range

edits() Iterator[Edit]

Returns an iterator over this edit’s sub-edits

from_node: TreeNode
has_non_zero_cost() bool

Returns whether this edit has a non-zero cost.

This will tighten the edit’s bounds until either its lower bound is greater than zero or its bounds are definitive.

initial_bounds: Range
is_complete() bool

An edit is complete when no further calls to Edit.tighten_bounds() will change the nature of the edit.

This implementation considers an edit complete if it is valid and its bounds are definitive:

return not self.valid or self.bounds().definitive()

If an edit is able to discern that it has a unique solution even if its final bounds are unknown, it should reimplement this method to define that check.

For example, in the case of a CompoundEdit, this method should only return True if no future calls to Edit.tighten_bounds() will affect the result of CompoundEdit.edits().

Returns:

True if subsequent calls to Edit.tighten_bounds() will only serve to tighten the bounds of this edit and will not affect the semantics of the edit.

Return type:

bool

on_diff(from_node: EditedTreeNode)

A callback for when an edit is assigned to an EditedTreeNode in TreeNode.diff().

This default implementation adds the edit to the node, and recursively calls Edit.on_diff() on all of the sub-edits:

from_node.edit = self
from_node.edit_list.append(self)
for edit in self.edits():
    edit.on_diff(edit.from_node)
Parameters:

from_node – The edited node that was added to the diff

print(formatter: GraphtageFormatter, printer: Printer)

Prints this edit.

This is equivalent to:

formatter.get_formatter(self.sequence)(printer, self.sequence)
property sequence: SequenceNode

Returns the sequence being edited.

This is a convenience function solely to aid in automated type checking. It is equivalent to:

typing.cast(SequenceNode, self.from_node)
tighten_bounds() bool

Delegates to WeightedBipartiteMatcher.tighten_bounds().

to_insert

The set of nodes in to_set that do not exist in from_set.

to_remove

The set of nodes in from_set that do not exist in to_set.

property valid: bool

Returns whether this edit is valid