001/*
002 *                    BioJava development code
003 *
004 * This code may be freely distributed and modified under the
005 * terms of the GNU Lesser General Public Licence.  This should
006 * be distributed with the code.  If you do not have a copy,
007 * see:
008 *
009 *      http://www.gnu.org/copyleft/lesser.html
010 *
011 * Copyright for this code is held jointly by the individual
012 * authors.  These should be listed in @author doc comments.
013 *
014 * For more information on the BioJava project and its aims,
015 * or to join the biojava-l mailing list, visit the home page
016 * at:
017 *
018 *      http://www.biojava.org/
019 *
020 */
021
022package org.biojava.nbio.structure.symmetry.core;
023
024import java.util.ArrayList;
025import java.util.HashSet;
026import java.util.Iterator;
027import java.util.List;
028import java.util.Set;
029
030/**
031 *
032 * @author Peter
033 */
034public class PermutationGroup implements Iterable<List<Integer>> {
035        List<List<Integer>> permutations = new ArrayList<List<Integer>>();
036
037        public void addPermutation(List<Integer> permutation) {
038                if (!permutations.contains(permutation)) {
039                        permutations.add(permutation);
040                }
041        }
042
043        public List<Integer> getPermutation(int index) {
044                return permutations.get(index);
045        }
046
047        public int getOrder() {
048                return permutations.size();
049        }
050
051
052        /**
053         * Starts with an incomplete set of group generators in `permutations` and
054         * expands it to include all possible combinations.
055         *
056         * Ways to complete group:
057         * - combinations of permutations pi x pj
058         * - combinations with itself p^k
059         *
060         */
061        public void completeGroup() {
062                // Copy initial set to allow permutations to grow
063                List<List<Integer>> gens = new ArrayList<List<Integer>>(permutations);
064                // Keep HashSet version of permutations for fast lookup.
065                Set<List<Integer>> known = new HashSet<List<Integer>>(permutations);
066                //breadth-first search through the map of all members
067                List<List<Integer>> currentLevel = new ArrayList<List<Integer>>(permutations);
068                while( currentLevel.size() > 0) {
069                        List<List<Integer>> nextLevel = new ArrayList<List<Integer>>();
070                        for( List<Integer> p : currentLevel) {
071                                for(List<Integer> gen : gens) {
072                                        List<Integer> y = combine(p,gen);
073                                        if(!known.contains(y)) {
074                                                nextLevel.add(y);
075                                                //bypass addPermutation(y) for performance
076                                                permutations.add(y);
077                                                known.add(y);
078                                        }
079                                }
080                        }
081                        currentLevel = nextLevel;
082                }
083        }
084
085        @Override
086        public String toString() {
087                StringBuilder sb = new StringBuilder();
088                sb.append("Permutation Group: " + permutations.size() + " permutation");
089                for (List<Integer> permutation : permutations) {
090                        sb.append(permutation.toString());
091                }
092                return sb.toString();
093        }
094
095        public static List<Integer> combine(List<Integer> permutation1, List<Integer> permutation2) {
096                List<Integer> intermediate = new ArrayList<Integer>(permutation1.size());
097                for (int i = 0, n = permutation1.size(); i < n; i++) {
098                        intermediate.add(permutation2.get(permutation1.get(i)));
099                }
100                return intermediate;
101        }
102
103        public static int getOrder(List<Integer> permutation) {
104                List<Integer> copy = new ArrayList<Integer>(permutation);
105                for (int i = 0, n = permutation.size(); i < n; i++) {
106                        copy = combine(copy, permutation);
107                        if (copy.equals(permutation)) {
108                                return i + 1;
109                        }
110                }
111                return 0;
112        }
113
114        public String getGroupTable() {
115                StringBuilder builder = new StringBuilder();
116                builder.append("  |");
117                for (int i = 0; i < getOrder(); i++) {
118                        builder.append(" ");
119                        builder.append(i);
120                }
121                builder.append("\n");
122                builder.append("---");
123                for (int i = 0; i < getOrder(); i++) {
124                        builder.append("--");
125                }
126                builder.append("\n");
127                for (int i = 0; i < getOrder(); i++) {
128                        builder.append(i);
129                        builder.append(" |");
130                        for (int j = 0; j < getOrder(); j++) {
131                                builder.append(" ");
132                                builder.append(permutations.indexOf(combine(permutations.get(i), permutations.get(j))));
133                        }
134                        builder.append("\n");
135                }
136                return builder.toString();
137        }
138
139        @Override
140        public int hashCode() {
141            return getGroupTable().hashCode();
142        }
143
144        @Override
145        public Iterator<List<Integer>> iterator() {
146                return permutations.iterator();
147        }
148
149        @Override
150        public boolean equals(Object obj) {
151            if (this == obj) {
152                return true;
153            }
154            if (obj == null) {
155                return false;
156            }
157            if (this.getClass() == obj.getClass()) {
158                return permutations.equals(((PermutationGroup)obj).permutations);
159            }
160            return false;
161        }
162
163}