class FilePrio
{
    Evenement[] tas ; // tas[0] est inutilis'e
    int n ;

    FilePrio (int capacite) {
        tas = new Evenement [capacite+1] ;
        n = 0 ;
    }

    static int gauche (int i) {
        return 2*i ;
    }

    static int droit (int i) {
        return 2*i + 1 ;
    }

    static int pere (int i) {
        return i/2 ;
    }

    void echange (int i, int j) {
        Evenement inter = tas[i] ;
        tas[i] = tas[j] ;
        tas[j] = inter ;
    }

    void ajouter (Evenement e) {
        if (n >= tas.length) 
            throw new Error ("File pleine.") ;
        n++ ;
        tas[n] = e ;
        int pos = n ; // Position de l''ev`enement ins'er'e
        int date = e.getDate () ;
        while (pos > 1 && date < tas[pere(pos)].getDate ()) {
            echange (pos, pere(pos)) ;
            pos = pere(pos) ;
        }
    }

    boolean nonVide () {
        return n >= 1 ;
    }

    Evenement retirerMin () {
        if (n < 1)
            throw new Error ("File vide.") ;
        Evenement min = tas[1] ;
        n-- ;
        if (n >= 1) {
            tas[1] = tas[n+1] ; 
            descendre (1) ;
        }
        return min ;
    }

    /* Fait descendre l' 'ev'enement en position i
     * tant qu'il a une date plus grande que celle d'un de ses deux fils. */
    void descendre (int i) { 
        int di = tas[i].getDate () ;
        int imin = i ; // Evenement de date minimale entre i et ses deux fils
        int g = gauche(i), d = droit (i) ;
        if (g <= n && tas[g].getDate () < tas[imin].getDate ()) { 
                // Il y a un fils gauche et sa date est plus petite.
                imin = g ;
        }
        if (d <= n && tas[d].getDate () < tas[imin].getDate ()) { 
                // Il y a un fils droit et sa date est plus petite.
                imin = d ;
        }
        if (imin != i) {
            echange (i, imin) ;
            descendre (imin) ;
        }
    }

    public static void main (String[] args) {
        FenEcran fen = new FenEcran (300) ;
        FilePrio fp = new FilePrio (10000) ;
/*
        fp.ajouter (new EvCarre (0, 0, 12)) ;
        fp.ajouter (new EvCarre (100, 28, 0)) ;

        fp.ajouter (new Pyramide (0, 40, 50,50, 150, 150)) ;
        fp.ajouter (new Pyramide (100, 150, 60,40, 200, 140)) ;
        fp.ajouter (new Pluie (-50, 240, 256, 9)) ;

        fp.ajouter (new Entrelas (0, 2, new Point (60, 80),
                                  new Point (30, 200), new Point (130, 300))) ;

        fp.ajouter (new Pates (0, 2, new Point (5, 5), new Point (250, 250), 2, 255)) ;
*/
        fp.ajouter (new Gravite (0, 170, 10.f, 30.f, 40.f, 0.f, 250.f, 250.f)) ;
        fp.ajouter (new Gravite (500, 90, 70.f, 120.f, 60.f, -80.f, 250.f, 250.f)) ;
        fp.ajouter (new Gravite (1000, 230, 200.f, 40.f, 0.f, 0.f, 250.f, 250.f)) ;
/*
        fp.ajouter (new PyrInf (0, 300, 2, 10, 15, 250, 250, 50,50, 150,150)) ;
        fp.ajouter (new PyrInf (0, 150, 100, 10, 15, 250, 250, 60,40, 200,140)) ;
*/        

        long tpsDep = java.lang.System.currentTimeMillis() ;
        while (fp.nonVide ()) {
            Evenement e = fp.retirerMin () ;
            while (java.lang.System.currentTimeMillis() + 5 
                   < tpsDep + e.getDate ())
                try { // Dormir un peu jusqu'`a e.getDate()
                    Thread.sleep (5) ;
                } catch (InterruptedException exc) {}
            //System.out.println (java.lang.System.currentTimeMillis() - tpsDep + " " + e.getDate ()) ;
            e.effectuer (fen, fp) ;
        }
    }
}