package gizmoball.game;

import gizmoball.NotImplementedException;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import junit.framework.Assert;
import org.apache.log4j.Logger;
import physics.Vect;


/**
 * A represention of the state of a Gizmoball game. It makes use of
 * the composition design pattern: a GameBoard essentially acts as a
 * set of gizmos. The usual set operations (addition, removal, etc. of
 * gizmos) are provided.
 *
 * <p>The gameboard is simulated for one or more quanta with the
 * <code>tick</code> method. With each call, each gizmo is simulated
 * for one tick. The board is then checked for collisions, and any
 * gizmos that have collided are directed to resolve their collisions
 * and execute their triggers.
 *
 * @specfield gizmos : Set(AbstractGizmo) // the gizmos contained in
 * the board
 * @specfield triggers : Set(AbstractTrigger) // all triggers on
 *the board
 * @specfield currentTime : double // the simulated time since
 * construction
 * @specfield dimensions : Vect // the dimensions of the board
 *
 * @derivedfield keypressTriggers : Set(KeypressTrigger) = {x in
 * triggers | x instanceof KeypressTrigger}
 * @derivedfield collisionTriggers : Set(CollisionTrigger) = {x in
 * triggers | x instanceof CollisionTrigger}
 * @derivedfield incomingTriggersForGizmo : Map(AbstractGizmo gizmo,
 * AbstractTrigger trigger) = triggers | trigger.target = gizmo
 * @derivedfield outgoingTriggersForGizmo : Map(AbstractGizmo gizmo,
 * CollisionTrigger trigger) = collisionTriggers | trigger.source =
 * gizmo
 *
 * @author <a href="mailto:drkp@mit.edu">Dan R. K. Ports</a>
 * @version $Id: GameBoard.java,v 1.14 2004/04/27 20:48:54 dan Exp $
 */
public class GameBoard {

    /**
     * An internal class for representing a collision pair: a pair of
     * two gizmos that can collide. The first gizmo must have a
     * collision handler for collisions with the second gizmo
     * (i.e. <code>first.canCollideWith(second ==
     * Collidability.CAN_COLLIDE</code>); it is the one whose
     * <code>timeUntilCollisionWith</code> and <code>collide</code>
     * methods are called.
     */
    private class CollisionPair {
        private AbstractGizmo collider, collidee;

        public CollisionPair(AbstractGizmo collider,
            AbstractGizmo collidee) {
            this.collider = collider;
            this.collidee = collidee;
        }

        public AbstractGizmo getCollider() {
            return collider;
        }

        public AbstractGizmo getCollidee() {
            return collidee;
        }

        public double timeUntilCollision() {
            double time = collider.timeUntilCollisionWith(collidee);

            logger.debug("    timeUntilCollision between " +
                getCollider().getName() + " and " +
                getCollidee().getName() + " is " + time);
            
            return time;
        }

        public void collide() {
            logger.debug("    Collision between " +
                getCollider().getName() + " and " +
                getCollidee().getName());

            fireOutgoingTriggers(getCollider());
            fireOutgoingTriggers(getCollidee());
            
            collider.collide(collidee);
        }
    }

    /**
     * Counter variable used for assigning a unique identifier to
     * each new SimulatorEvent created.
     */
    private int eventCount = 0;
    
    /**
     * A record class for storing information about an event in the
     * simulator event queue.
     *
     * A simulator event can be of one of three types:
     *  END_OF_TICK: pseudo-event representing the end of the
     *      current simulation tick
     *  COLLISION: a collision between the pair <code>pair</code>
     *  RECALCULATE_COLLISION_TIME: recalculate all collisions for
     *      both gizmos in <code>pair</code>. This event is generated
     *      when two gizmos are not expected to collide for
     *      MAX_TICK_TIME seconds; it ensures that the gizmo's
     *      <code>tick</code> method is called at least once per
     *      MAX_TICK_TIME seconds.
     */
    private class SimulatorEvent implements Comparable {
        public double time;
        public int type;
        public CollisionPair pair;
        public int eventId;

        public static final int END_OF_TICK = 0;
        public static final int COLLISION = 1;
        public static final int RECALCULATE_COLLISION_TIME = 2;

        public SimulatorEvent(double time, int type,
            CollisionPair pair) {
            this.time = time;
            this.type = type;
            this.pair = pair;
            eventId = eventCount++;
        }
        
        // Implementation of java.lang.Comparable

