Java > Open Source Codes > org > eclipse > ui > views > markers > internal > DeferredQueue


1 /*******************************************************************************
2  * Copyright (c) 2000, 2004 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.ui.views.markers.internal;
12
13 import java.util.ArrayList ;
14 import java.util.Collection ;
15 import java.util.Comparator ;
16 import java.util.HashSet ;
17 import java.util.Iterator ;
18 import java.util.List ;
19 import java.util.Set ;
20 import java.util.TreeSet ;
21
22 import org.eclipse.core.runtime.IProgressMonitor;
23 import org.eclipse.core.runtime.NullProgressMonitor;
24 import org.eclipse.core.runtime.SubProgressMonitor;
25 import org.eclipse.jface.viewers.TableViewer;
26 import org.eclipse.swt.widgets.Table;
27
28 /**
29  * Contains a queue of changes to be applied to a particular TableViewer.
30  * This object is not multithread-friendly. The owning object must synchronize
31  * its access to this object such that no two threads attempt to access it
32  * simultaneously.
33  */
34 final class DeferredQueue {
35
36     private static final String SETTING_CONTENTS = Messages
37             .getString("DeferredQueue.setting_contents"); //$NON-NLS-1$
38
39     /**
40      * Maximum number of items to be added or removed from the viewer in a single update.
41      * (Will be used for an initially empty table)
42      */
43     private static final int MAX_UPDATE = 40;
44
45     /**
46      * Minimum number of items to be added or removed from the viewer in a single update
47      * (Will be used once the table size reaches (GROWTH_LIMIT)
48      */
49     private static final int MIN_UPDATE = 1;
50
51     /**
52      * Table size beyond which all updates will be approximately MIN_UPDATE
53      */
54     private static final int GROWTH_LIMIT = 20000;
55
56     // Member variables
57
58     /**
59      * Current sort order (note that this object does the sorting -- not the viewer. The
60      * view contents are sorted by controlling their insertion order and position.)
61      */
62     private Comparator sortOrder;
63
64     /**
65      * Set of items currently visible in the viewer
66      */
67     private Set visibleItems = new HashSet ();
68
69     /**
70      * Set of pending insertions that will occur at the end of the table (if the
71      * viewer is sorted, this will be changed into a sorted collection). This
72      * will not contain any items currently in the visibleItems set.
73      */
74     private Set insertionsAtEnd = new HashSet ();
75
76     /**
77      * Set of pending insertions that will occur in the middle of the table. This
78      * remains unsorted. Sorting will occur in the UI thread at insertion-time.
79      * This will not contain any items currently in the visibleItems set.
80      */
81     private Set insertionsInMiddle = new HashSet ();
82
83     /**
84      * List of pending removals. This is a subset of visibleItems.
85      */
86     private Set pendingRemovals = new HashSet ();
87
88     /**
89      * List of pending changes. This is a subset of visibleItems.
90      */
91     private Set pendingChanges = new HashSet ();
92
93     /**
94      * Pointer to the item currently at the end of the table, or null if
95      * the table is currently empty.
96      */
97     private Object lastVisible = null;
98
99     /**
100      * True iff there may be items inthe insertionsInMiddle queue
101      * that can be moved to the insertionsAtEnd queue. This is set to
102      * true when lastVisible is reduced, and set to false when
103      * insertionsInMiddle is repartitioned.
104      */
105     private boolean lastDirty = false;
106
107     /**
108      * pointer to the viewer being populated.
109      */
110     private TableViewer viewer;
111
112     private boolean hasPendingChanges = false;
113
114     /**
115      * Constructs a new DeferredQueue.
116      *
117      * @param viewer
118      */
119     public DeferredQueue(TableViewer viewer) {
120         this.viewer = viewer;
121     }
122
123     /**
124      * Returns the set of items currently visible in the viewer (read-only)
125      *
126      * @return the set of processed items
127      */
128     public Object [] getVisibleItems() {
129         synchronized (visibleItems) {
130             return visibleItems.toArray();
131         }
132     }
133
134     /**
135      * Queues the given set of items to be refreshed in the viewer. If there
136      * are any items in the viewer (or its queues) that compare as equal(...)
137      * to one of these items, the new item will replace the old one. Should
138      * be run in a background thread.
139      *
140      * @param changes set if items to be refreshed in the viewer
141      */
142     public void change(Collection changes) {
143         Iterator iter = changes.iterator();
144
145         while (iter.hasNext()) {
146             Object next = iter.next();
147             boolean isVisible = false;
148             synchronized (visibleItems) {
149                 if (visibleItems.contains(next)) {
150                     visibleItems.remove(next);
151                     visibleItems.add(next);
152                     pendingChanges.add(next);
153                     isVisible = true;
154                     hasPendingChanges = true;
155                 }
156             }
157
158             if (!isVisible) {
159                 if (insertionsInMiddle.contains(next)) {
160                     insertionsInMiddle.remove(next);
161                     insertionsInMiddle.add(next);
162                     hasPendingChanges = true;
163                 } else if (insertionsAtEnd.contains(next)) {
164                     insertionsAtEnd.remove(next);
165                     insertionsAtEnd.add(next);
166                     hasPendingChanges = true;
167                 }
168             }
169         }
170     }
171
172     /**
173      * Sets the desired contents of the viewer, enqueueing any additions and removals
174      * necessary such that the final contents of the viewer will be as specified.
175      * Should be run in a background thread. If the given montor is canceled (possibly
176      * in another thread), the operation will be aborted without modifying the queue.
177      *
178      * @param newPendingContents desired contents of the viewer
179      * @param mon progress monitor
180      */
181     public void set(Collection newPendingContents, IProgressMonitor mon) {
182         mon.beginTask(SETTING_CONTENTS, 100);
183
184         // Set of items in newPendingContents that are not currently in visibleItems
185 Set newInsertions = new HashSet ();
186
187         // New pendingRemovals queue
188 Set newPendingRemovals = new HashSet ();
189         // New insertionsInMiddle queue
190 Set newInsertionsInMiddle = new HashSet ();
191         // New insertionsAtEnd queue
192 Set newInsertionsAtEnd = newEndSet();
193
194         addWithProgress(newInsertions, newPendingContents, mon, 5);
195         synchronized (visibleItems) {
196             addWithProgress(newPendingRemovals, visibleItems, mon, 5);
197             removeWithProgress(newPendingRemovals, newInsertions, mon, 5);
198             removeWithProgress(newInsertions, visibleItems, mon, 5);
199         }
200
201         if (newInsertions.isEmpty() && newPendingRemovals.isEmpty()) {
202             return;
203         }
204
205         SubProgressMonitor sub = new SubProgressMonitor(mon, 80);
206         SortUtil.partition(newInsertionsInMiddle, newInsertionsAtEnd,
207                 newInsertionsAtEnd, newInsertions, sortOrder, lastVisible, sub);
208
209         // Do nothing if the operation was cancelled.
210 if (mon.isCanceled()) {
211             mon.done();
212             return;
213         }
214
215         // Now we've computed everything. Apply all the computed changes.
216 hasPendingChanges = true;
217         lastDirty = false;
218         insertionsAtEnd.clear();
219         insertionsAtEnd = newInsertionsAtEnd;
220
221         insertionsInMiddle.clear();
222         insertionsInMiddle = newInsertionsInMiddle;
223
224         pendingRemovals.clear();
225         pendingRemovals = newPendingRemovals;
226
227         mon.done();
228     }
229
230     /**
231      * Applies the next set of changes to the table. Returns the number of items
232      * actually refreshed. Must run in the UI thread.
233      *
234      * @param maximumToChange maximum number of queued changes to apply
235      * @return the number of changes actually applied.
236      */
237     private int nextChange(int maximumToChange) {
238         Collection result = SortUtil.removeFirst(pendingChanges,
239                 maximumToChange);
240
241         viewer.update(result.toArray(), null);
242
243         return result.size();
244     }
245
246     /**
247      * Applies the next set of removals from the table. Must run in the UI thread.
248      *
249      * @param maximumToRemove maximum number of items to remove from the table.
250      * @return the number of items actually removed.
251      */
252     private int nextRemoval(int maximumToRemove) {
253         ArrayList result = new ArrayList (maximumToRemove);
254
255         int counter = maximumToRemove;
256
257         Iterator iter = pendingRemovals.iterator();
258         while (iter.hasNext() && counter > 0) {
259             Object next = iter.next();
260
261             result.add(next);
262
263             if (lastVisible != null && lastVisible.equals(next)) {
264                 lastDirty = true;
265             }
266
267             iter.remove();
268             counter--;
269         }
270
271         synchronized (visibleItems) {
272             visibleItems.removeAll(result);
273         }
274
275         viewer.remove(result.toArray());
276
277         if (lastDirty) {
278             lastVisible = viewer
279                     .getElementAt(viewer.getTable().getItemCount() - 1);
280         }
281
282         return result.size();
283     }
284
285     /**
286      * Applies the next set of insertions into the middle of the queue.
287      *
288      * @param maximumToInsert
289      * @return
290      */
291     private int nextInsertionInMiddle(int maximumToInsert) {
292
293         refreshQueues(new NullProgressMonitor());
294
295         Collection result = SortUtil.removeFirst(insertionsInMiddle,
296                 maximumToInsert);
297
298         synchronized (visibleItems) {
299             visibleItems.addAll(result);
300         }
301
302         // We manually compute the insertion position because setting a sorter on
303 // the viewer would force a refresh, which can be very slow with a large number
304 // of items.
305
306         Iterator iter = result.iterator();
307         while (iter.hasNext()) {
308             Object element = iter.next();
309
310             int insertionPos = getInsertPosition(element);
311             viewer.insert(element, insertionPos);
312         }
313
314         return result.size();
315     }
316
317     /**
318      * Applies the next insertion at the end of the table. Returns the number of
319      * items actually inserted.
320      *
321      * @param maximumToInsert maximum number of items to insert into the end
322      * of the table
323      * @return the number of items actually inserted into the table
324      */
325     private int nextInsertionAtEnd(int maximumToInsert) {
326         refreshQueues(new NullProgressMonitor());
327
328         List result = new ArrayList (maximumToInsert);
329
330         Iterator iter = insertionsAtEnd.iterator();
331         for (int counter = 0; counter < maximumToInsert && iter.hasNext(); counter++) {
332             lastVisible = iter.next();
333
334             result.add(lastVisible);
335
336             iter.remove();
337         }
338
339         synchronized (visibleItems) {
340             visibleItems.addAll(result);
341         }
342
343         viewer.add(result.toArray());
344
345         return result.size();
346     }
347
348     /**
349      * Clears the set of visible items, and reinserts everything from scratch.
350      */
351     public void reset() {
352         synchronized (visibleItems) {
353             visibleItems.removeAll(pendingRemovals);
354
355             insertionsInMiddle.addAll(visibleItems);
356             lastVisible = null;
357             lastDirty = true;
358
359             visibleItems.clear();
360         }
361         pendingRemovals.clear();
362         hasPendingChanges = true;
363     }
364
365     /**
366      * Returns true iff there are pending changes remaining to be applied.
367      *
368      * @return true iff there are pending changes to be applied to the table
369      */
370     public boolean hasPendingChanges() {
371         return hasPendingChanges;
372     }
373
374     /**
375      * Returns an estimate of the work remaining (the result is meaningful with respect
376      * to the return value of nextUpdate())
377      *
378      * @return an estimate of the work remaining
379      */
380     public int workRemaining() {
381         return pendingRemovals.size() + insertionsAtEnd.size()
382                 + insertionsInMiddle.size() + pendingChanges.size();
383     }
384
385     /**
386      *
387      * Cancels all pending insertions and removals.
388      */
389     public void cancelPending() {
390         insertionsAtEnd.clear();
391         insertionsInMiddle.clear();
392         pendingRemovals.clear();
393         hasPendingChanges = false;
394     }
395
396     public void setComparator(Comparator c) {
397         if (sortOrder == c) {
398             return;
399         }
400
401         sortOrder = c;
402
403         lastVisible = null;
404
405         insertionsInMiddle.addAll(insertionsAtEnd);
406         insertionsAtEnd = newEndSet();
407         lastDirty = true;
408
409         reset();
410     }
411
412     /**
413      * Applies any deferred sorting.
414      * @param mon
415      */
416     public void refreshQueues(IProgressMonitor mon) {
417         if (lastDirty) {
418             if (mon.isCanceled()) {
419                 return;
420             }
421             HashSet newInsertionsInMiddle = new HashSet ();
422             SortUtil.partition(newInsertionsInMiddle, insertionsAtEnd,
423                     insertionsAtEnd, insertionsInMiddle, sortOrder,
424                     lastVisible, mon);
425
426             if (mon.isCanceled()) {
427                 insertionsInMiddle.removeAll(insertionsAtEnd);
428             } else {
429                 insertionsInMiddle = newInsertionsInMiddle;
430                 lastDirty = false;
431             }
432         }
433     }
434
435     /**
436      * Determines the insertion position for the given element in the table. Note
437      * that this is essentially the same as TableViewer.getInsertPosition, but we
438      * need to do it here because if we set a sorter on the TableViewer, this will
439      * force a refresh of the table which can be extremely slow.
440      *
441      * @param element object whose insertion position is being computed.
442      * @return
443      */
444     private int getInsertPosition(Object element) {
445         Table table = viewer.getTable();
446         if (sortOrder == null)
447             return table.getItemCount();
448         int count = table.getItemCount();
449         int min = 0, max = count - 1;
450         while (min <= max) {
451             int mid = (min + max) / 2;
452             Object data = table.getItem(mid).getData();
453             int compare = sortOrder.compare(data, element);
454             if (compare == 0) {
455                 // find first item > element
456 while (compare == 0) {
457                     ++mid;
458                     if (mid >= count) {
459                         break;
460                     }
461                     data = table.getItem(mid).getData();
462                     compare = sortOrder.compare(data, element);
463                 }
464                 return mid;
465             }
466             if (compare < 0)
467                 min = mid + 1;
468             else
469                 max = mid - 1;
470         }
471         return min;
472     }
473
474     /**
475      * Performs a single update to the viewer. Based on the contents of the pending* queues,
476      * items will either be removed, added, or refreshed in the viewer (in that order). This
477      * should only be called within a synchronized block, since the various queues shouldn't
478      * be modified during an update. This method is invoked repeatedly by jobs to gradually
479      * apply the pending changes.
480      */
481     public int nextUpdate() {
482
483         int pendingRemovalsSize = pendingRemovals.size();
484
485         if (pendingRemovalsSize > 0) {
486             int currentSize = countVisibleItems();
487             // Determine if we should remove incrementally or rebuild the table from scratch.
488 int finalSize = currentSize - pendingRemovalsSize;
489
490             if (finalSize * finalSize * 2 <= currentSize * currentSize) {
491
492                 // If we're removing enough items that it would be faster just to rebuild
493 // the table from scratch, do it that way.
494
495                 reset();
496                 getViewer().refresh();
497
498                 return 0;
499             }
500
501             return nextRemoval(nextUpdateSize());
502         } else if (insertionsInMiddle.size() > 0) {
503             return nextInsertionInMiddle(nextUpdateSize());
504         } else if (insertionsAtEnd.size() > 0) {
505             return nextInsertionAtEnd(MAX_UPDATE);
506         } else if (pendingChanges.size() > 0) {
507             return nextChange(MAX_UPDATE);
508         }
509
510         hasPendingChanges = false;
511
512         return 0;
513     }
514
515     /**
516      * @return
517      */
518     int countVisibleItems() {
519         synchronized (visibleItems) {
520             return visibleItems.size();
521         }
522     }
523
524     /**
525      * Returns the number of items that should be added or removed in the next
526      * incremental update. This is used for the operations whose runtime increases
527      * with the size of the visible items.
528      *
529      * @return the number of changes that should be applied in the next update
530      */
531     private int nextUpdateSize() {
532         int size = GROWTH_LIMIT * (MAX_UPDATE - MIN_UPDATE)
533                 / (GROWTH_LIMIT + countVisibleItems()) + MIN_UPDATE;
534
535         return size;
536     }
537
538     /**
539      * Returns the TableViewer that is being populated.
540      *
541      * @return the TableViewer that is being modified.
542      */
543     public TableViewer getViewer() {
544         return viewer;
545     }
546
547     /**
548      * Returns a new empty set to be used for insertionsAtEnd
549      *
550      * @return
551      */
552     private Set newEndSet() {
553         if (sortOrder == null) {
554             return new HashSet ();
555         } else {
556             return new TreeSet (sortOrder);
557         }
558     }
559
560     /**
561      * Removes all the given items from the target collection, and updates
562      * the given progress monitor by the given amount. If the monitor is cancelled,
563      * no changes are made to the target collection.
564      *
565      * @param target items will be removed from this collection
566      * @param toRemove items to be removed from the collection
567      * @param mon progress monitor to be updated
568      * @param worked amount to update the monitor
569      */
570     private static void removeWithProgress(Collection target,
571             Collection toRemove, IProgressMonitor mon, int worked) {
572         if (mon.isCanceled()) {
573             return;
574         }
575
576         target.removeAll(toRemove);
577
578         mon.worked(worked);
579     }
580
581     /**
582      * Inserts all the given items into the target collection, and updates
583      * the progress monitor. If the monitor is cancelled, no changes will
584      * be made to the target.
585      *
586      * @param target collection into which items will be inserted
587      * @param toInsert items to be inserted into the collection
588      * @param mon progress monitor that will be updated
589      * @param worked amount to update the progress monitor
590      */
591     private static void addWithProgress(Collection target, Collection toInsert,
592             IProgressMonitor mon, int worked) {
593         if (mon.isCanceled()) {
594             return;
595         }
596
597         target.addAll(toInsert);
598
599         mon.worked(worked);
600     }
601
602     /**
603      * @return
604      */
605     public Comparator getSorter() {
606         return sortOrder;
607     }
608
609 }
610

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags