Python 3.13: different sorting #2251
Description
This example from the manual has differences between Python versions. Up to 3.12, the behaviour seems to be identical. However, with Python 3.13, the sorted() built-in behaves differently. This is an example that can be run with an existing shapely release (e.g. shapely 2.0.7). Here is test_sorted.py:
from shapely import Point, Polygon
class Within:
def __init__(self, o):
print(f"init: {o}")
self.o = o
def __lt__(self, other):
print(f"self={self.o} other={other.o}: {self.o.within(other.o)}")
return self.o.within(other.o)
def test_sorted():
a = Point(2, 2)
b = Polygon([[1, 1], [1, 3], [3, 3], [3, 1]])
c = Polygon([[0, 0], [0, 4], [4, 4], [4, 0]])
d = Point(-1, -1)
assert (Within(d) < Within(c)) is False
features = [c, a, d, b, c]
assert [d, c, c, b, a] == sorted(features, key=Within, reverse=True)Running with Python 3.12:
$ pytest test_sorted.py -vv -s
========================================= test session starts ==========================================
platform linux -- Python 3.12.8, pytest-8.3.5, pluggy-1.5.0 -- /tmp/py312/bin/python3
cachedir: .pytest_cache
rootdir: /tmp
collected 1 item
test_sorted.py::test_sorted init: POINT (-1 -1)
init: POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))
self=POINT (-1 -1) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): False
init: POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))
init: POINT (2 2)
init: POINT (-1 -1)
init: POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))
init: POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))
self=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
self=POINT (-1 -1) other=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)): False
self=POINT (-1 -1) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): False
self=POINT (2 2) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
self=POINT (2 2) other=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)): True
self=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
self=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)) other=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)): False
PASSED
========================================== 1 passed in 0.06s ===========================================
Running with Python 3.13:
$ pytest test_sorted.py -vv -s
========================================= test session starts ==========================================
platform linux -- Python 3.13.1, pytest-8.3.5, pluggy-1.5.0 -- /tmp/py313/bin/python3
cachedir: .pytest_cache
rootdir: /tmp
collected 1 item
test_sorted.py::test_sorted init: POINT (-1 -1)
init: POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))
self=POINT (-1 -1) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): False
init: POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))
init: POINT (2 2)
init: POINT (-1 -1)
init: POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))
init: POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))
self=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
self=POINT (-1 -1) other=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)): False
self=POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1)) other=POINT (-1 -1): False
self=POINT (2 2) other=POINT (-1 -1): False
self=POINT (-1 -1) other=POINT (2 2): False
self=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)) other=POINT (2 2): False
self=POINT (2 2) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
self=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
self=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)) other=POINT (2 2): False
self=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)) other=POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0)): True
FAILED
=============================================== FAILURES ===============================================
_____________________________________________ test_sorted ______________________________________________
def test_sorted():
a = Point(2, 2)
b = Polygon([[1, 1], [1, 3], [3, 3], [3, 1]])
c = Polygon([[0, 0], [0, 4], [4, 4], [4, 0]])
d = Point(-1, -1)
assert (Within(d) < Within(c)) is False
features = [c, a, d, b, c]
> assert [d, c, c, b, a] == sorted(features, key=Within, reverse=True)
E assert [<POINT (-1 -1)>, <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>, <POINT (2 2)>] == [<POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POINT (2 2)>, <POINT (-1 -1)>, <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>]
E
E At index 0 diff: <POINT (-1 -1)> != <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>
E
E Full diff:
E [
E + <POINT (-1 -1)>,
E <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>,
E <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>,
E + <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>,
E <POINT (2 2)>,
E - <POINT (-1 -1)>,
E - <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>,
E ]
test_sorted.py:21: AssertionError
======================================= short test summary info ========================================
FAILED test_sorted.py::test_sorted - assert [<POINT (-1 -1)>, <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>, <POINT (2 2)>] == [<POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>, <POINT (2 2)>, <POINT (-1 -1)>, <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>]
At index 0 diff: <POINT (-1 -1)> != <POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>
Full diff:
[
+ <POINT (-1 -1)>,
<POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>,
<POLYGON ((0 0, 0 4, 4 4, 4 0, 0 0))>,
+ <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>,
<POINT (2 2)>,
- <POINT (-1 -1)>,
- <POLYGON ((1 1, 1 3, 3 3, 3 1, 1 1))>,
]
========================================== 1 failed in 0.10s ===========================================
This is a head-scratcher! Help welcome!
To help, here is an illustration of the example:
where a is within b and is within c, and d is outside (disjoint). So a "sorted" order is [a, b, c, d], as is demonstrated in the example.
With my Python 3.13.1 version I'm getting different orderings that don't make any sense:
>>> features = [c, a, d, b, c]
>>> assert [c, c, a, d, b] == sorted(features, key=Within, reverse=True)
>>> assert [a, d, b, c, c] == sorted(features, key=Within)