1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package android.support.test.aupt;
18 
19 import junit.framework.TestCase;
20 
21 import java.util.Iterator;
22 import java.util.List;
23 import java.util.Random;
24 
25 /**
26  * A Scheduler produces an execution ordering for our test cases.
27  *
28  * For example, the Sequential scheduler will just repeat our test cases a fixed number of times.
29  */
30 public abstract class Scheduler {
31 
32     /** Shuffle and/or iterate through a list of test cases. */
apply(final List<TestCase> cases)33     public final Iterable<TestCase> apply(final List<TestCase> cases) {
34         return new Iterable<TestCase>() {
35             public Iterator<TestCase> iterator() {
36                 return applyInternal(cases);
37             }
38         };
39     }
40 
41     /**
42      * A Scheduler that just loops through test cases a fixed number of times.
43      *
44      * @param iterations the number of times to loop through every test case.
45      */
46     public static Scheduler sequential(Long iterations) {
47         return new Sequential(iterations);
48     }
49 
50     /**
51      * A Scheduler that permutes the test case list, then just iterates.
52      *
53      * @param iterations the number of times to loop through every test case.
54      * @param random the Random to use: with the same random, we'll return the same ordering.
55      */
56     public static Scheduler shuffled(Random random, Long iterations) {
57         return new Shuffled(random, iterations);
58     }
59 
60     /** Private interface to Scheduler::apply */
61     protected abstract Iterator<TestCase> applyInternal(List<TestCase> cases);
62 
63     private static class Sequential extends Scheduler {
64         private final Long mIterations;
65 
66         Sequential(Long iterations) {
67             mIterations = iterations;
68         }
69 
70         protected Iterator<TestCase> applyInternal (final List<TestCase> cases) {
71             return new Iterator<TestCase>() {
72                 private int count = 0;
73 
74                 public boolean hasNext() {
75                     return count < (cases.size() * mIterations);
76                 }
77 
78                 public TestCase next() {
79                     return cases.get(count++ % cases.size());
80                 }
81 
82                 public void remove() { }
83             };
84         }
85     }
86 
87     private static class Shuffled extends Scheduler {
88         private final Random mRandom;
89         private final Long mIterations;
90 
91         Shuffled(Random random, Long iterations) {
92             mRandom = random;
93             mIterations = iterations;
94         }
95 
96         /**
97          * Find a GCD by the nieve Euclidean Algorithm
98          * TODO: get this from guava or some other library
99          */
100         private int gcd(final int _a, final int _b) {
101             int a = _a;
102             int b = _b;
103 
104             while (b > 0) {
105                 int tmp = b;
106                 b = a % b;
107                 a = tmp;
108             }
109 
110             return a;
111         }
112 
113         /**
114          * Find a random number relatively prime to our modulus
115          * TODO: get this from guava or some other library
116          */
117         private int randomRelPrime(Integer modulus) {
118             if (modulus <= 1) {
119                 return 1;
120             } else {
121                 int x = 0;
122 
123                 // Sample random numbers until we get something coprime to our modulus
124                 while (gcd(x, modulus) != 1) {
125                     x = mRandom.nextInt() % modulus;
126                 }
127 
128                 return x % modulus;
129             }
130         }
131 
132         /**
133          * Return the tests in a shuffled order using a simple linear congruential generator: i.e.
134          * the elements are permuted by (a x + b % n), will produce a permutation of the elements of n
135          * iff a is coprime to n.
136          * <p>
137          * The reason to do this is that it also produces a permutation each cases.size() rounds, which
138          * is *not* the case for Collections.shuffle(); and implementing a comparable iterator with
139          * those primitives is somewhat less elegant.
140          */
141         protected Iterator<TestCase> applyInternal(final List<TestCase> cases) {
142             final int a = randomRelPrime(cases.size());
143             final int b = Math.abs(mRandom.nextInt());
144 
145             return new Iterator<TestCase>() {
146                 private int count = 0;
147 
148                 public boolean hasNext() {
149                     return count < (cases.size() * mIterations);
150                 }
151 
152                 public TestCase next() {
153                     return cases.get((a * (count++) + b) % cases.size());
154                 }
155 
156                 public void remove() {
157                 }
158             };
159         }
160     }
161 }
162