Predefined Constants
SplDoublyLinkedList
SPL
PHP Manual

# Datastructures

Table of Contents

- SplDoublyLinkedList — The SplDoublyLinkedList class
  - SplDoublyLinkedList::bottom — Peeks at the node from the beginning of the doubly linked list
  - SplDoublyLinkedList::__construct — Constructs a new doubly linked list
  - SplDoublyLinkedList::count — Counts the number of elements in the doubly linked list.
  - SplDoublyLinkedList::current — Return current array entry
  - SplDoublyLinkedList::getIteratorMode — Returns the mode of iteration
  - SplDoublyLinkedList::isEmpty — Checks whether the doubly linked list is empty.
  - SplDoublyLinkedList::key — Return current node index
  - SplDoublyLinkedList::next — Move to next entry
  - SplDoublyLinkedList::offsetExists — Returns whether the requested $index exists
  - SplDoublyLinkedList::offsetGet — Returns the value at the specified $index
  - SplDoublyLinkedList::offsetSet — Sets the value at the specified $index to $newval
  - SplDoublyLinkedList::offsetUnset — Unsets the value at the specified $index
  - SplDoublyLinkedList::pop — Pops a node from the end of the doubly linked list
  - SplDoublyLinkedList::prev — Move to previous entry
  - SplDoublyLinkedList::push — Pushes an element at the end of the doubly linked list
  - SplDoublyLinkedList::rewind — Rewind iterator back to the start
  - SplDoublyLinkedList::serialize — Serializes the storage
  - SplDoublyLinkedList::setIteratorMode — Sets the mode of iteration
  - SplDoublyLinkedList::shift — Shifts a node from the beginning of the doubly linked list
  - SplDoublyLinkedList::top — Peeks at the node from the end of the doubly linked list
  - SplDoublyLinkedList::unserialize — Unserializes the storage
  - SplDoublyLinkedList::unshift — Prepends the doubly linked list with an element
  - SplDoublyLinkedList::valid — Check whether the doubly linked list contains more nodes
- SplStack — The SplStack class
  - SplStack::__construct — Constructs a new stack implemented using a doubly linked list
  - SplStack::setIteratorMode — Sets the mode of iteration
- SplQueue — The SplQueue class
  - SplQueue::__construct — Constructs a new queue implemented using a doubly linked list
  - SplQueue::dequeue — Dequeues a node from the queue
  - SplQueue::enqueue — Adds an element to the queue.
  - SplQueue::setIteratorMode — Sets the mode of iteration
- SplHeap — The SplHeap class
  - SplHeap::compare — Compare elements in order to place them correctly in the heap while sifting up.
  - SplHeap::__construct — Constructs a new empty heap
  - SplHeap::count — Counts the number of elements in the heap.
  - SplHeap::current — Return current node pointed by the iterator
  - SplHeap::extract — Extracts a node from top of the heap and sift up.
  - SplHeap::insert — Inserts an element in the heap by sifting it up.
  - SplHeap::isEmpty — Checks whether the heap is empty.
  - SplHeap::key — Return current node index
  - SplHeap::next — Move to the next node
  - SplHeap::recoverFromCorruption — Recover from the corrupted state and allow further actions on the heap.
  - SplHeap::rewind — Rewind iterator back to the start (no-op)
  - SplHeap::top — Peeks at the node from the top of the heap
  - SplHeap::valid — Check whether the heap contains more nodes
- SplMaxHeap — The SplMaxHeap class
  - SplMaxHeap::compare — Compare elements in order to place them correctly in the heap while sifting up.
- SplMinHeap — The SplMinHeap class
  - SplMinHeap::compare — Compare elements in order to place them correctly in the heap while sifting up.
- SplPriorityQueue — The SplPriorityQueue class
  - SplPriorityQueue::compare — Compare priorities in order to place elements correctly in the heap while sifting up.
  - SplPriorityQueue::__construct — Constructs a new empty queue
  - SplPriorityQueue::count — Counts the number of elements in the queue.
  - SplPriorityQueue::current — Return current node pointed by the iterator
  - SplPriorityQueue::extract — Extracts a node from top of the heap and sift up.
  - SplPriorityQueue::insert — Inserts an element in the queue by sifting it up.
  - SplPriorityQueue::isEmpty — Checks whether the queue is empty.
  - SplPriorityQueue::key — Return current node index
  - SplPriorityQueue::next — Move to the next node
  - SplPriorityQueue::recoverFromCorruption — Recover from the corrupted state and allow further actions on the queue.
  - SplPriorityQueue::rewind — Rewind iterator back to the start (no-op)
  - SplPriorityQueue::setExtractFlags — Sets the mode of extraction
  - SplPriorityQueue::top — Peeks at the node from the top of the queue
  - SplPriorityQueue::valid — Check whether the queue contains more nodes
- SplFixedArray — The SplFixedArray class
  - SplFixedArray::__construct — Constructs a new fixed array
  - SplFixedArray::count — Returns the size of the array
  - SplFixedArray::current — Return current array entry
  - SplFixedArray::fromArray — Import a PHP array in a SplFixedArray instance
  - SplFixedArray::getSize — Gets the size of the array
  - SplFixedArray::key — Return current array index
  - SplFixedArray::next — Move to next entry
  - SplFixedArray::offsetExists — Returns whether the requested index exists
  - SplFixedArray::offsetGet — Returns the value at the specified index
  - SplFixedArray::offsetSet — Sets a new value at a specified index
  - SplFixedArray::offsetUnset — Unsets the value at the specified $index
  - SplFixedArray::rewind — Rewind iterator back to the start
  - SplFixedArray::setSize — Change the size of an array
  - SplFixedArray::toArray — Returns a PHP array from the fixed array
  - SplFixedArray::valid — Check whether the array contains more elements
  - SplFixedArray::__wakeup — Reinitialises the array after being unserialised
- SplObjectStorage — The SplObjectStorage class
  - SplObjectStorage::addAll — Adds all objects from another storage
  - SplObjectStorage::attach — Adds an object in the storage
  - SplObjectStorage::contains — Checks if the storage contains a specific object
  - SplObjectStorage::count — Returns the number of objects in the storage
  - SplObjectStorage::current — Returns the current storage entry
  - SplObjectStorage::detach — Removes an object from the storage
  - SplObjectStorage::getHash — Calculate a unique identifier for the contained objects
  - SplObjectStorage::getInfo — Returns the data associated with the current iterator entry
  - SplObjectStorage::key — Returns the index at which the iterator currently is
  - SplObjectStorage::next — Move to the next entry
  - SplObjectStorage::offsetExists — Checks whether an object exists in the storage
  - SplObjectStorage::offsetGet — Returns the data associated with an object
  - SplObjectStorage::offsetSet — Associates data to an object in the storage
  - SplObjectStorage::offsetUnset — Removes an object from the storage
  - SplObjectStorage::removeAll — Removes objects contained in another storage from the current storage
  - SplObjectStorage::removeAllExcept — Removes all objects except for those contained in another storage from the current storage
  - SplObjectStorage::rewind — Rewind the iterator to the first storage element
  - SplObjectStorage::serialize — Serializes the storage
  - SplObjectStorage::setInfo — Sets the data associated with the current iterator entry
  - SplObjectStorage::unserialize — Unserializes a storage from its string representation
  - SplObjectStorage::valid — Returns if the current iterator entry is valid

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 others. 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 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 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 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 an 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)
    }