JFIFxxC      C  " }!1AQa"q2#BR$3br %&'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz w!1AQaq"2B #3Rbrphp-ds/composer.json000064400000001215150364337220010465 0ustar00{ "name": "php-ds/php-ds", "license": "MIT", "keywords": ["php", "ds", "data structures", "polyfill"], "authors": [ { "name": "Rudi Theunissen", "email": "rudolf.theunissen@gmail.com" } ], "require": { "php": ">=7.0", "ext-json": "*" }, "require-dev": { "php-ds/tests": "^1.3" }, "provide": { "ext-ds": "1.3.0" }, "suggest": { "ext-ds": "to improve performance and reduce memory usage" }, "scripts": { "test": "phpunit" }, "autoload": { "psr-4" : { "Ds\\": "src" } } } php-ds/tests/bootstrap.php000064400000000134150364337220011632 0ustar00toArray(); } /** * Creates a shallow copy of the collection. * * @return static a shallow copy of the collection. */ public function copy(): self { return new static($this); } /** * Returns an array representation of the collection. * * The format of the returned array is implementation-dependent. Some * implementations may throw an exception if an array representation * could not be created (for example when object are used as keys). * * @return array */ abstract public function toArray(): array; /** * Invoked when calling var_dump. * * @return array */ public function __debugInfo() { return $this->toArray(); } /** * Returns a string representation of the collection, which is invoked when * the collection is converted to a string. */ public function __toString() { return 'object(' . get_class($this) . ')'; } } php-ds/src/Traits/Capacity.php000064400000006151150364337220012252 0ustar00capacity; } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->capacity = max($capacity, $this->capacity); } /** * @return float the structures growth factor. */ protected function getGrowthFactor(): float { return 2; } /** * @return float to multiply by when decreasing capacity. */ protected function getDecayFactor(): float { return 0.5; } /** * @return float the ratio between size and capacity when capacity should be * decreased. */ protected function getTruncateThreshold(): float { return 0.25; } /** * Checks and adjusts capacity if required. */ protected function checkCapacity() { if ($this->shouldIncreaseCapacity()) { $this->increaseCapacity(); } else { if ($this->shouldDecreaseCapacity()) { $this->decreaseCapacity(); } } } /** * @param int $total */ protected function ensureCapacity(int $total) { if ($total > $this->capacity()) { $this->capacity = max($total, $this->nextCapacity()); } } /** * @return bool whether capacity should be increased. */ protected function shouldIncreaseCapacity(): bool { return $this->count() >= $this->capacity(); } protected function nextCapacity(): int { return (int) ($this->capacity() * $this->getGrowthFactor()); } /** * Called when capacity should be increased to accommodate new values. */ protected function increaseCapacity() { $this->capacity = max( $this->count(), $this->nextCapacity() ); } /** * Called when capacity should be decrease if it drops below a threshold. */ protected function decreaseCapacity() { $this->capacity = max( self::MIN_CAPACITY, (int) ($this->capacity() * $this->getDecayFactor()) ); } /** * @return bool whether capacity should be increased. */ protected function shouldDecreaseCapacity(): bool { return count($this) <= $this->capacity() * $this->getTruncateThreshold(); } } php-ds/src/Traits/GenericSequence.php000064400000020021150364337220013552 0ustar00 */ private $array = []; /** * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { foreach ($values as $value) { $this->push($value); } $this->capacity = max( $values === null ? 0 : count($values), $this::MIN_CAPACITY ); } /** * @inheritdoc */ public function toArray(): array { return $this->array; } /** * @inheritdoc */ public function apply(callable $callback) { foreach ($this->array as &$value) { $value = $callback($value); } } /** * @inheritdoc */ public function merge($values): Sequence { $copy = $this->copy(); $copy->push(...$values); return $copy; } /** * @inheritdoc */ public function count(): int { return count($this->array); } /** * @inheritDoc */ public function contains(...$values): bool { foreach ($values as $value) { if ($this->find($value) === null) { return false; } } return true; } /** * @inheritDoc */ public function filter(callable $callback = null): Sequence { return new self(array_filter($this->array, $callback ?: 'boolval')); } /** * @inheritDoc */ public function find($value) { $offset = array_search($value, $this->array, true); return $offset === false ? null : $offset; } /** * @inheritDoc */ public function first() { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->array[0]; } /** * @inheritDoc */ public function get(int $index) { if ( ! $this->validIndex($index)) { throw new OutOfRangeException(); } return $this->array[$index]; } /** * @inheritDoc */ public function insert(int $index, ...$values) { if ( ! $this->validIndex($index) && $index !== count($this)) { throw new OutOfRangeException(); } array_splice($this->array, $index, 0, $values); $this->checkCapacity(); } /** * @inheritDoc */ public function join(string $glue = null): string { return implode($glue ?? '', $this->array); } /** * @inheritDoc */ public function last() { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->array[count($this) - 1]; } /** * @inheritDoc */ public function map(callable $callback): Sequence { return new self(array_map($callback, $this->array)); } /** * @inheritDoc */ public function pop() { if ($this->isEmpty()) { throw new UnderflowException(); } $value = array_pop($this->array); $this->checkCapacity(); return $value; } /** * @inheritDoc */ public function push(...$values) { $this->ensureCapacity($this->count() + count($values)); foreach ($values as $value) { $this->array[] = $value; } } /** * @inheritDoc */ public function reduce(callable $callback, $initial = null) { return array_reduce($this->array, $callback, $initial); } /** * @inheritDoc */ public function remove(int $index) { if ( ! $this->validIndex($index)) { throw new OutOfRangeException(); } $value = array_splice($this->array, $index, 1, null)[0]; $this->checkCapacity(); return $value; } /** * @inheritDoc */ public function reverse() { $this->array = array_reverse($this->array); } /** * @inheritDoc */ public function reversed(): Sequence { return new self(array_reverse($this->array)); } /** * Converts negative or large rotations into the minimum positive number * of rotations required to rotate the sequence by a given $r. */ private function normalizeRotations(int $r) { $n = count($this); if ($n < 2) return 0; if ($r < 0) return $n - (abs($r) % $n); return $r % $n; } /** * @inheritDoc */ public function rotate(int $rotations) { for ($r = $this->normalizeRotations($rotations); $r > 0; $r--) { array_push($this->array, array_shift($this->array)); } } /** * @inheritDoc */ public function set(int $index, $value) { if ( ! $this->validIndex($index)) { throw new OutOfRangeException(); } $this->array[$index] = $value; } /** * @inheritDoc */ public function shift() { if ($this->isEmpty()) { throw new UnderflowException(); } $value = array_shift($this->array); $this->checkCapacity(); return $value; } /** * @inheritDoc */ public function slice(int $offset, int $length = null): Sequence { if (func_num_args() === 1) { $length = count($this); } return new self(array_slice($this->array, $offset, $length)); } /** * @inheritDoc */ public function sort(callable $comparator = null) { if ($comparator) { usort($this->array, $comparator); } else { sort($this->array); } } /** * @inheritDoc */ public function sorted(callable $comparator = null): Sequence { $copy = $this->copy(); $copy->sort($comparator); return $copy; } /** * @inheritDoc */ public function sum() { return array_sum($this->array); } /** * @inheritDoc */ public function unshift(...$values) { if ($values) { $this->array = array_merge($values, $this->array); $this->checkCapacity(); } } /** * */ private function validIndex(int $index) { return $index >= 0 && $index < count($this); } /** * */ #[\ReturnTypeWillChange] public function getIterator() { foreach ($this->array as $value) { yield $value; } } /** * @inheritdoc */ public function clear() { $this->array = []; $this->capacity = self::MIN_CAPACITY; } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->push($value); } else { $this->set($offset, $value); } } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function &offsetGet($offset) { if ( ! $this->validIndex($offset)) { throw new OutOfRangeException(); } return $this->array[$offset]; } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { if (is_integer($offset) && $this->validIndex($offset)) { $this->remove($offset); } } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetExists($offset) { return is_integer($offset) && $this->validIndex($offset) && $this->get($offset) !== null; } } php-ds/src/Traits/SquaredCapacity.php000064400000002714150364337220013600 0ustar00capacity = max($this->square($capacity), $this->capacity); } /** * Called when capacity should be increased to accommodate new values. */ protected function increaseCapacity() { $this->capacity = $this->square( max( count($this) + 1, $this->capacity * $this->getGrowthFactor() ) ); } /** * @param int $total */ protected function ensureCapacity(int $total) { while ($total > $this->capacity()) { $this->increaseCapacity(); } } } php-ds/src/PriorityQueue.php000064400000016012150364337220012072 0ustar00 */ final class PriorityQueue implements Collection { use Traits\GenericCollection; use Traits\SquaredCapacity; public const MIN_CAPACITY = 8; /** * @var array> */ private $heap = []; /** * @var int */ private $stamp = 0; /** * Creates a new instance. */ public function __construct() { } /** * @inheritDoc */ public function clear() { $this->heap = []; $this->stamp = 0; $this->capacity = self::MIN_CAPACITY; } /** * @inheritDoc */ public function copy(): self { $copy = new PriorityQueue(); $copy->heap = $this->heap; $copy->stamp = $this->stamp; $copy->capacity = $this->capacity; return $copy; } /** * @inheritDoc */ public function count(): int { return count($this->heap); } /** * Returns the value with the highest priority in the priority queue. * * @return mixed * * @throw UnderflowException * * @psalm-return TValue */ public function peek() { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->heap[0]->value; } /** * Returns the index of a node's left leaf. * * @param int $index The index of the node. * * @return int The index of the left leaf. */ private function left(int $index): int { return ($index * 2) + 1; } /** * Returns the index of a node's right leaf. * * @param int $index The index of the node. * * @return int The index of the right leaf. */ private function right(int $index): int { return ($index * 2) + 2; } /** * Returns the index of a node's parent node. * * @param int $index The index of the node. * * @return int The index of the parent. */ private function parent(int $index): int { return (int) (($index - 1) / 2); } /** * Compares two indices of the heap. * * @return int */ private function compare(int $a, int $b) { $x = $this->heap[$a]; $y = $this->heap[$b]; // Compare priority, using insertion stamp as fallback. return ($x->priority <=> $y->priority) ?: ($y->stamp <=> $x->stamp); } /** * Swaps the nodes at two indices of the heap. */ private function swap(int $a, int $b) { $temp = $this->heap[$a]; $this->heap[$a] = $this->heap[$b]; $this->heap[$b] = $temp; } /** * Returns the index of a node's largest leaf node. * * @param int $parent the parent node. * * @return int the index of the node's largest leaf node. */ private function getLargestLeaf(int $parent) { $left = $this->left($parent); $right = $this->right($parent); if ($right < count($this->heap) && $this->compare($left, $right) < 0) { return $right; } return $left; } /** * Starts the process of sifting down a given node index to ensure that * the heap's properties are preserved. */ private function siftDown(int $node) { $last = floor(count($this->heap) / 2); for ($parent = $node; $parent < $last; $parent = $leaf) { // Determine the largest leaf to potentially swap with the parent. $leaf = $this->getLargestLeaf($parent); // Done if the parent is not greater than its largest leaf if ($this->compare($parent, $leaf) > 0) { break; } $this->swap($parent, $leaf); } } /** * Sets the root node and sifts it down the heap. * * @param PriorityNode $node */ private function setRoot(PriorityNode $node) { $this->heap[0] = $node; $this->siftDown(0); } /** * Returns the root node of the heap. * * @return PriorityNode */ private function getRoot(): PriorityNode { return $this->heap[0]; } /** * Returns and removes the value with the highest priority in the queue. * * @return mixed * * @psalm-return TValue */ public function pop() { if ($this->isEmpty()) { throw new UnderflowException(); } // Last leaf of the heap to become the new root. $leaf = array_pop($this->heap); if (empty($this->heap)) { return $leaf->value; } // Cache the current root value to return before replacing with next. $value = $this->getRoot()->value; // Replace the root, then sift down. $this->setRoot($leaf); $this->checkCapacity(); return $value; } /** * Sifts a node up the heap until it's in the right position. */ private function siftUp(int $leaf) { for (; $leaf > 0; $leaf = $parent) { $parent = $this->parent($leaf); // Done when parent priority is greater. if ($this->compare($leaf, $parent) < 0) { break; } $this->swap($parent, $leaf); } } /** * Pushes a value into the queue, with a specified priority. * * @param mixed $value * * @psalm-param TValue $value */ public function push($value, int $priority) { $this->checkCapacity(); // Add new leaf, then sift up to maintain heap, $this->heap[] = new PriorityNode($value, $priority, $this->stamp++); $this->siftUp(count($this->heap) - 1); } /** * @inheritDoc */ public function toArray(): array { $heap = $this->heap; $array = []; while ( ! $this->isEmpty()) { $array[] = $this->pop(); } $this->heap = $heap; return $array; } /** * @inheritDoc */ #[\ReturnTypeWillChange] public function getIterator() { while ( ! $this->isEmpty()) { yield $this->pop(); } } } /** * @internal * * @template TValue */ final class PriorityNode { /** * @var mixed * * @psalm-var TValue */ public $value; /** * @var int */ public $priority; /** * @var int */ public $stamp; /** * @param mixed $value * @param int $priority * @param int $stamp * * @psalm-param TValue $value */ public function __construct($value, int $priority, int $stamp) { $this->value = $value; $this->priority = $priority; $this->stamp = $stamp; } } php-ds/src/Set.php000064400000031137150364337220010004 0ustar00 */ final class Set implements Collection, \ArrayAccess { use Traits\GenericCollection; public const MIN_CAPACITY = Map::MIN_CAPACITY; /** * @var Map internal map to store the values. * * @psalm-var Map */ private $table; /** * Creates a new set using the values of an array or Traversable object. * The keys of either will not be preserved. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { $this->table = new Map(); foreach ($values as $value) { $this->add($value); } } /** * Adds zero or more values to the set. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function add(...$values) { foreach ($values as $value) { $this->table->put($value, null); } } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->table->allocate($capacity); } /** * Returns the current capacity of the set. */ public function capacity(): int { return $this->table->capacity(); } /** * Clear all elements in the Set */ public function clear() { $this->table->clear(); } /** * Determines whether the set contains all of zero or more values. * * @param mixed ...$values * * @return bool true if at least one value was provided and the set * contains all given values, false otherwise. * * @psalm-param TValue ...$values */ public function contains(...$values): bool { foreach ($values as $value) { if ( ! $this->table->hasKey($value)) { return false; } } return true; } /** * @inheritDoc */ public function copy(): self { return new self($this); } /** * Returns the number of elements in the Stack * * @return int */ public function count(): int { return count($this->table); } /** * Creates a new set using values from this set that aren't in another set. * * Formally: A \ B = {x ∈ A | x ∉ B} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function diff(Set $set): Set { return $this->table->diff($set->table)->keys(); } /** * Creates a new set using values in either this set or in another set, * but not in both. * * Formally: A ⊖ B = {x : x ∈ (A \ B) ∪ (B \ A)} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function xor(Set $set): Set { return $this->table->xor($set->table)->keys(); } /** * Returns a new set containing only the values for which a callback * returns true. A boolean test will be used if a callback is not provided. * * @param callable|null $callback Accepts a value, returns a boolean: * true : include the value, * false: skip the value. * * @return Set * * @psalm-param (callable(TValue): bool)|null $callback * @psalm-return Set */ public function filter(callable $callback = null): Set { return new self(array_filter($this->toArray(), $callback ?: 'boolval')); } /** * Returns the first value in the set. * * @return mixed the first value in the set. * * @psalm-return TValue */ public function first() { return $this->table->first()->key; } /** * Returns the value at a specified position in the set. * * @return mixed|null * * @throws OutOfRangeException * * @psalm-return TValue */ public function get(int $position) { return $this->table->skip($position)->key; } /** * Creates a new set using values common to both this set and another set. * * In other words, returns a copy of this set with all values removed that * aren't in the other set. * * Formally: A ∩ B = {x : x ∈ A ∧ x ∈ B} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function intersect(Set $set): Set { return $this->table->intersect($set->table)->keys(); } /** * @inheritDoc */ public function isEmpty(): bool { return $this->table->isEmpty(); } /** * Joins all values of the set into a string, adding an optional 'glue' * between them. Returns an empty string if the set is empty. * * @param string|null $glue */ public function join(string $glue = null): string { return implode($glue ?? '', $this->toArray()); } /** * Returns the last value in the set. * * @return mixed the last value in the set. * * @psalm-return TValue */ public function last() { return $this->table->last()->key; } /** * Returns a new set using the results of applying a callback to each * value. * * @param callable $callback * * @return Set * * @template TNewValue * @psalm-param callable(TValue): TNewValue $callback * @psalm-return Set */ public function map(callable $callback) { return new self(array_map($callback, $this->toArray())); } /** * Iteratively reduces the set to a single value using a callback. * * @param callable $callback Accepts the carry and current value, and * returns an updated carry value. * * @param mixed|null $initial Optional initial carry value. * * @return mixed The carry value of the final iteration, or the initial * value if the set was empty. * * @template TCarry * @psalm-param callable(TCarry, TValue): TCarry $callback * @psalm-param TCarry $initial * @psalm-return TCarry */ public function reduce(callable $callback, $initial = null) { $carry = $initial; foreach ($this as $value) { $carry = $callback($carry, $value); } return $carry; } /** * Removes zero or more values from the set. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function remove(...$values) { foreach ($values as $value) { $this->table->remove($value, null); } } /** * Reverses the set in-place. */ public function reverse() { $this->table->reverse(); } /** * Returns a reversed copy of the set. * * @return Set * * @psalm-return Set */ public function reversed(): Set { $reversed = $this->copy(); $reversed->table->reverse(); return $reversed; } /** * Returns a subset of a given length starting at a specified offset. * * @param int $offset If the offset is non-negative, the set will start * at that offset in the set. If offset is negative, * the set will start that far from the end. * * @param int $length If a length is given and is positive, the resulting * set will have up to that many values in it. * If the requested length results in an overflow, only * values up to the end of the set will be included. * * If a length is given and is negative, the set * will stop that many values from the end. * * If a length is not provided, the resulting set * will contains all values between the offset and the * end of the set. * * @return Set * * @psalm-return Set */ public function slice(int $offset, int $length = null): Set { $sliced = new self(); $sliced->table = $this->table->slice($offset, $length); return $sliced; } /** * Sorts the set in-place, based on an optional callable comparator. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @psalm-param (callable(TValue, TValue): int)|null $comparator */ public function sort(callable $comparator = null) { $this->table->ksort($comparator); } /** * Returns a sorted copy of the set, based on an optional callable * comparator. Natural ordering will be used if a comparator is not given. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @return Set * * @psalm-param (callable(TValue, TValue): int)|null $comparator * @psalm-return Set */ public function sorted(callable $comparator = null): Set { $sorted = $this->copy(); $sorted->table->ksort($comparator); return $sorted; } /** * Returns the result of adding all given values to the set. * * @param array|\Traversable $values * * @return Set * * @template TValue2 * @psalm-param iterable $values * @psalm-return Set */ public function merge($values): Set { $merged = $this->copy(); foreach ($values as $value) { $merged->add($value); } return $merged; } /** * @inheritDoc */ public function toArray(): array { return iterator_to_array($this); } /** * Returns the sum of all values in the set. * * @return int|float The sum of all the values in the set. */ public function sum() { return array_sum($this->toArray()); } /** * Creates a new set that contains the values of this set as well as the * values of another set. * * Formally: A ∪ B = {x: x ∈ A ∨ x ∈ B} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function union(Set $set): Set { $union = new self(); foreach ($this as $value) { $union->add($value); } foreach ($set as $value) { $union->add($value); } return $union; } /** * Get iterator */ #[\ReturnTypeWillChange] public function getIterator() { foreach ($this->table as $key => $value) { yield $key; } } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->add($value); return; } throw new Error(); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetGet($offset) { return $this->table->skip($offset)->key; } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetExists($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { throw new Error(); } /** * Ensures that the internal table will be cloned too. */ public function __clone() { $this->table = clone $this->table; } } php-ds/src/Stack.php000064400000007701150364337220010316 0ustar00 */ final class Stack implements Collection, \ArrayAccess { use Traits\GenericCollection; /** * @var Vector internal vector to store values of the stack. * * @psalm-var Vector */ private $vector; /** * Creates an instance using the values of an array or Traversable object. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { $this->vector = new Vector($values); } /** * Clear all elements in the Stack */ public function clear() { $this->vector->clear(); } /** * @inheritdoc */ public function copy(): self { return new self($this->vector); } /** * Returns the number of elements in the Stack */ public function count(): int { return count($this->vector); } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->vector->allocate($capacity); } /** * Returns the current capacity of the stack. */ public function capacity(): int { return $this->vector->capacity(); } /** * Returns the value at the top of the stack without removing it. * * @return mixed * * @throws \UnderflowException if the stack is empty. * * @psalm-return TValue */ public function peek() { return $this->vector->last(); } /** * Returns and removes the value at the top of the stack. * * @return mixed * * @throws \UnderflowException if the stack is empty. * * @psalm-return TValue */ public function pop() { return $this->vector->pop(); } /** * Pushes zero or more values onto the top of the stack. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function push(...$values) { $this->vector->push(...$values); } /** * @inheritDoc */ public function toArray(): array { return array_reverse($this->vector->toArray()); } /** * */ #[\ReturnTypeWillChange] public function getIterator() { while ( ! $this->isEmpty()) { yield $this->pop(); } } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->push($value); } else { throw new Error(); } } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetGet($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetExists($offset) { throw new Error(); } /** * Ensures that the internal vector will be cloned too. */ public function __clone() { $this->vector = clone $this->vector; } } php-ds/src/Deque.php000064400000001340150364337220010305 0ustar00 */ final class Deque implements Sequence { use Traits\GenericCollection; use Traits\GenericSequence; use Traits\SquaredCapacity; public const MIN_CAPACITY = 8; protected function shouldIncreaseCapacity(): bool { return count($this) >= $this->capacity; } } php-ds/src/Pair.php000064400000006010150364337220010134 0ustar00key = $key; $this->value = $value; } /** * * @param mixed $name * * @return mixed|null */ public function __isset($name) { if ($name === 'key' || $name === 'value') { return $this->$name !== null; } return false; } /** * This allows unset($pair->key) to not completely remove the property, * but be set to null instead. * * @return void */ public function __unset(string $name) { if ($name === 'key' || $name === 'value') { $this->$name = null; return; } throw new OutOfBoundsException(); } /** * @param mixed $name * * @return mixed|null */ public function &__get($name) { if ($name === 'key' || $name === 'value') { return $this->$name; } throw new OutOfBoundsException(); } /** * @param mixed $name * @param mixed $value * * @return mixed|null */ public function __set($name, $value) { if ($name === 'key' || $name === 'value') { $this->$name = $value; return; } throw new OutOfBoundsException(); } /** * Returns a copy of the Pair * * @psalm-return self */ public function copy(): self { return new self($this->key, $this->value); } /** * Returns a representation to be used for var_dump and print_r. * * @return array * * @psalm-return array{key: TKey, value: TValue} */ public function __debugInfo() { return $this->toArray(); } /** * @inheritDoc * * @psalm-return array{key: TKey, value: TValue} */ public function toArray(): array { return [ 'key' => $this->key, 'value' => $this->value, ]; } /** * @inheritDoc * * @psalm-return array{key: TKey, value: TValue} */ #[\ReturnTypeWillChange] public function jsonSerialize() { return $this->toArray(); } /** * Returns a string representation of the pair. */ public function __toString() { return 'object(' . get_class($this) . ')'; } } php-ds/src/Sequence.php000064400000023260150364337220011017 0ustar00 */ interface Sequence extends Collection, \ArrayAccess { /** * Ensures that enough memory is allocated for a required capacity. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity); /** * Updates every value in the sequence by applying a callback, using the * return value as the new value. * * @param callable $callback Accepts the value, returns the new value. * * @psalm-param callable(TValue): TValue $callback */ public function apply(callable $callback); /** * Returns the current capacity of the sequence. * * @return int */ public function capacity(): int; /** * Determines whether the sequence contains all of zero or more values. * * @param mixed ...$values * * @return bool true if at least one value was provided and the sequence * contains all given values, false otherwise. * * @psalm-param TValue ...$values */ public function contains(...$values): bool; /** * Returns a new sequence containing only the values for which a callback * returns true. A boolean test will be used if a callback is not provided. * * @param callable|null $callback Accepts a value, returns a boolean result: * true : include the value, * false: skip the value. * * @return Sequence * * @psalm-param (callable(TValue): bool)|null $callback * @psalm-return Sequence */ public function filter(callable $callback = null): Sequence; /** * Returns the index of a given value, or null if it could not be found. * * @param mixed $value * * @return int|null * * @psalm-param TValue $value */ public function find($value); /** * Returns the first value in the sequence. * * @return mixed * * @throws \UnderflowException if the sequence is empty. * * @psalm-return TValue */ public function first(); /** * Returns the value at a given index (position) in the sequence. * * @return mixed * * @throws \OutOfRangeException if the index is not in the range [0, size-1] * * @psalm-return TValue */ public function get(int $index); /** * Inserts zero or more values at a given index. * * Each value after the index will be moved one position to the right. * Values may be inserted at an index equal to the size of the sequence. * * @param mixed ...$values * * @throws \OutOfRangeException if the index is not in the range [0, n] * * @psalm-param TValue ...$values */ public function insert(int $index, ...$values); /** * Joins all values of the sequence into a string, adding an optional 'glue' * between them. Returns an empty string if the sequence is empty. */ public function join(string $glue = null): string; /** * Returns the last value in the sequence. * * @return mixed * * @throws \UnderflowException if the sequence is empty. * * @psalm-return TValue */ public function last(); /** * Returns a new sequence using the results of applying a callback to each * value. * * @param callable $callback * * @return Sequence * * @template TNewValue * @psalm-param callable(TValue): TNewValue $callback * @psalm-return Sequence */ public function map(callable $callback): Sequence; /** * Returns the result of adding all given values to the sequence. * * @param array|\Traversable $values * * @return Sequence * * @template TValue2 * @psalm-param iterable $values * @psalm-return Sequence */ public function merge($values): Sequence; /** * Removes the last value in the sequence, and returns it. * * @return mixed what was the last value in the sequence. * * @throws \UnderflowException if the sequence is empty. * * @psalm-return TValue */ public function pop(); /** * Adds zero or more values to the end of the sequence. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function push(...$values); /** * Iteratively reduces the sequence to a single value using a callback. * * @param callable $callback Accepts the carry and current value, and * returns an updated carry value. * * @param mixed|null $initial Optional initial carry value. * * @return mixed The carry value of the final iteration, or the initial * value if the sequence was empty. * * @template TCarry * @psalm-param callable(TCarry, TValue): TCarry $callback * @psalm-param TCarry $initial * @psalm-return TCarry */ public function reduce(callable $callback, $initial = null); /** * Removes and returns the value at a given index in the sequence. * * @param int $index this index to remove. * * @return mixed the removed value. * * @throws \OutOfRangeException if the index is not in the range [0, size-1] * * @psalm-return TValue */ public function remove(int $index); /** * Reverses the sequence in-place. */ public function reverse(); /** * Returns a reversed copy of the sequence. * * @return Sequence * * @psalm-return Sequence */ public function reversed(); /** * Rotates the sequence by a given number of rotations, which is equivalent * to successive calls to 'shift' and 'push' if the number of rotations is * positive, or 'pop' and 'unshift' if negative. * * @param int $rotations The number of rotations (can be negative). */ public function rotate(int $rotations); /** * Replaces the value at a given index in the sequence with a new value. * * @param mixed $value * * @throws \OutOfRangeException if the index is not in the range [0, size-1] * * @psalm-param TValue $value */ public function set(int $index, $value); /** * Removes and returns the first value in the sequence. * * @return mixed what was the first value in the sequence. * * @throws \UnderflowException if the sequence was empty. * * @psalm-return TValue */ public function shift(); /** * Returns a sub-sequence of a given length starting at a specified index. * * @param int $index If the index is positive, the sequence will start * at that index in the sequence. If index is negative, * the sequence will start that far from the end. * * @param int $length If a length is given and is positive, the resulting * sequence will have up to that many values in it. * If the length results in an overflow, only values * up to the end of the sequence will be included. * * If a length is given and is negative, the sequence * will stop that many values from the end. * * If a length is not provided, the resulting sequence * will contain all values between the index and the * end of the sequence. * * @return Sequence * * @psalm-return Sequence */ public function slice(int $index, int $length = null): Sequence; /** * Sorts the sequence in-place, based on an optional callable comparator. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @psalm-param (callable(TValue, TValue): int)|null $comparator */ public function sort(callable $comparator = null); /** * Returns a sorted copy of the sequence, based on an optional callable * comparator. Natural ordering will be used if a comparator is not given. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @return Sequence * * @psalm-param (callable(TValue, TValue): int)|null $comparator * @psalm-return Sequence */ public function sorted(callable $comparator = null): Sequence; /** * Returns the sum of all values in the sequence. * * @return int|float The sum of all the values in the sequence. */ public function sum(); /** * @inheritDoc * * @return list */ function toArray(): array; /** * Adds zero or more values to the front of the sequence. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function unshift(...$values); } php-ds/src/Queue.php000064400000007375150364337220010344 0ustar00 */ final class Queue implements Collection, \ArrayAccess { use Traits\GenericCollection; /** * @var Deque internal deque to store values. * * @psalm-var Deque */ private $deque; /** * Creates an instance using the values of an array or Traversable object. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { $this->deque = new Deque($values); } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->deque->allocate($capacity); } /** * Returns the current capacity of the queue. */ public function capacity(): int { return $this->deque->capacity(); } /** * @inheritDoc */ public function clear() { $this->deque->clear(); } /** * @inheritDoc */ public function copy(): self { return new self($this->deque); } /** * @inheritDoc */ public function count(): int { return count($this->deque); } /** * Returns the value at the front of the queue without removing it. * * @return mixed * * @psalm-return TValue */ public function peek() { return $this->deque->first(); } /** * Returns and removes the value at the front of the Queue. * * @return mixed * * @psalm-return TValue */ public function pop() { return $this->deque->shift(); } /** * Pushes zero or more values into the back of the queue. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function push(...$values) { $this->deque->push(...$values); } /** * @inheritDoc */ public function toArray(): array { return $this->deque->toArray(); } /** * Get iterator */ #[\ReturnTypeWillChange] public function getIterator() { while ( ! $this->isEmpty()) { yield $this->pop(); } } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->push($value); } else { throw new Error(); } } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetGet($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetExists($offset) { throw new Error(); } /** * Ensures that the internal sequence will be cloned too. */ public function __clone() { $this->deque = clone $this->deque; } } php-ds/src/Map.php000064400000050566150364337220007775 0ustar00 */ final class Map implements Collection, \ArrayAccess { use Traits\GenericCollection; use Traits\SquaredCapacity; public const MIN_CAPACITY = 8; /** * @var array internal array to store pairs * * @psalm-var array */ private $pairs = []; /** * Creates a new instance. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { if (func_num_args()) { $this->putAll($values); } } /** * Updates all values by applying a callback function to each value. * * @param callable $callback Accepts two arguments: key and value, should * return what the updated value will be. * * @psalm-param callable(TKey, TValue): TValue $callback */ public function apply(callable $callback) { foreach ($this->pairs as &$pair) { $pair->value = $callback($pair->key, $pair->value); } } /** * @inheritDoc */ public function clear() { $this->pairs = []; $this->capacity = self::MIN_CAPACITY; } /** * Return the first Pair from the Map * * @return Pair * * @throws UnderflowException * * @psalm-return Pair */ public function first(): Pair { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->pairs[0]; } /** * Return the last Pair from the Map * * @return Pair * * @throws UnderflowException * * @psalm-return Pair */ public function last(): Pair { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->pairs[count($this->pairs) - 1]; } /** * Return the pair at a specified position in the Map * * @return Pair * * @throws OutOfRangeException * * @psalm-return Pair */ public function skip(int $position): Pair { if ($position < 0 || $position >= count($this->pairs)) { throw new OutOfRangeException(); } return $this->pairs[$position]->copy(); } /** * Returns the result of associating all keys of a given traversable object * or array with their corresponding values, as well as those of this map. * * @param array|\Traversable $values * * @return Map * * @template TKey2 * @template TValue2 * @psalm-param iterable $values * @psalm-return Map */ public function merge($values): Map { $merged = new self($this); $merged->putAll($values); return $merged; } /** * Creates a new map containing the pairs of the current instance whose keys * are also present in the given map. In other words, returns a copy of the * current map with all keys removed that are not also in the other map. * * @param Map $map The other map. * * @return Map A new map containing the pairs of the current instance * whose keys are also present in the given map. In other * words, returns a copy of the current map with all keys * removed that are not also in the other map. * * @template TKey2 * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function intersect(Map $map): Map { return $this->filter(function($key) use ($map) { return $map->hasKey($key); }); } /** * Returns the result of removing all keys from the current instance that * are present in a given map. * * @param Map $map The map containing the keys to exclude. * * @return Map The result of removing all keys from the current instance * that are present in a given map. * * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function diff(Map $map): Map { return $this->filter(function($key) use ($map) { return ! $map->hasKey($key); }); } /** * Determines whether two keys are equal. * * @param mixed $a * @param mixed $b * * @psalm-param TKey $a * @psalm-param TKey $b */ private function keysAreEqual($a, $b): bool { if (is_object($a) && $a instanceof Hashable) { return get_class($a) === get_class($b) && $a->equals($b); } return $a === $b; } /** * Attempts to look up a key in the table. * * @param $key * * @return Pair|null * * @psalm-return Pair|null */ private function lookupKey($key) { foreach ($this->pairs as $pair) { if ($this->keysAreEqual($pair->key, $key)) { return $pair; } } } /** * Attempts to look up a value in the table. * * @param $value * * @return Pair|null * * @psalm-return Pair|null */ private function lookupValue($value) { foreach ($this->pairs as $pair) { if ($pair->value === $value) { return $pair; } } } /** * Returns whether an association a given key exists. * * @param mixed $key * * @psalm-param TKey $key */ public function hasKey($key): bool { return $this->lookupKey($key) !== null; } /** * Returns whether an association for a given value exists. * * @param mixed $value * * @psalm-param TValue $value */ public function hasValue($value): bool { return $this->lookupValue($value) !== null; } /** * @inheritDoc */ public function count(): int { return count($this->pairs); } /** * Returns a new map containing only the values for which a predicate * returns true. A boolean test will be used if a predicate is not provided. * * @param callable|null $callback Accepts a key and a value, and returns: * true : include the value, * false: skip the value. * * @return Map * * @psalm-param (callable(TKey, TValue): bool)|null $callback * @psalm-return Map */ public function filter(callable $callback = null): Map { $filtered = new self(); foreach ($this as $key => $value) { if ($callback ? $callback($key, $value) : $value) { $filtered->put($key, $value); } } return $filtered; } /** * Returns the value associated with a key, or an optional default if the * key is not associated with a value. * * @param mixed $key * @param mixed $default * * @return mixed The associated value or fallback default if provided. * * @throws OutOfBoundsException if no default was provided and the key is * not associated with a value. * * @template TDefault * @psalm-param TKey $key * @psalm-param TDefault $default * @psalm-return TValue|TDefault */ public function get($key, $default = null) { if (($pair = $this->lookupKey($key))) { return $pair->value; } // Check if a default was provided. if (func_num_args() === 1) { throw new OutOfBoundsException(); } return $default; } /** * Returns a set of all the keys in the map. * * @return Set * * @psalm-return Set */ public function keys(): Set { $key = function($pair) { return $pair->key; }; return new Set(array_map($key, $this->pairs)); } /** * Returns a new map using the results of applying a callback to each value. * * The keys will be equal in both maps. * * @param callable $callback Accepts two arguments: key and value, should * return what the updated value will be. * * @return Map * * @template TNewValue * @psalm-param callable(TKey, TValue): TNewValue $callback * @psalm-return Map */ public function map(callable $callback): Map { $mapped = new self(); foreach ($this->pairs as $pair) { $mapped->put($pair->key, $callback($pair->key, $pair->value)); } return $mapped; } /** * Returns a sequence of pairs representing all associations. * * @return Sequence * * @psalm-return Sequence> */ public function pairs(): Sequence { $copy = function($pair) { return $pair->copy(); }; return new Vector(array_map($copy, $this->pairs)); } /** * Associates a key with a value, replacing a previous association if there * was one. * * @param mixed $key * @param mixed $value * * @psalm-param TKey $key * @psalm-param TValue $value */ public function put($key, $value) { $pair = $this->lookupKey($key); if ($pair) { $pair->value = $value; } else { $this->checkCapacity(); $this->pairs[] = new Pair($key, $value); } } /** * Creates associations for all keys and corresponding values of either an * array or iterable object. * * @param iterable $values * * @psalm-param iterable $values */ public function putAll(iterable $values) { foreach ($values as $key => $value) { $this->put($key, $value); } } /** * Iteratively reduces the map to a single value using a callback. * * @param callable $callback Accepts the carry, key, and value, and * returns an updated carry value. * * @param mixed|null $initial Optional initial carry value. * * @return mixed The carry value of the final iteration, or the initial * value if the map was empty. * * @template TCarry * @psalm-param callable(TCarry, TKey, TValue): TCarry $callback * @psalm-param TCarry $initial * @psalm-return TCarry */ public function reduce(callable $callback, $initial = null) { $carry = $initial; foreach ($this->pairs as $pair) { $carry = $callback($carry, $pair->key, $pair->value); } return $carry; } /** * Completely removes a pair from the internal array by position. It is * important to remove it from the array and not just use 'unset'. * * @return mixed * * @psalm-return TValue */ private function delete(int $position) { $pair = $this->pairs[$position]; $value = $pair->value; array_splice($this->pairs, $position, 1, null); $this->checkCapacity(); return $value; } /** * Removes a key's association from the map and returns the associated value * or a provided default if provided. * * @param mixed $key * @param mixed $default * * @return mixed The associated value or fallback default if provided. * * @throws \OutOfBoundsException if no default was provided and the key is * not associated with a value. * * @template TDefault * @psalm-param TKey $key * @psalm-param TDefault $default * @psalm-return TValue|TDefault */ public function remove($key, $default = null) { foreach ($this->pairs as $position => $pair) { if ($this->keysAreEqual($pair->key, $key)) { return $this->delete($position); } } // Check if a default was provided if (func_num_args() === 1) { throw new \OutOfBoundsException(); } return $default; } /** * Reverses the map in-place */ public function reverse() { $this->pairs = array_reverse($this->pairs); } /** * Returns a reversed copy of the map. * * @return Map * * @psalm-return Map */ public function reversed(): Map { $reversed = new self(); $reversed->pairs = array_reverse($this->pairs); return $reversed; } /** * Returns a sub-sequence of a given length starting at a specified offset. * * @param int $offset If the offset is non-negative, the map will * start at that offset in the map. If offset is * negative, the map will start that far from the * end. * * @param int|null $length If a length is given and is positive, the * resulting set will have up to that many pairs in * it. If the requested length results in an * overflow, only pairs up to the end of the map * will be included. * * If a length is given and is negative, the map * will stop that many pairs from the end. * * If a length is not provided, the resulting map * will contains all pairs between the offset and * the end of the map. * * @return Map * * @psalm-return Map */ public function slice(int $offset, int $length = null): Map { $map = new self(); if (func_num_args() === 1) { $slice = array_slice($this->pairs, $offset); } else { $slice = array_slice($this->pairs, $offset, $length); } foreach ($slice as $pair) { $map->put($pair->key, $pair->value); } return $map; } /** * Sorts the map in-place, based on an optional callable comparator. * * The map will be sorted by value. * * @param callable|null $comparator Accepts two values to be compared. * * @psalm-param (callable(TValue, TValue): int)|null $comparator */ public function sort(callable $comparator = null) { if ($comparator) { usort($this->pairs, function($a, $b) use ($comparator) { return $comparator($a->value, $b->value); }); } else { usort($this->pairs, function($a, $b) { return $a->value <=> $b->value; }); } } /** * Returns a sorted copy of the map, based on an optional callable * comparator. The map will be sorted by value. * * @param callable|null $comparator Accepts two values to be compared. * * @return Map * * @psalm-param (callable(TValue, TValue): int)|null $comparator * @psalm-return Map */ public function sorted(callable $comparator = null): Map { $copy = $this->copy(); $copy->sort($comparator); return $copy; } /** * Sorts the map in-place, based on an optional callable comparator. * * The map will be sorted by key. * * @param callable|null $comparator Accepts two keys to be compared. * * @psalm-param (callable(TKey, TKey): int)|null $comparator */ public function ksort(callable $comparator = null) { if ($comparator) { usort($this->pairs, function($a, $b) use ($comparator) { return $comparator($a->key, $b->key); }); } else { usort($this->pairs, function($a, $b) { return $a->key <=> $b->key; }); } } /** * Returns a sorted copy of the map, based on an optional callable * comparator. The map will be sorted by key. * * @param callable|null $comparator Accepts two keys to be compared. * * @return Map * * @psalm-param (callable(TKey, TKey): int)|null $comparator * @psalm-return Map */ public function ksorted(callable $comparator = null): Map { $copy = $this->copy(); $copy->ksort($comparator); return $copy; } /** * Returns the sum of all values in the map. * * @return int|float The sum of all the values in the map. */ public function sum() { return $this->values()->sum(); } /** * @inheritDoc */ public function toArray(): array { $array = []; foreach ($this->pairs as $pair) { $array[$pair->key] = $pair->value; } return $array; } /** * Returns a sequence of all the associated values in the Map. * * @return Sequence * * @psalm-return Sequence */ public function values(): Sequence { $value = function($pair) { return $pair->value; }; return new Vector(array_map($value, $this->pairs)); } /** * Creates a new map that contains the pairs of the current instance as well * as the pairs of another map. * * @param Map $map The other map, to combine with the current instance. * * @return Map A new map containing all the pairs of the current * instance as well as another map. * * @template TKey2 * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function union(Map $map): Map { return $this->merge($map); } /** * Creates a new map using keys of either the current instance or of another * map, but not of both. * * @param Map $map * * @return Map A new map containing keys in the current instance as well * as another map, but not in both. * * @template TKey2 * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function xor(Map $map): Map { return $this->merge($map)->filter(function($key) use ($map) { return $this->hasKey($key) ^ $map->hasKey($key); }); } /** * @inheritDoc */ #[\ReturnTypeWillChange] public function getIterator() { foreach ($this->pairs as $pair) { yield $pair->key => $pair->value; } } /** * Returns a representation to be used for var_dump and print_r. * * @psalm-return array> */ public function __debugInfo() { return $this->pairs()->toArray(); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { $this->put($offset, $value); } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function &offsetGet($offset) { $pair = $this->lookupKey($offset); if ($pair) { return $pair->value; } throw new OutOfBoundsException(); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { $this->remove($offset, null); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetExists($offset) { return $this->get($offset, null) !== null; } /** * Returns a representation that can be natively converted to JSON, which is * called when invoking json_encode. * * @return mixed * * @see \JsonSerializable */ #[\ReturnTypeWillChange] public function jsonSerialize() { return (object) $this->toArray(); } } php-ds/src/Hashable.php000064400000001733150364337220010757 0ustar00 */ final class Vector implements Sequence { use Traits\GenericCollection; use Traits\GenericSequence; use Traits\Capacity; public const MIN_CAPACITY = 8; protected function getGrowthFactor(): float { return 1.5; } /** * @return bool whether capacity should be increased. */ protected function shouldIncreaseCapacity(): bool { return count($this) > $this->capacity; } } php-ds/src/Collection.php000064400000002674150364337220011350 0ustar00 */ interface Collection extends \IteratorAggregate, \Countable, \JsonSerializable { /** * Removes all values from the collection. */ public function clear(); /** * Returns the size of the collection. * * @return int */ public function count(): int; /** * Returns a shallow copy of the collection. * * @return static a copy of the collection. * * @psalm-return static */ public function copy(); /** * Returns whether the collection is empty. * * This should be equivalent to a count of zero, but is not required. * Implementations should define what empty means in their own context. */ public function isEmpty(): bool; /** * Returns an array representation of the collection. * * The format of the returned array is implementation-dependent. * Some implementations may throw an exception if an array representation * could not be created. * * @return array */ public function toArray(): array; } php-ds/README.md000064400000002366150364337220007232 0ustar00# Data Structures for PHP [![Build Status](https://github.com/php-ds/polyfill/workflows/CI/badge.svg)](https://github.com/php-ds/polyfill/actions?query=workflow%3A%22CI%22+branch%3Amaster) [![Packagist](https://img.shields.io/packagist/v/php-ds/php-ds.svg)](https://packagist.org/packages/php-ds/php-ds) This is a compatibility polyfill for the [extension](https://github.com/php-ds/extension). You should include this package as a dependency of your project to ensure that your codebase would still be functional in an environment where the extension is not installed. The polyfill will not be loaded if the extension is installed and enabled. ## Install ```bash composer require php-ds/php-ds ``` You can also *require* that the extension be installed using `ext-ds`. ## Test ``` composer install composer test ``` Make sure that the *ds* extension is not enabled, as the polyfill will not be loaded if it is. The test output will indicate whether the extension is active. ## Contributing Please see [CONTRIBUTING](CONTRIBUTING.md) for more information. ### Credits - [Rudi Theunissen](https://github.com/rtheunissen) - [Joe Watkins](https://github.com/krakjoe) ### License The MIT License (MIT). Please see [LICENSE](LICENSE.md) for more information. php-ds/LICENSE000064400000002072150364337220006752 0ustar00The MIT License (MIT) Copyright (c) 2016 Rudi Theunissen Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. php-ds/CONTRIBUTING.md000064400000002146150364337220010200 0ustar00# Contributing Contributions are accepted via [pull requests](https://github.com/php-ds/ext/pulls). If you would like to report a bug, please create an [issue](https://github.com/php-ds/ext/issues) instead. ## Issues - **How to reproduce** - Provide an easy way to reproduce the bug. This makes it easier for others to debug. - **Platform details** - Specify your platform and your PHP version, eg. "PHP 7.0.2 on Ubuntu 14.04 64x". ## Pull Requests - **Add tests** - Your patch won't be accepted if it doesn't have tests where appropriate. - **Document any change in behaviour** - Make sure the README and any other relevant documentation updated. - **One pull request per feature** - If you want to do more than one thing, send multiple pull requests. - **Send coherent history** - Make sure each individual commit in your pull request is meaningful. If you had to make multiple intermediate commits while developing, please squash them before submitting. - **Coding style** - Try to match the style of the rest of the source wherever possible. Your patch won't be accepted if the style is significantly different. php-ds/CHANGELOG.md000064400000001346150364337220007561 0ustar00# Change Log All notable changes to this project will be documented in this file. This project adheres to [Semantic Versioning](http://semver.org/). ## [1.3.0] - 2020-10-13 ### Changed - Implement ArrayAccess consistently ### Fixed - Return types were incorrectly nullable in some cases - Deque capacity was inconsistent with the extension ## [1.2.0] - 2017-08-03 ### Changed - Minor capacity updates ## [1.1.1] - 2016-08-09 ### Fixed - `Stack` and `Queue` array access should throw `OutOfBoundsException`, not `Error`. ### Improved - Added a lot of docblock comments that were missing. ## [1.1.0] - 2016-08-04 ### Added - `Pair::copy` ## [1.0.3] - 2016-08-01 ### Added - `Set::merge` ## [1.0.2] - 2016-07-31 ### Added - `Map::putAll` composer.json000064400000001215150415043230007262 0ustar00{ "name": "php-ds/php-ds", "license": "MIT", "keywords": ["php", "ds", "data structures", "polyfill"], "authors": [ { "name": "Rudi Theunissen", "email": "rudolf.theunissen@gmail.com" } ], "require": { "php": ">=7.0", "ext-json": "*" }, "require-dev": { "php-ds/tests": "^1.3" }, "provide": { "ext-ds": "1.3.0" }, "suggest": { "ext-ds": "to improve performance and reduce memory usage" }, "scripts": { "test": "phpunit" }, "autoload": { "psr-4" : { "Ds\\": "src" } } } tests/bootstrap.php000064400000000134150415043230010427 0ustar00toArray(); } /** * Creates a shallow copy of the collection. * * @return static a shallow copy of the collection. */ public function copy(): self { return new static($this); } /** * Returns an array representation of the collection. * * The format of the returned array is implementation-dependent. Some * implementations may throw an exception if an array representation * could not be created (for example when object are used as keys). * * @return array */ abstract public function toArray(): array; /** * Invoked when calling var_dump. * * @return array */ public function __debugInfo() { return $this->toArray(); } /** * Returns a string representation of the collection, which is invoked when * the collection is converted to a string. */ public function __toString() { return 'object(' . get_class($this) . ')'; } } src/Traits/Capacity.php000064400000006151150415043230011047 0ustar00capacity; } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->capacity = max($capacity, $this->capacity); } /** * @return float the structures growth factor. */ protected function getGrowthFactor(): float { return 2; } /** * @return float to multiply by when decreasing capacity. */ protected function getDecayFactor(): float { return 0.5; } /** * @return float the ratio between size and capacity when capacity should be * decreased. */ protected function getTruncateThreshold(): float { return 0.25; } /** * Checks and adjusts capacity if required. */ protected function checkCapacity() { if ($this->shouldIncreaseCapacity()) { $this->increaseCapacity(); } else { if ($this->shouldDecreaseCapacity()) { $this->decreaseCapacity(); } } } /** * @param int $total */ protected function ensureCapacity(int $total) { if ($total > $this->capacity()) { $this->capacity = max($total, $this->nextCapacity()); } } /** * @return bool whether capacity should be increased. */ protected function shouldIncreaseCapacity(): bool { return $this->count() >= $this->capacity(); } protected function nextCapacity(): int { return (int) ($this->capacity() * $this->getGrowthFactor()); } /** * Called when capacity should be increased to accommodate new values. */ protected function increaseCapacity() { $this->capacity = max( $this->count(), $this->nextCapacity() ); } /** * Called when capacity should be decrease if it drops below a threshold. */ protected function decreaseCapacity() { $this->capacity = max( self::MIN_CAPACITY, (int) ($this->capacity() * $this->getDecayFactor()) ); } /** * @return bool whether capacity should be increased. */ protected function shouldDecreaseCapacity(): bool { return count($this) <= $this->capacity() * $this->getTruncateThreshold(); } } src/Traits/GenericSequence.php000064400000020021150415043230012347 0ustar00 */ private $array = []; /** * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { foreach ($values as $value) { $this->push($value); } $this->capacity = max( $values === null ? 0 : count($values), $this::MIN_CAPACITY ); } /** * @inheritdoc */ public function toArray(): array { return $this->array; } /** * @inheritdoc */ public function apply(callable $callback) { foreach ($this->array as &$value) { $value = $callback($value); } } /** * @inheritdoc */ public function merge($values): Sequence { $copy = $this->copy(); $copy->push(...$values); return $copy; } /** * @inheritdoc */ public function count(): int { return count($this->array); } /** * @inheritDoc */ public function contains(...$values): bool { foreach ($values as $value) { if ($this->find($value) === null) { return false; } } return true; } /** * @inheritDoc */ public function filter(callable $callback = null): Sequence { return new self(array_filter($this->array, $callback ?: 'boolval')); } /** * @inheritDoc */ public function find($value) { $offset = array_search($value, $this->array, true); return $offset === false ? null : $offset; } /** * @inheritDoc */ public function first() { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->array[0]; } /** * @inheritDoc */ public function get(int $index) { if ( ! $this->validIndex($index)) { throw new OutOfRangeException(); } return $this->array[$index]; } /** * @inheritDoc */ public function insert(int $index, ...$values) { if ( ! $this->validIndex($index) && $index !== count($this)) { throw new OutOfRangeException(); } array_splice($this->array, $index, 0, $values); $this->checkCapacity(); } /** * @inheritDoc */ public function join(string $glue = null): string { return implode($glue ?? '', $this->array); } /** * @inheritDoc */ public function last() { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->array[count($this) - 1]; } /** * @inheritDoc */ public function map(callable $callback): Sequence { return new self(array_map($callback, $this->array)); } /** * @inheritDoc */ public function pop() { if ($this->isEmpty()) { throw new UnderflowException(); } $value = array_pop($this->array); $this->checkCapacity(); return $value; } /** * @inheritDoc */ public function push(...$values) { $this->ensureCapacity($this->count() + count($values)); foreach ($values as $value) { $this->array[] = $value; } } /** * @inheritDoc */ public function reduce(callable $callback, $initial = null) { return array_reduce($this->array, $callback, $initial); } /** * @inheritDoc */ public function remove(int $index) { if ( ! $this->validIndex($index)) { throw new OutOfRangeException(); } $value = array_splice($this->array, $index, 1, null)[0]; $this->checkCapacity(); return $value; } /** * @inheritDoc */ public function reverse() { $this->array = array_reverse($this->array); } /** * @inheritDoc */ public function reversed(): Sequence { return new self(array_reverse($this->array)); } /** * Converts negative or large rotations into the minimum positive number * of rotations required to rotate the sequence by a given $r. */ private function normalizeRotations(int $r) { $n = count($this); if ($n < 2) return 0; if ($r < 0) return $n - (abs($r) % $n); return $r % $n; } /** * @inheritDoc */ public function rotate(int $rotations) { for ($r = $this->normalizeRotations($rotations); $r > 0; $r--) { array_push($this->array, array_shift($this->array)); } } /** * @inheritDoc */ public function set(int $index, $value) { if ( ! $this->validIndex($index)) { throw new OutOfRangeException(); } $this->array[$index] = $value; } /** * @inheritDoc */ public function shift() { if ($this->isEmpty()) { throw new UnderflowException(); } $value = array_shift($this->array); $this->checkCapacity(); return $value; } /** * @inheritDoc */ public function slice(int $offset, int $length = null): Sequence { if (func_num_args() === 1) { $length = count($this); } return new self(array_slice($this->array, $offset, $length)); } /** * @inheritDoc */ public function sort(callable $comparator = null) { if ($comparator) { usort($this->array, $comparator); } else { sort($this->array); } } /** * @inheritDoc */ public function sorted(callable $comparator = null): Sequence { $copy = $this->copy(); $copy->sort($comparator); return $copy; } /** * @inheritDoc */ public function sum() { return array_sum($this->array); } /** * @inheritDoc */ public function unshift(...$values) { if ($values) { $this->array = array_merge($values, $this->array); $this->checkCapacity(); } } /** * */ private function validIndex(int $index) { return $index >= 0 && $index < count($this); } /** * */ #[\ReturnTypeWillChange] public function getIterator() { foreach ($this->array as $value) { yield $value; } } /** * @inheritdoc */ public function clear() { $this->array = []; $this->capacity = self::MIN_CAPACITY; } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->push($value); } else { $this->set($offset, $value); } } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function &offsetGet($offset) { if ( ! $this->validIndex($offset)) { throw new OutOfRangeException(); } return $this->array[$offset]; } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { if (is_integer($offset) && $this->validIndex($offset)) { $this->remove($offset); } } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetExists($offset) { return is_integer($offset) && $this->validIndex($offset) && $this->get($offset) !== null; } } src/Traits/SquaredCapacity.php000064400000002714150415043230012375 0ustar00capacity = max($this->square($capacity), $this->capacity); } /** * Called when capacity should be increased to accommodate new values. */ protected function increaseCapacity() { $this->capacity = $this->square( max( count($this) + 1, $this->capacity * $this->getGrowthFactor() ) ); } /** * @param int $total */ protected function ensureCapacity(int $total) { while ($total > $this->capacity()) { $this->increaseCapacity(); } } } src/PriorityQueue.php000064400000016012150415043230010667 0ustar00 */ final class PriorityQueue implements Collection { use Traits\GenericCollection; use Traits\SquaredCapacity; public const MIN_CAPACITY = 8; /** * @var array> */ private $heap = []; /** * @var int */ private $stamp = 0; /** * Creates a new instance. */ public function __construct() { } /** * @inheritDoc */ public function clear() { $this->heap = []; $this->stamp = 0; $this->capacity = self::MIN_CAPACITY; } /** * @inheritDoc */ public function copy(): self { $copy = new PriorityQueue(); $copy->heap = $this->heap; $copy->stamp = $this->stamp; $copy->capacity = $this->capacity; return $copy; } /** * @inheritDoc */ public function count(): int { return count($this->heap); } /** * Returns the value with the highest priority in the priority queue. * * @return mixed * * @throw UnderflowException * * @psalm-return TValue */ public function peek() { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->heap[0]->value; } /** * Returns the index of a node's left leaf. * * @param int $index The index of the node. * * @return int The index of the left leaf. */ private function left(int $index): int { return ($index * 2) + 1; } /** * Returns the index of a node's right leaf. * * @param int $index The index of the node. * * @return int The index of the right leaf. */ private function right(int $index): int { return ($index * 2) + 2; } /** * Returns the index of a node's parent node. * * @param int $index The index of the node. * * @return int The index of the parent. */ private function parent(int $index): int { return (int) (($index - 1) / 2); } /** * Compares two indices of the heap. * * @return int */ private function compare(int $a, int $b) { $x = $this->heap[$a]; $y = $this->heap[$b]; // Compare priority, using insertion stamp as fallback. return ($x->priority <=> $y->priority) ?: ($y->stamp <=> $x->stamp); } /** * Swaps the nodes at two indices of the heap. */ private function swap(int $a, int $b) { $temp = $this->heap[$a]; $this->heap[$a] = $this->heap[$b]; $this->heap[$b] = $temp; } /** * Returns the index of a node's largest leaf node. * * @param int $parent the parent node. * * @return int the index of the node's largest leaf node. */ private function getLargestLeaf(int $parent) { $left = $this->left($parent); $right = $this->right($parent); if ($right < count($this->heap) && $this->compare($left, $right) < 0) { return $right; } return $left; } /** * Starts the process of sifting down a given node index to ensure that * the heap's properties are preserved. */ private function siftDown(int $node) { $last = floor(count($this->heap) / 2); for ($parent = $node; $parent < $last; $parent = $leaf) { // Determine the largest leaf to potentially swap with the parent. $leaf = $this->getLargestLeaf($parent); // Done if the parent is not greater than its largest leaf if ($this->compare($parent, $leaf) > 0) { break; } $this->swap($parent, $leaf); } } /** * Sets the root node and sifts it down the heap. * * @param PriorityNode $node */ private function setRoot(PriorityNode $node) { $this->heap[0] = $node; $this->siftDown(0); } /** * Returns the root node of the heap. * * @return PriorityNode */ private function getRoot(): PriorityNode { return $this->heap[0]; } /** * Returns and removes the value with the highest priority in the queue. * * @return mixed * * @psalm-return TValue */ public function pop() { if ($this->isEmpty()) { throw new UnderflowException(); } // Last leaf of the heap to become the new root. $leaf = array_pop($this->heap); if (empty($this->heap)) { return $leaf->value; } // Cache the current root value to return before replacing with next. $value = $this->getRoot()->value; // Replace the root, then sift down. $this->setRoot($leaf); $this->checkCapacity(); return $value; } /** * Sifts a node up the heap until it's in the right position. */ private function siftUp(int $leaf) { for (; $leaf > 0; $leaf = $parent) { $parent = $this->parent($leaf); // Done when parent priority is greater. if ($this->compare($leaf, $parent) < 0) { break; } $this->swap($parent, $leaf); } } /** * Pushes a value into the queue, with a specified priority. * * @param mixed $value * * @psalm-param TValue $value */ public function push($value, int $priority) { $this->checkCapacity(); // Add new leaf, then sift up to maintain heap, $this->heap[] = new PriorityNode($value, $priority, $this->stamp++); $this->siftUp(count($this->heap) - 1); } /** * @inheritDoc */ public function toArray(): array { $heap = $this->heap; $array = []; while ( ! $this->isEmpty()) { $array[] = $this->pop(); } $this->heap = $heap; return $array; } /** * @inheritDoc */ #[\ReturnTypeWillChange] public function getIterator() { while ( ! $this->isEmpty()) { yield $this->pop(); } } } /** * @internal * * @template TValue */ final class PriorityNode { /** * @var mixed * * @psalm-var TValue */ public $value; /** * @var int */ public $priority; /** * @var int */ public $stamp; /** * @param mixed $value * @param int $priority * @param int $stamp * * @psalm-param TValue $value */ public function __construct($value, int $priority, int $stamp) { $this->value = $value; $this->priority = $priority; $this->stamp = $stamp; } } src/Set.php000064400000031137150415043230006601 0ustar00 */ final class Set implements Collection, \ArrayAccess { use Traits\GenericCollection; public const MIN_CAPACITY = Map::MIN_CAPACITY; /** * @var Map internal map to store the values. * * @psalm-var Map */ private $table; /** * Creates a new set using the values of an array or Traversable object. * The keys of either will not be preserved. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { $this->table = new Map(); foreach ($values as $value) { $this->add($value); } } /** * Adds zero or more values to the set. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function add(...$values) { foreach ($values as $value) { $this->table->put($value, null); } } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->table->allocate($capacity); } /** * Returns the current capacity of the set. */ public function capacity(): int { return $this->table->capacity(); } /** * Clear all elements in the Set */ public function clear() { $this->table->clear(); } /** * Determines whether the set contains all of zero or more values. * * @param mixed ...$values * * @return bool true if at least one value was provided and the set * contains all given values, false otherwise. * * @psalm-param TValue ...$values */ public function contains(...$values): bool { foreach ($values as $value) { if ( ! $this->table->hasKey($value)) { return false; } } return true; } /** * @inheritDoc */ public function copy(): self { return new self($this); } /** * Returns the number of elements in the Stack * * @return int */ public function count(): int { return count($this->table); } /** * Creates a new set using values from this set that aren't in another set. * * Formally: A \ B = {x ∈ A | x ∉ B} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function diff(Set $set): Set { return $this->table->diff($set->table)->keys(); } /** * Creates a new set using values in either this set or in another set, * but not in both. * * Formally: A ⊖ B = {x : x ∈ (A \ B) ∪ (B \ A)} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function xor(Set $set): Set { return $this->table->xor($set->table)->keys(); } /** * Returns a new set containing only the values for which a callback * returns true. A boolean test will be used if a callback is not provided. * * @param callable|null $callback Accepts a value, returns a boolean: * true : include the value, * false: skip the value. * * @return Set * * @psalm-param (callable(TValue): bool)|null $callback * @psalm-return Set */ public function filter(callable $callback = null): Set { return new self(array_filter($this->toArray(), $callback ?: 'boolval')); } /** * Returns the first value in the set. * * @return mixed the first value in the set. * * @psalm-return TValue */ public function first() { return $this->table->first()->key; } /** * Returns the value at a specified position in the set. * * @return mixed|null * * @throws OutOfRangeException * * @psalm-return TValue */ public function get(int $position) { return $this->table->skip($position)->key; } /** * Creates a new set using values common to both this set and another set. * * In other words, returns a copy of this set with all values removed that * aren't in the other set. * * Formally: A ∩ B = {x : x ∈ A ∧ x ∈ B} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function intersect(Set $set): Set { return $this->table->intersect($set->table)->keys(); } /** * @inheritDoc */ public function isEmpty(): bool { return $this->table->isEmpty(); } /** * Joins all values of the set into a string, adding an optional 'glue' * between them. Returns an empty string if the set is empty. * * @param string|null $glue */ public function join(string $glue = null): string { return implode($glue ?? '', $this->toArray()); } /** * Returns the last value in the set. * * @return mixed the last value in the set. * * @psalm-return TValue */ public function last() { return $this->table->last()->key; } /** * Returns a new set using the results of applying a callback to each * value. * * @param callable $callback * * @return Set * * @template TNewValue * @psalm-param callable(TValue): TNewValue $callback * @psalm-return Set */ public function map(callable $callback) { return new self(array_map($callback, $this->toArray())); } /** * Iteratively reduces the set to a single value using a callback. * * @param callable $callback Accepts the carry and current value, and * returns an updated carry value. * * @param mixed|null $initial Optional initial carry value. * * @return mixed The carry value of the final iteration, or the initial * value if the set was empty. * * @template TCarry * @psalm-param callable(TCarry, TValue): TCarry $callback * @psalm-param TCarry $initial * @psalm-return TCarry */ public function reduce(callable $callback, $initial = null) { $carry = $initial; foreach ($this as $value) { $carry = $callback($carry, $value); } return $carry; } /** * Removes zero or more values from the set. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function remove(...$values) { foreach ($values as $value) { $this->table->remove($value, null); } } /** * Reverses the set in-place. */ public function reverse() { $this->table->reverse(); } /** * Returns a reversed copy of the set. * * @return Set * * @psalm-return Set */ public function reversed(): Set { $reversed = $this->copy(); $reversed->table->reverse(); return $reversed; } /** * Returns a subset of a given length starting at a specified offset. * * @param int $offset If the offset is non-negative, the set will start * at that offset in the set. If offset is negative, * the set will start that far from the end. * * @param int $length If a length is given and is positive, the resulting * set will have up to that many values in it. * If the requested length results in an overflow, only * values up to the end of the set will be included. * * If a length is given and is negative, the set * will stop that many values from the end. * * If a length is not provided, the resulting set * will contains all values between the offset and the * end of the set. * * @return Set * * @psalm-return Set */ public function slice(int $offset, int $length = null): Set { $sliced = new self(); $sliced->table = $this->table->slice($offset, $length); return $sliced; } /** * Sorts the set in-place, based on an optional callable comparator. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @psalm-param (callable(TValue, TValue): int)|null $comparator */ public function sort(callable $comparator = null) { $this->table->ksort($comparator); } /** * Returns a sorted copy of the set, based on an optional callable * comparator. Natural ordering will be used if a comparator is not given. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @return Set * * @psalm-param (callable(TValue, TValue): int)|null $comparator * @psalm-return Set */ public function sorted(callable $comparator = null): Set { $sorted = $this->copy(); $sorted->table->ksort($comparator); return $sorted; } /** * Returns the result of adding all given values to the set. * * @param array|\Traversable $values * * @return Set * * @template TValue2 * @psalm-param iterable $values * @psalm-return Set */ public function merge($values): Set { $merged = $this->copy(); foreach ($values as $value) { $merged->add($value); } return $merged; } /** * @inheritDoc */ public function toArray(): array { return iterator_to_array($this); } /** * Returns the sum of all values in the set. * * @return int|float The sum of all the values in the set. */ public function sum() { return array_sum($this->toArray()); } /** * Creates a new set that contains the values of this set as well as the * values of another set. * * Formally: A ∪ B = {x: x ∈ A ∨ x ∈ B} * * @param Set $set * * @return Set * * @template TValue2 * @psalm-param Set $set * @psalm-return Set */ public function union(Set $set): Set { $union = new self(); foreach ($this as $value) { $union->add($value); } foreach ($set as $value) { $union->add($value); } return $union; } /** * Get iterator */ #[\ReturnTypeWillChange] public function getIterator() { foreach ($this->table as $key => $value) { yield $key; } } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->add($value); return; } throw new Error(); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetGet($offset) { return $this->table->skip($offset)->key; } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetExists($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { throw new Error(); } /** * Ensures that the internal table will be cloned too. */ public function __clone() { $this->table = clone $this->table; } } src/Stack.php000064400000007701150415043230007113 0ustar00 */ final class Stack implements Collection, \ArrayAccess { use Traits\GenericCollection; /** * @var Vector internal vector to store values of the stack. * * @psalm-var Vector */ private $vector; /** * Creates an instance using the values of an array or Traversable object. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { $this->vector = new Vector($values); } /** * Clear all elements in the Stack */ public function clear() { $this->vector->clear(); } /** * @inheritdoc */ public function copy(): self { return new self($this->vector); } /** * Returns the number of elements in the Stack */ public function count(): int { return count($this->vector); } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->vector->allocate($capacity); } /** * Returns the current capacity of the stack. */ public function capacity(): int { return $this->vector->capacity(); } /** * Returns the value at the top of the stack without removing it. * * @return mixed * * @throws \UnderflowException if the stack is empty. * * @psalm-return TValue */ public function peek() { return $this->vector->last(); } /** * Returns and removes the value at the top of the stack. * * @return mixed * * @throws \UnderflowException if the stack is empty. * * @psalm-return TValue */ public function pop() { return $this->vector->pop(); } /** * Pushes zero or more values onto the top of the stack. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function push(...$values) { $this->vector->push(...$values); } /** * @inheritDoc */ public function toArray(): array { return array_reverse($this->vector->toArray()); } /** * */ #[\ReturnTypeWillChange] public function getIterator() { while ( ! $this->isEmpty()) { yield $this->pop(); } } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->push($value); } else { throw new Error(); } } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetGet($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetExists($offset) { throw new Error(); } /** * Ensures that the internal vector will be cloned too. */ public function __clone() { $this->vector = clone $this->vector; } } src/Deque.php000064400000001340150415043230007102 0ustar00 */ final class Deque implements Sequence { use Traits\GenericCollection; use Traits\GenericSequence; use Traits\SquaredCapacity; public const MIN_CAPACITY = 8; protected function shouldIncreaseCapacity(): bool { return count($this) >= $this->capacity; } } src/Pair.php000064400000006010150415043230006731 0ustar00key = $key; $this->value = $value; } /** * * @param mixed $name * * @return mixed|null */ public function __isset($name) { if ($name === 'key' || $name === 'value') { return $this->$name !== null; } return false; } /** * This allows unset($pair->key) to not completely remove the property, * but be set to null instead. * * @return void */ public function __unset(string $name) { if ($name === 'key' || $name === 'value') { $this->$name = null; return; } throw new OutOfBoundsException(); } /** * @param mixed $name * * @return mixed|null */ public function &__get($name) { if ($name === 'key' || $name === 'value') { return $this->$name; } throw new OutOfBoundsException(); } /** * @param mixed $name * @param mixed $value * * @return mixed|null */ public function __set($name, $value) { if ($name === 'key' || $name === 'value') { $this->$name = $value; return; } throw new OutOfBoundsException(); } /** * Returns a copy of the Pair * * @psalm-return self */ public function copy(): self { return new self($this->key, $this->value); } /** * Returns a representation to be used for var_dump and print_r. * * @return array * * @psalm-return array{key: TKey, value: TValue} */ public function __debugInfo() { return $this->toArray(); } /** * @inheritDoc * * @psalm-return array{key: TKey, value: TValue} */ public function toArray(): array { return [ 'key' => $this->key, 'value' => $this->value, ]; } /** * @inheritDoc * * @psalm-return array{key: TKey, value: TValue} */ #[\ReturnTypeWillChange] public function jsonSerialize() { return $this->toArray(); } /** * Returns a string representation of the pair. */ public function __toString() { return 'object(' . get_class($this) . ')'; } } src/Sequence.php000064400000023260150415043230007614 0ustar00 */ interface Sequence extends Collection, \ArrayAccess { /** * Ensures that enough memory is allocated for a required capacity. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity); /** * Updates every value in the sequence by applying a callback, using the * return value as the new value. * * @param callable $callback Accepts the value, returns the new value. * * @psalm-param callable(TValue): TValue $callback */ public function apply(callable $callback); /** * Returns the current capacity of the sequence. * * @return int */ public function capacity(): int; /** * Determines whether the sequence contains all of zero or more values. * * @param mixed ...$values * * @return bool true if at least one value was provided and the sequence * contains all given values, false otherwise. * * @psalm-param TValue ...$values */ public function contains(...$values): bool; /** * Returns a new sequence containing only the values for which a callback * returns true. A boolean test will be used if a callback is not provided. * * @param callable|null $callback Accepts a value, returns a boolean result: * true : include the value, * false: skip the value. * * @return Sequence * * @psalm-param (callable(TValue): bool)|null $callback * @psalm-return Sequence */ public function filter(callable $callback = null): Sequence; /** * Returns the index of a given value, or null if it could not be found. * * @param mixed $value * * @return int|null * * @psalm-param TValue $value */ public function find($value); /** * Returns the first value in the sequence. * * @return mixed * * @throws \UnderflowException if the sequence is empty. * * @psalm-return TValue */ public function first(); /** * Returns the value at a given index (position) in the sequence. * * @return mixed * * @throws \OutOfRangeException if the index is not in the range [0, size-1] * * @psalm-return TValue */ public function get(int $index); /** * Inserts zero or more values at a given index. * * Each value after the index will be moved one position to the right. * Values may be inserted at an index equal to the size of the sequence. * * @param mixed ...$values * * @throws \OutOfRangeException if the index is not in the range [0, n] * * @psalm-param TValue ...$values */ public function insert(int $index, ...$values); /** * Joins all values of the sequence into a string, adding an optional 'glue' * between them. Returns an empty string if the sequence is empty. */ public function join(string $glue = null): string; /** * Returns the last value in the sequence. * * @return mixed * * @throws \UnderflowException if the sequence is empty. * * @psalm-return TValue */ public function last(); /** * Returns a new sequence using the results of applying a callback to each * value. * * @param callable $callback * * @return Sequence * * @template TNewValue * @psalm-param callable(TValue): TNewValue $callback * @psalm-return Sequence */ public function map(callable $callback): Sequence; /** * Returns the result of adding all given values to the sequence. * * @param array|\Traversable $values * * @return Sequence * * @template TValue2 * @psalm-param iterable $values * @psalm-return Sequence */ public function merge($values): Sequence; /** * Removes the last value in the sequence, and returns it. * * @return mixed what was the last value in the sequence. * * @throws \UnderflowException if the sequence is empty. * * @psalm-return TValue */ public function pop(); /** * Adds zero or more values to the end of the sequence. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function push(...$values); /** * Iteratively reduces the sequence to a single value using a callback. * * @param callable $callback Accepts the carry and current value, and * returns an updated carry value. * * @param mixed|null $initial Optional initial carry value. * * @return mixed The carry value of the final iteration, or the initial * value if the sequence was empty. * * @template TCarry * @psalm-param callable(TCarry, TValue): TCarry $callback * @psalm-param TCarry $initial * @psalm-return TCarry */ public function reduce(callable $callback, $initial = null); /** * Removes and returns the value at a given index in the sequence. * * @param int $index this index to remove. * * @return mixed the removed value. * * @throws \OutOfRangeException if the index is not in the range [0, size-1] * * @psalm-return TValue */ public function remove(int $index); /** * Reverses the sequence in-place. */ public function reverse(); /** * Returns a reversed copy of the sequence. * * @return Sequence * * @psalm-return Sequence */ public function reversed(); /** * Rotates the sequence by a given number of rotations, which is equivalent * to successive calls to 'shift' and 'push' if the number of rotations is * positive, or 'pop' and 'unshift' if negative. * * @param int $rotations The number of rotations (can be negative). */ public function rotate(int $rotations); /** * Replaces the value at a given index in the sequence with a new value. * * @param mixed $value * * @throws \OutOfRangeException if the index is not in the range [0, size-1] * * @psalm-param TValue $value */ public function set(int $index, $value); /** * Removes and returns the first value in the sequence. * * @return mixed what was the first value in the sequence. * * @throws \UnderflowException if the sequence was empty. * * @psalm-return TValue */ public function shift(); /** * Returns a sub-sequence of a given length starting at a specified index. * * @param int $index If the index is positive, the sequence will start * at that index in the sequence. If index is negative, * the sequence will start that far from the end. * * @param int $length If a length is given and is positive, the resulting * sequence will have up to that many values in it. * If the length results in an overflow, only values * up to the end of the sequence will be included. * * If a length is given and is negative, the sequence * will stop that many values from the end. * * If a length is not provided, the resulting sequence * will contain all values between the index and the * end of the sequence. * * @return Sequence * * @psalm-return Sequence */ public function slice(int $index, int $length = null): Sequence; /** * Sorts the sequence in-place, based on an optional callable comparator. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @psalm-param (callable(TValue, TValue): int)|null $comparator */ public function sort(callable $comparator = null); /** * Returns a sorted copy of the sequence, based on an optional callable * comparator. Natural ordering will be used if a comparator is not given. * * @param callable|null $comparator Accepts two values to be compared. * Should return the result of a <=> b. * * @return Sequence * * @psalm-param (callable(TValue, TValue): int)|null $comparator * @psalm-return Sequence */ public function sorted(callable $comparator = null): Sequence; /** * Returns the sum of all values in the sequence. * * @return int|float The sum of all the values in the sequence. */ public function sum(); /** * @inheritDoc * * @return list */ function toArray(): array; /** * Adds zero or more values to the front of the sequence. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function unshift(...$values); } src/Queue.php000064400000007375150415043230007141 0ustar00 */ final class Queue implements Collection, \ArrayAccess { use Traits\GenericCollection; /** * @var Deque internal deque to store values. * * @psalm-var Deque */ private $deque; /** * Creates an instance using the values of an array or Traversable object. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { $this->deque = new Deque($values); } /** * Ensures that enough memory is allocated for a specified capacity. This * potentially reduces the number of reallocations as the size increases. * * @param int $capacity The number of values for which capacity should be * allocated. Capacity will stay the same if this value * is less than or equal to the current capacity. */ public function allocate(int $capacity) { $this->deque->allocate($capacity); } /** * Returns the current capacity of the queue. */ public function capacity(): int { return $this->deque->capacity(); } /** * @inheritDoc */ public function clear() { $this->deque->clear(); } /** * @inheritDoc */ public function copy(): self { return new self($this->deque); } /** * @inheritDoc */ public function count(): int { return count($this->deque); } /** * Returns the value at the front of the queue without removing it. * * @return mixed * * @psalm-return TValue */ public function peek() { return $this->deque->first(); } /** * Returns and removes the value at the front of the Queue. * * @return mixed * * @psalm-return TValue */ public function pop() { return $this->deque->shift(); } /** * Pushes zero or more values into the back of the queue. * * @param mixed ...$values * * @psalm-param TValue ...$values */ public function push(...$values) { $this->deque->push(...$values); } /** * @inheritDoc */ public function toArray(): array { return $this->deque->toArray(); } /** * Get iterator */ #[\ReturnTypeWillChange] public function getIterator() { while ( ! $this->isEmpty()) { yield $this->pop(); } } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { if ($offset === null) { $this->push($value); } else { throw new Error(); } } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetGet($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { throw new Error(); } /** * @inheritdoc * * @throws Error */ #[\ReturnTypeWillChange] public function offsetExists($offset) { throw new Error(); } /** * Ensures that the internal sequence will be cloned too. */ public function __clone() { $this->deque = clone $this->deque; } } src/Map.php000064400000050566150415043230006572 0ustar00 */ final class Map implements Collection, \ArrayAccess { use Traits\GenericCollection; use Traits\SquaredCapacity; public const MIN_CAPACITY = 8; /** * @var array internal array to store pairs * * @psalm-var array */ private $pairs = []; /** * Creates a new instance. * * @param iterable $values * * @psalm-param iterable $values */ public function __construct(iterable $values = []) { if (func_num_args()) { $this->putAll($values); } } /** * Updates all values by applying a callback function to each value. * * @param callable $callback Accepts two arguments: key and value, should * return what the updated value will be. * * @psalm-param callable(TKey, TValue): TValue $callback */ public function apply(callable $callback) { foreach ($this->pairs as &$pair) { $pair->value = $callback($pair->key, $pair->value); } } /** * @inheritDoc */ public function clear() { $this->pairs = []; $this->capacity = self::MIN_CAPACITY; } /** * Return the first Pair from the Map * * @return Pair * * @throws UnderflowException * * @psalm-return Pair */ public function first(): Pair { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->pairs[0]; } /** * Return the last Pair from the Map * * @return Pair * * @throws UnderflowException * * @psalm-return Pair */ public function last(): Pair { if ($this->isEmpty()) { throw new UnderflowException(); } return $this->pairs[count($this->pairs) - 1]; } /** * Return the pair at a specified position in the Map * * @return Pair * * @throws OutOfRangeException * * @psalm-return Pair */ public function skip(int $position): Pair { if ($position < 0 || $position >= count($this->pairs)) { throw new OutOfRangeException(); } return $this->pairs[$position]->copy(); } /** * Returns the result of associating all keys of a given traversable object * or array with their corresponding values, as well as those of this map. * * @param array|\Traversable $values * * @return Map * * @template TKey2 * @template TValue2 * @psalm-param iterable $values * @psalm-return Map */ public function merge($values): Map { $merged = new self($this); $merged->putAll($values); return $merged; } /** * Creates a new map containing the pairs of the current instance whose keys * are also present in the given map. In other words, returns a copy of the * current map with all keys removed that are not also in the other map. * * @param Map $map The other map. * * @return Map A new map containing the pairs of the current instance * whose keys are also present in the given map. In other * words, returns a copy of the current map with all keys * removed that are not also in the other map. * * @template TKey2 * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function intersect(Map $map): Map { return $this->filter(function($key) use ($map) { return $map->hasKey($key); }); } /** * Returns the result of removing all keys from the current instance that * are present in a given map. * * @param Map $map The map containing the keys to exclude. * * @return Map The result of removing all keys from the current instance * that are present in a given map. * * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function diff(Map $map): Map { return $this->filter(function($key) use ($map) { return ! $map->hasKey($key); }); } /** * Determines whether two keys are equal. * * @param mixed $a * @param mixed $b * * @psalm-param TKey $a * @psalm-param TKey $b */ private function keysAreEqual($a, $b): bool { if (is_object($a) && $a instanceof Hashable) { return get_class($a) === get_class($b) && $a->equals($b); } return $a === $b; } /** * Attempts to look up a key in the table. * * @param $key * * @return Pair|null * * @psalm-return Pair|null */ private function lookupKey($key) { foreach ($this->pairs as $pair) { if ($this->keysAreEqual($pair->key, $key)) { return $pair; } } } /** * Attempts to look up a value in the table. * * @param $value * * @return Pair|null * * @psalm-return Pair|null */ private function lookupValue($value) { foreach ($this->pairs as $pair) { if ($pair->value === $value) { return $pair; } } } /** * Returns whether an association a given key exists. * * @param mixed $key * * @psalm-param TKey $key */ public function hasKey($key): bool { return $this->lookupKey($key) !== null; } /** * Returns whether an association for a given value exists. * * @param mixed $value * * @psalm-param TValue $value */ public function hasValue($value): bool { return $this->lookupValue($value) !== null; } /** * @inheritDoc */ public function count(): int { return count($this->pairs); } /** * Returns a new map containing only the values for which a predicate * returns true. A boolean test will be used if a predicate is not provided. * * @param callable|null $callback Accepts a key and a value, and returns: * true : include the value, * false: skip the value. * * @return Map * * @psalm-param (callable(TKey, TValue): bool)|null $callback * @psalm-return Map */ public function filter(callable $callback = null): Map { $filtered = new self(); foreach ($this as $key => $value) { if ($callback ? $callback($key, $value) : $value) { $filtered->put($key, $value); } } return $filtered; } /** * Returns the value associated with a key, or an optional default if the * key is not associated with a value. * * @param mixed $key * @param mixed $default * * @return mixed The associated value or fallback default if provided. * * @throws OutOfBoundsException if no default was provided and the key is * not associated with a value. * * @template TDefault * @psalm-param TKey $key * @psalm-param TDefault $default * @psalm-return TValue|TDefault */ public function get($key, $default = null) { if (($pair = $this->lookupKey($key))) { return $pair->value; } // Check if a default was provided. if (func_num_args() === 1) { throw new OutOfBoundsException(); } return $default; } /** * Returns a set of all the keys in the map. * * @return Set * * @psalm-return Set */ public function keys(): Set { $key = function($pair) { return $pair->key; }; return new Set(array_map($key, $this->pairs)); } /** * Returns a new map using the results of applying a callback to each value. * * The keys will be equal in both maps. * * @param callable $callback Accepts two arguments: key and value, should * return what the updated value will be. * * @return Map * * @template TNewValue * @psalm-param callable(TKey, TValue): TNewValue $callback * @psalm-return Map */ public function map(callable $callback): Map { $mapped = new self(); foreach ($this->pairs as $pair) { $mapped->put($pair->key, $callback($pair->key, $pair->value)); } return $mapped; } /** * Returns a sequence of pairs representing all associations. * * @return Sequence * * @psalm-return Sequence> */ public function pairs(): Sequence { $copy = function($pair) { return $pair->copy(); }; return new Vector(array_map($copy, $this->pairs)); } /** * Associates a key with a value, replacing a previous association if there * was one. * * @param mixed $key * @param mixed $value * * @psalm-param TKey $key * @psalm-param TValue $value */ public function put($key, $value) { $pair = $this->lookupKey($key); if ($pair) { $pair->value = $value; } else { $this->checkCapacity(); $this->pairs[] = new Pair($key, $value); } } /** * Creates associations for all keys and corresponding values of either an * array or iterable object. * * @param iterable $values * * @psalm-param iterable $values */ public function putAll(iterable $values) { foreach ($values as $key => $value) { $this->put($key, $value); } } /** * Iteratively reduces the map to a single value using a callback. * * @param callable $callback Accepts the carry, key, and value, and * returns an updated carry value. * * @param mixed|null $initial Optional initial carry value. * * @return mixed The carry value of the final iteration, or the initial * value if the map was empty. * * @template TCarry * @psalm-param callable(TCarry, TKey, TValue): TCarry $callback * @psalm-param TCarry $initial * @psalm-return TCarry */ public function reduce(callable $callback, $initial = null) { $carry = $initial; foreach ($this->pairs as $pair) { $carry = $callback($carry, $pair->key, $pair->value); } return $carry; } /** * Completely removes a pair from the internal array by position. It is * important to remove it from the array and not just use 'unset'. * * @return mixed * * @psalm-return TValue */ private function delete(int $position) { $pair = $this->pairs[$position]; $value = $pair->value; array_splice($this->pairs, $position, 1, null); $this->checkCapacity(); return $value; } /** * Removes a key's association from the map and returns the associated value * or a provided default if provided. * * @param mixed $key * @param mixed $default * * @return mixed The associated value or fallback default if provided. * * @throws \OutOfBoundsException if no default was provided and the key is * not associated with a value. * * @template TDefault * @psalm-param TKey $key * @psalm-param TDefault $default * @psalm-return TValue|TDefault */ public function remove($key, $default = null) { foreach ($this->pairs as $position => $pair) { if ($this->keysAreEqual($pair->key, $key)) { return $this->delete($position); } } // Check if a default was provided if (func_num_args() === 1) { throw new \OutOfBoundsException(); } return $default; } /** * Reverses the map in-place */ public function reverse() { $this->pairs = array_reverse($this->pairs); } /** * Returns a reversed copy of the map. * * @return Map * * @psalm-return Map */ public function reversed(): Map { $reversed = new self(); $reversed->pairs = array_reverse($this->pairs); return $reversed; } /** * Returns a sub-sequence of a given length starting at a specified offset. * * @param int $offset If the offset is non-negative, the map will * start at that offset in the map. If offset is * negative, the map will start that far from the * end. * * @param int|null $length If a length is given and is positive, the * resulting set will have up to that many pairs in * it. If the requested length results in an * overflow, only pairs up to the end of the map * will be included. * * If a length is given and is negative, the map * will stop that many pairs from the end. * * If a length is not provided, the resulting map * will contains all pairs between the offset and * the end of the map. * * @return Map * * @psalm-return Map */ public function slice(int $offset, int $length = null): Map { $map = new self(); if (func_num_args() === 1) { $slice = array_slice($this->pairs, $offset); } else { $slice = array_slice($this->pairs, $offset, $length); } foreach ($slice as $pair) { $map->put($pair->key, $pair->value); } return $map; } /** * Sorts the map in-place, based on an optional callable comparator. * * The map will be sorted by value. * * @param callable|null $comparator Accepts two values to be compared. * * @psalm-param (callable(TValue, TValue): int)|null $comparator */ public function sort(callable $comparator = null) { if ($comparator) { usort($this->pairs, function($a, $b) use ($comparator) { return $comparator($a->value, $b->value); }); } else { usort($this->pairs, function($a, $b) { return $a->value <=> $b->value; }); } } /** * Returns a sorted copy of the map, based on an optional callable * comparator. The map will be sorted by value. * * @param callable|null $comparator Accepts two values to be compared. * * @return Map * * @psalm-param (callable(TValue, TValue): int)|null $comparator * @psalm-return Map */ public function sorted(callable $comparator = null): Map { $copy = $this->copy(); $copy->sort($comparator); return $copy; } /** * Sorts the map in-place, based on an optional callable comparator. * * The map will be sorted by key. * * @param callable|null $comparator Accepts two keys to be compared. * * @psalm-param (callable(TKey, TKey): int)|null $comparator */ public function ksort(callable $comparator = null) { if ($comparator) { usort($this->pairs, function($a, $b) use ($comparator) { return $comparator($a->key, $b->key); }); } else { usort($this->pairs, function($a, $b) { return $a->key <=> $b->key; }); } } /** * Returns a sorted copy of the map, based on an optional callable * comparator. The map will be sorted by key. * * @param callable|null $comparator Accepts two keys to be compared. * * @return Map * * @psalm-param (callable(TKey, TKey): int)|null $comparator * @psalm-return Map */ public function ksorted(callable $comparator = null): Map { $copy = $this->copy(); $copy->ksort($comparator); return $copy; } /** * Returns the sum of all values in the map. * * @return int|float The sum of all the values in the map. */ public function sum() { return $this->values()->sum(); } /** * @inheritDoc */ public function toArray(): array { $array = []; foreach ($this->pairs as $pair) { $array[$pair->key] = $pair->value; } return $array; } /** * Returns a sequence of all the associated values in the Map. * * @return Sequence * * @psalm-return Sequence */ public function values(): Sequence { $value = function($pair) { return $pair->value; }; return new Vector(array_map($value, $this->pairs)); } /** * Creates a new map that contains the pairs of the current instance as well * as the pairs of another map. * * @param Map $map The other map, to combine with the current instance. * * @return Map A new map containing all the pairs of the current * instance as well as another map. * * @template TKey2 * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function union(Map $map): Map { return $this->merge($map); } /** * Creates a new map using keys of either the current instance or of another * map, but not of both. * * @param Map $map * * @return Map A new map containing keys in the current instance as well * as another map, but not in both. * * @template TKey2 * @template TValue2 * @psalm-param Map $map * @psalm-return Map */ public function xor(Map $map): Map { return $this->merge($map)->filter(function($key) use ($map) { return $this->hasKey($key) ^ $map->hasKey($key); }); } /** * @inheritDoc */ #[\ReturnTypeWillChange] public function getIterator() { foreach ($this->pairs as $pair) { yield $pair->key => $pair->value; } } /** * Returns a representation to be used for var_dump and print_r. * * @psalm-return array> */ public function __debugInfo() { return $this->pairs()->toArray(); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetSet($offset, $value) { $this->put($offset, $value); } /** * @inheritdoc * * @throws OutOfBoundsException */ #[\ReturnTypeWillChange] public function &offsetGet($offset) { $pair = $this->lookupKey($offset); if ($pair) { return $pair->value; } throw new OutOfBoundsException(); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetUnset($offset) { $this->remove($offset, null); } /** * @inheritdoc */ #[\ReturnTypeWillChange] public function offsetExists($offset) { return $this->get($offset, null) !== null; } /** * Returns a representation that can be natively converted to JSON, which is * called when invoking json_encode. * * @return mixed * * @see \JsonSerializable */ #[\ReturnTypeWillChange] public function jsonSerialize() { return (object) $this->toArray(); } } src/Hashable.php000064400000001733150415043230007554 0ustar00 */ final class Vector implements Sequence { use Traits\GenericCollection; use Traits\GenericSequence; use Traits\Capacity; public const MIN_CAPACITY = 8; protected function getGrowthFactor(): float { return 1.5; } /** * @return bool whether capacity should be increased. */ protected function shouldIncreaseCapacity(): bool { return count($this) > $this->capacity; } } src/Collection.php000064400000002674150415043230010145 0ustar00 */ interface Collection extends \IteratorAggregate, \Countable, \JsonSerializable { /** * Removes all values from the collection. */ public function clear(); /** * Returns the size of the collection. * * @return int */ public function count(): int; /** * Returns a shallow copy of the collection. * * @return static a copy of the collection. * * @psalm-return static */ public function copy(); /** * Returns whether the collection is empty. * * This should be equivalent to a count of zero, but is not required. * Implementations should define what empty means in their own context. */ public function isEmpty(): bool; /** * Returns an array representation of the collection. * * The format of the returned array is implementation-dependent. * Some implementations may throw an exception if an array representation * could not be created. * * @return array */ public function toArray(): array; } README.md000064400000002366150415043230006027 0ustar00# Data Structures for PHP [![Build Status](https://github.com/php-ds/polyfill/workflows/CI/badge.svg)](https://github.com/php-ds/polyfill/actions?query=workflow%3A%22CI%22+branch%3Amaster) [![Packagist](https://img.shields.io/packagist/v/php-ds/php-ds.svg)](https://packagist.org/packages/php-ds/php-ds) This is a compatibility polyfill for the [extension](https://github.com/php-ds/extension). You should include this package as a dependency of your project to ensure that your codebase would still be functional in an environment where the extension is not installed. The polyfill will not be loaded if the extension is installed and enabled. ## Install ```bash composer require php-ds/php-ds ``` You can also *require* that the extension be installed using `ext-ds`. ## Test ``` composer install composer test ``` Make sure that the *ds* extension is not enabled, as the polyfill will not be loaded if it is. The test output will indicate whether the extension is active. ## Contributing Please see [CONTRIBUTING](CONTRIBUTING.md) for more information. ### Credits - [Rudi Theunissen](https://github.com/rtheunissen) - [Joe Watkins](https://github.com/krakjoe) ### License The MIT License (MIT). Please see [LICENSE](LICENSE.md) for more information. LICENSE000064400000002072150415043230005547 0ustar00The MIT License (MIT) Copyright (c) 2016 Rudi Theunissen Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. CONTRIBUTING.md000064400000002146150415043230006775 0ustar00# Contributing Contributions are accepted via [pull requests](https://github.com/php-ds/ext/pulls). If you would like to report a bug, please create an [issue](https://github.com/php-ds/ext/issues) instead. ## Issues - **How to reproduce** - Provide an easy way to reproduce the bug. This makes it easier for others to debug. - **Platform details** - Specify your platform and your PHP version, eg. "PHP 7.0.2 on Ubuntu 14.04 64x". ## Pull Requests - **Add tests** - Your patch won't be accepted if it doesn't have tests where appropriate. - **Document any change in behaviour** - Make sure the README and any other relevant documentation updated. - **One pull request per feature** - If you want to do more than one thing, send multiple pull requests. - **Send coherent history** - Make sure each individual commit in your pull request is meaningful. If you had to make multiple intermediate commits while developing, please squash them before submitting. - **Coding style** - Try to match the style of the rest of the source wherever possible. Your patch won't be accepted if the style is significantly different. CHANGELOG.md000064400000001346150415043230006356 0ustar00# Change Log All notable changes to this project will be documented in this file. This project adheres to [Semantic Versioning](http://semver.org/). ## [1.3.0] - 2020-10-13 ### Changed - Implement ArrayAccess consistently ### Fixed - Return types were incorrectly nullable in some cases - Deque capacity was inconsistent with the extension ## [1.2.0] - 2017-08-03 ### Changed - Minor capacity updates ## [1.1.1] - 2016-08-09 ### Fixed - `Stack` and `Queue` array access should throw `OutOfBoundsException`, not `Error`. ### Improved - Added a lot of docblock comments that were missing. ## [1.1.0] - 2016-08-04 ### Added - `Pair::copy` ## [1.0.3] - 2016-08-01 ### Added - `Set::merge` ## [1.0.2] - 2016-07-31 ### Added - `Map::putAll`