```/* <![CDATA[ */
2
3declare(strict_types=1);
4
5namespace Antlr\Antlr4\Runtime;
6
7use Antlr\Antlr4\Runtime\Comparison\Equality;
8use Antlr\Antlr4\Runtime\Comparison\Equatable;
9use Antlr\Antlr4\Runtime\Utils\StringUtils;
10
11/**
12 * This class implements the {@see IntSet} backed by a sorted array of
13 * non-overlapping intervals. It is particularly efficient for representing
14 * large collections of numbers, where the majority of elements appear as part
15 * of a sequential range of numbers that are all part of the set. For example,
16 * the set { 1, 2, 3, 4, 7, 8 } may be represented as { [1, 4], [7, 8] }.
17 *
18 * This class is able to represent sets containing any combination of values in
19 * the range {@see Integer::MIN_VALUE} to {@see Integer::MAX_VALUE}
20 * (inclusive).
21 */
22final class IntervalSet implements Equatable
23{
24    /** @var array<Interval> */
25    protected \$intervals = [];
26
27    /** @var bool */
29
30    /**
31     * Create a set with a single element, el.
32     */
33    public static function fromInt(int \$number) : self
34    {
35        \$set = new self();
36
38
39        return \$set;
40    }
41
42    /**
43     * Create a set with all ints within range [start..end] (inclusive).
44     */
45    public static function fromRange(int \$start, int \$end) : self
46    {
47        \$set = new self();
48
50
51        return \$set;
52    }
53
54    public function complement(IntervalSet \$set) : ?self
55    {
56        if (\$set->isNull()) {
57            return null;
58        }
59
60        return \$set->subtract(\$this);
61    }
62
63    public function subtract(IntervalSet \$set) : self
64    {
65        if (\$set->isNull()) {
66            return \$this;
67        }
68
69        return self::subtractSets(\$this, \$set);
70    }
71
72    public function orSet(IntervalSet \$other) : self
73    {
74        \$result = new self();
75
78
79        return \$result;
80    }
81
82    /**
83     * Compute the set difference between two interval sets. The specific
84     * operation is `left - right`. If either of the input sets is `null`,
85     * it is treated as though it was an empty set.
86     */
87    public static function subtractSets(IntervalSet \$left, IntervalSet \$right) : self
88    {
89        if (\$left->isNull()) {
90            return new self();
91        }
92
93        if (\$right->isNull()) {
94            // right set has no elements; just return the copy of the current set
95            return \$left;
96        }
97
98        \$result = \$left;
99        \$resultI = 0;
100        \$rightI = 0;
101        while (\$resultI < \count(\$result->intervals) && \$rightI < \count(\$right->intervals)) {
102            \$resultInterval = \$result->intervals[\$resultI];
103            \$rightInterval = \$right->intervals[\$rightI];
104
105            // operation: (resultInterval - rightInterval) and update indexes
106
107            if (\$rightInterval->stop < \$resultInterval->start) {
108                \$rightI++;
109
110                continue;
111            }
112
113            if (\$rightInterval->start > \$resultInterval->stop) {
114                \$resultI++;
115
116                continue;
117            }
118
119            \$beforeCurrent = null;
120            \$afterCurrent = null;
121            if (\$rightInterval->start > \$resultInterval->start) {
122                \$beforeCurrent = new Interval(\$resultInterval->start, \$rightInterval->start - 1);
123            }
124
125            if (\$rightInterval->stop < \$resultInterval->stop) {
126                \$afterCurrent = new Interval(\$rightInterval->stop + 1, \$resultInterval->stop);
127            }
128
129            if (\$beforeCurrent !== null) {
130                if (\$afterCurrent !== null) {
131                    // split the current interval into two
132                    \$result->intervals[\$resultI] = \$beforeCurrent;
133                    \$result->intervals[\$resultI + 1] = \$afterCurrent;
134                    \$resultI++;
135                    \$rightI++;
136
137                    continue;
138                }
139
140                // replace the current interval
141                \$result->intervals[\$resultI] = \$beforeCurrent;
142                \$resultI++;
143                continue;
144            }
145
146            if (\$afterCurrent !== null) {
147                // replace the current interval
148                \$result->intervals[\$resultI] = \$afterCurrent;
149                \$rightI++;
150
151                continue;
152            }
153
154            // remove the current interval (thus no need to increment resultI)
155            \array_splice(\$result->intervals, \$resultI, 1);
156
157            continue;
158        }
159
160        // If rightI reached right.intervals.size(), no more intervals to subtract from result.
161        // If resultI reached result.intervals.size(), we would be subtracting from an empty set.
162        // Either way, we are done.
163        return \$result;
164    }
165
166    public function isReadOnly() : bool
167    {
169    }
170
172    {
174    }
175
176    public function first() : int
177    {
178        if (\$this->intervals === null || \count(\$this->intervals) === 0) {
180        }
181
182        return \$this->intervals[0]->start;
183    }
184
185    public function addOne(int \$value) : void
186    {
188    }
189
190    public function addRange(int \$left, int \$right) : void
191    {
193    }
194
196    {
198            throw new \InvalidArgumentException('Can\'t alter readonly IntervalSet.');
199        }
200
202            return;
203        }
204
205        // find position in list
206        // Use iterators as we modify list in place
207        for (\$i = 0, \$count = \count(\$this->intervals); \$i < \$count; \$i++) {
208            /** @var Interval \$resilt */
209            \$resilt = \$this->intervals[\$i];
210
212                return;
213            }
214
216                // next to each other, make a single larger interval
218                \$this->intervals[\$i] = \$bigger;
219
220                // make sure we didn't just create an interval that
221                // should be merged with next interval in list
222                \$i++;
223                while (\$i < \count(\$this->intervals)) {
224                    \$next = \$this->intervals[\$i];
225
226                    if (!\$bigger->adjacent(\$next) && \$bigger->disjoint(\$next)) {
227                        break;
228                    }
229
230                    // if we bump up against or overlap next, merge
231                    \array_splice(\$this->intervals, \$i, 1); // remove this one
232
233                    \$i--; // move backwards to what we just set
234
235                    \$this->intervals[\$i] = \$bigger->union(\$next); // set to 3 merged ones
236
237                    \$i++; // first call to next after previous duplicates the result
238                }
239
240                return;
241            }
242
244                // insert before r
246
247                return;
248            }
249
250            // if disjoint and after r, a future iteration will handle it
251        }
252
253        // ok, must be after last interval (and disjoint from last interval) just add it
255    }
256
257    public function addSet(IntervalSet \$other) : self
258    {
259        if (\$other->intervals !== null) {
260            foreach (\$other->intervals as \$i) {
262            }
263        }
264
265        return \$this;
266    }
267
268    public function contains(int \$item) : bool
269    {
270        \$count = \count(\$this->intervals);
271        \$left = 0;
272        \$right = \$count - 1;
273        // Binary search for the element in the (sorted, disjoint) array of intervals.
274
275        while (\$left <= \$right) {
276            \$m = \intval(\$left + \$right, 2);
277
278            \$interval = \$this->intervals[\$m];
279            \$start = \$interval->start;
280            \$stop = \$interval->stop;
281
282            if (\$stop < \$item) {
283                \$left = \$m + 1;
284            } elseif (\$start > \$item) {
285                \$right = \$m - 1;
286            } else { // item >= start && item <= stop
287                return true;
288            }
289        }
290
291        return false;
292    }
293
294    public function length() : int
295    {
296        \$length = 0;
297
298        foreach (\$this->intervals as \$i) {
299            \$length += \$i->getLength();
300        }
301
302        return \$length;
303    }
304
305    public function removeOne(int \$v) : void
306    {
307        foreach (\$this->intervals as \$k => \$i) {
308            // intervals is ordered
309            if (\$v < \$i->start) {
310                return;
311            }
312
313            // check for single value range
314            if (\$v === \$i->start && \$v === \$i->stop) {
315                \array_splice(\$this->intervals, \$k, 1);
316
317                return;
318            }
319
320            // check for lower boundary
321            if (\$v === \$i->start) {
322                \$this->intervals[\$k] = new Interval(\$i->start + 1, \$i->stop);
323
324                return;
325            }
326
327            // check for upper boundary
328            if (\$v === \$i->stop - 1) {
329                \$this->intervals[\$k] = new Interval(\$i->start, \$i->stop - 1);
330
331                return;
332            }
333
334            // split existing range
335            if (\$v < \$i->stop - 1) {
336                \$x = new Interval(\$i->start, \$v);
337
338                \$i->start = \$v + 1;
339
340                \array_splice(\$this->intervals, \$k, 0, [\$x]);
341
342                return;
343            }
344        }
345    }
346
347    public function isNull() : bool
348    {
349        return \count(\$this->intervals) === 0;
350    }
351
352    /**
353     * Returns the maximum value contained in the set if not isNull().
354     *
355     * @return int The maximum value contained in the set.
356     *
357     * @throws \RuntimeException If set is empty.
358     */
359    public function getMaxElement() : int
360    {
361        if (\$this->isNull()) {
362            throw new \RuntimeException('The set is empty.');
363        }
364
365        return \$this->intervals[\count(\$this->intervals)-1]->stop;
366    }
367
368    /**
369     * Returns the minimum value contained in the set if not isNull().
370     *
371     * @return int The minimum value contained in the set.
372     *
373     * @throws \RuntimeException If set is empty.
374     */
375    public function getMinElement() : int
376    {
377        if (\$this->isNull()) {
378            throw new \RuntimeException('The set is empty.');
379        }
380
381        return \$this->intervals[0]->start;
382    }
383
384    public function toStringChars(bool \$elemAreChar) : string
385    {
386        if (!\$this->intervals) {
387            return '{}';
388        }
389
390        \$buf = '';
391
392        if (\$this->length() > 1) {
393            \$buf .= '{';
394        }
395
396        \$iter = new \ArrayIterator(\$this->intervals);
397
398        while (\$iter->valid()) {
399            \$interval = \$iter->current();
400            \$iter->next();
401            \$start = \$interval->start;
402            \$stop = \$interval->stop;
403
404            if (\$start === \$stop) {
405                if (\$start === Token::EOF) {
406                    \$buf .= '<EOF>';
407                } elseif (\$elemAreChar) {
408                    \$buf .= '\'' . StringUtils::char(\$start) . '\'';
409                } else {
410                    \$buf .= \$start;
411                }
412            } else {
413                if (\$elemAreChar) {
414                    \$buf .= \sprintf(
415                        '\'%s\'..\'%s\'',
416                        StringUtils::char(\$start),
417                        StringUtils::char(\$stop)
418                    );
419                } else {
420                    \$buf .= \sprintf('%s..%s', \$start, \$stop);
421                }
422            }
423
424            if (\$iter->valid()) {
425                \$buf .= ', ';
426            }
427        }
428
429        if (\$this->length() > 1) {
430            \$buf .= '}';
431        }
432
433        return \$buf;
434    }
435
436    public function toStringVocabulary(Vocabulary \$vocabulary) : string
437    {
438        if (!\$this->intervals) {
439            return '{}';
440        }
441
442        \$buf = '';
443        if (\$this->length() > 1) {
444            \$buf .= '{';
445        }
446
447        \$iterator = new \ArrayIterator(\$this->intervals);
448
449        while (\$iterator->valid()) {
450            \$interval = \$iterator->current();
451            \$iterator->next();
452            \$start = \$interval->start;
453            \$stop = \$interval->stop;
454
455            if (\$start === \$stop) {
456                \$buf .= \$this->elementName(\$vocabulary, \$start);
457            } else {
458                for (\$i = \$start; \$i <= \$stop; \$i++) {
459                    if (\$i > \$start) {
460                        \$buf .= ', ';
461                    }
462
463                    \$buf .= \$this->elementName(\$vocabulary, \$i);
464                }
465            }
466
467            if (\$iterator->valid()) {
468                \$buf .= ', ';
469            }
470        }
471
472        if (\$this->length() > 1) {
473            \$buf .= '}';
474        }
475
476        return \$buf;
477    }
478
479    protected function elementName(Vocabulary \$vocabulary, int \$a) : string
480    {
481        if (\$a === Token::EOF) {
482            return '<EOF>';
483        }
484
485        if (\$a === Token::EPSILON) {
486            return '<EPSILON>';
487        }
488
489        return \$vocabulary->getDisplayName(\$a);
490    }
491
492    public function equals(object \$other) : bool
493    {
494        if (\$this === \$other) {
495            return true;
496        }
497
498        if (!\$other instanceof self) {
499            return false;
500        }
501
503            && Equality::equals(\$this->intervals, \$other->intervals);
504    }
505
506    /**
507     * @return array<int>
508     */
509    public function toArray() : array
510    {
511        \$values = [];
512        foreach (\$this->intervals as \$interval) {
513            \$start = \$interval->start;
514            \$stop = \$interval->stop;
515
516            for (\$value = \$start; \$value <= \$stop; \$value++) {
517                \$values[] = \$value;
518            }
519        }
520
521        return \$values;
522    }
523
524    public function __toString() : string
525    {
526        return \$this->toStringChars(false);
527    }
528}
529```