OrderedSet.pop() with a non-default index breaks the contract

[rspeer]

>>> from ordered_set import OrderedSet
>>> a = OrderedSet(["a", "b", "c"])
>>> a.index("b")
1
>>> a.pop(0)
'a'
>>> a.index("b")
1
>>> a[1]
'c'

This was revealed by looking into #79. pop() would need to rebuild the mapping in place, like discard() does. Its current behavior, which only works for index=-1, would be an optimization.

[aranega]

Hi @rspeer,

Thanks a lot for your library, it's really really handy! Regarding this point, I implemented some patch in my project to deal with pop/insert and item assignation without slices.

https://github.com/pyecore/pyecore/blob/master/pyecore/ordered_set_patch.py

It's probably not perfect and a little bit naïve implementation, but perhaps it could help.

[whpeeters]

The below behavior of OrderedSet is related to this issue.

from ordered_set import OrderedSet
oset = OrderedSet(['A', 'B', 'C'])
print(oset)         # -> OrderedSet(['A', 'B', 'C'])
oset.pop(0)         # -> 'A'
print(oset)         # -> OrderedSet(['B', 'C'])
oset.discard('B')   # -> None
print(oset)         # -> OrderedSet(['B'])   ???!!!

@rspeer Could I help somehow to have this fixed at PyPI? I have no experience with building PyPI packages, but I think OrderedSet is sufficiently beautiful and important to be upgraded....

I saw pull request #84, which proposes a rebuild of self.map in the def pop(self, index) code block. I think that looks good. Maybe another solution could be to replicate the in-place-solution that is already present in the def discard(self, key) code block. The solution for def pop(self, index=-1) would then become:

def pop(self, index=-1) -> T:
    """
    Remove and return item at index (default last), updating
    self.map accordingly.

    Raises KeyError if the set is empty.
    Raises IndexError if index is out of range.

    Example:
        >>> oset = OrderedSet([1, 2, 3])
        >>> oset.pop()
        3
    """
    if not self.items:
        raise KeyError("Set is empty")

    elem = self.items[index]
    del self.items[index]
    del self.map[elem]
    if index >= 0:
        for k, v in self.map.items():
            if v >= index:
                self.map[k] = v - 1
    return elem