fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collection;
  4. import java.util.Collections;
  5. import java.util.Comparator;
  6. import java.util.Iterator;
  7. import java.util.List;
  8. import java.util.NoSuchElementException;
  9.  
  10. public class Main {
  11.  
  12.     @SafeVarargs
  13.     private static <T> Iterator<T> from(T... array) {
  14.         return Arrays.asList(array).iterator();
  15.     }
  16.  
  17.     @SafeVarargs
  18.     private static <T> void testSuperIterator(List<T> expected, Comparator<T> comparator, Iterator<T>... iterators) {
  19.         final SuperIterator<T> superIterator = new SuperIterator<T>(Arrays.asList(iterators), comparator);
  20.         final List<T> actual = new ArrayList<>(expected.size());
  21.         while (superIterator.hasNext()) {
  22.             actual.add(superIterator.next());
  23.         }
  24.  
  25.         if (!actual.equals(expected)) {
  26.             throw new IllegalStateException("Expected: " + expected + "! Actual: " + actual);
  27.         }
  28.         System.out.println(actual);
  29.     }
  30.  
  31.     private static Comparator<Integer> INTEGER_COMPARATOR = Integer::compareTo;
  32.  
  33.     @SafeVarargs
  34.     private static void testIntSuperIterator(List<Integer> expected, Iterator<Integer>... iterators) {
  35.         testSuperIterator(expected, INTEGER_COMPARATOR, iterators);
  36.     }
  37.  
  38.     private static Iterator EMPTY_ITERATOR_INSTANCE = new Iterator() {
  39.  
  40.         @Override
  41.         public boolean hasNext() {
  42.             return false;
  43.         }
  44.  
  45.         @Override
  46.         public Object next() {
  47.             throw new NoSuchElementException();
  48.         }
  49.     };
  50.  
  51.     private static <T> Iterator<T> emptyIterator() {
  52.         //noinspection unchecked
  53.         return EMPTY_ITERATOR_INSTANCE;
  54.     }
  55.  
  56.     static class SuperIterator<T> implements Iterator<T> {
  57.  
  58.         private final Iterator<T>[] iterators;
  59.  
  60.         private final Object[] peekedElements;
  61.  
  62.         private final Comparator<T> comparator;
  63.  
  64.         public SuperIterator(Collection<Iterator<T>> iterators, Comparator<T> comparator) {
  65.             //noinspection unchecked
  66.             final Iterator<T>[] iteratorsArray = (Iterator<T>[]) iterators.toArray();
  67.             this.iterators = iteratorsArray;
  68.             this.peekedElements = new Object[iteratorsArray.length];
  69.             this.comparator = comparator;
  70.         }
  71.  
  72.         @Override
  73.         public boolean hasNext() {
  74.             for (Object peekedElement : peekedElements) {
  75.                 if (peekedElement != null) {
  76.                     return true;
  77.                 }
  78.             }
  79.  
  80.             final Iterator<T>[] iterators = this.iterators;
  81.             for (int i = 0; i < iterators.length; i++) {
  82.                 final Iterator<T> iterator = iterators[i];
  83.                 if (iterator != null) {
  84.                     if (iterator.hasNext()) {
  85.                         return true;
  86.                     } else {
  87.                         iterators[i] = null;
  88.                     }
  89.                 }
  90.             }
  91.  
  92.             return false;
  93.         }
  94.  
  95.         @Override
  96.         public T next() {
  97.             final Iterator<T>[] iterators = this.iterators;
  98.             final Object[] peekedElements = this.peekedElements;
  99.  
  100.             final int length = iterators.length;
  101.             int minValuePosition = -1;
  102.             T minValue = null;
  103.             for (int i = 0; i < length; i++) {
  104.                 //noinspection unchecked
  105.                 T peekedElement = (T) peekedElements[i];
  106.                 if (peekedElement == null) {
  107.                     final Iterator<T> iterator = iterators[i];
  108.                     if (iterator != null) {
  109.                         if (iterator.hasNext()) {
  110.                             peekedElements[i] = peekedElement = iterator.next();
  111.                         } else {
  112.                             iterators[i] = null;
  113.                         }
  114.                     }
  115.                 }
  116.                 if (peekedElement != null && (minValuePosition < 0 || comparator.compare(peekedElement, minValue) < 0)) {
  117.                     minValuePosition = i;
  118.                     minValue = peekedElement;
  119.                 }
  120.             }
  121.  
  122.             if (minValuePosition < 0) {
  123.                 throw new NoSuchElementException();
  124.             }
  125.  
  126.             peekedElements[minValuePosition] = null;
  127.  
  128.             return minValue;
  129.         }
  130.     }
  131.  
  132.     public static void main(String[] args) {
  133.         testIntSuperIterator(
  134.                 Collections.emptyList(),
  135.                 emptyIterator()
  136.         );
  137.  
  138.         testIntSuperIterator(
  139.                 Collections.singletonList(1),
  140.                 from(1)
  141.         );
  142.  
  143.         testIntSuperIterator(
  144.                 Collections.singletonList(Integer.MIN_VALUE),
  145.                 from(Integer.MIN_VALUE)
  146.         );
  147.  
  148.         testIntSuperIterator(
  149.                 Arrays.asList(1, 2, 4, 5),
  150.                 from(1, 2, 4, 5)
  151.         );
  152.  
  153.         testIntSuperIterator(
  154.                 Arrays.asList(Integer.MIN_VALUE, 1, 2, 4, 5),
  155.                 from(Integer.MIN_VALUE, 1, 2, 4, 5)
  156.         );
  157.  
  158.         testIntSuperIterator(
  159.                 Arrays.asList(1, 2, 4, 5),
  160.                 emptyIterator(), from(1, 2, 4, 5)
  161.         );
  162.  
  163.         testIntSuperIterator(
  164.                 Arrays.asList(1, 2, 4, 5),
  165.                 from(1, 2, 4, 5), emptyIterator()
  166.         );
  167.  
  168.         testIntSuperIterator(
  169.                 Arrays.asList(Integer.MIN_VALUE, 1, 2, 4, 5),
  170.                 emptyIterator(), from(Integer.MIN_VALUE, 1, 2, 4, 5)
  171.         );
  172.  
  173.         testIntSuperIterator(
  174.                 Arrays.asList(Integer.MIN_VALUE, 1, 2, 4, 5),
  175.                 from(Integer.MIN_VALUE, 1, 2, 4, 5), emptyIterator()
  176.         );
  177.  
  178.         testIntSuperIterator(
  179.                 Arrays.asList(1, 2, 4, 5),
  180.                 from(5), from(4), from(1), from(2)
  181.         );
  182.  
  183.         testIntSuperIterator(
  184.                 Arrays.asList(1, 1, 2, 4, 5),
  185.                 from(1, 5), from(4), from(1), from(2)
  186.         );
  187.  
  188.         testIntSuperIterator(
  189.                 Arrays.asList(1, 1, 2, 2, 2, 4, 5),
  190.                 from(1, 2, 2, 5), from(4), from(1), from(2)
  191.         );
  192.  
  193.         testIntSuperIterator(
  194.                 Arrays.asList(1, 1, 2, 2, 2, 4, 5, Integer.MAX_VALUE, Integer.MAX_VALUE),
  195.                 from(1, 2, 5), from(4, Integer.MAX_VALUE), from(1), from(2, 2, Integer.MAX_VALUE)
  196.         );
  197.     }
  198. }
  199.  
Success #stdin #stdout 0.13s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[]
[1]
[-2147483648]
[1, 2, 4, 5]
[-2147483648, 1, 2, 4, 5]
[1, 2, 4, 5]
[1, 2, 4, 5]
[-2147483648, 1, 2, 4, 5]
[-2147483648, 1, 2, 4, 5]
[1, 2, 4, 5]
[1, 1, 2, 4, 5]
[1, 1, 2, 2, 2, 4, 5]
[1, 1, 2, 2, 2, 4, 5, 2147483647, 2147483647]
https://ideone.com/76xE4T
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!