Friday, October 14, 2016

Java Fixed Size Data Structure



http://www.keithschwarz.com/interesting/code/ring-buffer/RingBuffer.java.html
public final class RingBuffer<T> {
    /* The actual ring buffer. */
    private final T[] elements;

    /* The write pointer, represented as an offset into the array. */
    private int offset = 0;

    /* The read pointer is encoded implicitly by keeping track of the number of
     * unconsumed elements.  We can then determine its position by backing up
     * that many positions before the read position.
     */

    private int unconsumedElements = 0;

    /**
     * Constructs a new RingBuffer with the specified capacity, which must be
     * positive.
     *
     * @param size The capacity of the new ring buffer.
     * @throws IllegalArgumentException If the capacity is negative.
     */

    @SuppressWarnings("unchecked")
    public RingBuffer(int size) {
        /* Validate the size. */
        if (size <= 0)
            throw new IllegalArgumentException("RingBuffer capacity must be positive.");

        /* Construct the array to be that size. */
        elements = (T[]) new Object[size];
    }

    /**
     * Appends an element to the ring buffer, blocking until space becomes
     * available.
     *
     * @param elem The element to add to the ring buffer.
     * @throws InterruptedException If the thread is interrupted before the
     *                              insertion completes.
     */

    public synchronized void add(T elem) throws InterruptedException {
        /* Block until the capacity is nonzero.  Otherwise we don't have any
         * space to write.
         */

        while (unconsumedElements == elements.length)
            wait();

        /* Write the element into the next open spot, then advance the write
         * pointer forward a step.
         */

        elements[offset] = elem;
        offset = (offset + 1) % elements.length;

        /* Increase the number of unconsumed elements by one, then notify any
         * threads that are waiting that more data is now available.
         */

        ++unconsumedElements;
        notifyAll();
    }

    /**
     * Returns the maximum capacity of the ring buffer.
     *
     * @return The maximum capacity of the ring buffer.
     */

    public int capacity() {
        return elements.length;
    }

    /**
     * Observes, but does not dequeue, the next available element, blocking
     * until data becomes available.
     *
     * @return The next available element.
     * @throws InterruptedException If the caller is interrupted before data
     *                              becomes available.
     */

    public synchronized T peek() throws InterruptedException {
        /* Wait for data to become available. */
        while (unconsumedElements == 0)
            wait();

        /* Hand back the next value.  The index of this next value is a bit
         * tricky to compute.  We know that there are unconsumedElements
         * elements waiting to be read, and they're contiguously before the
         * write position.  However, the buffer wraps around itself, and so we
         * can't just do a naive subtraction; that might end up giving us a
         * negative index.  To avoid this, we'll use a clever trick in which
         * we'll add to the index the capacity minus the distance.  This value
         * must be positive, since the distance is never greater than the
         * capacity, and if we then wrap this value around using the modulus
         * operator we'll end up with a valid index.  All of this machinery
         * works because
         *
         *                 (x + (n - k)) mod n == (x - k) mod n
         *
         * And Java's modulus operator works best on positive values.
         */

        return elements[(offset + (capacity() - unconsumedElements)) % capacity()];
    }

    /**
     * Removes and returns the next available element, blocking until data
     * becomes available.
     *
     * @return The next available element
     * @throws InterruptedException If the caller is interrupted before data
     *                              becomes available.
     */

    public synchronized T remove() throws InterruptedException {
        /* Use peek() to get the element to return. */
        T result = peek();

        /* Mark that one fewer elements are now available to read. */
        --unconsumedElements;

        /* Because there is more space left, wake up any waiting threads. */
        notifyAll();

        return result;
    }

    /**
     * Returns the number of elements that are currently being stored in the
     * ring buffer.
     *
     * @return The number of elements currently stored in the ring buffer.
     */

    public synchronized int size() {
        return unconsumedElements;
    }

