1 | /*
|
---|
2 | * This program is free software; you can redistribute it and/or modify
|
---|
3 | * it under the terms of the GNU General Public License as published by
|
---|
4 | * the Free Software Foundation; either version 2 of the License, or
|
---|
5 | * (at your option) any later version.
|
---|
6 | *
|
---|
7 | * This program is distributed in the hope that it will be useful,
|
---|
8 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
9 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
10 | * GNU General Public License for more details.
|
---|
11 | *
|
---|
12 | * You should have received a copy of the GNU General Public License
|
---|
13 | * along with this program; if not, write to the Free Software
|
---|
14 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
15 | */
|
---|
16 |
|
---|
17 | /*
|
---|
18 | * Queue.java
|
---|
19 | * Copyright (C) 1999 Len Trigg
|
---|
20 | *
|
---|
21 | */
|
---|
22 |
|
---|
23 | package weka.core;
|
---|
24 |
|
---|
25 | import java.io.*;
|
---|
26 |
|
---|
27 | /**
|
---|
28 | * Class representing a FIFO queue.
|
---|
29 | *
|
---|
30 | * @author Len Trigg ([email protected])
|
---|
31 | * @version $Revision: 8815 $
|
---|
32 | */
|
---|
33 | public class Queue extends Object implements Serializable {
|
---|
34 |
|
---|
35 | /**
|
---|
36 | * Represents one node in the queue.
|
---|
37 | */
|
---|
38 | protected class QueueNode implements Serializable {
|
---|
39 |
|
---|
40 | /** The next node in the queue */
|
---|
41 | protected QueueNode m_Next;
|
---|
42 |
|
---|
43 | /** The nodes contents */
|
---|
44 | protected Object m_Contents;
|
---|
45 |
|
---|
46 | /**
|
---|
47 | * Creates a queue node with the given contents
|
---|
48 | */
|
---|
49 | public QueueNode(Object contents) {
|
---|
50 |
|
---|
51 | m_Contents = contents;
|
---|
52 | next(null);
|
---|
53 | }
|
---|
54 |
|
---|
55 | /**
|
---|
56 | * Sets the next node in the queue, and returns it.
|
---|
57 | */
|
---|
58 | public QueueNode next(QueueNode next) {
|
---|
59 |
|
---|
60 | return m_Next = next;
|
---|
61 | }
|
---|
62 |
|
---|
63 | /**
|
---|
64 | * Gets the next node in the queue.
|
---|
65 | */
|
---|
66 | public QueueNode next() {
|
---|
67 |
|
---|
68 | return m_Next;
|
---|
69 | }
|
---|
70 |
|
---|
71 | /**
|
---|
72 | * Sets the contents of the node.
|
---|
73 | */
|
---|
74 | public Object contents(Object contents) {
|
---|
75 |
|
---|
76 | return m_Contents = contents;
|
---|
77 | }
|
---|
78 |
|
---|
79 | /**
|
---|
80 | * Returns the contents in the node.
|
---|
81 | */
|
---|
82 | public Object contents() {
|
---|
83 |
|
---|
84 | return m_Contents;
|
---|
85 | }
|
---|
86 | }
|
---|
87 |
|
---|
88 | /** Store a reference to the head of the queue */
|
---|
89 | protected QueueNode m_Head = null;
|
---|
90 |
|
---|
91 | /** Store a reference to the tail of the queue */
|
---|
92 | protected QueueNode m_Tail = null;
|
---|
93 |
|
---|
94 | /** Store the current number of elements in the queue */
|
---|
95 | protected int m_Size = 0;
|
---|
96 |
|
---|
97 | /**
|
---|
98 | * Removes all objects from the queue.
|
---|
99 | */
|
---|
100 | public final synchronized void removeAllElements() {
|
---|
101 |
|
---|
102 | m_Size = 0;
|
---|
103 | m_Head = null;
|
---|
104 | m_Tail = null;
|
---|
105 | }
|
---|
106 |
|
---|
107 | /**
|
---|
108 | * Appends an object to the back of the queue.
|
---|
109 | *
|
---|
110 | * @param item the object to be appended
|
---|
111 | * @return the object appended
|
---|
112 | */
|
---|
113 | public synchronized Object push(Object item) {
|
---|
114 |
|
---|
115 | QueueNode newNode = new QueueNode(item);
|
---|
116 | if (m_Head == null) {
|
---|
117 | m_Head = m_Tail = newNode;
|
---|
118 | } else {
|
---|
119 | m_Tail = m_Tail.next(newNode);
|
---|
120 | }
|
---|
121 | m_Size++;
|
---|
122 | return item;
|
---|
123 | }
|
---|
124 |
|
---|
125 | /**
|
---|
126 | * Pops an object from the front of the queue.
|
---|
127 | *
|
---|
128 | * @return the object at the front of the queue
|
---|
129 | * @exception RuntimeException if the queue is empty
|
---|
130 | */
|
---|
131 | public synchronized Object pop() {
|
---|
132 |
|
---|
133 | if (m_Head == null) {
|
---|
134 | throw new RuntimeException("Queue is empty");
|
---|
135 | }
|
---|
136 | Object retval = m_Head.contents();
|
---|
137 | m_Size--;
|
---|
138 | m_Head = m_Head.next();
|
---|
139 | if (m_Head == null) {
|
---|
140 | m_Tail = null;
|
---|
141 | }
|
---|
142 | return retval;
|
---|
143 | }
|
---|
144 |
|
---|
145 | /**
|
---|
146 | * Gets object from the front of the queue.
|
---|
147 | *
|
---|
148 | * @return the object at the front of the queue
|
---|
149 | * @exception RuntimeException if the queue is empty
|
---|
150 | */
|
---|
151 | public synchronized Object peek() {
|
---|
152 |
|
---|
153 | if (m_Head == null) {
|
---|
154 | throw new RuntimeException("Queue is empty");
|
---|
155 | }
|
---|
156 | return m_Head.contents();
|
---|
157 | }
|
---|
158 |
|
---|
159 | /**
|
---|
160 | * Checks if queue is empty.
|
---|
161 | *
|
---|
162 | * @return true if queue is empty
|
---|
163 | */
|
---|
164 | public boolean empty() {
|
---|
165 |
|
---|
166 | return (m_Head == null);
|
---|
167 | }
|
---|
168 |
|
---|
169 | /**
|
---|
170 | * Gets queue's size.
|
---|
171 | *
|
---|
172 | * @return size of queue
|
---|
173 | */
|
---|
174 | public int size() {
|
---|
175 |
|
---|
176 | return m_Size;
|
---|
177 | }
|
---|
178 |
|
---|
179 | /**
|
---|
180 | * Produces textual description of queue.
|
---|
181 | *
|
---|
182 | * @return textual description of queue
|
---|
183 | */
|
---|
184 | public String toString() {
|
---|
185 |
|
---|
186 | String retval = "Queue Contents "+m_Size+" elements\n";
|
---|
187 | QueueNode current = m_Head;
|
---|
188 | if (current == null) {
|
---|
189 | return retval + "Empty\n";
|
---|
190 | } else {
|
---|
191 | while (current != null) {
|
---|
192 | retval += current.contents().toString()+"\n";
|
---|
193 | current = current.next();
|
---|
194 | }
|
---|
195 | }
|
---|
196 | return retval;
|
---|
197 | }
|
---|
198 |
|
---|
199 | /**
|
---|
200 | * Main method for testing this class.
|
---|
201 | *
|
---|
202 | * @param argv a set of strings that are pushed on a test queue
|
---|
203 | */
|
---|
204 | public static void main(String [] argv) {
|
---|
205 |
|
---|
206 | try {
|
---|
207 | Queue queue = new Queue();
|
---|
208 | for(int i = 0; i < argv.length; i++) {
|
---|
209 | queue.push(argv[i]);
|
---|
210 | }
|
---|
211 | System.out.println("After Pushing");
|
---|
212 | System.out.println(queue.toString());
|
---|
213 | System.out.println("Popping...");
|
---|
214 | while (!queue.empty()) {
|
---|
215 | System.out.println(queue.pop().toString());
|
---|
216 | }
|
---|
217 | } catch (Exception ex) {
|
---|
218 | System.out.println(ex.getMessage());
|
---|
219 | }
|
---|
220 | }
|
---|
221 | }
|
---|
222 |
|
---|
223 |
|
---|
224 |
|
---|
225 |
|
---|
226 |
|
---|
227 |
|
---|
228 |
|
---|
229 |
|
---|