Source code: javatools/util/JQueue.java
1 /*
2 Javatools (modified version) - Some useful general classes.
3 Copyright (C) 2002-2003 Chris Bitmead (original) Antonio Petrelli (modified)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
19 Contact me at: brenmcguire@users.sourceforge.net
20 */
21 package javatools.util;
22 import java.util.*;
23
24 /**
25 * Implements a regular queue. The only unusual thing is you can delete things
26 * from the middle of the queue efficiently by supplying the QueueKey which is
27 * returned by put(). In terms of implementation we use a Dictionary Hashtable
28 * instead of a perhaps more traditional vector with round-robin pointers. The
29 * benefit here is efficient implementation of the remove functionality. It
30 * also happens to be a really easy way to implement queues in general. The way
31 * it works is that the dictionary is used as a sparse array. The upper and
32 * lower bounds of the sparse array keeping growing up and up towards infinity.
33 * This is ok because the key is a long and will take several million years of
34 * running before any problems arise.
35 *
36 * @author Chris Bitmead
37 * @created December 13, 2001
38 * @version 0.7
39 * @comentedby Antonio Petrelli
40 */
41 public class JQueue {
42 /**
43 * We store the queue here
44 */
45 private Dictionary hash;
46
47 /**
48 * The next "put" position.
49 */
50 private long put;
51 /**
52 * The next "get" position
53 */
54 private long get;
55
56 /**
57 * Constructor which takes an initial guesstimate of how many items we expect
58 * to store in it
59 *
60 * @param size The size of this queue.
61 */
62 public JQueue(int size) {
63 init(size);
64 }
65
66 /** Creates a new empty JQueue.
67 */
68 public JQueue() {
69 init(10);
70 }
71
72 /**
73 * Pull something out of the end of the queue and remove it from the queue.
74 *
75 * @return The object in the end of the queue.
76 */
77 public Object get() {
78 Object rtn = peek();
79 hash.remove(new Long(get));
80 // allow garbage collection
81 get++;
82 return rtn;
83 }
84
85 /**
86 * Returns the number of elements in the queue
87 *
88 * @return The number of elements in the queue.
89 */
90 public int size() {
91 return hash.size();
92 }
93
94 /**
95 * Remove an item from anywhere in the queue.
96 *
97 * @param key The key which was returned from put().
98 * @return The object that was removed.
99 * @see Queue#put(Object)
100 */
101 public Object remove(QueueKey key) {
102 Long k = new Long(key.v);
103 Object rtn = hash.get(k);
104 hash.remove(k);
105 return rtn;
106 }
107
108 public void clear() {
109 init(hash.size());
110 }
111
112 /**
113 * Push something onto the queue
114 *
115 * @param o The object to push.
116 * @return An external key that can be passed to remove() to pull it from
117 * the queue. The value of the key should be regarded as meaningless to
118 * external parties.
119 * @see Queue#remove(QueueKey)
120 */
121 public QueueKey put(Object o) {
122 QueueKey rtn = null;
123 hash.put(new Long(put), o);
124 rtn = new QueueKey(put);
125 put++;
126 return rtn;
127 }
128
129 /**
130 * Is the queue empty?
131 *
132 * @return <CODE>true</CODE>: the queue is empty;
133 * <CODE>false</CODE>: it is not...
134 */
135 public boolean empty() {
136 return hash.size() == 0;
137 }
138
139 /**
140 * Get something out of the queue without removing it.
141 *
142 * @return The object at the end of the queue.
143 */
144 public Object peek() {
145 Object rtn = null;
146 if (empty()) {
147 throw new NoSuchElementException("Queue Empty");
148 }
149 while (rtn == null) {
150 rtn = hash.get(new Long(get));
151 if (rtn == null) {
152 get++;
153 }
154 }
155 return rtn;
156 }
157
158 /**
159 * Setup initialization
160 *
161 * @param size Description of Parameter
162 */
163 private void init(int size) {
164 hash = new Hashtable(size);
165 put = 0;
166 get = 0;
167 }
168
169 /**
170 * A class which can be used to pass to remove to remove something from the
171 * middle of the queue.
172 *
173 * @author Chris
174 * @created December 13, 2001
175 */
176 public class QueueKey {
177 /**
178 * A key for the dictionary
179 */
180 long v;
181
182 /** Creates a new QueueKey.
183 * @param key The key to use.
184 */
185 QueueKey(long key) {
186 v = key;
187 }
188 }
189 }