SPL
PHP Manual

Datastructures

Table of Contents

SPL provides a set of standard datastructures. They are grouped here by their underlying implementation which usually defines their general field of application.

Doubly Linked Lists

A Doubly Linked List (DLL) is a list of nodes linked in both directions to each other. Iterator's operations, access to both ends, addition or removal of nodes have a cost of O(1) when the underlying structure is a DLL. It hence provides a decent implementation for stacks and queues.

  • SplDoublyLinkedList
    • SplStack
    • SplQueue

Heaps

Heaps are tree-like structures that follow the heap-property: each node is greater than or equal to its children, when compared using the implemented compare method which is global to the heap.

  • SplHeap
    • SplMaxHeap
    • SplMinHeap
  • SplPriorityQueue

Arrays

Arrays are structures that store the data in a continuous way, accessible via indexes. Don't confuse them with PHP arrays: PHP arrays are in fact implemented as ordered hashtables.

  • SplFixedArray

Map

A map is a datastructure holding key-value pairs. PHP arrays can be seen as maps from integers/strings to values. SPL provides a map from objects to data. This map can also be used as an object set.

  • SplObjectStorage

The SplDoublyLinkedList class

Introduction

The SplDoublyLinkedList class provides the main functionalities of a doubly linked list.

Class synopsis

SplDoublyLinkedList
class SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
/* Methods */
public __construct ( void )
public void add ( mixed $index , mixed $newval )
public mixed bottom ( void )
public int count ( void )
public mixed current ( void )
public int getIteratorMode ( void )
public bool isEmpty ( void )
public mixed key ( void )
public void next ( void )
public bool offsetExists ( mixed $index )
public mixed offsetGet ( mixed $index )
public void offsetSet ( mixed $index , mixed $newval )
public void offsetUnset ( mixed $index )
public mixed pop ( void )
public void prev ( void )
public void push ( mixed $value )
public void rewind ( void )
public string serialize ( void )
public void setIteratorMode ( int $mode )
public mixed shift ( void )
public mixed top ( void )
public void unserialize ( string $serialized )
public void unshift ( mixed $value )
public bool valid ( void )
}

The SplStack class

Introduction

The SplStack class provides the main functionalities of a stack implemented using a doubly linked list.

Class synopsis

SplStack
class SplStack extends SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
/* Methods */
__construct ( void )
void setIteratorMode ( int $mode )
/* Inherited methods */
public void SplDoublyLinkedList::add ( mixed $index , mixed $newval )
public mixed SplDoublyLinkedList::bottom ( void )
public int SplDoublyLinkedList::count ( void )
public mixed SplDoublyLinkedList::current ( void )
public int SplDoublyLinkedList::getIteratorMode ( void )
public bool SplDoublyLinkedList::isEmpty ( void )
public mixed SplDoublyLinkedList::key ( void )
public void SplDoublyLinkedList::next ( void )
public bool SplDoublyLinkedList::offsetExists ( mixed $index )
public mixed SplDoublyLinkedList::offsetGet ( mixed $index )
public void SplDoublyLinkedList::offsetSet ( mixed $index , mixed $newval )
public void SplDoublyLinkedList::offsetUnset ( mixed $index )
public mixed SplDoublyLinkedList::pop ( void )
public void SplDoublyLinkedList::prev ( void )
public void SplDoublyLinkedList::push ( mixed $value )
public void SplDoublyLinkedList::rewind ( void )
public string SplDoublyLinkedList::serialize ( void )
public void SplDoublyLinkedList::setIteratorMode ( int $mode )
public mixed SplDoublyLinkedList::shift ( void )
public mixed SplDoublyLinkedList::top ( void )
public void SplDoublyLinkedList::unserialize ( string $serialized )
public void SplDoublyLinkedList::unshift ( mixed $value )
public bool SplDoublyLinkedList::valid ( void )
}

The SplQueue class

Introduction

The SplQueue class provides the main functionalities of a queue implemented using a doubly linked list.

Class synopsis

