#define WANT_OBFUSCATING_OPERATORS

#include <iostream>
#include <cln/integer.h>
#include <cln/integer_io.h>
#include <cln/io.h>
#include <math.h>
#include "palindromic.h"

using namespace std;
using namespace cln;

bool greedy_binary(int bits, cl_I input, int start) {

	bool lsb, msb;
	int reverse = bits - start - 1;

	// we could make this bits/2, I think. or bin.getNumVars()
	for (int counter = start; counter < reverse; counter++) {
	/*	lsb = (input >> counter) & 1;
		msb = (input >> reverse) & 1;*/
		lsb = logbitp(counter, input);
		msb = logbitp(reverse, input);

		reverse--;

		if (lsb != msb) return(false);
	}

	return(true);
}
		

void check_try(Palindromic binary, Palindromic decimal, cl_I residue, int
		decimal_pos, cl_I cur_try, int last_decimal, bool force_on,
		cl_I * binary_running_sum, cl_I * decimal_running_sum,
		unsigned long long & ctr, unsigned long long & actr) {
	

	// binary: obvious
	// decimal: again, obvious
	// residue: difference given to previous bits. Must be subtracted
	// 	for the routine to work
	// decimal_pos: current decimal position
	// force_on: Should the bit be forced on?
	
	static cl_I adjusted_cur_try, out_residue;
	bool contradiction, less_than_binary, should_have_binary_on;

	int bits = binary.getDigits();

	// cur_try starts with zeroes at our current position.
	
	if (decimal_pos + 10 == last_decimal) 
		cout << ctr << " recursions so far." << endl;
	
	for (int counter = 0; counter < 10; counter++) {
		if (counter > 0) 
			cur_try += *decimal.getConstant(decimal_pos);
		
		adjusted_cur_try = cur_try - residue;

		/*if (decimal_pos == last_decimal)
			if (adjusted_cur_try < 0) continue;*/

		// if the adjusted current try is greater than the current
		// running sum, there's no way we can represent it, because
		// the superincreasing property limits our representation.

		if (adjusted_cur_try > binary_running_sum[decimal_pos]) 
			continue;
		
		// It's a contradiction if our modulus calculation shows
		// the least bit doesn't correspond to what the superincreasing
		// property says about the number's highest addend.
		
		// Find out if the latter bit says we should be larger or
		// smaller than the binary constant.
		//
		// Then find out if we're at a phase transition
		// (adjusted_cur_try < binary constant, but adjusted_cur_try +
		//  next decimal constant > binary_constant)
		//
		//  If not, do a simple calculation of contradiction as before
		//  and bail if we have a contradiction
		//
		//  If we're at a phase transition, shift adjusted_cur_try
		//  left until we're above it, incrementing "barrier"
		//  each time (closest approximation to where it becomes high; 
		//  2, 4, 8), and
		//  	if should_have_binary_on is on, set the start
		//  	to this digit. otherwise, set the end to this digit.
		//  (assuming end isn't covered)
		
		if (decimal_pos != last_decimal) 
			adjusted_cur_try += decimal_running_sum[decimal_pos+1];
		
		// if it's less than zero, that means that there's no
		// possible way we can get a number out of this (similar to
		// the binary superincreasing property).
		//
		// This relies on the addition above.
		if (adjusted_cur_try < 0) continue;
		
		should_have_binary_on = logbitp(decimal_pos, adjusted_cur_try);
		
		// there used to be a clause here saying "if less_than_binary
		// then (...)" to cut down on time. However, it has been
		// removed because the optimization (if it's false then it
		// must always be so for higher numbers) doesn't hold true.
		// (Dunno when; maybe for negatives. I "can't be arsed" to find
		// out.)
		
		less_than_binary = ( adjusted_cur_try < 
				*binary.getConstant(decimal_pos) );
		
		contradiction = (should_have_binary_on == less_than_binary);

		// We're not using adjusted_cur_try anymore, so we don't need
		// to subtract.
		
		// If the bit is forced on, and it must be off, then we 
		// have a contradiction.
		if (force_on && less_than_binary) contradiction = true;
		
		if (!contradiction) {
			
			ctr++;

			if (decimal_pos == last_decimal) {
				actr++;
				if (greedy_binary(binary.getDigits(),
							adjusted_cur_try,
							decimal_pos)) {
					cout << "\n##############################################################################\n";
					cout << "Palindrome: " << cur_try << endl;
					cout << "##############################################################################\n";
				}
				continue;
			}

			if (should_have_binary_on) {
				out_residue = residue + *binary.getConstant(
						decimal_pos);
				
				check_try(binary, decimal, out_residue,
						decimal_pos+1, cur_try,
						last_decimal, false,
						binary_running_sum,
						decimal_running_sum, ctr, actr);
			}

			else
				
				check_try(binary, decimal, residue, 
						decimal_pos+1, cur_try, 
						last_decimal, false, 
						binary_running_sum, 
						decimal_running_sum, ctr, actr);
		}
	}
}

// This is 16 bits slower than the pure integer solution. (This means that
// solving 30 bits here takes as much time as solving 46 bits on the integer
// solution)

void renamed_main_function(int bits, bool use_upper, bool & can_use_upper) {

	//const int bits = 91;

	int upper_digits, lower_digits, cur_digits;
	double conversion_factor = log(2.0)/log(10.0);

	upper_digits = floor(bits*conversion_factor)+1;
	lower_digits = floor((bits-1)*conversion_factor)+1;

	can_use_upper = (lower_digits != upper_digits);

	if (use_upper)	cur_digits = upper_digits;
	else		cur_digits = lower_digits;

	Palindromic binary(2, bits);
	Palindromic decimal(10, cur_digits);

	int counter;
	unsigned long long ctr = 0, actr = 0;

	// we need a running sum to remove that which we can never reach.
	// It may be possible to make the search phase more efficient by
	// detecting "phase transitions" and locking 
	cl_I binary_sum[binary.getNumVars()], 
		decimal_sum[decimal.getNumVars()];

	cl_I binrunsum = 0, decrunsum = 0;

	for (counter = binary.getNumVars()-1; counter >= 0; counter--) {
		binrunsum += *binary.getConstant(counter);
		binary_sum[counter] = binrunsum;
	}

	for (counter = decimal.getNumVars()-1; counter >= 0; counter--) {
		decrunsum += (*decimal.getConstant(counter) * 9);
		decimal_sum[counter] = decrunsum;
	//	cout << decrunsum << endl;
	}

	/*for (counter = 0; counter < binary.getNumVars(); counter++) {
		cout << binary_sum[counter] << endl;
	}*/

	//for (counter = 0; counter < 8192; counter++) {
	//

	check_try(binary, decimal, 0, 0, 0, decimal.getNumVars()-1, true, 
			binary_sum, decimal_sum, ctr, actr);
	//}

	cout << endl;
	cout << ctr << " candidate trawls." << endl;
	cout << actr << " candidate numbers. " << endl << endl;

	cout << (double)actr/(double)ctr * 100 << "% search phase ";
	cout << "efficiency.";
	cout << endl;

}

main(int argc, char ** argv) {

	bool use_upper = false;
	int startbits = 80;

	if (argc > 1) {
		startbits = (int) atoi (argv[1]);
	} else {
		printf("dwpalin <number of binary digits to start on>\n");
		exit(1);
	}

	for (int counter = startbits; counter < 120; counter++) {

		cout << "-------------------------------" << endl;
		cout << counter << " bits follows." << endl;

		renamed_main_function(counter, false, use_upper);
		if (use_upper) {
			cout << "Use upper: " << endl;
			renamed_main_function(counter, true, use_upper);
			use_upper = false;
		}
// comment out the next few lines if you want it to continue to the next
// bitlength instead of exit:
//		cout << endl;
		cout <<"Done searching the "<<counter<<"-bit space."<<endl;
		exit(0);
	}
}