README

A PHP library implementing classic data structures and algorithms from scratch, PSR-4 autoloaded under Zack\PhpDsAlgo\. No framework, no HTTP layer, no external runtime dependencies — just data structures, algorithms, and a PHPUnit test suite.

Requirements
Installation
Quick Start
Data Structures
Algorithms
Exceptions & Error Handling
Known Quirks & Gotchas
Testing
Project Structure
Roadmap
License

Requirements

PHP >= 8.1
Composer

Installation

composer require zack965/php-ds-algo

For local development against a clone of this repo:

composer install
composer dump-autoload   # regenerate the PSR-4 autoload map after adding/moving classes

Quick Start

<?php

require 'vendor/autoload.php';

use Zack\PhpDsAlgo\DataStructure\LinkedList\Single\SingleLinkedList;
use Zack\PhpDsAlgo\DataStructure\Stack\ArrayStack;
use Zack\PhpDsAlgo\Algorithmes\ArraySortAlgorythmes;

$list = SingleLinkedList::of([3, 1, 2])->append(4)->prepend(0);
echo implode(', ', $list->toArrayValues()); // 0, 3, 1, 2, 4

$stack = ArrayStack::of(1, 2, 3);
echo $stack->pop(); // 3

$sorted = ArraySortAlgorythmes::bubbleSort([5, 3, 1, 4, 2]);
echo implode(', ', $sorted); // 1, 2, 3, 4, 5

Data Structures

All data structures live under src/DataStructure/. SingleLinkedList, DoublyLinkedList, and Graph are persistent/immutable: operations that look like mutations (append, insert, removeAt, addNode, ...) never change the receiver — they return a new instance and leave the original untouched. ArrayStack, Queue, Heap (MinHeap/MaxHeap), PriorityQueue, HashTable, and HashMap are the opposite: genuinely mutable. ArrayStack's and Queue's "mutating" methods change the object in place and return $this for chaining; Heap's, PriorityQueue's, HashTable's, and HashMap's insert()/put()/clear() also mutate in place but return void — no chaining (see Heap, PriorityQueue, HashTable, and HashMap below). Set mixes both styles on one class: add()/remove()/clear() mutate it in place, but union()/intersection()/difference() are pure and always return a new Set, leaving both operands untouched (see Set below). HashSet is fully mutable, same shape as HashTable/HashMap (see HashSet below). Keep this split in mind — it's the single biggest behavioral difference between the groups.

SingleLinkedList

Zack\PhpDsAlgo\DataStructure\LinkedList\Single\SingleLinkedList — implements ILinkedList, IteratorAggregate. Private constructor; build one via a static factory.

Creating a list

use Zack\PhpDsAlgo\DataStructure\LinkedList\Single\SingleLinkedList;
use Zack\PhpDsAlgo\DataStructure\LinkedList\Single\SingleLinkedListNode;

SingleLinkedList::empty();                 // empty list
SingleLinkedList::of([1, 2, 3]);           // from an array of values
SingleLinkedList::fromIterable($generator); // from any iterable (foreach-based)
SingleLinkedList::fromNodes([
    new SingleLinkedListNode(1),
    new SingleLinkedListNode(2),
]);                                        // from pre-built nodes (linked together for you)
SingleLinkedList::ofObjects($nodes);       // alias for fromNodes()

Insertion (each call returns a new list)

$list = SingleLinkedList::of([2, 3]);

$list->prepend(1);              // [1, 2, 3]
$list->append(4);               // [2, 3, 4]
$list->insert(99, 1);           // [2, 99, 3]  — insert 99 at index 1
$list->insertBeforeNode(3, 99); // [2, 99, 3]  — insert 99 immediately before the node holding 3
$list->insertAfterNode(2, 99);  // [2, 99, 3]  — insert 99 immediately after the node holding 2

// $list itself is untouched by all of the above — capture the return value:
$list = $list->append(4);

insertBeforeNode()/insertAfterNode() locate the target by value (via indexOf(), loose == comparison) and throw InvalidArgumentException (ErrorMessages::NO_NODE_WITH_THIS_VALUE) if it isn't found. Inserting before the head or after the tail both work correctly (no need to special-case list boundaries yourself).

Removal

$list->removeByValue(2);  // removes the first node holding 2
$list->removeAt(0);       // removes by index
$list->removeHead();
$list->removeTail();
$list->clear();           // empties the list — throws if already empty
$list->clearAndKeepHead(); // truncates to just the head node

Access

$list->get(1);        // SingleLinkedListNode at index 1
$list->getTail();      // last node
$list->contains(2);    // returns the matching node, or throws
$list->indexOf(2);     // returns the index, or throws
$list->getLength();    // int
$list->getHead();      // ?SingleLinkedListNode

Transformations & functional methods

$list->reverse();                              // new, reversed list
$list->toArray();                              // SingleLinkedListNode[]
$list->toArrayValues();                        // raw values, e.g. [1, 2, 3]
$list->map(fn($v) => $v * 2);                  // new list
$list->filter(fn($v) => $v % 2 === 0);         // new list
$list->reduce(fn($carry, $v) => $carry + $v, 0); // scalar

Iteration

SingleLinkedList implements IteratorAggregate — foreach yields SingleLinkedListNode objects, not raw values:

foreach ($list as $node) {
    echo $node->getValue();
}

All error paths throw InvalidArgumentException with a message from Zack\PhpDsAlgo\Constants\ErrorMessages (LINKEDLIST_IS_EMPTY, INDEX_OUT_OF_BOUND, NO_NODE_WITH_THIS_VALUE).

CircularLinkedList

Zack\PhpDsAlgo\DataStructure\LinkedList\Single\CircularLinkedList — implements ILinkedList, IteratorAggregate. Same persistent/immutable pattern, static factories, and method surface as SingleLinkedList above (reuses SingleLinkedListNode) — the one difference is that the tail's next wraps back around to the head instead of pointing to null:

use Zack\PhpDsAlgo\DataStructure\LinkedList\Single\CircularLinkedList;

$list = CircularLinkedList::of([1, 2, 3]);

$list->getTail()->getNext() === $list->getHead(); // true — the defining invariant

$list = $list->append(4)->prepend(0);   // [0, 1, 2, 3, 4], still circular
$list = $list->removeByValue(0);
$list = $list->reverse();               // old tail becomes new head, still wraps around

Because there's no null terminator to stop at, getIterator() (and every other traversal) is bounded by the tracked node count rather than a while ($current !== null) loop — foreach over a CircularLinkedList still yields exactly its nodes once each, not forever.

All the same factories/insertion/removal/access/transformation/functional methods as SingleLinkedList are supported (empty, of, fromNodes, fromIterable, ofObjects, prepend, append, insert, insertBeforeNode, insertAfterNode, removeByValue, removeAt, removeHead, removeTail, clear, clearAndKeepHead, get, getTail, contains, indexOf, reverse, toArray, toArrayValues, map, filter, reduce), throwing the same ErrorMessages-backed InvalidArgumentExceptions.

DoublyLinkedList

