from __future__ import annotations
import abc
import functools
import types
from collections.abc import Iterable, Mapping, Sequence
from functools import cached_property
from itertools import chain
from typing import TYPE_CHECKING, Any
from immutabledict import immutabledict as idict
import pyop3.obj
from pyop3 import utils
from pyop3.cache import cached_method
from pyop3.constants import DECIDE
from pyop3.exceptions import Pyop3Exception
from pyop3.utils import (
Labeled,
)
if TYPE_CHECKING:
from pyop3.types import *
[docs]
class NodeNotFoundException(Exception):
pass
[docs]
class EmptyTreeException(Exception):
pass
[docs]
class InvalidTreeException(ValueError):
pass
[docs]
class TreeMutationException(Pyop3Exception):
pass
# ah crud, this is another node!
[docs]
class LabeledNodeComponent(pyop3.obj.Object, abc.ABC):
__abstract_record_attrs = ("label",)
[docs]
class MultiComponentLabeledNode(Node, Labeled, pyop3.obj.Object):
__abstract_record_attrs = ("label",)
def __record_post_init(self) -> None:
assert all(cl is not DECIDE for cl in self.component_labels)
if not utils.has_unique_entries(self.component_labels):
raise ValueError("Duplicate component labels found")
@property
def degree(self) -> int:
return len(self.component_labels)
@property
@abc.abstractmethod
def component_labels(self) -> tuple:
pass
@property
def component_label(self):
return utils.just_one(self.component_labels)
[docs]
class AbstractLabeledTreeLike(pyop3.obj.Object):
@property
@abc.abstractmethod
def is_linear(self) -> bool:
pass
@functools.singledispatch
def _as_node_map(obj: Any, /) -> dict:
utils.raise_missing_dispatch_handler(obj)
@_as_node_map.register
def _(node_map: dict, /) -> dict:
return node_map
@_as_node_map.register
def _(node_map: idict, /) -> dict:
return dict(node_map)
@_as_node_map.register
def _(node: Node, /) -> dict:
return {idict(): node}
@_as_node_map.register
def _(none: types.NoneType, /) -> dict:
return {idict(): None}
def _fixup_node_map(*, path: idict, unvisited: dict) -> idict:
if path not in unvisited:
# at a leaf, attach a 'None'
return {path: None}
node = unvisited.pop(path)
if node is None:
# at a leaf, attach a 'None'
return {path: None}
if node.label is DECIDE:
new_label = f"_node_{type(node).__name__}_{len(path)}"
node = node.record_new(label=new_label)
if node.label in path.keys():
raise InvalidTreeException(f"Duplicate label '{node.label}' found along a path")
node_map = {path: node}
for component_label in node.component_labels:
path_ = path | {node.label: component_label}
node_map |= _fixup_node_map(path=path_, unvisited=unvisited)
return node_map
[docs]
class LabeledTree(AbstractLabeledTreeLike):
__abstract_record_attrs = ("node_map",)
def __record_post_init(self) -> None:
for node in self.nodes:
assert node.label is not DECIDE
assert all(cl is not DECIDE for cl in node.component_labels)
# {{{ factory methods
[docs]
@classmethod
def from_iterable(cls, iterable: Iterable, *args, **kwargs) -> LabeledTree:
raise NotImplementedError
@classmethod
def _node_map_from_iterable(cls, iterable: Iterable) -> dict:
node_map = {}
path = idict()
for i, node in enumerate(iterable):
node = cls._as_node(node)
assert node.degree == 1
assert node.label is not DECIDE, "old API"
node_map.update({path: node})
path = path | {node.label: node.component_label}
return node_map
[docs]
@classmethod
def from_nest(cls, nest: Any, *args, **kwargs) -> LabeledTree:
raise NotImplementedError
@classmethod
def _node_map_from_nest(
cls,
nest: Mapping[NodeLike, Sequence[Mapping | NodeLike]] | NodeLike,
*,
_path: ConcretePathT = idict(),
) -> dict:
def as_labeled_node(nodelike):
node = cls._as_node(nodelike)
assert node.label is not DECIDE, "old API"
return node
if not isinstance(nest, Mapping):
node = as_labeled_node(nest)
return {_path: node}
if len(nest) > 1:
raise InvalidTreeException(
"Nest contains multiple nodes at the same level"
)
node, subnests = utils.just_one(nest.items())
node = as_labeled_node(node)
if isinstance(subnests, Node) and node.degree == 1:
subnests = (subnests,)
node_map = {_path: node}
for component_label, subnest in zip(node.component_labels, subnests, strict=True):
path_ = _path | {node.label: component_label}
if isinstance(subnest, Mapping):
sub_node_map = cls._node_map_from_nest(nest=subnest, _path=path_)
else:
sub_node_map = {path_: subnest}
node_map |= sub_node_map
return node_map
@classmethod
def _prepare_node_map(cls, node_map: Any) -> idict:
initial_node_map = _as_node_map(node_map)
final_node_map = _fixup_node_map(path=idict(), unvisited=initial_node_map)
if initial_node_map:
raise InvalidTreeException("There are orphaned entries in the node map")
return idict(final_node_map)
# }}}
def __str__(self) -> str:
if self.is_empty:
return "<empty>"
else:
return "\n".join(
self._stringify(path=idict(), begin_prefix="", cont_prefix="")
)
def __contains__(self, node) -> bool:
return self._as_node(node) in self.nodes
def __bool__(self) -> bool:
"""Return `True` if the tree is non-empty."""
return not self.is_empty
@property
def root(self) -> Node | None:
return self.node_map.get(idict())
@property
def is_empty(self) -> bool:
assert len(self.node_map) > 0
return self.node_map == idict({idict(): None})
@property
def depth(self) -> int:
if self.is_empty:
return 0
else:
return postvisit(self, lambda _, *o: max(o or [0]) + 1)
[docs]
@cached_property
def child_to_parent(self):
child_to_parent_ = {}
for parent_id, children in self.node_map.items():
parent = self._as_node(parent_id)
for i, child in enumerate(children):
child_to_parent_[child] = (parent, i)
return child_to_parent_
[docs]
@cached_property
def nodes(self) -> tuple[Node]:
return tuple(filter(None, self.node_map.values()))
[docs]
def is_leaf(self, node):
return self._as_node(node) in self.leaves
[docs]
def parent(self, node):
node = self._as_node(node)
return self.child_to_parent[node]
def _stringify(
self,
*,
path: ConcretePathT,
begin_prefix: str,
cont_prefix: str,
) -> tuple[str]:
assert not self.is_empty
node = self.node_map[path]
nodestr = [f"{begin_prefix}{node}"]
for i, component_label in enumerate(node.component_labels):
path_ = path | {node.label: component_label}
last_child = i == len(node.component_labels) - 1
next_begin_prefix = f"{cont_prefix}{'└' if last_child else '├'}──➤ "
next_cont_prefix = f"{cont_prefix}{' ' if last_child else '│'} "
if self.node_map[path_]:
nodestr += self._stringify(
path=path_, begin_prefix=next_begin_prefix, cont_prefix=next_cont_prefix
)
return tuple(nodestr)
def _as_node(self, node):
if node is None:
return None
else:
return node if isinstance(node, Node) else self.id_to_node[node]
[docs]
@cached_property
def leaves(self) -> tuple[Node]:
assert False, "old code"
# # Note that this doesn't quite do the right thing for multicomponent axes
# return tuple(self.node_map[parent_path(leaf_path)] for leaf_path in self.leaf_paths)
@property
def is_linear(self) -> bool:
return len(self.leaf_paths) == 1
[docs]
def visited_nodes(self, path: PathT) -> tuple[tuple[Node, NodeComponentLabelT], ...]:
path = as_path(path)
ordered_path = utils.just_one(
path_
for path_ in self.node_map
if path_ == path
)
nodes = []
for path_acc in accumulate_path(ordered_path, skip_last=True):
node = self.node_map[path_acc]
# NOTE: this is kind of obvious
component_label = path[node.label]
nodes.append((node, component_label))
return tuple(nodes)
# TODO interface choice about whether we want whole nodes, ids or labels in paths
# maybe need to distinguish between paths, ancestors and label-only?
@cached_property
def _paths_with_nodes(self):
def paths_fn(node, component_label, current_path):
if current_path is None:
current_path = ()
new_path = current_path + ((node, component_label),)
paths_[node.id, component_label] = new_path
return new_path
paths_ = {}
previsit(self, paths_fn)
return idict(paths_)
[docs]
def ancestors(self, node, component_label):
"""Return the ancestors of a ``(node_id, component_label)`` 2-tuple."""
return idict(
{
nd: cpt
for nd, cpt in self.path(node, component_label).items()
if nd != node.label
}
)
[docs]
@cached_property
def paths(self) -> tuple[idict, ...]:
"""Return all possible paths through the tree."""
return self.node_map.keys()
[docs]
@cached_property
def leaf_paths(self) -> tuple[ConcretePathT, ...]:
"""Return the paths to each leaf of the tree."""
return tuple(path for path, node in self.node_map.items() if node is None)
@property
def leaf_path(self) -> idict:
return utils.just_one(self.leaf_paths)
[docs]
@cached_property
def leaf_node_paths(self):
return tuple(self.path_with_nodes(*leaf) for leaf in self.leaves)
[docs]
@cached_property
def ordered_leaf_node_paths(self):
return tuple(self.path_with_nodes(*leaf, ordered=True) for leaf in self.leaves)
def _node_from_path(self, path):
if not path:
return None
path_ = dict(path)
node = self.root
while True:
cpt_label = path_.pop(node.label)
cpt_index = node.component_labels.index(cpt_label)
new_node = self.node_map.get(node.id, [None] * node.degree)[
cpt_index
]
# if we are a leaf then return the final bit
if path_:
node = new_node
else:
return node, node.components[cpt_index]
assert False, "shouldn't get this far"
[docs]
@cached_property
def node_labels(self):
return frozenset(n.label for n in self.nodes)
[docs]
def find_component(self, node_label, cpt_label, also_node=False):
"""Return the first component in the tree matching the given labels.
Notes
-----
This will return the first component matching the labels. Multiple may exist
but we assume that they are identical.
"""
for node in self.nodes:
if node.label == node_label:
for cpt in node.components:
if cpt.label == cpt_label:
if also_node:
return node, cpt
else:
return cpt
raise ValueError("Matching component not found")
def _relabel_node_map(self, replace_map: Mapping) -> Mapping:
new_node_map = {}
for parent_id, children in self.node_map.items():
new_children = []
for child in children:
if child is not None:
new_child = child.copy(label=replace_map.get(child.label, child.label))
else:
new_child = None
new_children.append(new_child)
new_node_map[parent_id] = new_children
return new_node_map
# TODO, could be improved, same as other Tree apart from [None, None, ...] bit
@staticmethod
def _parse_parent_to_children(node_map) -> idict:
if not node_map:
return idict()
if isinstance(node_map, Node):
# just passing root
node_map = {None: (node_map,)}
else:
node_map = dict(node_map)
if None not in node_map:
raise ValueError("Root missing from tree")
if len(node_map[None]) != 1:
raise ValueError("Multiple roots provided, this is not allowed")
nodes = [
node
for node in chain.from_iterable(node_map.values())
if node is not None
]
if any(
parent not in nodes
for parent in node_map.keys() - {None}
):
raise ValueError("Tree is disconnected")
for node in nodes:
if node not in node_map.keys():
node_map[node] = [None] * node.degree
return idict(node_map)
[docs]
def to_nest(self) -> idict:
return self._to_nest_rec(idict())
def _to_nest_rec(self, path):
node = self.node_map[path]
nest = {node: []}
for component_label in node.component_labels:
path_ = path | {node.label: component_label}
if self.node_map[path_]:
subnest = self._to_nest_rec(path_)
nest[node].append(subnest)
else:
nest[node].append(None)
return idict(nest)
[docs]
class MutableLabeledTreeMixin:
[docs]
def add_node(self, path: PathT | None, node: Node) -> MutableLabeledTreeMixin:
"""Return a new tree with ``node`` attached at ``path``."""
if path is None:
path = self.leaf_path
else:
path = as_path(path)
if self.node_map[path]:
raise TreeMutationException(
"A node already exists at this location."
)
new_leaves = {path | {node.label: cl}: None for cl in node.component_labels}
if self.is_empty:
return self.record_new(node_map=idict({idict(): node}) | new_leaves)
*parent_path, (parent_axis_label, parent_component_label) = path.items()
parent_path = as_path(parent_path)
try:
parent_node = self.node_map[parent_path]
except KeyError:
raise TreeMutationException("Parent node does not exist")
if parent_axis_label != parent_node.label or parent_component_label not in parent_node.component_labels:
raise TreeMutationException("Bad parent descriptor")
return self.record_new(node_map=self.node_map | {path: node} | new_leaves)
[docs]
def add_subtree(self, path: PathT | None, subtree: LabeledTree) -> MutableLabeledTreeMixin:
"""Attach another tree to a leaf of the current tree."""
if path is None:
path = self.leaf_path
path = as_path(path)
if path not in self.leaf_paths:
raise TreeMutationException("Can only attach a subtree to an existing leaf")
if subtree.is_empty:
return self
# TODO: breaks abstraction
from pyop3.axis_tree.tree import _UnitAxisTree
if isinstance(subtree, _UnitAxisTree):
return self
node_map = dict(self.node_map)
for subpath, subnode in subtree.node_map.items():
assert not (path.keys() & subpath.keys())
node_map[path | subpath] = subnode
return self.record_new(node_map=idict(node_map))
[docs]
def subtree(self, path: PathT) -> MutableLabeledTreeMixin:
"""Return the subtree with ``path`` as the root."""
path = as_path(path)
if path not in self.node_map:
raise TreeMutationException("Provided path does not exist in the tree")
if path in self.leaf_paths:
return type(self)()
trimmed_node_map = self._subtree_node_map(path)
return self.record_new(node_map=trimmed_node_map)
@cached_method()
def _subtree_node_map(self, path: ConcretePathT) -> idict:
trimmed_node_map = {}
path_set = set(path.items())
for orig_path, node in self.node_map.items():
orig_path_set = set(orig_path.items())
if path_set <= orig_path_set:
trimmed_path = idict(
(axis_label, component_label)
for axis_label, component_label in orig_path.items()
if (axis_label, component_label) not in path.items()
)
trimmed_node_map[trimmed_path] = node
return idict(trimmed_node_map)
[docs]
def drop_subtree(self, path: PathT, *, allow_empty_subtree=False) -> MutableLabeledTreeMixin:
path = as_path(path)
if path not in self.node_map:
raise TreeMutationException("Provided path does not exist in the tree")
if path in self.leaf_paths:
if allow_empty_subtree:
return self
# ie dropping nothing is probably unexpected behaviour
else:
assert False
node_map = {}
for orig_path, node in self.node_map.items():
if is_subpath(path, orig_path):
continue
node_map[orig_path] = node
return type(self)(node_map)
[docs]
def drop_node(self, path: PathT) -> MutableLabeledTreeMixin:
path = as_path(path)
to_drop = self.node_map[path]
above = self.drop_subtree(path, allow_empty_subtree=True)
if path in {parent_path(lp) for lp in self.leaf_paths}:
# We are dropping a leaf node, nothing below to add back
return above
else:
below = self.subtree(path | {to_drop.label: to_drop.component_label})
return above.add_subtree(path, below)
[docs]
def as_component_label(component):
if isinstance(component, LabeledNodeComponent):
return component.label
else:
return component
[docs]
def previsit(
tree,
fn,
current_node: Node | None = None,
prev=None,
) -> Any:
if tree.is_empty:
raise RuntimeError("Cannot traverse an empty tree")
current_node = current_node or tree.root
for cpt_label in current_node.component_labels:
next = fn(current_node, cpt_label, prev)
if subnode := tree.child(current_node, cpt_label):
previsit(tree, fn, subnode, next)
[docs]
def postvisit(tree, fn, path: PathT = idict(), **kwargs) -> Any:
"""Traverse the tree in postorder.
Parameters
----------
tree: LabeledTree
The tree to be visited.
fn: collections.abc.Callable
A function to be applied at each node. The function should take
the node to be visited as its first argument, and the results of
visiting its children as any further arguments.
"""
if tree.is_empty:
raise RuntimeError("Cannot traverse an empty tree")
node = tree.node_map[path]
child_results = []
for component_label in node.component_labels:
path_ = path | {node.label: component_label}
if tree.node_map[path_]:
child_result = postvisit(tree, fn, path_, **kwargs)
child_results.append(child_result)
return fn(node, *child_results, **kwargs)
[docs]
@functools.singledispatch
def as_path(obj: Any) -> ConcretePathT:
raise TypeError(f"No handler provided for {type(obj).__name__}")
@as_path.register(idict)
def _(path: idict) -> ConcretePathT:
return path
@as_path.register(Iterable)
def _(path: Iterable) -> ConcretePathT:
return idict(path)
[docs]
def parent_path(path: PathT) -> ConcretePathT:
return idict({
node_label: component_label
for node_label, component_label in list(path.items())[:-1]
})
[docs]
def accumulate_path(path: PathT, *, skip_last: bool = False) -> tuple[ConcretePathT, ...]:
path_acc = idict()
paths = [path_acc]
for node_label, component_label in path.items():
path_acc = path_acc | {node_label: component_label}
paths.append(path_acc)
if skip_last:
paths = paths[:-1]
return tuple(paths)
[docs]
def filter_path(orig_path: PathT, to_remove: PathT) -> ConcretePathT:
orig_path = as_path(orig_path)
to_remove = as_path(to_remove)
filtered_path = {}
for node_label, component_label in orig_path.items():
if (node_label, component_label) not in to_remove.items():
filtered_path[node_label] = component_label
return idict(filtered_path)
[docs]
def is_subpath(subpath: PathT, full_path: PathT) -> bool:
subpath = as_path(subpath)
full_path = as_path(full_path)
return subpath.items() <= full_path.items()