Repository: JuliaLang/julia
File: base/range.jl (Julia)

Code before:
_has_length_one(r::AbstractRange) = isone(length(r))

function ==(r::AbstractRange, s::AbstractRange)
    lr = length(r)
    if lr != length(s)
        return false
    elseif iszero(lr)
        return true
    end
    yr, ys = iterate(r), iterate(s)
    while yr !== nothing
        yr[1] == ys[1] || return false
        yr, ys = iterate(r, yr[2]), iterate(s, ys[2])
    end
    return true
end

function cmp(r1::AbstractRange{T}, r2::AbstractRange{T}) where {T}
    firstindex(r1) == firstindex(r2) || return cmp(firstindex(r1), firstindex(r2))
    (isempty(r1) || isempty(r2)) && return cmp(isempty(r2), isempty(r1))
    first(r1) != first(r2) && return cmp(first(r1), first(r2))
    # Assume that ranges are monotonic and use the last shared element as a high precision proxy for step.
    x1, x2 = last(zip(r1, r2))
    x1 != x2 && return cmp(x1, x2)
    cmp(length(r1), length(r2))
end

intersect(r::OneTo, s::OneTo) = OneTo(min(r.stop,s.stop))
union(r::OneTo, s::OneTo) = OneTo(max(r.stop,s.stop))

intersect(r::AbstractUnitRange{<:Integer}, s::AbstractUnitRange{<:Integer}) = max(first(r),first(s)):min(last(r),last(s))

intersect(i::Integer, r::AbstractUnitRange{<:Integer}) = range(max(i, first(r)), length=in(i, r))

intersect(r::AbstractUnitRange{<:Integer}, i::Integer) = intersect(i, r)

function intersect(r::AbstractUnitRange{<:Integer}, s::StepRange{<:Integer})
    T = promote_type(eltype(r), eltype(s))
    if isempty(s)
        StepRange{T}(first(r), +step(s), first(r)-step(s))
    else
        sta, ste, sto = first_step_last_ascending(s)
        lo = first(r)
        hi = last(r)
        i0 = max(sta, lo + mod(sta - lo, ste))
        i1 = min(sto, hi - mod(hi - sta, ste))
        StepRange{T}(i0, ste, i1)
    end
end

function first_step_last_ascending(r::StepRange)

Review comment (performance):
`last(zip(r1, r2))` is still the abstract iterator's O(n) isn't it?  And if we're doing an O(n) thing, we might as well compare everything, no?  The goal here should be to detect the "fast" outs that are _definitively_ correct, falling back to O(n) iteration if we can't do that.

The worst case is where `step` is identical, but, yeah, it's tricky to rely on `step(r)`.  Perhaps this should just be done for `OrdinalRange`s.

Code after:
_has_length_one(r::AbstractRange) = isone(length(r))

function ==(r::AbstractRange, s::AbstractRange)
    lr = length(r)
    if lr != length(s)
        return false
    elseif iszero(lr)
        return true
    end
    yr, ys = iterate(r), iterate(s)
    while yr !== nothing
        yr[1] == ys[1] || return false
        yr, ys = iterate(r, yr[2]), iterate(s, ys[2])
    end
    return true
end

function cmp(r1::T, r2::T) where {T <: AbstractRange}
    firstindex(r1) == firstindex(r2) || return cmp(firstindex(r1), firstindex(r2))
    (isempty(r1) || isempty(r2)) && return cmp(isempty(r2), isempty(r1))
    first(r1) != first(r2) && return cmp(first(r1), first(r2))
    # Assume that ranges are monotonic and use the last shared element as a high precision proxy for step.
    n = min(lastindex(r1), lastindex(r2))
    x1, x2 = r1[n], r2[n]
    x1 != x2 && return cmp(x1, x2)
    cmp(length(r1), length(r2))
end

intersect(r::OneTo, s::OneTo) = OneTo(min(r.stop,s.stop))
union(r::OneTo, s::OneTo) = OneTo(max(r.stop,s.stop))

intersect(r::AbstractUnitRange{<:Integer}, s::AbstractUnitRange{<:Integer}) = max(first(r),first(s)):min(last(r),last(s))

intersect(i::Integer, r::AbstractUnitRange{<:Integer}) = range(max(i, first(r)), length=in(i, r))

intersect(r::AbstractUnitRange{<:Integer}, i::Integer) = intersect(i, r)

function intersect(r::AbstractUnitRange{<:Integer}, s::StepRange{<:Integer})
    T = promote_type(eltype(r), eltype(s))
    if isempty(s)
        StepRange{T}(first(r), +step(s), first(r)-step(s))
    else
        sta, ste, sto = first_step_last_ascending(s)
        lo = first(r)
        hi = last(r)
        i0 = max(sta, lo + mod(sta - lo, ste))
        i1 = min(sto, hi - mod(hi - sta, ste))
        StepRange{T}(i0, ste, i1)
    end
end