CartesianRuns.jl

A read-only AbstractVector{CartesianIndex{N}} view of the positions where a boolean mask is true, using SAMURAI-style interval compression for arbitrary N.

Coordinate spaces

Two coordinate spaces are distinguished throughout:

Mask space: the Cartesian indices of the original array. Contains gaps — the false cells.
Compact space: the 1-based linear positions 1…count(mask), enumerating only the true cells in column-major order. No gaps by definition.

CartesianRunIndices bridges the two spaces via a pair of dual operations:

Operation	Direction	Julia API
`cri[k]`	compact → mask	`Base.getindex`
`ci ∈ cri`	mask → compact (membership)	`Base.in`

The representation itself is also dual: CartesianRunIndices(mask) compresses a boolean mask into interval form, and expand(cri, axes(mask)) reconstructs the mask exactly. They are exact inverses:

expand(CartesianRunIndices(mask), axes(mask)) == mask   # always true

This duality mirrors the philosophy of SAMURAI, which separates the compressed mesh structure from the data it indexes.

Example

using CartesianRuns

mask = Bool[0 1 0; 1 1 0; 0 1 1]
cri  = CartesianRunIndices(mask)

collect(cri) == findall(mask)      # true — compact → mask
CartesianIndex(2, 1) ∈ cri        # true  — mask membership

Set operations

CartesianRunIndices supports set-algebraic operations that work directly on the interval representation — no boolean mask is ever materialised.

Unary operations

mask = Bool[0 1; 1 1; 0 1]
cri  = CartesianRunIndices(mask)

expand(cri, axes(mask)) == mask    # true — exact inverse of constructor
complement(cri, axes(mask))        # positions in axes(mask) not in cri

CartesianRunIndices(mask) and expand(cri, axes(mask)) are exact inverses.

expand requires a 1-based domain (NTuple{N,Base.OneTo{Int}}); for non-1-based domains load OffsetArrays.jl first, which returns an OffsetArray{Bool,N} with axes matching domain. complement accepts any AbstractUnitRange and always returns a CartesianRunIndices (no OffsetArray needed):

# The constructor and complement accept any AbstractUnitRange.
cri_sub = CartesianRunIndices(mask, (1:2, 2:3))   # restricted to sub-domain
c   = complement(cri_sub, (1:2, 2:3))  # CartesianRunIndices within sub-domain

# expand with a non-1-based domain requires OffsetArrays.
using OffsetArrays
out = expand(cri_sub, (1:2, 2:3))      # OffsetArray{Bool,2} with axes (1:2, 2:3)

expand returns an OffsetArray{Bool,N} whose axes match domain when loaded with OffsetArrays.

A second constructor restricts the scan to a sub-domain:

cri_sub = CartesianRunIndices(mask, (1:2, 1:2))  # only rows 1:2, cols 1:2

domain[d] must be a subset of axes(mask, d) for every dimension; an ArgumentError is thrown otherwise.

Binary operations

A = CartesianRunIndices(Bool[0 1; 1 1; 0 1])
B = CartesianRunIndices(Bool[1 1; 1 0; 0 1])

intersect(A, B)  # positions in both A and B
union(A, B)      # positions in A or B (or both)
setdiff(A, B)    # positions in A but not in B

API reference

CartesianRuns.Interval — Type

Interval(mask, shift)

A run of consecutive true cells in a boolean mask, paired with the corresponding run of compact positions.

Fields

mask::UnitRange{Int}: Indices of the run in the original mask (mask space).
compact::UnitRange{Int}: Corresponding 1-based positions in the compact array (compact space). Always satisfies length(compact) == length(mask).

The two ranges always have the same length; the constructor enforces this by deriving compact from mask and shift:

Interval(mask::UnitRange{Int}, shift::Int)

Methods

shift(iv::Interval) -> Int

Retrieve the integer offset such that i + shift(iv) maps any i ∈ iv.mask to its compact position. Equivalent to iv.compact.start - iv.mask.start.

source

CartesianRuns.shift — Function

shift(iv::Interval) -> Int

