"""
Phase 2: labs.

Slightly more advanced than Phase 1 — places every lab offering's weekly
labs greedily first, against Phase 1's already-fixed placements. When a
lab can't be placed, this backtracks *recursively*: it bumps an
already-placed lab from earlier in this phase that shares the contested
resource (same instructor or same lab room), and tries to re-place the
stuck lab; if the bumped lab then can't find a new slot either, that
bumped lab is itself backtracked the same way (bump one of *its*
resource-sharing predecessors), and so on, until either everything
settles or the attempt budget is exhausted. Phase 1's sessions are never
touched — only Phase 2's own placements are ever moved.
"""

from . import grid

MAX_BACKTRACK_ATTEMPTS = 2000


def run(board, data):
    """Places every lab offering's weekly labs. Returns this phase's sessions."""
    phase_start = len(board.sessions)
    offerings = [o for o in data["offerings"] if not o["course"]["is_general"] and o["course"]["labs_per_week"] > 0]

    placed_so_far = []  # [(offering, session), ...] placed so far in this phase
    attempts = [0]

    for offering in offerings:
        course = offering["course"]
        room_candidates = board.room_candidates(course["lab_room_id"], board.labs)
        for _ in range(course["labs_per_week"]):
            session = _place_lab_with_backtracking(board, offering, room_candidates, placed_so_far, attempts)
            if session is None:
                print(f"WARNING: could not place a lab for course {offering['course_id']} section {offering['section_id']} ({offering['batch_codes']}) even after backtracking")
            else:
                placed_so_far.append((offering, session))

    return board.sessions[phase_start:]


def _place_lab_with_backtracking(board, offering, room_candidates, placed_so_far, attempts):
    """
    Tries the plain first-fit placement first; if that fails, tries
    bumping each resource-sharing predecessor (most recent first) out of
    the way and recursively re-seating it, backing out cleanly if a given
    bump doesn't lead anywhere. Returns the newly placed session dict, or
    None if no arrangement works within the attempt budget.
    """
    session = board.place_lab(offering, room_candidates, grid.DAYS)
    if session is not None:
        return session

    # Snapshot the current candidates once — recursive calls will extend
    # placed_so_far with their own successful re-seatings, but we only
    # want to consider *this call's* view of what existed when we started.
    candidate_room_ids = {r["room_id"] for r in room_candidates}
    candidates = [
        (other_offering, other_session)
        for other_offering, other_session in placed_so_far
        if _shares_contested_resource(offering, other_session, candidate_room_ids)
    ]

    for other_offering, other_session in reversed(candidates):
        if attempts[0] >= MAX_BACKTRACK_ATTEMPTS:
            return None
        attempts[0] += 1

        if (other_offering, other_session) not in placed_so_far:
            # Already moved by an earlier (failed) branch of this search.
            continue

        placed_so_far.remove((other_offering, other_session))
        board.remove_session(other_session)

        session = board.place_lab(offering, room_candidates, grid.DAYS)
        if session is not None:
            other_room_candidates = board.room_candidates(other_offering["course"]["lab_room_id"], board.labs)
            new_other_session = _place_lab_with_backtracking(board, other_offering, other_room_candidates, placed_so_far, attempts)
            if new_other_session is not None:
                placed_so_far.append((other_offering, new_other_session))
                return session
            # Could not reseat the bumped lab even with recursion — undo
            # our placement and put the bump back exactly as it was.
            board.remove_session(session)
            placed_so_far.append((other_offering, _restore_lab(board, other_offering, other_session)))
            continue

        # Bumping didn't free a usable slot for `offering` — restore and
        # try the next candidate.
        placed_so_far.append((other_offering, _restore_lab(board, other_offering, other_session)))

    return None


def _restore_lab(board, offering, session):
    """Re-marks and re-adds a lab session dict exactly as it was."""
    room = board.data["rooms_by_id"][session["room_id"]]
    for slot_index in session["slot_indices"]:
        board.mark_busy(session["day"], slot_index, session["room_id"], session["instructor_code"], session["batch_codes"])
    return board.add_session(offering, session["day"], session["slot_indices"], room)


def _shares_contested_resource(offering, other_session, candidate_room_ids):
    """
    True if bumping other_session could plausibly free a slot offering
    needs: shares the instructor, a usable lab room, or one of offering's
    own batches (a batch can only be in one place at a time, so another
    session competing for that batch's slot is a real contested resource
    too, not just instructor/room).
    """
    if other_session["instructor_code"] == offering["instructor_code"]:
        return True
    if other_session["room_id"] in candidate_room_ids:
        return True
    return bool(set(other_session["batch_codes"]) & set(offering["batch_codes"]))