KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > exolab > jms > common > util > OrderedQueue


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 JavaDoc;
48 import java.util.Vector JavaDoc;
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 JavaDoc _queue = null;
66
67     /**
68      * The comparator for ordering the queue
69      */
70     private Comparator JavaDoc _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 JavaDoc comparator) {
80         _comparator = comparator;
81         _queue = new Vector JavaDoc();
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 JavaDoc object) {
91
92         if (_queue.size() == 0) {
93             // no elements then simply add it here
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                 // it need to go before the first element
102 _queue.insertElementAt(object, 0);
103             } else if (_comparator.compare(object,
104                                            _queue.lastElement()) > 0) {
105                 // add to the end of the queue
106 _queue.addElement(object);
107             } else {
108                 // somewhere in the middle
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                         // if the start and end are next to each other then
123 // insert after at the end
124 _queue.insertElementAt(object, end);
125                         break;
126                     } else {
127                         if (result > 0) {
128                             // musty be in the upper half
129 start = midpoint;
130                         } else {
131                             // must be in the lower half
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 JavaDoc 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 JavaDoc 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 JavaDoc removeFirstElement() {
182         return _queue.remove(0);
183     }
184
185 }
186
187
Popular Tags