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