/*
Online Java - IDE, Code Editor, Compiler

Online Java is a quick and easy tool that helps you to build, compile, test your programs online.
*/

import java.util.*;

//Note the anagram code is inserted into for loop in which it checks if ALREADY PROCESSED.
//As reminder, this was implemented in my previous challenges due to multiple method calls from the calculator class. 
//This in turn caused Set to populate in random manner (native to Java).
//In this challenge there is only one method call to FindAnagram()
//If this exercise was to be extended in which we performed P(p.length(),r)
//where r=1, p.length(), the code structure is suitable.
//We would require an additional for loop to support this.
//We would also then need to move some variables to class level (static) such as Set for storage, index counters for its size......

//With respect to my previous coding examples using Statistic calculators, I have passed the permutation or combination number
//argument to parameter in constructor of the main application.
//I want to attempt this challenge without modifying the signature if possible
//This will be only way it will meet exact requirements
//I am also performing this action since I feel that there are basic requirements with
//Permutations Calculator nPr for this challenge.
//We are only utilising P(p.length(), p.length()
//Hence the focus will remain on the anagram loops.

//Also this time, we do not need to go through the pos for loop. Since in the previous example, we were going through 
//each Character in String p and eliminating it from the StringBuilder if it did appear in String S (within same block size).
//The fact that we have created this permutation means that requirement is to find anagram exactly as it appears in String s.

public class Main 
{
    static long permutations;
    
    public static void main(String[] args) 
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        
        //TEST CASE 1: findAnagrams("cbaebabacd","abc");
        //String p="abc";
        //String s="cbaebabacd";
        
        //TEST CASE 2:  findAnagrams("abab","ab");
        //String p = "ab";
        //String s = "abab";
        
        //TEST CASE 3: findAnagrams("azazazazazazzzzaaazazazaz", "az")
        //String p = "az";
        //String s = "azazazazazazzzzaaazazazaz";
        
        //TEST CASE 4: findAnagrams("azazazazazazzzzaaazazazpp", "az");
        //String p = "az";
        //String s = "azazazazazazzzzaaazazazpp";
        
        //TEST CASE 5: findAnagrams("abcbcacab", "abc");
        String p = "abc";
        String s = "abcbcacab";
        
        //These would have been in calculator class in previous examples
        int originalNumber=p.length();
        int n=originalNumber;
        int r = p.length();
        Map <Integer, Long> m = new HashMap<>();
        
        Permutation perm = new Permutation();
        n=originalNumber;
        
        //This is part of the method signature
        //(int n, int r, int originalNumber, Map factorialResults)
        perm.Permutations (n,r,originalNumber, m);
        
        permutations = perm.getPermutations();
       
