Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?php
- class LineSegment {
- public $user_id;
- public $start_point;
- public $end_point;
- public function __construct($user_id, $start_value, $end_value) {
- $this->user_id = $user_id;
- $this->start_point = new Endpoint($start_value, $user_id, TRUE);
- $this->end_point = new Endpoint($end_value, $user_id, FALSE);
- }
- public function __toString() {
- return "$user_id [{$start_point->value}, {$end_point->value}]";
- }
- }
- class Endpoint {
- public $value;
- public $user_id;
- public $is_start;
- public function __construct($value, $user_id, $is_start) {
- $this->value = $value;
- $this->user_id = $user_id;
- $this->is_start = $is_start;
- }
- public function __toString() {
- $location = $this->is_start ? "start" : "end";
- return "{$this->user_id}: {$this->value} ($location)";
- }
- }
- class ResultSegment {
- public $user_ids;
- public $start_value;
- public $end_value;
- public $num_users;
- public $duration;
- public function __construct($user_ids, $start_value, $end_value) {
- $this->user_ids = $user_ids;
- $this->start_value = $start_value;
- $this->end_value = $end_value;
- $this->num_users = count($user_ids);
- $this->duration = $end_value - $start_value; //assumption: values are numeric (insert your own function here)
- }
- }
- class Sweepline {
- public $last_endpoint_value; //value of last encountered endpoint
- public $last_endpoint_was_end; //last encountered endpoint was an end (right) endpoint
- public $active_users; //set of user IDs (user_id => user_id)
- public $result_segments; //value-sorted array of LineSegments (with user_id being the number of available users)
- public function __construct() {
- $this->last_endpoint_value = 0;
- $this->last_endpoint_was_end = false;
- $this->active_users = array();
- }
- public function execute($endpoints) {
- $this->result_segments = array();
- foreach ($endpoints as $endpoint) {
- $this->advance($endpoint);
- }
- return $this->result_segments;
- }
- public function advance(Endpoint $next_endpoint) {
- $user_id = $next_endpoint->user_id;
- if ($next_endpoint->is_start) {
- $this->active_users[$user_id] = $user_id;
- } else {
- //when multiple segments end at the same value, you only need one result
- if (!$this->last_endpoint_was_end) {
- $result = new ResultSegment(array_values($this->active_users), $this->last_endpoint_value, $next_endpoint->value);
- $this->result_segments[] = $result;
- }
- unset($this->active_users[$user_id]);
- }
- $this->last_endpoint_was_end = !$next_endpoint->is_start;
- $this->last_endpoint_value = $next_endpoint->value;
- }
- }
- function endpoint_comparer(Endpoint &$point1, Endpoint &$point2) {
- if ($point1->value == $point2->value) {
- if ($point1->is_start != $point2->is_start) {
- return $point1->is_start ? -1 : 1; //ending points before starting
- }
- }
- return $point1->value > $point2->value;
- }
- function result_comparer(ResultSegment &$line1, ResultSegment &$line2) {
- if ($line1->num_users == $line2->num_users) {
- return $line1->duration > $line2->duration;
- }
- return $line1->num_users > $line2->num_users;
- }
- //1) Create line-segments (assumption: for each line-segment, start_value is less than end_value)
- $segments = array(
- new LineSegment(1, 10, 20),
- new LineSegment(1, 40, 74),
- new LineSegment(2, 19, 25),
- new LineSegment(2, 34, 50),
- new LineSegment(3, 15, 25),
- new LineSegment(3, 55, 90),
- );
- //1a) TODO: merge same-user segments that start/end at the same time.
- //2) create a sorted array of all endpoints (start and end)
- $endpoints = array();
- foreach ($segments as $segment) {
- $endpoints[] = $segment->start_point;
- $endpoints[] = $segment->end_point;
- }
- usort($endpoints, 'endpoint_comparer');
- //3) Initialize sweep-line
- $sweepline = new Sweepline();
- //4) Execute sweep-line
- $results = $sweepline->execute($endpoints);
- //5) Sort results
- usort($results, 'result_comparer');
- $results = array_reverse($results);
- echo "<pre>";
- print_r($results);
- echo "</pre>";
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement