SortedIterator::mergeSort() - Code Metrics - Inspection of "Merge pull request #23 from zicht/feature/propagat..." - zicht/itertools - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 46a804...2137d7 )

unknown

created 2017-02-16 17:00 UTC

SortedIterator::mergeSort() C

↳ Parent: SortedIterator

Complexity

Conditions	8
Paths	14

Size

Total Lines	42
Code Lines	23

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	22
CRAP Score	8

Importance

Changes

Metric	Value
cc	8
eloc	23
c	0
b	0
f	0
nc	14
nop	2
dl	0
loc	42
ccs	22
cts	22
cp	1
crap	8
rs	5.3846

<?php
/**
 * @author Boudewijn Schoon <[email protected]>
 * @copyright Zicht Online <http://zicht.nl>
 */

namespace Zicht\Itertools\lib;

use Zicht\Itertools\lib\Traits\AllTrait;
use Zicht\Itertools\lib\Traits\AnyTrait;
use Zicht\Itertools\lib\Traits\ArrayAccessTrait;
use Zicht\Itertools\lib\Traits\ChainTrait;
use Zicht\Itertools\lib\Traits\CountableTrait;
use Zicht\Itertools\lib\Traits\CycleTrait;
use Zicht\Itertools\lib\Traits\DebugInfoTrait;
use Zicht\Itertools\lib\Traits\FilterTrait;
use Zicht\Itertools\lib\Traits\FirstTrait;
use Zicht\Itertools\lib\Traits\GroupByTrait;
use Zicht\Itertools\lib\Traits\ItemsTrait;
use Zicht\Itertools\lib\Traits\KeysTrait;
use Zicht\Itertools\lib\Traits\LastTrait;
use Zicht\Itertools\lib\Traits\MapByTrait;
use Zicht\Itertools\lib\Traits\MapTrait;
use Zicht\Itertools\lib\Traits\ReduceTrait;
use Zicht\Itertools\lib\Traits\ReversedTrait;
use Zicht\Itertools\lib\Traits\SliceTrait;
use Zicht\Itertools\lib\Traits\SortedTrait;
use Zicht\Itertools\lib\Traits\ToArrayTrait;
use Zicht\Itertools\lib\Traits\UniqueTrait;
use Zicht\Itertools\lib\Traits\ValuesTrait;
use Zicht\Itertools\lib\Traits\ZipTrait;

/**
 * Class SortedIterator
 *
 * @package Zicht\Itertools\lib
 */
class SortedIterator extends \IteratorIterator implements \Countable, \ArrayAccess
{
    use ArrayAccessTrait;
    use CountableTrait;
    use DebugInfoTrait;

    // Fluent interface traits
    use AllTrait;
    use AnyTrait;
    use ChainTrait;
    use CycleTrait;
    use FilterTrait;
    use FirstTrait;
    use GroupByTrait;
    use ItemsTrait;
    use KeysTrait;
    use LastTrait;
    use MapByTrait;
    use MapTrait;
    use ReduceTrait;
    use ReversedTrait;
    use SliceTrait;
    use SortedTrait;
    use ToArrayTrait;
    use UniqueTrait;
    use ValuesTrait;
    use ZipTrait;

    /**
     * SortedIterator constructor.
     *
     * @param \Closure $func
     * @param \Iterator $iterable
     * @param bool $reverse
     */
    public function __construct(\Closure $func, \Iterator $iterable, $reverse = false)
    {
        if ($reverse) {
            $cmp = function ($a, $b) use ($func) {

                $orderA = $a['order'];
                $orderB = $b['order'];
                return $orderA == $orderB ? 0 : ($orderA < $orderB ? 1 : -1);
            };
        } else {
            $cmp = function ($a, $b) use ($func) {

                $orderA = $a['order'];
                $orderB = $b['order'];
                return $orderA == $orderB ? 0 : ($orderA < $orderB ? -1 : 1);
            };
        }

        $data = [];
        foreach ($iterable as $key => $value) {
            $data [] = ['key' => $key, 'value' => $value, 'order' => call_user_func($func, $value, $key)];
        }

        $this->mergeSort($data, $cmp);

        parent::__construct(new \ArrayIterator($data));
    }

    /**
     * @{inheritDoc}
     */
    public function key()
    {
        return $this->getInnerIterator()->current()['key'];
    }

