#include "ds/heap.h"
#include "ds/priorityqueue.h"

#include "fxttypes.h"
#include "sort/monotone.h"


#include "aux1/arith1.h"
#include "perm/reverse.h"

#include "aux0/randf.h"  // rnd01()

#include "jjassert.h"

#include "fxtio.h"
#include "fxtiomanip.h"

#include "nextarg.h" // NXARG()

#include "aux1/copy.h"


//% Priority queue.


void
print(char ev, double tev, ulong k)
{
    cout << setw(2) << k << ": ";
    cout << setw(6) << ev;

    cout.flags(ios::left);
    cout << "  @      " << setw(12) << tev << endl;

    cout.flags(ios::right);
}
// -------------------------


//#define RSEED

int
main(int argc, char **argv)
{
#ifdef  RSEED
    cout << " rseed=" << rseed() << endl;
#endif

    ulong n = 10;
    NXARG(n, "Number of elements (0<n<=26)");

//    priority_queue<double, double> Q(n);
    priority_queue<double, char> Q(3, 2); // check grow

    double *t = new double[n];
    char *e = new char[n];
    rnd01(t, n);
//    print("random values:", t, n);
    for (ulong k=0; k<n; ++k)  e[k] = (char)('A' + k);  // events names are A, B, C, ...

    cout << endl;
    cout << "Inserting into piority_queue:" << endl;
    cout << setw(2) << "# " << ": ";
    cout << setw(6) << " event" << "  @  " << setw(10) << "time" << endl;
    for (ulong k=0; k<n; ++k)
    {
        char ev = e[k];
        double tev = t[k];
        print(ev, tev, k);
        jjassert( Q.insert(t[k], e[k]) );
    }

    cout << endl;
    cout << "Extracting from piority_queue:" << endl;
    cout << setw(2) << "# " << ": ";
    cout << setw(6) << " event";
    cout << "  @  " << setw(10) << "time" << endl;
    ulong k = n;
    while ( k )
    {
        --k;

        char ev=' ';  double tev = 0;  // avoid warning 'may be used uninitialized'
        jjassert( Q.extract_next(tev, ev) );
        print(ev, tev, k);
        t[k] = tev;
        e[k] = ev;
    }
    jjassert( 0==Q.num() );

    jjassert( is_monotone(t, n) );

    delete [] t;
    delete [] e;

    return 0;
}
// -------------------------


/// Emacs:
/// Local Variables:
/// MyRelDir: "demo/ds"
/// makefile-dir: "../../"
/// make-target: "1demo DSRC=demo/ds/priorityqueue-demo.cc"
/// make-target2: "1demo DSRC=demo/ds/priorityqueue-demo.cc DEMOFLAGS=-DTIMING"
/// End: