This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Stack Overflow Q# 11965455

By: a guest on Aug 26th, 2012  |  syntax: PHP  |  size: 3.97 KB  |  views: 29  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. <?php
  2.  
  3. class LineSegment {
  4.         public $user_id;
  5.         public $start_point;
  6.         public $end_point;
  7.        
  8.         public function __construct($user_id, $start_value, $end_value) {
  9.                 $this->user_id = $user_id;
  10.                 $this->start_point = new Endpoint($start_value, $user_id, TRUE);
  11.                 $this->end_point = new Endpoint($end_value, $user_id, FALSE);
  12.         }
  13.        
  14.         public function __toString() {
  15.                 return "$user_id [{$start_point->value}, {$end_point->value}]";
  16.         }
  17. }
  18.  
  19. class Endpoint {
  20.         public $value;
  21.         public $user_id;
  22.         public $is_start;
  23.        
  24.         public function __construct($value, $user_id, $is_start) {
  25.                 $this->value = $value;
  26.                 $this->user_id = $user_id;
  27.                 $this->is_start = $is_start;
  28.         }
  29.        
  30.         public function __toString() {
  31.                 $location = $this->is_start ? "start" : "end";
  32.                 return "{$this->user_id}: {$this->value} ($location)";
  33.         }
  34. }
  35.  
  36. class ResultSegment {
  37.         public $user_ids;
  38.         public $start_value;
  39.         public $end_value;
  40.        
  41.         public $num_users;
  42.         public $duration;
  43.        
  44.         public function __construct($user_ids, $start_value, $end_value) {
  45.                 $this->user_ids = $user_ids;
  46.                 $this->start_value = $start_value;
  47.                 $this->end_value = $end_value;
  48.                 $this->num_users = count($user_ids);
  49.                 $this->duration = $end_value - $start_value; //assumption: values are numeric (insert your own function here)
  50.         }
  51. }
  52.  
  53. class Sweepline {
  54.         public $last_endpoint_value; //value of last encountered endpoint
  55.         public $last_endpoint_was_end; //last encountered endpoint was an end (right) endpoint
  56.         public $active_users; //set of user IDs (user_id => user_id)
  57.         public $result_segments; //value-sorted array of LineSegments (with user_id being the number of available users)
  58.        
  59.         public function __construct() {
  60.                 $this->last_endpoint_value = 0;
  61.                 $this->last_endpoint_was_end = false;
  62.                 $this->active_users = array();
  63.         }
  64.        
  65.         public function execute($endpoints) {
  66.                 $this->result_segments = array();
  67.                 foreach ($endpoints as $endpoint) {
  68.                         $this->advance($endpoint);
  69.                 }
  70.                 return $this->result_segments;
  71.         }
  72.        
  73.         public function advance(Endpoint $next_endpoint) {
  74.                 $user_id = $next_endpoint->user_id;
  75.                 if ($next_endpoint->is_start) {
  76.                         $this->active_users[$user_id] = $user_id;
  77.                 } else {
  78.                         //when multiple segments end at the same value, you only need one result
  79.                         if (!$this->last_endpoint_was_end) {
  80.                                 $result = new ResultSegment(array_values($this->active_users), $this->last_endpoint_value, $next_endpoint->value);
  81.                                 $this->result_segments[] = $result;
  82.                         }
  83.                         unset($this->active_users[$user_id]);
  84.                 }
  85.                 $this->last_endpoint_was_end = !$next_endpoint->is_start;
  86.                 $this->last_endpoint_value = $next_endpoint->value;
  87.         }
  88. }
  89.  
  90.  
  91. function endpoint_comparer(Endpoint &$point1, Endpoint &$point2) {
  92.         if ($point1->value == $point2->value) {
  93.                 if ($point1->is_start != $point2->is_start) {
  94.                         return $point1->is_start ? -1 : 1; //ending points before starting
  95.                 }
  96.         }
  97.         return $point1->value > $point2->value;
  98. }
  99.  
  100. function result_comparer(ResultSegment &$line1, ResultSegment &$line2) {
  101.         if ($line1->num_users == $line2->num_users) {
  102.                 return $line1->duration > $line2->duration;
  103.         }
  104.         return $line1->num_users > $line2->num_users;
  105. }
  106.  
  107.  
  108. //1) Create line-segments (assumption: for each line-segment, start_value is less than end_value)
  109. $segments = array(
  110.                 new LineSegment(1, 10, 20),
  111.                 new LineSegment(1, 40, 74),
  112.                 new LineSegment(2, 19, 25),
  113.                 new LineSegment(2, 34, 50),
  114.                 new LineSegment(3, 15, 25),
  115.                 new LineSegment(3, 55, 90),
  116.         );
  117.  
  118. //1a) TODO: merge same-user segments that start/end at the same time.
  119.  
  120. //2) create a sorted array of all endpoints (start and end)
  121. $endpoints = array();
  122. foreach ($segments as $segment) {
  123.         $endpoints[] = $segment->start_point;
  124.         $endpoints[] = $segment->end_point;
  125. }
  126. usort($endpoints, 'endpoint_comparer');
  127.  
  128. //3) Initialize sweep-line
  129. $sweepline = new Sweepline();
  130.  
  131. //4) Execute sweep-line
  132. $results = $sweepline->execute($endpoints);
  133.  
  134. //5) Sort results
  135. usort($results, 'result_comparer');
  136. $results = array_reverse($results);
  137.  
  138.  
  139. echo "<pre>";
  140. print_r($results);
  141. echo "</pre>";
clone this paste RAW Paste Data