Bounded Blocking Queue

Problem

Implement BoundedBlockingQueue(capacity) for producer-consumer use between threads:

• put(item): append item; if the queue holds capacity items, block until space is available.
• get() -> item: remove and return the oldest item; if the queue is empty, block until an item arrives.
• size() -> int: current number of items.

Guarantees: FIFO order per producer (items from one producer come out in the order that producer put them), no item is ever lost or delivered twice, the queue never holds more than capacity items, and blocked callers wake when their condition becomes true without spinning. Multiple producers and multiple consumers may run at once. Do not use queue.Queue; build it from threading.Lock and threading.Condition and explain the choices.

• capacity >= 1.
• Items may be any object, including None, so you cannot use None as a sentinel inside the queue.

Examples

• Capacity 2: producer puts 1, 2, 3. The third put blocks until a consumer calls get() (which returns 1), then 3 is accepted.
• 4 producers each put 1,000 distinct items, 4 consumers drain 4,000 items total → the multiset of consumed items equals the multiset produced, and size() never exceeded capacity at any observed moment.
• Consumer calls get() on an empty queue; 50 ms later a producer puts "x" → the consumer returns "x", having slept rather than spun.

Hints

1. A lock protects the list, but a lock cannot make a thread wait for "there is room." You need a way to sleep and be woken when the state changes.
2. There are two distinct things a thread can wait for: not-full (producers) and not-empty (consumers). Waking everyone for every change works but is wasteful; waking the right group is better.
3. After waking, re-check the condition in a loop. Another thread may have consumed the space between the notify and your wake-up.