1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.rng;
18
19 import java.util.Objects;
20 import java.util.Spliterator;
21 import java.util.function.Consumer;
22 import java.util.function.DoubleConsumer;
23 import java.util.function.IntConsumer;
24 import java.util.function.LongConsumer;
25 import java.util.function.ToDoubleFunction;
26 import java.util.function.ToIntFunction;
27 import java.util.function.ToLongFunction;
28
29 /**
30 * Support for {@link UniformRandomProvider} default methods.
31 *
32 * @since 1.5
33 */
34 final class UniformRandomProviderSupport {
35 /** Message for an invalid stream size. */
36 private static final String INVALID_STREAM_SIZE = "Invalid stream size: ";
37 /** Message for an invalid upper bound (must be positive, finite and above zero). */
38 private static final String INVALID_UPPER_BOUND = "Upper bound must be above zero: ";
39 /** Message format for an invalid range for lower inclusive and upper exclusive. */
40 private static final String INVALID_RANGE = "Invalid range: [%s, %s)";
41 /** 2^32. */
42 private static final long POW_32 = 1L << 32;
43 /** Message when the consumer action is null. */
44 private static final String NULL_ACTION = "action must not be null";
45
46 /** No instances. */
47 private UniformRandomProviderSupport() {}
48
49 /**
50 * Validate the stream size.
51 *
52 * @param size Stream size.
53 * @throws IllegalArgumentException if {@code size} is negative.
54 */
55 static void validateStreamSize(long size) {
56 if (size < 0) {
57 throw new IllegalArgumentException(INVALID_STREAM_SIZE + size);
58 }
59 }
60
61 /**
62 * Validate the upper bound.
63 *
64 * @param bound Upper bound (exclusive) on the random number to be returned.
65 * @throws IllegalArgumentException if {@code bound} is equal to or less than zero.
66 */
67 static void validateUpperBound(int bound) {
68 if (bound <= 0) {
69 throw new IllegalArgumentException(INVALID_UPPER_BOUND + bound);
70 }
71 }
72
73 /**
74 * Validate the upper bound.
75 *
76 * @param bound Upper bound (exclusive) on the random number to be returned.
77 * @throws IllegalArgumentException if {@code bound} is equal to or less than zero.
78 */
79 static void validateUpperBound(long bound) {
80 if (bound <= 0) {
81 throw new IllegalArgumentException(INVALID_UPPER_BOUND + bound);
82 }
83 }
84
85 /**
86 * Validate the upper bound.
87 *
88 * @param bound Upper bound (exclusive) on the random number to be returned.
89 * @throws IllegalArgumentException if {@code bound} is equal to or less than zero, or
90 * is not finite
91 */
92 static void validateUpperBound(float bound) {
93 // Negation of logic will detect NaN
94 if (!(bound > 0 && bound <= Float.MAX_VALUE)) {
95 throw new IllegalArgumentException(INVALID_UPPER_BOUND + bound);
96 }
97 }
98
99 /**
100 * Validate the upper bound.
101 *
102 * @param bound Upper bound (exclusive) on the random number to be returned.
103 * @throws IllegalArgumentException if {@code bound} is equal to or less than zero, or
104 * is not finite
105 */
106 static void validateUpperBound(double bound) {
107 // Negation of logic will detect NaN
108 if (!(bound > 0 && bound <= Double.MAX_VALUE)) {
109 throw new IllegalArgumentException(INVALID_UPPER_BOUND + bound);
110 }
111 }
112
113 /**
114 * Validate the range between the specified {@code origin} (inclusive) and the
115 * specified {@code bound} (exclusive).
116 *
117 * @param origin Lower bound on the random number to be returned.
118 * @param bound Upper bound (exclusive) on the random number to be returned.
119 * @throws IllegalArgumentException if {@code origin} is greater than or equal to
120 * {@code bound}.
121 */
122 static void validateRange(int origin, int bound) {
123 if (origin >= bound) {
124 throw new IllegalArgumentException(String.format(INVALID_RANGE, origin, bound));
125 }
126 }
127
128 /**
129 * Validate the range between the specified {@code origin} (inclusive) and the
130 * specified {@code bound} (exclusive).
131 *
132 * @param origin Lower bound on the random number to be returned.
133 * @param bound Upper bound (exclusive) on the random number to be returned.
134 * @throws IllegalArgumentException if {@code origin} is greater than or equal to
135 * {@code bound}.
136 */
137 static void validateRange(long origin, long bound) {
138 if (origin >= bound) {
139 throw new IllegalArgumentException(String.format(INVALID_RANGE, origin, bound));
140 }
141 }
142
143 /**
144 * Validate the range between the specified {@code origin} (inclusive) and the
145 * specified {@code bound} (exclusive).
146 *
147 * @param origin Lower bound on the random number to be returned.
148 * @param bound Upper bound (exclusive) on the random number to be returned.
149 * @throws IllegalArgumentException if {@code origin} is not finite, or {@code bound}
150 * is not finite, or {@code origin} is greater than or equal to {@code bound}.
151 */
152 static void validateRange(double origin, double bound) {
153 if (origin >= bound || !Double.isFinite(origin) || !Double.isFinite(bound)) {
154 throw new IllegalArgumentException(String.format(INVALID_RANGE, origin, bound));
155 }
156 }
157
158 /**
159 * Checks if the sub-range from fromIndex (inclusive) to fromIndex + size (exclusive) is
160 * within the bounds of range from 0 (inclusive) to length (exclusive).
161 *
162 * <p>This function provides the functionality of
163 * {@code java.utils.Objects.checkFromIndexSize} introduced in JDK 9. The
164 * <a href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Objects.html#checkFromIndexSize(int,int,int)">Objects</a>
165 * javadoc has been reproduced for reference.
166 *
167 * <p>The sub-range is defined to be out of bounds if any of the following inequalities
168 * is true:
169 * <ul>
170 * <li>{@code fromIndex < 0}
171 * <li>{@code size < 0}
172 * <li>{@code fromIndex + size > length}, taking into account integer overflow
173 * <li>{@code length < 0}, which is implied from the former inequalities
174 * </ul>
175 *
176 * <p>Note: This is not an exact implementation of the functionality of
177 * {@code Objects.checkFromIndexSize}. The following changes have been made:
178 * <ul>
179 * <li>The method signature has been changed to avoid the return of {@code fromIndex};
180 * this value is not used within this package.
181 * <li>No checks are made for {@code length < 0} as this is assumed to be derived from
182 * an array length.
183 * </ul>
184 *
185 * @param fromIndex the lower-bound (inclusive) of the sub-interval
186 * @param size the size of the sub-range
187 * @param length the upper-bound (exclusive) of the range
188 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
189 */
190 static void validateFromIndexSize(int fromIndex, int size, int length) {
191 // check for any negatives (assume 'length' is positive array length),
192 // or overflow safe length check given the values are all positive
193 // remaining = length - fromIndex
194 if ((fromIndex | size) < 0 || size > length - fromIndex) {
195 throw new IndexOutOfBoundsException(
196 // Note: %<d is 'relative indexing' to re-use the last argument
197 String.format("Range [%d, %<d + %d) out of bounds for length %d",
198 fromIndex, size, length));
199 }
200 }
201
202 /**
203 * Generates random bytes and places them into a user-supplied array.
204 *
205 * <p>The array is filled with bytes extracted from random {@code long} values. This
206 * implies that the number of random bytes generated may be larger than the length of
207 * the byte array.
208 *
209 * @param source Source of randomness.
210 * @param bytes Array in which to put the generated bytes. Cannot be null.
211 * @param start Index at which to start inserting the generated bytes.
212 * @param len Number of bytes to insert.
213 */
214 static void nextBytes(UniformRandomProvider source,
215 byte[] bytes, int start, int len) {
216 // Index of first insertion plus multiple of 8 part of length
217 // (i.e. length with 3 least significant bits unset).
218 final int indexLoopLimit = start + (len & 0x7ffffff8);
219
220 // Start filling in the byte array, 8 bytes at a time.
221 int index = start;
222 while (index < indexLoopLimit) {
223 final long random = source.nextLong();
224 bytes[index++] = (byte) random;
225 bytes[index++] = (byte) (random >>> 8);
226 bytes[index++] = (byte) (random >>> 16);
227 bytes[index++] = (byte) (random >>> 24);
228 bytes[index++] = (byte) (random >>> 32);
229 bytes[index++] = (byte) (random >>> 40);
230 bytes[index++] = (byte) (random >>> 48);
231 bytes[index++] = (byte) (random >>> 56);
232 }
233
234 // Index of last insertion + 1
235 final int indexLimit = start + len;
236
237 // Fill in the remaining bytes.
238 if (index < indexLimit) {
239 long random = source.nextLong();
240 for (;;) {
241 bytes[index++] = (byte) random;
242 if (index == indexLimit) {
243 break;
244 }
245 random >>>= 8;
246 }
247 }
248 }
249
250 /**
251 * Generates an {@code int} value between 0 (inclusive) and the specified value
252 * (exclusive).
253 *
254 * @param source Source of randomness.
255 * @param n Bound on the random number to be returned. Must be strictly positive.
256 * @return a random {@code int} value between 0 (inclusive) and {@code n} (exclusive).
257 */
258 static int nextInt(UniformRandomProvider source,
259 int n) {
260 // Lemire (2019): Fast Random Integer Generation in an Interval
261 // https://arxiv.org/abs/1805.10941
262 long m = (source.nextInt() & 0xffffffffL) * n;
263 long l = m & 0xffffffffL;
264 if (l < n) {
265 // 2^32 % n
266 final long t = POW_32 % n;
267 while (l < t) {
268 m = (source.nextInt() & 0xffffffffL) * n;
269 l = m & 0xffffffffL;
270 }
271 }
272 return (int) (m >>> 32);
273 }
274
275 /**
276 * Generates an {@code int} value between the specified {@code origin} (inclusive) and
277 * the specified {@code bound} (exclusive).
278 *
279 * @param source Source of randomness.
280 * @param origin Lower bound on the random number to be returned.
281 * @param bound Upper bound (exclusive) on the random number to be returned. Must be
282 * above {@code origin}.
283 * @return a random {@code int} value between {@code origin} (inclusive) and
284 * {@code bound} (exclusive).
285 */
286 static int nextInt(UniformRandomProvider source,
287 int origin, int bound) {
288 final int n = bound - origin;
289 if (n > 0) {
290 return nextInt(source, n) + origin;
291 }
292 // Range too large to fit in a positive integer.
293 // Use simple rejection.
294 int v = source.nextInt();
295 while (v < origin || v >= bound) {
296 v = source.nextInt();
297 }
298 return v;
299 }
300
301 /**
302 * Generates an {@code long} value between 0 (inclusive) and the specified value
303 * (exclusive).
304 *
305 * @param source Source of randomness.
306 * @param n Bound on the random number to be returned. Must be strictly positive.
307 * @return a random {@code long} value between 0 (inclusive) and {@code n}
308 * (exclusive).
309 */
310 static long nextLong(UniformRandomProvider source,
311 long n) {
312 long bits;
313 long val;
314 do {
315 bits = source.nextLong() >>> 1;
316 val = bits % n;
317 } while (bits - val + (n - 1) < 0);
318
319 return val;
320 }
321
322 /**
323 * Generates a {@code long} value between the specified {@code origin} (inclusive) and
324 * the specified {@code bound} (exclusive).
325 *
326 * @param source Source of randomness.
327 * @param origin Lower bound on the random number to be returned.
328 * @param bound Upper bound (exclusive) on the random number to be returned. Must be
329 * above {@code origin}.
330 * @return a random {@code long} value between {@code origin} (inclusive) and
331 * {@code bound} (exclusive).
332 */
333 static long nextLong(UniformRandomProvider source,
334 long origin, long bound) {
335 final long n = bound - origin;
336 if (n > 0) {
337 return nextLong(source, n) + origin;
338 }
339 // Range too large to fit in a positive integer.
340 // Use simple rejection.
341 long v = source.nextLong();
342 while (v < origin || v >= bound) {
343 v = source.nextLong();
344 }
345 return v;
346 }
347
348 /**
349 * Generates a {@code float} value between 0 (inclusive) and the specified value
350 * (exclusive).
351 *
352 * @param source Source of randomness.
353 * @param bound Bound on the random number to be returned. Must be strictly positive.
354 * @return a random {@code float} value between 0 (inclusive) and {@code bound}
355 * (exclusive).
356 */
357 static float nextFloat(UniformRandomProvider source,
358 float bound) {
359 float v = source.nextFloat() * bound;
360 if (v >= bound) {
361 // Correct rounding
362 v = Math.nextDown(bound);
363 }
364 return v;
365 }
366
367 /**
368 * Generates a {@code float} value between the specified {@code origin} (inclusive)
369 * and the specified {@code bound} (exclusive).
370 *
371 * @param source Source of randomness.
372 * @param origin Lower bound on the random number to be returned. Must be finite.
373 * @param bound Upper bound (exclusive) on the random number to be returned. Must be
374 * above {@code origin} and finite.
375 * @return a random {@code float} value between {@code origin} (inclusive) and
376 * {@code bound} (exclusive).
377 */
378 static float nextFloat(UniformRandomProvider source,
379 float origin, float bound) {
380 float v = source.nextFloat();
381 // This expression allows (bound - origin) to be infinite
382 // origin + (bound - origin) * v
383 // == origin - origin * v + bound * v
384 v = (1f - v) * origin + v * bound;
385 if (v >= bound) {
386 // Correct rounding
387 v = Math.nextDown(bound);
388 }
389 return v;
390 }
391
392 /**
393 * Generates a {@code double} value between 0 (inclusive) and the specified value
394 * (exclusive).
395 *
396 * @param source Source of randomness.
397 * @param bound Bound on the random number to be returned. Must be strictly positive.
398 * @return a random {@code double} value between 0 (inclusive) and {@code bound}
399 * (exclusive).
400 */
401 static double nextDouble(UniformRandomProvider source,
402 double bound) {
403 double v = source.nextDouble() * bound;
404 if (v >= bound) {
405 // Correct rounding
406 v = Math.nextDown(bound);
407 }
408 return v;
409 }
410
411 /**
412 * Generates a {@code double} value between the specified {@code origin} (inclusive)
413 * and the specified {@code bound} (exclusive).
414 *
415 * @param source Source of randomness.
416 * @param origin Lower bound on the random number to be returned. Must be finite.
417 * @param bound Upper bound (exclusive) on the random number to be returned. Must be
418 * above {@code origin} and finite.
419 * @return a random {@code double} value between {@code origin} (inclusive) and
420 * {@code bound} (exclusive).
421 */
422 static double nextDouble(UniformRandomProvider source,
423 double origin, double bound) {
424 double v = source.nextDouble();
425 // This expression allows (bound - origin) to be infinite
426 // origin + (bound - origin) * v
427 // == origin - origin * v + bound * v
428 v = (1f - v) * origin + v * bound;
429 if (v >= bound) {
430 // Correct rounding
431 v = Math.nextDown(bound);
432 }
433 return v;
434 }
435
436 // Spliterator support
437
438 /**
439 * Base class for spliterators for streams of values. Contains the range current position and
440 * end position. Splitting is expected to divide the range in half and create instances
441 * that span the two ranges.
442 */
443 private static class ProviderSpliterator {
444 /** The current position in the range. */
445 protected long position;
446 /** The upper limit of the range. */
447 protected final long end;
448
449 /**
450 * @param start Start position of the stream (inclusive).
451 * @param end Upper limit of the stream (exclusive).
452 */
453 ProviderSpliterator(long start, long end) {
454 position = start;
455 this.end = end;
456 }
457
458 // Methods required by all Spliterators
459
460 // See Spliterator.estimateSize()
461 public long estimateSize() {
462 return end - position;
463 }
464
465 // See Spliterator.characteristics()
466 public int characteristics() {
467 return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL | Spliterator.IMMUTABLE;
468 }
469 }
470
471 /**
472 * Spliterator for streams of SplittableUniformRandomProvider.
473 */
474 static class ProviderSplitsSpliterator extends ProviderSpliterator
475 implements Spliterator<SplittableUniformRandomProvider> {
476 /** Source of randomness used to initialise the new instances. */
477 private final SplittableUniformRandomProvider source;
478 /** Generator to split to create new instances. */
479 private final SplittableUniformRandomProvider rng;
480
481 /**
482 * @param start Start position of the stream (inclusive).
483 * @param end Upper limit of the stream (exclusive).
484 * @param source Source of randomness used to initialise the new instances.
485 * @param rng Generator to split to create new instances.
486 */
487 ProviderSplitsSpliterator(long start, long end,
488 SplittableUniformRandomProvider source,
489 SplittableUniformRandomProvider rng) {
490 super(start, end);
491 this.source = source;
492 this.rng = rng;
493 }
494
495 @Override
496 public Spliterator<SplittableUniformRandomProvider> trySplit() {
497 final long start = position;
498 final long middle = (start + end) >>> 1;
499 if (middle <= start) {
500 return null;
501 }
502 position = middle;
503 return new ProviderSplitsSpliterator(start, middle, source.split(), rng);
504 }
505
506 @Override
507 public boolean tryAdvance(Consumer<? super SplittableUniformRandomProvider> action) {
508 Objects.requireNonNull(action, NULL_ACTION);
509 final long pos = position;
510 if (pos < end) {
511 // Advance before exceptions from the action are relayed to the caller
512 position = pos + 1;
513 action.accept(rng.split(source));
514 return true;
515 }
516 return false;
517 }
518
519 @Override
520 public void forEachRemaining(Consumer<? super SplittableUniformRandomProvider> action) {
521 Objects.requireNonNull(action, NULL_ACTION);
522 long pos = position;
523 final long last = end;
524 if (pos < last) {
525 // Ensure forEachRemaining is called only once
526 position = last;
527 final SplittableUniformRandomProvider s = source;
528 final SplittableUniformRandomProvider r = rng;
529 do {
530 action.accept(r.split(s));
531 } while (++pos < last);
532 }
533 }
534 }
535
536 /**
537 * Spliterator for streams of int values that may be recursively split.
538 */
539 static class ProviderIntsSpliterator extends ProviderSpliterator
540 implements Spliterator.OfInt {
541 /** Source of randomness. */
542 private final SplittableUniformRandomProvider source;
543 /** Value generator function. */
544 private final ToIntFunction<SplittableUniformRandomProvider> gen;
545
546 /**
547 * @param start Start position of the stream (inclusive).
548 * @param end Upper limit of the stream (exclusive).
549 * @param source Source of randomness.
550 * @param gen Value generator function.
551 */
552 ProviderIntsSpliterator(long start, long end,
553 SplittableUniformRandomProvider source,
554 ToIntFunction<SplittableUniformRandomProvider> gen) {
555 super(start, end);
556 this.source = source;
557 this.gen = gen;
558 }
559
560 @Override
561 public Spliterator.OfInt trySplit() {
562 final long start = position;
563 final long middle = (start + end) >>> 1;
564 if (middle <= start) {
565 return null;
566 }
567 position = middle;
568 return new ProviderIntsSpliterator(start, middle, source.split(), gen);
569 }
570
571 @Override
572 public boolean tryAdvance(IntConsumer action) {
573 Objects.requireNonNull(action, NULL_ACTION);
574 final long pos = position;
575 if (pos < end) {
576 // Advance before exceptions from the action are relayed to the caller
577 position = pos + 1;
578 action.accept(gen.applyAsInt(source));
579 return true;
580 }
581 return false;
582 }
583
584 @Override
585 public void forEachRemaining(IntConsumer action) {
586 Objects.requireNonNull(action, NULL_ACTION);
587 long pos = position;
588 final long last = end;
589 if (pos < last) {
590 // Ensure forEachRemaining is called only once
591 position = last;
592 final SplittableUniformRandomProvider s = source;
593 final ToIntFunction<SplittableUniformRandomProvider> g = gen;
594 do {
595 action.accept(g.applyAsInt(s));
596 } while (++pos < last);
597 }
598 }
599 }
600
601 /**
602 * Spliterator for streams of long values that may be recursively split.
603 */
604 static class ProviderLongsSpliterator extends ProviderSpliterator
605 implements Spliterator.OfLong {
606 /** Source of randomness. */
607 private final SplittableUniformRandomProvider source;
608 /** Value generator function. */
609 private final ToLongFunction<SplittableUniformRandomProvider> gen;
610
611 /**
612 * @param start Start position of the stream (inclusive).
613 * @param end Upper limit of the stream (exclusive).
614 * @param source Source of randomness.
615 * @param gen Value generator function.
616 */
617 ProviderLongsSpliterator(long start, long end,
618 SplittableUniformRandomProvider source,
619 ToLongFunction<SplittableUniformRandomProvider> gen) {
620 super(start, end);
621 this.source = source;
622 this.gen = gen;
623 }
624
625 @Override
626 public Spliterator.OfLong trySplit() {
627 final long start = position;
628 final long middle = (start + end) >>> 1;
629 if (middle <= start) {
630 return null;
631 }
632 position = middle;
633 return new ProviderLongsSpliterator(start, middle, source.split(), gen);
634 }
635
636 @Override
637 public boolean tryAdvance(LongConsumer action) {
638 Objects.requireNonNull(action, NULL_ACTION);
639 final long pos = position;
640 if (pos < end) {
641 // Advance before exceptions from the action are relayed to the caller
642 position = pos + 1;
643 action.accept(gen.applyAsLong(source));
644 return true;
645 }
646 return false;
647 }
648
649 @Override
650 public void forEachRemaining(LongConsumer action) {
651 Objects.requireNonNull(action, NULL_ACTION);
652 long pos = position;
653 final long last = end;
654 if (pos < last) {
655 // Ensure forEachRemaining is called only once
656 position = last;
657 final SplittableUniformRandomProvider s = source;
658 final ToLongFunction<SplittableUniformRandomProvider> g = gen;
659 do {
660 action.accept(g.applyAsLong(s));
661 } while (++pos < last);
662 }
663 }
664 }
665
666 /**
667 * Spliterator for streams of double values that may be recursively split.
668 */
669 static class ProviderDoublesSpliterator extends ProviderSpliterator
670 implements Spliterator.OfDouble {
671 /** Source of randomness. */
672 private final SplittableUniformRandomProvider source;
673 /** Value generator function. */
674 private final ToDoubleFunction<SplittableUniformRandomProvider> gen;
675
676 /**
677 * @param start Start position of the stream (inclusive).
678 * @param end Upper limit of the stream (exclusive).
679 * @param source Source of randomness.
680 * @param gen Value generator function.
681 */
682 ProviderDoublesSpliterator(long start, long end,
683 SplittableUniformRandomProvider source,
684 ToDoubleFunction<SplittableUniformRandomProvider> gen) {
685 super(start, end);
686 this.source = source;
687 this.gen = gen;
688 }
689
690 @Override
691 public Spliterator.OfDouble trySplit() {
692 final long start = position;
693 final long middle = (start + end) >>> 1;
694 if (middle <= start) {
695 return null;
696 }
697 position = middle;
698 return new ProviderDoublesSpliterator(start, middle, source.split(), gen);
699 }
700
701 @Override
702 public boolean tryAdvance(DoubleConsumer action) {
703 Objects.requireNonNull(action, NULL_ACTION);
704 final long pos = position;
705 if (pos < end) {
706 // Advance before exceptions from the action are relayed to the caller
707 position = pos + 1;
708 action.accept(gen.applyAsDouble(source));
709 return true;
710 }
711 return false;
712 }
713
714 @Override
715 public void forEachRemaining(DoubleConsumer action) {
716 Objects.requireNonNull(action, NULL_ACTION);
717 long pos = position;
718 final long last = end;
719 if (pos < last) {
720 // Ensure forEachRemaining is called only once
721 position = last;
722 final SplittableUniformRandomProvider s = source;
723 final ToDoubleFunction<SplittableUniformRandomProvider> g = gen;
724 do {
725 action.accept(g.applyAsDouble(s));
726 } while (++pos < last);
727 }
728 }
729 }
730 }