        public int compareTo(Object object) {
            SimulatorEvent event = (SimulatorEvent) object;
            if (Double.compare(this.time, event.time) == 0) {
                return this.eventId - event.eventId;
            } // end of if (Double.compare(this.time, event.time) ==
              // 0)
            else {
                return Double.compare(this.time, event.time);
            } // end of if (Double.compare(this.time, event.time) ==
              // 0) else
            
        }
    }    
    
    private Set/*<AbstractGizmo>*/ gizmos;
    private Set/*<CollisionTrigger>*/ collisionTriggers;
    private Map/*<Integer, Set<KeypressTrigger>>*/ keypressTriggers;
    private Map/*<AbstractGizmo, Set<AbstractTrigger>>*/ incomingTriggersForGizmo;
    private Map/*<AbstractGizmo, Set<CollisionTrigger>>*/ outgoingTriggersForGizmo;
    private Set/*<CollisionPair>*/ collisionPairs;
    private SortedSet/*<SimulatorEvent>*/ eventQueue;
    private double currentTime;
    private Vect dimensions;
    
    /**
     * log4j Logger
     */
    private static Logger logger = Logger.getLogger(GameBoard.class);

    
    /**
     * The maximum length of a discrete time segment. The GameBoard
     * may be simulated for longer than this length, but no
     * individual gizmo will be simulated (by its <code>tick</code>
     * method) for longer than this length; the GameBoard will divide
     * the requested time into sub-intervals. The tradeoff in
     * choosing this parameter is between accuracy and speed.
     */
    public static final double MAX_TICK_TIME = 0.1;
    // FIXME: this is a random arbitrary number, choose a better one.

    /**
     * The default dimensions of a GameBoard whose dimensions are not
     * otherwise specified, in L: 20 L x 20 L.
     */
    public static final Vect DEFAULT_DIMENSIONS = new Vect(20, 20);
    
    
    /*
     * Abstraction function:
     *  gizmos = gizmos
     *  triggers = collisionTriggers U keypressTriggers
     *  collisionTriggers = collisionTriggers
     *  keypressTriggers = keypressTriggers
     *  incomingTriggersForGizmo = incomingTriggersForGizmo
     *  outgoingTriggersForGizmo = outgoingTriggersForGizmo
     */