    /**
     * Returns whether the ring buffer is empty.
     *
     * @return Whether the ring buffer is empty.
     */

    public synchronized boolean isEmpty() {
        return size() == 0;
    }
}
http://www.sanfoundry.com/java-program-circular-buffer/

https://commons.apache.org/proper/commons-collections/javadocs/api-3.2.2/org/apache/commons/collections/buffer/CircularFifoBuffer.html
public class BoundedFifoBuffer extends AbstractCollection
        implements Buffer, BoundedCollection, Serializable {
        private transient Object[] elements;
       
        /** Array index of first (oldest) buffer element */
        private transient int start = 0;
        * Index mod maxElements of the array position following the last buffer
        * element.  Buffer elements start at elements[start] and "wrap around"
        * elements[maxElements-1], ending at elements[decrement(end)].
        * For example, elements = {c,a,b}, start=1, end=1 corresponds to
        * the buffer [a,b,c].
        */
       private transient int end = 0;
     
       /** Flag to indicate if the buffer is currently full. */
       private transient boolean full = false;
     
       /** Capacity of the buffer */
       private final int maxElements;
       public int size() {
           int size = 0;

           if (end &lt; start) {
               size = maxElements - start + end;
           } else if (end == start) {
               size = (full ? maxElements : 0);
           } else {
               size = end - start;
           }

           return size;
       }
       public boolean isEmpty() {
           return size() == 0;
       }
       public boolean isFull() {
           return size() == maxElements;
       }
       public boolean add(Object element) {
           if (null == element) {
               throw new NullPointerException("Attempted to add null object to buffer");
           }

           if (full) {
               throw new BufferOverflowException("The buffer cannot hold more than " + maxElements + " objects.");
           }

           elements[end++] = element;

           if (end &gt;= maxElements) {
               end = 0;
           }

           if (end == start) {
               full = true;
           }

           return true;
       }
       public Object get() {
           if (isEmpty()) {
               throw new BufferUnderflowException("The buffer is already empty");
           }

           return elements[start];
       }
       public Object remove() {
           if (isEmpty()) {
               throw new BufferUnderflowException("The buffer is already empty");
           }

           Object element = elements[start];

           if (null != element) { //\\
               elements[start++] = null;

               if (start &gt;= maxElements) {
                   start = 0;
               }

               full = false;
           }

           return element;
       }                                    
       private int increment(int index) {
           index++;
           if (index &gt;= maxElements) {
               index = 0;
           }
           return index;
       }
       private int decrement(int index) {
           index--;
           if (index &lt; 0) {
               index = maxElements - 1;
           }
           return index;
       }
       public Iterator iterator() {
           return new Iterator() {

               private int index = start;
               private int lastReturnedIndex = -1;
               private boolean isFirst = full;

               public boolean hasNext() {
                   return isFirst || (index != end);                  
               }
               public Object next() {
                   if (!hasNext()) {
                       throw new NoSuchElementException();
                   }
                   isFirst = false;
                   lastReturnedIndex = index;
                   index = increment(index);
                   return elements[lastReturnedIndex];
               }

               public void remove() {
                   if (lastReturnedIndex == -1) {
                       throw new IllegalStateException();
                   }

                   // First element can be removed quickly
                   if (lastReturnedIndex == start) {
                       BoundedFifoBuffer.this.remove();
                       lastReturnedIndex = -1;
                       return;
                   }

                   int pos = lastReturnedIndex + 1;
                   if (start &lt; lastReturnedIndex && pos &lt; end) {
                       // shift in one part
                       System.arraycopy(elements, pos, elements,
                               lastReturnedIndex, end - pos);
                   } else {
                       // Other elements require us to shift the subsequent elements
                       while (pos != end) {
                           if (pos &gt;= maxElements) {
                               elements[pos - 1] = elements[0];
                               pos = 0;
                           } else {
                               elements[decrement(pos)] = elements[pos];
                               pos = increment(pos);
                           }
                       }
                   }

                   lastReturnedIndex = -1;
                   end = decrement(end);
                   elements[end] = null;
                   full = false;
                   index = decrement(index);
               }

           };
       }
 }
             
