|
1
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.Iterator ;
17 import java.util.List ;
18 import java.util.SortedSet ;
19
20 import org.eclipse.core.runtime.IProgressMonitor;
21
22
25 class SortUtil {
26
27
36 public static MarkerList getFirst(MarkerList elements, Comparator c, int k,
37 IProgressMonitor mon) {
38 Collection start = elements.asList();
39 Collection result = new ArrayList (start.size());
40
41 mon.beginTask(MarkerMessages.SortUtil_finding_first, 1000);
42
43 getFirst(result, start, c, k, mon, 1000);
44
45 mon.done();
46
47 return new MarkerList(result);
48 }
49
50 private static void getFirst(Collection result, Collection elements,
51 Comparator c, int k, IProgressMonitor mon, int totalWork) {
52
53 if (mon.isCanceled()) {
54 return;
55 }
56
57 if (elements.size() <= k) {
58 result.addAll(elements);
59 mon.worked(totalWork);
60 return;
61 }
62
63 Object pivot;
64
65 if (elements instanceof ArrayList ) {
66 pivot = ((ArrayList ) elements).get(elements.size() / 2);
67 } else {
68 pivot = elements.iterator().next();
69 }
70 Collection more = new ArrayList (elements.size());
71 Collection less = new ArrayList (elements.size());
72 Collection equal = new ArrayList ();
73
74 partitionHelper(less, more, equal, elements, c, pivot, mon,
75 totalWork / 2);
76
77 if (less.size() >= k) {
78 getFirst(result, less, c, k, mon, totalWork / 2);
79 } else if (less.size() + equal.size() >= k) {
80
81 int count = k - less.size();
82
83 result.addAll(less);
84
85 Iterator iter = equal.iterator();
86 while (iter.hasNext() && count > 0) {
87 Object next = iter.next();
88
89 result.add(next);
90 count--;
91 }
92 mon.worked(totalWork / 2);
93 } else if (less.size() + equal.size() + more.size() >= k) {
94 result.addAll(less);
95 result.addAll(equal);
96
97 getFirst(result, more, c, k - less.size() - equal.size(), mon,
98 totalWork / 2);
99 }
100 }
101
102 private static void partitionHelper(Collection less, Collection more,
103 Collection equal, Collection input, Comparator c, Object toTest,
104 IProgressMonitor mon, int totalWork) {
105 int workRemaining = totalWork;
106 int counter = 0;
107 int totalItems = input.size();
108
109 Iterator iter = input.iterator();
110
111 while (iter.hasNext()) {
112 Object next = iter.next();
113
114 int compareResult = c.compare(next, toTest);
115
116 if (compareResult < 0) {
117 less.add(next);
118 } else if (compareResult > 0) {
119 more.add(next);
120 } else {
121 equal.add(next);
122 }
123
124 counter++;
125 if (counter > 100) {
126 if (mon.isCanceled()) {
127 return;
128 }
129 int nextWorked = counter * workRemaining / totalItems;
130 mon.worked(nextWorked);
131 workRemaining -= nextWorked;
132 totalItems -= counter;
133 counter = 0;
134 }
135 }
136
137 mon.worked(workRemaining);
138 }
139
140
155 public static void partition(Collection less, Collection more,
156 Collection equal, Collection input, Comparator c, Object toTest,
157 IProgressMonitor mon) {
158 mon
159 .beginTask(
160 MarkerMessages.SortUtil_partitioning, input.size());
161
162 if (toTest == null || c == null) {
163 int counter = 0;
164 Iterator iter = input.iterator();
165 while (iter.hasNext()) {
166 Object next = iter.next();
167
168 counter++;
169 if (counter >= 20) {
170 mon.worked(counter);
171 counter = 0;
172 if (mon.isCanceled()) {
173 return;
174 }
175 }
176
177 more.add(next);
178 }
179 mon.worked(counter);
180 } else {
181 partitionHelper(less, more, equal, input, c, toTest, mon, input
182 .size());
183 }
184
185 mon.done();
186 }
187
188
195 public static List removeFirst(Collection collection, int numToRemove) {
196 int toRemove = Math.min(collection.size(), numToRemove);
197
198 List removed = new ArrayList (toRemove);
199
200 Iterator iter = collection.iterator();
201
202 for (int idx = 0; idx < toRemove; idx++) {
203 removed.add(iter.next());
204
205 iter.remove();
206 }
207
208 return removed;
209 }
210
211
219 public static Object findGreatest(Collection toSearch, Comparator c) {
220 if (toSearch instanceof SortedSet
222 && ((SortedSet ) toSearch).comparator().equals(c)) {
223 return ((SortedSet ) toSearch).last();
224 }
225
226 Object result = null;
228 Iterator iter = toSearch.iterator();
229
230 while (iter.hasNext()) {
231 Object next = iter.next();
232
233 if (result == null || c.compare(result, next) > 0) {
234 result = next;
235 }
236 }
237
238 return result;
239 }
240 }
241 |
Popular Tags |
Java API By Example, From Geeks To Geeks.