Spaces:
Running
Running
File size: 3,543 Bytes
d631808 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
# This module contains a single function, `c3linear_merge`.
# The function is generic enough to be in its own module.
#
# - Copyright (c) 2019 Vitaly R. Samigullin
# - Adapted from https://github.com/pilosus/c3linear
# - Adapted from https://github.com/tristanlatr/pydocspec
from __future__ import annotations
from collections import deque
from itertools import islice
from typing import TypeVar
_T = TypeVar("_T")
class _Dependency(deque[_T]):
"""A class representing a (doubly-ended) queue of items."""
@property
def head(self) -> _T | None:
"""Head of the dependency."""
try:
return self[0]
except IndexError:
return None
@property
def tail(self) -> islice:
"""Tail of the dependency.
The `islice` object is sufficient for iteration or testing membership (`in`).
"""
try:
return islice(self, 1, self.__len__())
except (ValueError, IndexError):
return islice([], 0, 0)
class _DependencyList:
"""A class representing a list of linearizations (dependencies).
The last element of DependencyList is a list of parents.
It's needed to the merge process preserves the local
precedence order of direct parent classes.
"""
def __init__(self, *lists: list[_T | None]) -> None:
"""Initialize the list.
Parameters:
*lists: Lists of items.
"""
self._lists = [_Dependency(lst) for lst in lists]
def __contains__(self, item: _T) -> bool:
"""Return True if any linearization's tail contains an item."""
return any(item in lst.tail for lst in self._lists)
def __len__(self) -> int:
size = len(self._lists)
return (size - 1) if size else 0
def __repr__(self) -> str:
return self._lists.__repr__()
@property
def heads(self) -> list[_T | None]:
"""Return the heads."""
return [lst.head for lst in self._lists] # type: ignore[misc]
@property
def tails(self) -> _DependencyList:
"""Return self so that `__contains__` could be called."""
return self
@property
def exhausted(self) -> bool:
"""True if all elements of the lists are exhausted."""
return all(len(x) == 0 for x in self._lists)
def remove(self, item: _T | None) -> None:
"""Remove an item from the lists.
Once an item removed from heads, the leftmost elements of the tails
get promoted to become the new heads.
"""
for i in self._lists:
if i and i.head == item:
i.popleft()
def c3linear_merge(*lists: list[_T]) -> list[_T]:
"""Merge lists of lists in the order defined by the C3Linear algorithm.
Parameters:
*lists: Lists of items.
Returns:
The merged list of items.
"""
result: list[_T] = []
linearizations = _DependencyList(*lists) # type: ignore[arg-type]
while True:
if linearizations.exhausted:
return result
for head in linearizations.heads:
if head and (head not in linearizations.tails):
result.append(head) # type: ignore[arg-type]
linearizations.remove(head)
# Once candidate is found, continue iteration
# from the first element of the list.
break
else:
# Loop never broke, no linearization could possibly be found.
raise ValueError("Cannot compute C3 linearization")
|