http://tutorials.jenkov.com/java-performance/ring-buffer.html
Ring buffers are especially useful when you need a hard upper bound for how much data can be in the ring buffer (in the queue).
If you don't want an upper bound on your queue structure, perhaps you should be using a linked list, or a ring buffer that can resize itself (allocate a new, bigger array when it is full, and move all elements to that array).

One way to keep track of write position, read position and the number of elements in the ring buffer is to use a write position and a fill count. The write position marks the next position in the ring buffer to write an element to. The fill count tells how many elements are currently stored in the buffer.
When writing elements to the ring buffer it just has to check the fill count to see if it is full or not. If it is not full the element can be inserted at the write position and the write position advanced to the next free slot.
Similarly, when reading elements from the ring buffer it just has to check the fill count to see if the ring buffer is empty. The read position is calculated by subtracting the fill count from the write position. If the result of that calculation is negative, the write position has wrapped around, and you need to add the size of the buffer (array) to the read position to get the correct read position.
Below is a ring buffer implementation that uses a fill count. Notice that it does not track the read position explicitly, but calculates the read position based on the write position and the fill count. Notice also, that the fill count field is called available (not fillCount).
public class RingBufferFillCount {
    public Object[] elements = null;

    private int capacity  = 0;
    private int writePos  = 0;
    private int available = 0;

    public RingBufferFillCount(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public void reset() {
        this.writePos = 0;
        this.available = 0;
    }

    public int capacity() { return this.capacity; }
    public int available(){ return this.available; }

    public int remainingCapacity() {
        return this.capacity - this.available;
    }

    public boolean put(Object element){

        if(available < capacity){
            if(writePos >= capacity){
                writePos = 0;
            }
            elements[writePos] = element;
            writePos++;
            available++;
            return true;
        }

        return false;
    }

    public Object take() {
        if(available == 0){
            return null;
        }
        int nextSlot = writePos - available;
        if(nextSlot < 0){
            nextSlot += capacity;
        }
        Object nextObj = elements[nextSlot]; elements[nextSlot]=null;

        available--;
        return nextObj;
    }
}

Ring Buffer Using Flip Marker

Another option to keep track of read position, write position and how many elements are in the buffer, is to simply keep a read position in addition to the write position.
How many elements are in the buffer is calculated based on the write and read position. How the calculation looks depends on whether the write position has flipped (wrapped around) or not.
If the write position has not wrapped around you can simply subtract the read position from the write position to know how many elements are in the buffer. If the write position has wrapped around (flipped) then the available space is equal to the capacity minus the read position plus the write position.
To keep track of whether the write position has flipped or not a special "flip marker" is used. That is where the name of the implementation comes from. Actually, in most cases you could just check if the write position is larger or smaller than the read position to detect if the write position has wrapped around. But, that doesn't work when write position and read position are equal (the ring buffer is either completely full or completely empty).
public class RingBufferFlipMarker {

    public Object[] elements = null;

    public int capacity = 0;
    public int writePos = 0;
    public int readPos  = 0;
    public boolean flipped = false;   //the flip marker

