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.planning.ldm.plan;
028:
029: import java.util.ArrayList;
030: import java.util.Collection;
031: import java.util.Iterator;
032: import java.util.List;
033: import java.util.Vector;
034:
035: import org.cougaar.util.Thunk;
036:
037: public final class ScheduleUtilities {
038: public static final long millisperday = (24 * 60 * 60 * 1000L);
039:
040: /** Simplify a Quantity schedule by producing the smallest
041: * schedule which has the same quantity-value curve. That is,
042: * no temporally-overlapping elements and no abutting elements
043: * with the same value.
044: **/
045: public static Schedule simplifySchedule(Schedule s) {
046: //return combineLikeQuantityElements(computeNonOverlappingSchedule(s));
047: return computeNonOverlappingSchedule(s);
048: }
049:
050: /**
051: * Return non-overlapping schedules from thescheduleelements.
052: * Assumes that all schedule elements are ScheduleElementWithValue
053: * Sums all ScheduleElementWithValue on a per day basis.
054: * @param aSchedule
055: * @return Schedule A new Schedule object with non-overlapping (time)
056: * ScheduleElementWithValue
057: * @see org.cougaar.planning.ldm.plan.Schedule
058: * @see org.cougaar.planning.ldm.plan.ScheduleElementWithValue
059: * @throws IllegalArgumentException
060: */
061: public static Schedule computeNonOverlappingSchedule(
062: Schedule aSchedule) {
063: final Vector scheduleElements = new Vector();
064:
065: class MyThunk implements Thunk {
066: ScheduleElement pending = null;
067:
068: /** a list of pushed back scheduleElements ordered by decreasing start time **/
069: private ArrayList pbl = new ArrayList();
070:
071: /** insert se at the right place in the pushback list **/
072: private void pushback(ScheduleElement se) {
073: int l = pbl.size();
074: long s0 = se.getStartTime();
075: for (int i = 0; i < l; i++) {
076: if (s0 > ((ScheduleElement) pbl.get(i))
077: .getStartTime()) {
078: pbl.add(i, se);
079: return;
080: }
081: }
082: pbl.add(se);
083: }
084:
085: public void apply(Object o) {
086: ScheduleElement se = (ScheduleElement) o;
087: long s0 = se.getStartTime();
088: int l;
089: while ((l = pbl.size()) != 0) {
090: int l1 = l - 1;
091: ScheduleElement last = (ScheduleElement) pbl
092: .get(l1);
093: if (last.getStartTime() <= s0) {
094: pbl.remove(l1);
095: consumeOne(last);
096: } else {
097: break;
098: }
099: }
100: consumeOne(se);
101: }
102:
103: public void finish() {
104: int l;
105: while ((l = pbl.size()) != 0) {
106: int l1 = l - 1;
107: ScheduleElement last = (ScheduleElement) pbl
108: .get(l1);
109: pbl.remove(l1);
110: consumeOne(last);
111: }
112: if (pending != null)
113: scheduleElements.add(pending);
114: }
115:
116: private void consumeOne(ScheduleElement se) {
117: if (pending == null) {
118: pending = se; // nothing pending, so just watch for next iteration
119: } else {
120: if (pending.overlapSchedule(se)) {
121: long p0 = pending.getStartTime();
122: long p1 = pending.getEndTime();
123: long s0 = se.getStartTime();
124: long s1 = se.getEndTime();
125:
126: // create an initial span before the overlapping span
127: if (p0 < s0) {
128: scheduleElements.add(createElement(p0, s0,
129: pending, null));
130: }
131: // compute the tail
132: long lesser;
133: if (p1 < s1) {
134: lesser = p1;
135: pushback(createElement(p1, s1, se, null));
136: } else if (p1 > s1) {
137: lesser = s1;
138: pushback(createElement(s1, p1, pending,
139: null));
140: } else {
141: lesser = s1;
142: }
143:
144: // add the overlap
145: pending = createElement(s0, lesser, pending, se);
146: } else {
147: scheduleElements.add(pending);
148: pending = se;
149: }
150: }
151: }
152:
153: /** e1 must be non-null **/
154: private ScheduleElement createElement(long start, long end,
155: ScheduleElement e1, ScheduleElement e2) {
156:
157: double acc = ((ScheduleElementWithValue) e1).getValue();
158: if (e2 != null) {
159: acc += ((ScheduleElementWithValue) e2).getValue();
160: }
161: return ((ScheduleElementWithValue) e1).newElement(
162: start, end, acc);
163: }
164: }
165: ;
166: MyThunk thunk = new MyThunk();
167:
168: synchronized (aSchedule) {
169: aSchedule.applyThunkToScheduleElements(thunk);
170: thunk.finish(); // finish up the pushedback elements
171: }
172:
173: // create a new schedule with the new elements
174: ScheduleImpl newsched = new ScheduleImpl();
175: newsched.setScheduleType(aSchedule.getScheduleType());
176: newsched.setScheduleElementType(aSchedule
177: .getScheduleElementType());
178: newsched.setScheduleElements(scheduleElements);
179:
180: return newsched;
181: }
182:
183: /**
184: * Returns a schedule that creates ScheduleElementWithValue that span multiple
185: * days if there are Like ScheduleElementWithValues during that time period.
186: * This is more efficient than having a scheduleelement for each day.
187: * This method expects a Schedule containing ONLY ScheduleElementWithValues
188: * @param aSchedule
189: * @return Schedule
190: * @see org.cougaar.planning.ldm.plan.Schedule
191: * @see org.cougaar.planning.ldm.plan.ScheduleElementWithValue
192: * @throws IllegalArgumentException
193: **/
194: public static Schedule combineLikeQuantityElements(
195: Schedule aSchedule) {
196: if (!ScheduleElementWithValue.class.isAssignableFrom(aSchedule
197: .getScheduleElementType())) {
198: throw new IllegalArgumentException(
199: "ScheduleUtilities.combineLikeQuantityElements expects "
200: + "a Schedule with ScheduleElementWithValues!");
201: }
202: double currentQuantity = 0;
203: long startTime = 0;
204: long endTime = 0;
205: ArrayList minimalScheduleElements = new ArrayList();
206:
207: ArrayList scheduleElements = new ArrayList(aSchedule);
208:
209: if (scheduleElements.size() > 0) {
210: ScheduleElementWithValue s = (ScheduleElementWithValue) scheduleElements
211: .get(0);
212: startTime = s.getStartTime();
213: endTime = s.getEndTime();
214: currentQuantity = s.getValue();
215:
216: for (int i = 1; i < scheduleElements.size(); i++) {
217: s = (ScheduleElementWithValue) scheduleElements.get(i);
218: if (s.getStartTime() > (endTime + 1000)
219: || s.getValue() != currentQuantity) {
220: minimalScheduleElements.add(s.newElement(startTime,
221: endTime, currentQuantity));
222: currentQuantity = s.getValue();
223: startTime = s.getStartTime();
224: }
225: endTime = s.getEndTime();
226: }
227: //get the last range element
228: if (startTime != 0 && (endTime - startTime) > 1000L) {
229: minimalScheduleElements.add(s.newElement(startTime,
230: endTime, currentQuantity));
231: }
232: }
233:
234: // create a new schedule to return
235: ScheduleImpl newsched = new ScheduleImpl();
236: newsched.setScheduleType(aSchedule.getScheduleType());
237: newsched.setScheduleElementType(aSchedule
238: .getScheduleElementType());
239: newsched.setScheduleElements(minimalScheduleElements);
240:
241: return newsched;
242: }
243:
244: /**
245: * Add the quantities of the scheduleelements in the set.
246: * Must be a set of ScheduleElementWithValues or RateScheduleElement
247: * @param aSet Called with all the schedule elements for a day.
248: * @return double
249: * @throws IllegalArgumentException
250: **/
251: public static double sumElements(Collection aSet) {
252: if (aSet == null)
253: return 0.0;
254: double quantity = 0;
255:
256: for (Iterator i = new ArrayList(aSet).iterator(); i.hasNext();) {
257: ScheduleElementWithValue s = (ScheduleElementWithValue) i
258: .next();
259: quantity += s.getValue();
260: }
261: return quantity;
262: }
263:
264: //
265: // thunk utilities
266: //
267:
268: /** Utility to select ScheduleElements which overlap with a specific time **/
269: public void selectElementsAtTime(Schedule s, final Thunk t,
270: final long d) {
271: synchronized (s) {
272: s.applyThunkToScheduleElements(new Thunk() {
273: public void apply(Object o) {
274: ScheduleElement se = (ScheduleElement) o;
275: if (d >= se.getStartTime() && d < se.getEndTime())
276: t.apply(o);
277: }
278: });
279: }
280: }
281:
282: /** Utility to select ScheduleElements which overlap with a time span **/
283: public void selectElementsOverlappingSpan(Schedule s,
284: final Thunk t, final long startt, final long endt) {
285: synchronized (s) {
286: s.applyThunkToScheduleElements(new Thunk() {
287: public void apply(Object o) {
288: ScheduleElement se = (ScheduleElement) o;
289: if (se.getStartTime() < endt
290: && se.getEndTime() > startt)
291: t.apply(o);
292: }
293: });
294: }
295: }
296:
297: /** Utility to select ScheduleElements which overlap with a time span **/
298: public void selectElementsOverlappingSpan(Schedule s,
299: final Thunk t, ScheduleElement span) {
300: selectElementsOverlappingSpan(s, t, span.getStartTime(), span
301: .getEndTime());
302: }
303:
304: /** Utility to select ScheduleElements which enclose (or equal) a time span **/
305: public void selectElementsEnclosingSpan(Schedule s, final Thunk t,
306: final long startt, final long endt) {
307: synchronized (s) {
308: s.applyThunkToScheduleElements(new Thunk() {
309: public void apply(Object o) {
310: ScheduleElement se = (ScheduleElement) o;
311: if (se.getStartTime() >= startt
312: && se.getEndTime() <= endt)
313: t.apply(o);
314: }
315: });
316: }
317: }
318:
319: /** Utility to select ScheduleElements which enclose (or equal) a time span **/
320: public void selectElementsEnclosingSpan(Schedule s, final Thunk t,
321: ScheduleElement span) {
322: selectElementsEnclosingSpan(s, t, span.getStartTime(), span
323: .getEndTime());
324: }
325:
326: //////////////// For UIPlugins and ScheduleImpl internals ////////////
327:
328: /** combine two quantity schedules. **/
329: public static final Schedule addSchedules(Schedule aSchedule,
330: Schedule bSchedule) {
331: Schedule tmp = new ScheduleImpl(aSchedule);
332: tmp.addAll(bSchedule);
333: return simplifySchedule(tmp);
334: }
335:
336: /** Subtract out the bSchedule from the aSchedule **/
337: public static final Schedule subtractSchedules(Schedule aSchedule,
338: Schedule bSchedule) {
339: Schedule tmp = new ScheduleImpl(aSchedule);
340:
341: synchronized (bSchedule) {
342: for (Iterator iterator = new ScheduleUtilitiesIterator(
343: bSchedule); iterator.hasNext();) {
344: ScheduleElementWithValue e = (ScheduleElementWithValue) iterator
345: .next();
346: ScheduleElementWithValue n = e.newElement(e
347: .getStartTime(), e.getEndTime(), -e.getValue());
348: tmp.add(n);
349: }
350: }
351:
352: return simplifySchedule(tmp);
353: }
354:
355: //Convenience class - uses Iterator for Collection, List.get(int) for
356: //List.
357: private static class ScheduleUtilitiesIterator implements Iterator {
358: Collection myCollection;
359: Iterator myIterator;
360: int myIndex;
361:
362: public ScheduleUtilitiesIterator(Collection c) {
363: myCollection = c;
364:
365: if (c instanceof List) {
366: myIndex = 0;
367: myIterator = null;
368: } else {
369: myIndex = -1;
370: myIterator = c.iterator();
371: }
372: }
373:
374: public boolean hasNext() {
375: if (myCollection instanceof List) {
376: return myIndex < myCollection.size();
377: } else {
378: return myIterator.hasNext();
379: }
380: }
381:
382: public Object next() {
383: if (myCollection instanceof List) {
384: return ((List) myCollection).get(myIndex++);
385: } else {
386: return myIterator.next();
387: }
388: }
389:
390: public void remove() {
391: if (myCollection instanceof List) {
392: ((List) myCollection).remove(myIndex);
393: } else {
394: myIterator.remove();
395: }
396: }
397: }
398: }
|