1
\$\begingroup\$

Initially, I posted this question on StackOverflow. I wanted to know if there's an existing library that implements the concept I have in mind, which is the following.

I want to define a hierarchy/tree, e.g.:

                Commit
             /     |    \
        Feature   Fix    Refactoring
                 /   \
             CodeFix  DocFix

and then be able to define sets where the elements are the nodes of the tree, e.g. X = {Feature, Fix}, Y = {DocFix, Refactoring}. When performing operations, in contrast to the standard python sets, I would like to consider that the elements in the set that are a child and a parent in the tree have the SUBSET-OF relationship (like DocFix and Fix). I would like, therefore, X.union(Y) to yield {DocFix} rather than {}. Please see more examples in the doc-test I provided.

My biggest concern is not to "reinvent the wheel", and I would be grateful to pointers to existing data structures in the standard python library or custom libraries that can be used to fully/partially replace my code. Of course, other comments regarding the code are greatly appreciated.

Cheers, Hlib.

hset.py

from typing import List

from hset.tree import _Tree


class HSet:
    """
    >>> commit = HSet.create_root_element("Commit")
    >>> feature, fix, refactoring = commit.add_children("Feature", "Fix", "Refactoring")
    >>> code_fix, doc_fix = fix.add_children("CodeFix", "DocFix")

    #                Commit
    #             /     |    \
    #        Feature   Fix    Refactoring
    #                 /   \
    #             CodeFix  DocFix

    >>> str(code_fix | doc_fix)
    '{Fix}'
    >>> str(code_fix | refactoring)
    '{CodeFix|Refactoring}'
    >>> str(feature | fix | refactoring)
    '{Commit}'

    >>> str(~ code_fix)
    '{Feature|DocFix|Refactoring}'
    >>> str(~ commit)
    '{}'
    >>> str(~ (feature | refactoring))
    '{Fix}'
    """
    def __init__(self, subtrees: List[_Tree], domain: _Tree):
        self.subtrees = domain.collapse_subtrees(subtrees)
        self.domain = domain

    @classmethod
    def create_root_element(cls, label: str) -> 'HSet':
        tree = _Tree(label, None, [])
        return cls([tree], tree)

    def add_children(self, *labels: str) -> List['HSet']:
        if len(self.subtrees) != 1:
            raise ValueError(f"Cannot add children to this HSet since it has multiple root elements: {self}")
        if self.subtrees[0].children:
            raise ValueError(f"This HSet already has children.")

        trees = self.subtrees[0].add_children(*labels)
        return list(map(lambda t: self._create([t]), trees))

    def _create(self, subtrees: List[_Tree]) -> 'HSet':
        return HSet(subtrees, self.domain)

    def __str__(self):
        return '{' + "|".join(map(lambda x: x.label, self.subtrees)) + '}'

    def __invert__(self) -> 'HSet':
        return self._create(self.domain.complement(self.subtrees))

    def __or__(self, other: 'HSet') -> 'HSet':
        if self.domain != other.domain:
            raise ValueError("Cannot perform operations on HSets with different domains")

        return self._create(self.domain.collapse_subtrees(self.subtrees + other.subtrees))

tree.py

from dataclasses import dataclass
from typing import Optional, List


@dataclass
class _Tree:
    label: str
    parent: Optional['_Tree']
    children: List['_Tree']

    def add_children(self, *labels: str) -> List['_Tree']:
        children = [_Tree(label, self, []) for label in labels]
        self.children = children
        return children

    def collapse_subtrees(self, subtrees: List['_Tree']) -> List['_Tree']:
        if self in subtrees:
            return [self]
        elif not self.children:
            return []
        fully_covered = True
        res = []
        for child in self.children:
            collapsed_child = child.collapse_subtrees(subtrees)
            fully_covered &= (collapsed_child == [child])
            res.extend(collapsed_child)

        return [self] if fully_covered else res

    def complement(self, subtrees: List['_Tree']) -> List['_Tree']:
        if self in subtrees:
            return []
        elif not self.children:
            return [self]
        return [elem for lst in map(lambda x: x.complement(subtrees), self.children) for elem in lst]

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.