Cartesian Index Inequalities

General Usage
1

I’m finding the behaviour of comparison for CartesianIndex(s) very confusing;

e.g.

CartesianIndex(1,1) <= CartesianIndex(2,0) 
false 
CartesianIndex(1,1) <= CartesianIndex(0,2) 
true

I don’t have a good intuitive reason as to why this should be; is there a principle I am missing out on?

2

Looks like lexicographic ordering Lexicographic Order -- from Wolfram MathWorld

1 Like
3

By lexicographic ordering you must get

CartesianIndex(1,1) <= CartesianIndex(2,0) 
true
CartesianIndex(1,1) <= CartesianIndex(0,2) 
false

which is opposite of what Julia is returning.

4

If you want to get technical, lexicographical ordering is a generalized concept, with several variations. Most likely, whatever the ordering you want to call that, it is probably of a lexicographical order type.

5

I think its a little unfortunate that the design has settled on this ordering since most likely use of these comparisons (at least in my experience and with reference to the CartesianIndex examples) is for bounds checking multidimensional algorithms

1 Like
6

Without checking, it looks to me like the behavior is according to the column-major order of Julia arrays. That is, I1 < I2 if in an array A, the element A[I1] comes before the element A[I2] in memory. This is consistent with the behavior you see, although of course there’s not zero-based indexing in Julia. The first example compares the index of an element in column 1 to the index of an element in column 0; the first index comes after the second in memory so it’s not <=. In the second the first index is still in column 1, but the second is in column 2 and so comes later in memory; then the first one is less than the second according to their appearance in memory.

7

I think that this is the traversal order for CartesianIndices, ie column-major. Can be understood as a lexicographic ordering on the reversed indices.

2 Likes
8

It becomes really clear if you print the cartesian and linear indices next to eachother:

julia> A = OffsetArray{Int}(undef, 0:2, 0:1);

julia> LinearIndices(A)
LinearIndices{2,Tuple{Base.Slice{UnitRange{Int64}},Base.Slice{UnitRange{Int64}}}} with indices 0:2×0:1:
 1  4
 2  5
 3  6

julia> CartesianIndices(A)
CartesianIndices{2,Tuple{Base.Slice{UnitRange{Int64}},Base.Slice{UnitRange{Int64}}}} with indices 0:2×0:1:
 CartesianIndex(0, 0)  CartesianIndex(0, 1)
 CartesianIndex(1, 0)  CartesianIndex(1, 1)
 CartesianIndex(2, 0)  CartesianIndex(2, 1)

I’m using OffsetArrays to get 0-based indexing.

1 Like
9

Yes, this is comparing the indices based upon a column-major iteration order assuming the indices are valid (and they very well may be with an offset array).

https://github.com/JuliaLang/julia/pull/16054