SortedList does not find an element it contains while list does

user_14578331 0
Viewed 101

In a project I am using a SortedContainers.SortedList. In the following pseudo-code, I am getting an assertion error:

assert custom_class in list(sorted_list) # This does not cause an error
assert custom_class in sorted_list # This causes an assertion error

Unfortunately, I couldn't yet create a small runnable example that reproduces the error. custom_class is a class that derives from abc.ABC and sorted_list is a SortedContainers.SortedList. Does anybody have an idea why there could be a difference between the a pure list and a SortedList?

sorted_list.remove() also throws an error because SortedList.bisect_left() doesn't find the element either...

Thanks!

Edit1: The issue seems to be occuring here in __contains__ of SortedList:

    def __contains__(self, value):
        """Return true if `value` is an element of the sorted list.

        ``sl.__contains__(value)`` <==> ``value in sl``

        Runtime complexity: `O(log(n))`

        >>> sl = SortedList([1, 2, 3, 4, 5])
        >>> 3 in sl
        True

        :param value: search for value in sorted list
        :return: true if `value` in sorted list

        """
        _maxes = self._maxes

        if not _maxes:
            return False

        pos = bisect_left(_maxes, value)

        if pos == len(_maxes):
            return False

        _lists = self._lists
        idx = bisect_left(_lists[pos], value) # <- This finds the wrong index (in my case 38 instead of 39)

        return _lists[pos][idx] == value # <- The comparison here consequently leads to a falsey value

Edit2: The problem is that the items at position 38 and 39 are of equal value (i.e. their sorting is arbitrary). This breaks the bisec-logic. Does anybody have a good idea of how to solve this?

sortedcontainers sortedlist python
1 Answers

As jsonharper pointed out in their comment, the problem was that SortedList relies on bisec and therefore requires that all elements are absolutely rigid in their sorting (i.e. if __eq__ is False between to objects, their __lt__ also needs to be different and uniform). I solved this by keeping tracks of how many objects I have created and used the index of creation if the value that I am actually interested in is equal. This is a quite arbitrary approach and could be swapped for any other rigid sorting.

user_145783310
Related