ItemIdxKey¶
- class iteration_utilities.ItemIdxKey(item, idx, /, key)¶
Helper class that makes it easier and faster to compare two values for stable sorting algorithms supporting key functions.
- Parameters:
- itemany type
The original item.
- idx
int
The position (index) of the item.
- keyany type, optional
If given (even as
None
) this should be the item processed by the key function. If it is set then comparisons will compare the key instead of the item.
Notes
Comparisons involving
ItemIdxKey
have some limitations:Both have to be
ItemIdxKey
instances.The
idx
must be different.
The implementation is roughly like:
_notgiven = object() class ItemIdxKey: def __init__(self, item, idx, key=_notgiven): self.item = item self.idx = idx self.key = key def __lt__(self, other): if type(other) != ItemIdxKey: raise TypeError() if self.key is _notgiven: item1, item2 = self.item, other.item else: item1, item2 = self.key, other.key if self.idx < other.idx: return item1 <= item2 else: return item1 < item2 def __gt__(self, other): if type(other) != ItemIdxKey: raise TypeError() if self.key is _notgiven: item1, item2 = self.item, other.item else: item1, item2 = self.key, other.key if self.idx < other.idx: return item1 >= item2 else: return item1 > item2
Note
The actual C makes the initialization and comparisons several times faster than the above illustrated Python class! But it’s only slightly faster than comparing
tuple
orlist
. If you do not plan to support reverse or key then there is no need to use this class!Warning
You should never insert a
ItemIdxKey
instance asitem
orkey
in anotherItemIdxKey
instance. This would yield wrong results and breaks your computer! (the latter might not be true.)Examples
Stability is one of the distinct features of sorting algorithms. This class aids in supporting those algorithms which allow reverse and key. This means that comparisons require absolute lesser (or greater if reverse) if the
idx
is bigger but only require lesser or equal (or greater or equal) if theidx
is smaller. This class implements exactly these conditions:>>> # Use < for normal sorting. >>> ItemIdxKey(10, 2) < ItemIdxKey(10, 3) True >>> # and > for reverse sorting. >>> ItemIdxKey(10, 2) > ItemIdxKey(10, 3) True
The result may seem surprising but if the
item
(orkey
) is equal then in either normal or reverse sorting the one with the smalleridx
should come first! If theitem
(orkey
) differ they take precedence.>>> ItemIdxKey(10, 2) < ItemIdxKey(11, 3) True >>> ItemIdxKey(10, 2) > ItemIdxKey(11, 3) False
But it compares the
key
instead of theitem
if it’s given:>>> ItemIdxKey(0, 2, 20) < ItemIdxKey(10, 3, 19) False >>> ItemIdxKey(0, 2, 20) > ItemIdxKey(10, 3, 19) True
This allows to sort based on
item
orkey
but always to access theitem
for the value that should be sorted.- __lt__(other)¶
Compare to other
ItemIdxKey
instance.
- __gt__(other)¶
Compare to other
ItemIdxKey
instance.
- item¶
(any type) The item to sort.
- key¶
(any type) The result of a key function applied to the item.