# 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: item : any type The original item. idx : int The position (index) of the item. key : any 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:

The implementation is rougly like:

_notgiven = object()

class ItemIdxKey(object):
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 or list. 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 as item or key in another ItemIdxKey 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 the idx 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 (or key) is equal then in either normal or reverse sorting the one with the smaller idx should come first! If the item (or key) 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 the item 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 or key but always to access the item for the value that should be sorted.

__lt__(other)

Compare to other ItemIdxKey instance.

__gt__(other)

Compare to other ItemIdxKey instance.

idx

(int) The original position of the item.

item

(any type) The item to sort.

key

(any type) The result of a key function applied to the item.