Below are some simple tutorials on using the various types of data structures provided by this library.
Let's say we have the following code relying on » SplDoublyLinkedList:
<?php
$ll = new SplDoublyLinkedList();
$ll->push(2);
$ll->push(3);
$ll->unshift(5);
foreach($ll as $item) echo $item."\n";
?>
Now let's say we would like to test whether a singly linked list would be a better choice. After installing the library we can switch to a singly linked list by making the following changes to the code:
<?php
// The following two lines have been added
require 'vendor/autoload.php'; // The autoloader provided by composer
use SEIDS\LinkedLists\Singly\LinkedList; // The singly linked list class
// The following line has been changed
$ll = new LinkedList();
$ll->push(2);
$ll->push(3);
$ll->unshift(5);
foreach($ll as $item) echo $item."\n";
?>
Both of these programs produce the same output:
5 2 3
Sadly, the end result of doing this is pretty disappointing as the singly linked list offers less functionality in that it does not support the LIFO iteration mode and runs around three times slower than » SplDoublyLinkedList for most operations, whilst consuming around three times as much memory, making it one of the least useful classes in this library.
Let's say we have the following code relying on » SplMaxHeap:
<?php
$mh = new SplMaxHeap();
$mh->insert(4);
$mh->insert(1);
$mh->insert(5);
$mh->insert(2);
$mh->insert(3);
foreach($mh as $item) echo $item."\n";
?>
Now let's say we would like to be able to update items already in the heap, which is not an operation supported by » SplMaxHeap. After installing the library we can switch to an updatable heap by making the following changes to the code:
<?php
// The following two lines have been added
require 'vendor/autoload.php'; // The autoloader provided by composer
use SEIDS\Heaps\Pairing\MaxHeap; // The pairing, max-heap class
// The following line has been changed
$mh = new MaxHeap();
$mh->insert(4);
$mh->insert(1);
$mh->insert(5);
$mh->insert(2);
$mh->insert(3);
foreach($mh as $item) echo $item."\n";
?>
Both of these programs produce the same output:
5 4 3 2 1
At this point we have only succeeded in slowing down our program a little. (Though for a heap of this size the difference would be imperceptible.) We do now have access to an update method which can be utilised as follows:
<?php
require 'vendor/autoload.php'; // The autoloader provided by composer
use SEIDS\Heaps\Pairing\MaxHeap; // The pairing, max-heap class
$mh = new MaxHeap();
$mh->insert(4);
$mh->insert(1);
$mh->insert(5);
$mh->insert(2);
$mh->insert(3);
$mh_clone = clone $mh; // Use a clone as iterating removes items from the heap
foreach($mh_clone as $item) echo $item."\n";
echo "\nBecomes:\n";
$mh->update(2, 7); // Update a '2' in the heap to a '7'
$mh->update(4, 9); // Update a '4' in the heap to a '9'
foreach($mh as $item) echo $item."\n";
?>
Which gives the following output:
5 4 3 2 1 Becomes: 9 7 5 3 1
Similarly, we can move from a priority queue based on » SplPriorityQueue to an updatable priority queue based on an updatable heap.
Let us suppose we have the following code:
<?php
$pq = new SplPriorityQueue();
$pq->insert('three', 3);
$pq->insert('one', 1);
$pq->insert('five', 5);
$pq->insert('four', 4);
$pq->insert('two', 2);
foreach($pq as $item) echo $item."\n";
?>
Which gives the following output:
five four three two one
We can update the priority queue to reorder the items in the queue by making following changes:
<?php
// The following two lines have been added
require 'vendor/autoload.php'; // The autoloader provided by composer
use SEIDS\Heaps\Pairing\PriorityQueue; // The pairing, priority queue class
// The following line has been changed
$pq = new PriorityQueue();
$pq->insert('three', 3);
$pq->insert('one', 1);
$pq->insert('five', 5);
$pq->insert('four', 4);
$pq->insert('two', 2);
$pq_clone = clone $pq; // Use a clone as iterating removes items from the queue
foreach($pq_clone as $item) echo $item."\n";
echo "\nBecomes:\n";
$pq->update('one', 5);
$pq->update('two', 4);
$pq->update('four', 2);
$pq->update('five', 1);
foreach($pq as $item) echo $item."\n";
?>
Which gives us the following output:
five four three two one Becomes: one two three four five
Again, it is important to realise that we have paid a performance penalty for the ability to update, in the forms of both execution speed and memory consumption.
Let us suppose that we have some data that we wish to store in a linear array. We could simply use the standard PHP arrays. Take the following code for example:
<?php
$arr = array();
$arr[] = 'a';
$arr[] = 'b';
$arr[] = 'C';
$arr[] = 'd';
$arr[] = 'e';
echo middle($arr)."\n";
function middle($arr)
{
$N = count($arr);
return $N ? $arr[(int)(($N - 1) / 2)] : null;
}
?>
Which gives the following output:
C
There is a problem with this though. The function middle() assumes that its argument is an array that takes integer keys and that the keys are numbered from zero to 'one less than the size of the array'. Standard PHP arrays do not guarantee this as they are in fact hash maps, and can take keys of any type. For this reason it is convenient to use the ArrayDeque class instead:
<?php
// The following two lines have been added
require 'vendor/autoload.php'; // The autoloader provided by composer
use SEIDS\Arrays\Dynamic\ArrayDeque;
// The following line has been changed
$arr = new ArrayDeque();
$arr[] = 'a';
$arr[] = 'b';
$arr[] = 'C';
$arr[] = 'd';
$arr[] = 'e';
echo middle($arr)."\n";
// The following line has been changed
function middle(ArrayDeque $arr)
{
$N = count($arr);
return $N ? $arr[(int)(($N - 1) / 2)] : null;
}
?>
Not only does this help us to ensure the correctness of our program but also, in the case of large arrays, less memory is consumed. Although, we do pay a penalty in terms of speed. This penalty can be reduced by switching to the DynamicArray class, though this comes at the cost of the ability to grow and shrink from the start of the array and not just the end. i.e. The shift() and unshift() methods.
In fact, we can reclaim this loss of performance provided we always know the size of the array before we build it, and therefore have no need to automatically grow the array. We can do so by switching to the » SplFixedArray class:
<?php
// Two redundant lines deleted
// The following line has been changed
$arr = new SplFixedArray(5);
// The following lines now have explicit indexes
$arr[0] = 'a';
$arr[1] = 'b';
$arr[2] = 'C';
$arr[3] = 'd';
$arr[4] = 'e';
echo middle($arr)."\n";
// The following line has been changed
function middle(SplFixedArray $arr)
{
$N = count($arr);
return $N ? $arr[(int)(($N - 1) / 2)] : null;
}
?>
The ArrayDeque and DynamicArray classes therefore represent 'half-way houses' between standard PHP arrays and the » SplFixedArray class.