Cython-like rich comparisons in Python

With “rich comparisons”, we mean the Python 3 comparisons which are usually implemented in Python using methods like __eq__ and __lt__. Internally in Python, there is only one rich comparison slot tp_richcompare. The actual operator is passed as an integer constant (defined in this module as op_LT, op_LE, op_EQ, op_NE, op_GT, op_GE).

Cython exposes rich comparisons in cdef classes as the __richcmp__ special method. The Sage coercion model also supports rich comparisons this way: for two instances x and y of Element, x._richcmp_(y, op) is called when the user does something like x <= y (possibly after coercion if x and y have different parents).

Various helper functions exist to make it easier to implement rich comparison: the most important one is the richcmp() function. This is analogous to the Python 2 function cmp() but implements rich comparison, with the comparison operator (e.g. op_GE) as third argument. There is also richcmp_not_equal() which is like richcmp() but it is optimized assuming that the compared objects are not equal.

The functions rich_to_bool() and rich_to_bool_sgn() can be used to convert results of cmp() (i.e. -1, 0 or 1) to a boolean True/False for rich comparisons.

AUTHORS:

  • Jeroen Demeyer
sage.structure.richcmp.revop(op)

Return the reverse operation of op.

For example, <= becomes >=, etc.

EXAMPLES:

sage: from sage.structure.richcmp import revop
sage: [revop(i) for i in range(6)]
[4, 5, 2, 3, 0, 1]
sage.structure.richcmp.rich_to_bool(op, c)

Return the corresponding True or False value for a rich comparison, given the result of an old-style comparison.

INPUT:

  • op – a rich comparison operation (e.g. Py_EQ)
  • c – the result of an old-style comparison: -1, 0 or 1.

OUTPUT: 1 or 0 (corresponding to True and False)

See also

rich_to_bool_sgn() if c could be outside the [-1, 0, 1] range.

EXAMPLES:

sage: from sage.structure.richcmp import (rich_to_bool,
....:    op_EQ, op_NE, op_LT, op_LE, op_GT, op_GE)
sage: for op in (op_LT, op_LE, op_EQ, op_NE, op_GT, op_GE):
....:     for c in (-1,0,1):
....:         print(rich_to_bool(op, c))
True False False
True True False
False True False
True False True
False False True
False True True

Indirect tests using integers:

sage: 0 < 5, 5 < 5, 5 < -8
(True, False, False)
sage: 0 <= 5, 5 <= 5, 5 <= -8
(True, True, False)
sage: 0 >= 5, 5 >= 5, 5 >= -8
(False, True, True)
sage: 0 > 5, 5 > 5, 5 > -8
(False, False, True)
sage: 0 == 5, 5 == 5, 5 == -8
(False, True, False)
sage: 0 != 5, 5 != 5, 5 != -8
(True, False, True)
sage.structure.richcmp.rich_to_bool_sgn(op, c)

Same as rich_to_bool, but allow any \(c < 0\) and \(c > 0\) instead of only \(-1\) and \(1\).

Note

This is in particular needed for mpz_cmp().

sage.structure.richcmp.richcmp(x, y, op)

Return the result of the rich comparison of x and y with operator op.

INPUT:

  • x, y – arbitrary Python objects
  • op – comparison operator (one of op_LT`, ``op_LE, op_EQ, op_NE, op_GT, op_GE).

EXAMPLES:

sage: from sage.structure.richcmp import *
sage: richcmp(3, 4, op_LT)
True
sage: richcmp(x, x^2, op_EQ)
x == x^2

The two examples above are completely equivalent to 3 < 4 and x == x^2. For this reason, it only makes sense in practice to call richcmp with a non-constant value for op.

We can write a custom Element class which shows a more realistic example of how to use this:

sage: from sage.structure.element import Element
sage: class MyElement(Element):
....:     def __init__(self, parent, value):
....:         Element.__init__(self, parent)
....:         self.v = value
....:     def _richcmp_(self, other, op):
....:         return richcmp(self.v, other.v, op)
sage: P = Parent()
sage: x = MyElement(P, 3)
sage: y = MyElement(P, 3)
sage: x < y
False
sage: x == y
True
sage: x > y
False
sage.structure.richcmp.richcmp_by_eq_and_lt(eq_attr, lt_attr)

Create a rich comparison method for a partial order, where the order is specified by methods called eq_attr and lt_attr.

INPUT when creating the method:

  • eq_attr – attribute name for equality comparison
  • lt_attr – attribute name for less-than comparison

INPUT when calling the method:

  • self – objects having methods eq_attr and lt_attr
  • other – arbitrary object. If it does have eq_attr and lt_attr methods, these are used for the comparison. Otherwise, the comparison is undefined.
  • op – a rich comparison operation (e.g. op_EQ)

Note

For efficiency, identical objects (when self is other) always compare equal.

Note

The order is partial, so x <= y is implemented as x == y or x < y. It is not required that this is the negation of y < x.

Note

This function is intended to be used as a method _richcmp_ in a class derived from sage.structure.element.Element or a method __richcmp__ in a class using richcmp_method().

EXAMPLES:

sage: from sage.structure.richcmp import richcmp_by_eq_and_lt
sage: from sage.structure.element import Element

sage: class C(Element):
....:     def __init__(self, a, b):
....:         super(C, self).__init__(ZZ)
....:         self.a = a
....:         self.b = b
....:     _richcmp_ = richcmp_by_eq_and_lt("eq", "lt")
....:     def eq(self, other):
....:         return self.a == other.a and self.b == other.b
....:     def lt(self, other):
....:         return self.a < other.a and self.b < other.b

sage: x = C(1,2); y = C(2,1); z = C(3,3)

sage: x == x, x <= x, x == C(1,2), x <= C(1,2)  # indirect doctest
(True, True, True, True)
sage: y == z, y != z
(False, True)

sage: x < y, y < x, x > y, y > x, x <= y, y <= x, x >= y, y >= x
(False, False, False, False, False, False, False, False)
sage: y < z, z < y, y > z, z > y, y <= z, z <= y, y >= z, z >= y
(True, False, False, True, True, False, False, True)
sage: z < x, x < z, z > x, x > z, z <= x, x <= z, z >= x, x >= z
(False, True, True, False, False, True, True, False)

A simple example using richcmp_method:

sage: from sage.structure.richcmp import richcmp_method, richcmp_by_eq_and_lt
sage: @richcmp_method
....: class C(object):
....:     __richcmp__ = richcmp_by_eq_and_lt("_eq", "_lt")
....:     def _eq(self, other):
....:         return True
....:     def _lt(self, other):
....:         return True
sage: a = C(); b = C()
sage: a == b
True
sage: a > b  # Calls b._lt(a)
True
sage: class X(object): pass
sage: x = X()
sage: a == x  # Does not call a._eq(x) because x does not have _eq
False
sage.structure.richcmp.richcmp_item(x, y, op)

This function is meant to implement lexicographic rich comparison of sequences (lists, vectors, polynomials, …). The inputs x and y are corresponding items of such lists which should compared.

INPUT:

  • x, y – arbitrary Python objects. Typically, these are X[i] and Y[i] for sequences X and Y.
  • op – comparison operator (one of op_LT`, ``op_LE, op_EQ, op_NE, op_GT, op_GE)

OUTPUT:

Assuming that x = X[i] and y = Y[i]:

  • if the comparison X {op} Y (where op is the given operation) could not be decided yet (i.e. we should compare the next items in the list): return NotImplemented
  • otherwise, if the comparison X {op} Y could be decided: return x {op} y, which should then also be the result for X {op} Y.

Note

Since x {op} y cannot return NotImplemented, the two cases above are mutually exclusive.

The semantics of the comparison is different from Python lists or tuples in the case that the order is not total. Assume that A and B are lists whose rich comparison is implemented using richcmp_item (as in EXAMPLES below). Then

  • A == B iff A[i] == B[i] for all indices \(i\).
  • A != B iff A[i] != B[i] for some index \(i\).
  • A < B iff A[i] < B[i] for some index \(i\) and for all \(j < i\), A[j] <= B[j].
  • A <= B iff A < B or A[i] <= B[i] for all \(i\).
  • A > B iff A[i] > B[i] for some index \(i\) and for all \(j < i\), A[j] >= B[j].
  • A >= B iff A > B or A[i] >= B[i] for all \(i\).

See below for a detailed description of the exact semantics of richcmp_item in general.

EXAMPLES:

sage: from sage.structure.richcmp import *
sage: @richcmp_method
....: class Listcmp(list):
....:     def __richcmp__(self, other, op):
....:         for i in range(len(self)):  # Assume equal lengths
....:             res = richcmp_item(self[i], other[i], op)
....:             if res is not NotImplemented:
....:                 return res
....:         return rich_to_bool(op, 0)  # Consider the lists to be equal
sage: a = Listcmp([0, 1, 3])
sage: b = Listcmp([0, 2, 1])
sage: a == a
True
sage: a != a
False
sage: a < a
False
sage: a <= a
True
sage: a > a
False
sage: a >= a
True
sage: a == b, b == a
(False, False)
sage: a != b, b != a
(True, True)
sage: a < b, b > a
(True, True)
sage: a <= b, b >= a
(True, True)
sage: a > b, b < a
(False, False)
sage: a >= b, b <= a
(False, False)

The above tests used a list of integers, where the result of comparisons are the same as for Python lists.

If we want to see the difference, we need more general entries in the list. The comparison rules are made to be consistent with setwise operations. If \(A\) and \(B\) are sets, we define A {op} B to be true if a {op} B is true for every \(a\) in \(A\) and \(b\) in \(B\). Interval comparisons are a special case of this. For lists of non-empty(!) sets, we want that [A1, A2] {op} [B1, B2] is true if and only if [a1, a2] {op} [b1, b2] is true for all elements. We verify this:

sage: @richcmp_method
....: class Setcmp(tuple):
....:     def __richcmp__(self, other, op):
....:         return all(richcmp(x, y, op) for x in self for y in other)
sage: sym = {op_EQ: "==", op_NE: "!=", op_LT: "<", op_GT: ">", op_LE: "<=", op_GE: ">="}
sage: for A1 in Set(range(4)).subsets():  # long time
....:     if not A1: continue
....:     for B1 in Set(range(4)).subsets():
....:         if not B1: continue
....:         for A2 in Set(range(4)).subsets():
....:             if not A2: continue
....:             for B2 in Set(range(3)).subsets():
....:                 if not B2: continue
....:                 L1 = Listcmp([Setcmp(A1), Setcmp(A2)])
....:                 L2 = Listcmp([Setcmp(B1), Setcmp(B2)])
....:                 for op in range(6):
....:                     reslist = richcmp(L1, L2, op)
....:                     reselt = all(richcmp([a1, a2], [b1, b2], op) for a1 in A1 for a2 in A2 for b1 in B1 for b2 in B2)
....:                     assert reslist is reselt

EXACT SEMANTICS:

Above, we only described how richcmp_item behaves when it is used to compare sequences. Here, we specify the exact semantics. First of all, recall that the result of richcmp_item(x, y, op) is either NotImplemented or x {op} y.

  • if op is ==: return NotImplemented if x == y. If x == y is false, then return x == y.
  • if op is !=: return NotImplemented if not x != y. If x != y is true, then return x != y.
  • if op is <: return NotImplemented if x == y. If x < y or not x <= y, return x < y. Otherwise (if both x == y and x < y are false but x <= y is true), return NotImplemented.
  • if op is <=: return NotImplemented if x == y. If x < y or not x <= y, return x <= y. Otherwise (if both x == y and x < y are false but x <= y is true), return NotImplemented.
  • the > and >= operators are analogous to < and <=.
sage.structure.richcmp.richcmp_method(cls)

Class decorator to implement rich comparison using the special method __richcmp__ (analogous to Cython) instead of the 6 methods __eq__ and friends.

This changes the class in-place and returns the given class.

EXAMPLES:

sage: from sage.structure.richcmp import *
sage: sym = {op_EQ: "==", op_NE: "!=", op_LT: "<", op_GT: ">", op_LE: "<=", op_GE: ">="}
sage: @richcmp_method
....: class A(str):
....:     def __richcmp__(self, other, op):
....:         print("%s %s %s" % (self, sym[op], other))
sage: A("left") < A("right")
left < right
sage: object() <= A("right")
right >= <object object at ...>

We can call this comparison with the usual Python special methods:

sage: x = A("left"); y = A("right")
sage: x.__eq__(y)
left == right
sage: A.__eq__(x, y)
left == right

Everything still works in subclasses:

sage: class B(A):
....:     pass
sage: x = B("left"); y = B("right")
sage: x != y
left != right
sage: x.__ne__(y)
left != right
sage: B.__ne__(x, y)
left != right

We can override __richcmp__ with standard Python rich comparison methods and conversely:

sage: class C(A):
....:     def __ne__(self, other):
....:         return False
sage: C("left") != C("right")
False
sage: C("left") == C("right")  # Calls __eq__ from class A
left == right

sage: class Base(object):
....:     def __eq__(self, other):
....:         return False
sage: @richcmp_method
....: class Derived(Base):
....:     def __richcmp__(self, other, op):
....:         return True
sage: Derived() == Derived()
True
sage.structure.richcmp.richcmp_not_equal(x, y, op)

Like richcmp(x, y, op) but assuming that \(x\) is not equal to \(y\).

INPUT:

  • op – a rich comparison operation (e.g. Py_EQ)

OUTPUT:

If op is not op_EQ or op_NE, the result of richcmp(x, y, op). If op is op_EQ, return False. If op is op_NE, return True.

This is useful to compare lazily two objects A and B according to 2 (or more) different parameters, say width and height for example. One could use:

return richcmp((A.width(), A.height()), (B.width(), B.height()), op)

but this will compute both width and height in all cases, even if A.width() and B.width() are enough to decide the comparison.

Instead one can do:

wA = A.width()
wB = B.width()
if wA != wB:
    return richcmp_not_equal(wA, wB, op)
return richcmp(A.height(), B.height(), op)

The difference with richcmp is that richcmp_not_equal assumes that its arguments are not equal, which is excluding the case where the comparison cannot be decided so far, without knowing the rest of the parameters.

EXAMPLES:

sage: from sage.structure.richcmp import (richcmp_not_equal,
....:    op_EQ, op_NE, op_LT, op_LE, op_GT, op_GE)
sage: for op in (op_LT, op_LE, op_EQ, op_NE, op_GT, op_GE):
....:     print(richcmp_not_equal(3, 4, op))
True
True
False
True
False
False
sage: for op in (op_LT, op_LE, op_EQ, op_NE, op_GT, op_GE):
....:     print(richcmp_not_equal(5, 4, op))
False
False
False
True
True
True