/*
 * Copyright (c) 2021.
 *
 * Juergen Key. Alle Rechte vorbehalten.
 *
 * Weiterverbreitung und Verwendung in nichtkompilierter oder kompilierter Form,
 * mit oder ohne Veraenderung, sind unter den folgenden Bedingungen zulaessig:
 *
 *    1. Weiterverbreitete nichtkompilierte Exemplare muessen das obige Copyright,
 * die Liste der Bedingungen und den folgenden Haftungsausschluss im Quelltext
 * enthalten.
 *    2. Weiterverbreitete kompilierte Exemplare muessen das obige Copyright,
 * die Liste der Bedingungen und den folgenden Haftungsausschluss in der
 * Dokumentation und/oder anderen Materialien, die mit dem Exemplar verbreitet
 * werden, enthalten.
 *    3. Weder der Name des Autors noch die Namen der Beitragsleistenden
 * duerfen zum Kennzeichnen oder Bewerben von Produkten, die von dieser Software
 * abgeleitet wurden, ohne spezielle vorherige schriftliche Genehmigung verwendet
 * werden.
 *
 * DIESE SOFTWARE WIRD VOM AUTOR UND DEN BEITRAGSLEISTENDEN OHNE
 * JEGLICHE SPEZIELLE ODER IMPLIZIERTE GARANTIEN ZUR VERFUEGUNG GESTELLT, DIE
 * UNTER ANDEREM EINSCHLIESSEN: DIE IMPLIZIERTE GARANTIE DER VERWENDBARKEIT DER
 * SOFTWARE FUER EINEN BESTIMMTEN ZWECK. AUF KEINEN FALL IST DER AUTOR
 * ODER DIE BEITRAGSLEISTENDEN FUER IRGENDWELCHE DIREKTEN, INDIREKTEN,
 * ZUFAELLIGEN, SPEZIELLEN, BEISPIELHAFTEN ODER FOLGENDEN SCHAEDEN (UNTER ANDEREM
 * VERSCHAFFEN VON ERSATZGUETERN ODER -DIENSTLEISTUNGEN; EINSCHRAENKUNG DER
 * NUTZUNGSFAEHIGKEIT; VERLUST VON NUTZUNGSFAEHIGKEIT; DATEN; PROFIT ODER
 * GESCHAEFTSUNTERBRECHUNG), WIE AUCH IMMER VERURSACHT UND UNTER WELCHER
 * VERPFLICHTUNG AUCH IMMER, OB IN VERTRAG, STRIKTER VERPFLICHTUNG ODER
 * UNERLAUBTE HANDLUNG (INKLUSIVE FAHRLAESSIGKEIT) VERANTWORTLICH, AUF WELCHEM
 * WEG SIE AUCH IMMER DURCH DIE BENUTZUNG DIESER SOFTWARE ENTSTANDEN SIND, SOGAR,
 * WENN SIE AUF DIE MOEGLICHKEIT EINES SOLCHEN SCHADENS HINGEWIESEN WORDEN SIND.
 *
 */

package de.elbosso.scratch.algorithms.graph;

import java.io.FileNotFoundException;

/**
 * This class can be used to look for cycles in the graph obtained by iterating the (extended) collatz map.
 * The original collatz map is
 * <pre>
 *     C(n)=n/2 if n is even
 *     C(n)=3n+1 if n is odd
 * </pre>
 * The variant here takes on a parameter m so that
 * <pre>
 *     C(n)=n/2 if n is even
 *     C(n)=3n+2m+1 if n is odd
 * </pre>
 * Note that the computation uses Javas type long - this has to be kept in mind when determining the parameters...
 * If the algorithm seems to find cycles with negative numbers in it, the parameter was choosen so that there happened
 * an overflow!
 */
public class Collatz
{
	private final long m;
	private final long startingNumber;
	private final long endingNumber;
	private final long maxIterations;
	private final boolean findAll;

