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

import ds.persistent.map.BinaryTree;
import ds.util.KV;

import static ds.persistent.map.BinaryTree.empty;

public abstract class MainBinaryTree
    extends tests.util.Main {

    protected BinaryTree t;
    protected final int n;

    protected MainBinaryTree(int n1) {
	t = (BinaryTree)empty();
	n = n1;
    }

    protected abstract void buildTree();
    protected abstract void removeAll();

    protected void balanceTree() {
	startTime("balance tree");
	t = t.balance();
	stopTime();
    }

    protected 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();
    }

    protected 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();
    }

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

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

    protected void classStats() {
	msg(BinaryTree.stats());
    }

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