001    /*
002     * Copyright (c) Andrey Kuznetsov. All Rights Reserved.
003     *
004     * Redistribution and use in source and binary forms, with or without
005     * modification, are permitted provided that the following conditions are met:
006     *
007     *  o Redistributions of source code must retain the above copyright notice,
008     *    this list of conditions and the following disclaimer.
009     *
010     *  o Redistributions in binary form must reproduce the above copyright notice,
011     *    this list of conditions and the following disclaimer in the documentation
012     *    and/or other materials provided with the distribution.
013     *
014     *  o Neither the name of imagero Andrey Kuznetsov nor the names of
015     *    its contributors may be used to endorse or promote products derived
016     *    from this software without specific prior written permission.
017     *
018     * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019     * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
020     * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
021     * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
022     * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023     * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024     * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
025     * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
026     * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
027     * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
028     * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029     */
030    
031     package com.imagero.util;
032    
033    import java.util.EmptyStackException;
034    
035    /**
036     *
037     * Optimized Firt-In-First-Out implementation.
038     *
039     * @author Andrey Kuznetsov
040     */
041    public class Fifo {
042    
043        protected Object[] elements;
044    
045        protected int readPos;
046        protected int writePos;
047    
048        int threshold = 10;
049    
050        public Fifo() {
051            this(10);
052        }
053    
054        public Fifo(int count) {
055            this.elements = new Object[count];
056        }
057    
058        public void push(Object o) {
059            checkWritePos();
060            elements[writePos++] = o;
061        }
062    
063        public int size() {
064            return writePos - readPos;
065        }
066    
067        protected void checkWritePos() {
068            if(writePos >= elements.length) {
069                int length = size();
070                if(readPos > 0) {
071                    System.arraycopy(elements, readPos, elements, 0, length);
072                    readPos = 0;
073                    int wp = writePos;
074                    writePos = length;
075                    for (int i = writePos; i < wp; i++) {
076                        elements[i] = null;
077                    }
078                }
079                else {
080                    int nl = elements.length + (int) Math.min(4, Math.log(elements.length));
081                    Object [] tmp = new Object[nl];
082                    System.arraycopy(elements, 0, tmp, 0, length);
083                    elements = tmp;
084                }
085            }
086        }
087    
088        public Object pop() {
089            if(readPos < writePos) {
090                return elements[readPos++];
091            }
092            else {
093                throw new EmptyStackException();
094            }
095        }
096    }