1 /***
2 * Redistribution and use of this software and associated documentation
3 * ("Software"), with or without modification, are permitted provided
4 * that the following conditions are met:
5 *
6 * 1. Redistributions of source code must retain copyright
7 * statements and notices. Redistributions must also contain a
8 * copy of this document.
9 *
10 * 2. Redistributions in binary form must reproduce the
11 * above copyright notice, this list of conditions and the
12 * following disclaimer in the documentation and/or other
13 * materials provided with the distribution.
14 *
15 * 3. The name "Exolab" must not be used to endorse or promote
16 * products derived from this Software without prior written
17 * permission of Exoffice Technologies. For written permission,
18 * please contact info@exolab.org.
19 *
20 * 4. Products derived from this Software may not be called "Exolab"
21 * nor may "Exolab" appear in their names without prior written
22 * permission of Exoffice Technologies. Exolab is a registered
23 * trademark of Exoffice Technologies.
24 *
25 * 5. Due credit should be given to the Exolab Project
26 * (http://www.exolab.org/).
27 *
28 * THIS SOFTWARE IS PROVIDED BY EXOFFICE TECHNOLOGIES AND CONTRIBUTORS
29 * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
30 * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
31 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
32 * EXOFFICE TECHNOLOGIES OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
33 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
34 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
35 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
37 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
38 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
39 * OF THE POSSIBILITY OF SUCH DAMAGE.
40 *
41 * Copyright 2000-2004 (C) Exoffice Technologies Inc. All Rights Reserved.
42 *
43 * $Id: OrderedQueue.java,v 1.1 2004/11/26 01:50:35 tanderson Exp $
44 */
45 package org.exolab.jms.common.util;
46
47 import java.util.Comparator;
48 import java.util.Vector;
49
50
51 /***
52 * The OrderedQueue is responsible for managing the expiration of the leases.
53 * The LeaseComparator is used to determine where they are inserted and the
54 * lease with the shortest duration is removed from the queue first. It is
55 * implemented suing a Vector but this could be changed to improve performance.
56 *
57 * @author <a href="mailto:jima@exoffice.com">Jim Alateras</a>
58 * @version $Revision: 1.1 $ $Date: 2004/11/26 01:50:35 $
59 */
60 public class OrderedQueue {
61
62 /****
63 * The queue
64 */
65 private Vector _queue = null;
66
67 /***
68 * The comparator for ordering the queue
69 */
70 private Comparator _comparator = null;
71
72 /***
73 * Construct an instance of this class with the comparator to order the
74 * elements in the queue. Elements with the same order value are placed
75 * after each other.
76 *
77 * @param comparator used for ordering
78 */
79 public OrderedQueue(Comparator comparator) {
80 _comparator = comparator;
81 _queue = new Vector();
82 }
83
84 /***
85 * Add this element to the queue in the required order. It uses a binary
86 * search to locate the correct position
87 *
88 * @param object object to add
89 */
90 public synchronized void add(Object object) {
91
92 if (_queue.size() == 0) {
93
94 _queue.addElement(object);
95 } else {
96 int start = 0;
97 int end = _queue.size() - 1;
98
99 if (_comparator.compare(object,
100 _queue.firstElement()) < 0) {
101
102 _queue.insertElementAt(object, 0);
103 } else if (_comparator.compare(object,
104 _queue.lastElement()) > 0) {
105
106 _queue.addElement(object);
107 } else {
108
109 while (true) {
110 int midpoint = start + (end - start) / 2;
111 if (((end - start) % 2) != 0) {
112 midpoint++;
113 }
114
115 int result = _comparator.compare(
116 object, _queue.elementAt(midpoint));
117
118 if (result == 0) {
119 _queue.insertElementAt(object, midpoint);
120 break;
121 } else if ((start + 1) == end) {
122
123
124 _queue.insertElementAt(object, end);
125 break;
126 } else {
127 if (result > 0) {
128
129 start = midpoint;
130 } else {
131
132 end = midpoint;
133 }
134 }
135 }
136 }
137 }
138 }
139
140 /***
141 * Remove the object from the queue
142 *
143 * @param object object to remove
144 * @return <code>true</code> if the object was removed
145 */
146 public synchronized boolean remove(Object object) {
147 return _queue.remove(object);
148 }
149
150 /***
151 * Remove all the elements from the queue
152 */
153 public synchronized void clear() {
154 _queue.clear();
155 }
156
157 /***
158 * Return the number elements in the queue
159 *
160 * @return int size of the queue
161 */
162 public int size() {
163 return _queue.size();
164 }
165
166 /***
167 * Return the first element on the queue
168 *
169 * @return Object
170 */
171 public Object firstElement() {
172 return _queue.firstElement();
173 }
174
175 /***
176 * Remove the first element from the queue or null if there are no elements
177 * on the queue.
178 *
179 * @return Object
180 */
181 public synchronized Object removeFirstElement() {
182 return _queue.remove(0);
183 }
184
185 }
186