QueueBase


1   /*
2    * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3    *
4    * Permission is hereby granted, free of charge, to any person obtaining a copy
5    * of this software and associated documentation files (the "Software"), to deal
6    * in the Software without restriction, including without limitation the rights 
7    * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 
8    * copies of the Software, and to permit persons to whom the Software is 
9    * furnished to do so, subject to the following conditions:
10   *
11   * The above copyright notice and this permission notice shall be included in 
12   * all copies or substantial portions of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
19   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 
20   * IN THE SOFTWARE.
21   */
22  
23  package com.sosnoski.util.queue;
24  
25  import java.lang.reflect.Array  ;
26  
27  import com.sosnoski.util.*;
28  
29  /**
30   * Base class for type-specific growable circular queue classes with any type 
31   * of values (including primitive types). This class builds on the basic 
32   * structure provided by <code>GrowableBase</code>, specializing it for usage 
33   * as a queue. See the base class description for details of the 
34   * implementation.<p>
35   *
36   * Queues based on this class are unsynchronized in order to provide the
37   * best possible performance for typical usage scenarios, so explicit
38   * synchronization must be implemented by the subclass or the application in
39   * cases where they are to be modified in a multithreaded environment.<p>
40   *
41   * Subclasses need to implement the abstract methods defined by the base class
42   * for working with the data array, as well as the actual data access methods
43   * (at least the basic <code>add()</code> and <code>remove()</code> methods).
44   * 
45   * @author Dennis M. Sosnoski
46   * @version 1.0
47   */
48  
49  public abstract class QueueBase extends GrowableBase
50  {
51      /** Offset for adding next item to queue. */
52      protected int m_fillOffset;
53      
54      /** Offset for removing next item from queue. */
55      protected int m_emptyOffset;
56  
57      /**
58       * Constructor with full specification.
59       * 
60       * @param size number of elements initially allowed in queue
61       * @param growth maximum size increment for growing queue
62       * @param type queue element type
63       */
64      
65      public QueueBase(int size, int growth, Class   type) {
66          super(size, growth, type);
67      }
68  
69      /**
70       * Constructor with partial specification.
71       * 
72       * @param size number of elements initially allowed in queue
73       * @param type queue element type
74       */
75      
76      public QueueBase(int size, Class   type) {
77          this(size, Integer.MAX_VALUE, type);
78      }
79  
80      /**
81       * Copy (clone) constructor.
82       * 
83       * @param from instance being copied
84       */
85      
86      public QueueBase(QueueBase base) {
87          super(base);
88          System.arraycopy(base.getArray(), 0, getArray(), 0, m_countLimit);
89          m_fillOffset = base.m_fillOffset;
90          m_emptyOffset = base.m_emptyOffset;
91      }
92  
93      /**
94       * Copy data after array resize. This override of the default
95       * implementation rearranges the data present in the queue when the
96       * data was wrapped in the original array.
97       * 
98       * @param base original array containing data
99       * @param grown resized array for data
100      */
101     
102     protected void resizeCopy(Object   base, Object   grown) {
103         
104         // check if we have a wrapped queue
105         if (m_fillOffset < m_emptyOffset) {
106             
107             // copy wrapped queue data to new array
108             int size = Array.getLength(base);
109             int length = size - m_emptyOffset;
110             System.arraycopy(base, m_emptyOffset, grown, 0, length);
111             System.arraycopy(base, 0, grown, length, m_fillOffset);
112             m_fillOffset += size;
113             
114         } else {
115             
116             // copy single block of queue data to new array
117             int length = m_fillOffset - m_emptyOffset;
118             System.arraycopy(base, m_emptyOffset, grown, 0, length);
119         }
120         
121         // set data limits in new array
122         m_fillOffset -= m_emptyOffset;
123         m_emptyOffset = 0;
124     }
125 
126     /**
127      * Make space for adding a value to those in the queue.
128      * If the underlying array is full, it is grown by the appropriate size
129      * increment so that the index value returned is always valid for the 
130      * array in use by the time of the return.
131      * 
132      * @return index position to store added element
133      */
134     
135     protected int getAddIndex() {
136         
137         // increment fill offset in queue
138         int next = (m_fillOffset + 1) % m_countLimit;
139         
140         // check for queue full condition
141         if (next == m_emptyOffset) {
142             
143             // grow the underlying array
144             growArray(m_countLimit + 1);
145             next = m_fillOffset + 1;
146         }
147         
148         // set next offset and return this
149         int index = m_fillOffset;
150         m_fillOffset = next;
151         return index;
152     }
153 
154     /**
155      * Removes the next item from the queue.
156      * 
157      * @return index position of removed element
158      * @exception IllegalStateException on attempt to remove an item from an
159      * empty queue
160      */
161     
162     protected int getRemoveIndex() {
163         if (m_fillOffset == m_emptyOffset) {
164             throw new IllegalStateException  
165                 ("Attempted remove from empty queue");
166         } else {
167             int offset = m_emptyOffset;
168             m_emptyOffset = (m_emptyOffset + 1) % m_countLimit;
169             return offset;
170         }
171     }
172 
173     /**
174      * Get the number of values currently present in the queue.
175      * 
176      * @return count of values present
177      */
178     
179     public int size() {
180         int diff = m_fillOffset - m_emptyOffset;
181         return (diff >= 0) ? diff : (diff + m_countLimit);
182     }
183 
184     /**
185      * Check if queue is empty.
186      * 
187      * @return <code>true</code> if queue empty, <code>false</code> if not
188      */
189     
190     public boolean isEmpty() {
191         return m_fillOffset == m_emptyOffset;
192     }
193 
194     /**
195      * Set the queue to the empty state.
196      */
197     
198     public void clear() {
199         if (m_fillOffset >= m_emptyOffset) {
200             discardValues(m_emptyOffset, m_fillOffset);
201         } else {
202             discardValues(m_emptyOffset, m_countLimit);
203             discardValues(0, m_fillOffset);
204         }
205         m_fillOffset = m_emptyOffset = 0;
206     }
207 
208     /**
209      * Discard items from queue.
210      *
211      * @param count number of items to be discarded
212      * @exception IllegalStateException if attempt to discard more items than
213      * present on queue
214      */
215     
216     public void discard(int count) {
217         if (count > size()) {
218             throw new IllegalStateException  
219                 ("Attempted to discard more items than present on queue");
220         } else {
221             int limit = m_emptyOffset + count;
222             if (limit > m_countLimit) {
223                 limit -= m_countLimit;
224                 discardValues(m_emptyOffset, m_countLimit);
225                 discardValues(0, limit);
226             } else {
227                 discardValues(m_emptyOffset, limit);
228             }
229             m_emptyOffset = limit;
230         }
231     }
232 
233     /**
234      * Constructs and returns a simple array containing the same data as held 
235      * in this queue.
236      * 
237      * @param type element type for constructed array
238      * @return array containing a copy of the data
239      */
240     
241     protected Object   buildArray(Class   type) {
242         int length = size();
243         Object   copy = Array.newInstance(type, length);
244         if (m_fillOffset >= m_emptyOffset) {
245             System.arraycopy(getArray(), m_emptyOffset, copy, 0, length);
246         } else {
247             int offset = m_countLimit - m_emptyOffset;
248             System.arraycopy(getArray(), m_emptyOffset, copy, 0, offset);
249             System.arraycopy(getArray(), 0, copy, offset, m_fillOffset);
250         }
251         return copy;
252     }
253 }
254
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags