Files

54 lines
2.9 KiB
Python

"""The order blockers impose on the ranked items: each blocker above every item it blocks, no blocker in a later release than an item it blocks, and no blockers in a loop."""
import dataclasses
import graphlib
from failure import Failure
from plan.todo_table import Item
from plan.release import version
def blockers_first(scored: list[tuple[Item, float]]) -> list[tuple[Item, float]] | Failure:
"""scored, each blocker that ranks below an item it blocks moved up to just above the first such item; a blocker the table no longer holds was finished or deleted, and is dropped from the Blocked by cells."""
held = {item.id: (item, value) for item, value in scored}
position = {item.id: index for index, (item, _) in enumerate(scored)}
for item, _ in scored:
for blocker in item.blocked_by:
if blocker in held and held[blocker][0].release > item.release:
later, earlier = version(held[blocker][0].release), version(item.release)
return Failure(f"item {item.id}, in release {earlier}, is blocked by item {blocker}, in later release {later}; move item {blocker} to release {earlier} or earlier, or item {item.id} to release {later} or later")
if loop := blocking_loop(held):
return Failure(f"items {', '.join(map(str, loop[:-1]))} and {loop[-1]} block each other in a loop; drop one of the blockers")
placed: set[int] = set()
return [entry for item, _ in scored for entry in place(item.id, held, position, placed)]
def blocking_loop(held: dict[int, tuple[Item, float]]) -> list[int] | None:
"""The IDs of items that block each other in a loop, sorted; None where there is no loop."""
graph = {id_: {blocker for blocker in item.blocked_by if blocker in held} for id_, (item, _) in held.items()}
try:
graphlib.TopologicalSorter(graph).prepare()
except graphlib.CycleError as cycle:
return sorted(set(cycle.args[1]))
return None
def place(id_: int, held: dict[int, tuple[Item, float]], position: dict[int, int], placed: set[int]) -> list[tuple[Item, float]]:
"""id_'s item, preceded by each of its blockers not yet in placed, in score order, each of them preceded in turn by its own blockers; empty where placed already holds id_. Each item returned joins placed. blocking_loop has ruled out a loop, so the recursion ends."""
if id_ in placed:
return []
placed.add(id_)
item, value = held[id_]
blockers = sorted((blocker for blocker in set(item.blocked_by) if blocker in held), key=position.__getitem__)
before = [entry for blocker in blockers for entry in place(blocker, held, position, placed)]
return [*before, (dataclasses.replace(item, blocked_by=tuple(sorted(blockers))), value)]
def blocked_through(id_: int, items: list[Item]) -> set[int]:
"""The IDs of the items id_ blocks, and of those they block in turn."""
found: set[int] = set()
reached = {id_}
while reached:
reached = {other.id for other in items if reached.intersection(other.blocked_by)} - found
found |= reached
return found