Hi,
I was evaluating this library today for a custom typed generator that I'm developing and I noticed something and I wanted to share what I have in mind.
Current code:
private function ensureNoDuplicateTypes(Type ...$types): void
{
$names = [];
foreach ($types as $type) {
assert($type instanceof ObjectType);
$names[] = $type->className()->qualifiedName();
}
if (count(array_unique($names)) < count($names)) {
throw new RuntimeException(
'An intersection type must not contain duplicate types'
);
}
}
The time complexity for this would be:
foreach
loop: $\mathcal{O}(n)$
- first
count
: $\mathcal{O}(1)$
array_unique
:
- Worst case: $\mathcal{O}(n)$
- Best case: $\Omega(n)$
- second
count
: $\mathcal{O}(1)$
What matter here in this snippet is that, no matter how many groups of duplicates $types
contains, it will always traverse the full array, this is why $\mathcal{O}(n) == \Omega(n)$ in the first case. However, what we are looking for here, is to throw an exception as soon as there is a duplicate.
And here we have two scenarios:
- worst case scenario( $\mathcal{O}$ ): the last item is a duplicate
- best case scenario( $\Omega$ ): the second item is a duplicate
Here's what I propose:
private function ensureNoDuplicateTypes(Type ...$types): void
{
$names = [];
foreach ($types as $type) {
assert($type instanceof ObjectType);
$classQualifiedName = $type->className()->qualifiedName();
$names[] = in_array($classQualifiedName, $names, true)
? throw new RuntimeException('An intersection type must not contain duplicate types')
: $classQualifiedName;
}
}
What I propose is to break the loop as soon as a duplicate is found.
The time complexity for this would be:
foreach
loop: $\mathcal{O}(n)$
in_array
:
- Worst case: $\mathcal{O}(n)$
- Best case: $\mathcal{O}(2)$
- Between best and worst cases: $\mathcal{O}(m)$ with $(m < n)$
What do you think?
Actually I often see such things in PHP here and there and I'm wondering if introducing pull-requests for changing these kind of subtle things make sense.
Do you think it worth submitting a PR ?
Thanks in advance.