    /**
     * Representation invariant:
     */
    protected void checkRep() {
        // Check fields are not null
        Assert.assertNotNull(gizmos);
        Assert.assertNotNull(collisionTriggers);
        Assert.assertNotNull(keypressTriggers);
        Assert.assertNotNull(incomingTriggersForGizmo);
        Assert.assertNotNull(outgoingTriggersForGizmo);
        Assert.assertNotNull(dimensions);
        
        // This is an extensive checkRep; it's probably worth
        // disabling it for anything that needs to run even remotely
        // fast.
        if (BuildOptions.FAST_CHECK_REP) {
            return;
        } // end of if (BuildOptions.FAST_CHECK_REP)
        
        
        for (Iterator it = gizmos.iterator(); it.hasNext();) {
             Object o = it.next();
             // All items in gizmos are AbstractGizmos
             Assert.assertTrue(o instanceof AbstractGizmo);

             // All gizmos have this as their gameboard
             AbstractGizmo g = (AbstractGizmo) o;
             Assert.assertSame(this, g.getGameBoard());
        } // end of for (Iterator it = gizmos.iterator();
          // it.hasNext();)

        for (Iterator it = collisionTriggers.iterator(); it.hasNext();) {
             Object o = it.next();
             Assert.assertTrue(o instanceof CollisionTrigger);

             CollisionTrigger t = (CollisionTrigger) o;
             Assert.assertTrue(gizmos.contains(t.getTarget()));
             Assert.assertTrue(gizmos.contains(t.getSource()));
             Assert.assertTrue(((Set) incomingTriggersForGizmo.get(
                                    t.getTarget())).contains(t));
             Assert.assertTrue(((Set) outgoingTriggersForGizmo.get(
                                    t.getSource())).contains(t));
        } // end of for (Iterator it = collisionTriggers.iterator();
          // it.hasNext();)

        for (Iterator it = keypressTriggers.entrySet().iterator();
             it.hasNext();) {
            Map.Entry e = (Map.Entry) it.next();
            Assert.assertTrue(e.getKey() instanceof Integer);
            Assert.assertTrue(e.getValue() instanceof Set);

            Set s = (Set) e.getValue();
            for (Iterator it2 = s.iterator(); it2.hasNext();) {
                 Object o = it2.next();
                 Assert.assertTrue(o instanceof KeypressTrigger);
                 KeypressTrigger t = (KeypressTrigger) o;
                 Assert.assertEquals(((Integer) e.getKey()).intValue(),
                     t.getKeyCode());
                 Assert.assertTrue(gizmos.contains(t.getTarget()));
                 Assert.assertTrue(((Set) incomingTriggersForGizmo.get(
                                        t.getTarget())).contains(t));
            } // end of for (Iterator it2 = s.iterator();
              // it2.hasNext();)
        } // end of for (Iterator it =
          // keypressTriggers.entrySet().iterator(); it.hasNext();)

        for (Iterator it = incomingTriggersForGizmo.entrySet().iterator();
             it.hasNext();) {
            Map.Entry e = (Map.Entry) it.next();
            Assert.assertTrue(e.getKey() instanceof AbstractGizmo);
            Assert.assertTrue(gizmos.contains(e.getKey()));

            Set s = (Set) e.getValue();
            for (Iterator it2 = s.iterator(); it2.hasNext();) {
                 Object o = it2.next();
                 Assert.assertTrue(o instanceof AbstractTrigger);
                 AbstractTrigger t = (AbstractTrigger) o;
                 Assert.assertSame(e.getKey(), t.getTarget());
            } // end of for (Iterator it2 = s.iterator();
              // it2.hasNext();)
        } // end of for (Iterator it =
          // incomingTriggersForGizmo.entrySet().iterator();
          // it.hasNext();)

        for (Iterator it = outgoingTriggersForGizmo.entrySet().iterator();
             it.hasNext();) {
            Map.Entry e = (Map.Entry) it.next();
            Assert.assertTrue(e.getKey() instanceof AbstractGizmo);
            Assert.assertTrue(gizmos.contains(e.getKey()));

            Set s = (Set) e.getValue();
            for (Iterator it2 = s.iterator(); it2.hasNext();) {
                 Object o = it2.next();
                 Assert.assertTrue(o instanceof CollisionTrigger);
                 CollisionTrigger t = (CollisionTrigger) o;
                 Assert.assertSame(e.getKey(), t.getSource());
            } // end of for (Iterator it2 = s.iterator();
              // it2.hasNext();)             
        } // end of for (Iterator it =
          // outgoingTriggersForGizmo.entrySet().iterator();
          // it.hasNext();)

        // Validate collision pairs: a pair exists in collisionPairs
        //   iff it has Collidability.CAN_COLLIDE collider-collidee
        //   Collidability
        for (Iterator it = collisionPairs.iterator(); it.hasNext();) {
            CollisionPair cp = (CollisionPair) it.next();
            Assert.assertTrue(gizmos.contains(cp.getCollider()));
            Assert.assertTrue(gizmos.contains(cp.getCollidee()));
            Assert.assertTrue(
                cp.getCollider().canCollideWith(cp.getCollidee()) ==
                Collidability.CAN_COLLIDE);
        } // end of for (Iterator it = collisionPairs.iterator();
          // it.hasNext();)

        Assert.assertTrue(currentTime >= 0);
        
        for (Iterator it = eventQueue.iterator(); it.hasNext();) {
            SimulatorEvent event = (SimulatorEvent) it.next();
            Assert.assertTrue(event.time >= currentTime);
            Assert.assertTrue(event.type !=
                SimulatorEvent.END_OF_TICK); // can only have these in
                                             // the middle of a tick
                                             // simulation
            Assert.assertNotNull(event.pair);
            Assert.assertTrue(collisionPairs.contains(event.pair));
        } // end of for (Iterator it = eventQueue.iterator();
          // it.hasNext();)
        
    }
    
    /**
     * Creates a new <code>GameBoard</code> instance with the
     * specified dimensions. It is empty except for an OuterWallGizmo
     * with the specified dimensions.
     *
     * @param dimensions the dimensions of the GameBoard
     * @throws IllegalArgumentException if dimensions = null
     * @effects constructs this
     */
    public GameBoard(Vect dimensions) {
        if (dimensions == null) {
            throw new IllegalArgumentException("dimensions are null");
        } // end of if (dimensions == null)
        
        gizmos = new HashSet();
        collisionTriggers = new HashSet();
        keypressTriggers = new HashMap();
        incomingTriggersForGizmo = new HashMap();
        outgoingTriggersForGizmo = new HashMap();
        collisionPairs = new HashSet();
        eventQueue = new TreeSet();
        currentTime = 0;
        this.dimensions = dimensions;
        
        addGizmo(new OuterWallsGizmo(dimensions));
        
        checkRep();
    } // GameBoard constructor

    /**
     * Creates a new, empty <code>GameBoard</code> instance with the
     * default dimensions.
     *
     * @see #DEFAULT_DIMENSIONS
     * @effects constructs this
     */
    public GameBoard() {
        this(DEFAULT_DIMENSIONS);
    }
    
    /**
     * Helper function for checking when a collision pair will
     * collide and adding an event to the simulator event queue:
     * either a collision event or a recalculate-collision-time
     * event.
     *
     * @param pair the <code>CollisionPair</code> to add
     */
    private void addCollisionPairEvent(CollisionPair pair) {
        double timeUntilCollision = pair.timeUntilCollision();
        
        if (timeUntilCollision <= MAX_TICK_TIME) {
            eventQueue.add(new SimulatorEvent(
                               currentTime + timeUntilCollision,
                               SimulatorEvent.COLLISION,
                               pair));
        } // end of if (timeUntilCollision <= MAX_TICK_TIME)
        else {
            eventQueue.add(new SimulatorEvent(
                               currentTime + MAX_TICK_TIME,
                               SimulatorEvent.RECALCULATE_COLLISION_TIME,
                               pair));
        } // end of if (timeUntilCollision <= MAX_TICK_TIME) else
    }
    
    /**
     * Helper function to remove all events that have a specified
     * gizmo in their CollisionPair
     *
     * @param gizmo the <code>AbstractGizmo</code> whose events to
     * eliminate
     */
    private void removeEventsInvolving(AbstractGizmo gizmo) {
        // FIXME: optimize this with a map from gizmo to event
        for (Iterator it = eventQueue.iterator(); it.hasNext();) {
            SimulatorEvent event = (SimulatorEvent) it.next();

            if (event.pair != null &&
                (event.pair.getCollider() == gizmo ||
                    event.pair.getCollidee() == gizmo)) {
                it.remove();
            } // end of if
            
        } // end of for (Iterator it = eventQueue.iterator();
          // it.hasNext();)
    }

    /**
     * Helper function to ecalculate all simulator events for a set
     * of gizmos.
     *
     * @param recalculateGizmos the <code>Set</code> of gizmos to
     * recalculate
     */
    private void recalculateSimulatorEventsForGizmos(
        Set recalculateGizmos) {

        for (Iterator it = recalculateGizmos.iterator();
             it.hasNext();) {
            AbstractGizmo gizmo = (AbstractGizmo) it.next();
            removeEventsInvolving(gizmo);
        } // end of for (Iterator it = recalculateGizmos.iterator();
          // it.hasNext();)

        // Recompute collisions for this gizmo.
        // FIXME: optimize this too! (map gizmo to CPair)
        for (Iterator it = recalculateGizmos.iterator();
             it.hasNext();) {
            AbstractGizmo gizmo = (AbstractGizmo) it.next();

            for (Iterator it2 = collisionPairs.iterator();
                 it2.hasNext();) {
                CollisionPair pair = (CollisionPair) it2.next();

                if (pair.getCollider() == gizmo ||
                    pair.getCollidee() == gizmo) {
                    addCollisionPairEvent(pair);
                } // end of if (pair.getCollider() == gizmo ||
                  // pair.getCollidee() == gizmo)
            } // end of for (Iterator it2 = collisionPairs.iterator();
              // it2.hasNext();)
        } // end of for (Iterator it = recalculateGizmos.iterator();
          // it.hasNext();)
    }
    
