SHOW:
|
|
- or go back to the newest paste.
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 | - | echo "next endpoint: " . $next_endpoint, "\n"; |
74 | + | |
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>"; |