1 | /* |
2 | * @(#) $Id: Queue.java 158877 2005-03-24 04:13:08Z trustin $ |
3 | * |
4 | * Copyright 2004 The Apache Software Foundation |
5 | * |
6 | * Licensed under the Apache License, Version 2.0 (the "License"); |
7 | * you may not use this file except in compliance with the License. |
8 | * You may obtain a copy of the License at |
9 | * |
10 | * http://www.apache.org/licenses/LICENSE-2.0 |
11 | * |
12 | * Unless required by applicable law or agreed to in writing, software |
13 | * distributed under the License is distributed on an "AS IS" BASIS, |
14 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
15 | * See the License for the specific language governing permissions and |
16 | * limitations under the License. |
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: 158877 $, $Date: 2005-03-24 13:13:08 +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 | // expand queue |
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 | } |