// Homework 4+5. Please turn in your homework to the TA at the *beginning* of the discussion section. Note that all 
// C++ code that you use as part of your solution must be real C++ code (that is, we must be able to compile it).
// Do *not* express your solution in pseudo code. In order to make sure that your ideas work, compile your
// code and test it thoroughly. 

// THIS HOMEWORK WILL HELP YOU UNDERSTAND *ALL* OF THE MOST IMPORTANT CONCEPTS NEEDED FOR PROJECT 2.




// For the 1st problem, you'll need to use condition variables and locks. Think about what are the conditions that
// each type of car (either a car traveling left or one traveling right) might have to wait for. Think about what variable(s) 
// need to be protected by a lock. 

// Remember that when signaling a condition, you must unlock the mutex *after* signaling. This avoids all kinds
// of weird, unexpected behaviors. If you want to know more about why you need to unlock after signaling, please
// take a look at this explanation: http://www.domaigne.com/blog/computing/condvars-signal-with-mutex-locked-or-not/

Problem 1.) You have been hired to synchronize traffic over a narrow
light-duty bridge on a public highway. Traffic may only cross the
bridge in one direction at a time, and if there are ever more than 3
vehicles on the bridge at one time, it will collapse under their
weight. In this system, each car is represented by one thread, which
executes the procedure OneVehicle when it arrives at the bridge:

enum Direction (East, West);
OneVehicle(Direction direc)
{
	ArriveBridge(direc); // needs to make sure the car can enter the bridge
	CrossBridge(direc);  // doesn't really do anything; just prints a message
	ExitBridge(direc);   // needs to make sure that cars that are eventually 
                             // waiting to cross will be able to do so
}

In the code above, direc gives the direction in which the vehicle will
cross the bridge. 

(a) Write the procedures ArriveBridge and ExitBridge
(the CrossBridge procedure should just print out a debug message),
using locks and condition variables. ArriveBridge must not
return until it safe for the car to cross the bridge in the given
direction (it must guarantee that there will be no head-on collisions
or bridge collapses). ExitBridge is called to indicate that the caller
has finished crossing the bridge; ExitBridge should take steps to let
additional cars cross the bridge. This is a lightly-travelled rural
bridge, so you do not need to guarantee fairness or freedom from
starvation. 

(b) In your solution, if a car arrives while traffic is
currently moving in its direction of travel across the bridge, but
there is another car already waiting to cross in the opposite
direction, will the new arrival cross before the car waiting on the
other side, after the car on the other side, or is it impossible to
say? Explain briefly.

(This problem was stolen from Tom Anderson at the University of Washington)



Problem 2.)

1.) Implement semaphores with monitors.

Your semaphore should be declared as a struct:

struct {
    (...)   // variables, locks, conditional variables, etc
} semaphore_t;


The functions that operate on a given semaphore are:
down(semaphore_t &s) {
   (...)
}
and

up(semaphore_t &s) {
   (...)
}


// Remember that a semaphore implements two functions: up()  (also known as V)   and down()  (also known as P)
// The monitor functions that are available to you are lock(), unlock(), wait() and signal().
// It might help to remember that a semaphore is basically a special type of *counter* that blocks
// in some cases.

// For more details on the difference between semaphores and monitors, please take look at the lecture notes;
// this might also help: http://wiki.answers.com/Q/What_is_basic_difference_between_semaphore_and_monitor_in_operating_system