/**
  * 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.map;

import ds.persistent.map.RedBlackTree;
import ds.util.KV;
import ds.util.K;

import static ds.util.K.mkK;
import static ds.util.V.mkV;
import static ds.util.KV.mkPair;

import tests.util.Args;

public class RedBlackWorstCase {

    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 {
	RedBlackTree t;
	final int n;

	Main(int n1) {
	    t = RedBlackTree.empty();
	    n = n1;
	}

	void buildTree() {
	    startTime("building red-black tree by inserting " +
		      n +
		      " elements in ascending order (worst case)");
	    for (int i = 0; i < n; ++i) {
		t = t.insert(mkK(i), mkV(i));
	    }
	    stopTime();
	}

	void deleteTree() {
	    startTime("deleting a red-black tree by removing " +
		      n +
		      " elements in ascending order");
	    for (int i = 0; i < n; ++i) {
		//		msg("" + i);
		t = t.remove(mkK(i));
		//		msg("" + t);
	    }
	    stopTime();
	}

	void lookupAll(int times) {
	    startTime("looking up all elements in tree " + times + " times");

	    boolean found = true;
	    for (int j = 0; j < times; ++j)
		for (KV p : t) {
		    found &= (t.lookup(p.fst) == p.snd);
		}
	    stopTime();
	}

	void traverse(int times) {
	    startTime("traversing all elements in tree " + times + " times");

	    int res = 0;
	    for (int j = 0; j < times; ++j)
		for (KV p : t) {
		    res += p.fst.key;
		}
	    stopTime();
	}

	void stats() {
	    if ( n < 10 )
		msg("t                 = " + t);
	    msg("t.size()          = " + t.size());
	    msg("t.depth()         = " + t.depth());
	    msg("t.minDepth()      = " + t.minDepth());
	    msg("t.inv()           = " + t.inv());
	    msg("");
	}

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

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

	public void run() {
	    nl();
	    buildTree();
	    stats();
	    memStats();
	    classStats();
	    traverse(20);
	    lookupAll(20);
	    deleteTree();
	    stats();
	    classStats();
	}
    }
}