Sorting multi-dimensional array by weighted value

Question

There are numerous questions here asking how to sort a multi-dimensional array in PHP. The answer is usort(). I know that. But I have a question that takes it a bit further, and I couldn't see a similar answer here.

I have an array of records, each of which includes a country ID (or a country name if you prefer; it's not relevant).

My task is to sort the array in such a way as to favour certain countries. This is dynamic -- ie the choice of countries to favour is determined by the user's config. I have a separate array which specifies the required sort order for the first few countries; results from other countries would just be left unsorted at the end of the list.

So the question is: how do I get the this sort criteria into usort() without resorting to using a global variable. And preferably without injecting the criteria array into every element of the main array ('coz if I'm going to loop it anyway, what's the point in using usort() at all?)

Please note: Since it's going to be relevant to the answers here, I'm stuck on PHP 5.2 for the time being, so I can't use an anonymous function. We are in the process of upgrading, but for now I need answers that will work for 5.2. (answers for 5.3/5.4 will be welcome too, especially if they make it significantly easier, but I won't be able to use them)

Earnest

Still hoping for an answer that doesn't involve globals or any awkward constructs, so I'm putting up a bounty for this. – Earnest

Not sure if this is relevant or not, but if you're fetching the records from a database, you could simply add another column to the table, like relativeOrder and do something like SELECT name FROM countries ORDER BY relativeOrder – Huntington

Answer 1

You explicitly write that you do not want to have global variables, so I do not make you a suggestion with static variables as well because those are actually global variables - and those are not needed at all.

In PHP 5.2 (and earlier) if you need call context within the callback, you can create your context by making use of a class of it's own that carries it:

class CallContext
{
}

For example you have the compare function for sort:

class CallContext
{
    ...
    public function compare($a, $b)
    {
         return $this->weight($a) - $this->weight($b);
    }

    public function getCallback()
    {
         return array($this, 'compare');
    }
    ...
}

That function can be used as the following as a callback with usort then:

$context = new CallContext();

usort($array, $context->getCallback());

Pretty straight forward. The private implementation of CallContext::weight is still missing, and from your question we know it needs some sort data and information. For example the name of the key of the country id in each record. Lets assume records are Stdclass objects so to get the weight of one record the context class needs to know the name of the property, the sort-order you define your own and a sort-value for those country-ids that are not defined in the custom sort order (the others, the rest).

These configuration values are given with the constructor function (ctor in short) and are stored as private members. The missing weight function then converts a record into the sort-value based on that information:

class CallContext
{
    private $property, $sortOrder, $sortOther;

    public function __construct($property, $sortOrder, $sortOther = 9999)
    {
        $this->property = $property;
        $this->sortOrder = $sortOrder;
        $this->sortOther = $sortOther;
    }

    private function weight($object) {
        if (!is_object($object)) {
            throw new InvalidArgumentException(sprintf('Not an object: %s.', print_r($object, 1)));
        }
        if (!isset($object->{$this->property})) {
            throw new InvalidArgumentException(sprintf('Property "%s" not found in object: %s.', $this->property, print_r($object, 1)));
        }
        $value = $object->{$this->property};
        return isset($this->sortOrder[$value])
               ? $this->sortOrder[$value]
               : $this->sortOther;
    }
    ...

The usage now extends to the following:

$property = 'country';
$order = array(
    # country ID => sort key (lower is first)
    46 => 1,
    45 => 2
);
$context = new CallContext('country', $order);
usort($array, $context->getCallback());

With the same principle you can very often convert any PHP 5.3 closure with use clauses to PHP 5.2. The variables from the use clause become private members injected with construction.

This variant does not only prevent the usage of static, it also makes visible that you have got some mapping per each element and as both elements are treated equal, it makes use of a private implementation of some weight function which works very well with usort.

I hope this is helpful.

Nganngc

I prefer this approach to Super::$tatic :) – Grandiloquence

@Leigh: Sure, but as this requires paying high royalty fees, I did not suggest it :D – Nganngc

I prefer this option to @Grampa's answer. They're similar, but as you say, this one avoids any kind of global, even on hiding in a class as a static. This is good. I don't know what you mean by your comment about royalty fees, though??? – Earnest

@SDC: That is a joke between my friend Leigh and me, you can learn more about the concepts of super-static with this in-depth chart about the silvery bullet nature of super static: i.sstatic.net/WhPyr.png or this learning image: i.imgur.com/RJEsz.png - bascially a joke about when some user asks on SO for how to prevent global variables and then some ohter users suggest a static variable instead "because it ain't global" (sigh). The price for that attitude is high, so we call that you need to pay high royalty fees using Super::$tatic - that's all ;) – Nganngc

The bounty is yours. Thank you for your help. If nothing else, this episode is giving me some ammunition for getting our PHP version upgraded, which can only be a good thing. – Earnest

@SDC: Thanks and yes, PHP 5.3 compared to PHP 5.2 is much faster, too. I really did bite my ass because I switched so late. I mean much faster. And with PHP 5.4 it should be again be much faster, but I have not played around with it yet that much. But since about one/two weeks I am evaluating it more straight forward. – Nganngc

Answer 2

You might not want a global variable, but you need something that behaves like one. You could use a class with static methods and parameters. It won't pollute the global scope that much and it would still function the way you need it.

class CountryCompare {
    public static $country_priorities;

    public static function compare( $a, $b ) {
        // Some custom sorting criteria
        // Work with self::country_priorities
    }

    public static function sort( $countries ) {
        return usort( $countries, array( 'CountryCompare', 'compare' ) );
    }
}

Then just call it like this:

CountryCompare::country_priorities = loadFromConfig();
CountryCompare::sort( $countries );

Nanji

This looks like it might be about the closest I'll get to the answer I want. +1 for now; will accept and award bounty later if nothing else comes along that's better. Thank you for your help. :) – Earnest

