<?php

/**
 * PHP Data Structures — Zero-Dependency Typed Data Structures
 *
 * A single-file library providing essential data structures for PHP 8.0+.
 * No external dependencies.
 *
 * Classes:
 *   Stack      — LIFO (Last In, First Out)
 *   Queue      — FIFO (First In, First Out)
 *   Collection — Fluent, chainable array wrapper
 *   Set        — Unique-value collection
 *   TypedArray — Type-enforced array
 *   Pair       — Immutable key-value tuple
 *
 * @version 1.0.0
 * @author  Ahmed Habib
 * @license MIT
 */

namespace PhpDataStructures;

// ─── Stack (LIFO) ───────────────────────────────────────────────────────────

class Stack implements \Countable, \IteratorAggregate
{
    private array $items = [];

    public function __construct(array $items = [])
    {
        $this->items = array_values($items);
    }

    /** Push one or more items onto the top of the stack. */
    public function push(mixed ...$values): self
    {
        foreach ($values as $v) {
            $this->items[] = $v;
        }
        return $this;
    }

    /** Remove and return the top item. */
    public function pop(): mixed
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Cannot pop from an empty stack.');
        }
        return array_pop($this->items);
    }

    /** Return the top item without removing it. */
    public function peek(): mixed
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Cannot peek at an empty stack.');
        }
        return end($this->items);
    }

    /** Check if the stack is empty. */
    public function isEmpty(): bool
    {
        return $this->items === [];
    }

    /** Return the number of items. */
    public function size(): int
    {
        return count($this->items);
    }

    /** Remove all items. */
    public function clear(): self
    {
        $this->items = [];
        return $this;
    }

    /** Check if a value exists in the stack. */
    public function contains(mixed $value): bool
    {
        return in_array($value, $this->items, true);
    }

    /** Return all items as an array (top element last). */
    public function toArray(): array
    {
        return $this->items;
    }

    /** Create a new stack from an array. */
    public static function from(array $items): self
    {
        return new self($items);
    }

    public function count(): int
    {
        return $this->size();
    }

    public function getIterator(): \ArrayIterator
    {
        return new \ArrayIterator(array_reverse($this->items));
    }
}

// ─── Queue (FIFO) ───────────────────────────────────────────────────────────

class Queue implements \Countable, \IteratorAggregate
{
    private array $items = [];

    public function __construct(array $items = [])
    {
        $this->items = array_values($items);
    }

    /** Add an item to the back of the queue. */
    public function enqueue(mixed ...$values): self
    {
        foreach ($values as $v) {
            $this->items[] = $v;
        }
        return $this;
    }

    /** Remove and return the front item. */
    public function dequeue(): mixed
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Cannot dequeue from an empty queue.');
        }
        return array_shift($this->items);
    }

    /** Return the front item without removing it. */
    public function front(): mixed
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Cannot peek at an empty queue.');
        }
        return $this->items[0];
    }

    /** Return the back item without removing it. */
    public function back(): mixed
    {
        if ($this->isEmpty()) {
            throw new \UnderflowException('Cannot peek at an empty queue.');
        }
        return end($this->items);
    }

    /** Check if the queue is empty. */
    public function isEmpty(): bool
    {
        return $this->items === [];
    }

    /** Return the number of items. */
    public function size(): int
    {
        return count($this->items);
    }

    /** Remove all items. */
    public function clear(): self
    {
        $this->items = [];
        return $this;
    }

    /** Check if a value exists in the queue. */
    public function contains(mixed $value): bool
    {
        return in_array($value, $this->items, true);
    }

    /** Return all items as an array. */
    public function toArray(): array
    {
        return $this->items;
    }

    /** Create a new queue from an array. */
    public static function from(array $items): self
    {
        return new self($items);
    }

    public function count(): int
    {
        return $this->size();
    }

    public function getIterator(): \ArrayIterator
    {
        return new \ArrayIterator($this->items);
    }
}

// ─── Collection (Fluent Array Wrapper) ──────────────────────────────────────

class Collection implements \Countable, \IteratorAggregate, \JsonSerializable
{
    private array $items;