SplQueue
class SplQueue extends SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {
/* Methods */
__construct ( void )
mixed dequeue ( void )
void enqueue ( mixed $value )
void setIteratorMode ( int $mode )
/* Inherited methods */
public void SplDoublyLinkedList::add ( mixed $index , mixed $newval )
public mixed SplDoublyLinkedList::bottom ( void )
public int SplDoublyLinkedList::count ( void )
public mixed SplDoublyLinkedList::current ( void )
public int SplDoublyLinkedList::getIteratorMode ( void )
public bool SplDoublyLinkedList::isEmpty ( void )
public mixed SplDoublyLinkedList::key ( void )
public void SplDoublyLinkedList::next ( void )
public bool SplDoublyLinkedList::offsetExists ( mixed $index )
public mixed SplDoublyLinkedList::offsetGet ( mixed $index )
public void SplDoublyLinkedList::offsetSet ( mixed $index , mixed $newval )
public void SplDoublyLinkedList::offsetUnset ( mixed $index )
public mixed SplDoublyLinkedList::pop ( void )
public void SplDoublyLinkedList::prev ( void )
public void SplDoublyLinkedList::push ( mixed $value )
public void SplDoublyLinkedList::rewind ( void )
public string SplDoublyLinkedList::serialize ( void )
public void SplDoublyLinkedList::setIteratorMode ( int $mode )
public mixed SplDoublyLinkedList::shift ( void )
public mixed SplDoublyLinkedList::top ( void )
public void SplDoublyLinkedList::unserialize ( string $serialized )
public void SplDoublyLinkedList::unshift ( mixed $value )
public bool SplDoublyLinkedList::valid ( void )
}

The SplHeap class

Introduction

The SplHeap class provides the main functionalities of a Heap.

Class synopsis

SplHeap
abstract class SplHeap implements Iterator , Countable {
/* Methods */
public __construct ( void )
abstract protected int compare ( mixed $value1 , mixed $value2 )
public int count ( void )
public mixed current ( void )
public mixed extract ( void )
public void insert ( mixed $value )
public bool isEmpty ( void )
public mixed key ( void )
public void next ( void )
public void recoverFromCorruption ( void )
public void rewind ( void )
public mixed top ( void )
public bool valid ( void )
}

The SplMaxHeap class

Introduction

The SplMaxHeap class provides the main functionalities of a heap, keeping the maximum on the top.

Class synopsis

SplMaxHeap
class SplMaxHeap extends SplHeap implements Iterator , Countable {
/* Methods */
protected int compare ( mixed $value1 , mixed $value2 )
/* Inherited methods */
abstract protected int SplHeap::compare ( mixed $value1 , mixed $value2 )
public int SplHeap::count ( void )
public mixed SplHeap::current ( void )
public mixed SplHeap::extract ( void )
public void SplHeap::insert ( mixed $value )
public bool SplHeap::isEmpty ( void )
public mixed SplHeap::key ( void )
public void SplHeap::next ( void )
public void SplHeap::recoverFromCorruption ( void )
public void SplHeap::rewind ( void )
public mixed SplHeap::top ( void )
public bool SplHeap::valid ( void )
}

The SplMinHeap class

Introduction

The SplMinHeap class provides the main functionalities of a heap, keeping the minimum on the top.

Class synopsis

SplMinHeap
class SplMinHeap extends SplHeap implements Iterator , Countable {
/* Methods */
protected int compare ( mixed $value1 , mixed $value2 )
/* Inherited methods */
abstract protected int SplHeap::compare ( mixed $value1 , mixed $value2 )
public int SplHeap::count ( void )
public mixed SplHeap::current ( void )
public mixed SplHeap::extract ( void )
public void SplHeap::insert ( mixed $value )
public bool SplHeap::isEmpty ( void )
public mixed SplHeap::key ( void )
public void SplHeap::next ( void )
public void SplHeap::recoverFromCorruption ( void )
public void SplHeap::rewind ( void )
public mixed SplHeap::top ( void )
public bool SplHeap::valid ( void )
}

The SplPriorityQueue class

Introduction

The SplPriorityQueue class provides the main functionalities of a prioritized queue, implemented using a max heap.

Class synopsis

SplPriorityQueue
class SplPriorityQueue implements Iterator , Countable {
/* Methods */
public __construct ( void )
public int compare ( mixed $priority1 , mixed $priority2 )
public int count ( void )
public mixed current ( void )
public mixed extract ( void )
public void insert ( mixed $value , mixed $priority )
public bool isEmpty ( void )
public mixed key ( void )
public void next ( void )
public void recoverFromCorruption ( void )
public void rewind ( void )
public void setExtractFlags ( int $flags )
public mixed top ( void )
public bool valid ( void )
}

