mercredi 9 octobre 2019

Best practice to implement a SortedKeyList that returns idx when adding values to it

Python's sortedcontainers.SortedKeyList has an add method that enables adding one element into the SortedKeyList while preserving the order. Unfortunately the native implementation of add doesn't tell you where (which idx) it's inserting the element, which I need. What would be a nice solution to do this?

For what it's worth, here's my attempt via subclassing and it (kind of) works. I didn't change the internal algorithm, but just catch the idx and return it:

from sortedcontainers import SortedKeyList
from bisect import bisect_left, bisect_right


class CustomSortedKeyList(SortedKeyList):
    def add(self, value):
        """Add `value` to sorted-key list.

        Runtime complexity: `O(log(n))` -- approximate.

        >>> from operator import neg
        >>> skl = SortedKeyList(key=neg)
        >>> skl.add(3)
        >>> skl.add(1)
        >>> skl.add(2)
        >>> skl
        SortedKeyList([3, 2, 1], key=<built-in function neg>)

        :param value: value to add to sorted-key list

        """
        _lists = self._lists
        _keys = self._keys
        _maxes = self._maxes

        key = self._key(value)

        if _maxes:
            pos = bisect_right(_maxes, key)

            if pos == len(_maxes):
                idx = -1
                pos -= 1
                _lists[pos].append(value)
                _keys[pos].append(key)
                _maxes[pos] = key
            else:
                idx = bisect_right(_keys[pos], key)
                _lists[pos].insert(idx, value)
                _keys[pos].insert(idx, key)

            self._expand(pos)
        else:
            idx = 0
            _lists.append([value])
            _keys.append([key])
            _maxes.append(key)

        self._len += 1
        return idx


a = CustomSortedKeyList([1, 3, 4, 5, -2, -3, 5,])
print(a.add(0))
print(a)
"""Output as expected:
2
CustomSortedKeyList([-3, -2, 0, 1, 3, 4, 5, 5], key=<function identity at 0x0000018A1A99CB70>)
"""

Everything is fine except that:

  1. PyCharm IDE complains that CustomSortedKeyList should implement all abstract methods:
Class CustomSortedKeyList must implement all abstract methods less... (Ctrl+F1) 
Inspection info: This inspection detects when not all abstract properties/methods are defined in a subclass

I don't know why PyCharm warns of this, since I'm simply suclassing SortedKeyList. The only explanation I can think of is that SortedKeyList itself doesn't implement all the abstract methods. If so, this cannot be helped.

  1. In my custom class I actually change the return type, and hence the interface of add. Although it seems that there isn't any conflict caused by this change of interface yet (maybe because originally add doesn't return anything anyway), I still find changing the interface not very desirable and should be avoided if possible.

Can anyone help? Thanks!

Aucun commentaire:

Enregistrer un commentaire