    public function __construct(array $items = [])
    {
        $this->items = $items;
    }

    /** Create a new collection. */
    public static function of(array $items = []): self
    {
        return new self($items);
    }

    /** Apply a callback to each item and return a new collection. */
    public function map(callable $callback): self
    {
        return new self(array_map($callback, $this->items));
    }

    /** Filter items using a callback and return a new collection. */
    public function filter(?callable $callback = null): self
    {
        return new self(array_values(
            $callback ? array_filter($this->items, $callback) : array_filter($this->items)
        ));
    }

    /** Reduce the collection to a single value. */
    public function reduce(callable $callback, mixed $initial = null): mixed
    {
        return array_reduce($this->items, $callback, $initial);
    }

    /** Execute a callback on each item (no return value). */
    public function each(callable $callback): self
    {
        foreach ($this->items as $key => $item) {
            $callback($item, $key);
        }
        return $this;
    }

    /** Return the first item, or first matching a callback. */
    public function first(?callable $callback = null): mixed
    {
        if ($callback === null) {
            return $this->items === [] ? null : reset($this->items);
        }
        foreach ($this->items as $item) {
            if ($callback($item)) {
                return $item;
            }
        }
        return null;
    }

    /** Return the last item, or last matching a callback. */
    public function last(?callable $callback = null): mixed
    {
        if ($callback === null) {
            return $this->items === [] ? null : end($this->items);
        }
        $result = null;
        foreach ($this->items as $item) {
            if ($callback($item)) {
                $result = $item;
            }
        }
        return $result;
    }

    /** Sort items and return a new collection. */
    public function sort(?callable $callback = null): self
    {
        $items = $this->items;
        $callback ? usort($items, $callback) : sort($items);
        return new self($items);
    }

    /** Reverse the order and return a new collection. */
    public function reverse(): self
    {
        return new self(array_reverse($this->items));
    }

    /** Remove duplicates and return a new collection. */
    public function unique(): self
    {
        return new self(array_values(array_unique($this->items, SORT_REGULAR)));
    }

    /** Split into chunks and return a collection of collections. */
    public function chunk(int $size): self
    {
        return new self(array_map(
            fn(array $chunk) => new self($chunk),
            array_chunk($this->items, $size)
        ));
    }

    /** Flatten nested arrays by one level. */
    public function flatten(): self
    {
        $result = [];
        foreach ($this->items as $item) {
            if (is_array($item)) {
                $result = array_merge($result, $item);
            } elseif ($item instanceof self) {
                $result = array_merge($result, $item->toArray());
            } else {
                $result[] = $item;
            }
        }
        return new self($result);
    }

    /** Extract a single column from items. */
    public function pluck(string $key): self
    {
        return new self(array_map(function ($item) use ($key) {
            if (is_array($item)) {
                return $item[$key] ?? null;
            }
            if (is_object($item)) {
                return $item->$key ?? null;
            }
            return null;
        }, $this->items));
    }

    /** Group items by a key value. */
    public function groupBy(string $key): self
    {
        $groups = [];
        foreach ($this->items as $item) {
            $groupKey = is_array($item) ? ($item[$key] ?? '') : ($item->$key ?? '');
            $groups[$groupKey][] = $item;
        }
        return new self(array_map(fn($g) => new self($g), $groups));
    }

    /** Check if the collection contains a value. */
    public function contains(mixed $value): bool
    {
        return in_array($value, $this->items, true);
    }

    /** Slice a portion of the collection. */
    public function slice(int $offset, ?int $length = null): self
    {
        return new self(array_slice($this->items, $offset, $length));
    }

    /** Take the first N items. */
    public function take(int $count): self
    {
        return $this->slice(0, $count);
    }

    /** Skip the first N items. */
    public function skip(int $count): self
    {
        return $this->slice($count);
    }

    /** Merge another array or collection. */
    public function merge(array|self $items): self
    {
        $other = $items instanceof self ? $items->toArray() : $items;
        return new self(array_merge($this->items, $other));
    }

    /** Get the sum of all items (or a key). */
    public function sum(?string $key = null): int|float
    {
        if ($key === null) {
            return array_sum($this->items);
        }
        return $this->pluck($key)->sum();
    }