    /**
     * @{inheritDoc}
     */
    public function current()
    {
        return $this->getInnerIterator()->current()['value'];
    }

    /**
     * As the manual says, "If two members compare as equal, their
     * order in the sorted array is undefined."  This means that the
     * sort used is not "stable" and may change the order of elements
     * that compare equal.
     *
     * Sometimes you really do need a stable sort. For example, if you
     * sort a list by one field, then sort it again by another field,
     * but don't want to lose the ordering from the previous field.
     * In that case it is better to use usort with a comparison
     * function that takes both fields into account, but if you can't
     * do that then use the function below. It is a merge sort, which
     * is guaranteed O(n*log(n)) complexity, which means it stays
     * reasonably fast even when you use larger lists (unlike
     * bubblesort and insertion sort, which are O(n^2)).
     *
     * http://www.php.net/manual/en/function.usort.php#38827
     *
     * @param array &$array
     * @param \Closure $cmp_function
     */
    protected function mergeSort(array &$array, \Closure $cmp_function)
    {
        // Arrays of size < 2 require no action.
        if (count($array) < 2) {
            return;
        }

        // Split the array in half
        $halfway = count($array) / 2;
        $array1 = array_slice($array, 0, $halfway);
        $array2 = array_slice($array, $halfway);

        // Recurse to sort the two halves
        $this->mergesort($array1, $cmp_function);
        $this->mergesort($array2, $cmp_function);

        // If all of $array1 is <= all of $array2, just append them.
        if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
            $array = array_merge($array1, $array2);
            return;
        }

        // Merge the two sorted arrays into a single sorted array
        $array = [];
        $ptr1 = $ptr2 = 0;
        while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
            if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
                $array[] = $array1[$ptr1++];
            } else {
                $array[] = $array2[$ptr2++];
            }
        }

        // Merge the remainder
        while ($ptr1 < count($array1)) {
            $array[] = $array1[$ptr1++];
        }
        while ($ptr2 < count($array2)) {
            $array[] = $array2[$ptr2++];
        }
        return;
    }
}


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\Traits\AllTrait;
10			use Zicht\Itertools\lib\Traits\AnyTrait;
11			use Zicht\Itertools\lib\Traits\ArrayAccessTrait;
12			use Zicht\Itertools\lib\Traits\ChainTrait;
13			use Zicht\Itertools\lib\Traits\CountableTrait;
14			use Zicht\Itertools\lib\Traits\CycleTrait;
15			use Zicht\Itertools\lib\Traits\DebugInfoTrait;
16			use Zicht\Itertools\lib\Traits\FilterTrait;
17			use Zicht\Itertools\lib\Traits\FirstTrait;
18			use Zicht\Itertools\lib\Traits\GroupByTrait;
19			use Zicht\Itertools\lib\Traits\ItemsTrait;
20			use Zicht\Itertools\lib\Traits\KeysTrait;
21			use Zicht\Itertools\lib\Traits\LastTrait;
22			use Zicht\Itertools\lib\Traits\MapByTrait;
23			use Zicht\Itertools\lib\Traits\MapTrait;
24			use Zicht\Itertools\lib\Traits\ReduceTrait;
25			use Zicht\Itertools\lib\Traits\ReversedTrait;
26			use Zicht\Itertools\lib\Traits\SliceTrait;
27			use Zicht\Itertools\lib\Traits\SortedTrait;
28			use Zicht\Itertools\lib\Traits\ToArrayTrait;
29			use Zicht\Itertools\lib\Traits\UniqueTrait;
30			use Zicht\Itertools\lib\Traits\ValuesTrait;
31			use Zicht\Itertools\lib\Traits\ZipTrait;
32
33			/**
34			* Class SortedIterator
35			*
36			* @package Zicht\Itertools\lib
37			*/
38			class SortedIterator extends \IteratorIterator implements \Countable, \ArrayAccess
39			{
40			use ArrayAccessTrait;
41			use CountableTrait;
42			use DebugInfoTrait;
43
44			// Fluent interface traits
45			use AllTrait;
46			use AnyTrait;
47			use ChainTrait;
48			use CycleTrait;
49			use FilterTrait;
50			use FirstTrait;
51			use GroupByTrait;
52			use ItemsTrait;
53			use KeysTrait;
54			use LastTrait;
55			use MapByTrait;
56			use MapTrait;
57			use ReduceTrait;
58			use ReversedTrait;
59			use SliceTrait;
60			use SortedTrait;
61			use ToArrayTrait;
62			use UniqueTrait;
63			use ValuesTrait;
64			use ZipTrait;
65
66			/**
67			* SortedIterator constructor.
68			*
69			* @param \Closure $func
70			* @param \Iterator $iterable
71			* @param bool $reverse
72			*/
73	32		public function __construct(\Closure $func, \Iterator $iterable, $reverse = false)
74			{
75	32		if ($reverse) {
76		View Code Duplication	$cmp = function ($a, $b) use ($func) {
			0 ignored issues – show Duplication introduced 2017-01-12 12:49 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. 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. Loading history...
77	2		$orderA = $a['order'];
78	2		$orderB = $b['order'];
79	2		return $orderA == $orderB ? 0 : ($orderA < $orderB ? 1 : -1);
80	2		};
81			} else {
82	30	View Code Duplication	$cmp = function ($a, $b) use ($func) {
			0 ignored issues – show Duplication introduced 2017-01-12 12:49 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. 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. Loading history...
83	30		$orderA = $a['order'];
84	30		$orderB = $b['order'];
85	30		return $orderA == $orderB ? 0 : ($orderA < $orderB ? -1 : 1);
86	30		};
87			}
88
89	32		$data = [];
90	32		foreach ($iterable as $key => $value) {
91	32		$data [] = ['key' => $key, 'value' => $value, 'order' => call_user_func($func, $value, $key)];
92			}
93
94	32		$this->mergeSort($data, $cmp);
95
96	32		parent::__construct(new \ArrayIterator($data));
97	32		}
98
99			/**
100			* @{inheritDoc}
101			*/
102	30		public function key()
103			{
104	30		return $this->getInnerIterator()->current()['key'];
105			}
106
107			/**
108			* @{inheritDoc}
109			*/
110	30		public function current()
111			{
112	30		return $this->getInnerIterator()->current()['value'];
113			}
114
115			/**
116			* As the manual says, "If two members compare as equal, their
117			* order in the sorted array is undefined." This means that the
118			* sort used is not "stable" and may change the order of elements
119			* that compare equal.
120			*
121			* Sometimes you really do need a stable sort. For example, if you
122			* sort a list by one field, then sort it again by another field,
123			* but don't want to lose the ordering from the previous field.
124			* In that case it is better to use usort with a comparison
125			* function that takes both fields into account, but if you can't
126			* do that then use the function below. It is a merge sort, which
127			* is guaranteed O(n*log(n)) complexity, which means it stays
128			* reasonably fast even when you use larger lists (unlike
129			* bubblesort and insertion sort, which are O(n^2)).
130			*
131			* http://www.php.net/manual/en/function.usort.php#38827
132			*
133			* @param array &$array
134			* @param \Closure $cmp_function
135			*/
136	32		protected function mergeSort(array &$array, \Closure $cmp_function)
137			{
138			// Arrays of size < 2 require no action.
139	32		if (count($array) < 2) {
140	32		return;
141			}
142
143			// Split the array in half
144	32		$halfway = count($array) / 2;
145	32		$array1 = array_slice($array, 0, $halfway);
146	32		$array2 = array_slice($array, $halfway);
147
148			// Recurse to sort the two halves
149	32		$this->mergesort($array1, $cmp_function);
150	32		$this->mergesort($array2, $cmp_function);
151
152			// If all of $array1 is <= all of $array2, just append them.
153	32		if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
154	28		$array = array_merge($array1, $array2);
155	28		return;
156			}
157
158			// Merge the two sorted arrays into a single sorted array
159	19		$array = [];
160	19		$ptr1 = $ptr2 = 0;
161	19		while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
162	19		if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
163	8		$array[] = $array1[$ptr1++];
164			} else {
165	19		$array[] = $array2[$ptr2++];
166			}
167			}
168
169			// Merge the remainder
170	19		while ($ptr1 < count($array1)) {
171	17		$array[] = $array1[$ptr1++];
172			}
173	19		while ($ptr2 < count($array2)) {
174	8		$array[] = $array2[$ptr2++];
175			}
176	19		return;
177			}
178			}
179

zicht / itertools

Push — master ( 46a804...2137d7 )

SortedIterator::mergeSort() C

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like