1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.mina.util;
20
21 import java.io.Serializable;
22 import java.util.Arrays;
23
24 /***
25 * A unbounded circular queue.
26 *
27 * @author Trustin Lee (trustin@apache.org)
28 * @version $Rev: 210062 $, $Date: 2005-07-11 12:52:38 +0900 $
29 */
30 public class Queue implements Serializable
31 {
32 private static final long serialVersionUID = 3835151744526464313L;
33
34 private static final int DEFAULT_CAPACITY = 4;
35
36 private static final int DEFAULT_MASK = DEFAULT_CAPACITY - 1;
37
38 private Object[] items;
39
40 private int mask;
41
42 private int first = 0;
43
44 private int last = 0;
45
46 private int size = 0;
47
48 /***
49 * Construct a new, empty queue.
50 */
51 public Queue()
52 {
53 items = new Object[ DEFAULT_CAPACITY ];
54 mask = DEFAULT_MASK;
55 }
56
57 /***
58 * Returns the capacity of this queue.
59 */
60 public int capacity()
61 {
62 return items.length;
63 }
64
65 /***
66 * Clears this queue.
67 */
68 public void clear()
69 {
70 Arrays.fill( items, null );
71 first = 0;
72 last = 0;
73 size = 0;
74 }
75
76 /***
77 * Dequeues from this queue.
78 *
79 * @return <code>null</code>, if this queue is empty or the element is
80 * really <code>null</code>.
81 */
82 public Object pop()
83 {
84 if( size == 0 )
85 {
86 return null;
87 }
88
89 Object ret = items[ first ];
90 items[ first ] = null;
91 first = ( first + 1 ) & mask;
92
93 size--;
94
95 return ret;
96 }
97
98 /***
99 * Enqueue into this queue.
100 */
101 public void push( Object obj )
102 {
103 if( size == items.length )
104 {
105
106 final int oldLen = items.length;
107 Object[] tmp = new Object[ oldLen * 2 ];
108
109 if( first < last )
110 {
111 System.arraycopy( items, first, tmp, 0, last - first );
112 }
113 else
114 {
115 System.arraycopy( items, first, tmp, 0, oldLen - first );
116 System.arraycopy( items, 0, tmp, oldLen - first, last );
117 }
118
119 first = 0;
120 last = oldLen;
121 items = tmp;
122 mask = tmp.length - 1;
123 }
124
125 items[ last ] = obj;
126 last = ( last + 1 ) & mask;
127 size++;
128 }
129
130 /***
131 * Returns the first element of the queue.
132 *
133 * @return <code>null</code>, if the queue is empty, or the element is
134 * really <code>null</code>.
135 */
136 public Object first()
137 {
138 if( size == 0 )
139 {
140 return null;
141 }
142
143 return items[ first ];
144 }
145
146 public Object last()
147 {
148 if( size == 0 )
149 {
150 return null;
151 }
152
153 return items[ ( last + items.length - 1 ) & mask ];
154 }
155
156 public Object get( int idx )
157 {
158 return items[ ( first + idx ) & mask ];
159 }
160
161 /***
162 * Returns <code>true</code> if the queue is empty.
163 */
164 public boolean isEmpty()
165 {
166 return ( size == 0 );
167 }
168
169 /***
170 * Returns the number of elements in the queue.
171 */
172 public int size()
173 {
174 return size;
175 }
176
177 public String toString()
178 {
179 return "first=" + first + ", last=" + last + ", size=" + size + ", mask = " + mask;
180 }
181 }