    public RingBufferFlipMarker(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public void reset() {
        this.writePos = 0;
        this.readPos  = 0;
        this.flipped  = false;
    }

    public int available() {
        if(!flipped){
            return writePos - readPos;
        }
        return capacity - readPos + writePos;
    }

    public int remainingCapacity() {
        if(!flipped){
            return capacity - writePos;
        }
        return readPos - writePos;
    }

    public boolean put(Object element){
        if(!flipped){
            if(writePos == capacity){
                writePos = 0;
                flipped = true;

                if(writePos < readPos){
                    elements[writePos++] = element;
                    return true;
                } else {
                    return false;
                }
            } else {
                elements[writePos++] = element;
                return true;
            }
        } else {
            if(writePos < readPos ){
                elements[writePos++] = element;
                return true;
            } else {
                return false;
            }
        }
    }


    public Object take() {
        if(!flipped){
            if(readPos < writePos){
                return elements[readPos++];
            } else {
                return null;
            }
        } else {
            if(readPos == capacity){
                readPos = 0;
                flipped = false;

                if(readPos < writePos){
                    return elements[readPos++];
                } else {
                    return null;
                }
            } else {
                return elements[readPos++];
            }
        }
    }
}

Ring Buffer Using Fill Count - Including Batch Operations
public class RingBufferFillCount {
    public Object[] elements = null;

    public int capacity  = 0;
    public int writePos  = 0;
    public int available = 0;

    public RingBufferFillCount(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public void reset() {
        this.writePos = 0;
        this.available = 0;
    }

    public int remainingCapacity() {
        return this.capacity - this.available;
    }



    public boolean put(Object element){

        if(available < capacity){
            if(writePos >= capacity){
                writePos = 0;
            }
            elements[writePos] = element;
            writePos++;
            available++;
            return true;
        }

        return false;
    }

    public int put(Object[] newElements){
        return put(newElements, newElements.length);
    }

    public int put(Object[] newElements, int length){
        int readPos = 0;
        if(this.writePos > this.available){
            //space above writePos is all empty

            if(length <= this.capacity - this.writePos){
                //space above writePos is sufficient to insert batch

                for(;  readPos < length; readPos++){
                    this.elements[this.writePos++] = newElements[readPos];
                }
                this.available += readPos;
                return length;

            } else {
                //both space above writePos and below writePos is necessary to use
                //to insert batch.

                int lastEmptyPos = writePos - available;

                for(; this.writePos < this.capacity; this.writePos++){
                    this.elements[this.writePos] = newElements[readPos++];
                }

                //fill into bottom of array too.
                this.writePos = 0;

                int endPos = Math.min(length - readPos, capacity - available - readPos);
                for(;this.writePos < endPos; this.writePos++){
                    this.elements[this.writePos] = newElements[readPos++];
                }
                this.available += readPos;
                return readPos;
            }
        } else {
            int endPos = this.capacity - this.available + this.writePos;

            for(; this.writePos < endPos; this.writePos++){
                this.elements[this.writePos] = newElements[readPos++];
            }
            this.available += readPos;

            return readPos;
        }

    }


    public Object take() {
        if(available == 0){
            return null;
        }
        int nextSlot = writePos - available;
        if(nextSlot < 0){
            nextSlot += capacity;
        }
        Object nextObj = elements[nextSlot];
        available--;
        return nextObj;
    }


    public int take(Object[] into){
        return take(into, into.length);
    }


    public int take(Object[] into, int length){
        int intoPos = 0;

        if(available <= writePos){
            int nextPos= writePos - available;
            int endPos   = nextPos + Math.min(available, length);

            for(;nextPos < endPos; nextPos++){
                into[intoPos++] = this.elements[nextPos];
            }
            this.available -= intoPos;
            return intoPos;
        } else {
            int nextPos = writePos - available + capacity;

            int leftInTop = capacity - nextPos;
            if(length <= leftInTop){
                //copy directly
                for(; intoPos < length; intoPos++){
                    into[intoPos] = this.elements[nextPos++];
                }
                this.available -= length;
                return length;

            } else {
                //copy top
                for(; nextPos < capacity; nextPos++){
                    into[intoPos++] = this.elements[nextPos];
                }

                //copy bottom - from 0 to writePos
                nextPos = 0;
                int leftToCopy = length - intoPos;
                int endPos = Math.min(writePos, leftToCopy);

                for(;nextPos < endPos; nextPos++){
                    into[intoPos++] = this.elements[nextPos];
                }

                this.available -= intoPos;

                return intoPos;
            }
        }
    }
}

Ring Buffer Using Flip Marker - Including Batch Operations
public class RingBufferFlip {