    /**
     * Add a new gizmo to the game board.
     *
     * @requires gizmo has not already been added to a GameBoard
     * @param gizmo the <code>AbstractGizmo</code> to add
     * @throws IllegalArgumentException if gizmo == null
     * @modifies this
     * @effects gizmos = gizmos U gizmo
     */
    public void addGizmo(AbstractGizmo gizmo) {
        checkRep();

        if (gizmo == null) {
            throw new IllegalArgumentException("gizmo is null");
        } // end of if (gizmo == null)

        if (gizmos.contains(gizmo)) {
            return;
        } // end of if (gizmos.contains(gizmo))

        gizmos.add(gizmo);
        gizmo.setGameBoard(this);
        incomingTriggersForGizmo.put(gizmo, new HashSet());
        outgoingTriggersForGizmo.put(gizmo, new HashSet());

        // Identify the collision pairs involving this gizmo
        for (Iterator it = gizmos.iterator(); it.hasNext();) {
            AbstractGizmo otherGizmo = (AbstractGizmo) it.next();
            if (otherGizmo.canCollideWith(gizmo) ==
                Collidability.CAN_COLLIDE) {
                CollisionPair cp = new CollisionPair(otherGizmo, gizmo);
                collisionPairs.add(cp);
                addCollisionPairEvent(cp);
            } // end of if
            else if (gizmo.canCollideWith(otherGizmo) ==
                Collidability.CAN_COLLIDE) {
                CollisionPair cp = new CollisionPair(gizmo, otherGizmo);
                collisionPairs.add(cp);
                addCollisionPairEvent(cp);
            } // end of else if
            else if (!(gizmo.canCollideWith(otherGizmo) ==
                    Collidability.NEVER_COLLIDE ||
                    otherGizmo.canCollideWith(gizmo) ==
                    Collidability.NEVER_COLLIDE)) {
                throw new RuntimeException(
                    "No collision handler found for some new gizmo pair");
            } // end of else if
        } // end of for (Iterator it = gizmos.iterator(); it.hasNext();)

        checkRep();
    }

    /**
     * Removes a gizmo from the game board.
     *
     * @param gizmo the <code>AbstractGizmo</code> to remove
     * @throws IllegalArgumentException if gizmo == null
     * @modifies this
     * @effects gizmos = gizmos \ gizmo
     * @return false if gizmo was not contained in gizmos, true
     * otherwise 
     */
    public boolean removeGizmo(AbstractGizmo gizmo) {
        checkRep();
        
        if (gizmo == null) {
            throw new IllegalArgumentException("gizmo is null");
        } // end of if (gizmo == null)

        incomingTriggersForGizmo.remove(gizmo);
        outgoingTriggersForGizmo.remove(gizmo);
        removeEventsInvolving(gizmo);
        
        for (Iterator it = collisionPairs.iterator(); it.hasNext();) {
            CollisionPair pair = (CollisionPair) it.next();

            if (pair.getCollider() == gizmo || pair.getCollidee() == gizmo) {
                it.remove();
            } // end of if (pair.getCollider() == gizmo ||
              // pair.getCollidee() == gizmo)
        } // end of for (Iterator it = collisionPairs.iterator();
          // it.hasNext();)
        
        boolean r =  gizmos.remove(gizmo);
        
        checkRep();

        return r;
    }

    /**
     * Returns the set of gizmos on the board.
     *
     * @return an immutable <code>Set</code> view of gizmos
     */
    public Set/*<AbstractGizmo>*/ getGizmos() {
        checkRep();
        
        return Collections.unmodifiableSet(gizmos);
    }

    /**
     * Get the dimensions value.
     *
     * @return the dimensions value.
     */
    public Vect getDimensions() {
        checkRep();
        
        return dimensions;
    }
    
    /**
     * Simulate the gameboard for <code>time</code> seconds. A
     * <i>discretized continuous time simulation</i> is used, which
     * performs individual discrete ticks of various length, chosen
     * to 
     *
     * <p>Simulation is performed according to the following procedure:
     *
     * <ol>
     * <li> If the specified tick time is greater than the constant
     * MAX_TICK_TIME, it is divided into multiple ticks whose length
     * is MAX_TICK_TIME or less. The remainder of the procedure
     * assumes that the tick has been divided up.
     *
     * <li> An END_OF_TICK event is placed in the queue
     * <code>time</code> seconds in the queue.
     *
     * <li> The earliest event in the queue is repeatedly processed,
     * until the END_OF_TICK event is reached:
     *
     *   <ol> <li> All gizmos on the board are simulated up to the
     *   event. Their <code>tick</code> method is called. If it
     *   returns true for any gizmo, indicating that the gizmo's
     *   velocity changed, that gizmo is scheduled for collision
     *   recomputation.
     *   
     *     <ul> <li> If the event represents a collision, the collider
     *     gizmo's collide() method is called. Collision triggers for
     *     both gizmos are fired. Both the collider and collidee are
     *     scheduled for collision recomputation.
     *
     *     <li> If the event is a RECALCULATE_COLLISION_TIME event,
     *     both gizmos associated with it are scheduled for collision
     *     recomputation.
     *
     *     <li> If the event is the END_OF_TICK event, the tick ends.
     *     </ul>
     *
     *   <li>Collision recomputation is performed. First, every event
     *   involving any gizmo identified for collision recomputation is
     *   removed from the queue.
     *  
     *   <li> Next, every pair involving any gizmo identified for
     *   collision recomputation earlier in this processing algorithm
     *   is processed:
     *
     *     <ul> <li> If the time to collision for the pair is less
     *     than MAX_TICK_TIME, a COLLISION event is placed in the
     *     queue at the time the collision will occur.
     *
     *     <li> Otherwise, if the time to collision for the pair is
     *     greater than MAX_TICK_TIME, a RECALCULATE_COLLISION_TIME
     *     event is placed in the queue MAX_TICK_TIME in the future.
     *
     *     </ul>
     *   </ol>
     * </ol>
     *
     * @param time the time to simulate for, in seconds
     * @throws IllegalArgumentException if time <= 0
     * @modifies this
     * @effects this is simulated for <code>time</code> seconds,
     * according to the procedure above.
     */
    public void tick(double time) {
        // Implementation note: tick() divides the provided time into
        // ticks smaller than MAX_TICK_TIME if necessary, then calls
        // doTick() to actually execute the individual ticks
        checkRep();
        
        if (time <= 0) {
            throw new IllegalArgumentException(
                "non-positive time argument");
        } // end of if (time <= 0)

        // If time is longer than the maximum allowed per tick, divide
        // into multiple ticks.
        while (time > MAX_TICK_TIME) {
            time -= MAX_TICK_TIME;
            doTick(MAX_TICK_TIME);
        } // end of while (time > MAX_TICK_TIME)
        if (time > 0) {
            doTick(time);
        } // end of if (time > 0)

        checkRep();
    }

