traq

yes, I'm still doing the tutorial. : )

Did you know ...?

PHP Code:

<?php

class alphaHeap extends SplHeap{
    public function compare( $a,$b ){
        return strcmp( $b,$a );
    }
}

$alpha = new alphaHeap;

# IN put:
$alpha->insert( 'cat' );       // C
$alpha->insert( 'dog' );       // D
$alpha->insert( 'boy' );       // B
$alpha->insert( 'elephant' );  // E
$alpha->insert( 'apple' );     // A

foreach( $alpha as $str ){ print "$str<br>"; }
#OUT put:
/*
apple     // A
boy       // B
cat       // C
dog       // D
elephant  // E
*/

a Heap

...is a data structure commonly used for sorting values. They're very efficient (edit: 35%-40% faster, in fact). I don't have an expert understanding, but here's a good place to read more.

In practice, you might think of a Heap as an Ordered List.

With normal PHP arrays, new values are inserted either according to their numeric keys, at a specific position using a complicated sequence of array_slice(), array_push() or array_unshift(), and/or array_splice(), or are (often) simply appended to the end of the array. You have to be responsible for sorting these yourself, sometimes several times during script execution, which can lead to complicated loops or multi-dimensional indexing. With a Heap, new values are "sifted" (compared and ordered) when they're inserted, so the Heap is always in the correct order.


the Standard PHP Library

...is a collection of object classes that most PHP coders have never even heard of. Shame, really. There's some great stuff in there - like Heaps.

The SplHeap class is ready to go, with everything you need, save one lil' detail: how to order the data. You have to define that yourself.*

*The SPL also provides the truly ready-to-use SplMinHeap and SplMaxHeap classes, which order things (you guessed it!) smallest-first and largest-first, respectively. But you can do such cool stuff with your own implementation!

In my first example, I used the SplHeap's ::compare() method to sort words alphabetically. But you can do any number of other things. Just extend the SplHeap class, and write your own version of compare() (compare() must return -1 [less-than], 0 [equal], or 1 [greater-than]). Try these:

PHP Code:

<?php
# biggest word first
class bigWordHeap extends SplHeap{
    public function compare( $a,$b ){
        return strlen( $a ) > strlen( $b )? 1: -1; 
    }
}
# fewest vowels first
class fewestVowelsHeap extends SplHeap{
    public function compare( $a,$b ){ 
        $A = $this->numVowels( $a );
        $B = $this->numVowels( $b );
        if( $A === $B ){ return 0; }
        return $A > $B ? 1: -1;
    }
    private function numVowels( $str ){
        $vowels = array( 'a','e','i','o','u' );
        $letters = str_split( $str );
        $totalVowels = 0;
        foreach( $letters as $ltr ){
            if( in_array( $ltr,$vowels ) ){ $totalVowels++; }
        }
        return $totalVowels;
    }
}
# who knows first
class randomOrderHeap extends SplHeap{
    public function compare( $a,$b ){ 
        return rand( -1,1 );
    }
}

It Gets Better

All well and good, right? "But we already have the various sort() functions for arrays, and I already know how to use those." Check this out.

Say you're getting info about a bunch of people from your database.

Code:

SELECT `name`,`age` FROM `people`

You get your result set (and NOT by using the mysql_*() functions, of course) and put it in an array. For simplicity, we'll say you end up with something like this:

PHP Code:

$example_resultSet = array(
    array( 'name'=>'John'    ,'age'=>22 )
   ,array( 'name'=>'Mary'    ,'age'=>44 )
   ,array( 'name'=>'Albert'  ,'age'=>48 )
   ,array( 'name'=>'Vincent' ,'age'=>22 )
   ,array( 'name'=>'Jane'    ,'age'=>19 )
   ,array( 'name'=>'Michael' ,'age'=>22 )
   ,array( 'name'=>'Julia'   ,'age'=>22 )
   ,array( 'name'=>'Heather' ,'age'=>32 )
   ,array( 'name'=>'George'  ,'age'=>25 )
   ,array( 'name'=>'Erin'    ,'age'=>48 )
); 


Each item in this example "result set" represents a "row" from our query. Say you want to order everyone from oldest to youngest - but we seem to have a lot of people who are the same age. Not being anarchists

(UNSORTED DATA!!?! HERETIC!!!),

we decide that people who are the same age should be grouped and sorted alphabetically.

PHP Code:

<?php

class ageGroupAlphaHeap extends SplHeap{
    public function compare( $a,$b ){
        if( $a['age'] === $b['age'] ){
            return strcmp( $b['name'],$a['name'] );
        }
        return $a['age'] > $b['age']? 1: -1;
    }
}

# instantiate Heap
$sorted_resultSet = new ageGroupAlphaHeap;

# insert each row from our *unsorted* result set
foreach( $example_resultSet as $row ){ $sorted_resultSet->insert( $row ); }

# print out our *sorted* records
foreach( $sorted_resultSet as $person ){ print "{$person['age']} year-old {$person['name']}.<br>"; }

# Output:
/*
48 year-old Albert.
48 year-old Erin.
44 year-old Mary.
32 year-old Heather.
25 year-old George.
22 year-old John.
22 year-old Julia.
22 year-old Michael.
22 year-old Vincent.
19 year-old Jane.
*/

What's more, if we add another "row" later on, everything is still in proper order -

PHP Code:

<?php
$newRow = array( 'name'=>'Bethany','age'=>27 );

$sorted_resultSet->insert( $newRow );

foreach( $sorted_resultSet as $person ){ print "{$person['age']} year-old {$person['name']}.<br>"; }

# Output:
/*
48 year-old Albert.
48 year-old Erin.
44 year-old Mary.
32 year-old Heather.
27 year-old Bethany.
25 year-old George.
22 year-old John.
22 year-old Julia.
22 year-old Michael.
22 year-old Vincent.
19 year-old Jane.
*/

...and we got to be lazy about it.


Enjoy

SPL also has other interesting and useful data structures, iteritors, functions, and classes. Check them out. You might find something awesome for your next project.

Please Ask Questions,

-Adrian