View Javadoc

1   /*
2    *   @(#) $Id: Queue.java 210062 2005-07-11 03:52:38Z 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: 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             // 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 }