001: /*
002: * <copyright>
003: *
004: * Copyright 1997-2004 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026:
027: package org.cougaar.util;
028:
029: import java.io.Serializable;
030: import java.util.Collection;
031: import java.util.Collections;
032: import java.util.Comparator;
033: import java.util.Iterator;
034: import java.util.List;
035: import java.util.SortedSet;
036:
037: /**
038: * A Collection which implements a set of TimeSpan elements
039: * which are maintained sorted first by start time and then by
040: * end time. The order of temporally-equivalent but non-equal
041: * objects is undefined but stable.
042: **/
043: public class TimeSpanSet extends ArrayListFoundation implements
044: SortedSet, Serializable {
045: // constructors
046: public TimeSpanSet() {
047: super ();
048: }
049:
050: public TimeSpanSet(int i) {
051: super (i);
052: }
053:
054: public TimeSpanSet(Collection c) {
055: super (c.size());
056:
057: addAll(c);
058: }
059:
060: public TimeSpanSet(TimeSpanSet t) {
061: super (t.size());
062:
063: unsafeUpdate(t);
064: }
065:
066: public boolean add(Object o) {
067: if (!(o instanceof TimeSpan))
068: throw new IllegalArgumentException();
069: TimeSpan timeSpan = (TimeSpan) o;
070:
071: TimeSpan last = (TimeSpan) last();
072: if (last == null
073: || last.getStartTime() < timeSpan.getStartTime()) {
074: super .add(size, timeSpan);
075: return true;
076: }
077:
078: int i = Collections.binarySearch(this , timeSpan, bsComparator);
079: if (i >= 0)
080: return false; // This timespan is already in set
081: i = -(i + 1); // The insertion point
082:
083: for (int j = i; --j >= 0;) {
084: if (bsComparator.compare(timeSpan, elementData[j]) != 0)
085: break;
086: if (timeSpan.equals(elementData[j]))
087: return false;
088: }
089:
090: for (int j = i, e = size(); j < e; j++) {
091: if (bsComparator.compare(timeSpan, elementData[j]) != 0)
092: break;
093: if (timeSpan.equals(elementData[j]))
094: return false;
095: }
096:
097: super .add(i, timeSpan);
098: return true;
099: }
100:
101: public void add(int i, Object o) {
102: throw new UnsupportedOperationException(
103: "TimeSpanSet.add(int index, Object o) is not supported.");
104: }
105:
106: public boolean addAll(Collection c) {
107: boolean hasChanged = false;
108:
109: if (c instanceof List) {
110: List list = (List) c;
111: int numToAdd = list.size();
112:
113: for (int index = 0; index < numToAdd; index++) {
114: if (add(list.get(index))) {
115: hasChanged = true;
116: }
117: }
118: } else {
119: for (Iterator i = c.iterator(); i.hasNext();) {
120: if (add(i.next()))
121: hasChanged = true;
122: }
123: }
124:
125: return hasChanged;
126: }
127:
128: public boolean addAll(int index, Collection c) {
129: throw new UnsupportedOperationException(
130: "TimeSpanSet.addAll(int index, Collection c) is not supported.");
131: }
132:
133: public boolean contains(Object o) {
134: if (o instanceof TimeSpan) {
135: return find((TimeSpan) o) != -1;
136: }
137: return false;
138: }
139:
140: public boolean remove(Object o) {
141: // find it faster
142: if (o instanceof TimeSpan) {
143: int i = find((TimeSpan) o);
144: if (i == -1)
145: return false;
146: super .remove(i);
147: return true;
148: } else {
149: return false;
150: }
151: }
152:
153: public Object set(int index, Object element) {
154: throw new UnsupportedOperationException(
155: "TimeSpanSet.set(int index, Object element) is not supported.");
156: }
157:
158: public String toString() {
159: // do we want to change the implementation here?
160: return super .toString();
161: }
162:
163: // SortedSet implementation
164: public Comparator comparator() {
165: return myComparator;
166: }
167:
168: public final Object first() {
169: return (size > 0) ? (elementData[0]) : null;
170: }
171:
172: public final SortedSet headSet(Object toElement) {
173: throw new UnsupportedOperationException();
174: }
175:
176: public Object last() {
177: int l = size;
178: return (l > 0) ? elementData[l - 1] : null;
179: }
180:
181: public final SortedSet subSet(Object fromElement, Object toElement) {
182: throw new UnsupportedOperationException();
183: }
184:
185: public final SortedSet tailSet(Object fromElement) {
186: throw new UnsupportedOperationException();
187: }
188:
189: /** generic timespan comparison **/
190: private static int compare(TimeSpan p1, TimeSpan p2) {
191: int compare;
192:
193: if (p2.getStartTime() != p1.getStartTime()) {
194: compare = (p2.getStartTime() > p1.getStartTime()) ? 1 : -1;
195: } else if (p2.getEndTime() != p1.getEndTime()) {
196: compare = (p2.getEndTime() > p1.getEndTime()) ? 1 : -1;
197: } else if (p2.hashCode() != p2.hashCode()) {
198: compare = (p2.hashCode() > p1.hashCode()) ? 1 : -1;
199: } else {
200: compare = 0;
201: }
202:
203: return compare;
204: }
205:
206: /** optimization for non-comparator use **/
207: private static int compare(long p1s, long p1e, TimeSpan p2) {
208: int compare;
209:
210: if (p2.getStartTime() != p1s) {
211: compare = (p2.getStartTime() > p1s) ? 1 : -1;
212: } else if (p2.getEndTime() != p1e) {
213: compare = (p2.getEndTime() > p1e) ? 1 : -1;
214: } else {
215: compare = 0;
216: }
217:
218: return compare;
219: }
220:
221: /** comparator for Collection use **/
222: private static final Comparator myComparator = new Comparator() {
223: public int compare(Object o1, Object o2) {
224: if (o1 instanceof TimeSpan && o2 instanceof TimeSpan) {
225: return TimeSpanSet
226: .compare((TimeSpan) o1, (TimeSpan) o2);
227: } else {
228: return 0;
229: }
230: }
231: };
232:
233: private static final Comparator bsComparator = new Comparator() {
234: public int compare(Object o1, Object o2) {
235: TimeSpan ts1 = (TimeSpan) o1;
236: TimeSpan ts2 = (TimeSpan) o2;
237: long diff = ts1.getStartTime() - ts2.getStartTime();
238: if (diff > 0L)
239: return 1;
240: if (diff < 0L)
241: return -1;
242: diff = ts1.getEndTime() - ts2.getEndTime();
243: if (diff > 0L)
244: return 1;
245: if (diff < 0L)
246: return -1;
247: return System.identityHashCode(o1)
248: - System.identityHashCode(o2);
249: }
250: };
251:
252: /** @return the intersecting Element with the smallest timespan.
253: * The result is undefined if there is a tie for smallest and null
254: * if there are no elements.
255: **/
256: public Object getMinimalIntersectingElement(final long time) {
257: int l = size;
258: if (l == 0)
259: return null;
260:
261: TimeSpan best = null;
262: long bestd = TimeSpan.MAX_VALUE - TimeSpan.MIN_VALUE;
263:
264: for (int i = 0; i < l; i++) {
265: TimeSpan ts = (TimeSpan) elementData[i];
266: long t0 = ts.getStartTime();
267: if (time < t0)
268: break; // if the element is after our point, we're done
269:
270: long t1 = ts.getEndTime();
271: if (t1 < time)
272: continue; // if the point is after the endpoint, we continue
273:
274: long d = t1 - t0;
275: if (best == null || (d < bestd)) {
276: best = ts;
277: bestd = d;
278: }
279: }
280: return best;
281: }
282:
283: /** @return the subset of elements which meet the specified predicate.
284: **/
285: public Collection filter(UnaryPredicate predicate) {
286: return Filters.filter(this , predicate);
287: }
288:
289: /** @return the subset of elements which intersect with
290: * the specified time.
291: **/
292: public final Collection intersectingSet(final long time) {
293: return filter(new UnaryPredicate() {
294: public boolean execute(Object o) {
295: TimeSpan ts = (TimeSpan) o;
296: return (time >= ts.getStartTime() && time < ts
297: .getEndTime());
298: }
299: });
300: }
301:
302: /** @return the subset of elements which intersect with the
303: * specified time span.
304: **/
305: public final Collection intersectingSet(final long startTime,
306: final long endTime) {
307: return filter(new UnaryPredicate() {
308: public boolean execute(Object o) {
309: TimeSpan ts = (TimeSpan) o;
310: return (ts.getStartTime() < endTime && ts.getEndTime() > startTime);
311: }
312: });
313: }
314:
315: /** @return the subset of elements which intersect with the
316: * specified time span.
317: **/
318: public final Collection intersectingSet(TimeSpan span) {
319: return intersectingSet(span.getStartTime(), span.getEndTime());
320: }
321:
322: /** @return the subset of elements which are completely enclosed
323: * by the specified time span.
324: **/
325: public final Collection encapsulatedSet(final long startTime,
326: final long endTime) {
327: return filter(new UnaryPredicate() {
328: public boolean execute(Object o) {
329: TimeSpan ts = (TimeSpan) o;
330: return (ts.getStartTime() >= startTime && ts
331: .getEndTime() <= endTime);
332: }
333: });
334: }
335:
336: /** @return the subset of elements which are completely enclosed
337: * by the specified time span.
338: **/
339: public final Collection encapsulatedSet(TimeSpan span) {
340: return encapsulatedSet(span.getStartTime(), span.getEndTime());
341: }
342:
343: /** @return the subset of elements which completely enclose
344: * the specified time span.
345: **/
346: private Collection encapsulatingSet(final long startTime,
347: final long endTime) {
348: return filter(new UnaryPredicate() {
349: public boolean execute(Object o) {
350: TimeSpan ts = (TimeSpan) o;
351: return (startTime <= ts.getStartTime() && endTime >= ts
352: .getEndTime());
353: }
354: });
355: }
356:
357: /** @return the subset of elements which completely enclose
358: * the specified time span.
359: **/
360: public final Collection encapsulatingSet(TimeSpan span) {
361: return encapsulatingSet(span.getStartTime(), span.getEndTime());
362: }
363:
364: // private support
365:
366: /**
367: * unsafeUpdate - replaces all elements with specified Collection
368: * Should only be used if c has already been validated.
369: * @return boolean - true if any elements added else false.
370: */
371: protected boolean unsafeUpdate(Collection c) {
372: clear();
373: return super .addAll(c);
374: }
375:
376: /** @return the index of the object in the list or -1 **/
377: private int find(TimeSpan o) {
378: // we should really use a boolean search rather
379: // than iterating through
380: int l = size;
381: for (int i = 0; i < l; i++) {
382: if (o.equals(elementData[i]))
383: return i;
384: }
385: return -1;
386: }
387:
388: /** @return the index of the first object in the list which is not
389: * less than the specified object. If there are no elements or
390: * all elements are less than the specified timespan, will
391: * return the length of the list.
392: **/
393: protected final int search(TimeSpan o) {
394: return search(o.getStartTime(), o.getEndTime());
395: }
396:
397: /** @return the index of the first object in the list which is not
398: * less than the specified span. If there are no elements or
399: * all elements are less than the specified timespan, will
400: * return the length of the list.
401: **/
402: protected final int search(long t0, long t1) {
403: int l = size;
404: if (l == 0)
405: return 0; // bail if empty
406:
407: // this is a crock - we should do a binary search.
408: for (int i = 0; i < l; i++) {
409: if (compare(t0, t1, (TimeSpan) elementData[i]) >= 0)
410: return i;
411: }
412: return l;
413: }
414: }
|