note 90567 deleted from function.usort by bjori
| From: | bjori@php.net | Date: | Tue, 28 Apr 2009 18:39:58 +0000 |
| Subject: | note 90567 deleted from function.usort by bjori | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-153938@lists.php.net to get a copy of this message | ||
Note Submitter: Anonymous
----
If you already have a sorted array and you want to add a new item, the obvious solution is to append
the new item and then resort:
<?php
$already_sorted[] = $new_item;
usort($already_sorted, 'sort_callback');
?>
However, the performance of this is horrible. usort has no way of knowing that the array you're
passing it is already sorted (except for the one appended item). usort therefore will have to
compare and resort the entire array, even though 99.99% of the work is already done.
An alternative is this uisort function I wrote (uisort = user-insert-sort):
<?php
/**
* insert an item into an already-sorted array
*
* given an $array that is already sorted via $cmp_function,
* insert $insert_item in the correct position. does not
* maintain index association.
*
* this is simply an efficient replacement for the following:
* // this:
* $array[] = $insert_item;
* usort($array, $cmp_function);
*
* // becomes this:
* uisort($array, $cmp_function, $insert_item);
*
* @param &$array the array in which to insert the new item. MUST BE already sorted via
$cmp_function
* @param $cmp_function the comparison function ({@link usort})
* @param $insert_item the item to insert
*
* @return bool on success returns true, otherwise false
*/
function uisort (&$array, $cmp_function, $insert_item) {
if (! is_callable($cmp_function)) {
user_error('uisort(): Invalid comparison function', E_USER_WARNING);
return false;
}
$array = array_values($array);
foreach ($array as $k => $existing_item) {
if (($ret = call_user_func($cmp_function, $existing_item, $insert_item)) >= 0) {
array_splice($array, $k, 0, array($insert_item));
return true;
}
}
array_push($array, $insert_item);
return true;
}
?>