1 /***
2 * ArrayQueue.java
3 *
4 * Project: Dependency Tool
5 *
6 * WHEN WHO WHAT
7 * 06.06.2003 pko initial public release
8 * 22.05.2002 ctr creation
9 *
10 * Copyright 2003 ELCA Informatique SA
11 * Av. de la Harpe 22-24, 1000 Lausanne 13, Switzerland
12 * www.elca.ch
13 *
14 * This library is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU Lesser General Public License
16 * as published by the Free Software Foundation; either version 2.1 of
17 * the License, or (at your option) any later version.
18 *
19 * This library is distributed in the hope that it will be useful, but
20 * WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 * Lesser General Public License for more details.
23 *
24 * You should have received a copy of the GNU Lesser General Public
25 * License along with this library; if not, write to the Free Software
26 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
27 * USA
28 */
29
30 package ch.elca.dependency.util;
31
32 import ch.elca.dependency.exception.QueueEmptyException;
33 import ch.elca.dependency.exception.QueueFullException;
34
35 /***
36 * Implementation of the standard <code>Queue</code> interface.
37 *
38 * @author Christoph Trutmann
39 * @version 1.0-beta
40 */
41 public class ArrayQueue implements Queue {
42
43 /***
44 * If the user does not specify anything, this capacity is used.
45 */
46 private static final int INITIAL_CAPACITY = 1000000;
47
48 /***
49 * Capacity of the queue.
50 */
51 private int m_capacity;
52
53 /***
54 * Pointer on the front element.
55 */
56 private int m_front = 0;
57
58 /***
59 * Pointer on the rear element.
60 */
61 private int m_rear = 0;
62
63 /***
64 * Array containing the elements of the queue.
65 */
66 private Object[] m_Q;
67
68 /***
69 * Constructor - Initializes the fields.
70 * The capacity is defined as a constant.
71 */
72 public ArrayQueue() {
73 m_capacity = INITIAL_CAPACITY;
74 m_Q = new Object[m_capacity];
75 }
76
77 /***
78 * Constructor - Initializes the fields.
79 * The capacity is defined as an argument in the constructor.
80 *
81 * @param capacity an <code>int</code> value
82 */
83 public ArrayQueue(int capacity) {
84 m_capacity = capacity;
85 m_Q = new Object[m_capacity];
86 }
87
88 /***
89 * Insert object o at the rear of the queue.
90 *
91 * @param o Object to be inserted at the rear of the queue.
92 * @throws QueueFullException If the queue is full.
93 */
94 public void enqueue(Object o) throws QueueFullException {
95 if ( size() >= m_capacity - 1 ) {
96 throw new QueueFullException("Queue overflow.");
97 }
98 m_Q[m_rear] = o;
99 m_rear = (m_rear + 1) % m_capacity;
100 }
101
102 /***
103 * Remove and return from the queue the object at the front.
104 *
105 * @return Object removed from the front of the queue.
106 * @throws QueueEmptyException If the queue is empty.
107 */
108 public Object dequeue() throws QueueEmptyException {
109 if ( isEmpty() ) {
110 throw new QueueEmptyException("Queue underflow.");
111 }
112 Object tmp = m_Q[m_front];
113 m_Q[m_front] = null;
114 m_front = (m_front + 1) % m_capacity;
115 return tmp;
116 }
117
118 /***
119 * Return the number of objects in the queue.
120 *
121 * @return Number of objects in the queue.
122 */
123 public int size() {
124 return (m_capacity - m_front + m_rear) % m_capacity;
125 }
126
127 /***
128 * Return a boolean value that indicates whether the queue is empty.
129 *
130 * @return True if the queue is empty.
131 */
132 public boolean isEmpty(){
133 return (m_front == m_rear);
134 }
135
136 /***
137 * Return, but do not remove, the front object in the queue. An error occurs
138 * if the qeue is empty.
139 *
140 * @return Object in front of the queue.
141 * @throws QueueEmptyException If the queue is empty.
142 */
143 public Object front() throws QueueEmptyException {
144 if ( isEmpty() ) {
145 throw new QueueEmptyException("Queue underflow.");
146 }
147 return m_Q[m_front];
148 }
149 }
This page was automatically generated by Maven