Report index
StatProfilerHTML.jl report
Generated on Mon, 01 Apr 2024 21:01:18
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 (:)(a::Real, b::Real) = (:)(promote(a, b)...)
4
5 (:)(start::T, stop::T) where {T<:Real} = UnitRange{T}(start, stop)
6
7 (:)(start::T, stop::T) where {T} = (:)(start, oftype(stop >= start ? stop - start : start - stop, 1), stop)
8
9 # promote start and stop, leaving step alone
10 (:)(start::A, step, stop::C) where {A<:Real, C<:Real} =
11 (:)(convert(promote_type(A, C), start), step, convert(promote_type(A, C), stop))
12
13 # AbstractFloat specializations
14 (:)(a::T, b::T) where {T<:AbstractFloat} = (:)(a, T(1), b)
15
16 (:)(a::T, b::AbstractFloat, c::T) where {T<:Real} = (:)(promote(a, b, c)...)
17 (:)(a::T, b::AbstractFloat, c::T) where {T<:AbstractFloat} = (:)(promote(a, b, c)...)
18 (:)(a::T, b::Real, c::T) where {T<:AbstractFloat} = (:)(promote(a, b, c)...)
19
20 (:)(start::T, step::T, stop::T) where {T<:AbstractFloat} =
21 _colon(OrderStyle(T), ArithmeticStyle(T), start, step, stop)
22 (:)(start::T, step::T, stop::T) where {T<:Real} =
23 _colon(OrderStyle(T), ArithmeticStyle(T), start, step, stop)
24 _colon(::Ordered, ::Any, start::T, step, stop::T) where {T} = StepRange(start, step, stop)
25 # for T<:Union{Float16,Float32,Float64} see twiceprecision.jl
26 _colon(::Ordered, ::ArithmeticRounds, start::T, step, stop::T) where {T} =
27 StepRangeLen(start, step, convert(Integer, fld(stop - start, step)) + 1)
28 _colon(::Any, ::Any, start::T, step, stop::T) where {T} =
29 StepRangeLen(start, step, convert(Integer, fld(stop - start, step)) + 1)
30
31 """
32 (:)(start, [step], stop)
33
34 Range operator. `a:b` constructs a range from `a` to `b` with a step size
35 equal to 1, which produces:
36
37 * a [`UnitRange`](@ref) when `a` and `b` are integers, or
38 * a [`StepRange`](@ref) when `a` and `b` are characters, or
39 * a [`StepRangeLen`](@ref) when `a` and/or `b` are floating-point.
40
41 `a:s:b` is similar but uses a step size of `s` (a [`StepRange`](@ref) or
42 [`StepRangeLen`](@ref)). See also [`range`](@ref) for more control.
43
44 The operator `:` is also used in indexing to select whole dimensions, e.g. in `A[:, 1]`.
45
46 `:` is also used to [`quote`](@ref) code, e.g. `:(x + y) isa Expr` and `:x isa Symbol`.
47 Since `:2 isa Int`, it does *not* create a range in indexing: `v[:2] == v[2] != v[begin:2]`.
48 """
49 (:)(start::T, step, stop::T) where {T} = _colon(start, step, stop)
50 (:)(start::T, step, stop::T) where {T<:Real} = _colon(start, step, stop)
51 # without the second method above, the first method above is ambiguous with
52 # (:)(start::A, step, stop::C) where {A<:Real,C<:Real}
53 function _colon(start::T, step, stop::T) where T
54 T′ = typeof(start+zero(step))
55 StepRange(convert(T′,start), step, convert(T′,stop))
56 end
57
58 """
59 range(start, stop, length)
60 range(start, stop; length, step)
61 range(start; length, stop, step)
62 range(;start, length, stop, step)
63
64 Construct a specialized array with evenly spaced elements and optimized storage (an [`AbstractRange`](@ref)) from the arguments.
65 Mathematically a range is uniquely determined by any three of `start`, `step`, `stop` and `length`.
66 Valid invocations of range are:
67 * Call `range` with any three of `start`, `step`, `stop`, `length`.
68 * Call `range` with two of `start`, `stop`, `length`. In this case `step` will be assumed
69 to be one. If both arguments are Integers, a [`UnitRange`](@ref) will be returned.
70 * Call `range` with one of `stop` or `length`. `start` and `step` will be assumed to be one.
71
72 See Extended Help for additional details on the returned type.
73
74 # Examples
75 ```jldoctest
76 julia> range(1, length=100)
77 1:100
78
79 julia> range(1, stop=100)
80 1:100
81
82 julia> range(1, step=5, length=100)
83 1:5:496
84
85 julia> range(1, step=5, stop=100)
86 1:5:96
87
88 julia> range(1, 10, length=101)
89 1.0:0.09:10.0
90
91 julia> range(1, 100, step=5)
92 1:5:96
93
94 julia> range(stop=10, length=5)
95 6:10
96
97 julia> range(stop=10, step=1, length=5)
98 6:1:10
99
100 julia> range(start=1, step=1, stop=10)
101 1:1:10
102
103 julia> range(; length = 10)
104 Base.OneTo(10)
105
106 julia> range(; stop = 6)
107 Base.OneTo(6)
108
109 julia> range(; stop = 6.5)
110 1.0:1.0:6.0
111 ```
112 If `length` is not specified and `stop - start` is not an integer multiple of `step`, a range that ends before `stop` will be produced.
113 ```jldoctest
114 julia> range(1, 3.5, step=2)
115 1.0:2.0:3.0
116 ```
117
118 Special care is taken to ensure intermediate values are computed rationally.
119 To avoid this induced overhead, see the [`LinRange`](@ref) constructor.
120
121 !!! compat "Julia 1.1"
122 `stop` as a positional argument requires at least Julia 1.1.
123
124 !!! compat "Julia 1.7"
125 The versions without keyword arguments and `start` as a keyword argument
126 require at least Julia 1.7.
127
128 !!! compat "Julia 1.8"
129 The versions with `stop` as a sole keyword argument,
130 or `length` as a sole keyword argument require at least Julia 1.8.
131
132
133 # Extended Help
134
135 `range` will produce a `Base.OneTo` when the arguments are Integers and
136 * Only `length` is provided
137 * Only `stop` is provided
138
139 `range` will produce a `UnitRange` when the arguments are Integers and
140 * Only `start` and `stop` are provided
141 * Only `length` and `stop` are provided
142
143 A `UnitRange` is not produced if `step` is provided even if specified as one.
144 """
145 function range end
146
147 range(start; stop=nothing, length::Union{Integer,Nothing}=nothing, step=nothing) =
148 _range(start, step, stop, length)
149 range(start, stop; length::Union{Integer,Nothing}=nothing, step=nothing) = _range(start, step, stop, length)
150 range(start, stop, length::Integer) = _range(start, nothing, stop, length)
151
152 range(;start=nothing, stop=nothing, length::Union{Integer, Nothing}=nothing, step=nothing) =
153 _range(start, step, stop, length)
154
155 _range(start::Nothing, step::Nothing, stop::Nothing, len::Nothing) = range_error(start, step, stop, len)
156 _range(start::Nothing, step::Nothing, stop::Nothing, len::Any ) = range_length(len)
157 _range(start::Nothing, step::Nothing, stop::Any , len::Nothing) = range_stop(stop)
158 _range(start::Nothing, step::Nothing, stop::Any , len::Any ) = range_stop_length(stop, len)
159 _range(start::Nothing, step::Any , stop::Nothing, len::Nothing) = range_error(start, step, stop, len)
160 _range(start::Nothing, step::Any , stop::Nothing, len::Any ) = range_error(start, step, stop, len)
161 _range(start::Nothing, step::Any , stop::Any , len::Nothing) = range_error(start, step, stop, len)
162 _range(start::Nothing, step::Any , stop::Any , len::Any ) = range_step_stop_length(step, stop, len)
163 _range(start::Any , step::Nothing, stop::Nothing, len::Nothing) = range_error(start, step, stop, len)
164 _range(start::Any , step::Nothing, stop::Nothing, len::Any ) = range_start_length(start, len)
165 _range(start::Any , step::Nothing, stop::Any , len::Nothing) = range_start_stop(start, stop)
166 _range(start::Any , step::Nothing, stop::Any , len::Any ) = range_start_stop_length(start, stop, len)
167 _range(start::Any , step::Any , stop::Nothing, len::Nothing) = range_error(start, step, stop, len)
168 _range(start::Any , step::Any , stop::Nothing, len::Any ) = range_start_step_length(start, step, len)
169 _range(start::Any , step::Any , stop::Any , len::Nothing) = range_start_step_stop(start, step, stop)
170 _range(start::Any , step::Any , stop::Any , len::Any ) = range_error(start, step, stop, len)
171
172 # Length as the only argument
173 range_length(len::Integer) = OneTo(len)
174
175 # Stop as the only argument
176 range_stop(stop) = range_start_stop(oftype(stop, 1), stop)
177 range_stop(stop::Integer) = range_length(stop)
178
179 function range_step_stop_length(step, a, len::Integer)
180 start = a - step * (len - oneunit(len))
181 if start isa Signed
182 # overflow in recomputing length from stop is okay
183 return StepRange{typeof(start),typeof(step)}(start, step, convert(typeof(start), a))
184 end
185 return StepRangeLen{typeof(start),typeof(start),typeof(step)}(start, step, len)
186 end
187
188 # Stop and length as the only argument
189 function range_stop_length(a, len::Integer)
190 step = oftype(a - a, 1) # assert that step is representable
191 start = a - (len - oneunit(len))
192 if start isa Signed
193 # overflow in recomputing length from stop is okay
194 return UnitRange(start, oftype(start, a))
195 end
196 return StepRangeLen{typeof(start),typeof(start),typeof(step)}(start, step, len)
197 end
198
199 # Start and length as the only argument
200 function range_start_length(a, len::Integer)
201 step = oftype(a - a, 1) # assert that step is representable
202 stop = a + (len - oneunit(len))
203 if stop isa Signed
204 # overflow in recomputing length from stop is okay
205 return UnitRange(oftype(stop, a), stop)
206 end
207 return StepRangeLen{typeof(stop),typeof(a),typeof(step)}(a, step, len)
208 end
209
210 range_start_stop(start, stop) = start:stop
211
212 function range_start_step_length(a, step, len::Integer)
213 stop = a + step * (len - oneunit(len))
214 if stop isa Signed
215 # overflow in recomputing length from stop is okay
216 return StepRange{typeof(stop),typeof(step)}(convert(typeof(stop), a), step, stop)
217 end
218 return StepRangeLen{typeof(stop),typeof(a),typeof(step)}(a, step, len)
219 end
220
221 range_start_step_stop(start, step, stop) = start:step:stop
222
223 function range_error(start, step, stop, length)
224 hasstart = start !== nothing
225 hasstep = step !== nothing
226 hasstop = stop !== nothing
227 haslength = start !== nothing
228
229 hint = if hasstart && hasstep && hasstop && haslength
230 "Try specifying only three arguments"
231 elseif !hasstop && !haslength
232 "At least one of `length` or `stop` must be specified."
233 elseif !hasstep && !haslength
234 "At least one of `length` or `step` must be specified."
235 elseif !hasstart && !hasstop
236 "At least one of `start` or `stop` must be specified."
237 else
238 "Try specifying more arguments."
239 end
240
241 msg = """
242 Cannot construct range from arguments:
243 start = $start
244 step = $step
245 stop = $stop
246 length = $length
247 $hint
248 """
249 throw(ArgumentError(msg))
250 end
251
252 ## 1-dimensional ranges ##
253
254 """
255 AbstractRange{T}
256
257 Supertype for ranges with elements of type `T`.
258 [`UnitRange`](@ref) and other types are subtypes of this.
259 """
260 abstract type AbstractRange{T} <: AbstractArray{T,1} end
261
262 RangeStepStyle(::Type{<:AbstractRange}) = RangeStepIrregular()
263 RangeStepStyle(::Type{<:AbstractRange{<:Integer}}) = RangeStepRegular()
264
265 convert(::Type{T}, r::AbstractRange) where {T<:AbstractRange} = r isa T ? r : T(r)::T
266
267 ## ordinal ranges
268
269 """
270 OrdinalRange{T, S} <: AbstractRange{T}
271
272 Supertype for ordinal ranges with elements of type `T` with
273 spacing(s) of type `S`. The steps should be always-exact
274 multiples of [`oneunit`](@ref), and `T` should be a "discrete"
275 type, which cannot have values smaller than `oneunit`. For example,
276 `Integer` or `Date` types would qualify, whereas `Float64` would not (since this
277 type can represent values smaller than `oneunit(Float64)`.
278 [`UnitRange`](@ref), [`StepRange`](@ref), and other types are subtypes of this.
279 """
280 abstract type OrdinalRange{T,S} <: AbstractRange{T} end
281
282 """
283 AbstractUnitRange{T} <: OrdinalRange{T, T}
284
285 Supertype for ranges with a step size of [`oneunit(T)`](@ref) with elements of type `T`.
286 [`UnitRange`](@ref) and other types are subtypes of this.
287 """
288 abstract type AbstractUnitRange{T} <: OrdinalRange{T,T} end
289
290 """
291 StepRange{T, S} <: OrdinalRange{T, S}
292
293 Ranges with elements of type `T` with spacing of type `S`. The step
294 between each element is constant, and the range is defined in terms
295 of a `start` and `stop` of type `T` and a `step` of type `S`. Neither
296 `T` nor `S` should be floating point types. The syntax `a:b:c` with `b != 0`
297 and `a`, `b`, and `c` all integers creates a `StepRange`.
298
299 # Examples
300 ```jldoctest
301 julia> collect(StepRange(1, Int8(2), 10))
302 5-element Vector{Int64}:
303 1
304 3
305 5
306 7
307 9
308
309 julia> typeof(StepRange(1, Int8(2), 10))
310 StepRange{Int64, Int8}
311
312 julia> typeof(1:3:6)
313 StepRange{Int64, Int64}
314 ```
315 """
316 struct StepRange{T,S} <: OrdinalRange{T,S}
317 start::T
318 step::S
319 stop::T
320
321 function StepRange{T,S}(start, step, stop) where {T,S}
322 start = convert(T, start)
323 step = convert(S, step)
324 stop = convert(T, stop)
325 return new(start, step, steprange_last(start, step, stop))
326 end
327 end
328
329 # to make StepRange constructor inlineable, so optimizer can see `step` value
330 function steprange_last(start, step, stop)::typeof(stop)
331 if isa(start, AbstractFloat) || isa(step, AbstractFloat)
332 throw(ArgumentError("StepRange should not be used with floating point"))
333 end
334 if isa(start, Integer) && !isinteger(start + step)
335 throw(ArgumentError("StepRange{<:Integer} cannot have non-integer step"))
336 end
337 z = zero(step)
338 step == z && throw(ArgumentError("step cannot be zero"))
339
340 if stop == start
341 last = stop
342 else
343 if (step > z) != (stop > start)
344 last = steprange_last_empty(start, step, stop)
345 else
346 # Compute absolute value of difference between `start` and `stop`
347 # (to simplify handling both signed and unsigned T and checking for signed overflow):
348 absdiff, absstep = stop > start ? (stop - start, step) : (start - stop, -step)
349
350 # Compute remainder as a nonnegative number:
351 if absdiff isa Signed && absdiff < zero(absdiff)
352 # unlikely, but handle the signed overflow case with unsigned rem
353 overflow_case(absdiff, absstep) = (@noinline; convert(typeof(absdiff), unsigned(absdiff) % absstep))
354 remain = overflow_case(absdiff, absstep)
355 else
356 remain = convert(typeof(absdiff), absdiff % absstep)
357 end
358 # Move `stop` closer to `start` if there is a remainder:
359 last = stop > start ? stop - remain : stop + remain
360 end
361 end
362 return last
363 end
364
365 function steprange_last_empty(start::Integer, step, stop)::typeof(stop)
366 # empty range has a special representation where stop = start-1,
367 # which simplifies arithmetic for Signed numbers
368 if step > zero(step)
369 last = start - oneunit(step)
370 else
371 last = start + oneunit(step)
372 end
373 return last
374 end
375 # For types where x+oneunit(x) may not be well-defined use the user-given value for stop
376 steprange_last_empty(start, step, stop) = stop
377
378 StepRange{T}(start, step::S, stop) where {T,S} = StepRange{T,S}(start, step, stop)
379 StepRange(start::T, step::S, stop::T) where {T,S} = StepRange{T,S}(start, step, stop)
380
381 """
382 UnitRange{T<:Real}
383
384 A range parameterized by a `start` and `stop` of type `T`, filled
385 with elements spaced by `1` from `start` until `stop` is exceeded.
386 The syntax `a:b` with `a` and `b` both `Integer`s creates a `UnitRange`.
387
388 # Examples
389 ```jldoctest
390 julia> collect(UnitRange(2.3, 5.2))
391 3-element Vector{Float64}:
392 2.3
393 3.3
394 4.3
395
396 julia> typeof(1:10)
397 UnitRange{Int64}
398 ```
399 """
400 struct UnitRange{T<:Real} <: AbstractUnitRange{T}
401 start::T
402 stop::T
403 UnitRange{T}(start::T, stop::T) where {T<:Real} = new(start, unitrange_last(start, stop))
404 end
405 UnitRange{T}(start, stop) where {T<:Real} = UnitRange{T}(convert(T, start), convert(T, stop))
406 UnitRange(start::T, stop::T) where {T<:Real} = UnitRange{T}(start, stop)
407 function UnitRange(start, stop)
408 startstop_promoted = promote(start, stop)
409 not_sametype((start, stop), startstop_promoted)
410 UnitRange(startstop_promoted...)
411 end
412
413 # if stop and start are integral, we know that their difference is a multiple of 1
414 unitrange_last(start::Integer, stop::Integer) =
415 stop >= start ? stop : convert(typeof(stop), start - oneunit(start - stop))
416 # otherwise, use `floor` as a more efficient way to compute modulus with step=1
417 unitrange_last(start, stop) =
418 stop >= start ? convert(typeof(stop), start + floor(stop - start)) :
419 convert(typeof(stop), start - oneunit(start - stop))
420
421 unitrange(x::AbstractUnitRange) = UnitRange(x) # convenience conversion for promoting the range type
422
423 if isdefined(Main, :Base)
424 # Constant-fold-able indexing into tuples to functionally expose Base.tail and Base.front
425 function getindex(@nospecialize(t::Tuple), r::AbstractUnitRange)
426 @inline
427 require_one_based_indexing(r)
428 if length(r) <= 10
429 return ntuple(i -> t[i + first(r) - 1], length(r))
430 elseif first(r) == 1
431 last(r) == length(t) && return t
432 last(r) == length(t)-1 && return front(t)
433 last(r) == length(t)-2 && return front(front(t))
434 elseif last(r) == length(t)
435 first(r) == 2 && return tail(t)
436 first(r) == 3 && return tail(tail(t))
437 end
438 return (eltype(t)[t[ri] for ri in r]...,)
439 end
440 end
441
442 """
443 Base.OneTo(n)
444
445 Define an `AbstractUnitRange` that behaves like `1:n`, with the added
446 distinction that the lower limit is guaranteed (by the type system) to
447 be 1.
448 """
449 struct OneTo{T<:Integer} <: AbstractUnitRange{T}
450 stop::T
451 function OneTo{T}(stop) where {T<:Integer}
452 throwbool(r) = (@noinline; throw(ArgumentError("invalid index: $r of type Bool")))
453 T === Bool && throwbool(stop)
454 return new(max(zero(T), stop))
455 end
456
457 function OneTo{T}(r::AbstractRange) where {T<:Integer}
458 throwstart(r) = (@noinline; throw(ArgumentError("first element must be 1, got $(first(r))")))
459 throwstep(r) = (@noinline; throw(ArgumentError("step must be 1, got $(step(r))")))
460 throwbool(r) = (@noinline; throw(ArgumentError("invalid index: $r of type Bool")))
461 first(r) == 1 || throwstart(r)
462 step(r) == 1 || throwstep(r)
463 T === Bool && throwbool(r)
464 return new(max(zero(T), last(r)))
465 end
466 end
467 OneTo(stop::T) where {T<:Integer} = OneTo{T}(stop)
468 OneTo(r::AbstractRange{T}) where {T<:Integer} = OneTo{T}(r)
469 oneto(r) = OneTo(r)
470
471 ## Step ranges parameterized by length
472
473 """
474 StepRangeLen( ref::R, step::S, len, [offset=1]) where { R,S}
475 StepRangeLen{T,R,S}( ref::R, step::S, len, [offset=1]) where {T,R,S}
476 StepRangeLen{T,R,S,L}(ref::R, step::S, len, [offset=1]) where {T,R,S,L}
477
478 A range `r` where `r[i]` produces values of type `T` (in the first
479 form, `T` is deduced automatically), parameterized by a `ref`erence
480 value, a `step`, and the `len`gth. By default `ref` is the starting
481 value `r[1]`, but alternatively you can supply it as the value of
482 `r[offset]` for some other index `1 <= offset <= len`. The syntax `a:b`
483 or `a:b:c`, where any of `a`, `b`, or `c` are floating-point numbers, creates a
484 `StepRangeLen`.
485
486 !!! compat "Julia 1.7"
487 The 4th type parameter `L` requires at least Julia 1.7.
488 """
489 struct StepRangeLen{T,R,S,L<:Integer} <: AbstractRange{T}
490 ref::R # reference value (might be smallest-magnitude value in the range)
491 step::S # step value
492 len::L # length of the range
493 offset::L # the index of ref
494
495 function StepRangeLen{T,R,S,L}(ref::R, step::S, len::Integer, offset::Integer = 1) where {T,R,S,L}
496 if T <: Integer && !isinteger(ref + step)
497 throw(ArgumentError("StepRangeLen{<:Integer} cannot have non-integer step"))
498 end
499 len = convert(L, len)
500 len >= zero(len) || throw(ArgumentError("length cannot be negative, got $len"))
501 offset = convert(L, offset)
502 L1 = oneunit(typeof(len))
503 L1 <= offset <= max(L1, len) || throw(ArgumentError("StepRangeLen: offset must be in [1,$len], got $offset"))
504 return new(ref, step, len, offset)
505 end
506 end
507
508 StepRangeLen{T,R,S}(ref::R, step::S, len::Integer, offset::Integer = 1) where {T,R,S} =
509 StepRangeLen{T,R,S,promote_type(Int,typeof(len))}(ref, step, len, offset)
510 StepRangeLen(ref::R, step::S, len::Integer, offset::Integer = 1) where {R,S} =
511 StepRangeLen{typeof(ref+zero(step)),R,S,promote_type(Int,typeof(len))}(ref, step, len, offset)
512 StepRangeLen{T}(ref::R, step::S, len::Integer, offset::Integer = 1) where {T,R,S} =
513 StepRangeLen{T,R,S,promote_type(Int,typeof(len))}(ref, step, len, offset)
514
515 ## range with computed step
516
517 """
518 LinRange{T,L}
519
520 A range with `len` linearly spaced elements between its `start` and `stop`.
521 The size of the spacing is controlled by `len`, which must
522 be an `Integer`.
523
524 # Examples
525 ```jldoctest
526 julia> LinRange(1.5, 5.5, 9)
527 9-element LinRange{Float64, Int64}:
528 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0, 5.5
529 ```
530
531 Compared to using [`range`](@ref), directly constructing a `LinRange` should
532 have less overhead but won't try to correct for floating point errors:
533 ```jldoctest
534 julia> collect(range(-0.1, 0.3, length=5))
535 5-element Vector{Float64}:
536 -0.1
537 0.0
538 0.1
539 0.2
540 0.3
541
542 julia> collect(LinRange(-0.1, 0.3, 5))
543 5-element Vector{Float64}:
544 -0.1
545 -1.3877787807814457e-17
546 0.09999999999999999
547 0.19999999999999998
548 0.3
549 ```
550 """
551 struct LinRange{T,L<:Integer} <: AbstractRange{T}
552 start::T
553 stop::T
554 len::L
555 lendiv::L
556
557 function LinRange{T,L}(start::T, stop::T, len::L) where {T,L<:Integer}
558 len >= 0 || throw(ArgumentError("range($start, stop=$stop, length=$len): negative length"))
559 onelen = oneunit(typeof(len))
560 if len == onelen
561 start == stop || throw(ArgumentError("range($start, stop=$stop, length=$len): endpoints differ"))
562 return new(start, stop, len, len)
563 end
564 lendiv = max(len - onelen, onelen)
565 if T <: Integer && !iszero(mod(stop-start, lendiv))
566 throw(ArgumentError("LinRange{<:Integer} cannot have non-integer step"))
567 end
568 return new(start, stop, len, lendiv)
569 end
570 end
571
572 function LinRange{T,L}(start, stop, len::Integer) where {T,L}
573 LinRange{T,L}(convert(T, start), convert(T, stop), convert(L, len))
574 end
575
576 function LinRange{T}(start, stop, len::Integer) where T
577 LinRange{T,promote_type(Int,typeof(len))}(start, stop, len)
578 end
579
580 function LinRange(start, stop, len::Integer)
581 T = typeof((zero(stop) - zero(start)) / oneunit(len))
582 LinRange{T}(start, stop, len)
583 end
584
585 range_start_stop_length(start, stop, len::Integer) =
586 range_start_stop_length(promote(start, stop)..., len)
587 range_start_stop_length(start::T, stop::T, len::Integer) where {T} = LinRange(start, stop, len)
588 range_start_stop_length(start::T, stop::T, len::Integer) where {T<:Integer} =
589 _linspace(float(T), start, stop, len)
590 ## for Float16, Float32, and Float64 we hit twiceprecision.jl to lift to higher precision StepRangeLen
591 # for all other types we fall back to a plain old LinRange
592 _linspace(::Type{T}, start::Integer, stop::Integer, len::Integer) where T = LinRange{T}(start, stop, len)
593
594 function show(io::IO, r::LinRange{T}) where {T}
595 print(io, "LinRange{")
596 show(io, T)
597 print(io, "}(")
598 ioc = IOContext(io, :typeinfo=>T)
599 show(ioc, first(r))
600 print(io, ", ")
601 show(ioc, last(r))
602 print(io, ", ")
603 show(io, length(r))
604 print(io, ')')
605 end
606
607 """
608 `print_range(io, r)` prints out a nice looking range r in terms of its elements
609 as if it were `collect(r)`, dependent on the size of the
610 terminal, and taking into account whether compact numbers should be shown.
611 It figures out the width in characters of each element, and if they
612 end up too wide, it shows the first and last elements separated by a
613 horizontal ellipsis. Typical output will look like `1.0, 2.0, …, 5.0, 6.0`.
614
615 `print_range(io, r, pre, sep, post, hdots)` uses optional
616 parameters `pre` and `post` characters for each printed row,
617 `sep` separator string between printed elements,
618 `hdots` string for the horizontal ellipsis.
619 """
620 function print_range(io::IO, r::AbstractRange,
621 pre::AbstractString = " ",
622 sep::AbstractString = ", ",
623 post::AbstractString = "",
624 hdots::AbstractString = ", \u2026, ") # horiz ellipsis
625 # This function borrows from print_matrix() in show.jl
626 # and should be called by show and display
627 sz = displaysize(io)
628 if !haskey(io, :compact)
629 io = IOContext(io, :compact => true)
630 end
631 screenheight, screenwidth = sz[1] - 4, sz[2]
632 screenwidth -= length(pre) + length(post)
633 postsp = ""
634 sepsize = length(sep)
635 m = 1 # treat the range as a one-row matrix
636 n = length(r)
637 # Figure out spacing alignments for r, but only need to examine the
638 # left and right edge columns, as many as could conceivably fit on the
639 # screen, with the middle columns summarized by horz, vert, or diag ellipsis
640 maxpossiblecols = div(screenwidth, 1+sepsize) # assume each element is at least 1 char + 1 separator
641 colsr = n <= maxpossiblecols ? (1:n) : [1:div(maxpossiblecols,2)+1; (n-div(maxpossiblecols,2)):n]
642 rowmatrix = reshape(r[colsr], 1, length(colsr)) # treat the range as a one-row matrix for print_matrix_row
643 nrow, idxlast = size(rowmatrix, 2), last(axes(rowmatrix, 2))
644 A = alignment(io, rowmatrix, 1:m, 1:length(rowmatrix), screenwidth, screenwidth, sepsize, nrow) # how much space range takes
645 if n <= length(A) # cols fit screen, so print out all elements
646 print(io, pre) # put in pre chars
647 print_matrix_row(io,rowmatrix,A,1,1:n,sep,idxlast) # the entire range
648 print(io, post) # add the post characters
649 else # cols don't fit so put horiz ellipsis in the middle
650 # how many chars left after dividing width of screen in half
651 # and accounting for the horiz ellipsis
652 c = div(screenwidth-length(hdots)+1,2)+1 # chars remaining for each side of rowmatrix
653 alignR = reverse(alignment(io, rowmatrix, 1:m, length(rowmatrix):-1:1, c, c, sepsize, nrow)) # which cols of rowmatrix to put on the right
654 c = screenwidth - sum(map(sum,alignR)) - (length(alignR)-1)*sepsize - length(hdots)
655 alignL = alignment(io, rowmatrix, 1:m, 1:length(rowmatrix), c, c, sepsize, nrow) # which cols of rowmatrix to put on the left
656 print(io, pre) # put in pre chars
657 print_matrix_row(io, rowmatrix,alignL,1,1:length(alignL),sep,idxlast) # left part of range
658 print(io, hdots) # horizontal ellipsis
659 print_matrix_row(io, rowmatrix,alignR,1,length(rowmatrix)-length(alignR)+1:length(rowmatrix),sep,idxlast) # right part of range
660 print(io, post) # post chars
661 end
662 end
663
664 ## interface implementations
665
666 length(r::AbstractRange) = error("length implementation missing") # catch mistakes
667 size(r::AbstractRange) = (length(r),)
668
669 isempty(r::StepRange) =
670 # steprange_last(r.start, r.step, r.stop) == r.stop
671 (r.start != r.stop) & ((r.step > zero(r.step)) != (r.stop > r.start))
672 isempty(r::AbstractUnitRange) = first(r) > last(r)
673 isempty(r::StepRangeLen) = length(r) == 0
674 isempty(r::LinRange) = length(r) == 0
675
676 """
677 step(r)
678
679 Get the step size of an [`AbstractRange`](@ref) object.
680
681 # Examples
682 ```jldoctest
683 julia> step(1:10)
684 1
685
686 julia> step(1:2:10)
687 2
688
689 julia> step(2.5:0.3:10.9)
690 0.3
691
692 julia> step(range(2.5, stop=10.9, length=85))
693 0.1
694 ```
695 """
696 step(r::StepRange) = r.step
697 step(r::AbstractUnitRange{T}) where {T} = oneunit(T) - zero(T)
698 step(r::StepRangeLen) = r.step
699 step(r::StepRangeLen{T}) where {T<:AbstractFloat} = T(r.step)
700 step(r::LinRange) = (last(r)-first(r))/r.lendiv
701
702 # high-precision step
703 step_hp(r::StepRangeLen) = r.step
704 step_hp(r::AbstractRange) = step(r)
705
706 axes(r::AbstractRange) = (oneto(length(r)),)
707
708 # Needed to ensure `has_offset_axes` can constant-fold.
709 has_offset_axes(::StepRange) = false
710
711 # n.b. checked_length for these is defined iff checked_add and checked_sub are
712 # defined between the relevant types
713 function checked_length(r::OrdinalRange{T}) where T
714 s = step(r)
715 start = first(r)
716 if isempty(r)
717 return Integer(div(start - start, oneunit(s)))
718 end
719 stop = last(r)
720 if isless(s, zero(s))
721 diff = checked_sub(start, stop)
722 s = -s
723 else
724 diff = checked_sub(stop, start)
725 end
726 a = div(diff, s)
727 return Integer(checked_add(a, oneunit(a)))
728 end
729
730 function checked_length(r::AbstractUnitRange{T}) where T
731 # compiler optimization: remove dead cases from above
732 if isempty(r)
733 return Integer(first(r) - first(r))
734 end
735 a = checked_sub(last(r), first(r))
736 return Integer(checked_add(a, oneunit(a)))
737 end
738
739 function length(r::OrdinalRange{T}) where T
740 s = step(r)
741 start = first(r)
742 if isempty(r)
743 return Integer(div(start - start, oneunit(s)))
744 end
745 stop = last(r)
746 if isless(s, zero(s))
747 diff = start - stop
748 s = -s
749 else
750 diff = stop - start
751 end
752 a = div(diff, s)
753 return Integer(a + oneunit(a))
754 end
755
756 function length(r::AbstractUnitRange{T}) where T
757 @inline
758 start, stop = first(r), last(r)
759 a = oneunit(zero(stop) - zero(start))
760 if a isa Signed || stop >= start
761 a += stop - start # Signed are allowed to go negative
762 else
763 a = zero(a) # Unsigned don't necessarily underflow
764 end
765 return Integer(a)
766 end
767
768 length(r::OneTo) = Integer(r.stop - zero(r.stop))
769 length(r::StepRangeLen) = r.len
770 length(r::LinRange) = r.len
771
772 let bigints = Union{Int, UInt, Int64, UInt64, Int128, UInt128},
773 smallints = (Int === Int64 ?
774 Union{Int8, UInt8, Int16, UInt16, Int32, UInt32} :
775 Union{Int8, UInt8, Int16, UInt16}),
776 bitints = Union{bigints, smallints}
777 global length, checked_length, firstindex
778 # compile optimization for which promote_type(T, Int) == T
779 length(r::OneTo{T}) where {T<:bigints} = r.stop
780 # slightly more accurate length and checked_length in extreme cases
781 # (near typemax) for types with known `unsigned` functions
782 function length(r::OrdinalRange{T}) where T<:bigints
783 s = step(r)
784 diff = last(r) - first(r)
785 isempty(r) && return zero(diff)
786 # if |s| > 1, diff might have overflowed, but unsigned(diff)÷s should
787 # therefore still be valid (if the result is representable at all)
788 # n.b. !(s isa T)
789 if s isa Unsigned || -1 <= s <= 1 || s == -s
790 a = div(diff, s) % typeof(diff)
791 elseif s < 0
792 a = div(unsigned(-diff), -s) % typeof(diff)
793 else
794 a = div(unsigned(diff), s) % typeof(diff)
795 end
796 return a + oneunit(a)
797 end
798 function checked_length(r::OrdinalRange{T}) where T<:bigints
799 s = step(r)
800 stop, start = last(r), first(r)
801 ET = promote_type(typeof(stop), typeof(start))
802 isempty(r) && return zero(ET)
803 # n.b. !(s isa T)
804 if s > 1
805 diff = stop - start
806 a = convert(ET, div(unsigned(diff), s))
807 elseif s < -1
808 diff = start - stop
809 a = convert(ET, div(unsigned(diff), -s))
810 elseif s > 0
811 a = convert(ET, div(checked_sub(stop, start), s))
812 else
813 a = convert(ET, div(checked_sub(start, stop), -s))
814 end
815 return checked_add(a, oneunit(a))
816 end
817 firstindex(r::StepRange{<:bigints,<:bitints}) = one(last(r)-first(r))
818
819 # some special cases to favor default Int type
820 function length(r::OrdinalRange{<:smallints})
821 s = step(r)
822 isempty(r) && return 0
823 # n.b. !(step isa T)
824 return Int(div(Int(last(r)) - Int(first(r)), s)) + 1
825 end
826 length(r::AbstractUnitRange{<:smallints}) = Int(last(r)) - Int(first(r)) + 1
827 length(r::OneTo{<:smallints}) = Int(r.stop)
828 checked_length(r::OrdinalRange{<:smallints}) = length(r)
829 checked_length(r::AbstractUnitRange{<:smallints}) = length(r)
830 checked_length(r::OneTo{<:smallints}) = length(r)
831 firstindex(::StepRange{<:smallints,<:bitints}) = 1
832 end
833
834 first(r::OrdinalRange{T}) where {T} = convert(T, r.start)
835 first(r::OneTo{T}) where {T} = oneunit(T)
836 first(r::StepRangeLen) = unsafe_getindex(r, 1)
837 first(r::LinRange) = r.start
838
839 last(r::OrdinalRange{T}) where {T} = convert(T, r.stop) # via steprange_last
840 last(r::StepRangeLen) = unsafe_getindex(r, length(r))
841 last(r::LinRange) = r.stop
842
843 minimum(r::AbstractUnitRange) = isempty(r) ? throw(ArgumentError("range must be non-empty")) : first(r)
844 maximum(r::AbstractUnitRange) = isempty(r) ? throw(ArgumentError("range must be non-empty")) : last(r)
845 minimum(r::AbstractRange) = isempty(r) ? throw(ArgumentError("range must be non-empty")) : min(first(r), last(r))
846 maximum(r::AbstractRange) = isempty(r) ? throw(ArgumentError("range must be non-empty")) : max(first(r), last(r))
847
848 """
849 argmin(r::AbstractRange)
850
851 Ranges can have multiple minimal elements. In that case
852 `argmin` will return a minimal index, but not necessarily the
853 first one.
854 """
855 function argmin(r::AbstractRange)
856 if isempty(r)
857 throw(ArgumentError("range must be non-empty"))
858 elseif step(r) > 0
859 firstindex(r)
860 else
861 lastindex(r)
862 end
863 end
864
865 """
866 argmax(r::AbstractRange)
867
868 Ranges can have multiple maximal elements. In that case
869 `argmax` will return a maximal index, but not necessarily the
870 first one.
871 """
872 function argmax(r::AbstractRange)
873 if isempty(r)
874 throw(ArgumentError("range must be non-empty"))
875 elseif step(r) > 0
876 lastindex(r)
877 else
878 firstindex(r)
879 end
880 end
881
882 extrema(r::AbstractRange) = (minimum(r), maximum(r))
883
884 # Ranges are immutable
885 copy(r::AbstractRange) = r
886
887
888 ## iteration
889
890 function iterate(r::Union{StepRangeLen,LinRange}, i::Integer=zero(length(r)))
891 @inline
892 i += oneunit(i)
893 length(r) < i && return nothing
894 unsafe_getindex(r, i), i
895 end
896
897 iterate(r::OrdinalRange) = isempty(r) ? nothing : (first(r), first(r))
898
899 function iterate(r::OrdinalRange{T}, i) where {T}
900 @inline
901 1 (2 %)
1 (2 %) samples spent in iterate
1 (100 %) (incl.) when called from residual! line 444
1 (100 %) samples spent calling ==
i == last(r) && return nothing
902 next = convert(T, i + step(r))
903 (next, next)
904 end
905
906 ## indexing
907
908 function isassigned(r::AbstractRange, i::Integer)
909 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
910 firstindex(r) <= i <= lastindex(r)
911 end
912
913 _in_unit_range(v::UnitRange, val, i::Integer) = i > 0 && val <= v.stop && val >= v.start
914
915 function getindex(v::UnitRange{T}, i::Integer) where T
916 @inline
917 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
918 val = convert(T, v.start + (i - oneunit(i)))
919 @boundscheck _in_unit_range(v, val, i) || throw_boundserror(v, i)
920 val
921 end
922
923 const OverflowSafe = Union{Bool,Int8,Int16,Int32,Int64,Int128,
924 UInt8,UInt16,UInt32,UInt64,UInt128}
925
926 function getindex(v::UnitRange{T}, i::Integer) where {T<:OverflowSafe}
927 @inline
928 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
929 val = v.start + (i - oneunit(i))
930 @boundscheck _in_unit_range(v, val, i) || throw_boundserror(v, i)
931 val % T
932 end
933
934 function getindex(v::OneTo{T}, i::Integer) where T
935 @inline
936 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
937 @boundscheck ((i > 0) & (i <= v.stop)) || throw_boundserror(v, i)
938 convert(T, i)
939 end
940
941 function getindex(v::AbstractRange{T}, i::Integer) where T
942 @inline
943 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
944 ret = convert(T, first(v) + (i - oneunit(i))*step_hp(v))
945 ok = ifelse(step(v) > zero(step(v)),
946 (ret <= last(v)) & (ret >= first(v)),
947 (ret <= first(v)) & (ret >= last(v)))
948 @boundscheck ((i > 0) & ok) || throw_boundserror(v, i)
949 ret
950 end
951
952 function getindex(r::Union{StepRangeLen,LinRange}, i::Integer)
953 @inline
954 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
955 @boundscheck checkbounds(r, i)
956 unsafe_getindex(r, i)
957 end
958
959 # This is separate to make it useful even when running with --check-bounds=yes
960 function unsafe_getindex(r::StepRangeLen{T}, i::Integer) where T
961 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
962 u = oftype(r.offset, i) - r.offset
963 T(r.ref + u*r.step)
964 end
965
966 function _getindex_hiprec(r::StepRangeLen, i::Integer) # without rounding by T
967 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
968 u = oftype(r.offset, i) - r.offset
969 r.ref + u*r.step
970 end
971
972 function unsafe_getindex(r::LinRange, i::Integer)
973 i isa Bool && throw(ArgumentError("invalid index: $i of type Bool"))
974 lerpi(i-oneunit(i), r.lendiv, r.start, r.stop)
975 end
976
977 function lerpi(j::Integer, d::Integer, a::T, b::T) where T
978 @inline
979 t = j/d # ∈ [0,1]
980 # compute approximately fma(t, b, -fma(t, a, a))
981 return T((1-t)*a + t*b)
982 end
983
984 getindex(r::AbstractRange, ::Colon) = copy(r)
985
986 function getindex(r::AbstractUnitRange, s::AbstractUnitRange{T}) where {T<:Integer}
987 @inline
988 @boundscheck checkbounds(r, s)
989
990 if T === Bool
991 return range(first(s) ? first(r) : last(r), length = last(s))
992 else
993 f = first(r)
994 start = oftype(f, f + first(s) - firstindex(r))
995 len = length(s)
996 stop = oftype(f, start + (len - oneunit(len)))
997 return range(start, stop)
998 end
999 end
1000
1001 function getindex(r::OneTo{T}, s::OneTo) where T
1002 @inline
1003 @boundscheck checkbounds(r, s)
1004 return OneTo(T(s.stop))
1005 end
1006
1007 function getindex(r::AbstractUnitRange, s::StepRange{T}) where {T<:Integer}
1008 @inline
1009 @boundscheck checkbounds(r, s)
1010
1011 if T === Bool
1012 return range(first(s) ? first(r) : last(r), step=oneunit(eltype(r)), length=last(s))
1013 else
1014 f = first(r)
1015 start = oftype(f, f + s.start - firstindex(r))
1016 st = step(s)
1017 len = length(s)
1018 stop = oftype(f, start + (len - oneunit(len)) * st)
1019 return range(start, stop; step=st)
1020 end
1021 end
1022
1023 function getindex(r::StepRange, s::AbstractRange{T}) where {T<:Integer}
1024 @inline
1025 @boundscheck checkbounds(r, s)
1026
1027 if T === Bool
1028 if length(s) == 0
1029 start, len = first(r), 0
1030 elseif length(s) == 1
1031 if first(s)
1032 start, len = first(r), 1
1033 else
1034 start, len = first(r), 0
1035 end
1036 else # length(s) == 2
1037 start, len = last(r), 1
1038 end
1039 return range(start, step=step(r); length=len)
1040 else
1041 f = r.start
1042 fs = first(s)
1043 st = r.step
1044 start = oftype(f, f + (fs - oneunit(fs)) * st)
1045 st = st * step(s)
1046 len = length(s)
1047 stop = oftype(f, start + (len - oneunit(len)) * st)
1048 return range(start, stop; step=st)
1049 end
1050 end
1051
1052 function getindex(r::StepRangeLen{T}, s::OrdinalRange{S}) where {T, S<:Integer}
1053 @inline
1054 @boundscheck checkbounds(r, s)
1055
1056 len = length(s)
1057 sstep = step_hp(s)
1058 rstep = step_hp(r)
1059 L = typeof(len)
1060 if S === Bool
1061 rstep *= one(sstep)
1062 if len == 0
1063 return StepRangeLen{T}(first(r), rstep, zero(L), oneunit(L))
1064 elseif len == 1
1065 if first(s)
1066 return StepRangeLen{T}(first(r), rstep, oneunit(L), oneunit(L))
1067 else
1068 return StepRangeLen{T}(first(r), rstep, zero(L), oneunit(L))
1069 end
1070 else # len == 2
1071 return StepRangeLen{T}(last(r), rstep, oneunit(L), oneunit(L))
1072 end
1073 else
1074 # Find closest approach to offset by s
1075 ind = LinearIndices(s)
1076 offset = L(max(min(1 + round(L, (r.offset - first(s))/sstep), last(ind)), first(ind)))
1077 ref = _getindex_hiprec(r, first(s) + (offset - oneunit(offset)) * sstep)
1078 return StepRangeLen{T}(ref, rstep*sstep, len, offset)
1079 end
1080 end
1081
1082 function getindex(r::LinRange{T}, s::OrdinalRange{S}) where {T, S<:Integer}
1083 @inline
1084 @boundscheck checkbounds(r, s)
1085
1086 len = length(s)
1087 L = typeof(len)
1088 if S === Bool
1089 if len == 0
1090 return LinRange{T}(first(r), first(r), len)
1091 elseif len == 1
1092 if first(s)
1093 return LinRange{T}(first(r), first(r), len)
1094 else
1095 return LinRange{T}(first(r), first(r), zero(L))
1096 end
1097 else # length(s) == 2
1098 return LinRange{T}(last(r), last(r), oneunit(L))
1099 end
1100 else
1101 vfirst = unsafe_getindex(r, first(s))
1102 vlast = unsafe_getindex(r, last(s))
1103 return LinRange{T}(vfirst, vlast, len)
1104 end
1105 end
1106
1107 show(io::IO, r::AbstractRange) = print(io, repr(first(r)), ':', repr(step(r)), ':', repr(last(r)))
1108 show(io::IO, r::UnitRange) = print(io, repr(first(r)), ':', repr(last(r)))
1109 show(io::IO, r::OneTo) = print(io, "Base.OneTo(", r.stop, ")")
1110 function show(io::IO, r::StepRangeLen)
1111 if !iszero(step(r))
1112 print(io, repr(first(r)), ':', repr(step(r)), ':', repr(last(r)))
1113 else
1114 # ugly temporary printing, to avoid 0:0:0 etc.
1115 print(io, "StepRangeLen(", repr(first(r)), ", ", repr(step(r)), ", ", repr(length(r)), ")")
1116 end
1117 end
1118
1119 function ==(r::T, s::T) where {T<:AbstractRange}
1120 isempty(r) && return isempty(s)
1121 _has_length_one(r) && return _has_length_one(s) & (first(r) == first(s))
1122 (first(r) == first(s)) & (step(r) == step(s)) & (last(r) == last(s))
1123 end
1124
1125 function ==(r::OrdinalRange, s::OrdinalRange)
1126 isempty(r) && return isempty(s)
1127 _has_length_one(r) && return _has_length_one(s) & (first(r) == first(s))
1128 (first(r) == first(s)) & (step(r) == step(s)) & (last(r) == last(s))
1129 end
1130
1131 ==(r::AbstractUnitRange, s::AbstractUnitRange) =
1132 (isempty(r) & isempty(s)) | ((first(r) == first(s)) & (last(r) == last(s)))
1133
1134 ==(r::OneTo, s::OneTo) = last(r) == last(s)
1135
1136 ==(r::T, s::T) where {T<:Union{StepRangeLen,LinRange}} =
1137 (isempty(r) & isempty(s)) | ((first(r) == first(s)) & (length(r) == length(s)) & (last(r) == last(s)))
1138
1139 function ==(r::Union{StepRange{T},StepRangeLen{T,T}}, s::Union{StepRange{T},StepRangeLen{T,T}}) where {T}
1140 isempty(r) && return isempty(s)
1141 _has_length_one(r) && return _has_length_one(s) & (first(r) == first(s))
1142 (first(r) == first(s)) & (step(r) == step(s)) & (last(r) == last(s))
1143 end
1144
1145 _has_length_one(r::OrdinalRange) = first(r) == last(r)
1146 _has_length_one(r::AbstractRange) = isone(length(r))
1147
1148 function ==(r::AbstractRange, s::AbstractRange)
1149 lr = length(r)
1150 if lr != length(s)
1151 return false
1152 elseif iszero(lr)
1153 return true
1154 end
1155 yr, ys = iterate(r), iterate(s)
1156 while yr !== nothing
1157 yr[1] == ys[1] || return false
1158 yr, ys = iterate(r, yr[2]), iterate(s, ys[2])
1159 end
1160 return true
1161 end
1162
1163 intersect(r::OneTo, s::OneTo) = OneTo(min(r.stop,s.stop))
1164 union(r::OneTo, s::OneTo) = OneTo(max(r.stop,s.stop))
1165
1166 intersect(r::AbstractUnitRange{<:Integer}, s::AbstractUnitRange{<:Integer}) = max(first(r),first(s)):min(last(r),last(s))
1167
1168 intersect(i::Integer, r::AbstractUnitRange{<:Integer}) = range(max(i, first(r)), length=in(i, r))
1169
1170 intersect(r::AbstractUnitRange{<:Integer}, i::Integer) = intersect(i, r)
1171
1172 function intersect(r::AbstractUnitRange{<:Integer}, s::StepRange{<:Integer})
1173 T = promote_type(eltype(r), eltype(s))
1174 if isempty(s)
1175 StepRange{T}(first(r), +step(s), first(r)-step(s))
1176 else
1177 sta, ste, sto = first_step_last_ascending(s)
1178 lo = first(r)
1179 hi = last(r)
1180 i0 = max(sta, lo + mod(sta - lo, ste))
1181 i1 = min(sto, hi - mod(hi - sta, ste))
1182 StepRange{T}(i0, ste, i1)
1183 end
1184 end
1185
1186 function first_step_last_ascending(r::StepRange)
1187 if step(r) < zero(step(r))
1188 last(r), -step(r), first(r)
1189 else
1190 first(r), +step(r), last(r)
1191 end
1192 end
1193
1194 function intersect(r::StepRange{<:Integer}, s::AbstractUnitRange{<:Integer})
1195 if step(r) < 0
1196 reverse(intersect(s, reverse(r)))
1197 else
1198 intersect(s, r)
1199 end
1200 end
1201
1202 function intersect(r::StepRange, s::StepRange)
1203 T = promote_type(eltype(r), eltype(s))
1204 S = promote_type(typeof(step(r)), typeof(step(s)))
1205 if isempty(r) || isempty(s)
1206 return StepRange{T,S}(first(r), step(r), first(r)-step(r))
1207 end
1208
1209 start1, step1, stop1 = first_step_last_ascending(r)
1210 start2, step2, stop2 = first_step_last_ascending(s)
1211 a = lcm(step1, step2)
1212
1213 g, x, y = gcdx(step1, step2)
1214
1215 if !iszero(rem(start1 - start2, g))
1216 # Unaligned, no overlap possible.
1217 if step(r) < zero(step(r))
1218 return StepRange{T,S}(stop1, -a, stop1+a)
1219 else
1220 return StepRange{T,S}(start1, a, start1-a)
1221 end
1222 end
1223
1224 z = div(start1 - start2, g)
1225 b = start1 - x * z * step1
1226 # Possible points of the intersection of r and s are
1227 # ..., b-2a, b-a, b, b+a, b+2a, ...
1228 # Determine where in the sequence to start and stop.
1229 m = max(start1 + mod(b - start1, a), start2 + mod(b - start2, a))
1230 n = min(stop1 - mod(stop1 - b, a), stop2 - mod(stop2 - b, a))
1231 step(r) < zero(step(r)) ? StepRange{T,S}(n, -a, m) : StepRange{T,S}(m, a, n)
1232 end
1233
1234 function intersect(r1::AbstractRange, r2::AbstractRange)
1235 # To iterate over the shorter range
1236 length(r1) > length(r2) && return intersect(r2, r1)
1237
1238 r1 = unique(r1)
1239 T = promote_eltype(r1, r2)
1240
1241 return T[x for x in r1 if x ∈ r2]
1242 end
1243
1244 function intersect(r1::AbstractRange, r2::AbstractRange, r3::AbstractRange, r::AbstractRange...)
1245 i = intersect(intersect(r1, r2), r3)
1246 for t in r
1247 i = intersect(i, t)
1248 end
1249 i
1250 end
1251
1252 # _findin (the index of intersection)
1253 function _findin(r::AbstractRange{<:Integer}, span::AbstractUnitRange{<:Integer})
1254 fspan = first(span)
1255 lspan = last(span)
1256 fr = first(r)
1257 lr = last(r)
1258 sr = step(r)
1259 if sr > 0
1260 ifirst = fr >= fspan ? 1 : cld(fspan-fr, sr)+1
1261 ilast = lr <= lspan ? length(r) : length(r) - cld(lr-lspan, sr)
1262 elseif sr < 0
1263 ifirst = fr <= lspan ? 1 : cld(lspan-fr, sr)+1
1264 ilast = lr >= fspan ? length(r) : length(r) - cld(lr-fspan, sr)
1265 else
1266 ifirst = fr >= fspan ? 1 : length(r)+1
1267 ilast = fr <= lspan ? length(r) : 0
1268 end
1269 r isa AbstractUnitRange ? (ifirst:ilast) : (ifirst:1:ilast)
1270 end
1271
1272 issubset(r::OneTo, s::OneTo) = r.stop <= s.stop
1273
1274 issubset(r::AbstractUnitRange{<:Integer}, s::AbstractUnitRange{<:Integer}) =
1275 isempty(r) || (first(r) >= first(s) && last(r) <= last(s))
1276
1277 ## linear operations on ranges ##
1278
1279 -(r::OrdinalRange) = range(-first(r), step=negate(step(r)), length=length(r))
1280 -(r::StepRangeLen{T,R,S,L}) where {T,R,S,L} =
1281 StepRangeLen{T,R,S,L}(-r.ref, -r.step, r.len, r.offset)
1282 function -(r::LinRange)
1283 start = -r.start
1284 LinRange{typeof(start)}(start, -r.stop, length(r))
1285 end
1286
1287 # promote eltype if at least one container wouldn't change, otherwise join container types.
1288 el_same(::Type{T}, a::Type{<:AbstractArray{T,n}}, b::Type{<:AbstractArray{T,n}}) where {T,n} = a # we assume a === b
1289 el_same(::Type{T}, a::Type{<:AbstractArray{T,n}}, b::Type{<:AbstractArray{S,n}}) where {T,S,n} = a
1290 el_same(::Type{T}, a::Type{<:AbstractArray{S,n}}, b::Type{<:AbstractArray{T,n}}) where {T,S,n} = b
1291 el_same(::Type, a, b) = promote_typejoin(a, b)
1292
1293 promote_rule(a::Type{UnitRange{T1}}, b::Type{UnitRange{T2}}) where {T1,T2} =
1294 el_same(promote_type(T1, T2), a, b)
1295 UnitRange{T}(r::UnitRange{T}) where {T<:Real} = r
1296 UnitRange{T}(r::UnitRange) where {T<:Real} = UnitRange{T}(r.start, r.stop)
1297
1298 promote_rule(a::Type{OneTo{T1}}, b::Type{OneTo{T2}}) where {T1,T2} =
1299 el_same(promote_type(T1, T2), a, b)
1300 OneTo{T}(r::OneTo{T}) where {T<:Integer} = r
1301 OneTo{T}(r::OneTo) where {T<:Integer} = OneTo{T}(r.stop)
1302
1303 promote_rule(a::Type{UnitRange{T1}}, ::Type{UR}) where {T1,UR<:AbstractUnitRange} =
1304 promote_rule(a, UnitRange{eltype(UR)})
1305 UnitRange{T}(r::AbstractUnitRange) where {T<:Real} = UnitRange{T}(first(r), last(r))
1306 UnitRange(r::AbstractUnitRange) = UnitRange(first(r), last(r))
1307
1308 AbstractUnitRange{T}(r::AbstractUnitRange{T}) where {T} = r
1309 AbstractUnitRange{T}(r::UnitRange) where {T} = UnitRange{T}(r)
1310 AbstractUnitRange{T}(r::OneTo) where {T} = OneTo{T}(r)
1311
1312 OrdinalRange{T, S}(r::OrdinalRange) where {T, S} = StepRange{T, S}(r)
1313 OrdinalRange{T, T}(r::AbstractUnitRange) where {T} = AbstractUnitRange{T}(r)
1314
1315 function promote_rule(::Type{StepRange{T1a,T1b}}, ::Type{StepRange{T2a,T2b}}) where {T1a,T1b,T2a,T2b}
1316 Tb = promote_type(T1b, T2b)
1317 # el_same only operates on array element type, so just promote second type parameter
1318 el_same(promote_type(T1a, T2a), StepRange{T1a,Tb}, StepRange{T2a,Tb})
1319 end
1320 StepRange{T1,T2}(r::StepRange{T1,T2}) where {T1,T2} = r
1321
1322 promote_rule(a::Type{StepRange{T1a,T1b}}, ::Type{UR}) where {T1a,T1b,UR<:AbstractUnitRange} =
1323 promote_rule(a, StepRange{eltype(UR), eltype(UR)})
1324 StepRange{T1,T2}(r::AbstractRange) where {T1,T2} =
1325 StepRange{T1,T2}(convert(T1, first(r)), convert(T2, step(r)), convert(T1, last(r)))
1326 StepRange(r::AbstractUnitRange{T}) where {T} =
1327 StepRange{T,T}(first(r), step(r), last(r))
1328 (StepRange{T1,T2} where T1)(r::AbstractRange) where {T2} = StepRange{eltype(r),T2}(r)
1329
1330 function promote_rule(::Type{StepRangeLen{T1,R1,S1,L1}},::Type{StepRangeLen{T2,R2,S2,L2}}) where {T1,T2,R1,R2,S1,S2,L1,L2}
1331 R, S, L = promote_type(R1, R2), promote_type(S1, S2), promote_type(L1, L2)
1332 el_same(promote_type(T1, T2), StepRangeLen{T1,R,S,L}, StepRangeLen{T2,R,S,L})
1333 end
1334 StepRangeLen{T,R,S,L}(r::StepRangeLen{T,R,S,L}) where {T,R,S,L} = r
1335 StepRangeLen{T,R,S,L}(r::StepRangeLen) where {T,R,S,L} =
1336 StepRangeLen{T,R,S,L}(convert(R, r.ref), convert(S, r.step), convert(L, r.len), convert(L, r.offset))
1337 StepRangeLen{T}(r::StepRangeLen) where {T} =
1338 StepRangeLen(convert(T, r.ref), convert(T, r.step), r.len, r.offset)
1339
1340 promote_rule(a::Type{StepRangeLen{T,R,S,L}}, ::Type{OR}) where {T,R,S,L,OR<:AbstractRange} =
1341 promote_rule(a, StepRangeLen{eltype(OR), eltype(OR), eltype(OR), Int})
1342 StepRangeLen{T,R,S,L}(r::AbstractRange) where {T,R,S,L} =
1343 StepRangeLen{T,R,S,L}(R(first(r)), S(step(r)), length(r))
1344 StepRangeLen{T}(r::AbstractRange) where {T} =
1345 StepRangeLen(T(first(r)), T(step(r)), length(r))
1346 StepRangeLen(r::AbstractRange) = StepRangeLen{eltype(r)}(r)
1347
1348 function promote_rule(a::Type{LinRange{T1,L1}}, b::Type{LinRange{T2,L2}}) where {T1,T2,L1,L2}
1349 L = promote_type(L1, L2)
1350 el_same(promote_type(T1, T2), LinRange{T1,L}, LinRange{T2,L})
1351 end
1352 LinRange{T,L}(r::LinRange{T,L}) where {T,L} = r
1353 LinRange{T,L}(r::AbstractRange) where {T,L} = LinRange{T,L}(first(r), last(r), length(r))
1354 LinRange{T}(r::AbstractRange) where {T} = LinRange{T,typeof(length(r))}(first(r), last(r), length(r))
1355 LinRange(r::AbstractRange{T}) where {T} = LinRange{T}(r)
1356
1357 promote_rule(a::Type{LinRange{T,L}}, ::Type{OR}) where {T,L,OR<:OrdinalRange} =
1358 promote_rule(a, LinRange{eltype(OR),L})
1359
1360 promote_rule(::Type{LinRange{A,L}}, b::Type{StepRangeLen{T2,R2,S2,L2}}) where {A,L,T2,R2,S2,L2} =
1361 promote_rule(StepRangeLen{A,A,A,L}, b)
1362
1363 ## concatenation ##
1364
1365 function vcat(rs::AbstractRange{T}...) where T
1366 n::Int = 0
1367 for ra in rs
1368 n += length(ra)
1369 end
1370 a = Vector{T}(undef, n)
1371 i = 1
1372 for ra in rs, x in ra
1373 @inbounds a[i] = x
1374 i += 1
1375 end
1376 return a
1377 end
1378
1379 # This method differs from that for AbstractArrays as it
1380 # use iteration instead of indexing. This works even if certain
1381 # non-standard ranges don't support indexing.
1382 # See https://github.com/JuliaLang/julia/pull/27302
1383 # Similarly, collect(r::AbstractRange) uses iteration
1384 function Array{T,1}(r::AbstractRange{T}) where {T}
1385 a = Vector{T}(undef, length(r))
1386 i = 1
1387 for x in r
1388 @inbounds a[i] = x
1389 i += 1
1390 end
1391 return a
1392 end
1393 collect(r::AbstractRange) = Array(r)
1394
1395 _reverse(r::OrdinalRange, ::Colon) = (:)(last(r), negate(step(r)), first(r))
1396 function _reverse(r::StepRangeLen, ::Colon)
1397 # If `r` is empty, `length(r) - r.offset + 1 will be nonpositive hence
1398 # invalid. As `reverse(r)` is also empty, any offset would work so we keep
1399 # `r.offset`
1400 offset = isempty(r) ? r.offset : length(r)-r.offset+1
1401 return typeof(r)(r.ref, negate(r.step), length(r), offset)
1402 end
1403 _reverse(r::LinRange{T}, ::Colon) where {T} = typeof(r)(r.stop, r.start, length(r))
1404
1405 ## sorting ##
1406
1407 issorted(r::AbstractUnitRange) = true
1408 issorted(r::AbstractRange) = length(r) <= 1 || step(r) >= zero(step(r))
1409
1410 sort(r::AbstractUnitRange) = r
1411 sort!(r::AbstractUnitRange) = r
1412
1413 sort(r::AbstractRange) = issorted(r) ? r : reverse(r)
1414
1415 sortperm(r::AbstractUnitRange) = 1:length(r)
1416 sortperm(r::AbstractRange) = issorted(r) ? (1:1:length(r)) : (length(r):-1:1)
1417
1418 function sum(r::AbstractRange{<:Real})
1419 l = length(r)
1420 # note that a little care is required to avoid overflow in l*(l-1)/2
1421 return l * first(r) + (iseven(l) ? (step(r) * (l-1)) * (l>>1)
1422 : (step(r) * l) * ((l-1)>>1))
1423 end
1424
1425 function _in_range(x, r::AbstractRange)
1426 isempty(r) && return false
1427 f, l = first(r), last(r)
1428 # check for NaN, Inf, and large x that may overflow in the next calculation
1429 f <= x <= l || l <= x <= f || return false
1430 iszero(step(r)) && return true
1431 n = round(Integer, (x - f) / step(r)) + 1
1432 n >= 1 && n <= length(r) && r[n] == x
1433 end
1434 in(x::Real, r::AbstractRange{<:Real}) = _in_range(x, r)
1435 # This method needs to be defined separately since -(::T, ::T) can be implemented
1436 # even if -(::T, ::Real) is not
1437 in(x::T, r::AbstractRange{T}) where {T} = _in_range(x, r)
1438
1439 in(x::Integer, r::AbstractUnitRange{<:Integer}) = (first(r) <= x) & (x <= last(r))
1440
1441 in(x::Real, r::AbstractRange{T}) where {T<:Integer} =
1442 isinteger(x) && !isempty(r) &&
1443 (iszero(step(r)) ? x == first(r) : (x >= minimum(r) && x <= maximum(r) &&
1444 (mod(convert(T,x),step(r))-mod(first(r),step(r)) == 0)))
1445 in(x::AbstractChar, r::AbstractRange{<:AbstractChar}) =
1446 !isempty(r) &&
1447 (iszero(step(r)) ? x == first(r) : (x >= minimum(r) && x <= maximum(r) &&
1448 (mod(Int(x) - Int(first(r)), step(r)) == 0)))
1449
1450 # Addition/subtraction of ranges
1451
1452 function _define_range_op(@nospecialize f)
1453 @eval begin
1454 function $f(r1::OrdinalRange, r2::OrdinalRange)
1455 r1l = length(r1)
1456 (r1l == length(r2) ||
1457 throw(DimensionMismatch("argument dimensions must match: length of r1 is $r1l, length of r2 is $(length(r2))")))
1458 StepRangeLen($f(first(r1), first(r2)), $f(step(r1), step(r2)), r1l)
1459 end
1460
1461 function $f(r1::LinRange{T}, r2::LinRange{T}) where T
1462 len = r1.len
1463 (len == r2.len ||
1464 throw(DimensionMismatch("argument dimensions must match: length of r1 is $len, length of r2 is $(r2.len)")))
1465 LinRange{T}(convert(T, $f(first(r1), first(r2))),
1466 convert(T, $f(last(r1), last(r2))), len)
1467 end
1468
1469 $f(r1::Union{StepRangeLen, OrdinalRange, LinRange},
1470 r2::Union{StepRangeLen, OrdinalRange, LinRange}) =
1471 $f(promote(r1, r2)...)
1472 end
1473 end
1474 _define_range_op(:+)
1475 _define_range_op(:-)
1476
1477 function +(r1::StepRangeLen{T,S}, r2::StepRangeLen{T,S}) where {T,S}
1478 len = length(r1)
1479 (len == length(r2) ||
1480 throw(DimensionMismatch("argument dimensions must match: length of r1 is $len, length of r2 is $(length(r2))")))
1481 StepRangeLen(first(r1)+first(r2), step(r1)+step(r2), len)
1482 end
1483
1484 -(r1::StepRangeLen, r2::StepRangeLen) = +(r1, -r2)
1485
1486 # Modular arithmetic on ranges
1487
1488 """
1489 mod(x::Integer, r::AbstractUnitRange)
1490
1491 Find `y` in the range `r` such that ``x ≡ y (mod n)``, where `n = length(r)`,
1492 i.e. `y = mod(x - first(r), n) + first(r)`.
1493
1494 See also [`mod1`](@ref).
1495
1496 # Examples
1497 ```jldoctest
1498 julia> mod(0, Base.OneTo(3)) # mod1(0, 3)
1499 3
1500
1501 julia> mod(3, 0:2) # mod(3, 3)
1502 0
1503 ```
1504
1505 !!! compat "Julia 1.3"
1506 This method requires at least Julia 1.3.
1507 """
1508 mod(i::Integer, r::OneTo) = mod1(i, last(r))
1509 mod(i::Integer, r::AbstractUnitRange{<:Integer}) = mod(i-first(r), length(r)) + first(r)