Abstract data containers and structures for PHP
composer require smoren/containers
composer install
./vendor/bin/codecept build
./vendor/bin/codecept run unit tests/unit
Classic implementation of linked list structure. Also can be used as stack and queue.
use Smoren\Containers\Structs\LinkedList;
use Smoren\Containers\Structs\LinkedListItem;
$ll = new LinkedList([6, 4, 2]);
var_dump($ll->count()); // output: 3
$ll->pushBack(1);
$ll->pushFront(7);
var_dump($ll->count()); // output: 5
print_r($ll->toArray()); // output: [7, 6, 4, 2, 1]
$ll->sort(function($lhs, $rhs) {
return $lhs > $rhs;
});
print_r($ll->toArray()); // output: [1, 2, 4, 6, 7]
$ll->swap($ll->getFirst(), $ll->getLast());
print_r($ll->toArray()); // output: [7, 2, 4, 6, 1]
$ll->swap($ll->getFirst()->getNext(), $ll->getLast()->getPrev());
print_r($ll->toArray()); // output: [7, 6, 4, 2, 1]
var_dump($ll->popFront()); // output: 7
var_dump($ll->popBack()); // output: 1
print_r($ll->toArray()); // output: [6, 4, 2]
$ll->delete($ll->getFirst()->getNext());
print_r($ll->toArray()); // output: [6, 2]
$llNew = LinkedList::merge(new LinkedList([-2, -1]), $ll, new LinkedList([1, 2]));
var_dump($llNew->count()); // output: 6
print_r($llNew->toArray()); // output: [-2, -1, 6, 2, 1, 2]
$ll->pushBefore($ll->getFirst(), -3);
$ll->pushAfter($ll->getLast(), 3);
print_r($llNew->toArray()); // output: [-3, -2, -1, 6, 2, 1, 2, 3]
/**
* @var LinkedListItem $id
* @var mixed $item
*/
foreach($ll as $id => $item) {
// you can iterate collection
}
$ll->clear();
print_r($ll->toArray()); // output: []Map-like data structure.
use Smoren\Containers\Exceptions\MappedCollectionException;
use Smoren\Containers\Structs\MappedCollection;
$coll = new MappedCollection(['1' => ['id' => 1]]);
var_dump($coll->count()); // output: 1
print_r($coll->toArray()); // output: ['1' => ['id' => 1]]
$coll->add('2', ['id' => 2]);
var_dump($coll->count()); // output: 1
print_r($coll->toArray()); // output: ['1' => ['id' => 1], '2' => ['id' => 2]]
var_dump($coll->exist(1)); // output: true
var_dump($coll->exist(2)); // output: true
var_dump($coll->exist(3)); // output: false
try {
$coll->add('1', ['id' => 1, 'extra' => 'test']);
} catch(MappedCollectionException $e) {
// cannot silently replace existing value
}
print_r($coll->get(1)); // output: ['id' => 1]
$coll->replace('1', ['id' => 1, 'extra' => 'test']);
print_r($coll->get(1)); // output: ['id' => 1, 'extra' => 'test']
try {
$coll->get('3');
} catch(MappedCollectionException $e) {
// element with id = 3 does not exist so you cannot get it
}
/**
* @var string $id
* @var mixed $item
*/
foreach($coll as $id => $item) {
// you can iterate collection
}
$coll->clear();
print_r($coll->toArray()); // output: []LinkedList with mapping by id.
use Smoren\Containers\Structs\MappedLinkedList;
$mll = new MappedLinkedList([]);
var_dump($mll->count()); // output: 0
$mll->pushBack(102, 2);
$mll->pushFront(101, 1);
$mll->pushBack(100, 0);
var_dump($mll->count()); // output: 4
print_r($mll->toArray()); // output: [101 => 1, 102 => 2, 100 => 0]]
$mll->sort(function($lhs, $rhs) {
return $lhs > $rhs;
});
print_r($mll->toArray()); // output: [100 => 0, 101 => 1, 102 => 2]]
$mll->swap(100, 101);
print_r($mll->toArray()); // output: [101 => 1, 100 => 0, 102 => 2]]
var_dump($mll->popFront()); // output: [101, 1]
var_dump($mll->popBack()); // output: [102, 2]
print_r($mll->toArray()); // output: [100 => 0]
$mllNew = MappedLinkedList::merge(
new MappedLinkedList([-999 => -99]),
$mll,
new MappedLinkedList([999 => 99])
);
var_dump($mllNew->count()); // output: 5
print_r($mllNew->toArray()); // output: [-999 => 99, 100 => 0, 999 => 9]
$mllNew->pushBefore(100, -101, -1);
$mllNew->pushAfter(100, 101, 1);
print_r($mllNew->toArray()); // output: [-999 => 99, -101 => -1, 100 => 0, 101 => 1, 999 => 9]
/**
* @var string $id
* @var mixed $value
*/
foreach($mllNew as $id => $value) {
// you can iterate collection
}
$mllNew->clear();
print_r($mllNew->toArray()); // output: []use Smoren\Containers\Structs\SortedLinkedList;
use Smoren\Containers\Exceptions\LinkedListException;
/**
* Class IntegerSortedLinkedList
*/
class IntegerSortedLinkedList extends SortedLinkedList
{
/**
* @inheritDoc
*/
protected function getComparator(): callable
{
return function(int $lhs, int $rhs) {
return $lhs > $rhs;
};
}
}
$sll = new IntegerSortedLinkedList([2, 5, 1]);
var_dump($sll->count()); // output: 3
print_r($sll->toArray()); // output: [1, 2, 5]
$sll->insert(2);
$pos = $sll->insert(3);
var_dump($sll->count()); // output: 5
print_r($sll->toArray()); // output: [1, 2, 2, 3, 5]
var_dump($sll->delete($pos)); // output: 3
var_dump($sll->count()); // output: 4
print_r($sll->toArray()); // output: [1, 2, 2, 5]
var_dump($sll->popBack()); // output: 5
var_dump($sll->popFront()); // output: 1
var_dump($sll->count()); // output: 2
print_r($sll->toArray()); // output: [2, 2]
/**
* @var string $id
* @var mixed $value
*/
foreach($sll as $id => $value) {
// you can iterate collection
}
$sll->clear();
var_dump($sll->count()); // output: 0
print_r($sll->toArray()); // output: []
try {
$sll->popBack();
} catch(LinkedListException $e) {
// cannot pop when collection is empty
}
try {
$sll->popFront();
} catch(LinkedListException $e) {
// cannot pop when collection is empty
}LinkedList with presort and mapping.
use Smoren\Containers\Exceptions\MappedLinkedListException;
use Smoren\Containers\Structs\LinkedListItem;
use Smoren\Containers\Structs\SortedMappedLinkedList;
$smll = new SortedMappedLinkedList([1 => -1, 10 => -10, 5 => -5]);
var_dump($smll->count()); // output: 3
print_r($smll->toArray()); // output: [1 => -1, 5 => -5, 10 => -10]
$smll->insert(3, -3);
var_dump($smll->count()); // output: 4
print_r($smll->toArray()); // output: [1 => -1, 3 => -3, 5 => -5, 10 => -10]
$smll->popBack();
$smll->popFront();
var_dump($smll->count()); // output: 2
print_r($smll->toArray()); // output: [3 => -3, 5 => -5]
/**
* Class ArrayMappedSortedLinkedList
*/
class ArraySortedMappedLinkedList extends SortedMappedLinkedList
{
/**
* @inheritDoc
*/
protected function getComparator(): callable
{
return function(array $lhs, array $rhs) {
return $lhs['a'] > $rhs['a'];
};
}
}
$ll = new ArraySortedMappedLinkedList([
-5 => ['a' => 5],
-1 => ['a' => 1],
-2 => ['a' => 2],
]);
var_dump($smll->count()); // output: 3
print_r($smll->toArray()); // output: [-1 => ['a' => 1], -2 => ['a' => 2], -5 => ['a' => 5]]
/**
* @var string $id
* @var mixed $value
*/
foreach($smll as $id => $value) {
// you can iterate collection
}
try {
$smll->insert(-2, ['a' => 2, 'extra' => 'test']);
} catch(MappedLinkedListException $e) {
// cannot simply replace existing element
}
/** @var LinkedListItem $pos */
$pos = $ll->delete(-1);
print_r($pos->getData()); // output: ['a' => 1]
var_dump($smll->count()); // output: 2
print_r($smll->toArray()); // output: [-2 => ['a' => 2], -5 => ['a' => 5]]
print_r($ll->popBack()); // output: [-5, ['a' => 5]]
print_r($ll->popFront()); // output: [-2, ['a' => 2]]
var_dump($smll->count()); // output: 0
print_r($smll->toArray()); // output: []Graph data structure with tools for traversing.
use Smoren\Containers\Structs\Graph;
$graph = new Graph(
[1 => 11, 2 => 22, 3 => 33, 4 => 44, 5 => 55, 6 => 66],
[[1, 2, 'a'], [2, 3, 'a'], [3, 4, 'a'], [2, 5, 'b'], [5, 3, 'b'], [5, 6, 'c'], [6, 4, 'c']]
);
$paths = $graph->traverseBackward(4);
var_dump($paths); // output: 3
var_dump($paths[0]->toArray(true)); // output: [4, 3, 2, 1]
var_dump($paths[1]->toArray(true)); // output: [4, 3, 5, 2, 1]
var_dump($paths[2]->toArray(true)); // output: [4, 6, 5, 2, 1]
$paths = $graph->traverseForward(1);
var_dump(3, $paths); // output: 3
var_dump($paths[0]->toArray(true)); // output: [1, 2, 3, 4]
var_dump($paths[1]->toArray(true)); // output: [1, 2, 5, 3, 4]
var_dump($paths[2]->toArray(true)); // output: [1, 2, 5, 6, 4]
$paths = $graph->traverseForward(1, ['a', 'b']);
var_dump(2, $paths); // output:
var_dump($paths[0]->toArray(true)); // output: [1, 2, 3, 4]
var_dump($paths[1]->toArray(true)); // output: [1, 2, 5, 3, 4]
$graph->insert(7, 77);
$graph->link(7, 1, 'a');
$paths = $graph->traverseBackward(7);
var_dump($paths); // output: 3
var_dump($paths[0]->toArray(true)); // output: [4, 3, 2, 1, 7]
var_dump($paths[1]->toArray(true)); // output: [4, 3, 5, 2, 1, 7]
var_dump($paths[2]->toArray(true)); // output: [4, 6, 5, 2, 1, 7]
var_dump($paths[2]->reverse()->toArray(true)); // output: [1, 2, 5, 6, 4, 7]