fork(1) download
copy 
  1. import java.util.Arrays;
  2. import java.util.NoSuchElementException;
  3.  
  4. /**
  5.  * Deque (double-ended queue) implementation which uses an array to store
  6.  * references to the objects added to the deque.
  7.  */
  8. class Deque<T> {
  9.     private Object[] data = new Object[1];
  10.     // index of the most lastly added object (-1 if no object has been added)
  11.     private int lo = -1;
  12.     // index of the most recently added object
  13.     private int hi = -1;
  14.  
  15.     public void addFront(T value) {
  16.         if (lo == -1) {
  17.             data[0] = value;
  18.             lo = 0;
  19.             hi = 0;
  20.         } else {
  21.             changeArraySizeIfNeeded();
  22.             lo = dec(lo);
  23.             data[lo] = value;
  24.         }
  25.         System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("addFront(%s):", value), Arrays.toString(data), lo, hi);
  26.     }
  27.  
  28.     public void addBack(T value) {
  29.         if (hi == -1) {
  30.             data[0] = value;
  31.             lo = 0;
  32.             hi = 0;
  33.         } else {
  34.             changeArraySizeIfNeeded();
  35.             hi = inc(hi);
  36.             data[hi] = value;
  37.         }
  38.         System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("addBack(%s):", value), Arrays.toString(data), lo, hi);
  39.     }
  40.  
  41.     public T popFront() {
  42.         if (lo == -1) {
  43.             throw new NoSuchElementException("The deque is empty");
  44.         }
  45.  
  46.         T value = (T) data[lo];
  47.         data[lo] = null;
  48.         if (lo == hi) {
  49.             lo = -1;
  50.             hi = -1;
  51.         } else {
  52.             lo = inc(lo);
  53.         }
  54.         changeArraySizeIfNeeded();
  55.         System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("popFront() = %s:", value), Arrays.toString(data), lo, hi);
  56.         return value;
  57.     }
  58.  
  59.     public T popBack() {
  60.         if (hi == -1) {
  61.             throw new NoSuchElementException("The deque is empty");
  62.         }
  63.  
  64.         T value = (T) data[hi];
  65.         data[hi] = null;
  66.         if (lo == hi) {
  67.             lo = -1;
  68.             hi = -1;
  69.         } else {
  70.             hi = dec(hi);
  71.         }
  72.         changeArraySizeIfNeeded();
  73.         System.out.printf("%-20s %s lo = %d hi = %d\n", String.format("popBack() = %s:", value), Arrays.toString(data), lo, hi);
  74.         return value;
  75.     }
  76.  
  77.     public T peekFront() {
  78.         if (lo == -1) {
  79.             throw new NoSuchElementException("The deque is empty");
  80.         }
  81.         return (T) data[lo];
  82.     }
  83.  
  84.     public T peekBack() {
  85.         if (hi == -1) {
  86.             throw new NoSuchElementException("The deque is empty");
  87.         }
  88.         return (T) data[hi];
  89.     }
  90.  
  91.     /**
  92.      * Decrements the given index in a cyclic manner (modulo data.length)
  93.      */
  94.     private int dec(int i) {
  95.         i--;
  96.         if (i < 0) {
  97.             i += data.length;
  98.         }
  99.         return i;
  100.     }
  101.  
  102.     /**
  103.      * Increments the given index in a cyclic manner (modulo data.length)
  104.      */
  105.     private int inc(int i) {
  106.         return ++i % data.length;
  107.     }
  108.  
  109.     /**
  110.      * Doubles the size of the `data` array in case it is full and
  111.      * decreases the size of `data` array twice if it is filled
  112.      * at one quarter or less
  113.      */
  114.     private void changeArraySizeIfNeeded() {
  115.         int pureDataLength = lo < 0 ?
  116.                 0 :
  117.                 moduloDistance(lo, hi, data.length);
  118.  
  119.         if (pureDataLength == data.length) {
  120.             data = resizeArray(data, lo, hi, 2 * data.length);
  121.             hi = pureDataLength - 1;
  122.             lo = 0;
  123.         } else if (pureDataLength != 0 && data.length / pureDataLength >= 4) {
  124.             data = resizeArray(data, lo, hi, data.length / 2);
  125.             hi = pureDataLength - 1;
  126.             lo = 0;
  127.         } else if (pureDataLength == 0) {
  128.             data = new Object[1];
  129.         }
  130.     }
  131.  
  132.     /**
  133.      * Computes the distance between `lo` and `hi` as if
  134.      * they were put into a cyclic array of size `n`
  135.      */
  136.     private static int moduloDistance(int lo, int hi, int n) {
  137.         assert lo >= 0 && hi >= 0;
  138.  
  139.         return lo <= hi ?
  140.             hi - lo + 1 :
  141.             n - lo + hi + 1;
  142.     }
  143.  
  144.     /**
  145.      * Copies the given array into a new one of the {@code newSize} size
  146.      * @param src the source array
  147.      * @param lo points to the first element in the sequence to be copied
  148.      * @param hi points to the last element in the sequence to be copied.
  149.      *           It is not necessary for `lo` to be less, than `hi`:
  150.      *           this method copies the data from the `src` as if it would be cyclic
  151.      * @param newSize size of the resulting array
  152.      */
  153.     private static Object[] resizeArray(Object[] src, int lo, int hi, int newSize) {
  154.         assert newSize >= 0;
  155.         assert moduloDistance(lo, hi, src.length) <= newSize;
  156.  
  157.         Object[] resizedArray = new Object[newSize];
  158.         if (lo <= hi) {
  159.             System.arraycopy(src, lo, resizedArray, 0, hi - lo + 1);
  160.         } else {
  161.             System.arraycopy(src, lo, resizedArray, 0, src.length - lo);
  162.             System.arraycopy(src, 0, resizedArray, src.length - lo, hi + 1);
  163.         }
  164.         return resizedArray;
  165.     }
  166.  
  167.     public static void main(String[] args) {
  168.         Deque<Integer> deque = new Deque<>();
  169.         for (int i = 3; i >= 0; i--) {
  170.             deque.addFront(i);
  171.         }
  172.         for (int i = 4; i <= 7; i++) {
  173.             deque.addBack(i);
  174.         }
  175.         System.out.println();
  176.         for (int i = 0; i < 4; i++) {
  177.             deque.popFront();
  178.             deque.popBack();
  179.         }
  180.         deque.addBack(1);
  181.         deque.addFront(0);
  182.     }
  183. }