Zack\PhpDsAlgo\DataStructure\LinkedList\Doubly\DoublyLinkedList — implements IDoublyLinkedList, IteratorAggregate (note: not ILinkedList — it's a separate interface). Same persistent/immutable pattern and near-identical API surface to SingleLinkedList, plus backward traversal via DoublyLinkedListNode::getPrevious().

use Zack\PhpDsAlgo\DataStructure\LinkedList\Doubly\DoublyLinkedList;

$list = DoublyLinkedList::of([1, 2, 3]);

$list = $list->append(4)->prepend(0);          // [0, 1, 2, 3, 4]
$list = $list->insertBeforeNode(2, 99);        // insert 99 before the node holding 2
$list = $list->insertAfterNode(2, 99);         // insert 99 after the node holding 2
$list = $list->removeByValue(99);
$list = $list->removeAt(0);
$list = $list->reverse();

foreach ($list as $node) {
    echo $node->getValue(), ' prev=', $node->getPrevious()?->getValue();
}

Supported operations mirror SingleLinkedList exactly: prepend, append, insert, insertBeforeNode, insertAfterNode, removeByValue, removeAt, removeHead, removeTail, clear, clearAndKeepHead, get, getTail, contains, indexOf, reverse, toArray, toArrayValues, map, filter, reduce.

DoublyLinkedListNode differs slightly from SingleLinkedListNode: it has getPrevious()/setPrevious(?DoublyLinkedListNode $previous) in addition to getNext()/setNext(), but has no setValue() — nodes are value-immutable once created (only SingleLinkedListNode lets you mutate a node's value in place).

Gotcha: DoublyLinkedList::fromIterable() only works with a real array (or another Countable + ArrayAccess iterable) — it internally does count($values) and $values[$i] index access, so passing a Generator throws a TypeError/Error. SingleLinkedList::fromIterable() doesn't have this restriction (it uses a plain foreach). If you need to build a DoublyLinkedList from a generator, collect it into an array first: DoublyLinkedList::fromIterable(iterator_to_array($generator)).

ArrayStack

Zack\PhpDsAlgo\DataStructure\Stack\ArrayStack — implements IStack, IteratorAggregate. Mutable (unlike the linked lists above) — push/pop/clear change the stack in place.

use Zack\PhpDsAlgo\DataStructure\Stack\ArrayStack;

ArrayStack::empty();
ArrayStack::of(1, 2, 3);              // variadic
ArrayStack::fromArray([1, 2, 3]);
ArrayStack::fromIterable($iterable);
new ArrayStack([1, 2, 3]);            // constructor is public too

$stack = ArrayStack::of(1, 2, 3);

$stack->push(4);       // mutates $stack in place, returns $this (chainable)
$stack->pop();          // removes & returns the top value — throws if empty
$stack->peek();         // top value without removing it — throws if empty
$stack->bottom();       // bottom value — throws if empty
$stack->isEmpty();      // bool
$stack->contains(2);    // bool, strict (===) comparison
$stack->clear();        // empties the stack in place, returns $this
$stack->toArray();      // bottom-to-top order
$stack->count();        // int

// Chaining, since push()/clear() return $this:
$stack->push(1)->push(2)->push(3);

Iteration is top-to-bottom and yields raw values (not nodes):

foreach (ArrayStack::of(1, 2, 3) as $value) {
    echo $value; // 3, 2, 1
}

Errors (pop()/peek()/bottom() on an empty stack) throw InvalidArgumentException with a plain message ("The stack is already empty") — not one of the ErrorMessages constants used by the linked lists.

Queue

Zack\PhpDsAlgo\DataStructure\Queue\Queue — implements IQueue (extends Countable). Mutable, like ArrayStack. Has no static factories — construct it directly with an array.

use Zack\PhpDsAlgo\DataStructure\Queue\Queue;

$queue = new Queue(['a', 'b']);      // maxCapacity defaults to PHP_INT_MAX — effectively unbounded
$queue = new Queue(['a', 'b'], 10);  // or set a real capacity from the start

$queue->enqueue('c'); // chainable, mutates in place — throws once the queue reaches maxCapacity
$queue->dequeue();      // removes & returns the front item — throws if empty
$queue->front();        // peek the front item
$queue->rear();         // peek the back item
$queue->isEmpty();      // bool
$queue->isFull();       // bool — count() >= maxCapacity
$queue->contains('b');  // bool, strict comparison
$queue->clear();        // empties in place
$queue->toArray();      // front-to-rear order
$queue->toIterable();   // generator, front-to-rear
$queue->getMaxCapacity();
$queue->setMaxCapacity(20); // throws InvalidArgumentException if smaller than the current size

maxCapacity defaults to PHP_INT_MAX (effectively unbounded) — set it via the constructor's second argument or setMaxCapacity() any time you want a real cap. The constructor throws InvalidArgumentException if maxCapacity is smaller than the number of initial items; setMaxCapacity() throws the same way if the new capacity is smaller than the queue's current size.

Queue does not implement IteratorAggregate — you cannot foreach a Queue directly. Use toIterable() or toArray() instead.

See Known Quirks & Gotchas for a Queue-specific edge case (front()/rear() on an empty queue) worth knowing about before relying on it.

Deque

Zack\PhpDsAlgo\DataStructure\Queue\Deque — implements IDeque (extends IQueue). Extends Queue, adding push/pop at the front so items can be added or removed from either end:

use Zack\PhpDsAlgo\DataStructure\Queue\Deque;

$deque = new Deque([2, 3]);

$deque->enqueueFront(1);   // [1, 2, 3] — push to the front
$deque->enqueue(4);        // [1, 2, 3, 4] — inherited from Queue, pushes to the rear
$deque->dequeue();         // 1 — inherited from Queue, pops the front
$deque->dequeueTail();     // 4 — pops the rear

Two asymmetries worth knowing: enqueueFront() does not check isFull() against maxCapacity the way inherited enqueue() does — it can push past the configured capacity. And dequeueTail() does not throw on an empty deque the way inherited dequeue() does — it returns null instead (array_pop()'s own behavior on an empty array).

Graph

Zack\PhpDsAlgo\DataStructure\Graph\Graph — implements IGraph. Persistent/immutable like the linked lists. Supports directed/undirected and weighted/unweighted graphs, backed by an adjacency list of GraphEdge objects.

use Zack\PhpDsAlgo\DataStructure\Graph\Graph;

$graph = new Graph(directed: true); // defaults as shown; `weighted` isn't a constructor
                                     // flag — it's inferred implicitly the first time
                                     // addEdge() is called with a non-null weight

$graph->addNode('A')->addNode('B')->addNode('C');
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C', weight: 5, metadata: ['label' => 'road']);

$graph->hasNode('A');            // bool
$graph->hasEdge('A', 'B');       // bool
$graph->getEdge('A', 'C')->getWeight();   // 5 (or null if unweighted)
$graph->getNeighbors('A');       // GraphEdge[] leaving 'A'
$graph->getOutgoingEdges('A');   // same idea, scanning the whole adjacency list
$graph->getIncomingEdges('C');   // edges arriving at 'C'
$graph->getIncidentEdges('A');   // edges touching 'A' in either direction

$graph->getNodes();              // ['A', 'B', 'C']
$graph->getNodesCount();         // 3
$graph->getEdgeCount();          // 2
$graph->isDirected();            // bool
$graph->isWeighted();            // bool
$graph->isEmpty();               // bool

$graph->removeEdge('A', 'B');
$graph->removeNode('C');         // also drops every edge touching 'C'
$graph->clearEdges();            // keeps nodes, drops all edges
$graph->clear();                 // drops everything

$graph->display(); // pretty-prints the adjacency list to stdout

$graph->getAdjencyMetrix();      // square adjacency matrix (see below)
$graph->printAdjacencyMatrix();  // pretty-prints that matrix to stdout

Adjacency matrix

getAdjencyMetrix() builds a square matrix from the graph's current nodes: row 0 and column 0 hold the node labels (in insertion order), and cell [i][j] is 1 when an edge exists from the i-th node to the j-th node, 0 otherwise. Returns [] for an empty graph.

$graph = new Graph();
$graph->addNode('A')->addNode('B')->addNode('C');
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');

$graph->getAdjencyMetrix();
// [
//     0 => [1 => 'A', 2 => 'B', 3 => 'C'],
//     1 => [0 => 'A', 1 => 0, 2 => 1, 3 => 1],
//     2 => [0 => 'B', 1 => 0, 2 => 0, 3 => 0],
//     3 => [0 => 'C', 1 => 0, 2 => 0, 3 => 0],
// ]

$graph->printAdjacencyMatrix();
//     A  B  C
//    +---------
// A  | 0  1  1
// B  | 0  0  0
// C  | 0  0  0

For an undirected graph the matrix is symmetric only if you've added the reciprocal edge yourself (addEdge() doesn't auto-mirror it — see the caveat below). printAdjacencyMatrix() prints "Graph is empty." instead of a matrix when there are no nodes.

Building from an adjacency list

buildFromAdjencyList() maps each source node to a list of edge rows. Each row is ['destination' => ..., 'weight' => ..., 'metadata' => ...], where destination is required and weight/metadata are optional (defaulting to null and [], same defaults as addEdge()):

$graph = new Graph();
$graph->buildFromAdjencyList([
    'A' => [
        ['destination' => 'B', 'weight' => 4.5, 'metadata' => ['label' => 'road']],
        ['destination' => 'C', 'weight' => 2.0],
    ],
    'B' => [
        ['destination' => 'C', 'weight' => 1.0],
    ],
]);
// nodes A, B, C are created automatically (including 'C', which only ever
// appears as a destination); edges A→B, A→C, B→C are added, each with
// its own weight/metadata; the graph becomes weighted as a result.
// buildFromAdjencyList() clears any existing graph state first.

Rows without a weight key produce an unweighted edge (weight defaults to null) — mixing weighted and unweighted rows across the whole call throws InvalidArgumentException, same as calling addEdge() directly. The graph's isWeighted() flag is set implicitly from the first edge added this way, same as with manual addEdge() calls.

Traversal

Graph doesn't have bfs()/dfs() methods itself — traversal is done via separate algorithm classes (see Graph Traversal below):

use Zack\PhpDsAlgo\Algorithmes\GraphBreadthFirstTraversal;
use Zack\PhpDsAlgo\Algorithmes\GraphDepthFirstTraversal;

GraphBreadthFirstTraversal::traverse($graph, 'A'); // ['A', 'B', 'C']
GraphDepthFirstTraversal::traverse($graph, 'A');   // ['A', 'C', 'B']

addEdge() allows duplicate edges to the same destination (no uniqueness check) — calling addEdge('A', 'B') twice gives you two distinct GraphEdge objects in getNeighbors('A').

GraphEdge (getSourceNode(), getDestinationNode(), getWeight(): int|float|null, getMetadata(): array) and GraphNode (getValue()) are separate small value-object classes under the same namespace. GraphNode is currently a standalone class — Graph stores nodes as plain int|string values internally and never actually constructs a GraphNode. GraphEdge, by contrast, is used throughout Graph's adjacency list.

Graph cannot be foreach'd directly. It has a getIterator(): Traversable method, but the class only implements IGraph — and IGraph does not extend IteratorAggregate. So foreach ($graph as ...) silently iterates zero times (PHP falls back to iterating public properties, and Graph has none) rather than erroring or calling getIterator(). Call getIterator() explicitly instead:
foreach ($graph->getIterator() as $sourceNode => $edges) {
    // $edges is that node's GraphEdge[]
}

Error handling: addNode() on a duplicate throws DuplicateNodeException; getEdge() on a missing edge throws EdgeNotFoundException; traversal helpers throw NotFoundException for an unknown start node; most other node/edge lookups throw plain InvalidArgumentException.

Heap (MinHeap / MaxHeap)

Zack\PhpDsAlgo\DataStructure\Heap\MinHeap and ...\MaxHeap — both extend the shared AbstractBinaryHeap and implement IHeap. An array-backed binary heap: MinHeap keeps the smallest element at the root, MaxHeap the largest. Mutable, like ArrayStack/Queue/Graph — insert(), extract(), and clear() change the heap in place. No static factories (no empty()/of(), unlike the linked lists) — construct directly with new.

use Zack\PhpDsAlgo\DataStructure\Heap\MinHeap;
use Zack\PhpDsAlgo\DataStructure\Heap\MaxHeap;

// __construct(array $data = [], int $capacity = 0, ?callable $comparator = null)
new MinHeap();                      // empty, default capacity (16), default (ascending) ordering
new MinHeap([5, 3, 8, 1, 9]);       // built from an array — heapified immediately, O(n)
new MinHeap([], 64);                // empty, explicit initial capacity
new MinHeap([5, 3, 8], 0, $cmp);    // custom comparator (see below) — 0 means "use the default capacity"

Insert / peek / extract — the core priority-queue operations

$heap = new MinHeap([5, 3, 8, 1, 9]);

$heap->insert(0);     // void — mutates in place, no chaining
$heap->peek();         // 0 — smallest element, without removing it
$heap->extract();      // 0 — removes and returns the smallest element
$heap->extract();      // 1 — next smallest

MaxHeap is the same shape but root-is-largest:

$heap = new MaxHeap([5, 3, 8, 1, 9]);
$heap->peek();    // 9
$heap->extract(); // 9, then 8, then 5, ...

The classic drain-into-sorted-array pattern:

$heap = new MinHeap([5, 3, 8, 1, 9, 2, 7]);
$sorted = [];
while (!$heap->isEmpty()) {
    $sorted[] = $heap->extract();
}
// $sorted === [1, 2, 3, 5, 7, 8, 9]

peek() and extract() both throw RuntimeException ("Heap is empty") when called on an empty heap — note this is RuntimeException, not the InvalidArgumentException most of the rest of this library throws for "invalid state" errors (see the note in Exceptions & Error Handling).

Size, capacity, and clearing

$heap->isEmpty();          // bool
$heap->size();              // current element count
$heap->getCapacity();       // current backing-array capacity (starts at 16, doubles on growth)
$heap->ensureCapacity(100); // pre-grow to at least 100 if not already there; no-op if already >= 100
$heap->clear();             // empties the heap in place, keeps current capacity

Capacity grows automatically on insert() (and on the array constructor, if $data is bigger than the requested/default capacity) — you never have to call ensureCapacity() yourself unless you want to avoid intermediate reallocations up front.

Inspecting the heap

$heap->toArray();  // the raw, level-order backing array — NOT sorted order
$heap->isValid();  // bool — true iff every parent satisfies the heap property against its children

toArray() returns the heap's internal array representation (root at index 0, children of index $i at 2*$i+1/2*$i+2) — it is not the elements in ascending/descending order. To get sorted order, drain the heap with repeated extract() calls as shown above (this also empties it — extract into a fresh copy if you need to keep the original).

Custom comparators — the main way to reshape ordering

The third constructor argument is ?callable $comparator, taking (mixed $a, mixed $b): int. It must return exactly -1, 0, or 1 (not an arbitrary signed integer) — see the gotcha below. The natural way to do this is PHP's spaceship operator <=>, which always returns one of those three values.

// Reverse a MinHeap's ordering (largest first) with a descending comparator:
$descending = fn($a, $b) => $b <=> $a;
$heap = new MinHeap([1, 3, 2, 5, 4], 0, $descending);
$heap->peek(); // 5

// Sort custom objects by a property — the priority-queue use case:
class Task {
    public function __construct(public string $name, public int $priority) {}
}
$byPriority = fn(Task $a, Task $b) => $a->priority <=> $b->priority;
$heap = new MinHeap([], 0, $byPriority);
$heap->insert(new Task('low', 5));
$heap->insert(new Task('urgent', 1));
$heap->extract()->name; // 'urgent' — lowest priority number extracted first

// Sort strings by length instead of lexicographically:
$byLength = fn(string $a, string $b) => strlen($a) <=> strlen($b);
$heap = new MinHeap(['banana', 'fig', 'kiwi'], 0, $byLength);
$heap->peek(); // 'fig'

A MinHeap with a descending comparator and a MaxHeap with an ascending comparator behave identically — the class you pick only sets the default comparator (used when you pass null); a custom comparator fully overrides it.

Gotcha — custom comparators must return exactly -1/0/1, not an arbitrary signed integer. The classic PHP usort()-style comparator idiom fn($a, $b) => $a - $b (or strcmp()-style "any negative/positive number") does not work reliably here — heapifyDown()'s internal child-selection logic checks the comparator's return value against the literal value -1, not "is it negative." A comparator that returns e.g. -5 will silently misorder the heap on extract()/the array constructor (though insert()-only usage is unaffected — that path only checks the sign). Always write comparators with <=>, which is spec'd to return exactly -1/0/1, and this is a non-issue.

Advanced / internal-use methods

heapifyUp(int $index), heapifyDown(int $index), and buildHeap() are part of the public IHeap contract (so they're callable), but they operate on internal array positions and are meant to be used by the class itself (insert(), extract(), and the array constructor already call them at the right times) — normal client code has no reason to call them directly.

PriorityQueue

Zack\PhpDsAlgo\DataStructure\Heap\PriorityQueue — implements IPriorityQueue. A thin, value-priority wrapper around an internal MaxHeap or MinHeap of PriorityQueueNode objects (each pairing a value with a numeric priority), rather than a heap you feed raw comparable values yourself. Mutable, same as MinHeap/MaxHeap — insert()/insertMany()/clear() change the queue in place and return void. No static factories — construct with new PriorityQueue(PriorityQueueTypeEnum $type, int $capacity = 10); $type (required, no default) picks which internal heap backs the queue and $capacity is forwarded straight to it.

use Zack\PhpDsAlgo\DataStructure\Heap\PriorityQueue;
use Zack\PhpDsAlgo\DataStructure\Heap\PriorityQueueNode;
use Zack\PhpDsAlgo\enums\PriorityQueueTypeEnum;

$queue = new PriorityQueue(PriorityQueueTypeEnum::Max); // capacity defaults to 10

$queue->insert('low', 1);
$queue->insert('urgent', 9);
$queue->insert('medium', 5);

$queue->peek()->getValue();     // 'urgent' — peek() returns the PriorityQueueNode itself, not the bare value
$queue->peek()->getPriority();  // 9

$queue->extract()->getValue();  // 'urgent' — removes and returns the highest-priority node
$queue->extract()->getValue();  // 'medium'
$queue->extract()->getValue();  // 'low'

PriorityQueueTypeEnum (Zack\PhpDsAlgo\enums\PriorityQueueTypeEnum) is a string-backed enum with two cases, Max and Min. Pass PriorityQueueTypeEnum::Max to extract highest-priority-first (backed internally by a MaxHeap), or PriorityQueueTypeEnum::Min to extract lowest-priority-first (backed internally by a MinHeap) — same API either way, just swap the constructor argument:

$queue = new PriorityQueue(PriorityQueueTypeEnum::Min);

$queue->insert('low', 1);
$queue->insert('urgent', 9);
$queue->insert('medium', 5);

$queue->extract()->getValue();  // 'low' — lowest priority extracts first
$queue->extract()->getValue();  // 'medium'
$queue->extract()->getValue();  // 'urgent'

insert(mixed $value, int|float $priority) wraps $value/$priority into a PriorityQueueNode internally and feeds it to whichever heap $type selected. insertMany(array $nodes) takes an array of pre-built PriorityQueueNode instances and inserts each one in turn:

$queue->insertMany([
    new PriorityQueueNode('a', 1),
    new PriorityQueueNode('b', 9),
    new PriorityQueueNode('c', 5),
]);

isEmpty(), size(), and clear() all delegate straight to the underlying heap and behave identically regardless of $type. Like MaxHeap/MinHeap, peek() and extract() throw RuntimeException ("Heap is empty") — not InvalidArgumentException — when called on an empty queue.

PriorityQueueNode (Zack\PhpDsAlgo\DataStructure\Heap\PriorityQueueNode) is a small, standalone value object — getValue(): mixed and getPriority(): int|float, both set only via the constructor (no setters). Nothing stops you from constructing one directly and passing it to insertMany(), but insert() is the more direct path for adding a single value/priority pair.

Priority ties aren't ordered by insertion. When two nodes share the same priority, PriorityQueue's comparator returns 0 for them, so which one extracts first depends on the underlying heap's internal layout, not FIFO/LIFO order among equal priorities — don't rely on tie-breaking behavior.

HashTable

Zack\PhpDsAlgo\DataStructure\HashTabe\HashTable — implements IHashTable, IteratorAggregate, Countable. A bucketed hash table using separate chaining for collisions — really a hash set (unique-ish bag of values; duplicates are allowed and stored as separate entries, not deduplicated), since values act as their own keys. Mutable, like MinHeap/MaxHeap/PriorityQueue — insert()/delete()/update()/clear()/reset()/resize() all change the table in place and return void (or bool for the ones that report whether they found a match) rather than a new instance. No static factories — construct directly with new HashTable(int $capacity = 10); $capacity <= 0 throws InvalidArgumentException.

use Zack\PhpDsAlgo\DataStructure\HashTabe\HashTable;

$table = new HashTable(); // capacity defaults to 10

$table->insert('apple');
$table->insert(42);
$table->insert(['id' => 1]);

$table->hasValue('apple'); // true
$table->hasValue('missing'); // false

$table->delete('apple');   // true — removed
$table->update(42, 43);    // true — 42 replaced by 43

$table->getSize();         // current element count
$table->getCapacity();     // current bucket count
$table->getLoadFactor();   // getSize() / getCapacity()
$table->isEmpty();         // bool

count($table);             // same as getSize(), via Countable
foreach ($table as $value) { /* ... */ } // via IteratorAggregate

HashTable is documented generically (@template T in its PHPDoc, @implements IHashTable<T>) since PHP has no runtime generics — every method is typed mixed in code but annotated T for static analysis, so a single instance can hold any mix of hashable types, not just strings.

What counts as "hashable"

A value is placed into a bucket by reducing it to a string key and hashing that with PHP's xxh3 algorithm, then reducing modulo the current capacity:

Strings are used directly (no conversion overhead).
Other scalars, null, arrays, and objects are reduced via serialize().
Closures and resources have no stable value representation and are rejected — insert(), hasValue(), delete(), getValuePosition(), and update() all throw InvalidArgumentException if passed one.

-0.0 and 0.0 are canonicalized to the same key before hashing, so they always land in the same bucket — matching the fact that -0.0 === 0.0 is true in PHP (the comparison this class uses everywhere else). Without that normalization the two would hash differently (serialize() encodes them as "d:-0;" vs "d:0;") despite comparing equal, which would otherwise make hasValue(0.0) fail to find a value inserted as -0.0.

The hash key only decides which bucket a value lands in — actual membership checks (hasValue(), delete(), getValuePosition(), update()) always compare candidates with strict ===. That matters for objects in particular: two distinct object instances with identical properties serialize to the same key (same bucket, exercising the chaining path) but are not ===-equal, so hasValue() correctly reports one as present and the other as absent even though they'd land in the same bucket:

$a = new stdClass(); $a->name = 'same';
$b = new stdClass(); $b->name = 'same'; // same bucket as $a, but a different instance

$table->insert($a);
$table->hasValue($a); // true
$table->hasValue($b); // false — not the same instance

=== also means 1, '1', and true are tracked as distinct entries even though they may share a bucket.

Inspecting values

$table->getAllValues();   // list<T> — every stored value, flattened across all buckets
$table->getValuePosition('apple'); // ['bucketIndex' => ..., 'itemIndex' => ...] or false
$table->getValue('apple'); // returns 'apple' if present, null otherwise (values are their own keys)

No getBucket()/getBuckets(). Earlier versions exposed the raw bucket array (or, for HashSet below, the live internal Set per bucket) via these two methods. Both were removed — they leaked internal storage structure that callers had no business depending on, and for HashSet specifically, exposing the actual internal Set per bucket meant a caller mutating one directly (e.g. $bucket->add(...)) could corrupt the table without going through tableHash() at all. getValuePosition() still tells you which bucket a value landed in, without exposing the bucket itself.

Resizing

insert() automatically doubles the capacity (via resize()) once the load factor exceeds 0.7, rebuilding the table and re-bucketing every existing value against the new capacity. resize() is also public, so you can grow the table pre-emptively; clear() empties all buckets but keeps the current capacity, while reset() empties the table and resets capacity back to the default of 10.

Note: the folder/namespace is HashTabe, not HashTable — src/DataStructure/HashTabe/HashTable.php. This is a genuine typo (not one of the intentional Algorythmes/Alogorthme misspellings that features.md scopes to the algorithms area), but PSR-4 resolution depends on it, so match it exactly when importing: use Zack\PhpDsAlgo\DataStructure\HashTabe\HashTable;.

HashMap

Zack\PhpDsAlgo\DataStructure\HashTabe\HashMap — implements IHashMap, IteratorAggregate, Countable. A proper key-value map living alongside HashTable in the same HashTabe folder/namespace, sharing its hashing approach (separate chaining, xxh3-hashed buckets, the same "hashable" rules and -0.0/0.0 normalization described under HashTable above) but keyed independently of the stored value. Each bucket entry is a small HashMapNode value object (getKey(), getValue(), setValue()). Mutable, same shape as HashTable — construct directly with new HashMap(int $capacity = 10); $capacity <= 0 throws InvalidArgumentException.

use Zack\PhpDsAlgo\DataStructure\HashTabe\HashMap;

$map = new HashMap(); // capacity defaults to 10

$map->put('name', 'zack');
$map->put(42, 'answer');

$map->hasKey('name');   // true
$map->get('name');      // 'zack'
$map->get('missing');   // null — not an exception, see below

$map->put('name', 'updated'); // put() upserts: replaces the value in place, doesn't throw
$map->update('name', 'again'); // update() also replaces, but returns false instead of inserting if the key is missing

$map->delete('name');   // true — removed
$map->getSize();        // current entry count
$map->isEmpty();        // bool

count($map);                          // same as getSize(), via Countable
foreach ($map as $key => $value) { /* ... */ } // via IteratorAggregate — keys aren't limited to int|string

put() is an upsert: if the key already exists, its value is replaced in place (no new entry, no load-factor check); only a genuinely new key can push the load factor past 0.7 and trigger a resize(). update() is the "must already exist" counterpart — it never creates a new entry, returning false instead when the key is missing. get() returns null for a missing key rather than throwing (mirroring HashTable::getValue()), so a present-but-null value and a missing key both currently read as null — use hasKey() first if that distinction matters to you.

Keys vs. values

Keys follow the same hashability rules as HashTable's values (see What counts as "hashable" above) — strings hash directly, other scalars/null/arrays/objects via serialize(), closures/resources rejected. Values have no such restriction — any value, including a closure or a resource, can be stored, since only keys are ever hashed:

$map = new HashMap();
$map->put('handler', fn() => 'ok'); // fine — the closure is the value, not the key
$map->put(['id' => 1], 'array key works too');

Key lookups (hasKey(), get(), getKeyPosition(), delete(), update()) are bucket-scoped and O(1)-ish, same as HashTable. Value lookups (hasValue(), getValuePosition()) scan every bucket — O(n) — since a value isn't part of what's hashed:

$map->hasKey('name');           // bucket lookup
$map->hasValue('zack');         // full scan
$map->getKeyPosition('name');   // ['bucketIndex' => ..., 'itemIndex' => ...] or false
$map->getValuePosition('zack'); // same shape, found by scanning every bucket

Inspecting entries

$map->getAllEntries(); // list<HashMapNode<K, V>> — every entry, as HashMapNode objects
$map->getAllKeys();    // list<K>
$map->getAllValues();  // list<V>
$map->getKeyPosition('name');   // ['bucketIndex' => ..., 'itemIndex' => ...] or false

HashMap::delete() uses array_splice() (not unset(), unlike HashTable::delete()), so a bucket's keys internally always stay a contiguous 0-based list — not observable directly since (see the note under HashTable above) getBucket()/getBuckets() were removed from all three hash structures for exposing internal storage; getKeyPosition()'s itemIndex reflects the reindexing instead.

There's deliberately no toArray() returning a plain [key => value] PHP array: since keys can be arrays or objects, and native PHP array keys are restricted to int|string, a naive toArray() would have to silently coerce or crash on exactly the keys this class is generic enough to accept. getAllEntries()/getAllKeys()/getAllValues() (and foreach, which yields real K-typed keys via a generator — not restricted the way a native array's keys are) are the intended way to read a HashMap out.

Resizing

Same as HashTable: put() doubles the capacity (via resize()) once a genuine insert pushes the load factor past 0.7, re-bucketing every entry against the new capacity; resize() is also public for pre-emptive growth. clear() empties all buckets but keeps capacity; reset() empties the map and restores the default capacity of 10.

Set

Zack\PhpDsAlgo\DataStructure\Set\Set — implements ISet, IteratorAggregate, Countable. A plain, array-backed collection of unique values plus indexed access (get, indexOf, update) and set-algebra operations (union, intersection, difference, isSubsetOf, isSupersetOf, equals). Unlike HashTable, it does no hashing — membership is a linear scan (O(n)) using strict (===) comparison, so it favors simplicity over lookup speed (see Set vs. HashTable in the article for when to reach for which). Mixes mutable and pure styles on one class: add()/remove()/clear()/update() mutate in place, but union()/intersection()/difference() never touch either operand and always return a new Set. No static factories — construct directly with new Set(array $data = []).

use Zack\PhpDsAlgo\DataStructure\Set\Set;

$set = new Set([1, 2, 2, 3]); // duplicates collapse: [1, 2, 3]

$set->add(4);          // true — added
$set->add(4);           // false — already present, set unchanged
$set->contains(2);      // true
$set->remove(2);        // true — removed
$set->remove(99);       // false — wasn't present
$set->isEmpty();        // bool
$set->getAll();         // list<T> snapshot, insertion order
$set->count();           // int
$set->clear();           // empties in place

count($set);              // same as count(), via Countable
foreach ($set as $value) { /* ... */ } // via IteratorAggregate, insertion order

null is not a valid element — add(null), contains(null), and remove(null) all throw InvalidArgumentException (this comes from GeneralArrayAlgorithms::contains(), which every membership check routes through — see General Array Helpers below). Comparison is always strict, so values a looser check would merge stay distinct:

$set = new Set([1, '1', true]);
$set->count(); // 3 — int 1, string "1", and bool true are three different elements

One deliberate carve-out to "strict": two NAN floats compare equal to each other for Set's purposes, even though NAN === NAN is false in PHP — see GeneralArrayAlgorithms::equals() below, which add()/contains()/remove()/indexOf() all share.

$set = new Set();
$set->add(NAN);
$set->add(NAN);     // false — already present, not a second entry
$set->remove(NAN);  // true — actually removed (not just reported as found)

Indexed access

$set = new Set(['a', 'b', 'c']);

$set->get(1);          // 'b' — value at iteration index 1, throws OutOfBoundsException if out of range
$set->indexOf('b');    // 1
$set->indexOf('z');    // false — not present
$set->update('b', 'z'); // true — 'b' replaced by 'z' at the same index

get()/indexOf() refer to the set's current iteration order (insertion order for this implementation), which ISet doesn't otherwise guarantee is stable — don't rely on a specific index surviving an add()/remove(). update() only replaces $oldValue if it exists and $newValue isn't already present elsewhere in the set (both checked before anything is mutated); it returns false and leaves the set untouched if either condition fails.

Set algebra

$a = new Set([1, 2, 3]);
$b = new Set([2, 3, 4]);

$a->union($b)->getAll();        // [1, 2, 3, 4] — new Set, $a and $b unchanged
$a->intersection($b)->getAll(); // [2, 3]
$a->difference($b)->getAll();   // [1]           — in $a, not in $b (directional)
$b->difference($a)->getAll();   // [4]           — in $b, not in $a

$a->isSubsetOf($b);    // false
$a->isSupersetOf($b);  // false
$a->equals(new Set([3, 2, 1])); // true — order doesn't matter

The empty set is a subset of every set, and every set is a subset of itself. equals() compares size first (O(1)) before falling through to an element-by-element check.

See articles/15-set.md for the full internals walkthrough, including why remove() has to reassign $this->data rather than just call GeneralArrayAlgorithms::remove() (that helper is pure — it returns a new array rather than mutating its argument).

HashSet

Zack\PhpDsAlgo\DataStructure\HashTabe\HashSet — implements IHashSet, IteratorAggregate, Countable. Lives in the HashTabe folder/namespace alongside HashTable/HashMap (sharing their hashing approach — separate chaining, xxh3-hashed buckets, auto-resize past a 0.7 load factor), but each bucket is a real Set instance rather than a raw array — so HashSet, unlike HashTable (a bag: duplicates allowed), is a genuine set: inserting an equal value twice is a no-op. Mutable, same shape as HashTable/HashMap — insert()/delete()/update()/clear()/reset()/resize() change the table in place. No static factories — construct directly with new HashSet(int $capacity = 10); $capacity <= 0 throws InvalidArgumentException.

use Zack\PhpDsAlgo\DataStructure\HashTabe\HashSet;

$set = new HashSet(); // capacity defaults to 10

$set->insert('apple');
$set->insert('apple'); // no-op — already present, unlike HashTable::insert()

$set->hasValue('apple'); // true
$set->hasValue('missing'); // false

$set->delete('apple');      // true — removed
$set->update('a', 'b');     // renames a value in place — see below

$set->getSize();         // current element count
$set->getCapacity();     // current bucket count
$set->getLoadFactor();   // getSize() / getCapacity()
$set->isEmpty();         // bool

count($set);              // same as getSize(), via Countable
foreach ($set as $value) { /* ... */ } // via IteratorAggregate

HashSet is documented generically with a narrower type bound than HashTable/HashMap: @template T of scalar|object — null and arrays are outside that bound and explicitly rejected (HashTable accepts both).

What counts as "hashable"

Mostly the same rules as HashTable, with two differences:

null and arrays are rejected — HashTable accepts both; HashSet's narrower scalar|object type bound doesn't.
Objects (including closures) are hashed by spl_object_id(), not serialize() — bucketing is by object identity, not by property values. Two distinct instances with identical properties will very likely land in different buckets here (HashTable/HashMap would put them in the same bucket via serialize(), then still tell them apart with ===). Either way, membership is always decided by ===, so this only affects which bucket a lookup starts scanning from, never correctness.

Otherwise unchanged: strings hash directly; other scalars go through serialize(); resources and closures have no stable representation and are rejected with InvalidArgumentException; -0.0/0.0 are canonicalized before hashing so they land in the same bucket, matching -0.0 === 0.0. One more carve-out shared with Set: two NAN floats compare equal for hasValue()/delete()/update()'s purposes (via the same GeneralArrayAlgorithms::equals() used by Set), even though NAN === NAN is false — without it, a NAN could be reported present by hasValue() yet never actually removable by delete().

$set = new HashSet();
$set->insert(NAN);
$set->insert(NAN);   // no-op, not a second entry
$set->delete(NAN);   // true — actually removed

update()

$set = new HashSet();
$set->insert('old');

$set->update('old', 'new'); // true — 'old' renamed to 'new', possibly moving to a different bucket
$set->update('missing', 'x'); // false — nothing to rename
$set->update('a', 'b'); // false if 'b' already exists elsewhere — never overwrites/merges

Unlike getValuePosition()/hasValue(), which throw InvalidArgumentException for an unhashable $value, update() never throws — an invalid $oldValue or $newValue (e.g. null, an array, a closure) makes it return false instead, same as "nothing to do." update(x, x) (old and new value equal, including the NAN-equals-NAN carve-out) is a no-op success (true), without touching the set.

Inspecting values

$set->getAllValues();          // list<T> — every stored value, flattened across all buckets
$set->getValuePosition('apple'); // ['bucketIndex' => ..., 'itemIndex' => ...] or false

Like HashTable/HashMap, HashSet has no getBucket()/getBuckets() — exposing a bucket here would mean exposing the actual internal Set instance backing it, letting a caller mutate the table directly (bypassing tableHash() entirely) via a plain Set method call. See the note under HashTable above.

Resizing

Same as HashTable/HashMap: insert() doubles the capacity (via resize()) once a genuine insert pushes the load factor past 0.7, re-bucketing every value against the new capacity; resize() is also public for pre-emptive growth. clear() empties all buckets but keeps capacity; reset() empties the set and restores the default capacity of 10.

BinaryTree & BinarySearchTree

Zack\PhpDsAlgo\DataStructure\Tree\BinaryTree and ...\BinarySearchTree — implement IBinaryTree/IBinarySearchTree (both extend the shared ITree), over a common BinaryTreeNode and a shared base class AbstractTree. Mutable, like ArrayStack/Queue/Graph/the heaps — not the clone-then-splice persistent pattern the linked lists use; insert()/remove()/balance() change nodes in place and return $this for chaining.

Both share, via AbstractTree:

$tree->getRoot();     // ?BinaryTreeNode
$tree->isEmpty();     // bool
$tree->clear();       // empties the tree
$tree->getHeight();   // int — -1 empty, 0 a single node
$tree->contains(5);   // bool, breadth-first scan
$tree->levelOrder();  // list<T>, breadth-first — same as toArray()
$tree->count();       // int, also via Countable

foreach ($tree as $value) { /* in-order: left, node, right */ }

`BinaryTree` — plain binary tree, level-order insertion

use Zack\PhpDsAlgo\DataStructure\Tree\BinaryTree;

$tree = new BinaryTree();
$tree->insert(1)->insert(2)->insert(3)->insert(4); // fills breadth-first, left to right

$tree->preOrder();    // [1, 2, 4, 3]  — node, left, right
$tree->inOrder();     // [4, 2, 1, 3]  — left, node, right
$tree->postOrder();   // [4, 2, 3, 1]  — left, right, node

$tree->search(4);     // ?BinaryTreeNode — breadth-first scan, no ordering to exploit
$tree->remove(2);     // removes the first match, promoting the deepest/rightmost node's value into its place

$tree->isFull();      // bool — every node has 0 or 2 children (never exactly 1)
$tree->isComplete();  // bool — every level full except possibly the last, filled left to right
$tree->isPerfect();   // bool — every internal node has 2 children, every leaf at the same depth
$tree->isBalanced();  // bool — every node's two subtrees' heights differ by at most 1
$tree->getDiameter(); // int — edges on the longest path between any two nodes

BinaryTree allows duplicate values (there's no ordering property to enforce uniqueness against) — insert() never rejects one.

`BinarySearchTree` — ordered insertion, `O(log n)` average lookups

use Zack\PhpDsAlgo\DataStructure\Tree\BinarySearchTree;

$bst = new BinarySearchTree([50, 30, 70, 20, 40, 60, 80]); // constructor accepts an initial array
$bst = BinarySearchTree::fromArray([50, 30, 70]);           // equivalent static factory

$bst->insert(35);   // maintains BST order; duplicate values are silently ignored
$bst->search(40);   // ?BinaryTreeNode, O(log n) average via BST-order descent (not breadth-first)
$bst->remove(30);   // maintains BST order — leaf / one-child / two-children (successor-promotion) cases

$bst->min();               // ?BinaryTreeNode
$bst->max();               // ?BinaryTreeNode
$bst->predecessor(40);     // ?BinaryTreeNode — largest value < 40
$bst->successor(40);       // ?BinaryTreeNode — smallest value > 40
$bst->floor(45);            // T|null — largest value <= 45 (need not exist in the tree)
$bst->ceiling(45);           // T|null — smallest value >= 45
$bst->findClosest(999);       // T — nearest value to the target; ties favor the shallower node

$bst->inOrder();             // list<T>, ascending — BST in-order traversal is sorted by construction
$bst->rangeSearch(25, 65);    // list<T>, ascending, values in [25, 65]
$bst->countInRange(25, 65);   // int, same range without collecting values
$bst->kthSmallest(2);          // T|null — null if $k is out of bounds
$bst->kthLargest(2);            // T|null
$bst->lowestCommonAncestor(20, 80); // ?BinaryTreeNode — null if either value is absent

$bst->isValid();   // bool — true iff every node's left/right subtrees satisfy left < node < right
$bst->balance();   // rebalances in place via the Day-Stout-Warren algorithm, O(n)

balance() is a genuine DSW (Day–Stout–Warren) rebalance — not an AVL rotation — and runs in two passes: createVine() first rotates the whole tree into a right-only "vine" with no left children at all (without changing the in-order value sequence), then compressVine() repeatedly left-rotates that vine into a balanced shape. A tree built by inserting values in strictly increasing order degrades into an n-node chain (height n - 1); balance() brings it down to the height of a complete binary tree with the same node count.

Algorithms

Algorithm classes live under src/Algorithmes/ and are static-method utility classes operating on plain PHP arrays — fully decoupled from the data structures above.

Sorting — `ArraySortAlgorythmes`

Zack\PhpDsAlgo\Algorithmes\ArraySortAlgorythmes

use Zack\PhpDsAlgo\Algorithmes\ArraySortAlgorythmes;

ArraySortAlgorythmes::bubbleSort([5, 3, 1, 4, 2]);     // [1, 2, 3, 4, 5]
ArraySortAlgorythmes::selectionSort([5, 3, 1, 4, 2]);  // [1, 2, 3, 4, 5]
ArraySortAlgorythmes::insertionSort([5, 3, 1, 4, 2]);  // [1, 2, 3, 4, 5]
ArraySortAlgorythmes::MergeSort([5, 3, 1, 4, 2]);      // [1, 2, 3, 4, 5]
ArraySortAlgorythmes::QuickSOrt([5, 3, 1, 4, 2]);      // [1, 2, 3, 4, 5]
ArraySortAlgorythmes::heapSort([5, 3, 1, 4, 2]);       // [1, 2, 3, 4, 5]  — backed by MinHeap
ArraySortAlgorythmes::bucketSort([5, 3, 1, 4, 2]);     // [1, 2, 3, 4, 5]

All seven take an array by value and return a new sorted array — the input is never mutated. This is the canonical sorting implementation (the legacy top-level Zack\PhpDsAlgo\SortingAlgorithms duplicate has been removed — nothing to avoid building against anymore).

MergeSort() and QuickSOrt() keep their PascalCase method names (unlike the lowerCamelCase bubbleSort/selectionSort/insertionSort/heapSort/bucketSort) — an inconsistency in the existing API, not a typo.

bucketSort() validates every element up front — anything that isn't an int or float (strings, including numeric ones, bools, null, arrays, objects) throws InvalidArgumentException before any bucketing work runs. Negatives, floats, and duplicates are all fine; NAN/INF/-INF pass the type check (they're still floats) but aren't meaningfully sortable — NAN in particular compares false against everything, including itself. Buckets are sized via bucketCount = max(1, floor(sqrt(n))), each covering an equal slice of the array's value range; every bucket is sorted independently with insertionSort() and concatenated in order, which stays correct even when the input is heavily clustered into one bucket.

Searching — `ArraySearchAlogorthme`

Zack\PhpDsAlgo\Algorithmes\ArraySearchAlogorthme — all seven methods return the found index/key, or -1 if not found. binarySearch(), exponentialSearchImplementation(), interpolationSearchRecursive(), jumpSearch(), TernarySearchAlgorythme(), and FibonacciSearchALgorythme() all require a sorted array; linearSearch() does not.

use Zack\PhpDsAlgo\Algorithmes\ArraySearchAlogorthme;

// binarySearch(array $nums, int $target, int $start, int $end = 0)
ArraySearchAlogorthme::binarySearch([10, 20, 30, 40, 50], 30, 0, 4); // 2

// exponentialSearchImplementation(array $nums, int $target)
ArraySearchAlogorthme::exponentialSearchImplementation([1, 2, 3, 4, 5, 6, 7, 8], 8); // 7

// interpolationSearchRecursive(array $data, int $target, int $low, int $high)
// best suited to roughly-uniformly-distributed integer data
ArraySearchAlogorthme::interpolationSearchRecursive([10, 20, 30, 40, 50], 30, 0, 4); // 2

// jumpSearch(array $data, int $target, int $jumpSize, int $start, int $end, int $jumpIndex)
// caller manages block boundaries manually — see below
ArraySearchAlogorthme::jumpSearch([1, 3, 5, 7, 9, 11, 13, 15], 11, 3, 0, 2, 0); // 5

// linearSearch(array $data, int|string $target)
// no sort required; works on list or associative arrays, returns the matching key
ArraySearchAlogorthme::linearSearch([10, 20, 30, 40, 50], 40); // 3
ArraySearchAlogorthme::linearSearch(['a' => 1, 'b' => 2, 'c' => 3], 2); // 'b'

// TernarySearchAlgorythme(array $data, int|string $target)
// splits the range into three parts per call instead of binary search's two
ArraySearchAlogorthme::TernarySearchAlgorythme([10, 20, 30, 40, 50], 30); // 2

// FibonacciSearchALgorythme(array $data, int $target)
// narrows the range using Fibonacci numbers instead of a midpoint
ArraySearchAlogorthme::FibonacciSearchALgorythme([10, 20, 30, 40, 50], 30); // 2

jumpSearch() has no convenience wrapper — you must pass the first block's $start/$end yourself (typically 0 and $jumpSize - 1) and $jumpIndex = 0; the method advances the block internally on each recursive call.

linearSearch() uses strict comparison (===), so 0, '0', and false are not interchangeable as targets, and it's O(n) regardless of ordering — reach for it only when the array isn't sorted or is too small to justify the other methods' setup cost.

binarySearch()'s parameter order is ($nums, $target, $start, $end = 0) — note $start comes before $end, and $end is the one with a default. Passing arguments in the wrong order is a silent logic bug, not a type error, since both are int.

TernarySearchAlgorythme() is a thin wrapper — unlike jumpSearch(), it takes just ($data, $target) and manages the $low/$high boundaries internally via a private recursive helper.

FibonacciSearchALgorythme() takes ($data, $target) with $target typed strictly int (not int|string like linearSearch()/TernarySearchAlgorythme()). It relies on the public getClosestFibonacci(int $n): array helper (returns ['f1' => ..., 'f2' => ..., 'f3' => ...], the smallest Fibonacci number >= $n plus its two predecessors) to seed the probe range.

String Matching — `KMP`

Zack\PhpDsAlgo\Algorithmes\Strings\KMP — Knuth-Morris-Pratt substring search.

use Zack\PhpDsAlgo\Algorithmes\Strings\KMP;

KMP::run('ABABDABACDABABCABAB', 'ABABCABAB'); // [10]
KMP::run('AABAACAADAABAABA', 'AABA');          // [0, 9, 12] — overlapping occurrences included
KMP::run('hello', '');                          // [] — an empty pattern (or text) returns no matches

KMP::calculateLspTable(str_split('AABA'));      // [0, 1, 0, 1] — the "longest suffix-prefix" table run() uses internally

run($text, $pattern) returns the zero-based starting index of every occurrence of $pattern in $text, including overlapping ones — KMP's whole point is avoiding re-comparing characters already matched after a mismatch, using the LSP (longest suffix-prefix) table calculateLspTable() builds from the pattern up front.

Sliding Window — `SlidingWindow`

Zack\PhpDsAlgo\Algorithmes\SlidingWindow

use Zack\PhpDsAlgo\Algorithmes\SlidingWindow;

SlidingWindow::processFixedSizeSlidingWindow(
    [1, 2, 3, 4, 5],
    3, // window size
    function (array $window, int $startIndex) {
        echo implode(',', $window), ' @ ', $startIndex, PHP_EOL;
    }
);
// 1,2,3 @ 0
// 2,3,4 @ 1
// 3,4,5 @ 2

If $size <= 0 or $size is larger than the array, the callback is never invoked (no error).

Edit Distance — `LevenshteinDistance`

Zack\PhpDsAlgo\Algorithmes\LevenshteinDistance — classic Wagner-Fischer dynamic-programming edit distance between two strings, comparing characters with === (case-sensitive). calculate() returns an array with the DP table and the reconstructed optimal path of edits, not just the distance.

use Zack\PhpDsAlgo\Algorithmes\LevenshteinDistance;

$result = LevenshteinDistance::calculate('kitten', 'sitting');

$result['minimumEditDistance']; // 3
$result['path'];                // list of ['step' => 'Match'|'Substitute'|'Insert'|'Delete', 'from' => ..., 'to' => ..., 'direction' => ...],
                                 // walked from the last character back to the first
$result['matrix'];              // the full DP table, headers included
$result['WordsData'];           // ['word1', 'word2', 'Word1Spaced', 'Word2Spaced', 'Xrows', 'YColumns']

Graph Traversal — BFS / DFS

Zack\PhpDsAlgo\Algorithmes\GraphBreadthFirstTraversal / GraphDepthFirstTraversal — each has one static traverse(IGraph $graph, int|string $start): array method, returning visited nodes in traversal order. Both throw NotFoundException if $start isn't a node in the graph.

use Zack\PhpDsAlgo\Algorithmes\GraphBreadthFirstTraversal;
use Zack\PhpDsAlgo\Algorithmes\GraphDepthFirstTraversal;

GraphBreadthFirstTraversal::traverse($graph, 'A');
GraphDepthFirstTraversal::traverse($graph, 'A');

DFS is stack-based (iterative, not recursive) — for a node with neighbors [B, C], C is explored before B (last-pushed, first-popped).

Shortest Path — `DijkstraAlgorithm`

Zack\PhpDsAlgo\Algorithmes\DijkstraAlgorithm\DijkstraAlgorithm — single-source shortest paths on a weighted Graph, using a PriorityQueue(PriorityQueueTypeEnum::Min) internally. Unlike every other class under Algorithmes/, it's stateful — construct one, call calculateDistances(), then query the result off the same instance.

use Zack\PhpDsAlgo\Algorithmes\DijkstraAlgorithm\DijkstraAlgorithm;

$dijkstra = new DijkstraAlgorithm();
$dijkstra->calculateDistances($graph, 'A');   // populates internal per-node distance/predecessor state

$dijkstra->findShortestPath('D'); // ['D', 'B', 'C', 'A'] — target-to-source order, reverse it yourself
$dijkstra->display();             // pretty-prints every node's distance/visited/previous to stdout

calculateDistances(IGraph $graph, int|string $sourceNode) throws RuntimeException("No node with this value") if $sourceNode isn't in the graph, and RuntimeException("the weight is not a numeric value") the moment it relaxes across an edge with a null (unweighted) weight — checked lazily per edge as the algorithm reaches it, not via $graph->isWeighted() up front. findShortestPath(int|string $targetNode) throws RuntimeException("Target node does not exist") if $targetNode was never in the graph the last calculateDistances() call computed against; call calculateDistances() first or it always throws. An unreachable node's path is just itself (single-element array).

MinHeap/PriorityQueue have no decreaseKey(), so relaxation re-inserts a fresh, cheaper queue entry for a node instead of updating one in place; stale entries for an already-finalized node are skipped lazily when popped. See articles/12-dijkstra.md for the full walkthrough, including the current test-coverage gaps (display() and a couple of branches are untested as of this writing).

General Array Helpers — `GeneralArrayAlgorithms`

Zack\PhpDsAlgo\Algorithmes\GeneralArrayAlgorithms — generic (@template T, mixed at runtime) helpers used internally by Set/HashSet and reusable directly.

use Zack\PhpDsAlgo\Algorithmes\GeneralArrayAlgorithms;

GeneralArrayAlgorithms::hasDuplicates([1, 2, 3, 2]); // true
GeneralArrayAlgorithms::contains([1, 2, 3], 2);      // true, strict (===) comparison
GeneralArrayAlgorithms::remove([1, 2, 3], 2);        // [1, 3] — returns a NEW array, does not mutate its argument
GeneralArrayAlgorithms::equals(1, 1);                // true
GeneralArrayAlgorithms::equals(NAN, NAN);            // true — the one carve-out from plain ===

contains() throws InvalidArgumentException if $value is null (null is never treated as a findable element). remove() is pure: it takes $data by value and returns a new, re-indexed (array_values()) array with every matching element removed — callers must capture the return value ($data = GeneralArrayAlgorithms::remove($data, $x)) to see the removal, since the input array itself is left untouched.

equals() is the shared equality definition behind both contains() and remove(): strict ===, except that two NAN floats are treated as equal to each other. Without that carve-out, NAN === NAN is always false in PHP, so contains() and remove() would disagree with each other about a NAN element — contains() could report it present while remove() could never actually match and delete it. Keeping both methods on this one equals() definition is what keeps them consistent; Set::indexOf() (and, through it, HashSet::getValuePosition()/update()) also calls equals() directly for the same reason.

Low-level Helpers — `AlgorythmesGlobalHelpers`

Zack\PhpDsAlgo\Helpers\Algorythmes\AlgorythmesGlobalHelpers — shared primitives used internally by the sorting/searching algorithms above; also usable directly.

use Zack\PhpDsAlgo\Helpers\Algorythmes\AlgorythmesGlobalHelpers;

AlgorythmesGlobalHelpers::isBetween(5, 1, 10); // true, inclusive on both ends

$nums = [1, 2, 3];
AlgorythmesGlobalHelpers::swapValuesOfArray($nums, 0, 2); // by reference; $nums is now [3, 2, 1]
// throws InvalidArgumentException if either index doesn't exist in the array

getMinAndMax(array $data) (used internally by bucketSort(), see Sorting above) returns ['min' => ..., 'max' => ...] in one linear pass; passing an empty $data triggers a PHP "undefined array key" warning rather than a validated error, so don't call it with an empty array. isOdd(int $value)/isEven(int $value) round out the set.

Exceptions & Error Handling

Exception	Thrown by	Notes
`InvalidArgumentException` (SPL)	Most linked-list, stack, and queue error paths	Linked lists — including `CircularLinkedList` — use constants from `Zack\PhpDsAlgo\Constants\ErrorMessages` (`LINKEDLIST_IS_EMPTY`, `INDEX_OUT_OF_BOUND`, `NO_NODE_WITH_THIS_VALUE`); `ArrayStack`/`Queue`/`Graph` mostly use plain inline messages instead
`InvalidArgumentException` (SPL)	`Queue`'s constructor, when `$maxCapacity` is smaller than the number of initial items; `setMaxCapacity()`, when the new capacity is smaller than the queue's current size; `enqueue()`, once the queue is at `maxCapacity`	See Queue above — `Deque::enqueueFront()` is the one exception, it doesn't check capacity
`InvalidArgumentException` (SPL)	`ArraySortAlgorythmes::bucketSort()`, for any element that isn't an `int` or `float` (checked for every element before any bucketing work runs)	See Sorting above
`InvalidArgumentException` (SPL)	`HashTable`'s constructor (`$capacity <= 0`); `insert()`/`hasValue()`/`delete()`/`getValuePosition()`/`update()`/`getValue()` when given an unhashable value (a closure or a resource)	See What counts as "hashable"
`InvalidArgumentException` (SPL)	`HashMap`'s constructor (`$capacity <= 0`); `put()`/`hasKey()`/`get()`/`delete()`/`getKeyPosition()`/`update()` when given an unhashable key (a closure or a resource) — values have no such restriction	See Keys vs. values
`InvalidArgumentException` (SPL)	`GeneralArrayAlgorithms::contains()` (used internally by `Set::add()`/`contains()`/`remove()` and the set-algebra methods) when given `null`	See Set / General Array Helpers
`InvalidArgumentException` (SPL)	`HashSet`'s constructor (`$capacity <= 0`); `insert()`/`hasValue()`/`delete()`/`getValuePosition()` when given an unhashable value (`null`, an array, a resource, or a closure)	See What counts as "hashable" — `update()` is the one exception: it never throws, returning `false` instead
`OutOfBoundsException` (SPL)	`Set::get(int $index)` for an index outside the set's current range	See Indexed access above
`RuntimeException` (SPL)	`MinHeap`/`MaxHeap` (`AbstractBinaryHeap::peek()`/`extract()`) on an empty heap; `PriorityQueue::peek()`/`extract()` on an empty queue (delegates straight to its internal `MaxHeap`/`MinHeap`, whichever `PriorityQueueTypeEnum` was passed to the constructor)	The only structures in this library that throw `RuntimeException` for an empty-container error instead of `InvalidArgumentException` — worth remembering if you're catching by exception type
`RuntimeException` (SPL)	`DijkstraAlgorithm::calculateDistances()` (unknown source node, or a non-numeric/unweighted edge weight hit mid-relaxation); `DijkstraAlgorithm::findShortestPath()` (unknown target node)	See Shortest Path — DijkstraAlgorithm
`Zack\PhpDsAlgo\Exception\NotFoundException`	`GraphBreadthFirstTraversal::traverse()`, `GraphDepthFirstTraversal::traverse()`	Built via `NotFoundException::nodeNotFound($value)`
`Zack\PhpDsAlgo\Exception\DuplicateNodeException`	`Graph::addNode()` on a duplicate	Built via `DuplicateNodeException::nodeDuplicate($value)`
`Zack\PhpDsAlgo\Exception\EdgeNotFoundException`	`Graph::getEdge()` on a missing edge	Built via `EdgeNotFoundException::edgeNotFound($source, $destination)`

use Zack\PhpDsAlgo\Exception\NotFoundException;

try {
    GraphBreadthFirstTraversal::traverse($graph, 'unknown-node');
} catch (NotFoundException $e) {
    echo $e->getMessage(); // "Node with value 'unknown-node' was not found."
}

Known Quirks & Gotchas

A few behaviors worth knowing before you rely on them — none of these are "wrong" enough to change without a deliberate decision, but all of them have surprised someone while building this library:

Queue::front()/Queue::rear() don't check for an empty queue, despite IQueue's docblock promising @throws InvalidArgumentException. Calling either on an empty queue just triggers a PHP "undefined array key" warning and returns null.
Queue's constructor doesn't reindex array keys (no array_values()), unlike ArrayStack::fromArray(). Building a Queue from a non-sequential array (e.g. [5 => 'a', 9 => 'b']) will break front()/rear(), which assume index 0 and count - 1.
Deque::enqueueFront() doesn't check isFull(), but dequeueTail() doesn't throw on empty. Both break the symmetry with their inherited Queue counterparts (enqueue() checks capacity; dequeue() throws on empty) — see Deque above.
BinaryTree/BinarySearchTree are mutable, unlike the linked lists above. insert()/remove()/balance() change nodes in place and return $this for chaining — there's no clone-then-splice persistence here, matching ArrayStack/Queue/Graph/the heaps instead. See BinaryTree & BinarySearchTree above.
AbstractTree::getIterator() is in-order (left, node, right); levelOrder()/toArray() are breadth-first. foreach ($tree as $value) and $tree->toArray() visit nodes in a genuinely different order on any tree with more than one level — don't assume they agree.
GraphEdge::getWeight() returns null for an unweighted edge — int|float|null, not int|float. Always null-check (or use Graph::isWeighted()) before doing arithmetic on it.
A handful of defensive null/false guards are unreachable in practice. Graph::removeNode(), and insert()/removeAt()/get() on both linked lists, each have a redundant guard clause that's already preceded by an equivalent bounds check earlier in the same method — under the classes' normal invariants they can never actually trigger. Harmless, just dead code.
ArraySearchAlogorthme::interpolationSearchRecursive() computes its estimated position with float division and uses the (possibly fractional) result both as an array index and as a recursive int argument — PHP emits an implicit float-to-int-conversion deprecation notice in that case. It still returns the correct result; it's just noisy.
Graph::getAdjencyMetrix() and Graph::printAdjacencyMatrix() spell "adjacency"/"matrix" inconsistently — the getter matches the existing getAdjency() typo (Adjency, Metrix), while the printer spells both correctly. Same method pair, two different spellings; match whichever one you're calling.
HashMap::get() returns null both for a missing key and for a key whose value genuinely is null. The two cases are indistinguishable from get()'s return value alone — call hasKey() first if that distinction matters.
MinHeap/MaxHeap custom comparators must return exactly -1/0/1. heapifyDown()'s child-selection compares the comparator's result against the literal -1, not its sign — a comparator written in the common fn($a, $b) => $a - $b style (returning an arbitrary signed magnitude) will misorder the heap once extract() or the array constructor runs. Always use <=> in a heap comparator. See Heap above.
HashSet objects hash by identity (spl_object_id()), while HashTable/HashMap hash objects by value (serialize()). Two distinct object instances with identical properties will very likely land in different buckets in a HashSet but the same bucket in a HashTable/HashMap — membership is always === either way, so this only affects which bucket a lookup starts scanning, never correctness, but it's a real difference between structures that otherwise look alike. See HashSet above.
Set/HashSet treat two NAN floats as equal to each other, unlike PHP's own ===. This is a deliberate carve-out in GeneralArrayAlgorithms::equals() (see General Array Helpers above) so that contains()/hasValue() and remove()/delete() agree with each other about a stored NAN — without it, a NAN could be reported present yet never actually removable.

Testing

composer test                                  # full suite (vendor/bin/phpunit)
vendor/bin/phpunit tests/Unit/DataStructure     # just the data-structure tests
vendor/bin/phpunit --filter QueueTest           # a single test class
vendor/bin/phpunit --coverage-text              # coverage summary (needs Xdebug or PCOV)

There is no other linter or static analysis tool configured — php -l path/to/File.php is the extent of syntax checking beyond the test suite.

Project Structure

src/
├── Algorithmes/            # static utility classes operating on plain arrays
│   ├── DijkstraAlgorithm/   # DijkstraAlgorithm, DijkstraAlgorithmDistance — stateful, not static, see above
│   └── Strings/              # KMP — see String Matching section above
├── Constants/               # ErrorMessages
├── Contracts/                # interfaces: ILinkedList, IDoublyLinkedList, IStack, IQueue, IDeque, IGraph, IHeap, IPriorityQueue, IHashTable, IHashMap, ISet, IHashSet
│   └── Tree/                  # ITree, IBinaryTree, IBinarySearchTree
├── DataStructure/
│   ├── LinkedList/Single/    # SingleLinkedList, SingleLinkedListNode, CircularLinkedList (reuses SingleLinkedListNode)
│   ├── LinkedList/Doubly/    # DoublyLinkedList, DoublyLinkedListNode
│   ├── Stack/                 # ArrayStack
│   ├── Queue/                 # Queue, Deque
│   ├── Graph/                  # Graph, GraphNode, GraphEdge
│   ├── Heap/                   # AbstractBinaryHeap, MinHeap, MaxHeap, PriorityQueue, PriorityQueueNode
│   ├── HashTabe/                # HashTable, HashMap, HashMapNode, HashSet (folder name is a typo — see the HashTable section above)
│   ├── Set/                      # Set — array-backed, no hashing, see the Set section above
│   └── Tree/                      # AbstractTree, BinaryTreeNode, BinaryTree, BinarySearchTree — see BinaryTree & BinarySearchTree section above
├── enums/                     # PriorityQueueTypeEnum
├── Exception/                # NotFoundException, DuplicateNodeException, EdgeNotFoundException
└── Helpers/Algorythmes/       # AlgorythmesGlobalHelpers

(src/index.php is a scratch/demo entrypoint, not part of the library proper; the legacy top-level Zack\PhpDsAlgo\SortingAlgorithms duplicate has been removed entirely.)

Note the intentional misspellings (Algorythmes, Alogorthme) used consistently across namespaces and folder names — they're not typos to "fix," PSR-4 resolution depends on them matching exactly. (The plain-tree class files were briefly a genuine, unintentional PSR-4 mismatch — BinarryTree.php/IBinarryTree.php on disk, declaring correctly-spelled BinaryTree/IBinaryTree inside — which is why case matters: get it wrong by accident and the class is silently unreachable via use, not merely inconsistently named.)

Roadmap

See TODO.md and features.md for the current backlog. Graph algorithms (topological sort, undirected cycle detection, connected components, Bellman-Ford, Kruskal's/Prim's MST, A*) and dynamic programming beyond edit distance are the main remaining category gaps — tree (BinaryTree/BinarySearchTree), deque, heap sort, bucket sort, and string matching (KMP) are now done, see BinaryTree & BinarySearchTree, Deque, Sorting, and String Matching above. Further out: AVL/Red-Black trees, trie, disjoint set / union-find (a hash table, hash map, a plain unique-value Set, and a hashed HashSet now exist, see HashTable, HashMap, Set, and HashSet — note disjoint set/union-find is a different structure with its own find/union-by-rank shape, still on the backlog), skip list, segment/Fenwick trees.

License

MIT

zack965 / php-ds-algo

Package info

Security

Statistics

README

Table of Contents

Requirements

Installation

Quick Start

Data Structures

SingleLinkedList

Creating a list

Insertion (each call returns a new list)

Removal

Access

Transformations & functional methods

Iteration

CircularLinkedList

DoublyLinkedList

ArrayStack

Queue

Deque

Graph

Adjacency matrix

Building from an adjacency list

Traversal

Heap (MinHeap / MaxHeap)

Insert / peek / extract — the core priority-queue operations

Size, capacity, and clearing

Inspecting the heap

Custom comparators — the main way to reshape ordering

Advanced / internal-use methods

PriorityQueue

HashTable

What counts as "hashable"

Inspecting values

Resizing

HashMap

Keys vs. values

Inspecting entries

Resizing

Set

Indexed access

Set algebra

HashSet

What counts as "hashable"

update()

Inspecting values

Resizing

BinaryTree & BinarySearchTree

BinaryTree — plain binary tree, level-order insertion

BinarySearchTree — ordered insertion, O(log n) average lookups

Algorithms

Sorting — ArraySortAlgorythmes

Searching — ArraySearchAlogorthme

String Matching — KMP

Sliding Window — SlidingWindow

Edit Distance — LevenshteinDistance

Graph Traversal — BFS / DFS

Shortest Path — DijkstraAlgorithm

General Array Helpers — GeneralArrayAlgorithms

Low-level Helpers — AlgorythmesGlobalHelpers

Exceptions & Error Handling

Known Quirks & Gotchas

Testing

Project Structure

Roadmap

License

`BinaryTree` — plain binary tree, level-order insertion

`BinarySearchTree` — ordered insertion, `O(log n)` average lookups

Sorting — `ArraySortAlgorythmes`

Searching — `ArraySearchAlogorthme`

String Matching — `KMP`

Sliding Window — `SlidingWindow`

Edit Distance — `LevenshteinDistance`

Shortest Path — `DijkstraAlgorithm`

General Array Helpers — `GeneralArrayAlgorithms`

Low-level Helpers — `AlgorythmesGlobalHelpers`