並行處理模式（Java）

// LC 1114 — Print in Order
class Foo {
    private CountDownLatch latch1 = new CountDownLatch(1);
    private CountDownLatch latch2 = new CountDownLatch(1);

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        latch1.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        latch1.await();
        printSecond.run();
        latch2.countDown();
    }

    public void third(Runnable printThird) throws InterruptedException {
        latch2.await();
        printThird.run();
    }
}

// LC 1115 — Print FooBar Alternately
class FooBar {
    private int n;
    private Semaphore fooSem = new Semaphore(1);
    private Semaphore barSem = new Semaphore(0);

    public FooBar(int n) { this.n = n; }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooSem.acquire();
            printFoo.run();
            barSem.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barSem.acquire();
            printBar.run();
            fooSem.release();
        }
    }
}

// LC 1188 — Design Bounded Blocking Queue
class BoundedBlockingQueue {
    private Queue<Integer> queue = new LinkedList<>();
    private int capacity;
    private ReentrantLock lock = new ReentrantLock();
    private Condition notFull = lock.newCondition();
    private Condition notEmpty = lock.newCondition();

    public BoundedBlockingQueue(int capacity) { this.capacity = capacity; }

    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try {
            while (queue.size() == capacity) notFull.await();
            queue.offer(element);
            notEmpty.signal();
        } finally { lock.unlock(); }
    }

    public int dequeue() throws InterruptedException {
        lock.lock();
        try {
            while (queue.isEmpty()) notEmpty.await();
            int val = queue.poll();
            notFull.signal();
            return val;
        } finally { lock.unlock(); }
    }

    public int size() { lock.lock(); try { return queue.size(); } finally { lock.unlock(); } }
}

// LC 1117 — Building H2O
class H2O {
    private Semaphore hSem = new Semaphore(2);
    private Semaphore oSem = new Semaphore(0);
    private CyclicBarrier barrier = new CyclicBarrier(3, () -> {
        hSem.release(2);
    });

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSem.acquire();
        releaseHydrogen.run();
        try { barrier.await(); } catch (BrokenBarrierException e) {}
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        // NOTE: sketch only — oSem is initialized to 0 permits and never released,
        // so this acquire() blocks forever. A correct H2O gates O with its own
        // Semaphore(1) (limit one O in flight) and lets the CyclicBarrier(3)
        // rendezvous 2 H + 1 O; the barrier action then release(2)s hSem.
        oSem.acquire();
        releaseOxygen.run();
        try { barrier.await(); } catch (BrokenBarrierException e) {}
    }
}

// java
// Transfer between two accounts without deadlocking against the reverse transfer
// IDEA: order the two locks by a stable id, so t1 (A->B) and t2 (B->A) both take
//       the lower id first and one of them simply waits
void transfer(Account from, Account to, long amount) {
    Account first  = from.id < to.id ? from : to;     // total order over the locks
    Account second = from.id < to.id ? to   : from;
    synchronized (first) {
        synchronized (second) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

// java
// LC 1226 — The Dining Philosophers
// IDEA: a Semaphore(4) means at most 4 philosophers ever hold a fork, so at least one
//       always finds both free — the cycle can never close
// time = O(1) per meal, space = O(n)
class DiningPhilosophers {
    private final ReentrantLock[] forks = new ReentrantLock[5];
    private final Semaphore room = new Semaphore(4);   // n - 1 diners

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
    }

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,  Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,   Runnable putRightFork)
            throws InterruptedException {
        int left = philosopher, right = (philosopher + 1) % 5;

        room.acquire();
        forks[left].lock();
        forks[right].lock();

        pickLeftFork.run(); pickRightFork.run(); eat.run();
        putLeftFork.run();  putRightFork.run();

        forks[right].unlock();
        forks[left].unlock();
        room.release();
    }
}

// java
// LC 1195 — Fizz Buzz Multithreaded
// IDEA: one semaphore per role, all starting at 0 except number(). After printing i,
//       hand the permit to whoever owns i+1, so the order is enforced by construction.
// time = O(n) total, space = O(1)
class FizzBuzz {
    private final int n;
    private final Semaphore num      = new Semaphore(1);   // 1 owns the first turn
    private final Semaphore fizz     = new Semaphore(0);
    private final Semaphore buzz     = new Semaphore(0);
    private final Semaphore fizzbuzz = new Semaphore(0);

    public FizzBuzz(int n) { this.n = n; }

    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 3; i <= n; i += 3) {
            if (i % 5 == 0) continue;                      // 15s belong to fizzbuzz()
            fizz.acquire();
            printFizz.run();
            handOff(i + 1);
        }
    }

    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (int i = 5; i <= n; i += 5) {
            if (i % 3 == 0) continue;
            buzz.acquire();
            printBuzz.run();
            handOff(i + 1);
        }
    }

    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (int i = 15; i <= n; i += 15) {
            fizzbuzz.acquire();
            printFizzBuzz.run();
            handOff(i + 1);
        }
    }

    public void number(Runnable printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 || i % 5 == 0) continue;
            num.acquire();
            printNumber.run();
            handOff(i + 1);
        }
    }

    /** Wake the single thread that owns value i. */
    private void handOff(int i) {
        if (i > n) {                                       // past the end: wake everyone
            num.release(); fizz.release();                 // so nobody is left blocked
            buzz.release(); fizzbuzz.release();
        } else if (i % 15 == 0) fizzbuzz.release();
        else if (i % 3 == 0)    fizz.release();
        else if (i % 5 == 0)    buzz.release();
        else                    num.release();
    }
}