diff --git a/src/applications/phrequent/storage/PhrequentTimeBlock.php b/src/applications/phrequent/storage/PhrequentTimeBlock.php index 866275ac08..60721e45ca 100644 --- a/src/applications/phrequent/storage/PhrequentTimeBlock.php +++ b/src/applications/phrequent/storage/PhrequentTimeBlock.php @@ -1,155 +1,268 @@ events = $events; } public function getTimeSpentOnObject($phid, $now) { $ranges = idx($this->getObjectTimeRanges($now), $phid, array()); $sum = 0; foreach ($ranges as $range) { $sum += ($range[1] - $range[0]); } return $sum; } public function getObjectTimeRanges($now) { $ranges = array(); $object_ranges = array(); foreach ($this->events as $event) { // First, convert each event's preempting stack into a linear timeline // of events. $timeline = array(); $timeline[] = array( + 'event' => $event, 'at' => $event->getDateStarted(), 'type' => 'start', ); $timeline[] = array( + 'event' => $event, 'at' => nonempty($event->getDateEnded(), $now), 'type' => 'end', ); $base_phid = $event->getObjectPHID(); $preempts = $event->getPreemptingEvents(); foreach ($preempts as $preempt) { $same_object = ($preempt->getObjectPHID() == $base_phid); $timeline[] = array( + 'event' => $preempt, 'at' => $preempt->getDateStarted(), 'type' => $same_object ? 'start' : 'push', ); $timeline[] = array( + 'event' => $preempt, 'at' => nonempty($preempt->getDateEnded(), $now), 'type' => $same_object ? 'end' : 'pop', ); } // Now, figure out how much time was actually spent working on the // object. - $timeline = isort($timeline, 'at'); + usort($timeline, array(__CLASS__, 'sortTimeline')); $stack = array(); $depth = null; + // NOTE: "Strata" track the separate layers between each event tracking + // the object we care about. Events might look like this: + // + // |xxxxxxxxxxxxxxxxx| + // |yyyyyyy| + // |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| + // 9AM 5PM + // + // ...where we care about event "x". When "y" is popped, that shouldn't + // pop the top stack -- we need to pop the stack a level down. Each + // event tracking "x" creates a new stratum, and we keep track of where + // timeline events are among the strata in order to keep stack depths + // straight. + + $stratum = null; + $strata = array(); + + $ranges = array(); foreach ($timeline as $timeline_event) { - switch ($timeline_event['type']) { + $id = $timeline_event['event']->getID(); + $type = $timeline_event['type']; + + switch ($type) { case 'start': $stack[] = $depth; $depth = 0; + $stratum = count($stack); + $strata[$id] = $stratum; $range_start = $timeline_event['at']; break; case 'end': - if ($depth == 0) { - $ranges[] = array($range_start, $timeline_event['at']); + if ($strata[$id] == $stratum) { + if ($depth == 0) { + $ranges[] = array($range_start, $timeline_event['at']); + $depth = array_pop($stack); + } else { + // Here, we've prematurely ended the current stratum. Merge all + // the higher strata into it. This looks like this: + // + // V + // V + // |zzzzzzzz| + // |xxxxx| + // |yyyyyyyyyyyyy| + // |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| + + $depth = array_pop($stack) + $depth; + } + } else { + // Here, we've prematurely ended a deeper stratum. Merge higher + // stata. This looks like this: + // + // V + // V + // |aaaaaaa| + // |xxxxxxxxxxxxxxxxxxx| + // |zzzzzzzzzzzzz| + // |xxxxxxx| + // |yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy| + // |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| + + $extra = $stack[$strata[$id]]; + unset($stack[$strata[$id] - 1]); + $stack = array_values($stack); + $stack[$strata[$id] - 1] += $extra; + } + + // Regardless of how we got here, we need to merge down any higher + // strata. + $target = $strata[$id]; + foreach ($strata as $strata_id => $id_stratum) { + if ($id_stratum >= $target) { + $strata[$strata_id]--; + } } - $depth = array_pop($stack); + $stratum = count($stack); + + unset($strata[$id]); break; case 'push': + $strata[$id] = $stratum; if ($depth == 0) { $ranges[] = array($range_start, $timeline_event['at']); } $depth++; break; case 'pop': - $depth--; - if ($depth == 0) { - $range_start = $timeline_event['at']; + if ($strata[$id] == $stratum) { + $depth--; + if ($depth == 0) { + $range_start = $timeline_event['at']; + } + } else { + $stack[$strata[$id]]--; } + unset($strata[$id]); break; } } $object_ranges[$base_phid][] = $ranges; } // Finally, collapse all the ranges so we don't double-count time. foreach ($object_ranges as $phid => $ranges) { $object_ranges[$phid] = self::mergeTimeRanges(array_mergev($ranges)); } return $object_ranges; } /** * Merge a list of time ranges (pairs of `` epochs) so that no * elements overlap. For example, the ranges: * * array( * array(50, 150), * array(100, 175), * ); * * ...are merged to: * * array( * array(50, 175), * ); * * This is used to avoid double-counting time on objects which had timers * started multiple times. * * @param list> List of possibly overlapping time ranges. * @return list> Nonoverlapping time ranges. */ public static function mergeTimeRanges(array $ranges) { $ranges = isort($ranges, 0); $result = array(); $current = null; foreach ($ranges as $key => $range) { if ($current === null) { $current = $range; continue; } if ($range[0] <= $current[1]) { $current[1] = max($range[1], $current[1]); continue; } $result[] = $current; $current = $range; } $result[] = $current; return $result; } + + /** + * Sort events in timeline order. Notably, for events which occur on the same + * second, we want to process end events after start events. + */ + public static function sortTimeline(array $u, array $v) { + // If these events occur at different times, ordering is obvious. + if ($u['at'] != $v['at']) { + return ($u['at'] < $v['at']) ? -1 : 1; + } + + $u_end = ($u['type'] == 'end' || $u['type'] == 'pop'); + $v_end = ($v['type'] == 'end' || $v['type'] == 'pop'); + + $u_id = $u['event']->getID(); + $v_id = $v['event']->getID(); + + if ($u_end == $v_end) { + // These are both start events or both end events. Sort them by ID. + if (!$u_end) { + return ($u_id < $v_id) ? -1 : 1; + } else { + return ($u_id < $v_id) ? 1 : -1; + } + } else { + // Sort them (start, end) if they're the same event, and (end, start) + // otherwise. + if ($u_id == $v_id) { + return $v_end ? -1 : 1; + } else { + return $v_end ? 1 : -1; + } + } + + return 0; + } + } diff --git a/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php b/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php index 0c110c36d5..6bb09b5497 100644 --- a/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php +++ b/src/applications/phrequent/storage/__tests__/PhrequentTimeBlockTestCase.php @@ -1,128 +1,226 @@ assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input)); // Identical ranges. $input = array( array(1, 1), array(1, 1), array(1, 1), ); $expect = array( array(1, 1), ); $this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input)); // Range which is a strict subset of another range. $input = array( array(2, 7), array(1, 10), ); $expect = array( array(1, 10), ); $this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input)); // These are discontinuous and should not be merged. $input = array( array(5, 6), array(7, 8), ); $expect = array( array(5, 6), array(7, 8), ); $this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input)); // These overlap only on an edge, but should merge. $input = array( array(5, 6), array(6, 7), ); $expect = array( array(5, 7), ); $this->assertEqual($expect, PhrequentTimeBlock::mergeTimeRanges($input)); } public function testPreemptingEvents() { // Roughly, this is: got into work, started T1, had a meeting from 10-11, // left the office around 2 to meet a client at a coffee shop, worked on // T1 again for about 40 minutes, had the meeting from 3-3:30, finished up // on T1, headed back to the office, got another hour of work in, and // headed home. $event = $this->newEvent('T1', 900, 1700); $event->attachPreemptingEvents( array( $this->newEvent('meeting', 1000, 1100), $this->newEvent('offsite', 1400, 1600), $this->newEvent('T1', 1420, 1580), $this->newEvent('offsite meeting', 1500, 1550), )); $block = new PhrequentTimeBlock(array($event)); $ranges = $block->getObjectTimeRanges(1800); $this->assertEqual( array( 'T1' => array( array(900, 1000), // Before morning meeting. array(1100, 1400), // After morning meeting. array(1420, 1500), // Coffee, before client meeting. array(1550, 1580), // Coffee, after client meeting. array(1600, 1700), // After returning from off site. ), ), $ranges); - $event = $this->newEvent('T2', 100, 300); $event->attachPreemptingEvents( array( $this->newEvent('meeting', 200, null), )); $block = new PhrequentTimeBlock(array($event)); $ranges = $block->getObjectTimeRanges(1000); $this->assertEqual( array( 'T2' => array( array(100, 200), ), ), $ranges); } + public function testTimelineSort() { + $e1 = $this->newEvent('X1', 1, 1)->setID(1); + + $in = array( + array( + 'event' => $e1, + 'at' => 1, + 'type' => 'start', + ), + array( + 'event' => $e1, + 'at' => 1, + 'type' => 'end', + ), + ); + + usort($in, array('PhrequentTimeBlock', 'sortTimeline')); + + $this->assertEqual( + array( + 'start', + 'end', + ), + ipull($in, 'type')); + } + + public function testInstantaneousEvent() { + + $event = $this->newEvent('T1', 8, 8); + $event->attachPreemptingEvents(array()); + + $block = new PhrequentTimeBlock(array($event)); + + $ranges = $block->getObjectTimeRanges(1800); + $this->assertEqual( + array( + 'T1' => array( + array(8, 8), + ), + ), + $ranges); + } + + public function testPopAcrossStrata() { + + $event = $this->newEvent('T1', 1, 1000); + $event->attachPreemptingEvents( + array( + $this->newEvent('T2', 100, 300), + $this->newEvent('T1', 200, 400), + $this->newEvent('T3', 250, 275), + )); + + $block = new PhrequentTimeBlock(array($event)); + + $ranges = $block->getObjectTimeRanges(1000); + + $this->assertEqual( + array( + 'T1' => array( + array(1, 100), + array(200, 250), + array(275, 1000), + ), + ), + $ranges); + } + + public function testEndDeeperStratum() { + $event = $this->newEvent('T1', 1, 1000); + $event->attachPreemptingEvents( + array( + $this->newEvent('T2', 100, 900), + $this->newEvent('T1', 200, 400), + $this->newEvent('T3', 300, 800), + $this->newEvent('T1', 350, 600), + $this->newEvent('T4', 380, 390), + )); + + $block = new PhrequentTimeBlock(array($event)); + + $ranges = $block->getObjectTimeRanges(1000); + + $this->assertEqual( + array( + 'T1' => array( + array(1, 100), + array(200, 300), + array(350, 380), + array(390, 600), + array(900, 1000), + ), + ), + $ranges); + } + private function newEvent($object_phid, $start_time, $end_time) { + static $id = 0; + return id(new PhrequentUserTime()) + ->setID(++$id) ->setObjectPHID($object_phid) ->setDateStarted($start_time) ->setDateEnded($end_time); } }