psorty2.py

#!/usr/bin/env python3
import sys
from pprint import pprint


class Serial:
    def __init__(self, *args):
        self.list = list(*args)

    def extend(self, *args):
        self.list.extend(*args)

    def append(self, *args):
        self.list.append(*args)

    def __len__(self):
        return len(self.list)

    def __iter__(self):
        return self.list.__iter__()

    def __getitem__(self, item):
        return self.list[item]

    def map(self, func):
        return self.__class__(list(map(func, self.list)))

    def __repr__(self):
        return '(' + ' '.join(map(str, self.list)) + ')'


class Parallel(Serial):
    def __repr__(self):
        return '(' + ' | '.join(map(str, self.list)) + ')'


def resolve_layers(from_layer, fulfilled, dependencies, parents, current=None):
    current = current if current is not None else set()
    prev_layer = from_layer
    layers = []
    tree = Serial()

    while len(prev_layer) > 0:
        next_layer, next_tree = add_layer(prev_layer, fulfilled, dependencies, parents, current)

        if len(next_tree) > 0:
            tree.append(Parallel(next_tree))

        if len(next_layer) == 0:
            break

        fulfilled |= next_layer
        layers.append(next_layer)
        prev_layer = next_layer

    return fulfilled, layers, flatten(tree)


def flatten(input):
    return input.map(flatten_self)


def flatten_self(input):
    if not isinstance(input, Serial) and not isinstance(input, Parallel):
        return input

    if len(input) == 1:
        return input[0]

    return input


def add_layer(last_layer, fulfilled, dependencies, parents, current=None):
    current = current if current is not None else set()

    layer = set()
    order = Parallel()

    new_fulfilled_items = set()
    for item in last_layer:
        if item not in parents:
            # Current item is a stub
            continue

        # Check for new dependencies that might have come free
        children = parents[item]

        for child in children:
            # Check if all dependencies are fulfilled
            if dependencies[child] <= fulfilled and child not in fulfilled and child not in current:
                layer.add(child)

    for item in layer:
        curr_tree = Serial(item)

        new_fulfilled, layers, tree = resolve_layers(last_layer | set(item), fulfilled | set(item),
                                                     dependencies,
                                                     parents, current | layer)

        new_fulfilled_items |= new_fulfilled

        if len(tree) > 0:
            curr_tree.extend(tree)

        order.append(curr_tree)

    layer |= new_fulfilled_items

    return layer, flatten(order)


dependencies = dict()
parents = dict()
entities = set()
tree = dict()

for line in sys.stdin:
    items = line.strip().split(' ')

    entity = items[0].strip()

    if entity == '':
        continue

    entities.add(entity)

    if len(items) == 1:
        continue

    dep = items[1].strip()

    if dep == '':
        continue

    entities.add(dep)

    # Make a symmetric dictionary of what depends on what
    # And what needs what
    if dep not in dependencies:
        dependencies[dep] = set()

    dependencies[dep].add(entity)

    if entity not in parents:
        parents[entity] = set()

    parents[entity].add(dep)

# Get all items without dependencies
top = dependencies.keys() ^ entities

TOP_KEY = ''
parents[TOP_KEY] = set(top)

start = set()
start.add(TOP_KEY)

for item in parents[TOP_KEY]:
    dependencies[item] = set(start)

fulfilled, layers, tree = resolve_layers(set(start), set(start), dependencies, parents)

tree = flatten_self(tree)
print(' '.join(map(str, tree)))