Datenstrukturen

Inhaltsverzeichnis

SplDoublyLinkedList — The SplDoublyLinkedList class
- SplDoublyLinkedList::add — Add/insert a new value at the specified index
- 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 shift 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 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

Einführung

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

Klassenbeschreibung

SplDoublyLinkedList

class SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {

/* Methoden */

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

Einführung

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

Klassenbeschreibung

SplStack

class SplStack extends SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {

/* Methoden */

__construct ( void )

void setIteratorMode ( int $mode )

/* Geerbte Methoden */

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

Einführung

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

Klassenbeschreibung

SplQueue

class SplQueue extends SplDoublyLinkedList implements Iterator , ArrayAccess , Countable {

/* Methoden */

__construct ( void )

mixed dequeue ( void )

void enqueue ( mixed $value )

void setIteratorMode ( int $mode )

/* Geerbte Methoden */

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

Einführung

The SplHeap class provides the main functionalities of a Heap.

Klassenbeschreibung

SplHeap

abstract class SplHeap implements Iterator , Countable {

/* Methoden */

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

Einführung

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

Klassenbeschreibung

SplMaxHeap

class SplMaxHeap extends SplHeap implements Iterator , Countable {

/* Methoden */

protected int compare ( mixed $value1 , mixed $value2 )

/* Geerbte Methoden */

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

Einführung

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

Klassenbeschreibung

SplMinHeap

class SplMinHeap extends SplHeap implements Iterator , Countable {

/* Methoden */

protected int compare ( mixed $value1 , mixed $value2 )

/* Geerbte Methoden */

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

Einführung

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

Klassenbeschreibung

SplPriorityQueue

class SplPriorityQueue implements Iterator , Countable {

/* Methoden */

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

Einführung

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.

Klassenbeschreibung

SplFixedArray

class SplFixedArray implements Iterator , ArrayAccess , Countable {

/* Methoden */

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 )

}

Beispiele

Beispiel #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";
}
?>

Das oben gezeigte Beispiel erzeugt folgende Ausgabe:

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

Einführung

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.

Klassenbeschreibung

SplObjectStorage

class SplObjectStorage implements Countable , Iterator , Serializable , ArrayAccess {

/* Methoden */

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 )

}

Beispiele

Beispiel #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));
?>

Das oben gezeigte Beispiel erzeugt folgende Ausgabe:

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

Beispiel #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]);
}
?>

Das oben gezeigte Beispiel erzeugt folgende Ausgabe:

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