Unit tests for the Permutor class and fix to permutor.

Signed-off-by: Egon Willighagen <egonw@users.sourceforge.net>
cdk · Sep 18, 2011 · 88ceb38 · 88ceb38
1 parent 217977c
commit 88ceb38
Show file tree

Hide file tree

Showing 2 changed files with 157 additions and 4 deletions.
diff --git a/src/main/org/openscience/cdk/graph/Permutor.java b/src/main/org/openscience/cdk/graph/Permutor.java
@@ -24,6 +24,9 @@
 
 import java.util.Random;
 
+import org.openscience.cdk.annotations.TestClass;
+import org.openscience.cdk.annotations.TestMethod;
+
 /**
  * General permutation generator, that uses orderly generation by ranking and
  * unranking. The basic idea is that all permutations of length N can be ordered
@@ -49,6 +52,7 @@
  * @cdk.module     standard
  * 
  */
+@TestClass("PermutorTest")
 public class Permutor {
 
     /**
@@ -77,13 +81,15 @@ public class Permutor {
      * 
      * @param size the size of the permutations to generate
      */
+    @TestMethod("constructorTest")
     public Permutor(int size) {
         this.currentRank = 0;
         this.size = size;
         this.maxRank = this.calculateMaxRank();
         this.random = new Random();
     }
 
+    @TestMethod("hasNextTest")
     public boolean hasNext() {
         return this.currentRank < this.maxRank;
     }
@@ -93,6 +99,7 @@ public boolean hasNext() {
      * 
      * @param rank the order of the permutation in the list
      */
+    @TestMethod("setRankTest")
     public void setRank(int rank) {
         this.currentRank = rank;
     }
@@ -102,10 +109,21 @@ public void setRank(int rank) {
      * 
      * @param permutation the permutation to use, as an int array
      */
+    @TestMethod("setPermutationTest")
     public void setPermutation(int[] permutation) {
         this.currentRank = this.rankPermutationLexicographically(permutation);
     }
 
+    /**
+     * Get the current rank.
+     * 
+     * @return the current rank
+     */
+    @TestMethod("getRankTest")
+    public int getRank() {
+        return currentRank;
+    }
+
     /**
      * Randomly skip ahead in the list of permutations.
      *  
@@ -123,6 +141,7 @@ public int[] getRandomNextPermutation() {
      * 
      * @return the next permutation
      */
+    @TestMethod("countGeneratedPermutations")
     public int[] getNextPermutation() {
         this.currentRank++;
         return this.getCurrentPermutation();
@@ -133,6 +152,7 @@ public int[] getNextPermutation() {
      * 
      * @return the permutation as an int array
      */
+    @TestMethod("getCurrentPermutationTest")
     public int[] getCurrentPermutation() {
         return this.unrankPermutationLexicographically(currentRank, size);
     }
@@ -142,6 +162,7 @@ public int[] getCurrentPermutation() {
      *  
      * @return the maximum number of permutations
      */
+    @TestMethod("maxRankTest")
     public int calculateMaxRank() {
         return factorial(size) - 1;
     }
@@ -168,16 +189,18 @@ private int rankPermutationLexicographically(int[] permutation) {
         int rank = 0;
         int n = permutation.length;
         int[] counter = new int[n + 1];
-        System.arraycopy(permutation, 0, counter, 1, n);
+        for (int i = 1; i < permutation.length; i++) {
+            counter[i] = permutation[i - 1] + 1;
+        }
         for (int j = 1; j <= n; j++) {
-            rank = rank + ((counter[j] - 1) * factorial(n - j));
-            for (int i = j + 1; i < n; i++) {
+            rank += (counter[j] - 1) * factorial(n - j);
+            for (int i = j + 1; i <= n; i++) {
                 if (counter[i] > counter[j]) {
                     counter[i]--;
                 }
             }
         }
-        return rank;
+        return rank + 1;
     }
 
     /**

diff --git a/src/test/org/openscience/cdk/graph/PermutorTest.java b/src/test/org/openscience/cdk/graph/PermutorTest.java
@@ -0,0 +1,130 @@
+package org.openscience.cdk.graph;
+
+import java.util.BitSet;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * @author maclean
+ * @cdk.module test-standard
+ */
+public class PermutorTest {
+
+    private int factorial(int n) {
+        if (n <= 1) {
+            return 1;
+        } else {
+            return n * factorial(n - 1);
+        }
+    }
+
+    private int[] getIdentity(int size) {
+        int[] identity = new int[size];
+        for (int index = 0; index < size; index++) {
+            identity[index] = index;
+        }
+        return identity;
+    }
+
+    private boolean arrayElementsDistinct(int[] array) {
+        BitSet bitSet = new BitSet(array.length);
+        for (int index = 0; index < array.length; index++) {
+            if (bitSet.get(index)) {
+                return false;
+            } else {
+                bitSet.set(index);
+            }
+        }
+        return true;
+    }
+
+    @Test
+    public void constructorTest() {
+        int size = 4;
+        Permutor permutor = new Permutor(size);
+        int[] current = permutor.getCurrentPermutation();
+        Assert.assertArrayEquals(getIdentity(size), current);
+    }
+
+    @Test
+    public void hasNextTest() {
+        int size = 4;
+        Permutor permutor = new Permutor(size);
+        Assert.assertTrue(permutor.hasNext());
+    }
+
+    @Test
+    public void setRankTest() {
+        int size = 4;
+        int[] reverse = new int[] {3, 2, 1, 0};
+        Permutor permutor = new Permutor(size);
+        // out of 4! = 24 permutations, numbered 0-23, this is the last
+        permutor.setRank(23);
+        Assert.assertArrayEquals(reverse, permutor.getCurrentPermutation());
+    }
+
+    @Test
+    public void getRankTest() {
+        int size = 4;
+        int rank = 10;
+        Permutor permutor = new Permutor(size);
+        permutor.setRank(rank);
+        Assert.assertEquals(rank, permutor.getRank());
+    }
+
+    @Test
+    public void setPermutationTest() {
+        int size = 4;
+        int[] target = new int[] {3, 1, 0, 2};
+        Permutor permutor = new Permutor(size);
+        permutor.setPermutation(target);
+        Assert.assertArrayEquals(target, permutor.getCurrentPermutation());
+    }
+
+    @Test
+    public void countGeneratedPermutations() {
+        int size = 4;
+        Permutor permutor = new Permutor(size);
+        int count = 1;  // the identity permutation is not generated
+        while (permutor.hasNext()) {
+            permutor.getNextPermutation();
+            count++;
+        }
+        Assert.assertEquals(factorial(size), count);
+    }
+
+    @Test
+    public void getCurrentPermutationTest() {
+        int size = 4;
+        Permutor permutor = new Permutor(size);
+        boolean allOk = true;
+        while (permutor.hasNext()) {
+            permutor.getNextPermutation();
+            int[] current = permutor.getCurrentPermutation();
+            if (arrayElementsDistinct(current)) {
+                continue;
+            } else {
+                allOk = false;
+                break;
+            }
+        }
+        Assert.assertTrue(allOk);
+    }
+
+    @Test
+    public void maxRankTest() {
+        int size = 4;
+        Permutor permutor = new Permutor(size);
+        Assert.assertEquals(factorial(size) - 1, permutor.calculateMaxRank());
+    }
+
+    @Test
+    public void getRandomNextTest() {
+        int size = 4;
+        Permutor permutor = new Permutor(size);
+        int[] random = permutor.getRandomNextPermutation();
+        Assert.assertTrue(arrayElementsDistinct(random));
+    }
+
+}