Collections Data Structure Java

/*
 *  Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *  
 *    http://www.apache.org/licenses/LICENSE-2.0
 *  
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License. 
 *  
 */
import java.io.Serializable;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
/**
 * A unbounded circular queue based on array.
 * 
 * @author The Apache MINA Project (dev@mina.apache.org)
 * @version $Rev: 762170 $, $Date: 2009-04-06 00:01:18 +0200 (Mon, 06 Apr 2009) $
 */
public class CircularQueue extends AbstractList implements List, Queue, Serializable {
    /** The serialVersionUID : mandatory for serializable classes */
    private static final long serialVersionUID = 3993421269224511264L;
    /** Minimal size fo the underlying attay */
    private static final int DEFAULT_CAPACITY = 4;
    /** The initial capacity of the list */
    private final int initialCapacity;
    
    // XXX: This volatile keyword here is a workaround for SUN Java Compiler bug,
    //      which produces buggy byte code.  I don't event know why adding a volatile
    //      fixes the problem.  Eclipse Java Compiler seems to produce correct byte code.
    private volatile Object[] items;
    private int mask;
    private int first = 0;
    private int last = 0;
    private boolean full;
    private int shrinkThreshold;
    /**
     * Construct a new, empty queue.
     */
    public CircularQueue() {
        this(DEFAULT_CAPACITY);
    }
    
    public CircularQueue(int initialCapacity) {
        int actualCapacity = normalizeCapacity(initialCapacity);
        items = new Object[actualCapacity];
        mask = actualCapacity - 1;
        this.initialCapacity = actualCapacity;
        this.shrinkThreshold = 0;
    }
    /**
     * The capacity must be a power of 2.
     */
    private static int normalizeCapacity(int initialCapacity) {
        int actualCapacity = 1;
        
        while (actualCapacity < initialCapacity) {
            actualCapacity <<= 1;
            if (actualCapacity < 0) {
                actualCapacity = 1 << 30;
                break;
            }
        }
        return actualCapacity;
    }
    /**
     * Returns the capacity of this queue.
     */
    public int capacity() {
        return items.length;
    }
    @Override
    public void clear() {
        if (!isEmpty()) {
            Arrays.fill(items, null);
            first = 0;
            last = 0;
            full = false;
            shrinkIfNeeded();
        }
    }
    @SuppressWarnings("unchecked")
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Object ret = items[first];
        items[first] = null;
        decreaseSize();
        