Another global variable that is not a global variable but behaves like one is a so called superglobal variable. For example $GLOBALS. You could just use $GLOBALS['country_priorities'] which is similar to CountryCompare::$country_priorities - a global variable that by name is not a global variable but behaves like it. ^^ – Nganngc

Hmm, I now prefer @hakra's answer, so he's now on course for the bounty. But Jack's answer is the one I really wanted... too bad I can't use it. So frustrating to be stuck on an old version of PHP. – Earnest

Bounty goes to hakra, but thank you for your help. If nothing else, this episode is giving me some ammunition for getting our PHP version upgraded, which can only be a good thing. – Earnest

Answer 3

You can use closures (PHP >= 5.3):

$weights = array( ... );
usort($records, function($a, $b) use ($weights) {
    // use $weights in here as usual and perform your sort logic
});

Wolfsbane

This would be perfect if I could use 5.3. I'm sure we'll upgrade soon. No bounty for you, but +1 because I did say 5.3 answers would be welcome as well. – Earnest

Yes, it's complicated to turn a closure with use clause to something working in PHP 5.2. Another trick is to encapsulate the details as well (I might add that to the answer later probably) so you can easily change when you change the PHP version sometimes in the future w/o having too many issues with the rest of the codebase. – Nganngc

@Earnest Too bad you can't switch to 5.3 yet :) of course, there's the simulation ... #2209827 – Bechler

I guess that question is asking pretty much the same as I am. Bounty goes to hakra. But thank you for your answer. If nothing else, this episode is giving me some solid ammunition for getting our PHP version upgraded, which can only be a good thing. – Earnest

@Jack: That is a nice reference, however I'd say there is some room for improvement. The accepted answer so far however does show the problematic areas that need to be circumvented. – Nganngc

@hakra I agree, my former colleague wrote a solution in that thread as well - techblog.triptic.nl/… - but that's not great either because it uses create_function(); guess time (and upgrades) will solve all problems :) – Bechler

Yeah and all static and such. I'd say that can be done better, but each solution is for it's case. If it did cure some problem, why not. But I would not say it is particularly flexible. – Nganngc

Answer 4

See Demo : http://codepad.org/vDI2k4n6

$arrayMonths = array(
       'jan' => array(1, 8, 5,4),
       'feb' => array(10,12,15,11),
       'mar' => array(12, 7, 4, 3),
       'apr' => array(10,16,7,17),
    );

$position = array("Foo1","Foo2","Foo3","FooN");
$set = array();