	/**
	 * Tries to find the number of cycles when computing the map for the Collatz conjecture
	 * @param m parameter for computing the map
	 * @param startingNumber the search for cycles in the graph is started at this number
	 * @param endingNumber the search for cycles in the map stops before this number. Be aware that this number is small enough
	 *                     so that at least 3n+2m+1 fits into Javas type long!
	 *                     If the algorithm seems to find cycles with negative numbers in it,
	 *                     the parameter was choosen so that there happened an overflow!
	 * @param maxIterations for each number betwenn startingNumber (inclusive) and
	 *                      endingNumber(exclusive) maximal this number of iterations of the map
	 *                      are computed looking for cycles
	 * @param findAll if false, the search is stopped after finding a second cycle
	 */
	public Collatz(long m, long startingNumber, long endingNumber, long maxIterations,boolean findAll)
	{
		this.m = m;
		this.startingNumber = startingNumber;
		this.endingNumber = endingNumber;
		this.maxIterations = maxIterations;
		this.findAll=findAll;
	}

	public static void main(java.lang.String[] args)throws FileNotFoundException
	{
		long startingNumber=4;
		long endingNumber=10000000l;
		long maxIterations=10000;
		boolean findAll=true;
		boolean digDeeper=false;
		long digDeeperFactorEndingNumber=10;
		long digDeeperFactorMaxIterations=10;
		for(long m=0;m<20;++m)
		{
			System.out.print("m= "+m+" Suspicion is: ["+((2*m+1))+", "+((2*m+1)*2)+", "+((2*m+1)*4)+"] - cyclecount: ");
			long cyclecount=new Collatz(m,startingNumber,endingNumber,maxIterations,findAll).run();
			System.out.println(cyclecount);
			if((digDeeper)&&((m>0)&&(cyclecount<2)))
			{
				System.out.println("Digging deeper at m= "+m);
				cyclecount = new Collatz(m, startingNumber,endingNumber*digDeeperFactorEndingNumber,maxIterations*digDeeperFactorMaxIterations,findAll).run();
			}
		}
	}
	public long run() throws FileNotFoundException
	{
		java.util.Set<java.lang.Long> alreadySeen=new java.util.HashSet();
		java.io.PrintWriter pw=new java.io.PrintWriter("/tmp/graph"+m+".gv");
		java.io.PrintWriter pw1=new java.io.PrintWriter("/tmp/lengths"+m+".dat");
		pw.println("digraph G {\nlayout=neato");
		long cyclecount=0;
		long maxIter=0;
		long i=startingNumber%2==0?startingNumber-1:startingNumber;
		if(i<0)
			i=1;
		for(;i<endingNumber;i+=2)
		{
			java.util.Set<java.lang.Long> alreadySeenThisRun=new java.util.HashSet();
			java.lang.Long currentValue=java.lang.Long.valueOf(i);
			if(alreadySeen.contains(currentValue)==false)
			{
				alreadySeen.add(currentValue);
				alreadySeenThisRun.add(currentValue);
				long j=0;
				for(;j<maxIterations;++j)
				{
					pw.print(currentValue);
					pw.print(" -> ");
					currentValue=collatz(currentValue);
					pw.println(currentValue);
					if(alreadySeen.contains(currentValue)==false)
					{
						alreadySeen.add(currentValue);
						alreadySeenThisRun.add(currentValue);
					}
					else
					{
						if(alreadySeenThisRun.contains(currentValue)==true)
						{
							System.out.println("new cycle found at " + currentValue+": "+alreadySeenThisRun);
							++cyclecount;
						}
						if(j>maxIter)
							maxIter=j;
						break;
					}
				}
				pw1.println(i+"\t"+j);
			}
			if((findAll==false)&&(cyclecount>1))
				break;
		}
		pw.println("}");
		pw1.close();
		pw.close();
		System.out.println("Maximum iterations needed to find a cycle: "+maxIter);
		return cyclecount;
	}

	private Long collatz(Long currentValue)
	{
		long n=currentValue.longValue();
		return java.lang.Long.valueOf(n%2==0?n/2:3*n+2*m+1);
	}
}