/** @file utils.h
 *
 *	Declaration of useful functions and classes widely used through the program.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _UTILS_H
#define _UTILS_H

#include <bitset>
#include <map>
#include <string>
#include <utility>
#include <vector>

// bits_in_char value
#include "config.h"

namespace ace {

/** Template for functor class for function returning 1st pair member.
 *	T stands for pair type.
 */
template<class T>
struct select1st: public std::unary_function<T, typename T::first_type> {
	typename T::first_type operator()(const T& pair_arg) const {
		return pair_arg.first;
	}
};

/** Template for functor class for function returning 2nd pair member.
 *	T stands for pair type.
 */
template<class T>
struct select2nd: public std::unary_function<T, typename T::second_type> {
	typename T::second_type operator()(const T& pair_arg) const {
		return pair_arg.second;
	}
};

/**	@param expr Expression.
 *	@param i Index.
 *	@return True, if ith-bit of given expression is 1, false otherwise.
 */
template<typename _Type>
inline bool ith_bit(_Type expr, size_t i) {
	return (expr >> i) & 1;
}

/**	@param expr Expression.
 *	@param i Index.
 *	@param on Set to 1 (true) or to 0 (false)?
 *	@return Expression 
 */
template<typename _Type>
inline _Type set_ith_bit(_Type expr, size_t i, bool on = true) {
	return expr | (static_cast<_Type>(on) << i);
}

/**	@param expr Expression.
 *	@return Number of nonzero bits in given expression.
 */
template<typename _Type>
size_t bits_in(_Type expr) {
	size_t counter = 0;
	for ( size_t i = 0; i < sizeof(_Type)*constants::bits_per_char; ++i ) {
		counter += ith_bit<_Type>(expr, i);
	}
	return counter;
}

/** @return Expression with all bits set to 1.
 */
template<typename _Type>
inline _Type ff(void) {
	return ~ static_cast<_Type>(0);
}


/** Converts given unsigned number to string.
 *	@param num Number to become the string.
 *	@return String representation of given number.
 */
std::string unsigned2str(size_t num);

/** Converts given floating point number to string.
 *	@param num Number to become the string.
 *	@param precision Output number precision.
 *	@return String representation of given number.
 */
std::string double2str(double num, unsigned precision = 0);

#ifdef _DEPENDENCY_MODE

/** The container with tables (vectors of unsigned) which are
 *	decompositions of certain number (N) into certain number of addends (M).
 */
typedef std::vector<std::vector<size_t> > sum_decompositions_t;

/** Class purpose is to hold information about all decompositions of given sum (N)
 *	into given number of addends (M).
 *	Class stores decompositions not only for given numbers, but up to them.
 *	So for constructor parameters N = 4, M = 7 it's possible to ask for all
 *	decompositions of sum 4 into 7 addends (and one of them is: 0+0+2+0+1+1+0).
 *	Moreover it's possible to ask for all decompositions of params higher than
 *	those passed to constructor (e.g. decompositions of sum 5 into 10 addends),
 *	but this calls have slower performance, because results for them are counted
 *	at first-ask-time, not during object initialization.
 */
class SumDecompositions {
	/**
	 */
	typedef std::map<size_t, sum_decompositions_t*> overflow_sum_decompositions_mapping_t;
	/** Variables to store sum (N) and number of addends (M).
	 */
	size_t _n, _m;
	/** Pointer to the beginning of array of pointers to the decompositions tables.
	 */
	sum_decompositions_t **_tables;
	/** Map to hold the overflowed tables - tables that has one of their params bigger
	 *	than corresponding param in class constructor.
	 */
	overflow_sum_decompositions_mapping_t _overflow;

	/** Initialization procedure.
	 */
	void _init(void);

	// No copy constructs.
	SumDecompositions(const SumDecompositions& sum_decompositions);
	// No assignments.
	SumDecompositions& operator=(const SumDecompositions& sum_decompositions);
public:
	
	/** Initializes decompositions tables up to maximum `sum` and maximum number of `addends`.
	 */
	SumDecompositions(size_t sum, size_t addends): _n(sum), _m(addends), _tables(NULL), _overflow() {
		_tables = new sum_decompositions_t*[_n*_m];
		_init();
	}
	/** Deletes all dynamically allocated memory.
	 */
	~SumDecompositions(void);
	/** @return Pointer to decompositions table corresponding to given params.
	 *	@param sum Determines the sum.
	 *	@param addends Determines the number of addends.
	 */
	const sum_decompositions_t * get_decompositions_table(size_t sum, size_t addends);
};

#else
/**
 */
typedef std::vector<std::vector<bool> > bools_table_t;
/**
 */
bools_table_t bools_table(size_t ones, size_t length);
#endif

} // namespace ace

#endif