    /** Get the average of all items (or a key). */
    public function avg(?string $key = null): int|float
    {
        $count = $this->count();
        return $count > 0 ? $this->sum($key) / $count : 0;
    }

    /** Get the min value. */
    public function min(?string $key = null): mixed
    {
        $items = $key ? $this->pluck($key)->toArray() : $this->items;
        return $items === [] ? null : min($items);
    }

    /** Get the max value. */
    public function max(?string $key = null): mixed
    {
        $items = $key ? $this->pluck($key)->toArray() : $this->items;
        return $items === [] ? null : max($items);
    }

    /** Check if the collection is empty. */
    public function isEmpty(): bool
    {
        return $this->items === [];
    }

    /** Return items as an array. */
    public function toArray(): array
    {
        return $this->items;
    }

    /** Return items as JSON. */
    public function toJson(int $flags = 0): string
    {
        return json_encode($this->items, $flags | JSON_THROW_ON_ERROR);
    }

    public function count(): int
    {
        return count($this->items);
    }

    public function getIterator(): \ArrayIterator
    {
        return new \ArrayIterator($this->items);
    }

    public function jsonSerialize(): array
    {
        return $this->items;
    }
}

// ─── Set (Unique Values) ────────────────────────────────────────────────────

class Set implements \Countable, \IteratorAggregate
{
    private array $items = [];

    public function __construct(array $items = [])
    {
        foreach ($items as $item) {
            $this->add($item);
        }
    }

    /** Add a value to the set (ignored if already present). */
    public function add(mixed $value): self
    {
        $key = $this->hash($value);
        if (!isset($this->items[$key])) {
            $this->items[$key] = $value;
        }
        return $this;
    }

    /** Remove a value from the set. */
    public function remove(mixed $value): self
    {
        unset($this->items[$this->hash($value)]);
        return $this;
    }

    /** Check if the set contains a value. */
    public function has(mixed $value): bool
    {
        return isset($this->items[$this->hash($value)]);
    }

    /** Return the union with another set. */
    public function union(self $other): self
    {
        $result = new self($this->toArray());
        foreach ($other->toArray() as $item) {
            $result->add($item);
        }
        return $result;
    }

    /** Return the intersection with another set. */
    public function intersect(self $other): self
    {
        $result = new self();
        foreach ($this->items as $item) {
            if ($other->has($item)) {
                $result->add($item);
            }
        }
        return $result;
    }

    /** Return the difference (items in this set but not in the other). */
    public function diff(self $other): self
    {
        $result = new self();
        foreach ($this->items as $item) {
            if (!$other->has($item)) {
                $result->add($item);
            }
        }
        return $result;
    }

    /** Check if this set is a subset of another. */
    public function isSubsetOf(self $other): bool
    {
        foreach ($this->items as $item) {
            if (!$other->has($item)) {
                return false;
            }
        }
        return true;
    }

    /** Return the number of items. */
    public function size(): int
    {
        return count($this->items);
    }

    /** Check if the set is empty. */
    public function isEmpty(): bool
    {
        return $this->items === [];
    }

    /** Remove all items. */
    public function clear(): self
    {
        $this->items = [];
        return $this;
    }

    /** Return all items as an indexed array. */
    public function toArray(): array
    {
        return array_values($this->items);
    }

    /** Create a new set from values. */
    public static function from(mixed ...$values): self
    {
        return new self($values);
    }

    public function count(): int
    {
        return $this->size();
    }

    public function getIterator(): \ArrayIterator
    {
        return new \ArrayIterator(array_values($this->items));
    }

    private function hash(mixed $value): string
    {
        if (is_object($value)) {
            return spl_object_hash($value);
        }
        return gettype($value) . ':' . serialize($value);
    }
}

// ─── TypedArray (Type-Enforced Array) ───────────────────────────────────────

class TypedArray implements \Countable, \IteratorAggregate, \ArrayAccess
{
    private array $items = [];
    private string $type;

    /**
     * @param string $type A scalar type (int, float, string, bool) or a fully-qualified class name.
     */
    public function __construct(string $type, array $items = [])
    {
        $this->type = $type;
        foreach ($items as $item) {
            $this->add($item);
        }
    }