        if (first == last) {
            first = last = 0;
        }
        shrinkIfNeeded();
        return (E) ret;
    }
    public boolean offer(E item) {
        if (item == null) {
            throw new NullPointerException("item");
        }
        
        expandIfNeeded();
        items[last] = item;
        increaseSize();
        return true;
    }
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) items[first];
    }
    @SuppressWarnings("unchecked")
    @Override
    public E get(int idx) {
        checkIndex(idx);
        return (E) items[getRealIndex(idx)];
    }
    @Override
    public boolean isEmpty() {
        return (first == last) && !full;
    }
    @Override
    public int size() {
        if (full) {
            return capacity();
        }
        
        if (last >= first) {
            return last - first;
        } else {
            return last - first + capacity();
        }
    }
    
    @Override
    public String toString() {
        return "first=" + first + ", last=" + last + ", size=" + size()
                + ", mask = " + mask;
    }
    private void checkIndex(int idx) {
        if (idx < 0 || idx >= size()) {
            throw new IndexOutOfBoundsException(String.valueOf(idx));
        }
    }
    private int getRealIndex(int idx) {
        return (first + idx) & mask;
    }
    private void increaseSize() {
        last = (last + 1) & mask;
        full = first == last;
    }
    private void decreaseSize() {
        first = (first + 1) & mask;
        full = false;
    }
    private void expandIfNeeded() {
        if (full) {
            // expand queue
            final int oldLen = items.length;
            final int newLen = oldLen << 1;
            Object[] tmp = new Object[newLen];
    
            if (first < last) {
                System.arraycopy(items, first, tmp, 0, last - first);
            } else {
                System.arraycopy(items, first, tmp, 0, oldLen - first);
                System.arraycopy(items, 0, tmp, oldLen - first, last);
            }
    
            first = 0;
            last = oldLen;
            items = tmp;
            mask = tmp.length - 1;
            if (newLen >>> 3 > initialCapacity) {
                shrinkThreshold = newLen >>> 3;
            }
        }
    }
    
    private void shrinkIfNeeded() {
        int size = size();
        if (size <= shrinkThreshold) {
            // shrink queue
            final int oldLen = items.length;
            int newLen = normalizeCapacity(size);
            if (size == newLen) {
                newLen <<= 1;
            }
            
            if (newLen >= oldLen) {
                return;
            }
            
            if (newLen < initialCapacity) {
                if (oldLen == initialCapacity) {
                    return;
                } else {
                    newLen = initialCapacity;
                }
            }
            
            Object[] tmp = new Object[newLen];
    
            // Copy only when there's something to copy.
            if (size > 0) {
                if (first < last) {
                    System.arraycopy(items, first, tmp, 0, last - first);
                } else {
                    System.arraycopy(items, first, tmp, 0, oldLen - first);
                    System.arraycopy(items, 0, tmp, oldLen - first, last);
                }
            }
    
            first = 0;
            last = size;
            items = tmp;
            mask = tmp.length - 1;
            shrinkThreshold = 0;
        }
    }
    @Override
    public boolean add(E o) {
        return offer(o);
    }
    @SuppressWarnings("unchecked")
    @Override
    public E set(int idx, E o) {
        checkIndex(idx);
        int realIdx = getRealIndex(idx);
        Object old = items[realIdx];
        items[realIdx] = o;
        return (E) old;
    }
    @Override
    public void add(int idx, E o) {
        if (idx == size()) {
            offer(o);
            return;
        }
        checkIndex(idx);
        expandIfNeeded();
        int realIdx = getRealIndex(idx);
        // Make a room for a new element.
        if (first < last) {
            System
                    .arraycopy(items, realIdx, items, realIdx + 1, last
                            - realIdx);
        } else {
            if (realIdx >= first) {
                System.arraycopy(items, 0, items, 1, last);
                items[0] = items[items.length - 1];
                System.arraycopy(items, realIdx, items, realIdx + 1,
                        items.length - realIdx - 1);
            } else {
                System.arraycopy(items, realIdx, items, realIdx + 1, last
                        - realIdx);
            }
        }
        items[realIdx] = o;
        increaseSize();
    }
    @SuppressWarnings("unchecked")
    @Override
    public E remove(int idx) {
        if (idx == 0) {
            return poll();
        }
        checkIndex(idx);
        int realIdx = getRealIndex(idx);
        Object removed = items[realIdx];
        // Remove a room for the removed element.
        if (first < last) {
            System.arraycopy(items, first, items, first + 1, realIdx - first);
        } else {
            if (realIdx >= first) {
                System.arraycopy(items, first, items, first + 1, realIdx
                        - first);
            } else {
                System.arraycopy(items, 0, items, 1, realIdx);
                items[0] = items[items.length - 1];
                System.arraycopy(items, first, items, first + 1, items.length
                        - first - 1);
            }
        }
        items[first] = null;
        decreaseSize();
        shrinkIfNeeded();
        return (E) removed;
    }
    public E remove() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return poll();
    }
    public E element() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return peek();
    }
}
///////////////////////////////////////////////
/*
 *  Licensed to the Apache Software Foundation (ASF) under one
 *  or more contributor license agreements.  See the NOTICE file
 *  distributed with this work for additional information
 *  regarding copyright ownership.  The ASF licenses this file
 *  to you under the Apache License, Version 2.0 (the
 *  "License"); you may not use this file except in compliance
 *  with the License.  You may obtain a copy of the License at
 *  
 *    http://www.apache.org/licenses/LICENSE-2.0
 *  
 *  Unless required by applicable law or agreed to in writing,
 *  software distributed under the License is distributed on an
 *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *  KIND, either express or implied.  See the License for the
 *  specific language governing permissions and limitations
 *  under the License. 
 *  
 */
package org.apache.mina.util;
import junit.framework.TestCase;
import java.util.Iterator;
/**
 * Tests {@link org.apache.mina.util.CircularQueue}
 * 
 * @author The Apache MINA Project (dev@mina.apache.org)
 * @version $Rev: 755170 $, $Date: 2009-03-17 10:46:58 +0100 (Tue, 17 Mar 2009) $
 */
