fork download
copy 
  1. import java.util.Collection;
  2. import java.util.AbstractQueue;
  3. import java.util.Iterator;
  4.  
  5. import java.util.NoSuchElementException;
  6. import java.util.ConcurrentModificationException;
  7.  
  8. import static java.lang.Math.max;
  9.  
  10. /**
  11.  * A maximum priority queue based on an unordered array.
  12.  * Supports fast constant-time insertions of the elements, but
  13.  * the retrieve-max-value methods work only in linear time.
  14.  */
  15. class MaxPQUnorderedArray<T extends Comparable<? super T>>
  16.         extends AbstractQueue<T> {
  17.     // we will start with an array with 2 empty cells
  18.     public static final int MIN_SIZE = 2;
  19.  
  20.     private T[] data; 
  21.     private int size = 0;
  22.     private int nQueueMutations = 0;
  23.  
  24.     public MaxPQUnorderedArray() {
  25.         this(MIN_SIZE);
  26.     }
  27.  
  28.     /**
  29.      * Creates a MaxPQ containing the elements from the
  30.      * specified collection.
  31.      */
  32.     @SuppressWarnings("unchecked")
  33.     public MaxPQUnorderedArray(Collection<T> elements) {
  34.         final int arraySize = elements.size()
  35.             + max(MIN_SIZE, elements.size() / 2);
  36.         data = (T[]) new Comparable<?>[arraySize];
  37.  
  38.         int i = 0;
  39.         for (T element : elements) {
  40.             data[i] = element;
  41.             i++;
  42.         }
  43.         this.size = elements.size();
  44.     }
  45.  
  46.     /**
  47.      * Create an empty queue with the specified initial capacity.
  48.      * @param   initialCapacity has to be at least as large as
  49.      *          {@code MIN_SIZE}.
  50.      */
  51.     @SuppressWarnings("unchecked")
  52.     public MaxPQUnorderedArray(int initialCapacity) {
  53.         if (initialCapacity < MIN_SIZE) {
  54.             throw new IllegalStateException(String.format(
  55.                 "Expected: initialCapacity >= MIN_SIZE."
  56.                 + " Got: initialCapacity = %d", initialCapacity
  57.             ));
  58.         }
  59.         data = (T[]) new Comparable<?>[MIN_SIZE];
  60.     }
  61.  
  62.     @SuppressWarnings("unchecked")
  63.     private MaxPQUnorderedArray(T[] data, int size) {
  64.         T[] newData = (T[]) new Comparable<?>[data.length];
  65.         System.arraycopy(data, 0, newData, 0, data.length);
  66.         this.size = size;
  67.         this.data = newData;
  68.     }
  69.  
  70.     /**
  71.      * Adds an element to the queue.
  72.      * @return true in case the queue is modified as a result of the call.
  73.      */
  74.     @Override
  75.     public boolean offer(T value) {
  76.         grow(1);
  77.         data[size] = value;
  78.         size++;
  79.         nQueueMutations++;
  80.         return true;
  81.     }
  82.  
  83.     /**
  84.      * Adds all of the elements from the specified collection.
  85.      * @return  true in case every element from the collection has been
  86.      *          added to the queue.
  87.      */
  88.     @Override
  89.     public boolean addAll(Collection<? extends T> elements) {
  90.         grow(elements.size());
  91.         int i = 0;
  92.         for (T element : elements) {
  93.             data[size + i] = element;
  94.             i++;
  95.         }
  96.         size += elements.size();
  97.         nQueueMutations++;
  98.         return true;
  99.     }
  100.  
  101.     /**
  102.      * Retrieves, but does not remove, the max value stored in the queue
  103.      * or returns {@code null} in case the queue is empty.
  104.      * This method can be slightly improved by keeping the position
  105.      * of the max element, so that subsequential calls of {@code element} 
  106.      * or {@code remove} would take constant time instead of linear.
  107.      */
  108.     @Override
  109.     public T peek() {
  110.         if (size == 0) {
  111.             return null;
  112.         }
  113.         T max = data[0];
  114.         for (int i = 1; i < size; i++) {
  115.             if (max.compareTo(data[i]) < 0) {
  116.                 max = data[i];
  117.             }
  118.         }
  119.         return max;
  120.     }
  121.  
  122.     /**
  123.      * Retrieves and removes the maximum element of the queue or
  124.      * just retunrls {@code null} in case the queue is empty.
  125.      */
  126.     @Override
  127.     public T poll() {
  128.         if (size == 0) {
  129.             return null;
  130.         }
  131.         int iMax = 0;
  132.         for (int i = 1; i < size; i++) {
  133.             if (data[iMax].compareTo(data[i]) < 0) {
  134.                 iMax = i;
  135.             }
  136.         }
  137.         T max = data[iMax];
  138.         swap(data, iMax, size - 1);
  139.         data[size - 1] = null;
  140.         this.size--;
  141.         shrink();
  142.         nQueueMutations++;
  143.         return max;
  144.     }
  145.  
  146.     /**
  147.      * Removes all elements from the queue.
  148.      */
  149.     @Override
  150.     @SuppressWarnings("unchecked")
  151.     public void clear() {
  152.         size = 0;
  153.         data = (T[]) new Comparable<?>[MIN_SIZE];
  154.         nQueueMutations++;
  155.     }
  156.  
  157.     @Override
  158.     public boolean isEmpty() {
  159.         return size == 0;
  160.     }
  161.  
  162.     @Override
  163.     public int size() {
  164.         return size;
  165.     }
  166.  
  167.     @Override
  168.     public PQIterator iterator() {
  169.         return new PQIterator();
  170.     }
  171.  
  172.     /**
  173.      * Reallocates the memory used to store the elements of the queue
  174.      * in a way to fit next `by` added elements. Grows the length of the
  175.      * array at least 1.5 times. We call this method beforehand the
  176.      * actual insertions of the elements, because it allows us to
  177.      * have fully filled array.
  178.      */
  179.     private void grow(int by) {
  180.         if (size + by > data.length) {
  181.             // keep the length of the array at least MIN_SIZE elements
  182.             // ahead of the number of actual elements stored in the queue
  183.             reallocate(size + by + max(MIN_SIZE, (size + by) / 2));
  184.         }
  185.     }
  186.  
  187.     /**
  188.      * Reallocates the memory used to store the elements of the queue
  189.      * in a way that the array would be at most 25% full.
  190.      */
  191.     private void shrink() {
  192.         if (size == 0) {
  193.             reallocate(MIN_SIZE);
  194.         // the length of the array will be shortened at least twice,
  195.         // so to keep the min-size-invariant the length of the array
  196.         // should be at least of length 2 * MIN_SIZE
  197.         } else if (data.length > 2 * MIN_SIZE
  198.                 && size <= data.length / 4) {
  199.             // make the array that would be 50% full
  200.             reallocate(size + max(MIN_SIZE, size));
  201.         }
  202.     }
  203.  
  204.     /**
  205.      * Changes the size of the array in which the elements are stored.
  206.      */
  207.     @SuppressWarnings("unchecked")
  208.     private void reallocate(int newSize) {
  209.         assert newSize >= size();
  210.  
  211.         Comparable<?>[] newData = new Comparable<?>[newSize];
  212.         System.arraycopy(data, 0, newData, 0, size());
  213.         data = (T[]) newData;
  214.     }
  215.  
  216.     private class PQIterator implements Iterator<T> {
  217.         private final MaxPQUnorderedArray<T> pqCopy;
  218.         private int iLastlyTraversed = -1;
  219.         private int[] initialIndices;
  220.  
  221.         private final int nInitialQueueMutations;
  222.  
  223.         public PQIterator() {
  224.             pqCopy = new MaxPQUnorderedArray<T>(data, size);
  225.             initialIndices = new int[data.length];
  226.             for (int i = 0; i < data.length; i++) {
  227.                 initialIndices[i] = i;
  228.             }
  229.             nInitialQueueMutations = nQueueMutations;
  230.         }
  231.  
  232.         public boolean hasNext() {
  233.             if (nInitialQueueMutations != nQueueMutations) {
  234.                 throw new ConcurrentModificationException(
  235.                     "The queue has been modified."
  236.                 );
  237.             }
  238.             return !pqCopy.isEmpty();
  239.         }
  240.  
  241.         public T next() {
  242.             if (nInitialQueueMutations != nQueueMutations) {
  243.                 throw new ConcurrentModificationException(
  244.                     "The queue has been modified."
  245.                 );
  246.             }
  247.             if (!hasNext()) {
  248.                 throw new NoSuchElementException("The queue is empty");
  249.             }
  250.             int iMax = 0;
  251.             for (int i = 1; i < pqCopy.size; i++) {
  252.                 if (pqCopy.data[iMax].compareTo(pqCopy.data[i]) < 0) {
  253.                     iMax = i;
  254.                 }
  255.             }
  256.             // when an element is removed from the pqCopy, it is
  257.             // swapped with the last element of the array, so
  258.             // we should also swap the indices
  259.             iLastlyTraversed = initialIndices[iMax];
  260.             initialIndices[iMax] = initialIndices[pqCopy.size - 1];
  261.             initialIndices[pqCopy.size - 1] = -1;
  262.  
  263.             return pqCopy.remove();
  264.         }
  265.  
  266.         public void remove() {
  267.             if (nInitialQueueMutations != nQueueMutations) {
  268.                 throw new ConcurrentModificationException(
  269.                     "The queue has been modified."
  270.                 );
  271.             }
  272.             if (iLastlyTraversed == -1) {
  273.                 throw new IllegalStateException();
  274.             }
  275.             if (iLastlyTraversed != size - 1) {
  276.                 // indices to the right from the removed elements
  277.                 // should be shifted
  278.                 for (int i = 0; i < pqCopy.size; i++) {
  279.                     if (initialIndices[i] > iLastlyTraversed) {
  280.                         initialIndices[i]--;
  281.                     }
  282.                 }
  283.                 System.arraycopy(data, iLastlyTraversed + 1, data,
  284.                         iLastlyTraversed, size - iLastlyTraversed - 1);
  285.             }
  286.             data[size - 1] = null;
  287.             size--;
  288.             iLastlyTraversed = -1;
  289.         }
  290.     }
  291.  
  292.     private static void swap(Object[] array, int i, int j) {
  293.         assert rangeCheck(array, i) && rangeCheck(array, j);
  294.  
  295.         if (i != j) {
  296.             Object temp = array[i];
  297.             array[i] = array[j];
  298.             array[j] = temp;
  299.         }
  300.     }
  301.  
  302.     private static boolean rangeCheck(Object[] array, int i) {
  303.         return array != null && i >= 0 && i < array.length;
  304.     }
  305.  
  306.     public static void main(String[] args) {
  307.         MaxPQUnorderedArray<Integer> pq = new MaxPQUnorderedArray<>();
  308.         for (int i = 0; i < 10; i++) {
  309.             pq.add(i);
  310.         }
  311.         Iterator<Integer> iterator = pq.iterator();
  312.         while (iterator.hasNext()) {
  313.             int next = iterator.next();
  314.             System.out.printf("%d ", next);
  315.             if (next == 5 || next == 2 || next == 3) {
  316.                 iterator.remove();
  317.             }
  318.         }
  319.  
  320.         System.out.println();
  321.         for (int i : pq) {
  322.             System.out.printf("%d ", i);
  323.         }
  324.     }
  325. }
Success #stdin #stdout 0.08s 34244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9 8 7 6 5 4 3 2 1 0 
9 8 7 6 4 1 0
https://ideone.com/FC6zAU
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!