    public Object[] elements = null;

    public int capacity = 0;
    public int writePos = 0;
    public int readPos  = 0;
    public boolean flipped = false;

    public RingBufferFlip(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
    }

    public void reset() {
        this.writePos = 0;
        this.readPos  = 0;
        this.flipped  = false;
    }

    public int available() {
        if(!flipped){
            return writePos - readPos;
        }
        return capacity - readPos + writePos;
    }

    public int remainingCapacity() {
        if(!flipped){
            return capacity - writePos;
        }
        return readPos - writePos;
    }

    public boolean put(Object element){
        if(!flipped){
            if(writePos == capacity){
                writePos = 0;
                flipped = true;

                if(writePos < readPos){
                    elements[writePos++] = element;
                    return true;
                } else {
                    return false;
                }
            } else {
                elements[writePos++] = element;
                return true;
            }
        } else {
            if(writePos < readPos ){
                elements[writePos++] = element;
                return true;
            } else {
                return false;
            }
        }
    }

    public int put(Object[] newElements, int length){
        int newElementsReadPos = 0;
        if(!flipped){
            //readPos lower than writePos - free sections are:
            //1) from writePos to capacity
            //2) from 0 to readPos

            if(length <= capacity - writePos){
                //new elements fit into top of elements array - copy directly
                for(; newElementsReadPos < length; newElementsReadPos++){
                    this.elements[this.writePos++] = newElements[newElementsReadPos];
                }

                return newElementsReadPos;
            } else {
                //new elements must be divided between top and bottom of elements array

                //writing to top
                for(;this.writePos < capacity; this.writePos++){
                    this.elements[this.writePos] = newElements[newElementsReadPos++];
                }

                //writing to bottom
                this.writePos = 0;
                this.flipped  = true;
                int endPos = Math.min(this.readPos, length - newElementsReadPos);
                for(; this.writePos < endPos; this.writePos++){
                    this.elements[writePos] = newElements[newElementsReadPos++];
                }


                return newElementsReadPos;
            }

        } else {
            //readPos higher than writePos - free sections are:
            //1) from writePos to readPos

            int endPos = Math.min(this.readPos, this.writePos + length);

            for(; this.writePos < endPos; this.writePos++){
                this.elements[this.writePos] = newElements[newElementsReadPos++];
            }

            return newElementsReadPos;
        }
    }


    public Object take() {
        if(!flipped){
            if(readPos < writePos){
                return elements[readPos++];
            } else {
                return null;
            }
        } else {
            if(readPos == capacity){
                readPos = 0;
                flipped = false;

                if(readPos < writePos){
                    return elements[readPos++];
                } else {
                    return null;
                }
            } else {
                return elements[readPos++];
            }
        }
    }

    public int take(Object[] into, int length){
        int intoWritePos = 0;
        if(!flipped){
            //writePos higher than readPos - available section is writePos - readPos

            int endPos = Math.min(this.writePos, this.readPos + length);
            for(; this.readPos < endPos; this.readPos++){
                into[intoWritePos++] = this.elements[this.readPos];
            }
            return intoWritePos;
        } else {
            //readPos higher than writePos - available sections are
            //top + bottom of elements array

            if(length <= capacity - readPos){
                //length is lower than the elements available at the top
                //of the elements array - copy directly
                for(; intoWritePos < length; intoWritePos++){
                    into[intoWritePos] = this.elements[this.readPos++];
                }

                return intoWritePos;
            } else {
                //length is higher than elements available at the top of the elements array
                //split copy into a copy from both top and bottom of elements array.

                //copy from top
                for(; this.readPos < capacity; this.readPos++){
                    into[intoWritePos++] = this.elements[this.readPos];
                }

                //copy from bottom
                this.readPos = 0;
                this.flipped = false;
                int endPos = Math.min(this.writePos, length - intoWritePos);
                for(; this.readPos < endPos; this.readPos++){
                    into[intoWritePos++] = this.elements[this.readPos];
                }

                return intoWritePos;
            }
        }
    }
}

http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html
Traditionally, the following trick is used to to break the ambiguity:
    • We assume that the circular buffer is full when:
        • There is one empty slot left in the circular buffer:
      Example:

In other words, we use the following test to check if the circular buffer is full:
        read pointer == ( write pointer + 1 ) % (buf.length)   
       public class  ArrayQueue  implements Queue
       {
          public double[] buf;          // Circular buffer
          public int      read, write;  // read and write pointers
        
