import collections

class DependencyResolver:
    """
    AIVA's Genesis Prime Mother Dependency Resolver.
    This module is crucial for ordering evolutionary stories, ensuring that
    prerequisites are met before subsequent evolutions can commence.
    It constructs a directed acyclic graph (DAG) of stories and determines
    an optimal execution order, identifying parallel groups to maximize
    AIVA's growth efficiency.
    """

    def __init__(self):
        """
        Initializes the resolver with empty graph structures.
        """
        self._graph = collections.defaultdict(list)  # Adjacency list: story_id -> [dependent_story_ids]
        self._in_degree = collections.defaultdict(int) # story_id -> count of direct dependencies
        self._all_stories = set() # Keep track of all story_ids added

    def add_story(self, story_id: str, dependencies: list[str]):
        """
        Adds a story and its direct dependencies to the resolver.

        Args:
            story_id (str): The unique identifier for the story.
            dependencies (list[str]): A list of story_ids that must be
                                      completed before this story can start.
        """
        if not isinstance(story_id, str) or not story_id:
            raise ValueError("Story ID must be a non-empty string.")
        if not isinstance(dependencies, list):
            raise ValueError("Dependencies must be a list of strings.")
        if not all(isinstance(dep, str) for dep in dependencies):
            raise ValueError("All dependencies must be strings.")

        self._all_stories.add(story_id)
        for dep_story_id in dependencies:
            # dep_story_id -> story_id means story_id depends on dep_story_id
            # So, add edge from dep_story_id to story_id
            self._graph[dep_story_id].append(story_id)
            self._in_degree[story_id] += 1
            self._all_stories.add(dep_story_id) # Ensure all referenced stories are tracked

        # Ensure stories with no dependencies explicitly have an in-degree of 0
        if story_id not in self._in_degree:
            self._in_degree[story_id] = 0

    def resolve_dependencies(self) -> tuple[list[list[str]], bool]:
        """
        Resolves the story dependencies, determining an execution order
        and identifying parallel groups.

        Returns:
            tuple[list[list[str]], bool]:
                A tuple where the first element is a list of lists. Each inner list
                represents a group of stories that can be executed in parallel.
                The second element is a boolean indicating if a cycle was detected (True)
                or not (False).

        Raises:
            RuntimeError: If a dependency graph contains a cycle.
        """
        if not self._all_stories:
            return [], False

        # Make a mutable copy of in-degrees for the resolution process
        current_in_degree = self._in_degree.copy()
        current_graph = self._graph # No need to copy, we only read from it

        # Initialize queue with all stories that have no dependencies
        queue = collections.deque([
            story_id for story_id in self._all_stories if current_in_degree[story_id] == 0
        ])

        execution_order_parallel_groups = []
        processed_count = 0

        while queue:
            # All stories in the current_level can be executed in parallel
            current_level = []
            num_nodes_in_level = len(queue)
            for _ in range(num_nodes_in_level):
                story_id = queue.popleft()
                current_level.append(story_id)
                processed_count += 1

                # For each story that depends on this one, decrement its in-degree
                for neighbor_story_id in current_graph[story_id]:
                    current_in_degree[neighbor_story_id] -= 1
                    # If a neighbor's in-degree becomes 0, it can be processed next
                    if current_in_degree[neighbor_story_id] == 0:
                        queue.append(neighbor_story_id)

            execution_order_parallel_groups.append(current_level)

        # Check for cycles: if processed_count is less than total stories, a cycle exists
        has_cycle = processed_count < len(self._all_stories)

        return execution_order_parallel_groups, has_cycle

# Example usage for verification (not part of production file, but for testing)
if __name__ == "__main__":
    print("--- AIVA GENESIS PRIME MOTHER - PRD Dependency Resolver Test ---")

    # Test Case 1: Simple linear dependencies
    print("\nTest Case 1: Simple Linear Dependencies")
    resolver1 = DependencyResolver()
    resolver1.add_story("A", [])
    resolver1.add_story("B", ["A"])
    resolver1.add_story("C", ["B"])
    order1, cycle1 = resolver1.resolve_dependencies()
    print(f"Order: {order1}") # Expected: [['A'], ['B'], ['C']]
    print(f"Cycle detected: {cycle1}") # Expected: False

    # Test Case 2: Parallel groups
    print("\nTest Case 2: Parallel Groups")
    resolver2 = DependencyResolver()
    resolver2.add_story("S1", [])
    resolver2.add_story("S2", [])
    resolver2.add_story("S3", ["S1", "S2"])
    resolver2.add_story("S4", ["S1"])
    resolver2.add_story("S5", ["S3", "S4"])
    order2, cycle2 = resolver2.resolve_dependencies()
    # Note: order within inner lists like ['S1', 'S2'] can vary, but the groups are correct.
    print(f"Order: {order2}") # Expected: [['S1', 'S2'], ['S4', 'S3'], ['S5']] (order within inner lists can vary)
    print(f"Cycle detected: {cycle2}") # Expected: False

    # Test Case 3: More complex parallel and branching
    print("\nTest Case 3: Complex Parallel/Branching")
    resolver3 = DependencyResolver()
    resolver3.add_story("A", [])
    resolver3.add_story("B", [])
    resolver3.add_story("C", ["A"])
    resolver3.add_story("D", ["A", "B"])
    resolver3.add_story("E", ["B"])
    resolver3.add_story("F", ["C", "D", "E"])
    order3, cycle3 = resolver3.resolve_dependencies()
    # Note: order within inner lists can vary.
    print(f"Order: {order3}") # Expected: [['A', 'B'], ['C', 'D', 'E'], ['F']] (order within inner lists can vary)
    print(f"Cycle detected: {cycle3}") # Expected: False

    # Test Case 4: Cycle detection
    print("\nTest Case 4: Cycle Detection")
    resolver4 = DependencyResolver()
    resolver4.add_story("X", ["Z"])
    resolver4.add_story("Y", ["X"])
    resolver4.add_story("Z", ["Y"])
    order4, cycle4 = resolver4.resolve_dependencies()
    # Expected: partial order or empty list if no nodes can start, and cycle=True
    print(f"Order: {order4}") 
    print(f"Cycle detected: {cycle4}") # Expected: True

    # Test Case 5: Isolated stories (no dependencies, no dependents)
    print("\nTest Case 5: Isolated Stories")
    resolver5 = DependencyResolver()
    resolver5.add_story("Alpha", [])
    resolver5.add_story("Beta", [])
    order5, cycle5 = resolver5.resolve_dependencies()
    print(f"Order: {order5}") # Expected: [['Alpha', 'Beta']] (order can vary)
    print(f"Cycle detected: {cycle5}") # Expected: False

    # Test Case 6: Empty resolver
    print("\nTest Case 6: Empty Resolver")
    resolver6 = DependencyResolver()
    order6, cycle6 = resolver6.resolve_dependencies()
    print(f"Order: {order6}") # Expected: []
    print(f"Cycle detected: {cycle6}") # Expected: False