1 /**
  2  * @fileOverview Set of functions to separate overlapping intervals.
  3  */ 
  4 /**
  5  * @constructor
  6  * Constructs an instance of Interval with the provided parameters.
  7  * @param start Date instance representing start time of interval.
  8  * @param end Date instance representing end time of interval.
  9  * @param value Domain specific value for the interval.  Default 
 10  * behavior is for numeric values.
 11  */
 12 Interval = function(start, end, value) {
 13 	this.start = start;
 14 	this.end = end;
 15 	this.value = value;
 16 };
 17 
 18 /**
 19  * Compares provided intervals and returns -1, 0, or 1 based on the
 20  * following rules: 
 21  * <ul>
 22  * <li>-1: i1 start < i2 start or same and i1 end < 12 end 
 23  * <li>0: i1 start and end equal to i2 
 24  * <li>1: i1 start > i2 start or same and i1 end > i2 end
 25  * </ul>
 26  * 
 27  * @param int1
 28  * @param int2
 29  * @returns -1, 0, or 1 based on start and end times of the intervals.
 30  * @function
 31  */
 32 Interval.comparator = function(int1, int2) {
 33 	if (int1.start == int2.start) {
 34 		return int1.end == int2.end ? 0 : int1.end < int2.end ? -1 : 1;
 35 	} else {
 36 		return int1.start < int2.start ? -1 : 1;
 37 	}
 38 };
 39 
 40 /**
 41  * Set of functions to extract a set of intervals such that no interval 
 42  * overlaps any other interval.  Overlaps will be broken up into distinct
 43  * intervals with overlaps having their values combined.
 44  * @class
 45  * @requires MinHeap
 46  * 
 47  */
 48 function Intervals() {
 49     // no properties, only "class" methods.
 50 };
 51 
 52 /**
 53  * Takes two Intervals as input and returns an array of 1 to 3 Intervals 
 54  * based on the amount of overlap.  
 55  *
 56  * Input constraint: Start time for i1 must be less than or equal to 
 57  * start time for i2.
 58  *
 59  * Intervals returned are based on overlap of i1 and i2.  The intervals
 60  * will be split into distinct intervals with overlapping segments 
 61  * combining the values of both intervals.
 62  * 
 63  * Intervals returned will be in ascending order.
 64  * 
 65  * @param i1 Interval 1.
 66  * @param i2 Interval 2 with the constraint that i1.start <= i2.start;
 67  * @param accumulator Override of default accumulator. Must accept two values
 68  * and return a single value representing the "accumulated" value of the two
 69  * intervals.
 70  *
 71  * @return Array of Interval objects of length L where: 1 <= L <= 3.
 72  *
 73  */
 74 Intervals.splitIntervals = function(i1, i2, accumulator) {
 75     var acc = accumulator == null ? function(val1, val2){return val1 + val2;} : accumulator;
 76 	var newInt = new Array();
 77 	/*
 78 	 * Assumptions: ix[0] <= ix[1] start <= end i1[0] <= i2[0] in ascending
 79 	 * order by start
 80 	 */
 81 	if (i1.start == i2.start) {
 82 		if (i1.end == i2.end) { // a = b
 83 			// Combine both into a single entry with the combined values.
 84 			newInt.push(new Interval(i1.start, i1.end, acc(i1.value, i2.value)));
 85 		} else if (i1.end < i2.end) { // a.start = b.start and a.end <=
 86 			// b.end
 87 			newInt.push(new Interval(i1.start, i1.end, acc(i1.value, i2.value)));
 88 			newInt.push(new Interval(i1.end + 1, i2.end, i2.value));
 89 		} else { // a.start = b.start and a.end > b.end
 90 			newInt.push(new Interval(i1.start, i2.end, acc(i1.value, i2.value)));
 91 			newInt.push(new Interval(i2.end + 1, i1.end, i1.value));
 92 		}
 93 	} else { // a.start < b.start
 94 		if (i1.end <= i2.start) { // a.end <= b.start
 95 			// i1 before i2
 96 			newInt.push(i1);
 97 			newInt.push(i2);
 98 		} else if (i1.end < i2.end) { // a.end > b.start & a.end < b.end
 99 			// i2 overlaps i1
100 			newInt.push(new Interval(i1.start, i2.start - 1, i1.value));
101 			newInt.push(new Interval(i2.start, i1.end, acc(i1.value, i2.value)));
102 			newInt.push(new Interval(i1.end + 1, i2.end, i2.value));
103 		} else { // a.end > b.start & a.end >= b.end
104 			// i2 within i1 or equal
105 			newInt.push(new Interval(i1.start, i2.start - 1, i1.value));
106 			newInt.push(new Interval(i2.start, i2.end, acc(i1.value, i2.value)));
107 			if (i1.end > i2.end) {
108 				newInt.push(new Interval(i2.end + 1, i1.end, i1.value));
109 			}
110 		}
111 	}
112 
113 	;
114 	return newInt;
115 };
116 
117 /**
118  * Break it up.
119  * @param intervals Array of Interval objects in ascending order based on 
120  * Interval.comparator
121  * @param comparator
122  * @param accumulator
123  * @return Array of Interval objects of length L where: 1 <= L <= 3.
124  * @function
125  */
126 Intervals.accumulateByInterval = function(intervals, comparator, accumulator) {
127 	var results = new Array();
128     var compFunc = comparator ||  Interval.comparator;
129 	var heap = new MinHeap(intervals, compFunc);
130 	var i1, i2;
131 	while (heap.size() > 1) {
132 		i1 = heap.pop();
133 		i2 = heap.pop();
134 		var newInts = Intervals.splitIntervals(i1, i2, accumulator);
135 		switch (newInts.length) {
136 		case 1:
137 			heap.push(newInts[0]);
138 			break;
139 		case 2:
140 			if (i1 == newInts[0]) {
141 				results.push(i1);
142 				heap.push(newInts[1]);
143 			} else {
144 				heap.push(newInts[0]);
145 				heap.push(newInts[1]);
146 			}
147 			break;
148 		case 3:
149 			heap.push(newInts[0]);
150 			heap.push(newInts[1]);
151 			heap.push(newInts[2]);
152 			break;
153 		}
154 	}
155 	if (heap.size() == 1) {
156 		results.push(heap.pop());
157 	}
158     return results;
159 };
160