/**
  * 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 java.util.Random;

import ds.persistent.map.IntMap;

import ds.util.K;         // example class for keys
import ds.util.V;         // example class for values
import ds.util.KV;        // key value pair
import ds.util.Pair;

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

import tests.util.Args;

public class IntMapTest {

    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 {

	IntMap          t;
	final int       n;
	final Random    r;
        final int       traceTree;

	Main(int n1) {
	    t = IntMap.empty();
	    n = n1;
	    r = new Random(42);
	    traceTree = 255;
	}

	void buildTree() {
	    startTime("building binary patricia tree by inserting " +
		      n +
		      " random integers");
	    for (int i = 0; i < n; ++i) {
		int k = (int)r.nextLong() >>> 1; // test with values >= 0;
		if (n <= traceTree) {
		    // simplify tree output
		    // only the least significant byte
		    // of key is of interest
		    k &= 0xFF;
		}
		t = t.insert(mkK(k), mkV(i));
		/*
		if ( ! t.inv() ) {
		    msg("t.insert(" + k + "," + i + ") violates invariant");
		    msg("t = " + t);
		}
		*/
	    }
	    stopTime();
	}

	void deleteTree() {
	    startTime("deleting a tree by removing " +
		      n +
		      " elements in ascending order");

	    // this only works for persistent data structures
	    // "removal" is done during iteration

	    for (KV p : t) {
		t = t.remove(p.fst);
	    }
	    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() {
	    int s = t.size();
	    if ( s < 256 ) {
		msg("t                 = " + t);
	    }
	    msg("t.inv()           = " + t.inv());
	    msg("t.size()          = " + t.size());
	    msg("");
	    if ( 0 < s && s <= traceTree ) {
		msg("internal tree structure:\n");
		msg(t.showIntMap());
		msg("");
	    }
	}

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

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

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