          // Constructor
          public ArrayQueue(int size)
          {
         buf = new double[size];    // Create array for circular buffer
        
         read = 0;                  // Initialized read & write pointers
         write = 0;
          }
        
          /* ====================================================
          enqueue(x ):
         ==================================================== */
          public void enqueue( double x )   throws Exception
          {
         if ( read == ( write + 1 ) % (buf.length) )  // Full...
         {
            throw new Exception("Queue is full");
         }
        
         buf[write] = x;                 // Store x in buf at write pointer
         write = (write+1)%(buf.length); // Advance the write pointer
          }
        
          /* ====================================================
          dequeue():
         ==================================================== */
          public double dequeue( ) throws Exception
          {
         double r;   // Variable used to save the return value
        
         if ( read == write )
         {
            throw new Exception("Queue is empty");
         }
        
         r = buf[read];                 // Save return value
         read = (read+1)%(buf.length);  // Advance the read pointer
        
         return r;
          }
       }
http://fabian-kostadinov.github.io/2014/11/25/implementing-a-fixed-length-fifo-queue-in-java/
public interface Queue<E> {

    public boolean add(E e);
    public E element();
    public boolean offer(E e);
    public E peek();
    public E poll();
    public E remove();
    
}
public class NumberFixedLengthFifoQueue implements Queue<Number> {

    protected Number[] ring;
    protected int index;
    
    /**
     * @param initialValues contains the ring's initial values.
     * The "oldest" value in the queue is expected to reside in
     * position 0, the newest one in position length-1.
     */
    public NumberFixedLengthFifoQueue(Number[] initialValues) {
        // This is a little ugly, but there are no
        // generic arrays in Java
        ring = new Number[initialValues.length];
        
        // We don't want to work on the original data
        System.arraycopy(initialValues, 0, ring, 0, initialValues.length);
        
        // The next time we add something to the queue,
        // the oldest element should be replaced
        index = 0;
    }

    @Override
    public boolean add(Number newest) {
        return offer(newest);
    }

    @Override
    public Number element() {
        return ring[getHeadIndex()];
    }

    @Override
    public boolean offer(Number newest) {
        Number oldest = ring[index];
        ring[index] = newest;
        incrIndex();
        return true;      
    }

    @Override
    public Number peek() {
        return ring[getHeadIndex()];
    }

    @Override
    public Number poll() {
        throw new IllegalStateException("The poll method is not available for NumberFixedLengthFifoQueue.");
    }

    @Override
    public Number remove() {
        throw new IllegalStateException("The remove method is not available for NumberFixedLengthFifoQueue.");
    }

    @Override
    public Number get(int absIndex) throws IndexOutOfBoundsException {
        if (absIndex >= ring.length) {
            throw new IndexOutOfBoundsException("Invalid index " + absIndex);
        }
        int i = index + absIndex;
        if (i >= ring.length) {
            i -= ring.length;
        }
        return ring[i];
    }
    
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        for (int i = index, n = 0; n < ring.length; i = nextIndex(i), n++) {
            sb.append(ring[i]);
            if (n+1 < ring.length) { sb.append(", "); } 
        }
        return sb.append("]").toString();
    }
    
    protected void incrIndex() {
        index = nextIndex(index);
    }
    
    protected int nextIndex(int current) {
        if (current + 1 >= ring.length) { return 0; }
        else return current + 1;
    }

    protected int previousIndex(int current) {
        if (current - 1 < 0) { return ring.length - 1; }
        else return current - 1;
    }
    
    protected int getHeadIndex() {
        if (index == 0) { return ring.length-1; }
        else return index-1;
    }    
}
The queue "rolls" through the ring. Adding a new element at the head of the queue automatically removes the oldest element in the queue - no copying of arrays or resetting of object references required. Unlike with linked lists we can actually access each element in the ring directly with the get method. Finally, we can create a subclass of our queue object which will graciously roll over as new values are added into the queue/ring.
public class RollingMovingAverage extends NumberFixedLengthFifoQueue {

    private float maNumerator;
    private float maValue;
    
    public RollingMovingAverage(Number[] initialValues) {
        super(initialValues);
        maNumerator = 0.0f;
        maValue = 0.0f;
        initialize();
    }
    
    public float getValue() {
        return maValue;
    }
    
    @Override
    public boolean add(Number newest) {
        return this.offer(newest);
    }
    
    @Override
    public boolean offer(Number newest) {
        maNumerator -= ring[index].floatValue();
        
        boolean res = super.offer(newest);
        
        maNumerator += ring[getHeadIndex()].floatValue();
        maValue = maNumerator / (float) ring.length;
        
        return res;
    }
    
    private void initialize() {
        for (int i = previousIndex(index), n = 0; n < ring.length; i = previousIndex(i), n++) {
            maNumerator += ring[i].floatValue();
        }
        maValue = maNumerator / (float) ring.length;
    }    
}

http://algs4.cs.princeton.edu/13stacks/FixedCapacityStack.java.html


public class ArrayDeque&lt;E&gt; extends AbstractCollection&lt;E&gt;
                           implements Deque&lt;E&gt;, Cloneable, Serializable
{
  transient Object[] elements; // non-private to simplify nested class access
  // The index of the element at the head of the deque (which is the
  // element that would be removed by remove() or pop()); or an
  // arbitrary number equal to tail if the deque is empty.)
  transient int head;
  // The index at which the next element would be added to the tail
  transient int tail;
  public void addFirst(E e) {
      if (e == null)
          throw new NullPointerException();
      elements[head = (head - 1) & (elements.length - 1)] = e;
      if (head == tail)
          doubleCapacity();
  }
  public void addLast(E e) {
      if (e == null)
          throw new NullPointerException();
      elements[tail] = e;
      if ( (tail = (tail + 1) & (elements.length - 1)) == head)
          doubleCapacity();
  }

  public E pollFirst() {
      int h = head;
      @SuppressWarnings("unchecked")
      E result = (E) elements[h];
      // Element is null if deque empty
      if (result == null)
          return null;
      elements[h] = null;     // Must null out slot
      head = (h + 1) & (elements.length - 1);
      return result;
  }
  public E pollLast() {
      int t = (tail - 1) & (elements.length - 1);
      @SuppressWarnings("unchecked")
      E result = (E) elements[t];
      if (result == null)
          return null;
      elements[t] = null;
      tail = t;
      return result;
  }
  public E getFirst() {
      @SuppressWarnings("unchecked")
      E result = (E) elements[head];
      if (result == null)
          throw new NoSuchElementException();
      return result;
  }
  public E getLast() {
      @SuppressWarnings("unchecked")
      E result = (E) elements[(tail - 1) & (elements.length - 1)];
      if (result == null)
          throw new NoSuchElementException();
      return result;
  }
}

https://github.com/frohoff/jdk8u-jdk/blob/master/src/share/classes/com/sun/java/util/jar/pack/FixedList.java
https://www.usna.edu/Users/cs/aviv/classes/ic312/f16/hw/01/demo/FixedList.java.html


Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts