in reply to Assemble times into ranges
For each iterval, add 2 items to a hash, one with key:value of the start time and a unique interger (eg $i++); the second with the end time and the negative of that integer.
For each even, add one item to the same hash, key the event time, and value 0.
Grab the keys of the hash, and sort on time, with secondary sort on the ascending order of the absolute value of the hash value Eg, for three values with teh same key, the order would be something like 0, -3, 5.
Now, just iterate along the keys. If the value of a key is a positive integer, then in another hash (interval_hash), set that key to some value (eg, if the integer is 3, the interval_hash would be key 3, value 1). If a negative interger, undef that value from the interval_hash. If zero, then in a third hash (occured_hash), for each key currently in interval_hash, push the time onto an array for that interval. So, if time is currently 10, and interval_hash contains keys 3, 4, and 7, then for occured_hash keys 3,4, and 7, you'd push 10 onto the arrays that are referenced by this.
When you are all done, then the values for a given interval key in occured_hash will be an array with all the times that fall into those events.
Again, this should be faster based on the order calculations, but you'd have to try it out and make sure that the little things like hash manipulations don't slow it down too much (it shouldn't).
UPDATE: ok, the trick on the secondary sorting (dealing with intervals and events that occur at the same time), partially has to do if you want inclusive or exclusive intervals. If you want inclusive, then the secondary sort should be in decending, non-absolute order (eg 5, 0, -3 ), such that you 'initiate' new intervals before you process the events, and then 'deactivate' any intervals after processing. If you want 'exclusive', then sort in increasing order (-3, 0, 5) to delete intervals before dealing with events, then creating new ones.
|
|---|