        //Method call
        findAnagrams(s,p);
    }
    public static void findAnagrams(String s, String p)
    {
        //I decided to use collection to hold the generated random numbers
        //it is most efficient way to ascertain that same character index is not used
        //for String p (i.e simulating permutation without replacement)
        Set <Integer> stRandomNums = new HashSet<>();
        
        int pos=0;
        int subsetNumber=1;
        Set <String> st = new HashSet<>();
        StringBuilder sb = new StringBuilder(p);
        int startPos=0;
        boolean hasCharFound=false;
        int counter=0;
        StringJoiner sj;
        int temp1;
        Random rand = new Random();
        String[] valuesSet; 
        String []backupValuesSetBeforeModification;
        int num;
        int count=0;
        int subsetEntry=1;
        int cycles=0;
        int totalcycles=0;
        int difference = 0;
        List <String> backupValuesSet = new ArrayList<>();
        int currentSetSize;
        int newSetSize;
        int n;
        
        //*** I decided at end it was too excessive using a list to hold the characters
        //in String p in a Set. It would not add any efficiencies to code whatsoever
    
        //I did try to experiment with creating a character array and trying to add it into List
        //but Java did not like the syntax 
        //List <Character> lst = new ArrayList<Character>(Arrays.asList(p.toCharArray()));
    
        //NO ISSUES TRYING IN THIS CONVENTION
        //List <String> lst = new ArrayList<String>(Arrays.asList("test"));
    
        //List <Character> lst = new ArrayList<Character>();
    
        //So I have adopted more convention approach.
        //My instinct tells me using streams or possibly lamba would do this much more efficiently.
        //The knowledge is still above my capacity so I will attempt as such
        //for (char c: p.toCharArray())
        //{
        
        //   lst.add(c);
        //}
        
        System.out.println("String (s) to search in: " + s);
        System.out.println("String (p) template word: " + p);
        
        if (s.length()<p.length())
        {
            System.out.println("template word is longer length than main String");
            System.exit(0);
        }
        
        //at this point, it can call the permutation constructor
        //it can perform P(3,3) for instance
        //this will determine how many times to perform operation.
        //in terms of populating the hashSet with permutations.
        //it can perhaps obtain this and return this String (this will be permutation of p)
        //it would then assign the permutation to the StringBuilder
        
        //---------------------------------------------
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
        
        do
        {
            sj=new StringJoiner("");
            
            //to ensure each permutation is correct length
            for (int m=0;m<p.length();m++)
            {
                //nextInt(3) will generate numbers 0,1,2
                temp1 = rand.nextInt(p.length());
                currentSetSize=stRandomNums.size();
                stRandomNums.add(temp1);
                
                //the first generated random number is fully permissible
                if (m==0)
                {
                    //System.out.println("HERE");
                    //System.out.println(currentSetSize);
                    //System.out.println(stRandomNums.size());
                    System.out.println("random num: " + temp1);
                    sj.add(Character.toString(p.charAt(temp1)));
                }
                else
                {
                    //if the random number has been presented before
                    if (stRandomNums.size()==currentSetSize)
                    {
                        //System.out.println("HER1");
                        //it will set iteration back since the set has not grown, hence repeat random number
                        m=m-1;
                    }
                    else
                    {
                        System.out.println("random num: " + temp1);
                        sj.add(Character.toString(p.charAt(temp1)));
                    }
                }
            }
            //essential that set is cleared otherwise
            //it will attempt to add entry upon generating random number (when it performs identication of a new permutation) 
            //and never will be successful since all entries already exist.
            //hence it will loop indefinitely the do while loop
            //and not be able to derive another permutation
            stRandomNums.clear();
            
            System.out.println("\n");
            currentSetSize=st.size();
            
            //it will attempt to add the permutation into the Set
            st.add(sj.toString());
            sj=new StringJoiner("");
            newSetSize = st.size();
            cycles++;
            totalcycles++;
           //System.out.println("end\n");
           
        //this is post check, hence it will ensure newSetSize reaches
        //desired amount before exiting
        }while (newSetSize<permutations);

        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
        
        System.out.println("******************Contents of the backup set");
        System.out.println("******************Contents of the valuesSet");
        
        for (String g: valuesSet)
        {
            System.out.println("Subset " + subsetNumber+": " + g);
            subsetNumber++;
        }
        subsetNumber=1;

        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("**ENDING AT INDEX:***** " + st.size() +"\n");
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification)); 
        
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")
            {
                System.out.println("\n\n"+valuesSet[entry] + "\t\tSubset: " + subsetEntry  + "  at cycle number: " + totalcycles);
                
                subsetEntry++;
            
                //MAIN LOGIC OF THE NEW CODE OFFICIALLY STARTS HERE.
                //I HAVE PRESENTED THE ENTIRE CODE HERE
                //Note, I am using the permutation in the array from herein
                sb=new StringBuilder(valuesSet[entry]);
                
                //For some reason, the do while loop served its purpose iny my previous
                //code in which I did not explore permutation. But it failed here and it did 
                //overrun. Hence presenting while loop
                
                while(p.length()+startPos<s.length())
                {
                    do
                    {
                        //to ensure moving across String s
                        //counter is increased at bottom of code
                        //just before the outer while loop
                        startPos=counter;
            
                        for (int i=startPos; i<s.length();i++)
                        {
			    
                            if(!sb.toString().isEmpty())
                            {
                                System.out.println("This is STARTPOS: " + startPos);
                                System.out.println("This is sb length: " + sb.length());
                                System.out.println("This is s length: " +  s.length());
                            }
                            
                            //pos takes different role compared to last challenge
                            //we no longer use pos to check all indexes in sb (String p)
                            //within a nested for loop
                            //if this action is not performed there will be StringIndexOutOfBoundsException
                            
                            if (hasCharFound)
                            {
                                pos=0;
                            }
                        
                            if (!sb.toString().isEmpty())
                            {
                                System.out.println("value of pos: " + pos);
                                System.out.println("value of sb: " + sb.toString());
                                
                                //This is much tidier now given less complexity in checking the derived permutation
                                System.out.println("Checking character: " + sb.toString().charAt(pos) + 
                                "  against the main String index: " + i + "("+s.charAt(i)+")");
				
				System.out.println("SUBSTRING EXAMINED: " + s.substring(startPos,(startPos+p.length())));
                            
                                //now the focus is on checking to see if the character of String p appears in that order 
                                //in block size in String s.  Once again, it is tidier
                                if (Character.toString(s.charAt(i)).indexOf(sb.toString().charAt(pos))==0)
                                {
                                    System.out.println("char found: " + sb.toString().charAt(pos) + 
                                    "    at index: " + i);
                               
                                    System.out.println(sb.toString().charAt(pos) + " has been removed from StringBuilder (String p)" +  "= "+ sb.toString());
                                    sb.deleteCharAt(pos);
                                    System.out.println("This is current StringBuilder (String p): " + sb.toString());
                                    hasCharFound=true;
                                }
                                else
                                {
                                    System.out.println("NO MATCH FOUND");
                                    System.out.println("StringBuilder being emptied: " + sb.toString());
                                    sb.delete(0,sb.length());
                                    hasCharFound=false;
                                    break;
                                }
                            }
                            pos++;
                         
                            //this will prevent exceptions since pos is used
                            //as index for StringBuilder
                            if (pos==p.length())
                            {
                                pos=0;
                                break;
                            }
                        }
                    }while(!sb.toString().isEmpty());
        
                    if (sb.toString().isEmpty() && hasCharFound)
                    {
                        //once again valuesSet[entry] is used since we are no longer concerned with String p
                        //String p was the starting point to generate all the permutations
                        System.out.println("**********************************************************");
                        System.out.println(s.substring(startPos,(startPos+p.length())) + " is an anagram of: " + valuesSet[entry] 
                        + "\t\t\tIndex("+counter+")");
                        System.out.println("**********************************************************");
                    }
		            if (sb.toString().isEmpty() && !hasCharFound)
                    {
                        System.out.println("**********************************************************");
                        System.out.println(s.substring(startPos,(startPos+p.length())) + " is NOT an anagram of: " + valuesSet[entry] 
                        + "\t\t\tIndex("+counter+")");
                        System.out.println("**********************************************************");
                    }
                    System.out.println("*****RESTORING BACKUP OF STRINGBUILDER (String p): " + valuesSet[entry]);
                    pos=0;
            
                    //in previous code, we restored using variable p
                    //now the focus is on the permutation generated
                    sb=new StringBuilder(valuesSet[entry]);
                    hasCharFound=false;
                    counter++;
                } //end of while loop  while(p.length()+startPos<s.length())
        
//but we will find that counter is still one greater than startPos in which the while loop terminated
// so effectively, startPos will once again become 7.
//and for a main String s where the length is 9 characters, this will invalidate the situation and generate a
//StringIndexOutOfBoundsException

//*** FOR INSTANCE, EXECUTING check with string p
//we know the last starting index would be (c) at index 6
//String p = "abc";                     (3 characters)
//String s = "abcbca(c)ab";             (9 characters)


//effectively I have set the counter =0  once it exits the while loop.
//we know at this point it is in the for loop where it is processing the permutations.
//I believe all the conditions are now set for a fresh execution....

                counter=0;
                startPos=0;
            }
        }
        difference = newSetSize;
    }  //end of constructor...
}
    