    /** Add a value (must match the declared type). */
    public function add(mixed $value): self
    {
        $this->validate($value);
        $this->items[] = $value;
        return $this;
    }

    /** Set a value at a specific index. */
    public function set(int $index, mixed $value): self
    {
        $this->validate($value);
        $this->items[$index] = $value;
        return $this;
    }

    /** Get the value at a specific index. */
    public function get(int $index): mixed
    {
        if (!isset($this->items[$index])) {
            throw new \OutOfRangeException("Index {$index} does not exist.");
        }
        return $this->items[$index];
    }

    /** Remove the value at a specific index. */
    public function remove(int $index): self
    {
        unset($this->items[$index]);
        $this->items = array_values($this->items);
        return $this;
    }

    /** Return the enforced type. */
    public function getType(): string
    {
        return $this->type;
    }

    /** Return the number of items. */
    public function size(): int
    {
        return count($this->items);
    }

    /** Check if the array is empty. */
    public function isEmpty(): bool
    {
        return $this->items === [];
    }

    /** Remove all items. */
    public function clear(): self
    {
        $this->items = [];
        return $this;
    }

    /** Return all items as a plain array. */
    public function toArray(): array
    {
        return $this->items;
    }

    /** Create a new typed array from values. */
    public static function of(string $type, mixed ...$values): self
    {
        return new self($type, $values);
    }

    public function count(): int
    {
        return $this->size();
    }

    public function getIterator(): \ArrayIterator
    {
        return new \ArrayIterator($this->items);
    }

    public function offsetExists(mixed $offset): bool
    {
        return isset($this->items[$offset]);
    }

    public function offsetGet(mixed $offset): mixed
    {
        return $this->items[$offset] ?? null;
    }

    public function offsetSet(mixed $offset, mixed $value): void
    {
        $this->validate($value);
        if ($offset === null) {
            $this->items[] = $value;
        } else {
            $this->items[$offset] = $value;
        }
    }

    public function offsetUnset(mixed $offset): void
    {
        unset($this->items[$offset]);
        $this->items = array_values($this->items);
    }

    private function validate(mixed $value): void
    {
        $valid = match ($this->type) {
            'int', 'integer' => is_int($value),
            'float', 'double' => is_float($value) || is_int($value),
            'string' => is_string($value),
            'bool', 'boolean' => is_bool($value),
            'array' => is_array($value),
            default => $value instanceof $this->type,
        };

        if (!$valid) {
            $actual = get_debug_type($value);
            throw new \InvalidArgumentException(
                "Expected type [{$this->type}], got [{$actual}]."
            );
        }
    }
}

// ─── Pair (Immutable Key-Value Tuple) ───────────────────────────────────────

class Pair implements \JsonSerializable
{
    public function __construct(
        private readonly mixed $key,
        private readonly mixed $value
    ) {}

    /** Get the key. */
    public function key(): mixed
    {
        return $this->key;
    }

    /** Get the value. */
    public function value(): mixed
    {
        return $this->value;
    }

    /** Return a new Pair with a different value. */
    public function withValue(mixed $value): self
    {
        return new self($this->key, $value);
    }

    /** Return a new Pair with a different key. */
    public function withKey(mixed $key): self
    {
        return new self($key, $this->value);
    }

    /** Convert to a [key, value] array. */
    public function toArray(): array
    {
        return [$this->key, $this->value];
    }

    /** Convert to an associative array. */
    public function toAssoc(): array
    {
        return [$this->key => $this->value];
    }

    /** Check equality with another Pair. */
    public function equals(self $other): bool
    {
        return $this->key === $other->key && $this->value === $other->value;
    }

    /** Create a Pair from a [key, value] array. */
    public static function from(array $pair): self
    {
        return new self($pair[0] ?? null, $pair[1] ?? null);
    }

    /** Create a new pair. */
    public static function of(mixed $key, mixed $value): self
    {
        return new self($key, $value);
    }

    public function jsonSerialize(): array
    {
        return ['key' => $this->key, 'value' => $this->value];
    }
}