001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.util;
018:
019: import java.util.Collection;
020: import java.util.Iterator;
021: import java.util.NoSuchElementException;
022:
023: public class FIFOQueue implements Collection, Queue {
024: private static final int DEFAULT_SIZE = 10;
025:
026: private Object[] m_values;
027: private int m_in;
028: private int m_out;
029: private boolean m_full;
030: private boolean m_empty;
031:
032: public FIFOQueue() {
033: this (DEFAULT_SIZE);
034: m_full = false;
035: }
036:
037: public FIFOQueue(int size) {
038: m_values = new Object[size];
039: clear();
040:
041: }
042:
043: public void enq(Object element) {
044: if (m_full)
045: throw new IllegalStateException("Queue full.");
046: m_empty = false;
047:
048: m_values[m_in++] = element;
049: if (m_in == m_values.length)
050: m_in = 0;
051: m_full = m_in == m_out;
052: }
053:
054: public Object deq() {
055: if (m_empty)
056: throw new NoSuchElementException("Heap empty.");
057: m_full = false;
058:
059: Object o = m_values[m_out];
060: m_values[m_out++] = null;
061:
062: if (m_out == m_values.length)
063: m_out = 0;
064: m_empty = m_in == m_out;
065:
066: return (o);
067: }
068:
069: public int size() {
070: if (m_empty)
071: return (0);
072: if (m_full)
073: return (m_values.length);
074:
075: int size = 0;
076: for (int i = m_out; i < m_values.length; i++, size++) {
077: if (i == m_in)
078: return (size);
079: }
080:
081: for (int i = 0; i < m_in; i++, size++)
082: ;
083:
084: return (size);
085: }
086:
087: public void clear() {
088: m_in = 0;
089: m_out = 0;
090: m_full = false;
091: m_empty = true;
092: }
093:
094: public boolean isEmpty() {
095: return (m_empty);
096: }
097:
098: public boolean isFull() {
099: return (m_full);
100: }
101:
102: public Object[] toArray() {
103: return (m_values);
104: }
105:
106: public boolean add(Object o) {
107: enq(o);
108: return (true);
109: }
110:
111: public boolean contains(Object o) {
112: for (int i = 0; i < m_values.length; i++) {
113: if (m_values[i] != null && m_values[i].equals(o))
114: return (true);
115: }
116: return (false);
117: }
118:
119: public boolean remove(Object o) {
120: throw new UnsupportedOperationException("remove(Object)");
121: }
122:
123: public boolean addAll(Collection c) {
124: for (Iterator itr = c.iterator(); itr.hasNext();) {
125: enq(itr.next());
126: }
127: return (true);
128: }
129:
130: public boolean containsAll(Collection c) {
131: for (Iterator itr = c.iterator(); itr.hasNext();) {
132: if (!contains(itr.next()))
133: return (false);
134: }
135: return (true);
136: }
137:
138: public boolean removeAll(Collection c) {
139: throw new UnsupportedOperationException("removeAll(Collection)");
140: }
141:
142: public boolean retainAll(Collection c) {
143: throw new UnsupportedOperationException("retainAll(Collection)");
144: }
145:
146: public Iterator iterator() {
147: return (new QueueIterator());
148: }
149:
150: public Object[] toArray(Object[] a) {
151: int size = size();
152: if (a.length < size) {
153: a = (Object[]) java.lang.reflect.Array.newInstance(a
154: .getClass().getComponentType(), size);
155: }
156:
157: int j = 0;
158: for (int i = m_out; i < m_values.length; i++, j++) {
159: if (i == m_in) {
160: if (j < a.length)
161: a[j] = null;
162: return (a);
163: }
164: a[j] = m_values[i];
165: }
166:
167: for (int i = 0; i < m_out; i++, j++) {
168: a[j] = m_values[i];
169: }
170:
171: if (j < a.length)
172: a[j] = null;
173:
174: return (a);
175: }
176:
177: public class QueueIterator implements Iterator {
178: int m_index = m_out;
179:
180: private QueueIterator() {
181: }
182:
183: public void remove() {
184: throw new UnsupportedOperationException("remove()");
185: }
186:
187: public boolean hasNext() {
188: return (m_index != m_in);
189: }
190:
191: public Object next() {
192: Object o = m_values[m_index++];
193: if (m_index == m_values.length)
194: m_index = 0;
195: return (o);
196: }
197: }
198:
199: //package level visibility data methods for testing
200: int in() {
201: return (m_in);
202: }
203:
204: int out() {
205: return (m_out);
206: }
207:
208: Object[] values() {
209: return (m_values);
210: }
211:
212: }
|