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:
- PyCharm IDE complains that
CustomSortedKeyListshould 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.
- 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 originallyadddoesn'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