class Permutation
{
    //these variables had to be moved out of the methods
    //and into class level variables
    static long result=0;
    static int n;
    static int r;
    static int originalNumber;

    public long getPermutations()
    {
	//also due to multiple calls to methods in this class, I had to split these screen outputs to avoid screen repetitions
	//as offset, since the n variable has been modified during execution in method below, it has impacted this method.
	//so I have used originalNumber in screen outputs..

        System.out.println("***PERMUTATIONS*** nPr (without replacement)");
        System.out.println("P(n,r) = n! / (n−r)!");
        System.out.println("P(" + originalNumber+","+r+") = " + originalNumber+"!" + " / " + "("+originalNumber+"-"+r+")!");
        System.out.println(result);
        
        return result;
    }
     
    public static long Permutations (int n, int r, int originalNumber, Map factorialResults)
    {
        //instance not required since the static method is not class specific
        Permutation.n=n;
        Permutation.r=r;
	    Permutation.originalNumber=originalNumber;
       
        // n are objects
        // r is sample
        /*
        ***CALCULATION***
        P(n,r) = n! / (n−r)!
        */
        
        int temp;
        int denominator;
        
        if (originalNumber<r || r<0)
        {
            System.out.println("please enter n ≥ r ≥ 0");
            System.exit(0);
            
            return 0;
        }
        if (n>=1)
        {
            // EXAMPLE
            // P (5,6) = 5* 4 * 3 * 2 * 1 / (6-5)! = 24 / 2! = 24 / 2 * 1 = 24/2 = 12
            result = (n* (Permutations (n-1, r,originalNumber, factorialResults))); // this completes factorial for numerator
            factorialResults.put(n,result);
            
            if (n==originalNumber)
            {
                denominator = originalNumber-r;
                if (factorialResults.containsKey(denominator))
                {
                    factorialResults.get(denominator);
                    return result / (long)factorialResults.get(denominator);
                }
            }
            return result;
        }
        return 1;
    }
}