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
orFalse
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
andFalse
)See also
rich_to_bool_sgn()
ifc
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
andy
with operatorop
.INPUT:
x
,y
– arbitrary Python objectsop
– comparison operator (one ofop_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
andx == x^2
. For this reason, it only makes sense in practice to callrichcmp
with a non-constant value forop
.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
andlt_attr
.INPUT when creating the method:
eq_attr
– attribute name for equality comparisonlt_attr
– attribute name for less-than comparison
INPUT when calling the method:
self
– objects having methodseq_attr
andlt_attr
other
– arbitrary object. If it does haveeq_attr
andlt_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 asx == y or x < y
. It is not required that this is the negation ofy < x
.Note
This function is intended to be used as a method
_richcmp_
in a class derived fromsage.structure.element.Element
or a method__richcmp__
in a class usingrichcmp_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
andy
are corresponding items of such lists which should compared.INPUT:
x
,y
– arbitrary Python objects. Typically, these areX[i]
andY[i]
for sequencesX
andY
.op
– comparison operator (one ofop_LT`, ``op_LE
,op_EQ
,op_NE
,op_GT
,op_GE
)
OUTPUT:
Assuming that
x = X[i]
andy = Y[i]
:if the comparison
X {op} Y
(whereop
is the given operation) could not be decided yet (i.e. we should compare the next items in the list): returnNotImplemented
otherwise, if the comparison
X {op} Y
could be decided: returnx {op} y
, which should then also be the result forX {op} Y
.
Note
Since
x {op} y
cannot returnNotImplemented
, 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
andB
are lists whose rich comparison is implemented usingrichcmp_item
(as in EXAMPLES below). ThenA == B
iffA[i] == B[i]
for all indices \(i\).A != B
iffA[i] != B[i]
for some index \(i\).A < B
iffA[i] < B[i]
for some index \(i\) and for all \(j < i\),A[j] <= B[j]
.A <= B
iffA < B
orA[i] <= B[i]
for all \(i\).A > B
iffA[i] > B[i]
for some index \(i\) and for all \(j < i\),A[j] >= B[j]
.A >= B
iffA > B
orA[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 ifa {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 ofrichcmp_item(x, y, op)
is eitherNotImplemented
orx {op} y
.if
op
is==
: returnNotImplemented
ifx == y
. Ifx == y
is false, then returnx == y
.if
op
is!=
: returnNotImplemented
if notx != y
. Ifx != y
is true, then returnx != y
.if
op
is<
: returnNotImplemented
ifx == y
. Ifx < y
or notx <= y
, returnx < y
. Otherwise (if bothx == y
andx < y
are false butx <= y
is true), returnNotImplemented
.if
op
is<=
: returnNotImplemented
ifx == y
. Ifx < y
or notx <= y
, returnx <= y
. Otherwise (if bothx == y
andx < y
are false butx <= y
is true), returnNotImplemented
.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 notop_EQ
orop_NE
, the result ofrichcmp(x, y, op)
. Ifop
isop_EQ
, returnFalse
. Ifop
isop_NE
, returnTrue
.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 thatrichcmp_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