Map.php

<?php
namespace Ds;

use OutOfBoundsException;
use OutOfRangeException;
use UnderflowException;

/**
 * A Map is a sequential collection of key-value pairs, almost identical to an
 * array used in a similar context. Keys can be any type, but must be unique.
 *
 * @package Ds
 *
 * @template TKey
 * @template TValue
 * @implements Collection<TKey, TValue>
 * @implements \ArrayAccess<TKey, TValue>
 * @template-use Traits\GenericCollection<TKey, TValue>
 */
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<int, Pair>
     */
    private $pairs = [];

    /**
     * Creates a new instance.
     *
     * @param iterable<mixed, mixed> $values
     *
     * @psalm-param iterable<TKey, TValue> $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<TKey, TValue>
     */
    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<TKey, TValue>
     */
    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<TKey, TValue>
     */
    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<TKey2, TValue2> $values
     * @psalm-return Map<TKey|TKey2, TValue|TValue2>
     */
    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<TKey2, TValue2> $map
     * @psalm-return Map<TKey&TKey2, TValue>
     */
    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<TKey, TValue2> $map
     * @psalm-return Map<TKey, TValue>
     */
    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<TKey, TValue>|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<TKey, TValue>|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<TKey, TValue>
     */
    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<TKey>
     */
    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<TKey, TNewValue>
     */
    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<Pair<TKey, TValue>>
     */
    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<mixed, mixed> $values
     *
     * @psalm-param iterable<TKey, TValue> $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<TKey, TValue>
     */
    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<TKey, TValue>
     */
    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<TKey, TValue>
     */
    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<TKey, TValue>
     */
    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<TValue>
     */
    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<TKey2, TValue2> $map
     * @psalm-return Map<TKey|TKey2, TValue|TValue2>
     */
    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<TKey2, TValue2> $map
     * @psalm-return Map<TKey|TKey2, TValue|TValue2>
     */
    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<Pair<TKey, TValue>>
     */
    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();
    }
}