Success #stdin #stdout 0.17s 34356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
addFront(3):         [3] lo = 0 hi = 0
addFront(2):         [3, 2] lo = 1 hi = 0
addFront(1):         [2, 3, null, 1] lo = 3 hi = 1
addFront(0):         [2, 3, 0, 1] lo = 2 hi = 1
addBack(4):          [0, 1, 2, 3, 4, null, null, null] lo = 0 hi = 4
addBack(5):          [0, 1, 2, 3, 4, 5, null, null] lo = 0 hi = 5
addBack(6):          [0, 1, 2, 3, 4, 5, 6, null] lo = 0 hi = 6
addBack(7):          [0, 1, 2, 3, 4, 5, 6, 7] lo = 0 hi = 7

popFront() = 0:      [null, 1, 2, 3, 4, 5, 6, 7] lo = 1 hi = 7
popBack() = 7:       [null, 1, 2, 3, 4, 5, 6, null] lo = 1 hi = 6
popFront() = 1:      [null, null, 2, 3, 4, 5, 6, null] lo = 2 hi = 6
popBack() = 6:       [null, null, 2, 3, 4, 5, null, null] lo = 2 hi = 5
popFront() = 2:      [null, null, null, 3, 4, 5, null, null] lo = 3 hi = 5
popBack() = 5:       [3, 4, null, null] lo = 0 hi = 1
popFront() = 3:      [4, null] lo = 0 hi = 0
popBack() = 4:       [null] lo = -1 hi = -1
addBack(1):          [1] lo = 0 hi = 0
addFront(0):         [1, 0] lo = 1 hi = 0
https://ideone.com/nsAVWx
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!