| 1 | /******************************************************************************* |
| 2 | * Copyright (c) 2000, 2006 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.Iterator; |
| 17 | import java.util.List; |
| 18 | import java.util.SortedSet; |
| 19 | |
| 20 | import org.eclipse.core.runtime.IProgressMonitor; |
| 21 | |
| 22 | /** |
| 23 | * |
| 24 | */ |
| 25 | class SortUtil { |
| 26 | |
| 27 | /** |
| 28 | * * Returns the k smallest items in the given collection. Runs in |
| 29 | * O(n) time, average case. The resulting collection is not sorted. |
| 30 | * @param elements the MarkerList to check |
| 31 | * @param c the comparator |
| 32 | * @param k the number of items to collect |
| 33 | * @param mon the monitor |
| 34 | * @return MarkerList |
| 35 | */ |
| 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 | /** |
| 141 | * Divides the items in the input collection into three sets based on whether they are less than, |
| 142 | * equal to, or greater than the test item. |
| 143 | * |
| 144 | * If the given monitor is cancelled (possibly by another thread), the operation will |
| 145 | * be aborted. In this case, the insertions may only be partially complete. |
| 146 | * |
| 147 | * @param less |
| 148 | * @param more |
| 149 | * @param equal |
| 150 | * @param input |
| 151 | * @param c |
| 152 | * @param toTest |
| 153 | * @param mon |
| 154 | */ |
| 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 | /** |
| 189 | * Removes and returns the first n items from the given collection. |
| 190 | * |
| 191 | * @param collection |
| 192 | * @param numToRemove |
| 193 | * @return List |
| 194 | */ |
| 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 | /** |
| 212 | * Finds and returns the greatest element in the given collection, or null if the collection |
| 213 | * is empty. |
| 214 | * |
| 215 | * @param toSearch collection to search |
| 216 | * @param c comparator used to determine the greatest item |
| 217 | * @return the greatest item in the collection |
| 218 | */ |
| 219 | public static Object findGreatest(Collection toSearch, Comparator c) { |
| 220 | // If this set is already sorted using the given comparator, just return the last element |
| 221 | if (toSearch instanceof SortedSet |
| 222 | && ((SortedSet) toSearch).comparator().equals(c)) { |
| 223 | return ((SortedSet) toSearch).last(); |
| 224 | } |
| 225 | |
| 226 | // Otherwise, exhaustively search for the greatest element |
| 227 | 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 | } |