public class CircularQueueTest extends TestCase {
    private volatile int pushCount;
    private volatile int popCount;
    public void setUp() {
        pushCount = 0;
        popCount = 0;
    }
    public void testRotation() {
        CircularQueue q = new CircularQueue(); // DEFAULT_CAPACITY = 4
        testRotation0(q);
    }
    public void testExpandingRotation() {
        CircularQueue q = new CircularQueue(); // DEFAULT_CAPACITY = 4
        for (int i = 0; i < 10; i++) {
            testRotation0(q);
            // make expansion happen
            int oldCapacity = q.capacity();
            for (int j = q.capacity(); j >= 0; j--) {
                q.offer(new Integer(++pushCount));
            }
            assertTrue(q.capacity() > oldCapacity);
            testRotation0(q);
        }
    }
    private void testRotation0(CircularQueue q) {
        for (int i = 0; i < q.capacity() * 7 / 4; i++) {
            q.offer(new Integer(++pushCount));
            assertEquals(++popCount, q.poll().intValue());
        }
    }
    public void testRandomAddOnQueue() {
        CircularQueue q = new CircularQueue();
        // Create a queue with 5 elements and capacity 8;
        for (int i = 0; i < 5; i++) {
            q.offer(new Integer(i));
        }
        q.add(0, new Integer(100));
        q.add(3, new Integer(200));
        q.add(7, new Integer(300));
        Iterator i = q.iterator();
        assertEquals(8, q.size());
        assertEquals(new Integer(100), i.next());
        assertEquals(new Integer(0), i.next());
        assertEquals(new Integer(1), i.next());
        assertEquals(new Integer(200), i.next());
        assertEquals(new Integer(2), i.next());
        assertEquals(new Integer(3), i.next());
        assertEquals(new Integer(4), i.next());
        assertEquals(new Integer(300), i.next());
        try {
            i.next();
            fail();
        } catch (Exception e) {
            // an exception signifies a successfull test case
            assertTrue(true);            
        }
    }
    public void testRandomAddOnRotatedQueue() {
        CircularQueue q = getRotatedQueue();
        q.add(0, new Integer(100)); // addFirst
        q.add(2, new Integer(200));
        q.add(4, new Integer(300));
        q.add(10, new Integer(400));
        q.add(12, new Integer(500)); // addLast
        Iterator i = q.iterator();
        assertEquals(13, q.size());
        assertEquals(new Integer(100), i.next());
        assertEquals(new Integer(0), i.next());
        assertEquals(new Integer(200), i.next());
        assertEquals(new Integer(1), i.next());
        assertEquals(new Integer(300), i.next());
        assertEquals(new Integer(2), i.next());
        assertEquals(new Integer(3), i.next());
        assertEquals(new Integer(4), i.next());
        assertEquals(new Integer(5), i.next());
        assertEquals(new Integer(6), i.next());
        assertEquals(new Integer(400), i.next());
        assertEquals(new Integer(7), i.next());
        assertEquals(new Integer(500), i.next());
        try {
            i.next();
            fail();
        } catch (Exception e) {
            // an exception signifies a successfull test case
            assertTrue(true);
        }
    }
    public void testRandomRemoveOnQueue() {
        CircularQueue q = new CircularQueue();
        // Create a queue with 5 elements and capacity 8;
        for (int i = 0; i < 5; i++) {
            q.offer(new Integer(i));
        }
        q.remove(0);
        q.remove(2);
        q.remove(2);
        Iterator i = q.iterator();
        assertEquals(2, q.size());
        assertEquals(new Integer(1), i.next());
        assertEquals(new Integer(2), i.next());
        try {
            i.next();
            fail();
        } catch (Exception e) {
            // an exception signifies a successfull test case
            assertTrue(true);
        }
    }
    public void testRandomRemoveOnRotatedQueue() {
        CircularQueue q = getRotatedQueue();
        q.remove(0); // removeFirst
        q.remove(2); // removeLast in the first half
        q.remove(2); // removeFirst in the first half
        q.remove(4); // removeLast
        Iterator i = q.iterator();
        assertEquals(4, q.size());
        assertEquals(new Integer(1), i.next());
        assertEquals(new Integer(2), i.next());
        assertEquals(new Integer(5), i.next());
        assertEquals(new Integer(6), i.next());
        try {
            i.next();
            fail();
        } catch (Exception e) {
            // an exception signifies a successfull test case
            assertTrue(true);            
        }
    }
    
    public void testExpandAndShrink() throws Exception {
        CircularQueue q = new CircularQueue();
        for (int i = 0; i < 1024; i ++) {
            q.offer(i);
        }
        
        assertEquals(1024, q.capacity());
        
        for (int i = 0; i < 512; i ++) {
            q.offer(i);
            q.poll();
        }
        
        assertEquals(2048, q.capacity());
        
        for (int i = 0; i < 1024; i ++) { 
            q.poll();
        }
        
        assertEquals(4, q.capacity());
    }
    private CircularQueue getRotatedQueue() {
        CircularQueue q = new CircularQueue();
        // Ensure capacity: 16
        for (int i = 0; i < 16; i++) {
            q.offer(new Integer(-1));
        }
        q.clear();
        // Rotate it
        for (int i = 0; i < 12; i++) {
            q.offer(new Integer(-1));
            q.poll();
        }
        // Now push items
        for (int i = 0; i < 8; i++) {
            q.offer(new Integer(i));
        }
        return q;
    }
    public static void main(String[] args) {
        junit.textui.TestRunner.run(CircularQueueTest.class);
    }
}