1 /*
2 * File: DefaultOverlapStrategy.java
3 * Copyright (c) 2004-2007 Peter Kliem (Peter.Kliem@jaret.de)
4 * A commercial license is available, see http://www.jaret.de.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20 package de.jaret.util.ui.timebars.strategy;
21
22 import java.util.ArrayList;
23 import java.util.Arrays;
24 import java.util.Collection;
25 import java.util.Collections;
26 import java.util.Comparator;
27 import java.util.HashMap;
28 import java.util.List;
29 import java.util.Map;
30 import java.util.SortedMap;
31 import java.util.TreeMap;
32
33 import de.jaret.util.date.Interval;
34 import de.jaret.util.date.IntervalImpl;
35 import de.jaret.util.ui.timebars.TimeBarViewerDelegate;
36 import de.jaret.util.ui.timebars.model.TimeBarRow;
37
38 /**
39 * Default implementation of an overlap strategy that does a complete check on overlaps between intervals including
40 * transitive overlaps. This can be time consuming when dealing with a lot of intervals.
41 *
42 * Thanks go to Mathias Kurt for supplying an optimized algorithm for computing the overlapping quite fast.
43 *
44 * @author kliem
45 * @version $Id: $
46 */
47 public class DefaultOverlapStrategy implements IOverlapStrategy {
48 /** the delegate the strategy works for. */
49 protected TimeBarViewerDelegate _delegate;
50 /** Cache for overlap infos. */
51 protected Map<TimeBarRow, Map<Interval, OverlapInfo>> _oiRowCache = new HashMap<TimeBarRow, Map<Interval, OverlapInfo>>();
52
53 /** if set to false, intervals will be sorted before checking overlapping. */
54 protected boolean _assumeSortedIntervals = true;
55
56 /**
57 * Construct a default strategy for a specific delegate.
58 *
59 * @param delegate the delegate the strategy works for
60 */
61 public DefaultOverlapStrategy(TimeBarViewerDelegate delegate) {
62 _delegate = delegate;
63 }
64
65 /**
66 * {@inheritDoc}
67 */
68 public OverlapInfo getOverlapInfo(TimeBarRow row, Interval interval) {
69 Map<Interval, OverlapInfo> oiIntervalMap = _oiRowCache.get(row);
70 if (oiIntervalMap == null) {
71 oiIntervalMap = updateOICache(row);
72 }
73 OverlapInfo oi = oiIntervalMap.get(interval);
74 return oi;
75 }
76
77 /**
78 * {@inheritDoc}
79 */
80 public int getMaxOverlapCount(TimeBarRow row) {
81 // TODO caching
82 Map<Interval, OverlapInfo> oiIntervalMap = _oiRowCache.get(row);
83 if (oiIntervalMap == null) {
84 oiIntervalMap = updateOICache(row);
85 }
86 int max = 0;
87 Collection<OverlapInfo> infos = oiIntervalMap.values();
88 for (OverlapInfo overlapInfo : infos) {
89 if (overlapInfo.maxOverlapping > max) {
90 max = overlapInfo.maxOverlapping;
91 }
92 }
93 return max + 1;
94 }
95
96 /**
97 * {@inheritDoc} Assumes sorted intervals unless <code>assumeSortedIntervals</code> is set to false.
98 */
99 public Map<Interval, OverlapInfo> updateOICache(TimeBarRow row) {
100 // all intervals in the row
101 List<Interval> intervals = _delegate.filterIntervals(row.getIntervals());
102 // result is an overlap information for each interval
103 Map<Interval, OverlapInfo> result = new HashMap<Interval, OverlapInfo>();
104
105 // if intervals are not sorted: sort in advance by begin timestamp
106 if (!_assumeSortedIntervals) {
107 List<Interval> temp = new ArrayList<Interval>(intervals.size());
108 temp.addAll(intervals);
109 Collections.sort(temp, new Comparator<Interval>() {
110 public int compare(Interval o1, Interval o2) {
111 return (int) (o1.getBegin().getDate().getTime() - o2.getBegin().getDate().getTime());
112 }
113 });
114 intervals = temp;
115 }
116
117 // build a array of indices, sorted according to the start time
118 Integer[] sortedStartTime = new Integer[intervals.size()];
119 for (int i = 0; i < intervals.size(); i++) {
120 sortedStartTime[i] = i;
121 }
122 final List<Interval> finalIntervals = intervals;
123 Arrays.sort(sortedStartTime, new Comparator<Integer>() {
124 public int compare(Integer o1, Integer o2) {
125 return finalIntervals.get(o1).getBegin().compareTo(finalIntervals.get(o2).getBegin());
126 }
127 });
128
129 // map max end time of the list so far on index in sortedStartTime
130 TreeMap<Long, Integer> mapEndTime = new TreeMap<Long, Integer>();
131 long maxEndTime = Long.MIN_VALUE;
132 for (int i = 0; i < sortedStartTime.length; i++) {
133 Interval interval1 = intervals.get(sortedStartTime[i]);
134 maxEndTime = Math.max(maxEndTime, interval1.getEnd().getDate().getTime());
135 mapEndTime.put(maxEndTime, i);
136 }
137
138 // list of all overlapinfos
139 List<OverlapInfo> oList = new ArrayList<OverlapInfo>();
140 // create overlap information for all intervals in the row
141 for (int i = 0; i < intervals.size(); i++) {
142 Interval interval = intervals.get(i);
143 OverlapInfo oi = new OverlapInfo();
144 oi.interval = interval;
145 result.put(interval, oi);
146 oList.add(oi);
147
148 // collect intersecting intervals for each interval and store the intersecting intervals in the
149 // overlap information.
150
151 // java 5
152 SortedMap<Long, Integer> first = mapEndTime.subMap(0L, interval.getBegin().getDate().getTime());
153 int startIdx = (first.size() == 0 ? 0 : first.get(first.lastKey()));
154 // Java 6 (mapEndTime should be a navigable map than)
155 // Map.Entry<Long, Integer> first = mapEndTime.floorEntry(interval.getBegin().getDate().getTime() - 1);
156 // int startIdx = (null == first ? 0 : first.getValue());
157 for (int y = startIdx; y < sortedStartTime.length; y++) {
158 int x = sortedStartTime[y];
159 if (i == x) {
160 continue;
161 }
162 Interval cmp = intervals.get(x);
163 if (0 < cmp.getBegin().compareTo(interval.getEnd())) {
164 break;
165 }
166 if (IntervalImpl.intersectNonIncluding(interval, cmp)) {
167 oi.overlapping.add(cmp);
168 }
169 }
170
171 // set the current values
172 oi.overlappingCount = oi.overlapping.size();
173 oi.maxOverlapping = oi.overlappingCount;
174
175 }
176
177 // now get the transitive overlaps for eachinterval
178
179 for (OverlapInfo oi : oList) {
180 Interval interval = oi.interval;
181
182 // verify maxOverlapping
183 int max = 0;
184 int cur = 0;
185 for (Interval check : oi.overlapping) {
186 if (check.contains(interval.getBegin())) {
187 cur++;
188 }
189 }
190 if (cur > max) {
191 max = cur;
192 }
193 cur = 0;
194 for (Interval check : oi.overlapping) {
195 if (check.contains(interval.getEnd())) {
196 cur++;
197 }
198 }
199 if (cur > max) {
200 max = cur;
201 }
202
203 for (Interval check : oi.overlapping) {
204 if (interval.contains(check.getBegin())) {
205 cur = 1;
206 for (Interval check2 : oi.overlapping) {
207 if (!check.equals(check2)) {
208 if (IntervalImpl.containsNonIncluding(check2, check.getBegin())) {
209 cur++;
210 }
211 }
212 }
213 if (cur > max) {
214 max = cur;
215 }
216 }
217 }
218 for (Interval check : oi.overlapping) {
219 if (interval.contains(check.getEnd())) {
220 cur = 1;
221 for (Interval check2 : oi.overlapping) {
222 if (!check.equals(check2)) {
223 if (IntervalImpl.containsNonIncluding(check2, check.getEnd())) {
224 cur++;
225 }
226 }
227 }
228 if (cur > max) {
229 max = cur;
230 }
231 }
232 }
233
234 oi.maxOverlapping = max;
235 oi.overlappingCount = max;
236 }
237
238 // sort oList by overlap count for further processing
239 // intrevals with only some overlaps will be done first
240 // there might be scenarios that would require another order.
241 Collections.sort(oList, new Comparator<OverlapInfo>() {
242 public int compare(OverlapInfo arg0, OverlapInfo arg1) {
243 return -arg1.overlappingCount - arg0.overlappingCount;
244 }
245 });
246
247 // retrieve the maximum number of overlapping intervals for a single interval including transitive overlaps
248 // This runs unless no more changes will be encountered
249 calcTransitiveOverlaps(result, oList);
250
251 // positions
252 // go through all overlap infos and assign positions
253 for (int i = 0; i < oList.size(); i++) {
254 OverlapInfo oi = oList.get(i);
255 assignPosition(oi, result);
256 // check whether a position could be assigned
257 // in rare conditions the code above will not be concise
258 if (oi.pos == -1) {
259 // no position assigned --> correct maxoverlapping and do another round
260 oi.maxOverlapping = oi.maxOverlapping + 1;
261 // recalc transitive overlaps and assign position again
262 calcTransitiveOverlaps(result, oList);
263 assignPosition(oi, result);
264 }
265 }
266
267 // put to cache
268 _oiRowCache.put(row, result);
269 return result;
270 }
271
272 /**
273 * Calculate the tansitive overlaps for all interval. The algorith will run several times until no more changes will
274 * be encountered.
275 *
276 * @param result map interval, overlapinfo that holds the information of the complete row
277 * @param oList all overlap information objects as a list
278 */
279 private void calcTransitiveOverlaps(Map<Interval, OverlapInfo> result, List<OverlapInfo> oList) {
280 boolean change = true;
281 while (change) {
282 change = false;
283 for (int i = 0; i < oList.size(); i++) {
284 OverlapInfo oi = oList.get(i);
285 int max = getMaxOverlapping(oi, result);
286 if (max != oi.maxOverlapping) {
287 oi.maxOverlapping = max;
288 change = true;
289 }
290 }
291 }
292 }
293
294 /**
295 * Check and assign a position in the row to the gievn interval in th eoverlap information.
296 *
297 * @param oi the overlap information that should be processed
298 * @param result map interval, overlapinfo that holds the information of the complete row
299 */
300 private void assignPosition(OverlapInfo oi, Map<Interval, OverlapInfo> result) {
301 // position array for all overlapping intervals initialized with -1
302 int[] positions = new int[oi.maxOverlapping + 1];
303 for (int p = 0; p < oi.maxOverlapping + 1; p++) {
304 positions[p] = -1;
305 }
306 // fill in positions of overlapping intervals that already have an assigned position
307 for (Interval interval : oi.overlapping) {
308 OverlapInfo o = result.get(interval);
309 if (o.pos != -1) {
310 positions[o.pos] = o.pos;
311 }
312 }
313 // If the current overlap information does not have an assigned position yet,
314 // find an empty slot and assign it
315 if (oi.pos == -1) {
316 for (int p = 0; p < oi.maxOverlapping + 1; p++) {
317 if (positions[p] == -1) {
318 oi.pos = p;
319 positions[p] = p;
320 break;
321 }
322 }
323 }
324 }
325
326 // dump a row for debugging
327 // private void dumpRow(TimeBarRow row) {
328 // System.err.println("Row dump " + row);
329 // System.err.println("DefaultTimeBarRowModel row = new DefaultTimeBarRowModel(new DefaultRowHeader(\"abc\"));");
330 // for (Interval interval : row.getIntervals()) {
331 // System.err.println("i = new OtherIntervalImpl(new JaretDate(" + interval.getBegin().getDate().getTime()
332 // + "L), new JaretDate(" + interval.getEnd().getDate().getTime() + "L));");
333 // System.err.println("i.setLabel(\"" + interval.toString() + "\");");
334 // System.err.println("row.addInterval(i);");
335 // }
336 // }
337
338 /**
339 * Retrieve the maximum count of overlapping intervals for all overlapping intervals registered in an overlapInfo.
340 *
341 * @param oi OverlapInfo
342 * @param map map containing the overlapinfos of all intervals
343 * @return the maximum overlap count of all overlapping intervals
344 */
345 private int getMaxOverlapping(OverlapInfo oi, Map<Interval, OverlapInfo> map) {
346 int max = oi.overlappingCount;
347 for (Interval interval : oi.overlapping) {
348 OverlapInfo o = map.get(interval);
349 if (o.maxOverlapping > max) {
350 max = o.maxOverlapping;
351 }
352 }
353 return max;
354 }
355
356 /**
357 * {@inheritDoc}
358 */
359 public void clearCachedData() {
360 _oiRowCache.clear(); // clear oi cache
361 }
362
363 /**
364 * {@inheritDoc} Simply helps the garbage collector.
365 */
366 public void dispose() {
367 _delegate = null;
368 _oiRowCache = null;
369 }
370
371 /**
372 * Debug method for dumping all overlap informtaions contained in a map.
373 *
374 * @param map map containing intervls and overlap information
375 */
376 // private void dump(Map<Interval, OverlapInfo> map) {
377 // for (Interval i : map.keySet()) {
378 // OverlapInfo oi = map.get(i);
379 // dump(oi);
380 // }
381 // System.out.println();
382 // }
383
384 /**
385 * Debug helper for dumping the overlap informations.
386 *
387 * @param oi overlap information to dump
388 */
389 // private void dump(OverlapInfo oi) {
390 // System.out.println("oi " + oi.interval + " pos " + oi.pos + " max " + oi.maxOverlapping);
391 // for (Interval interval : oi.overlapping) {
392 // System.out.println(" --> " + interval);
393 // }
394 // }
395
396 /**
397 * Retrieve the status of assumeSortedIntervals. If this is false, intervals will be sorted temporarily for
398 * overlapping.
399 *
400 * @return the status
401 */
402 public boolean getAssumeSortedIntervals() {
403 return _assumeSortedIntervals;
404 }
405
406 /**
407 * If set to false intervals will be sorted often ... defaults to true.
408 *
409 * @param assumeSortedIntervals the new status
410 */
411 public void setAssumeSortedIntervals(boolean assumeSortedIntervals) {
412 _assumeSortedIntervals = assumeSortedIntervals;
413 }
414
415 }