[FIXED] SortedList does not find an element it contains while list does

Issue

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?

Solution

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.

Answered By - C Hecht