package simpledb;

import java.lang.*;
import java.util.*;

/**
 * Waits-for-graph-based deadlock detector. This detector operates by
 * searching for cycles in the waits-for graph, and aborting
 * transactions as necessary to break the cycles.
 *
 * Alas, it DOES NOT YET WORK. Currently passes the deadlock test but
 * fails grader test 7.
 *
 * @author <a href="mailto:drkp@mit.edu">Dan R. K. Ports</a>
 */
public class WaitsForDeadlockDetector extends AbstractDeadlockDetector {
    
    private LockRequest lastCheck;
    
    /**
     * Creates a new <code>WaitsForDeadlockDetector</code> instance.
     */
    public WaitsForDeadlockDetector(LockManager lm) {
        super(lm);
        
    }

    public synchronized void waitingForLock(PageId pid,
                                            TransactionId tid,
                                            boolean exclusive) {
        super.waitingForLock(pid, tid, exclusive);

        checkForDeadlockAll();
    }

    public synchronized void lockAcquired(PageId pid,
                                          TransactionId tid) {
        super.lockAcquired(pid, tid);

        checkForDeadlockAll();
    }

    public synchronized void transactionComplete(TransactionId tid,
                                                 boolean commit) {
        super.transactionComplete(tid, commit);

        checkForDeadlockAll();
    }


    private synchronized void checkForDeadlock(LockRequest req) {
        LockRequest deadlocker =
            checkForDeadlockInt(req, new HashSet(), req);
        
        if (deadlocker != null) {
            breakDeadlock(req);
        }
    }

    private synchronized LockRequest
        checkForDeadlockInt(LockRequest start, Set<TransactionId> seen,
                            LockRequest cur)
    {
        seen.add(cur.tid);

        // Figure out who we're waiting for
        Set<TransactionId> waitingFor = new HashSet();

        if (lockManager.exclusiveHolder(cur.pid) != null) {
            waitingFor.add(lockManager.exclusiveHolder(cur.pid));
        }

        if (cur.exclusive) {
            for (TransactionId tid :
                     lockManager.sharedHolders(cur.pid)) {
                waitingFor.add(tid);
            }
        }

        // Now figure out what they're waiting on, if anything, and
        // recurse on those lock requests
        for (TransactionId tid : waitingFor) {

            if (tid == cur.tid) {
                continue;
            }

            if (seen.contains(tid)) {
                return cur;
            }

            if (lockRequestsByTid.get(tid) != null) {
                for (LockRequest req :
                         lockRequestsByTid.get(tid)) {
                    LockRequest deadlocker =
                        checkForDeadlockInt(start, seen, req);
                    if (deadlocker != null) {
                        return deadlocker;
                    }
                }
            }
        }

        return null;
    }

    private synchronized void checkForDeadlockAll() {
        Set<TransactionId> allSeen = new HashSet();

        for (TransactionId tid : lockRequestsByTid.keySet()) {
            if (allSeen.contains(tid)) {
                continue;
            }

            for (LockRequest req : lockRequestsByTid.get(tid)) {
                LockRequest deadlocker =
                    checkForDeadlockInt(req, allSeen, req);

                if (deadlocker != null) {
                    breakDeadlock(deadlocker);
                    return;
                }
            }
        }
    }
}