/*
 *                    BioJava development code
 *
 * This code may be freely distributed and modified under the
 * terms of the GNU Lesser General Public Licence.  This should
 * be distributed with the code.  If you do not have a copy,
 * see:
 *
 *      http://www.gnu.org/copyleft/lesser.html
 *
 * Copyright for this code is held jointly by the individual
 * authors.  These should be listed in @author doc comments.
 *
 * For more information on the BioJava project and its aims,
 * or to join the biojava-l mailing list, visit the home page
 * at:
 *
 *      http://www.biojava.org/
 *
 */

package org.biojava.nbio.structure.symmetry.core;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Peter
 */
public class PermutationGroup {
    List<List<Integer>> permutations = new ArrayList<List<Integer>>();

    public void addPermutation(List<Integer> permutation) {
        if (!permutations.contains(permutation)) {
            permutations.add(permutation);
        }
    }

    public List<Integer> getPermutation(int index) {
    	return permutations.get(index);
    }
    
    public int getOrder() {
    	return permutations.size();
    }
    
 
    /**
     * Ways to complete group: 
     * - combinations of permutations pi x pj
     * - combinations with itself p^k
     * 
     */
    public void completeGroup() {
    	int n = permutations.size();
        for (int i = 0; i < permutations.size(); i++) {
            for (int j = i; j < permutations.size(); j++) {
                List<Integer> p = combine(permutations.get(i), permutations.get(j));
                addPermutation(p);
//                System.out.println("complete group: adding " + p);
            }
        }
        // repeat iteratively until no new permutation are created
        if (permutations.size() > n) {
        	completeGroup();
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("Permutation Group: " + permutations.size() + " permutation");
        for (List<Integer> permutation : permutations) {
            sb.append(permutation.toString());
        }
        return sb.toString();
    }

    public static List<Integer> combine(List<Integer> permutation1, List<Integer> permutation2) {
        List<Integer> intermediate = new ArrayList<Integer>(permutation1.size());
        for (int i = 0, n = permutation1.size(); i < n; i++) {
            intermediate.add(permutation2.get(permutation1.get(i)));
        }
        return intermediate;
    }

    public static int getOrder(List<Integer> permutation) {
        List<Integer> copy = new ArrayList<Integer>(permutation);
        for (int i = 0, n = permutation.size(); i < n; i++) {
            copy = combine(copy, permutation);
            if (copy.equals(permutation)) {
                return i + 1;
            }
        }
        return 0;
    }
    
    public String getGroupTable() {
    	StringBuilder builder = new StringBuilder();
    	builder.append("  |");
    	for (int i = 0; i < getOrder(); i++) {
    		builder.append(" ");
    		builder.append(i);
    	}
    	builder.append("\n");
    	builder.append("---");
    	for (int i = 0; i < getOrder(); i++) {
    		builder.append("--");
    	}
    	builder.append("\n");
    	for (int i = 0; i < getOrder(); i++) {
    		builder.append(i);
    		builder.append(" |");
    		for (int j = 0; j < getOrder(); j++) {
    			builder.append(" ");
    			builder.append(permutations.indexOf(combine(permutations.get(i), permutations.get(j))));
    		}
    		builder.append("\n");
    	}
    	return builder.toString();
    }
    
    public int hashCode() {
    	return getGroupTable().hashCode();
    }
}

@@ -689,19 +689,67 @@
 va.util.
-Lis
+HashSet;%0Aimport java.util.List;%0Aimport java.util.Se
 t;%0A%0A/**%0A
@@ -1230,16 +1230,158 @@
     /**%0A
+     * Starts with an incomplete set of group generators in %60permutations%60 and%0A     * expands it to include all possible combinations.%0A     *%0A
      * W
@@ -1547,506 +1547,877 @@
    %09
-int n = permutations.size();%0A        for (int i = 0; i %3C permutations.size(); i++) %7B%0A            for (int j = i; j %3C permutations.size(); j++) %7B%0A                List%3CInteger%3E p = combine(permutations.get(i), permutations.get(j));%0A                addPermutation(p
+// Copy initial set to allow permutations to grow%0A    %09List%3CList%3CInteger%3E%3E gens = new ArrayList%3CList%3CInteger%3E%3E(permutations);%0A    %09// Keep HashSet version of permutations for fast lookup.%0A    %09Set%3CList%3CInteger%3E%3E known = new HashSet%3CList%3CInteger%3E%3E(permutations);%0A    %09//breadth-first search through the map of all members%0A    %09List%3CList%3CInteger%3E%3E currentLevel = new ArrayList%3CList%3CInteger%3E%3E(permutations);%0A    %09while( currentLevel.size() %3E 0) %7B%0A    %09%09List%3CList%3CInteger%3E%3E nextLevel = new ArrayList%3CList%3CInteger%3E%3E(
 );%0A
-//
     
-            System.out.println(%22complete group: adding %22 + p);%0A            %7D%0A        %7D%0A        // repeat iteratively until no new permutation are created%0A        if (permutations.size() %3E n) %7B%0A        %09completeGroup()
+%09%09for( List%3CInteger%3E p : currentLevel) %7B%0A    %09%09%09for(List%3CInteger%3E gen : gens) %7B%0A    %09%09%09%09List%3CInteger%3E y = combine(p,gen);%0A    %09%09%09%09if(!known.contains(y)) %7B%0A    %09%09%09%09%09nextLevel.add(y);%0A    %09%09%09%09%09//bypass addPermutation(y) for performance%0A    %09%09%09%09%09permutations.add(y);%0A    %09%09%09%09%09known.add(y);%0A    %09%09%09%09%7D%0A    %09%09%09%7D%0A    %09%09%7D%0A    %09%09currentLevel = nextLevel
 ;%0A    
-    
+%09
 %7D%0A  

Fix #321. Optimized completeGroup() for large groups.