1<?php
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime\Utils;
6
7use Antlr\Antlr4\Runtime\Comparison\DefaultEquivalence;
8use Antlr\Antlr4\Runtime\Comparison\Equatable;
9use Antlr\Antlr4\Runtime\Comparison\Equivalence;
10use Antlr\Antlr4\Runtime\Comparison\Hashable;
11
12final class Map implements Equatable, \Countable, \IteratorAggregate
13{
14    /** @var array<int, array<array<Hashable, mixed>>> */
15    private $table = [];
16
17    /** @var int */
18    private $size = 0;
19
20    /** @var Equivalence */
21    private $equivalence;
22
23    public function __construct(?Equivalence $equivalence = null)
24    {
25        $this->equivalence = $equivalence ?? new DefaultEquivalence();
26    }
27
28    public function count() : int
29    {
30        return $this->size;
31    }
32
33    public function contains(Hashable $key) : bool
34    {
35        $hash = $this->equivalence->hash($key);
36
37        if (!isset($this->table[$hash])) {
38            return false;
39        }
40
41        foreach ($this->table[$hash] as [$entryKey]) {
42            if ($this->equivalence->equivalent($key, $entryKey)) {
43                return true;
44            }
45        }
46
47        return false;
48    }
49
50    /**
51     * @return mixed
52     */
53    public function get(Hashable $key)
54    {
55        $hash = $this->equivalence->hash($key);
56
57        if (!isset($this->table[$hash])) {
58            return null;
59        }
60
61        foreach ($this->table[$hash] as [$entryKey, $entryValue]) {
62            if ($this->equivalence->equivalent($key, $entryKey)) {
63                return $entryValue;
64            }
65        }
66
67        return null;
68    }
69
70    /**
71     * @param mixed $value
72     */
73    public function put(Hashable $key, $value) : void
74    {
75        $hash = $this->equivalence->hash($key);
76
77        if (!isset($this->table[$hash])) {
78            $this->table[$hash] = [];
79        }
80
81        foreach ($this->table[$hash] as $index => [$entryKey]) {
82            if ($this->equivalence->equivalent($key, $entryKey)) {
83                $this->table[$hash][$index] = [$key, $value];
84
85                return;
86            }
87        }
88
89        $this->table[$hash][] = [$key, $value];
90
91        $this->size++;
92    }
93
94    public function remove(Hashable $key) : void
95    {
96        $hash = $this->equivalence->hash($key);
97
98        if (!isset($this->table[$hash])) {
99            return;
100        }
101
102        foreach ($this->table[$hash] as $index => [$entryKey]) {
103            if (!$this->equivalence->equivalent($key, $entryKey)) {
104                continue;
105            }
106
107            unset($this->table[$hash][$index]);
108
109            if (\count($this->table[$hash]) === 0) {
110                unset($this->table[$hash]);
111            }
112
113            $this->size--;
114
115            return;
116        }
117    }
118
119    public function equals(object $other) : bool
120    {
121        if ($this === $other) {
122            return true;
123        }
124
125        if (!$other instanceof self
126            || $this->size !== $other->size
127            || !$this->equivalence->equals($other->equivalence)) {
128            return false;
129        }
130
131        foreach ($this->table as $hash => $bucket) {
132            if (!isset($other->table[$hash]) || \count($bucket) !== \count($other->table[$hash])) {
133                return false;
134            }
135
136            $otherBucket = $other->table[$hash];
137
138            foreach ($bucket as $index => [$key, $value]) {
139                [$otherKey, $otherValue] = $otherBucket[$index];
140
141                if (!$this->equivalence->equivalent($key, $otherKey)
142                    || !self::isEqual($value, $otherValue)) {
143                    return false;
144                }
145            }
146        }
147
148        return true;
149    }
150
151    /**
152     * @return array<Hashable>
153     */
154    public function getKeys() : array
155    {
156        $values = [];
157        foreach ($this->table as $bucket) {
158            foreach ($bucket as [$key]) {
159                $values[] = $key;
160            }
161        }
162
163        return $values;
164    }
165
166    /**
167     * @return array<mixed>
168     */
169    public function getValues() : array
170    {
171        $values = [];
172        foreach ($this->table as $bucket) {
173            foreach ($bucket as [, $value]) {
174                $values[] = $value;
175            }
176        }
177
178        return $values;
179    }
180
181    public function getIterator() : \Iterator
182    {
183        foreach ($this->table as $bucket) {
184            foreach ($bucket as [$key, $value]) {
185                yield $key => $value;
186            }
187        }
188    }
189
190    private static function isEqual($left, $right) : bool
191    {
192        if ($left instanceof Equatable && $right instanceof Equatable) {
193            return $left->equals($right);
194        }
195
196        return $left === $right;
197    }
198}
199