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:

  • Both have to be ItemIdxKey instances.
  • If the first operand has no key then the item are compared.
  • The idx must be different.
  • only < and > are supported!

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.