/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää and Jaakko Viertola
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.7 $
 *********************************************************************/

#include "Math.h"

namespace util
{
	double Math::factorial(unsigned int x)
	{
		double result = 1;
		for (unsigned int i=2; i<x; i++)
			result *= x;
		return result;
	}
	
	List<List<int> > Math::findCombinations(int numberOfClasses,int whichCombinations) throw (MathException&)
	{
		if(numberOfClasses < 1)
			throw MathException("Math<T>::findCombinations(int,int): NumberOfClasses is not reasonable");
		else if(whichCombinations < 1)
			throw MathException("Math<T>::findCombinations(int,int): whichCombinations is not reasonable");
		else if(numberOfClasses+1 <  whichCombinations)
			throw MathException("Math<T>::findCombinations(int,int): Number of combinations is bigger than given classes");
		
		// making new stack which functions "like for loops"
		List<int> lstStack(whichCombinations-1);
		for(int i=0;i<whichCombinations;i++)
			lstStack.addElement(0);
		lstStack.setLength(whichCombinations-1);

		int sp=0;
		int maxValue = numberOfClasses +1;
		int max = maxValue - whichCombinations;
  	int maxPointer = whichCombinations-1;

		List<List<int> > result;
		// if one's combination are needeed
		if(whichCombinations == 1)
			for(int i=0;i<maxValue;i++)
				{
					List<int> temp(1);
					temp.addElement(i);
					result.addElement(temp);
				}
		
		else
			{
				while(true)
					{
						if(lstStack[sp] < (max+sp+1) && sp < maxPointer)
							{	
								sp++;
								lstStack[sp] = lstStack[sp-1] + 1;
							}
						else if(lstStack[sp] == max && sp == 0 || lstStack[0] == max+1)break;
						else if(lstStack[sp] == (max+sp) && sp < maxPointer || lstStack[sp] == (max+sp+1))
							{
								sp--;
								lstStack[sp]++;
							}
						else
							{ 
								do
									{
										List<int> temp;
										for(int i=0;i< whichCombinations;i++)
											temp += lstStack[i];
										result += temp;
										lstStack[sp]++;
									}while(lstStack[sp] < maxValue);
								sp--;
								lstStack[sp]++;
							}//else
					}//while
			}//else
			return result;
	}

	List<List<int> > Math::findAllCombinations(int numberOfClasses) throw (MathException&)
	{
		if(numberOfClasses < 1)
			throw MathException("Math<T>::findAllCombinations(int,int): NumberOfClasses is not reasonable");
		
		List<List<int> > result;
		for(int i=1;i<= numberOfClasses+1;i++)result += findCombinations(numberOfClasses,i);

		return result;
	}
}