Stable Sorting in PHP with the Schwartzian Transform

You have an array:

$object0 = (object)array('priority' => 5);
$object1 = (object)array('priority' => 10);
$object2 = (object)array('priority' => 5);
$my_array = array(
  0 => $object0,
  1 => $object1,
  2 => $object2,

Now let’s say you want to sort that array. You would probably call uasort($my_array $callback) with a callback to sort by the objects’ priority property. And you might end up with:

$my_array == array(
  0 => $object0,
  2 => $object2,
  1 => $object1,

Or, you might end up with:

$my_array == array(
  2 => $object2,
  0 => $object0,
  1 => $object1,

Keep calling uasort($my_array, $callback), and you might even switch back and forth between the two. What if you want to maintain the order of $object0 and $object2, no matter how many times you sort the array? There’s no native PHP function to accomplish this, but it’s fairly easily done using the Schwartzian Transform.

The Schwartzian Transform is a three step process: decorate, sort, undecorate. We decorate each item in the array by wrapping it in a more-easily sorted container. We then sort those containers, then remove our wrapper, leaving us with our original elements, only sorted.

For our array above, we would transform each item in the array into an array with three items: the priority, the index, and the the object.

array_walk( $my_array, create_function( '&$v, $k' , '$v = array( $v->priority, $k, $v );'));

PHP’s built-in asort() sorts this first by priority (array index 0), and if priorities are the same, then items by index (array index 1). Since every index is distinct, the sorting will never fall back to the third item in the array.


Finally, put all the items in the array back where we found them:

array_walk( $my_array, create_function( '&$v, $k', '$v = $v[2];'));

The Schwartzian Transform has the benefits of being both stable (multiple calls will produce the same result) and efficient (you only have to calculate the “priority” of each item once; helpful if it’s a more expensive operation).

Downgrade PHP to 5.2 on Ubuntu 10.04

As of version 6.14, Drupal works with PHP 5.3, but many essential modules still issue warnings (usually due to passing expressions by reference). If your Ubuntu 10.04 (Lucid Lynx) server is running 5.3, this script will automate the downgrade to the latest 5.2 by telling aptitude to use the source lists for Ubuntu 9.10 (Karmic Koala).

Thanks to Nick Veenhof, mrkandy, and their many commenters, from whom this script is derived.

php_installed=`dpkg -l | grep php| awk '{print $2}' |tr "\n" " "`
# remove all php packge
sudo aptitude purge `dpkg -l | grep php| awk '{print $2}' |tr "\n" " "`
# use karmic for php pakage
# pin-params:  a (archive), c (components), v (version), o (origin) and l (label).
echo -e "Package: php5\nPin: release a=karmic\nPin-Priority: 991\n"  | sudo tee /etc/apt/preferences.d/php > /dev/null
apt-cache search php5-|grep php5-|awk '{print "Package:", $1,"\nPin: release a=karmic\nPin-Priority: 991\n"}'|sudo tee -a /etc/apt/preferences.d/php > /dev/null
apt-cache search -n libapache2-mod-php5 |awk '{print "Package:", $1,"\nPin: release a=karmic\nPin-Priority: 991\n"}'| sudo tee -a /etc/apt/preferences.d/php > /dev/null
echo -e "Package: php-pear\nPin: release a=karmic\nPin-Priority: 991\n"  | sudo tee -a /etc/apt/preferences.d/php > /dev/null
# add karmic to source list
egrep '(main restricted|universe|multiverse)' /etc/apt/sources.list|grep -v "#"| sed s/lucid/karmic/g | sudo tee /etc/apt/sources.list.d/karmic.list > /dev/null
# update package database (use apt-get if aptitude crash)
sudo apt-get update
# install php
sudo apt-get install $php_installed
sudo aptitude hold `dpkg -l | grep php5| awk '{print $2}' |tr "\n" " "`

Of course, make sure to restart Apache when you’re finished.