    private void doTick(double time) {
        checkRep();
        logger.debug("doTick " + Double.toString(time));
        
        // Add an end-of-tick simulator event to the queue
        eventQueue.add(new SimulatorEvent(
                           currentTime + time,
                           SimulatorEvent.END_OF_TICK,
                           null));

        // Work through the event queue until we reach the
        // end-of-tick event
        while (true) {
            if (eventQueue.isEmpty()) {
                throw new RuntimeException("event queue ran out");
            } // end of if (eventQueue.isEmpty())
            
            SimulatorEvent currentEvent = (SimulatorEvent) eventQueue.first();
            eventQueue.remove(currentEvent);

            if (currentEvent.pair == null) {
                logger.debug("  event: " + currentEvent.type + " @ " +
                    currentEvent.time);                
            } // end of if (currentEvent.pair == null)
            else {
                logger.debug("  event: " + currentEvent.type +
                    " @ " + currentEvent.time + "  " +
                    currentEvent.pair.getCollider().getName() +
                    "  " + currentEvent.pair.getCollidee().getName());
            } // end of if (currentEvent.pair == null) else
            
            Set gizmosToRecalculateFor = new HashSet();

            if (currentTime != currentEvent.time) {
                // Simulate all gizmos up to the event
                for (Iterator it = gizmos.iterator(); it.hasNext();) {
                    AbstractGizmo gizmo = (AbstractGizmo) it.next();
                    boolean recalculate = gizmo.tick(
                        currentEvent.time - currentTime);
                    if (recalculate) {
                        gizmosToRecalculateFor.add(gizmo);
                    } // end of if (recalculate)
                } // end of for (Iterator it = gizmos.iterator();
                // it.hasNext();)                 
            } // end of if (currentTime != currentEvent.time)

            currentTime = currentEvent.time;
            
            switch (currentEvent.type) {
            case SimulatorEvent.END_OF_TICK:
                // Done processing this tick.
                recalculateSimulatorEventsForGizmos(gizmosToRecalculateFor);
                checkRep();
                return;
                
            case SimulatorEvent.COLLISION:
            case SimulatorEvent.RECALCULATE_COLLISION_TIME:
                // Simulate the collision, if the event is actually a
                // collision
                if (currentEvent.type == SimulatorEvent.COLLISION) {
                    currentEvent.pair.collide(); 
                } // end of if (currentEvent.type == COLLISION)

                // Recalculate the collision times for the gizmos
                // involved in the collision (and others that need to
                // be recalculated)
                gizmosToRecalculateFor.add(currentEvent.pair.getCollider());
                gizmosToRecalculateFor.add(currentEvent.pair.getCollidee());
                recalculateSimulatorEventsForGizmos(gizmosToRecalculateFor);
                break;

            default:
                throw new RuntimeException("Invalid simulator event type");
            } // end of switch (nextEvent.type)
        } // end of while (true)
    }
    
    
    /**
     * Add a new trigger to the gameboard.
     *
     * @param trigger the <code>AbstractTrigger</code> to add
     * @throws IllegalArgumentException if trigger.target is not in
     * gizmos, or trigger is a CollisionTrigger and trigger.source is
     * not in gizmos
     * @throws UnsupportedOperationException if trigger is not a
     * CollisionTrigger or KeypressTrigger
     * @modifies this
     * @effects triggers U= trigger
     */
    public void addTrigger(AbstractTrigger trigger) {
        checkRep();
        
        if (trigger == null) {
            throw new IllegalArgumentException("trigger is null");
        } // end of if (trigger == null)

        if (!gizmos.contains(trigger.getTarget())) {
            throw new IllegalArgumentException(
                "trigger.target isn't in the GameBoard");
        } // end of if (!gizmos.contains(cTrigger.getTarget()))

        if (trigger instanceof CollisionTrigger) {
            CollisionTrigger cTrigger = (CollisionTrigger) trigger;
            
            if (!gizmos.contains(cTrigger.getSource())) {
                throw new IllegalArgumentException(
                    "trigger.source isn't in the GameBoard");
            } // end of if (!gizmos.contains(cTrigger.getSource()))

            ((Set) outgoingTriggersForGizmo.get(
                cTrigger.getSource())).add(
                    cTrigger);
            
            collisionTriggers.add(cTrigger);
        } // end of if (trigger instanceof CollisionTrigger)
        else if (trigger instanceof KeypressTrigger) {
            KeypressTrigger kTrigger = (KeypressTrigger) trigger;

            Integer keyCode = new Integer(kTrigger.getKeyCode());
        
            if (!keypressTriggers.containsKey(keyCode)) {
                // Set doesn't exist in the map, create it
                // (Sure would be nice if Java had a multimap class...)
                keypressTriggers.put(keyCode, new HashSet());
            } // end of if (!keypressTriggers.containsKey(keyCode))

            ((Set) keypressTriggers.get(keyCode)).add(kTrigger);
        } // end of else if (trigger instanceof KeypressTrigger)
        else {
            throw new UnsupportedOperationException(
                "Unsupported trigger type added");
        } // end of else
        
        ((Set) incomingTriggersForGizmo.get(trigger.getTarget())).add(
            trigger);

        checkRep();
    }
    
    /**
     * Remove a trigger from the gameboard.
     *
     * @param trigger the <code>AbstractTrigger</code> to remove
     * @modifies this
     * @effects triggers = triggers \ trigger
     */
    public void removeTrigger(AbstractTrigger trigger) {
        checkRep();
        
        if (trigger instanceof CollisionTrigger) {
            CollisionTrigger cTrigger = (CollisionTrigger) trigger;
            
            collisionTriggers.remove(trigger);
            ((Set) incomingTriggersForGizmo.get(
                trigger.getTarget())).remove(trigger);
            ((Set) outgoingTriggersForGizmo.get(
                cTrigger.getSource())).remove(trigger);
        } // end of if (trigger instanceof CollisionTrigger)
        else if (trigger instanceof KeypressTrigger) {
            KeypressTrigger kTrigger = (KeypressTrigger) trigger;

            Integer keyCode = new Integer(kTrigger.getKeyCode());
        
            if (keypressTriggers.get(keyCode) != null) {
                ((Set) keypressTriggers.get(keyCode)).remove(trigger);
            } // end of if (keypressTriggers.get(keyCode) != null)
            
            ((Set) incomingTriggersForGizmo.get(
                trigger.getTarget())).remove(trigger);
        } // end of else if (trigger instanceof KeypressTrigger)
        else {
            throw new UnsupportedOperationException(
                "Unsupported trigger type");
        } // end of else

        checkRep();
    }

