/*
 * bisectcost.c: Estimate cost of bisection and related search strategies
 * 	given the expected cost of detecting success and failure, respectively.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * Copyright (c) 2009 Paul E. McKenney, IBM Corporation.
 */

#include <stdio.h>

double failcost = 0.;
double successcost = 1.;
double searchcost = 0.;	/* cumulative cost of a given search. */
int maxversion = 100;	/* assumed to fail, version 0 assumed to succeed. */
int minfailversion = 3;	/* lowest-numbered version that fails. */

int probe(int version)
{
	if (version >= minfailversion) {
		searchcost += failcost;
		return 0; /* probed version failed. */
	}
	searchcost += successcost;
	return 1; /* probed version succeeded. */
}

double powersearch(double highweight)
{
	int low = 1;
	int mid;
	int high = maxversion - 1;
	double lowweight = 1.0;
	double normweight = highweight + 1.0;

	while (high > low + 1) {
		mid = ((double)high * highweight +
		       (double)low * lowweight) /
		      normweight + 0.5;
		if (mid == high)
			mid--;
		else if (mid == low)
			mid++;
		if (probe(mid))
			low = mid;
		else
			high = mid;
	}
	return searchcost;
}

void evalpower_size(int size_ary[], int size_ary_size, double myfailcost, double mysuccesscost, double highweight)
{
	int i;
	int j;
	double cumcost;
	double curcost = 0;

	failcost = myfailcost;
	successcost = mysuccesscost;
	for (i = 0; i < size_ary_size; i++) {
		cumcost = 0.0;
		for (j = 1; j <= size_ary[i]; j++) {
			maxversion = size_ary[i];
			searchcost = 0.0;
			minfailversion = j;
			curcost = powersearch(highweight);
			cumcost += curcost;
		}
		printf("fc: %g  sc: %g  hw: %g  nv: %d  cumcost: %g  cost %g\n",
		       myfailcost, mysuccesscost, highweight, size_ary[i],
		       cumcost, cumcost / size_ary[i]);
	}
}

void evalpower_weight(double weight_ary[], int weight_ary_size, double myfailcost, double mysuccesscost, int mymaxversion)
{
	int i;
	int j;
	double cumcost;
	double curcost = 0;

	failcost = myfailcost;
	successcost = mysuccesscost;
	for (i = 0; i < weight_ary_size; i++) {
		cumcost = 0.0;
		for (j = 1; j <= maxversion; j++) {
			maxversion = mymaxversion;
			searchcost = 0.0;
			minfailversion = j;
			curcost = powersearch(weight_ary[i]);
			cumcost += curcost;
		}
		printf("fc: %g  sc: %g  hw: %g  nv: %d  cumcost: %g  cost %g\n",
		       myfailcost, mysuccesscost, weight_ary[i], mymaxversion,
		       cumcost, cumcost / mymaxversion);
	}
}

int main(int argc, char *argv[])
{
	int size_ary[] = { 2, 4, 8, 16, 32, 64, 128 };
	int size_ary_size = sizeof(size_ary) / sizeof(size_ary[0]);
	double weight_ary[] = {
		100., 10., 9., 8., 7., 6., 4., 3., 2.,
		1.,
		0.5, 0.25, 0.1, 0.01
	};
	int weight_ary_size = sizeof(weight_ary) / sizeof(weight_ary[0]);

	/* printf("varying sizes\n");
	evalpower_size(size_ary, size_ary_size, 0.0, 1.0, 1.0); */
	printf("varying weights 35\n");
	evalpower_weight(weight_ary, weight_ary_size, 0.1, 1.0, 35);
	printf("varying weights 128\n");
	evalpower_weight(weight_ary, weight_ary_size, 0.1, 1.0, 128);
	printf("varying weights 1024\n");
	evalpower_weight(weight_ary, weight_ary_size, 0.1, 1.0, 1024);
	printf("varying weights 1,000,000\n");
	evalpower_weight(weight_ary, weight_ary_size, 0.1, 1.0, 1000000);
}