001 package org.rakeshv.utils;
002
003 /**
004 * A <i><b>F</b>irst <b>I</b>n <b>F</b>irst <b>O</b>ut</i>
005 * implementation using an <code>array</code>.
006 *
007 * @see SharedObject
008 * @see ObjectCache
009 *
010 * <p>Copyright 2002-2006 Rakesh Vidyadharan</p>
011 * @author Rakesh Vidyadharan 2002 March 1
012 * @version $Id: SimpleFIFO.java,v 1.4 2006/03/11 16:31:24 rakesh Exp $
013 */
014 public class SimpleFIFO<T> extends Object implements DataStructure<T>
015 {
016 /**
017 * An array that is used to implement a <code>FIFO</code>.
018 */
019 private T[] fifo;
020
021 /**
022 * A variable that holds the index into the {@link #fifo} at which
023 * a new instance is to be added. The index <code>rolls around
024 * </code> from the end of the fifo to the beginning when the fifo
025 * is full.
026 */
027 private int index;
028
029 /**
030 * A flag to indicate that the fifo has been filled. This will be
031 * set only once after the fifo has been filled initially.
032 */
033 private boolean filled;
034
035 /**
036 * Construct a new <code>FIFO</code> of the specified size.
037 */
038 @SuppressWarnings(value={"unchecked"})
039 public SimpleFIFO( int size )
040 {
041 super();
042 filled = false;
043 fifo = (T[]) new Object[ size ];
044 }
045
046 /**
047 * Return the current <code>Object</code> in the {@link #fifo}. This
048 * is the object that will be replaced when the next call to
049 * {@link #add( Object )} is made.
050 *
051 * @return The Object that is at the {@link #index} within the fifo.
052 * This will be <code>null</code> if the fifo has not been
053 * {@link #filled} yet.
054 */
055 public T get()
056 {
057 return fifo[ index ];
058 }
059
060 /**
061 * Add the specified object to {@link #fifo}. Updates the {@link
062 * #index} after adding the specified object to the next location
063 * in the fifo. Sets {@link #filled} to <code>true</code> when the
064 * {@link #index} rolls around to the beginning of the fifo for the
065 * first time.
066 *
067 * <p><b>Note:</b> This method does not perform any <code>
068 * synchronisation</code>, and hence is not <code>thread-safe</code>.
069 * Client's must perform their own synchronisation if they so desire.
070 * </p>
071 *
072 * @param object The object to be added to the fifo.
073 * @throws IllegalArgumentException If a <code>null</code> value was
074 * specified for the object.
075 */
076 public void add( T object )
077 {
078 if ( object == null )
079 {
080 throw new IllegalArgumentException(
081 "Null values are not allowed in the FIFO" );
082 }
083
084 fifo[ index ] = object;
085 index = ( ++index ) % fifo.length;
086
087 if ( ! filled && index == 0 ) filled = true;
088 }
089
090 /**
091 * Removes the current <code>Object</code> designated for removal
092 * (located at {@link #index}) from the {@link #fifo}.
093 *
094 * @return The Object that was removed.
095 */
096 public T remove()
097 {
098 T object = fifo[ index ];
099 fifo[ index ] = null;
100 return object;
101 }
102
103 /**
104 * Removes the specified object from the {@link #fifo}. The time to
105 * remove the specified object will be directly proportional to the
106 * size of the fifo.
107 *
108 * <p>This operation can be very heavy, since it involves iterating
109 * through the fifo. The following conditions apply:</p>
110 *
111 * <ol>
112 * <li>Iterate through the fifo, and find the first matching object.
113 * <li>Remove the matching object from the fifo.
114 * <li>Move all succeeding objects in the fifo up by one position.
115 * <li>Reset the {@link #index} to point to the end of the fifo
116 * or to the previous position depending upon whether the fifo was
117 * {@link #filled} or not.
118 * <li>Matching is performed using an exact matching rule (the
119 * <code>==</code> operator), and not the equivalent matching rule
120 * (the {@link #equals( Object )}) operator.
121 * </ol>
122 *
123 * <p>If there are multiple instances of the same object in the fifo,
124 * only the first matching object is removed.</p>
125 *
126 * <p><b>Note:</b> This method does not perform any <code>
127 * synchronisation</code>, and hence is not <code>thread-safe</code>.
128 * Client's must perform their own synchronisation if they so desire.
129 * </p>
130 *
131 * @param object The object that is to be removed from the fifo.
132 * @return Returns <code>true</code> if the specified object was
133 * found and removed from the fifo.
134 */
135 public boolean remove( T object )
136 {
137 boolean result = false;
138
139 int iterator = 0;
140
141 for ( ; iterator < fifo.length; ++iterator )
142 {
143 if ( fifo[ iterator ] == object )
144 {
145 fifo[ iterator ] = null;
146 result = true;
147 break;
148 }
149 }
150
151 if ( filled )
152 {
153 for ( ; iterator < fifo.length - 1; ++iterator )
154 {
155 fifo[ iterator ] = fifo[ iterator + 1 ];
156 }
157
158 index = fifo.length - 1;
159 }
160 else
161 {
162 for ( ; iterator < index - 1; ++iterator )
163 {
164 fifo[ iterator ] = fifo[ iterator + 1 ];
165 }
166
167 --index;
168 }
169
170 return result;
171 }
172
173 /**
174 * Removes all the objects from the {@link #fifo}. The most
175 * efficient way to do it is to create a new instance of the fifo
176 * array, and consign the old instance to the garbage collector.
177 *
178 * <p><b>Note:</b> This method does not perform any <code>
179 * synchronisation</code>, and hence is not <code>thread-safe</code>.
180 * Client's must perform their own synchronisation if they so desire.
181 * </p>
182 */
183 @SuppressWarnings(value={"unchecked"})
184 public void clear()
185 {
186 int size = fifo.length;
187 index = 0;
188 fifo = (T[]) new Object[ size ];
189 }
190
191 /**
192 * Returns the size of the {@link #fifo}. Returns the total size
193 * of the fifo, if the fifo has been {@link #filled}, else returns
194 * the {@link #index} value.
195 *
196 * @return The size of the fifo.
197 */
198 public int size()
199 {
200 int size = 0;
201 if ( filled )
202 {
203 size = fifo.length;
204 }
205 else
206 {
207 size = index;
208 }
209
210 return size;
211 }
212 }