The SplFixedArray class

Introduction

The SplFixedArray class provides the main functionalities of array. The main differences between a SplFixedArray and a normal PHP array is that the SplFixedArray is of fixed length and allows only integers within the range as indexes. The advantage is that it allows a faster array implementation.

Class synopsis

SplFixedArray
class SplFixedArray implements Iterator , ArrayAccess , Countable {
/* Methods */
public __construct ([ int $size = 0 ] )
public int count ( void )
public mixed current ( void )
public static SplFixedArray fromArray ( array $array [, bool $save_indexes = true ] )
public int getSize ( void )
public int key ( void )
public void next ( void )
public bool offsetExists ( int $index )
public mixed offsetGet ( int $index )
public void offsetSet ( int $index , mixed $newval )
public void offsetUnset ( int $index )
public void rewind ( void )
public int setSize ( int $size )
public array toArray ( void )
public bool valid ( void )
public void __wakeup ( void )
}

Examples

Example #1 SplFixedArray usage example

<?php
// Initialize the array with a fixed length
$array = new SplFixedArray(5);

$array[1] = 2;
$array[4] = "foo";

var_dump($array[0]); // NULL
var_dump($array[1]); // int(2)

var_dump($array["4"]); // string(3) "foo"

// Increase the size of the array to 10
$array->setSize(10);

$array[9] = "asdf";

// Shrink the array to a size of 2
$array->setSize(2);

// The following lines throw a RuntimeException: Index invalid or out of range
try {
    var_dump($array["non-numeric"]);
} catch(RuntimeException $re) {
    echo "RuntimeException: ".$re->getMessage()."\n";
}

try {
    var_dump($array[-1]);
} catch(RuntimeException $re) {
    echo "RuntimeException: ".$re->getMessage()."\n";
}

try {
    var_dump($array[5]);
} catch(RuntimeException $re) {
    echo "RuntimeException: ".$re->getMessage()."\n";
}
?>

The above example will output:

NULL
int(2)
string(3) "foo"
RuntimeException: Index invalid or out of range
RuntimeException: Index invalid or out of range
RuntimeException: Index invalid or out of range

The SplObjectStorage class

Introduction

The SplObjectStorage class provides a map from objects to data or, by ignoring data, an object set. This dual purpose can be useful in many cases involving the need to uniquely identify objects.

Class synopsis

SplObjectStorage
class SplObjectStorage implements Countable , Iterator , Serializable , ArrayAccess {
/* Methods */
public void addAll ( SplObjectStorage $storage )
public void attach ( object $object [, mixed $data = NULL ] )
public bool contains ( object $object )
public int count ( void )
public object current ( void )
public void detach ( object $object )
public string getHash ( object $object )
public mixed getInfo ( void )
public int key ( void )
public void next ( void )
public bool offsetExists ( object $object )
public mixed offsetGet ( object $object )
public void offsetSet ( object $object [, mixed $data = NULL ] )
public void offsetUnset ( object $object )
public void removeAll ( SplObjectStorage $storage )
public void removeAllExcept ( SplObjectStorage $storage )
public void rewind ( void )
public string serialize ( void )
public void setInfo ( mixed $data )
public void unserialize ( string $serialized )
public bool valid ( void )
}

Examples

Example #1 SplObjectStorage as a set

<?php
// As an object set
$s = new SplObjectStorage();

$o1 = new StdClass;
$o2 = new StdClass;
$o3 = new StdClass;

$s->attach($o1);
$s->attach($o2);

var_dump($s->contains($o1));
var_dump($s->contains($o2));
var_dump($s->contains($o3));

$s->detach($o2);

var_dump($s->contains($o1));
var_dump($s->contains($o2));
var_dump($s->contains($o3));
?>

The above example will output:

bool(true)
bool(true)
bool(false)
bool(true)
bool(false)
bool(false)

Example #2 SplObjectStorage as a map

<?php
// As a map from objects to data
$s = new SplObjectStorage();

$o1 = new StdClass;
$o2 = new StdClass;
$o3 = new StdClass;

$s[$o1] = "data for object 1";
$s[$o2] = array(1,2,3);

if (isset($s[$o2])) {
    var_dump($s[$o2]);
}
?>

The above example will output:

array(3) {
  [0]=>
  int(1)
  [1]=>
  int(2)
  [2]=>
  int(3)
}