Quadcap Embeddable Database

com/quadcap/util/collections/ArrayQueue.java

Go to the documentation of this file.

package com.quadcap.util.collections;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

/**
 * Implements the Queue interface using a growable array.
 *
 * @author Stan Bailes
 */
public class ArrayQueue implements Queue {
    int                         head            = 0;
    int                         tail            = 0;
    int                         capacity        = 0;
    Object[]                    queue           = null;

    /**
     * Create an empty Array queue with unbounded capacity
     */
    public ArrayQueue() {
        this(0, -1);
    }

    /**
     * Create an empty queue with an initial capacity
     */
    public ArrayQueue(int capacity) {
        this(0, capacity);
    }

    /**
     * Create an ArrayQueue with an initial capacity.
     */
    public ArrayQueue(int initialSize, int capacity) {
        this.capacity = capacity;
        this.queue = new Object[initialSize + 1];
    }
    
    /**
     * Specify the maximum capacity of this queue, -1 means unbounded.
     *
     * @param capacity the new capacity of the queue, or -1 to specify a
     *          queue of unlimited size.
     */
    public final void setCapacity(int capacity) {
        if (capacity < size()) {
            throw new RuntimeException("can't set capacity less than size");
        }
        if (capacity < queue.length) {
            resize(size() + 1);
        }
        this.capacity = capacity;
    }
    
    /**
     * Return the number of items in the queue.
     * @return the queue's size
     */
    public final int size() {
        int ret = 0;
        if (head > tail) {
            ret = head - tail;
        } else if (head < tail) {
            ret = queue.length - tail + head;
        }
        return ret;
    }
    
    /**
     * Add an object to the front of the queue.
     *
     * @param obj the object to add
     */
    public final void pushFront(Object obj) {
        addFront(obj);
    }
    
    public final void addFront(Object obj) {
        checkSizeForAdd();
        queue[head++] = obj;
        if (head == queue.length) head = 0;
    }

    /**
     * Add an object to the back of the queue.
     * @param obj the object to add
     */
    public final void pushBack(Object obj) {
        addBack(obj);
    }
    
    public final void addBack(Object obj) {
        checkSizeForAdd();
        if (--tail < 0) tail = queue.length - 1;
        queue[tail] = obj;
    }

    /**
     * Access the object at the front of the queue.  Return null
     * if the queue is empty.
     *
     * @return the item at the head of the queue
     */
    public final Object head() {
        Object ret = null;
        if (size() > 0) {
            ret = queue[head > 0 ? head - 1 : queue.length - 1];
        }
        return ret;
    }

    /**
     * Access the object at the back of the queue.  Return null
     * if the queue is empty.
     *
     * @return the item at the tail of the queue
     */
    public final Object tail() {
        Object ret = null;
        if (size() > 0) {
            ret = queue[tail];
        }
        return ret;
    }

    /**
     * Remove and return the item at the front of the queue.  Return null
     * if the queue is empty.
     *
     * @return the item at the head of the queue
     */
    public final Object popFront() {
        Object ret = null;
        if (size() > 0) {
            head = head > 0 ? head - 1 : queue.length - 1;
            ret = queue[head];
        }
        return ret;
    }
    
    /**
     * Remove and return the item at the back of the queue.  Return null
     * if the queue is empty.
     *
     * @return the item at the tail of the queue
     */     
    public final Object popBack() {
        Object ret = null;
        if (size() > 0) {
            ret = queue[tail++];
            if (tail >= queue.length) tail = 0;
        }
        return ret;
    }

    public final void push(Object obj) {
        addBack(obj);
    }

    public final Object pop() {
        return popBack();
    }

    public final Object top() {
        return tail();
    }

    public final Object top(int pos) {
        Object ret = null;
        if (pos >= 0 && pos < size()) {
            int x = tail + pos;
            if (x >= queue.length) x -= queue.length;
            ret = queue[x];
        }
        return ret;
    }

    /**
     * Remove the specified object
     */
    public final void remove(Object obj) {
        int pos = head - 1;
        int cnt = size();
        int last = -1;
        for (int i = 0; i < cnt; i++) {
            if (pos < 0) pos = queue.length - 1;
            if (last < 0) {
                if (queue[pos] == obj) {
                    last = pos;
                }
            } else {
                queue[last] = queue[pos];
                tail = last;
                last = pos;
            }
        }
    }

    final void checkSizeForAdd() {
        int siz = size();
        if (siz == queue.length - 1) {
            if (capacity <= 0) {
                resize(queue.length + queue.length/8 + 1);
            } else {
                if (siz >= capacity) {
                    throw new RuntimeException("queue full");
                }
                resize(Math.min(capacity+1,
                                queue.length + queue.length/8 + 1));
            }
        }
    }

    final void resize(int newsize) {
        Object[] nq = new Object[newsize];
        if (head > tail) {
            System.arraycopy(queue, tail, nq, 0, head - tail);
            head -= tail;
            tail = 0;
        } else if (head < tail) {
            System.arraycopy(queue, tail, nq, 0, queue.length - tail);
            if (head > 0) {
                System.arraycopy(queue, 0, nq, queue.length - tail, head);
            }
            head += queue.length - tail;
            tail = 0;
        } else {
            // queue's empty
            head = tail = 0;
        }
        queue = nq;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("ArrayQueue");
        sb.append('[');
        int pos = head - 1;
        int cnt = size();
        for (int i = 0; i < cnt; i++) {
            if (pos < 0) pos = queue.length - 1;
            if (i > 0) sb.append(',');
            sb.append(queue[pos--]).toString();
        }
        sb.append(']');
        return sb.toString();
    }   
}