Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:83995
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 74.125.82.175 as permitted sender)
Message-ID: <54F062EC.9000606@gmail.com>
Date: Fri, 27 Feb 2015 12:28:28 +0000
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: internals@lists.php.net
References: <CAGnBX03-qsCySW0qOZFWk60p1MaJe-ed1DN+z2fjAqJJLqu8fg@mail.gmail.com>
In-Reply-To: <CAGnBX03-qsCySW0qOZFWk60p1MaJe-ed1DN+z2fjAqJJLqu8fg@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [PHP-DEV] Feature request and RFC
From: rowan.collins@gmail.com (Rowan Collins)

Thomas Gielfeldt wrote on 24/02/2015 16:17:
> Hi internals.
>
> I've made PR proposing a feature request: A new interface Sortable.
>
> https://github.com/php/php-src/pull/1116
>
> If possible, I would like to create and RFC describing this in more detail,
> and perhaps get a voting on.

I think the reason this interface is proving hard to simplify is that 
you're putting too much of the responsibility on the implementing 
object. Most containers don't need or want to reimplement an entire 
quicksort algorithm, or be responsible for tracking the various types of 
comparison.

Ideally, you could start by writing an OO implementation of QuickSort 
which takes as its input an abstract "Collection" instead of an array, 
and look at what methods you end up wanting to call on that Collection. 
That might end up rather complex in practice, though, because the 
underlying data structures do make a difference to an efficient 
implementation.

However, the types of sort differ primarily in the way values are 
compared, so if the engine passed in an appropriate comparison callback, 
the interface needs only one method:

public function sort(callable $comparison_callback, boolean $preserve_keys)
where $comparison_callback is:
function($l_key, $l_value, $r_key, $r_value): int

The only flag that the object might want to care about is whether to 
preserve keys (asort, uasort, ksort, uksort), because it could allow 
optimisations rather than reindexing after the sort has completed. For 
everything else, it should just be repeatedly asking the engine "which 
of these two items should come first?" By passing both keys and values, 
ksort() can be implemented with the same callback signature, the only 
disadvantage being that the user callbacks to usort() and uksort() would 
need to be wrapped, with the engine basically emulating the following:

// For usort($object, $usort_callback)
$comparison_callback = function($l_key, $l_value, $r_key, $r_value) use 
($usort_callback) { return $usort_callback($l_value, $r_value); };
// For ksort($object, $ksort_callback)
$comparison_callback = function($l_key, $l_value, $r_key, $r_value) use 
($ksort_callback) { return $ksort_callback($l_key, $r_key); };

Regards,
-- 
Rowan Collins
[IMSoP]