Return the integer offset between mask space and compact space for iv: for any i ∈ iv.mask, i + shift(iv) is the corresponding compact position.

source

CartesianRuns.CartesianRunIndices — Type

CartesianRunIndices{N,M,I,O} <: AbstractVector{CartesianIndex{N}}

A read-only AbstractVector view of the positions where an N-dimensional boolean mask is true, using SAMURAI-style interval compression.

Type parameters

N: number of spatial dimensions.
M = N - 1: number of offset arrays (enforced by inner constructor).
I <: AbstractVector{Interval}: element type of each dimension's interval vector.
O <: AbstractVector{Int}: element type of each CSR offset array.

Fields

intervals::NTuple{N,I}: packed interval vectors, one per dimension. intervals[d] contains all dim-d runs in scan order across all scanlines.
offsets::NTuple{M,O}: 1-based CSR offset arrays connecting active cells in dimension d+1 to their ranges in intervals[d]. Empty tuple for N = 1.

Construction

CartesianRunIndices(mask::AbstractArray{Bool,N}) -> CartesianRunIndices

Construct from a boolean mask of any dimension.

CartesianRunIndices(mask::AbstractArray{Bool,N}, domain::NTuple{N,AbstractUnitRange{Int}}) -> CartesianRunIndices

Construct from a boolean mask, restricting the scan to positions within domain. Each element of domain must be a subset of the corresponding axis of mask; an ArgumentError is thrown otherwise. The returned CartesianRunIndices contains only the true cells of mask that lie within domain.

source

Base.size — Method

size(cri::CartesianRunIndices) -> Tuple{Int}

Return (n,) where n = count(mask) is the total number of true cells. Consistent with the AbstractVector interface.

source

Base.getindex — Method

getindex(cri::CartesianRunIndices, k::Int) -> CartesianIndex

Return the k-th true cell of the mask, in column-major (Julia-default) scan order. Delegates to _recover after a bounds check.

source

Base.in — Method

in(idx::CartesianIndex{N}, cri::CartesianRunIndices{N}) -> Bool

Return true if idx corresponds to a true cell in the mask used to construct cri. Equivalent to mask[idx], but works directly on the compressed representation in O(N log R) time (R = maximum run count per dimension) without reconstructing the mask.

source

CartesianRuns.expand — Function

expand(cri::CartesianRunIndices{N}, domain::NTuple{N,Base.OneTo{Int}}) -> Array{Bool,N}

Reconstruct the boolean mask from cri: the returned array has axes equal to domain and is true exactly at the positions in cri.

CartesianRunIndices(mask) and expand(cri, axes(mask)) are exact inverses:

expand(CartesianRunIndices(mask), axes(mask)) == mask   # always true

domain must be a NTuple of Base.OneTo{Int} ranges (i.e., 1-based). For non-1-based domains, load OffsetArrays.jl first; expand will then return an OffsetArray with axes equal to domain.

source

CartesianRuns.complement — Function

complement(cri::CartesianRunIndices{N}, domain::NTuple{N,<:AbstractUnitRange{Int}}) -> CartesianRunIndices{N}

Return a CartesianRunIndices containing every position in domain that is not in cri, computed directly from the interval representation.

All positions are returned in the original mask-space coordinates, so domain may be any AbstractUnitRange — it need not be 1-based.

source

Base.intersect — Method

intersect(a::CartesianRunIndices{N}, b::CartesianRunIndices{N}) -> CartesianRunIndices{N}

Return a CartesianRunIndices containing every CartesianIndex that is true in both a and b.

source

Base.setdiff — Method

setdiff(a::CartesianRunIndices{N}, b::CartesianRunIndices{N}) -> CartesianRunIndices{N}

Return a CartesianRunIndices containing every CartesianIndex that is true in a but not in b.

source

Base.union — Method

union(a::CartesianRunIndices{N}, b::CartesianRunIndices{N}) -> CartesianRunIndices{N}

Return a CartesianRunIndices containing every CartesianIndex that is true in a, in b, or in both. Overlapping or adjacent runs are merged.

source