/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

package tests.persistent.queue;

import ds.interfaces.PriorityQueue;

import java.util.Random;

import ds.persistent.queue.BinaryHeap;
import ds.util.PV;
import ds.util.P;

import static ds.util.P.mkP;
import static ds.util.V.mkV;
import static ds.util.PV.mkPair;

import tests.util.Args;

public class BinaryHeapTrace {

    public static void main(String [] args) {
	int noOfElems = Args.getInt(args, 0, 1023);

	(new Main(noOfElems)).run();
    }

    private static
	class Main
	extends tests.util.Main {
	final int n;
	final Random r;

	BinaryHeap h;

	Main(int n1) {
	    n = n1;
	    r = new Random();
	    h = BinaryHeap.empty();
	}

	void buildHeapRandom() {
	    startTime("building binary heap tree by inserting " +
		      n +
		      " random elements)");
	    for (int i = 0; i < n; ++i) {
		int p = r.nextInt();
		if ( n <= 100 )
		    msg("insert " + p + ", " + i);
		h = h.insert(mkP(p), mkV(i));
	    }
	    stopTime();
	}

	void buildHeapAscending() {
	    startTime("building binary heap tree by inserting " +
		      n +
		      " ascending elements");
	    for (int i = 0; i < n; ++i) {
		int p = i;
		if ( n <= 100 )
		    msg("insert " + p + ", " + i);
		h = h.insert(mkP(p), mkV(i));
	    }
	    stopTime();
	}

	void buildHeapDescending() {
	    startTime("building binary heap tree by inserting " +
		      n +
		      " descending elements");
	    for (int i = 0; i < n; ++i) {
		int p = n - i - 1;
		if ( n <= 100 )
		    msg("insert " + p + ", " + i);
		h = h.insert(mkP(p), mkV(i));
	    }
	    stopTime();
	}

	void buildHeapConst() {
	    startTime("building binary heap tree by inserting " +
		      n +
		      " times the same element");
	    for (int i = 0; i < n; ++i) {
		int p = 0;
		if ( n <= 100 )
		    msg("insert " + p + ", " + i);
		h = h.insert(mkP(p), mkV(i));
	    }
	    stopTime();
	}

	void deleteHeap() {
	    startTime("deleting a binary heap tree by removing " +
		      n +
		      " elements in ascending order");
	    for (int i = 0; i < n; ++i) {
		PV pv = h.findMin();
		if ( n <= 100 )
		    msg("remove " + pv.fst.prio + ", " + pv.snd.value);
		h = h.removeMin();
	    }
	    msg("binary heap: h.isEmpty() == " + h.isEmpty());
	    stopTime();
	}

	void stats() {
	    msg("h.size()          = " + h.size());
	    msg("h.depth()         = " + h.depth());
	    msg("h.minDepth()      = " + h.minDepth());
	    msg("h.inv()           = " + h.inv());
	    msg("");
	}

	void memStats() {
	    msg(h.objStats());
	}

	void classStats() {
	    msg(BinaryHeap.stats());
	}

	public void run() {
	    nl();
	    buildHeapRandom();
	    stats();
	    memStats();
	    classStats();
	    deleteHeap();
	    stats();
	    classStats();

	    buildHeapAscending();
	    stats();
	    memStats();
	    classStats();
	    deleteHeap();
	    stats();
	    classStats();

	    buildHeapDescending();
	    stats();
	    memStats();
	    classStats();
	    deleteHeap();
	    stats();
	    classStats();

	    buildHeapConst();
	    stats();
	    memStats();
	    classStats();
	    deleteHeap();
	    stats();
	    classStats();
	}
    }
}