# Cartesian Index Inequalities

**URL:** <https://discourse.julialang.org/t/cartesian-index-inequalities/19644>\
**Category:** General Usage\
**Created:** [January 15, 2019, 12:48am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644 "2019-01-15T00:48:05Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![jbmuir](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jbmuir/32/4798_2.png) [@jbmuir](https://discourse.julialang.org/u/jbmuir)\
**Post date:** [January 15, 2019, 12:48am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/1 "2019-01-15T00:48:05Z")

</div>

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

e.g.

```julia
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?

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [January 15, 2019, 12:52am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/2 "2019-01-15T00:52:35Z")

</div>

Looks like lexicographic ordering [Lexicographic Order -- from Wolfram MathWorld](http://mathworld.wolfram.com/LexicographicOrder.html)

---

<div class="post-metadata">

**Author:** ![Azamat](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/azamat/32/6892_2.png) [@Azamat](https://discourse.julialang.org/u/Azamat)\
**Post date:** [January 15, 2019, 3:50am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/3 "2019-01-15T03:50:10Z")

</div>

By lexicographic ordering you must get

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

```

which is opposite of what Julia is returning.

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [January 15, 2019, 3:58am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/4 "2019-01-15T03:58:29Z")

</div>

> [@Azamat](#):
>
> By lexicographic ordering you must get

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.

> **[Lexicographic order](https://en.wikipedia.org/wiki/Lexicographical_order)**
>
> In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set.
> There are several variants and generalizations of the lexicographical ordering. One variant applies to sequences of different lengths by comparing the lengths of the sequences before considering their elements.
> Another variant, widel...

---

<div class="post-metadata">

**Author:** ![jbmuir](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jbmuir/32/4798_2.png) [@jbmuir](https://discourse.julialang.org/u/jbmuir)\
**Post date:** [January 15, 2019, 4:06am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/5 "2019-01-15T04:06:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sean\_McBane](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sean_mcbane/32/4580_2.png) [@Sean\_McBane](https://discourse.julialang.org/u/Sean_McBane)\
**Post date:** [January 15, 2019, 4:28am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/6 "2019-01-15T04:28:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [January 15, 2019, 7:20am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/7 "2019-01-15T07:20:41Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [January 15, 2019, 8:30am UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/8 "2019-01-15T08:30:59Z")

</div>

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

```julia
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.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [January 15, 2019, 5:01pm UTC](https://discourse.julialang.org/t/cartesian-index-inequalities/19644/9 "2019-01-15T17:01:35Z")

</div>

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](https://github.com/JuliaLang/julia/pull/16054)