Circular Queue extends AbstractList : Queue « Collections Data Structure « Java

Java
1. 2D Graphics GUI
2. 3D
3. Advanced Graphics
4. Ant
5. Apache Common
6. Chart
7. Class
8. Collections Data Structure
9. Data Type
10. Database SQL JDBC
11. Design Pattern
12. Development Class
13. EJB3
14. Email
15. Event
16. File Input Output
17. Game
18. Generics
19. GWT
20. Hibernate
21. I18N
22. J2EE
23. J2ME
24. JDK 6
25. JNDI LDAP
26. JPA
27. JSP
28. JSTL
29. Language Basics
30. Network Protocol
31. PDF RTF
32. Reflection
33. Regular Expressions
34. Scripting
35. Security
36. Servlets
37. Spring
38. Swing Components
39. Swing JFC
40. SWT JFace Eclipse
41. Threads
42. Tiny Application
43. Velocity
44. Web Services SOA
45. XML
Java Tutorial
Java Source Code / Java Documentation
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java » Collections Data Structure » QueueScreenshots 
Circular Queue extends AbstractList
  
/*
 *  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<E> extends AbstractList<E> implements List<E>, Queue<E>, 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 = << 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[firstnull;
        decreaseSize();
        
        if (first == last) {
            first = last = 0;
        }

        shrinkIfNeeded();
        return (Eret;
    }

    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 (Eitems[first];
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int idx) {
        checkIndex(idx);
        return (Eitems[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 < || 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 >>> > 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 (Eold;
    }

    @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[firstnull;
        decreaseSize();

        shrinkIfNeeded();
        return (Eremoved;
    }

    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<Integer> q = new CircularQueue<Integer>()// DEFAULT_CAPACITY = 4
        testRotation0(q);
    }

    public void testExpandingRotation() {
        CircularQueue<Integer> q = new CircularQueue<Integer>()// 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<Integer> q) {
        for (int i = 0; i < q.capacity() 4; i++) {
            q.offer(new Integer(++pushCount));
            assertEquals(++popCount, q.poll().intValue());
        }
    }

    public void testRandomAddOnQueue() {
        CircularQueue<Integer> q = new CircularQueue<Integer>();
        // Create a queue with 5 elements and capacity 8;
        for (int i = 0; i < 5; i++) {
            q.offer(new Integer(i));
        }

        q.add(0new Integer(100));
        q.add(3new Integer(200));
        q.add(7new Integer(300));

        Iterator<Integer> 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<Integer> q = getRotatedQueue();

        q.add(0new Integer(100))// addFirst
        q.add(2new Integer(200));
        q.add(4new Integer(300));
        q.add(10new Integer(400));
        q.add(12new Integer(500))// addLast

        Iterator<Integer> 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<Integer> q = new CircularQueue<Integer>();

        // 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<Integer> 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<Integer> 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<Integer> 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<Integer> q = new CircularQueue<Integer>();
        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<Integer> getRotatedQueue() {
        CircularQueue<Integer> q = new CircularQueue<Integer>();

        // 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);
    }
}

   
    
  
Related examples in the same category
1. Priority queuePriority queue
2. Queue data structureQueue data structure
3. Convert a Queue to a List
4. Create a queue using LinkedList class
5. Simple Queue (FIFO) based on LinkedList
6. The Generic Queue Class
7. Blocking Queue
8. Circular Queue
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.