    /**
     * Returns the set of all triggers, of any type.
     *
     * @return an immutable <code>Set</code> view of triggers
     */
    public Set/*<AbstractTrigger>*/ getTriggers() {
        checkRep();
        
        Set s = new HashSet();

        s.addAll(getCollisionTriggers());
        s.addAll(getKeypressTriggers());

        return Collections.unmodifiableSet(s);
    }

    /**
     * Returns the set of all KeypressTriggers
     *
     * @return an immutable <code>Set</code> view of keypressTriggers
     */
    public Set/*<KeypressTrigger>*/ getKeypressTriggers() {
        checkRep();
        
        Set r = new HashSet();

        for (Iterator it = keypressTriggers.values().iterator();
             it.hasNext();) {
            Set s = (Set) it.next();
            r.addAll(s);
        } // end of for (Iterator it =
          // keypressTriggers.values().iterator(); it.hasNext();)

        return Collections.unmodifiableSet(r);
    }

    /**
     * Returns the set of all CollisionTriggers
     *
     * @return an immutable <code>Set</code> view of collisionTriggers
     */
    public Set/*<CollisionTrigger>*/ getCollisionTriggers() {
        checkRep();

        return Collections.unmodifiableSet(collisionTriggers);
    }

    /**
     * Get the set of incoming triggers for a specific gizmo.
     *
     * @param gizmo the <code>AbstractGizmo</code> whose incoming
     * triggers to get
     * @throws IllegalArgumentException if gizmo is null or is not
     * contained in gizmos
     * @return an unmodifiable <code>Set</code> view of
     * incomingTriggersForGizmo(trigger)
     */
    public Set/*<AbstractTrigger>*/ getIncomingTriggersForGizmo(
        AbstractGizmo gizmo) {
        checkRep();
        
        if (gizmo == null) {
            throw new IllegalArgumentException("gizmo was null");
        } // end of if (gizmo == null)

        if (!gizmos.contains(gizmo)) {
            throw new IllegalArgumentException("gizmo was not in gizmos");
        } // end of if (!gizmos.contains(gizmo))

        return Collections.unmodifiableSet(
            ((Set) incomingTriggersForGizmo.get(gizmo)));
    }

    /**
     * Get the set of outgoing triggers for a specific gizmo.
     *
     * @param gizmo the <code>AbstractGizmo</code> whose outgoing
     * triggers to get
     * @throws IllegalArgumentException if gizmo is null or is not
     * contained in gizmos
     * @return an unmodifiable <code>Set</code> view of
     * outgoingTriggersForGizmo(trigger)
     */
    public Set/*<CollisionTrigger>*/ getOutgoingTriggersForGizmo(
        AbstractGizmo gizmo) {
        checkRep();
        
        if (gizmo == null) {
            throw new IllegalArgumentException("gizmo was null");
        } // end of if (gizmo == null)

        if (!gizmos.contains(gizmo)) {
            throw new IllegalArgumentException("gizmo was not in gizmos");
        } // end of if (!gizmos.contains(gizmo))
        
        return Collections.unmodifiableSet(
            ((Set) outgoingTriggersForGizmo.get(gizmo)));
    }

    /**
     * Fire a keypress trigger by key code.
     *
     * @param keyCode the key code to fire triggers for
     * @modifies this
     * @effects all keypress triggers with key code
     * <code>keyCode</code> are fired
     */
    public void fireKeypressTrigger(int keyCode) {
        checkRep();

        Set s = (Set) keypressTriggers.get(new Integer(keyCode));
        if (s == null) {
            return;
        } // end of if (s == null)

        for (Iterator it = s.iterator(); it.hasNext();) {
            KeypressTrigger t = (KeypressTrigger) it.next();
            t.fire();
        } // end of for (Iterator it = s.iterator(); it.hasNext();)

        checkRep();
    }

    /**
     * Helper function that fires all outgoing triggers for a gizmo.
     *
     * @param gizmo the <code>AbstractGizmo</code> to fire outgoing
     * triggers for
     * @effects the fire() method of every trigger in
     * outgoingTriggersForGizmo(gizmo) is called
     */
    private void fireOutgoingTriggers(AbstractGizmo gizmo) {
        Set triggerSet = (Set) outgoingTriggersForGizmo.get(gizmo);
        for (Iterator it = triggerSet.iterator(); it.hasNext();) {
            AbstractTrigger trigger = (AbstractTrigger) it.next();
            trigger.fire();
        } // end of for (Iterator it = triggerSet.iterator();
          // it.hasNext();)
    }
    
} // GameBoard
