[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  final class PhrequentTimeBlock extends Phobject {
   4  
   5    private $events;
   6  
   7    public function __construct(array $events) {
   8      assert_instances_of($events, 'PhrequentUserTime');
   9      $this->events = $events;
  10    }
  11  
  12    public function getTimeSpentOnObject($phid, $now) {
  13      $slices = idx($this->getObjectTimeRanges(), $phid);
  14  
  15      if (!$slices) {
  16        return null;
  17      }
  18  
  19      return $slices->getDuration($now);
  20    }
  21  
  22    public function getObjectTimeRanges() {
  23      $ranges = array();
  24  
  25      $range_start = time();
  26      foreach ($this->events as $event) {
  27        $range_start = min($range_start, $event->getDateStarted());
  28      }
  29  
  30      $object_ranges = array();
  31      $object_ongoing = array();
  32      foreach ($this->events as $event) {
  33  
  34        // First, convert each event's preempting stack into a linear timeline
  35        // of events.
  36  
  37        $timeline = array();
  38        $timeline[] = array(
  39          'event' => $event,
  40          'at' => (int)$event->getDateStarted(),
  41          'type' => 'start',
  42        );
  43        $timeline[] = array(
  44          'event' => $event,
  45          'at' => (int)nonempty($event->getDateEnded(), PHP_INT_MAX),
  46          'type' => 'end',
  47        );
  48  
  49        $base_phid = $event->getObjectPHID();
  50        if (!$event->getDateEnded()) {
  51          $object_ongoing[$base_phid] = true;
  52        }
  53  
  54        $preempts = $event->getPreemptingEvents();
  55        foreach ($preempts as $preempt) {
  56          $same_object = ($preempt->getObjectPHID() == $base_phid);
  57          $timeline[] = array(
  58            'event' => $preempt,
  59            'at' => (int)$preempt->getDateStarted(),
  60            'type' => $same_object ? 'start' : 'push',
  61          );
  62          $timeline[] = array(
  63            'event' => $preempt,
  64            'at' => (int)nonempty($preempt->getDateEnded(), PHP_INT_MAX),
  65            'type' => $same_object ? 'end' : 'pop',
  66          );
  67        }
  68  
  69        // Now, figure out how much time was actually spent working on the
  70        // object.
  71  
  72        usort($timeline, array(__CLASS__, 'sortTimeline'));
  73  
  74        $stack = array();
  75        $depth = null;
  76  
  77        // NOTE: "Strata" track the separate layers between each event tracking
  78        // the object we care about. Events might look like this:
  79        //
  80        //             |xxxxxxxxxxxxxxxxx|
  81        //         |yyyyyyy|
  82        //    |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
  83        //   9AM                                            5PM
  84        //
  85        // ...where we care about event "x". When "y" is popped, that shouldn't
  86        // pop the top stack -- we need to pop the stack a level down. Each
  87        // event tracking "x" creates a new stratum, and we keep track of where
  88        // timeline events are among the strata in order to keep stack depths
  89        // straight.
  90  
  91        $stratum = null;
  92        $strata = array();
  93  
  94        $ranges = array();
  95        foreach ($timeline as $timeline_event) {
  96          $id = $timeline_event['event']->getID();
  97          $type = $timeline_event['type'];
  98  
  99          switch ($type) {
 100            case 'start':
 101              $stack[] = $depth;
 102              $depth = 0;
 103              $stratum = count($stack);
 104              $strata[$id] = $stratum;
 105              $range_start = $timeline_event['at'];
 106              break;
 107            case 'end':
 108              if ($strata[$id] == $stratum) {
 109                if ($depth == 0) {
 110                  $ranges[] = array($range_start, $timeline_event['at']);
 111                  $depth = array_pop($stack);
 112                } else {
 113                  // Here, we've prematurely ended the current stratum. Merge all
 114                  // the higher strata into it. This looks like this:
 115                  //
 116                  //                 V
 117                  //                 V
 118                  //              |zzzzzzzz|
 119                  //           |xxxxx|
 120                  //        |yyyyyyyyyyyyy|
 121                  //   |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
 122  
 123                  $depth = array_pop($stack) + $depth;
 124                }
 125              } else {
 126                // Here, we've prematurely ended a deeper stratum. Merge higher
 127                // stata. This looks like this:
 128                //
 129                //                V
 130                //                V
 131                //              |aaaaaaa|
 132                //            |xxxxxxxxxxxxxxxxxxx|
 133                //          |zzzzzzzzzzzzz|
 134                //        |xxxxxxx|
 135                //     |yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy|
 136                //   |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
 137  
 138                $extra = $stack[$strata[$id]];
 139                unset($stack[$strata[$id] - 1]);
 140                $stack = array_values($stack);
 141                $stack[$strata[$id] - 1] += $extra;
 142              }
 143  
 144              // Regardless of how we got here, we need to merge down any higher
 145              // strata.
 146              $target = $strata[$id];
 147              foreach ($strata as $strata_id => $id_stratum) {
 148                if ($id_stratum >= $target) {
 149                  $strata[$strata_id]--;
 150                }
 151              }
 152              $stratum = count($stack);
 153  
 154              unset($strata[$id]);
 155              break;
 156            case 'push':
 157              $strata[$id] = $stratum;
 158              if ($depth == 0) {
 159                $ranges[] = array($range_start, $timeline_event['at']);
 160              }
 161              $depth++;
 162              break;
 163            case 'pop':
 164              if ($strata[$id] == $stratum) {
 165                $depth--;
 166                if ($depth == 0) {
 167                  $range_start = $timeline_event['at'];
 168                }
 169              } else {
 170                $stack[$strata[$id]]--;
 171              }
 172              unset($strata[$id]);
 173              break;
 174          }
 175        }
 176  
 177        // Filter out ranges with an indefinite start time. These occur when
 178        // popping the stack when there are multiple ongoing events.
 179        foreach ($ranges as $key => $range) {
 180          if ($range[0] == PHP_INT_MAX) {
 181            unset($ranges[$key]);
 182          }
 183        }
 184  
 185        $object_ranges[$base_phid][] = $ranges;
 186      }
 187  
 188      // Collapse all the ranges so we don't double-count time.
 189      foreach ($object_ranges as $phid => $ranges) {
 190        $object_ranges[$phid] = self::mergeTimeRanges(array_mergev($ranges));
 191      }
 192  
 193      foreach ($object_ranges as $phid => $ranges) {
 194        foreach ($ranges as $key => $range) {
 195          if ($range[1] == PHP_INT_MAX) {
 196            $ranges[$key][1] = null;
 197          }
 198        }
 199  
 200        $object_ranges[$phid] = new PhrequentTimeSlices(
 201          $phid,
 202          isset($object_ongoing[$phid]),
 203          $ranges);
 204      }
 205  
 206      // Reorder the ranges to be more stack-like, so the first item is the
 207      // top of the stack.
 208      $object_ranges = array_reverse($object_ranges, $preserve_keys = true);
 209  
 210      return $object_ranges;
 211    }
 212  
 213    /**
 214     * Returns the current list of work.
 215     */
 216    public function getCurrentWorkStack($now, $include_inactive = false) {
 217      $ranges = $this->getObjectTimeRanges();
 218  
 219      $results = array();
 220      $active = null;
 221      foreach ($ranges as $phid => $slices) {
 222        if (!$include_inactive) {
 223          if (!$slices->getIsOngoing()) {
 224            continue;
 225          }
 226        }
 227  
 228        $results[] = array(
 229          'phid' => $phid,
 230          'time' => $slices->getDuration($now),
 231          'ongoing' => $slices->getIsOngoing(),
 232        );
 233      }
 234  
 235      return $results;
 236    }
 237  
 238  
 239    /**
 240     * Merge a list of time ranges (pairs of `<start, end>` epochs) so that no
 241     * elements overlap. For example, the ranges:
 242     *
 243     *   array(
 244     *     array(50, 150),
 245     *     array(100, 175),
 246     *   );
 247     *
 248     * ...are merged to:
 249     *
 250     *   array(
 251     *     array(50, 175),
 252     *   );
 253     *
 254     * This is used to avoid double-counting time on objects which had timers
 255     * started multiple times.
 256     *
 257     * @param list<pair<int, int>> List of possibly overlapping time ranges.
 258     * @return list<pair<int, int>> Nonoverlapping time ranges.
 259     */
 260    public static function mergeTimeRanges(array $ranges) {
 261      $ranges = isort($ranges, 0);
 262  
 263      $result = array();
 264  
 265      $current = null;
 266      foreach ($ranges as $key => $range) {
 267        if ($current === null) {
 268          $current = $range;
 269          continue;
 270        }
 271  
 272        if ($range[0] <= $current[1]) {
 273          $current[1] = max($range[1], $current[1]);
 274          continue;
 275        }
 276  
 277        $result[] = $current;
 278        $current = $range;
 279      }
 280  
 281      $result[] = $current;
 282  
 283      return $result;
 284    }
 285  
 286  
 287    /**
 288     * Sort events in timeline order. Notably, for events which occur on the same
 289     * second, we want to process end events after start events.
 290     */
 291    public static function sortTimeline(array $u, array $v) {
 292      // If these events occur at different times, ordering is obvious.
 293      if ($u['at'] != $v['at']) {
 294        return ($u['at'] < $v['at']) ? -1 : 1;
 295      }
 296  
 297      $u_end = ($u['type'] == 'end' || $u['type'] == 'pop');
 298      $v_end = ($v['type'] == 'end' || $v['type'] == 'pop');
 299  
 300      $u_id = $u['event']->getID();
 301      $v_id = $v['event']->getID();
 302  
 303      if ($u_end == $v_end) {
 304        // These are both start events or both end events. Sort them by ID.
 305        if (!$u_end) {
 306          return ($u_id < $v_id) ? -1 : 1;
 307        } else {
 308          return ($u_id < $v_id) ? 1 : -1;
 309        }
 310      } else {
 311        // Sort them (start, end) if they're the same event, and (end, start)
 312        // otherwise.
 313        if ($u_id == $v_id) {
 314          return $v_end ? -1 : 1;
 315        } else {
 316          return $v_end ? 1 : -1;
 317        }
 318      }
 319  
 320      return 0;
 321    }
 322  
 323  }