Closed ladvoc closed 1 week ago
In a standard Dictionary, Keys and Values share the same indices. That is, as long as the dictionary is not mutated and the indices remain stable, index i corresponds to the same element regardless if accessed from keys or values
I'm not certain that this statement is true. See this from the docs:
The order of key-value pairs in a dictionary is stable between mutations but is otherwise unpredictable.
A dictionary’s indices stay valid across additions to the dictionary as long as the dictionary has enough capacity to store the added values without allocating more buffer. When a dictionary outgrows its buffer, existing indices may be invalidated without any notification. https://developer.apple.com/documentation/swift/dictionary#Iterating-Over-the-Contents-of-a-Dictionary
In any case, perhaps it does make sense to use _ltr
for RightValues
. If so, that would mean that we don't have to worry about RightValues
and LeftValues
being out of sync or having mismatched order pairs.
However, I'm not sure if that could have any negative performance implications for certain use cases. But all current tests are passing with this PR.
This is probably good to go, but I think we should add more test coverage.
I added some test coverage. For this. It looks like I don't have permission to push my test coverage changes directly to this PR. I can PR my added tests after we merge this PR. This PR looks good to go.
👍🏼
You are right, my explanation implies that the indices get invalidated on each mutation which doesn’t always happen. But in any case, while the indices are valid, a given index should refer to the same left-right pair.
I will go ahead and merge this now. I also agree more testing is needed—especially performance testing; I will revise issue #4 to track this.
I noticed something I overlooked when I first implemented
LeftValues
andRightValues
. In a standardDictionary
,Keys
andValues
share the same indices. That is, as long as the dictionary is not mutated and the indices remain stable, index $i$ corresponds to the same element regardless if accessed fromkeys
orvalues
:This is the expected behavior for index-based access in a
Dictionary
. However,BijectiveDictionary
's current implementation has a bug. The reason the docs mention that order is not guaranteed forleftValues
andrightValues
is becauseLeftValues
uses_ltr
andRightValues
uses_rtl
. However, since_rtl
is a separate dictionary, it has different indices. This means index $i$ refers to a different element inleftValues
andrightValues
. This behavior is unexpected and is not consistent withDictionary
.Taking another look at this, there is no reason
RightValues
can’t also use_ltr
; this pull request modifiesRightValues
accordingly.