001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 * image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause).
006 * Copyright (c) 2006-2023 Wilhelm Burger, Mark J. Burge. All rights reserved.
007 * Visit https://imagingbook.com for additional details.
008 ******************************************************************************/
009package imagingbook.common.ransac;
010
011import java.util.Arrays;
012import java.util.Random;
013
014/**
015 * An instance of this class randomly draws a set of k unique, non-null elements from a given array of element type T,
016 * which may contain null elements (see method {@link #drawFrom(Object[], int)}). The size of the draw (k) is fixed and
017 * must be specified at construction. The resulting sets contain no duplicate elements.
018 *
019 * @param <T> element type
020 * @author WB
021 * @version 2022/11/19
022 */
023public class RandomDraw<T> {
024        
025        /**
026         * Default maximum number of tries before exception is thrown.
027         */
028        public static final int DefaultMaxTries = 1000;
029        
030        private int maxTries = DefaultMaxTries;
031        private final Random rand;
032        
033        // -------------------------------------------------------------
034
035        /**
036         * Constructor accepting an existing random generator. This may be useful to achieve predictable (repetitive) random
037         * behavior.
038         *
039         * @param rand a random generator of type {@link Random}
040         */
041        public RandomDraw(Random rand) {
042                this.rand = (rand == null) ? new Random() : rand;
043        }
044        
045        /**
046         * Constructor creating its own random generator.
047         */
048        public RandomDraw() {
049                this(new Random());
050        }
051        
052        /**
053         * Set the maximum number of tries.
054         * @param maxTries new maximum number of tries
055         * @see #DefaultMaxTries
056         */
057        public void setMaxTries(int maxTries) {
058                this.maxTries = maxTries;
059        }
060        
061        // -------------------------------------------------------------
062        
063        // alternative version using a HashSet (slower)
064//      public T[] drawFrom(T[] items, int k) {
065//              if (k < 1) throw new IllegalArgumentException("k must be greater or equal 1");
066//              HashSet<T> hs = new HashSet<>(k);
067//              int i = 0;
068//              while (i < k) {
069//                      int j = rand.nextInt(items.length);     // next random index
070//                      T item = items[j];
071//                      if (item != null && hs.add(item)) {
072//                              i++;
073//                      }
074//              }
075//              return hs.toArray(Arrays.copyOf(items, k));
076//      }
077
078        /**
079         * Randomly draws a set of k unique, non-null elements from the specified array of items, ignoring possible null
080         * elements. An exception is thrown if the maximum number of tries is exceeded (see {@link #DefaultMaxTries}). The
081         * returned array contains no null elements and no duplicates. Example:
082         * <pre>
083         * Integer[] numbers = { null, 1, 2, null, 3, 4, 5, 6, 7, null, null, null, 8, 9, 10, null };
084         * RandomDraw&lt;Integer&gt; rd = new RandomDraw&lt;&gt;();
085         * Integer[] draw = rd.drawFrom(numbers, 2);
086         * </pre>
087         *
088         * @param items an array of elements of type T, null elements being allowed
089         * @param k the number of items to draw
090         * @return an array of k randomly drawn (non-null) items
091         */
092        public T[] drawFrom(T[] items, int k) {
093                if (k < 1) throw new IllegalArgumentException("k must be greater or equal 1");
094                int[] idx = drawRandomIndexes(items, k);
095                T[] draw = Arrays.copyOf(items, k);     // trick to create an array of generic type T
096                for (int i = 0; i < k; i++) {
097                        draw[i] = items[idx[i]];
098                }
099                return draw;
100        }
101        
102        // draw k unique integers (all must be different):
103        private int[] drawRandomIndexes(T[] items, int k) {
104                int[] indexes = new int[k];
105                for (int d = 0; d < k; d++) {
106                        int j = 0;                                                      // count tries
107                        int i = rand.nextInt(items.length);
108                        while (items[i] == null || wasPickedBefore(indexes, d, i)) {
109                                i = rand.nextInt(items.length);
110                                if (j++ > maxTries) {
111                                        throw new RuntimeException("max. tries exceeded: " + j);
112                                }
113                        }
114                        indexes[d] = i;
115                }
116                return indexes;
117        }
118
119        // Checks if idx[0],...,idx[d-1] contains i.
120        private boolean wasPickedBefore(int[] indexes, int d, int i) {
121                for (int j = 0; j < d; j++) {
122                        if (i == indexes[j]) {
123                                return true;
124                        }
125                }       
126                return false;
127        }
128        
129}