foreach($arrayMonths as $key => $value)
{
    $max = max($value);
    $pos = array_search($max, $value);
    $set[$key][$position[$pos]] = $max ;
}


function cmp($a, $b)
{
    foreach($a as $key => $value )
    {
        foreach ($b  as $bKey => $bValue)
        {
            return $bValue - $value ;
        }
    }

}

uasort($set,"cmp");
var_dump($set);

output

array
      'apr' => 
        array
          'FooN' => int 17
      'feb' => 
        array
          'Foo3' => int 15
      'mar' => 
        array
          'Foo1' => int 12
      'jan' => 
        array
          'Foo2' => int 8

another example:-

Sorting a Multi-Dimensional Array with PHP

http://www.firsttube.com/read/sorting-a-multi-dimensional-array-with-php/

Every so often I find myself with a multidimensional array that I want to sort by a value in a sub-array. I have an array that might look like this:

//an array of some songs I like
$songs =  array(
        '1' => array('artist'=>'The Smashing Pumpkins', 'songname'=>'Soma'),
        '2' => array('artist'=>'The Decemberists', 'songname'=>'The Island'),
        '3' => array('artist'=>'Fleetwood Mac', 'songname' =>'Second-hand News')
    );

The problem is thus: I’d like to echo out the songs I like in the format “Songname (Artist),” and I’d like to do it alphabetically by artist. PHP provides many functions for sorting arrays, but none will work here. ksort() will allow me to sort by key, but the keys in the $songs array are irrelevant. asort() allows me to sort and preserves keys, but it will sort $songs by the value of each element, which is also useless, since the value of each is “array()”. usort() is another possible candidate and can do multi-dimensional sorting, but it involves building a callback function and is often pretty long-winded. Even the examples in the PHP docs references specific keys.

So I developed a quick function to sort by the value of a key in a sub-array. Please note this version does a case-insensitive sort. See subval_sort() below.

function subval_sort($a,$subkey) {
    foreach($a as $k=>$v) {
        $b[$k] = strtolower($v[$subkey]);
    }
    asort($b);
    foreach($b as $key=>$val) {
        $c[] = $a[$key];
    }
    return $c;
}

To use it on the above, I would simply type:

$songs = subval_sort($songs,'artist'); 
print_r($songs);

This is what you should expect see:

Array
(
    [0] => Array
        (
            [artist] => Fleetwood Mac
            [song] => Second-hand News
        )

    [1] => Array
        (
            [artist] => The Decemberists
            [song] => The Island
        )

    [2] => Array
        (
            [artist] => The Smashing Pumpkins
            [song] => Cherub Rock
        )

)

The songs, sorted by artist.

Emanuele

Answer 5

The answer to your question is indeed in the usort() function. However, what you need to do is write the function that you pass to it is doing the weighting for you properly.

Most of the time, you have something like

if($a>$b)
{
    return $a;
}

But what you need to do is something along the lines of

if($a>$b || $someCountryID != 36)
{
    return $a;
}
else
{
    return $b;
}

Triatomic

Yes, indeed. This would be great if the weighted country was a fixed value, but if it's dynamic, how to get that countryID into the usort function? – Earnest

@Earnest You know which CountryIDs are the ones you care about, hardcode them into function to take care of the sorting? – Triatomic

the whole point is that they're not fixed; it can't be hardcoded. The user gets to decide which country/countries to weight. – Earnest

@Earnest Seeing as you have the user preferences, why don't you pop them into an array (say a SESSION or a STATIC) and have the function access that variable to make the correct return value? – Triatomic

Yeah. I was trying to avoid using a global. If that's the answer, then so be it, but I was hoping for something better. – Earnest

@Earnest It's the best I can offer. If someone with more trickery up their sleeve can provide a trickier solution, great, otherwise you might be stuck with my answer :( – Triatomic

You can also encapsulate this logic inside a class and have the countries array as a member of this class? It's the same, but it kind of limits how "global" the array is. – Usual

Answer 6

You need to use ksort to sort by weight, not usort. That will be much cleaner.

Arrange your data in an associative array $weighted_data in the format weight => country_data_struct. This is a very intuitive form of presentation for weighted data. Then run

krsort($weighted_data)

Menides