EMMA Coverage Report (generated Sun Mar 01 22:06:14 CET 2015)
[all classes][org.h2.util]

COVERAGE SUMMARY FOR SOURCE FILE [Permutations.java]

nameclass, %method, %block, %line, %
Permutations.java100% (1/1)100% (7/7)99%  (226/229)98%  (49/50)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class Permutations100% (1/1)100% (7/7)99%  (226/229)98%  (49/50)
Permutations (Object [], Object [], int): void 100% (1/1)94%  (48/51)92%  (12/13)
create (Object [], Object []): Permutations 100% (1/1)100% (8/8)100% (1/1)
create (Object [], Object [], int): Permutations 100% (1/1)100% (7/7)100% (1/1)
moveIndex (): void 100% (1/1)100% (77/77)100% (15/15)
next (): boolean 100% (1/1)100% (28/28)100% (6/6)
reverseAfter (int): void 100% (1/1)100% (34/34)100% (10/10)
rightmostDip (): int 100% (1/1)100% (24/24)100% (4/4)

1/*
2 * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0,
3 * and the EPL 1.0 (http://h2database.com/html/license.html).
4 * Initial Developer: H2 Group
5 *
6 * According to a mail from Alan Tucker to Chris H Miller from IBM,
7 * the algorithm is in the public domain:
8 *
9 * Date: 2010-07-15 15:57
10 * Subject: Re: Applied Combinatorics Code
11 *
12 * Chris,
13 * The combinatorics algorithms in my textbook are all not under patent
14 * or copyright. They are as much in the public domain as the solution to any
15 * common question in an undergraduate mathematics course, e.g., in my
16 * combinatorics course, the solution to the problem of how many arrangements
17 * there are of the letters in the word MATHEMATICS. I appreciate your due
18 * diligence.
19 * -Alan
20 */
21package org.h2.util;
22 
23import org.h2.message.DbException;
24 
25/**
26 * A class to iterate over all permutations of an array.
27 * The algorithm is from Applied Combinatorics, by Alan Tucker as implemented in
28 * http://www.koders.com/java/fidD3445CD11B1DC687F6B8911075E7F01E23171553.aspx
29 *
30 * @param <T> the element type
31 */
32public class Permutations<T> {
33 
34    private final T[] in;
35    private final T[] out;
36    private final int n, m;
37    private final int[] index;
38    private boolean hasNext = true;
39 
40    private Permutations(T[] in, T[] out, int m) {
41        this.n = in.length;
42        this.m = m;
43        if (n < m || m < 0) {
44            DbException.throwInternalError("n < m or m < 0");
45        }
46        this.in = in;
47        this.out = out;
48        index = new int[n];
49        for (int i = 0; i < n; i++) {
50            index[i] = i;
51        }
52 
53        // The elements from m to n are always kept ascending right to left.
54        // This keeps the dip in the interesting region.
55        reverseAfter(m - 1);
56    }
57 
58    /**
59     * Create a new permutations object.
60     *
61     * @param <T> the type
62     * @param in the source array
63     * @param out the target array
64     * @return the generated permutations object
65     */
66    public static <T> Permutations<T> create(T[] in, T[] out) {
67        return new Permutations<T>(in, out, in.length);
68    }
69 
70    /**
71     * Create a new permutations object.
72     *
73     * @param <T> the type
74     * @param in the source array
75     * @param out the target array
76     * @param m the number of output elements to generate
77     * @return the generated permutations object
78     */
79    public static <T> Permutations<T> create(T[] in, T[] out, int m) {
80        return new Permutations<T>(in, out, m);
81    }
82 
83    /**
84     * Move the index forward a notch. The algorithm first finds the rightmost
85     * index that is less than its neighbor to the right. This is the dip point.
86     * The algorithm next finds the least element to the right of the dip that
87     * is greater than the dip. That element is switched with the dip. Finally,
88     * the list of elements to the right of the dip is reversed.
89     * For example, in a permutation of 5 items, the index may be {1, 2, 4, 3,
90     * 0}. The dip is 2 the rightmost element less than its neighbor on its
91     * right. The least element to the right of 2 that is greater than 2 is 3.
92     * These elements are swapped, yielding {1, 3, 4, 2, 0}, and the list right
93     * of the dip point is reversed, yielding {1, 3, 0, 2, 4}.
94     */
95    private void moveIndex() {
96        // find the index of the first element that dips
97        int i = rightmostDip();
98        if (i < 0) {
99            hasNext = false;
100            return;
101        }
102 
103        // find the least greater element to the right of the dip
104        int leastToRightIndex = i + 1;
105        for (int j = i + 2; j < n; j++) {
106            if (index[j] < index[leastToRightIndex] && index[j] > index[i]) {
107                leastToRightIndex = j;
108            }
109        }
110 
111        // switch dip element with least greater element to its right
112        int t = index[i];
113        index[i] = index[leastToRightIndex];
114        index[leastToRightIndex] = t;
115 
116        if (m - 1 > i) {
117            // reverse the elements to the right of the dip
118            reverseAfter(i);
119 
120            // reverse the elements to the right of m - 1
121            reverseAfter(m - 1);
122        }
123    }
124 
125    /**
126     * Get the index of the first element from the right that is less
127     * than its neighbor on the right.
128     *
129     * @return the index or -1 if non is found
130     */
131    private int rightmostDip() {
132        for (int i = n - 2; i >= 0; i--) {
133            if (index[i] < index[i + 1]) {
134                return i;
135            }
136        }
137        return -1;
138    }
139 
140    /**
141     * Reverse the elements to the right of the specified index.
142     *
143     * @param i the index
144     */
145    private void reverseAfter(int i) {
146        int start = i + 1;
147        int end = n - 1;
148        while (start < end) {
149            int t = index[start];
150            index[start] = index[end];
151            index[end] = t;
152            start++;
153            end--;
154        }
155    }
156 
157    /**
158     * Go to the next lineup, and if available, fill the target array.
159     *
160     * @return if a new lineup is available
161     */
162    public boolean next() {
163        if (!hasNext) {
164            return false;
165        }
166        for (int i = 0; i < m; i++) {
167            out[i] = in[index[i]];
168        }
169        moveIndex();
170        return true;
171    }
172 
173}

[all classes][org.h2.util]
EMMA 2.0.5312 (C) Vladimir Roubtsov