/*
 * Copyright (C) 2015 Imran Mammadli
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package hash.math.collatz;

import java.util.HashSet;

public class Solution1 
{
	/**
	 * Tests the Collatz Conjecture for all numbers up to the specified number
	 * 
	 * @param number the upper limit
	 * @return true, if conjecture holds for all the numbers up to the given one, otherwise false
	 * @throws ArithmeticException if the checked number is too big to be represented
	 * 
	 * @see <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz Conjecture</a>
	 * 
	 * @time <i>Ω(n)</i>
	 * @space <i>Ω(n)</i>
	 **/
	public static boolean checkCollatz(long number)
	{
		// all the odd numbers that were verified to converge
		HashSet<Long> checked_numbers = new HashSet<Long>();
		
		for (long i = 2; i <= number; i++)
		{
			// numbers encountered so far for the given value of i
			HashSet<Long> sequence = new HashSet<Long>();
			
			long current = i;
			
			// all numbers up to i already tested
			while (current >= i)
			{
				// the sequence falls into a loop, which is not 4-2-1
				if (sequence.contains(current))
				{
					return false; // never happens :)
				}
				
				sequence.add(current);
				
				 // current number is odd
				if ((current % 2) == 1)
				{
					// the number was already encountered
					if (checked_numbers.contains(current))
					{
						break;
					}
					
					long next = current * 3 + 1;
					
					// the next number is going to bee too big
					if (next <= current)
					{
						throw new ArithmeticException("The number is too big");
					}
					
					checked_numbers.add(current);
					current = next;
				}
				//current number is even
				else
				{
					current /= 2;
				}
			}
		}
		
		return true;
	}
}