|
1
|
|
|
<?php |
|
2
|
|
|
/** |
|
3
|
|
|
* @author Boudewijn Schoon <[email protected]> |
|
4
|
|
|
* @copyright Zicht Online <http://zicht.nl> |
|
5
|
|
|
*/ |
|
6
|
|
|
|
|
7
|
|
|
namespace Zicht\Itertools\lib; |
|
8
|
|
|
|
|
9
|
|
|
use Zicht\Itertools\lib\Interfaces\FiniteIterableInterface; |
|
10
|
|
|
use Zicht\Itertools\lib\Traits\FiniteIterableTrait; |
|
11
|
|
|
|
|
12
|
|
|
/** |
|
13
|
|
|
* Class SortedIterator |
|
14
|
|
|
* |
|
15
|
|
|
* @package Zicht\Itertools\lib |
|
16
|
|
|
*/ |
|
17
|
|
|
class SortedIterator extends \IteratorIterator implements FiniteIterableInterface |
|
18
|
|
|
{ |
|
19
|
|
|
use FiniteIterableTrait; |
|
20
|
|
|
|
|
21
|
|
|
/** |
|
22
|
|
|
* SortedIterator constructor. |
|
23
|
|
|
* |
|
24
|
|
|
* @param \Closure $func |
|
25
|
|
|
* @param \Iterator $iterable |
|
26
|
|
|
* @param bool $reverse |
|
27
|
|
|
*/ |
|
28
|
32 |
|
public function __construct(\Closure $func, \Iterator $iterable, $reverse = false) |
|
29
|
|
|
{ |
|
30
|
32 |
|
if ($reverse) { |
|
31
|
|
View Code Duplication |
$cmp = function ($a, $b) use ($func) { |
|
|
|
|
|
|
32
|
2 |
|
$orderA = $a['order']; |
|
33
|
2 |
|
$orderB = $b['order']; |
|
34
|
2 |
|
return $orderA == $orderB ? 0 : ($orderA < $orderB ? 1 : -1); |
|
35
|
2 |
|
}; |
|
36
|
|
|
} else { |
|
37
|
30 |
View Code Duplication |
$cmp = function ($a, $b) use ($func) { |
|
|
|
|
|
|
38
|
30 |
|
$orderA = $a['order']; |
|
39
|
30 |
|
$orderB = $b['order']; |
|
40
|
30 |
|
return $orderA == $orderB ? 0 : ($orderA < $orderB ? -1 : 1); |
|
41
|
30 |
|
}; |
|
42
|
|
|
} |
|
43
|
|
|
|
|
44
|
32 |
|
$data = []; |
|
45
|
32 |
|
foreach ($iterable as $key => $value) { |
|
46
|
32 |
|
$data [] = ['key' => $key, 'value' => $value, 'order' => call_user_func($func, $value, $key)]; |
|
47
|
|
|
} |
|
48
|
|
|
|
|
49
|
32 |
|
$this->mergeSort($data, $cmp); |
|
50
|
|
|
|
|
51
|
32 |
|
parent::__construct(new \ArrayIterator($data)); |
|
52
|
32 |
|
} |
|
53
|
|
|
|
|
54
|
|
|
/** |
|
55
|
|
|
* @{inheritDoc} |
|
56
|
|
|
*/ |
|
57
|
30 |
|
public function key() |
|
58
|
|
|
{ |
|
59
|
30 |
|
return $this->getInnerIterator()->current()['key']; |
|
60
|
|
|
} |
|
61
|
|
|
|
|
62
|
|
|
/** |
|
63
|
|
|
* @{inheritDoc} |
|
64
|
|
|
*/ |
|
65
|
30 |
|
public function current() |
|
66
|
|
|
{ |
|
67
|
30 |
|
return $this->getInnerIterator()->current()['value']; |
|
68
|
|
|
} |
|
69
|
|
|
|
|
70
|
|
|
/** |
|
71
|
|
|
* As the manual says, "If two members compare as equal, their |
|
72
|
|
|
* order in the sorted array is undefined." This means that the |
|
73
|
|
|
* sort used is not "stable" and may change the order of elements |
|
74
|
|
|
* that compare equal. |
|
75
|
|
|
* |
|
76
|
|
|
* Sometimes you really do need a stable sort. For example, if you |
|
77
|
|
|
* sort a list by one field, then sort it again by another field, |
|
78
|
|
|
* but don't want to lose the ordering from the previous field. |
|
79
|
|
|
* In that case it is better to use usort with a comparison |
|
80
|
|
|
* function that takes both fields into account, but if you can't |
|
81
|
|
|
* do that then use the function below. It is a merge sort, which |
|
82
|
|
|
* is guaranteed O(n*log(n)) complexity, which means it stays |
|
83
|
|
|
* reasonably fast even when you use larger lists (unlike |
|
84
|
|
|
* bubblesort and insertion sort, which are O(n^2)). |
|
85
|
|
|
* |
|
86
|
|
|
* http://www.php.net/manual/en/function.usort.php#38827 |
|
87
|
|
|
* |
|
88
|
|
|
* @param array &$array |
|
89
|
|
|
* @param \Closure $cmp_function |
|
90
|
|
|
*/ |
|
91
|
32 |
|
protected function mergeSort(array &$array, \Closure $cmp_function) |
|
92
|
|
|
{ |
|
93
|
|
|
// Arrays of size < 2 require no action. |
|
94
|
32 |
|
if (count($array) < 2) { |
|
95
|
32 |
|
return; |
|
96
|
|
|
} |
|
97
|
|
|
|
|
98
|
|
|
// Split the array in half |
|
99
|
32 |
|
$halfway = count($array) / 2; |
|
100
|
32 |
|
$array1 = array_slice($array, 0, $halfway); |
|
101
|
32 |
|
$array2 = array_slice($array, $halfway); |
|
102
|
|
|
|
|
103
|
|
|
// Recurse to sort the two halves |
|
104
|
32 |
|
$this->mergesort($array1, $cmp_function); |
|
105
|
32 |
|
$this->mergesort($array2, $cmp_function); |
|
106
|
|
|
|
|
107
|
|
|
// If all of $array1 is <= all of $array2, just append them. |
|
108
|
32 |
|
if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) { |
|
109
|
28 |
|
$array = array_merge($array1, $array2); |
|
110
|
28 |
|
return; |
|
111
|
|
|
} |
|
112
|
|
|
|
|
113
|
|
|
// Merge the two sorted arrays into a single sorted array |
|
114
|
19 |
|
$array = []; |
|
115
|
19 |
|
$ptr1 = $ptr2 = 0; |
|
116
|
19 |
|
while ($ptr1 < count($array1) && $ptr2 < count($array2)) { |
|
117
|
19 |
|
if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) { |
|
118
|
8 |
|
$array[] = $array1[$ptr1++]; |
|
119
|
|
|
} else { |
|
120
|
19 |
|
$array[] = $array2[$ptr2++]; |
|
121
|
|
|
} |
|
122
|
|
|
} |
|
123
|
|
|
|
|
124
|
|
|
// Merge the remainder |
|
125
|
19 |
|
while ($ptr1 < count($array1)) { |
|
126
|
17 |
|
$array[] = $array1[$ptr1++]; |
|
127
|
|
|
} |
|
128
|
19 |
|
while ($ptr2 < count($array2)) { |
|
129
|
8 |
|
$array[] = $array2[$ptr2++]; |
|
130
|
|
|
} |
|
131
|
19 |
|
return; |
|
132
|
|
|
} |
|
133
|
|
|
} |
|
134
|
|
|
|
zicht /
itertools
Loading history...
Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation.
You can also find more detailed suggestions in the “Code” section of your repository.