Debian Codegraph @

laf-widget/src/main/java/org/pushingpixels/lafwidget/utils/DeltaQueue.java

raw
1 /*
2 * Copyright (c) 2005-2010 Laf-Widget Kirill Grouchnikov. All Rights Reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * o Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 *
10 * o Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 *
14 * o Neither the name of Laf-Widget Kirill Grouchnikov nor the names of
15 * its contributors may be used to endorse or promote products derived
16 * from this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
20 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
25 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
26 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
27 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
28 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30 package org.pushingpixels.lafwidget.utils;
31
32 import java.util.*;
33
34 /**
35 * Delta queue. Follows a standard approach from OS world for effeciently
36 * keeping tracks of scheduled events.
37 *
38 * @author Kirill Grouchnikov
39 */
40 public class DeltaQueue {
41 /**
42 * Base class for entries in a {@link DeltaQueue}.
43 *
44 * @author Kirill Grouchnikov
45 */
46 public static abstract class Deltable {
47 /**
48 * Delta in application specific units.
49 */
50 protected int delta;
51
52 /**
53 * Creates a new delta.
54 */
55 public Deltable() {
56 super();
57 }
58
59 /**
60 * Returns the current delta in application specific units.
61 *
62 * @return The current delta in application specific units.
63 */
64 public int getDelta() {
65 return delta;
66 }
67
68 /**
69 * Sets the new value of delta in application specific units.
70 *
71 * @param delta
72 * New value of delta in application specific units.
73 */
74 public void setDelta(int delta) {
75 this.delta = delta;
76 }
77
78 /**
79 * Increments the delta value by the specified amount.
80 *
81 * @param diff
82 * Amount for incrementing the delta value.
83 */
84 public void incrementDelta(int diff) {
85 this.delta += diff;
86 }
87
88 /**
89 * Decrements the delta value by the specified amount.
90 *
91 * @param diff
92 * Amount for decrementing the delta value.
93 */
94 public void decrementDelta(int diff) {
95 this.delta -= diff;
96 }
97 }
98
99 /**
100 * Interface for comparing two delta instances.
101 *
102 * @author Kirill Grouchnikov.
103 */
104 public static interface DeltaMatcher {
105 /**
106 * Returns <code>true</code> if the specified delta matches some
107 * criteria.
108 *
109 * @param deltable
110 * Delta.
111 * @return <code>true</code> if the specified delta matches some
112 * criteria, <code>false</code> otherwise.
113 */
114 public boolean matches(Deltable deltable);
115 }
116
117 /**
118 * List of entries. Contains {@link Deltable}s.
119 */
120 protected ArrayList<Deltable> queue;
121
122 /**
123 * Constructs a new empty non-blocking synchronized delta queue.
124 */
125 public DeltaQueue() {
126 this.queue = new ArrayList<Deltable>();
127 }
128
129 /**
130 * Queues the specified deltable. The specified deltable is placed somewhere
131 * in the queue based on the initial value of its delta. Note that when this
132 * method returns, the value of a {@link Deltable#getDelta()} may have
133 * changed. Do not reuse or change the passed deltable after this method
134 * returns.
135 *
136 * @param deltable
137 * Deltable.
138 */
139 public synchronized void queue(Deltable deltable) {
140 // locate the correct position in a time-difference queue
141 int currDiff = deltable.getDelta();
142 for (int i = 0; i < this.queue.size(); i++) {
143 Deltable currDeltable = this.queue.get(i);
144 currDiff -= currDeltable.getDelta();
145 if (currDiff > 0) {
146 continue;
147 }
148
149 if (currDiff == 0) {
150 // scan until the next diff is more than 0
151 deltable.setDelta(0);
152 for (int j = i + 1; j < this.queue.size(); j++) {
153 Deltable nextDeltable = this.queue.get(j);
154 if (nextDeltable.getDelta() > 0) {
155 // put just before it
156 this.queue.add(j, deltable);
157 return;
158 }
159 }
160 // if here - add at the end
161 this.queue.add(this.queue.size(), deltable);
162 return;
163 }
164
165 deltable.setDelta(currDiff + currDeltable.getDelta());
166 currDeltable.decrementDelta(deltable.getDelta());
167 this.queue.add(i, deltable);
168 return;
169 }
170
171 // put last
172 deltable.setDelta(currDiff);
173 this.queue.add(this.queue.size(), deltable);
174 }
175
176 /**
177 * Returns all deltables that have at most specified delay left. The
178 * returned list may be empty.
179 *
180 * @param delay
181 * Delay.
182 * @return The possibly empty list of all deltables that have at most
183 * specified delay left.
184 */
185 public synchronized List<Deltable> dequeue(int delay) {
186 List<Deltable> result = new LinkedList<Deltable>();
187 while (this.queue.size() > 0) {
188 Deltable next = this.queue.get(0);
189 int timeToExpire = next.getDelta();
190 next.decrementDelta(delay);
191 if (next.getDelta() > 0) {
192 break;
193 }
194 if (timeToExpire > 0)
195 delay -= timeToExpire;
196 result.add(next);
197 this.queue.remove(0);
198 }
199 return result;
200 }
201
202 /**
203 * Removes all deltas matching the specified matcher.
204 *
205 * @param matcher
206 * Delta matcher.
207 */
208 public synchronized void removeMatching(DeltaMatcher matcher) {
209 // start from the end
210 while (true) {
211 int toRemoveInd = -1;
212 Deltable toRemove = null;
213 for (int i = this.queue.size() - 1; i >= 0; i--) {
214 Deltable deltable = this.queue.get(i);
215 if (!matcher.matches(deltable))
216 continue;
217 toRemoveInd = i;
218 toRemove = deltable;
219 break;
220 }
221
222 if (toRemoveInd >= 0) {
223 if (toRemoveInd < (this.queue.size() - 1)) {
224 Deltable next = this.queue.get(toRemoveInd + 1);
225 next.incrementDelta(toRemove.getDelta());
226 }
227 this.queue.remove(toRemoveInd);
228 } else {
229 return;
230 }
231 }
232 }
233
234 /**
235 * Dumps the contents of the delta queue.
236 */
237 public void dump() {
238 System.out.println("Dump");
239 for (int i = 0; i < this.queue.size(); i++) {
240 System.out.println("\t" + this.queue.get(i));
241 }
242 }
243
244 /**
245 * Test class.
246 *
247 * @author Kirill Grouchnikov
248 */
249 private static class DeltableTest extends Deltable {
250 /**
251 * ID.
252 */
253 private int id;
254
255 /**
256 * Creates a test delta.
257 *
258 * @param id
259 * ID.
260 * @param delta
261 * Delta.
262 */
263 public DeltableTest(int id, int delta) {
264 super();
265 this.id = id;
266 this.delta = delta;
267 }
268
269 public String toString() {
270 return this.id + ":" + this.delta;
271 }
272 }
273
274 /**
275 * For testing.
276 *
277 * @param args
278 * Ignored.
279 */
280 public static void main(String[] args) {
281 DeltaQueue dq = new DeltaQueue();
282 DeltableTest tpi11 = new DeltableTest(11, 100);
283 dq.queue(tpi11);
284 dq.dump();
285
286 DeltableTest tpi12 = new DeltableTest(12, 100);
287 dq.queue(tpi12);
288 dq.dump();
289
290 DeltableTest tpi21 = new DeltableTest(21, 200);
291 dq.queue(tpi21);
292 dq.dump();
293
294 DeltableTest tpi31 = new DeltableTest(31, 300);
295 dq.queue(tpi31);
296 dq.dump();
297
298 DeltableTest tpi13 = new DeltableTest(13, 100);
299 dq.queue(tpi13);
300 dq.dump();
301
302 DeltableTest tpi22 = new DeltableTest(22, 200);
303 dq.queue(tpi22);
304 dq.dump();
305
306 DeltableTest tpi25 = new DeltableTest(25, 250);
307 dq.queue(tpi25);
308 dq.dump();
309
310 DeltableTest tpi51 = new DeltableTest(51, 500);
311 dq.queue(tpi51);
312 dq.dump();
313
314 DeltableTest tpi05 = new DeltableTest(5, 50);
315 dq.queue(tpi05);
316 dq.dump();
317
318 List<Deltable> gr150 = dq.dequeue(100);
319 System.out.println("Dump 150");
320 for (int i = 0; i < gr150.size(); i++) {
321 DeltableTest tpi = (DeltableTest) gr150.get(i);
322 System.out.println("\t" + tpi);
323 }
324 dq.dump();
325
326 dq.removeMatching(new DeltaMatcher() {
327 @Override
328 public boolean matches(Deltable deltable) {
329 return ((DeltableTest) deltable).id < 30;
330 }
331 });
332 dq.dump();
333
334 TrackableThread.requestStopAllThreads();
335 }
336 }