Implementing Reverse for Take, Drop, TakeWhile, & DropWhile

header.jl

import .Iterators: Reverse, Take, Drop, DropWhile, TakeWhile, tail
import .Iterators: reverse, take, drop, takewhile, dropwhile
import .Iterators: Filter, filter, Cycle, cycle, Enumerate, enumerate
import .Base: IteratorSize, SizeUnknown, IsInfinite, HasLength, HasShape
import .Base: IteratorEltype, HasEltype
import Base: iterate, IteratorSize
const FiniteLength = Union{HasLength, HasShape}

### Functions for iterate.jl & reverse.jl

function drop_n(xs, n)
    y = iterate(xs)
    for i in 1:n
        y == nothing && return y
        y = iterate(xs, y[2])
    end
    y
end

function take_n(xs, n, state)
    n <= 0 && return nothing
    y = iterate(xs, state...)
    y === nothing && return nothing
    return y[1], (n - 1, y[2])
end

@inline revn(itr,n) = max(0, length(itr) - n)

function countwhile(pred, itr)
    n = 0
    for element in itr
        pred(element) || return n
        n += 1
    end
    n
end

### DropList structure for last.jl, last_reversable.jl and iterate_last.jl
#   O(1) push & popfirst.
#   to keep a constant number of changing elements for a indefinite amount of time.

mutable struct DropListCell{T}
    element::T
    next::Union{DropListCell{T}, Nothing}
end

mutable struct DropList{T}
    start::Union{DropListCell{T}, Nothing}
    final::Union{DropListCell{T}, Nothing}
    len::Int
    function DropList{T}() where T
        new{T}(nothing, nothing, 0)
    end
end

function Base.popfirst!(list::DropList)
    value = list.start.element
    if list.start === list.final
        list.final = list.start = nothing
    else
        list.start = list.start.next
    end
    list.len -= 1
    return value
end

function Base.push!(list::DropList{T}, element) where T
    if list.final === nothing
        list.final = list.start = DropListCell{T}(element, nothing)
    else
        list.final.next = DropListCell{T}(element, nothing)
        list.final = list.final.next
    end
    list.len += 1
    return list
end

function Base.length(list::DropList)
    list.len
end

function Base.isempty(list::DropList)
    list.start === nothing
end

function Base.empty!(list::DropList)
    list.start = list.final = nothing
    list.len = 0
end

### Types aliases and functions for last.jl, last_reversable.jl and iterate_last.jl

const IndexableItr = Union{Tuple, AbstractArray, AbstractString, AbstractRange}

nth(r::AbstractRange, n::Integer) = r[n]
function nth(elements, n::Integer)
    m = n
    for element in elements
        n == 1 && return element
        n -= 1
    end
    throw(BoundsError(elements, m))
end


### consts

const uncommon_length_support = Ref(false)

iterate.jl

include("./header.jl")

## Take

function iterate(rev::Reverse{<:Take})
    xs = reverse(rev.itr.xs)
    n = revn(xs,rev.itr.n)
    drop_n(xs, n)
end
iterate(rev::Reverse{<:Take}, state) = iterate(reverse(rev.itr.xs), state)

## Drop

function iterate(rev::Reverse{<:Drop}, state=(revn(rev.itr.xs, rev.itr.n),))
    xs = reverse(rev.itr.xs)
    take_n(xs, state[1], tail(state))
end

## TakeWhile

function iterate(rev::Reverse{<:TakeWhile})
    xs = reverse(rev.itr.xs)
    n = revn(xs, countwhile(rev.itr.pred, rev.itr.xs))
    drop_n(xs, n)
end
iterate(rev::Reverse{<:TakeWhile}, state) = iterate(reverse(rev.itr.xs), state)

## DropWhile

function iterate(rev::Reverse{<:DropWhile}, state=(revn(rev.itr.xs, countwhile(rev.itr.pred, rev.itr.xs)),))
    xs = reverse(rev.itr.xs)
    take_n(xs, state[1], tail(state))
end

iterate_last.jl

include("header.jl")

takelast(itr, n::Integer) = reverse(take(reverse(itr), n))
droplast(itr, n::Integer) = reverse(drop(reverse(itr), n))
takelastwhile(pred, itr) = reverse(takewhile(pred, reverse(itr)))
droplastwhile(pred, itr) = reverse(dropwhile(pred, reverse(itr)))

uncommon_length_support[] = true

## Reverse{<:Take}

function iterate(it::Reverse{Take{T}}) where T<:IndexableItr
    xs = it.itr.xs
    len = min(it.itr.n, length(xs))
    len <= 0 && return nothing
    i = nth(eachindex(xs), len)
    xs[i], (prevind(xs, firstindex(xs)), prevind(xs, i))
end

function iterate(it::Reverse{Take{T}}, state) where T<:IndexableItr
    stop, i = state
    xs = it.itr.xs
    if i == stop
        nothing
    else
        xs[i], (stop, prevind(xs, i))
    end
end

function iterate(it::Reverse{<:Take})
    it = it.itr
    elements = collect(take(it.xs, it.n))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate(it::Reverse{<:Take}, state)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## Reverse{<:Drop}

function iterate(it::Reverse{<:Drop}, state...)
    iterate_revdrop(it.itr, state..., IteratorSize(it))
end

function iterate_revdrop(it, ::HasLength)
    rev = reverse(it.xs)
    n = length(it.xs) - it.n
    n <= 0 && return nothing
    y = iterate(rev)
    y[1], (y[2], rev, n-1)
end

function iterate_revdrop(it, state, ::HasLength)
    state, rev, n = state
    n == 0 && return nothing
    y = iterate(rev, state)
    y[1], (y[2], rev, n-1)
end

function iterate_revdrop(it, ::IteratorSize)
    rev = reverse(it.xs)
    elements = DropList{eltype(it)}()
    state = ()
    for i in 1:(it.n+1)
        y = iterate(rev, state...)
        y === nothing && return nothing
        state = (y[2],)
        push!(elements, y[1])
    end
    popfirst!(elements), (state[1], rev, elements)
end

function iterate_revdrop(it, state, ::IteratorSize)
    state, rev, elements = state
    y = iterate(rev, state)
    y === nothing && return nothing
    push!(elements, y[1])
    popfirst!(elements), (y[2], rev, elements)
end

## Reverse{<:TakeWhile}

function iterate(it::Reverse{TakeWhile{T,P}}) where {T<:IndexableItr,P<:Function}
    it = it.itr
    local j = nothing
    for i in eachindex(it.xs)
        if it.pred(it.xs[i])
            j = i
        else
            break
        end
    end
    j === nothing && return nothing
    it.xs[j], (prevind(it.xs, firstindex(it.xs)), prevind(it.xs, j))
end

function iterate(it::Reverse{TakeWhile{T,P}}, state) where {T<:IndexableItr,P<:Function}
    it = it.itr
    stop, i = state
    if i == stop
        nothing
    else
        it.xs[i], (stop, prevind(it.xs, i))
    end
end

function iterate(it::Reverse{<:TakeWhile})
    it = it.itr
    elements = collect(takewhile(it.pred, it.xs))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate(it::Reverse{<:TakeWhile}, state)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## Reverse{<:DropWhile}

function iterate_revdropwhile(pred, xs, y, trues, elements)
    while y !== nothing
        if pred(y[1])
            push!(trues, y[1])
        else
            if isempty(trues)
                push!(elements, y[1])
            else
                push!(trues, y[1])
                append!(elements, trues)
                empty!(trues)
            end
            break
        end
        y = iterate(xs, y[2])
    end
    return y
end

function iterate(it::Reverse{<:DropWhile}, state=(1, reverse(it.itr.xs), eltype(it)[], eltype(it)[], ()))
    pred = it.itr.pred
    i, rev, trues, elements, state = state
    if i > length(elements)
        y = state === nothing ? nothing : iterate(rev, state...)
        y = iterate_revdropwhile(pred, rev, y, trues, elements)
        if i > length(elements)
            return nothing
        else
            state = y === nothing ? nothing : (y[2],)
        end
    end
    elements[i], (i+1, rev, trues, elements, state)
end

iterate_last_traits.jl

include("header.jl")
include("traits.jl")

takelast(itr, n::Integer) = reverse(take(reverse(itr), n))
droplast(itr, n::Integer) = reverse(drop(reverse(itr), n))
takelastwhile(pred, itr) = reverse(takewhile(pred, reverse(itr)))
droplastwhile(pred, itr) = reverse(dropwhile(pred, reverse(itr)))

uncommon_length_support[] = true

## Reverse{<:Take}

function iterate(it::Reverse{<:Take}, state...)
    xs = it.itr.xs
    iterate_rtake(it.itr, state...,
                  IteratorSize(xs), IteratorReversed(xs), IteratorIndexable(xs))
end


function iterate_rtake(it, ::FiniteLength, ::IteratorReversed, ::Indexable)
    xs = it.xs
    len = min(it.n, length(xs))
    len <= 0 && return nothing
    i = nth(eachindex(xs), len)
    xs[i], (prevind(xs, firstindex(xs)), prevind(xs, i))
end

function iterate_rtake(it, state, ::FiniteLength, ::IteratorReversed, ::Indexable)
    stop, i = state
    xs = it.xs
    if i == stop
        nothing
    else
        xs[i], (stop, prevind(xs, i))
    end
end

function iterate_rtake(it, ::FiniteLength, ::Reversed, ::NotIndexable)
    elements = DropList{eltype(it)}()
    for element in reverse(it.xs)
        push!(elements, element)
        if length(elements) > it.n
            popfirst!(elements)
        end
    end
    isempty(elements) && return nothing
    popfirst!(elements), elements
end

function iterate_rtake(it, elements, ::FiniteLength, ::Reversed, ::NotIndexable)
    if isempty(elements)
        nothing
    else
        popfirst!(elements), elements
    end
end

function iterate_rtake(it, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    elements = collect(take(it.xs, it.n))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_rtake(it, state, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## Reverse{<:Drop}

function iterate(it::Reverse{<:Drop}, state...)
    xs = it.itr.xs
    iterate_rdrop(it.itr, state...,
                  IteratorSize(xs), IteratorReversed(xs))
end

function iterate_rdrop(it, ::FiniteLength, ::NotReversed)
    elements = collect(drop(it.xs, it.n))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_rdrop(it, state, ::FiniteLength, ::NotReversed)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

function iterate_rdrop(it, ::FiniteLength, ::Reversed)
    rev = reverse(it.xs)
    n = length(it.xs) - it.n
    n <= 0 && return nothing
    y = iterate(rev)
    y[1], (y[2], rev, n-1)
end

function iterate_rdrop(it, state, ::FiniteLength, ::Reversed)
    state, rev, n = state
    n == 0 && return nothing
    y = iterate(rev, state)
    y[1], (y[2], rev, n-1)
end

function iterate_rdrop(it, ::IteratorSize, ::IteratorReversed)
    rev = reverse(it.xs)
    elements = DropList{eltype(it)}()
    state = ()
    for i in 1:(it.n+1)
        y = iterate(rev, state...)
        y === nothing && return nothing
        state = (y[2],)
        push!(elements, y[1])
    end
    popfirst!(elements), (state[1], rev, elements)
end

function iterate_rdrop(it, state, ::IteratorSize, ::IteratorReversed)
    state, rev, elements = state
    y = iterate(rev, state)
    y === nothing && return nothing
    push!(elements, y[1])
    popfirst!(elements), (y[2], rev, elements)
end

## Reverse{<:TakeWhile}

function iterate(it::Reverse{<:TakeWhile}, state...)
    xs = it.itr.xs
    iterate_rtakewhile(it.itr, state...,
                       IteratorSize(xs), IteratorReversed(xs), IteratorIndexable(xs))
end


function iterate_rtakewhile(it, ::FiniteLength, ::IteratorReversed, ::Indexable)
    local j = nothing
    for i in eachindex(it.xs)
        if it.pred(it.xs[i])
            j = i
        else break
        end
    end
    j === nothing && return nothing
    it.xs[j], (prevind(it.xs, firstindex(it.xs)), prevind(it.xs, j))
end

function iterate_rtakewhile(it, state, ::FiniteLength, ::IteratorReversed, ::Indexable)
    stop, i = state
    if i == stop
        nothing
    else
        it.xs[i], (stop, prevind(it.xs, i))
    end
end

function iterate_rtakewhile(it, ::FiniteLength, ::Reversed, ::NotIndexable)
    elements = eltype(it)[]
    for element in reverse(it.xs)
        if it.pred(element)
            push!(elements, element)
        else
            empty!(elements)
        end
    end
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_rtakewhile(it, state, ::FiniteLength, ::Reversed, ::NotIndexable)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

function iterate_rtakewhile(it, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    elements = collect(takewhile(it.pred, it.xs))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_rtakewhile(it, state, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## Reverse{<:DropWhile}

function iterate(it::Reverse{<:DropWhile}, state...)
    xs = it.itr.xs
    iterate_rdropwhile(it.itr, state...,
                       IteratorReversed(xs), IteratorSize(xs))
end

function iterate_rdropwhile(it, ::NotReversed, ::FiniteLength)
    elements = collect(dropwhile(it.pred, it.xs))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_rdropwhile(it, state, ::NotReversed, ::FiniteLength)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

function iterate_rdropwhile(it, R::IteratorReversed, S::IteratorSize)
    trues = eltype(it)[]
    elements = eltype(it)[]
    rev = reverse(it.xs)
    iterate_rdropwhile(it, (1, rev, trues, elements, ()), R, S)
end

function iterate_rdropwhile(it, state, ::IteratorReversed, ::IteratorSize)
    i, rev, trues, elements, state = state
    if i > length(elements)
        y = state === nothing ? nothing : iterate(rev, state...)
        y = _iterate_rdropwhile(it.pred, rev, y, trues, elements)
        if i > length(elements)
            return nothing
        else
            state = y === nothing ? nothing : (y[2],)
        end
    end
    elements[i], (i+1, rev, trues, elements, state)
end

function _iterate_rdropwhile(pred, xs, y, trues, elements)
    while y !== nothing
        if pred(y[1])
            push!(trues, y[1])
        else
            if isempty(trues)
                push!(elements, y[1])
            else
                push!(trues, y[1])
                append!(elements, trues)
                empty!(trues)
            end
            break
        end
        y = iterate(xs, y[2])
    end
    return y
end

last.jl

import .Iterators: Filter, Cycle, cycle, IteratorSize, SizeUnknown, IsInfinite, IteratorEltype

include("./header.jl")

uncommon_length_support[] = true

### reverse Base iterators

reverse(itr::Take) = takelast(reverse(itr.xs), itr.n)
reverse(itr::Drop) = droplast(reverse(itr.xs), itr.n)
reverse(itr::TakeWhile) = takelastwhile(itr.pred, reverse(itr.xs))
reverse(itr::DropWhile) = droplastwhile(itr.pred, reverse(itr.xs))

### Type Declarations

struct DropLast{T}
    xs::T
    n::Int
end

struct TakeLast{T}
    xs::T
    n::Int
end

struct TakeLastWhile{T,F}
    pred::F
    xs::T
end

struct DropLastWhile{T,F}
    pred::F
    xs::T
end

### reverse new iterators

reverse(itr::TakeLast) = take(reverse(itr.xs), itr.n)
reverse(itr::DropLast) = drop(reverse(itr.xs), itr.n)
reverse(itr::TakeLastWhile) = takewhile(itr.pred, reverse(itr.xs))
reverse(itr::DropLastWhile) = dropwhile(itr.pred, reverse(itr.xs))

### constructor functions

function droplast(itr, n::Integer)
    DropLast(itr, n)
end
droplast(itr::TakeLast, n::Integer) =
  TakeLast(DropLast(itr.xs, Int(n)), max(0, Int(n) - itr.n))

function takelast(itr, n::Integer)
    TakeLast(itr, n)
end

function takelastwhile(pred, itr)
    TakeLastWhile(pred, itr)
end

function droplastwhile(pred, itr)
    DropLastWhile(pred, itr)
end

### length & trait functions

Base.length(it::DropLast) = Iterators._diff_length(it.xs, 1:it.n, IteratorSize(it.xs), Iterators.HasLength())
Base.length(it::TakeLast) = Iterators._min_length(it.xs, 1:it.n, IteratorSize(it.xs), Iterators.HasLength())

IteratorSize(::Type{DropLast{T}}) where T = Iterators.drop_iteratorsize(IteratorSize(T))
IteratorSize(::Type{TakeLast{T}}) where T = Iterators.take_iteratorsize(IteratorSize(T))
IteratorSize(::Type{TakeLastWhile{T,F}}) where {T,F} = Iterators.SizeUnknown()
IteratorSize(::Type{DropLastWhile{T,F}}) where {T,F} = Iterators.SizeUnknown()

IteratorEltype(::Type{DropLast{T}}) where T = IteratorEltype(T)
IteratorEltype(::Type{TakeLast{T}}) where T = IteratorEltype(T)
IteratorEltype(::Type{TakeLastWhile{T}}) where T = IteratorEltype(T)
IteratorEltype(::Type{DropLastWhile{T}}) where T = IteratorEltype(T)

### iterate

## TakeLast

function iterate(it::TakeLast{<:IndexableItr})
    xs = it.xs
    len = length(xs) - min(it.n, length(xs)) + 1
    len <= 0 && return nothing
    i = nth(eachindex(xs), len)
    xs[i], (nextind(xs, lastindex(xs)), (nextind(xs, i)))
end

function iterate(it::TakeLast{<:IndexableItr}, state)
    stop, i = state
    xs = it.xs
    if i == stop
        nothing
    else
        xs[i], (stop, nextind(xs, i))
    end
end

function iterate(it::TakeLast)
    elements = collect(take(reverse(it.xs), it.n))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate(it::TakeLast, state)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## DropLast

function iterate(it::DropLast, state...)
    iterate_droplast(it, state..., IteratorSize(it))
end

function iterate_droplast(it, ::HasLength)
    n = length(it.xs) - it.n
    n <= 0 && return nothing
    y = iterate(it.xs)
    y[1], (y[2], n-1)
end

function iterate_droplast(it, state, ::HasLength)
    state, n = state
    n == 0 && return nothing
    y = iterate(it.xs, state)
    y[1], (y[2], n-1)
end

function iterate_droplast(it, ::IteratorSize)
    elements = DropList{eltype(it)}()
    state = ()
    for i in 1:(it.n+1)
        y = iterate(it.xs, state...)
        y == nothing && return nothing
        state = (y[2],)
        push!(elements, y[1])
    end
    popfirst!(elements), (state[1], elements)
end


function iterate_droplast(it, state, ::IteratorSize)
    state, elements = state
    y = iterate(it.xs, state)
    y === nothing && return nothing
    push!(elements, y[1])
    popfirst!(elements), (y[2], elements)
end

## TakeLastWhile

function iterate(it::TakeLastWhile{<:IndexableItr})
    local j = nothing
    for i in reverse(eachindex(it.xs))
        if it.pred(it.xs[i])
            j = i
        else
            break
        end
    end
    j === nothing && return nothing
    it.xs[j], (nextind(it.xs, lastindex(it.xs)), nextind(it.xs, j))
end

function iterate(it::TakeLastWhile{<:IndexableItr}, state)
    stop, i = state
    if i == stop
        nothing
    else
        it.xs[i], (stop, nextind(it.xs, i))
    end
end

function iterate(it::TakeLastWhile)
    elements = collect(takewhile(it.pred, reverse(it.xs)))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate(it::TakeLastWhile, state)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## DropLastWhile

function iterate_droplastwhile(it, y, trues, elements)
    while y !== nothing
        if it.pred(y[1])
            push!(trues, y[1])
        else
            if isempty(trues)
                push!(elements, y[1])
            else
                push!(trues, y[1])
                append!(elements, trues)
                empty!(trues)
            end
            break
        end
        y = iterate(it.xs, y[2])
    end
    return y
end

function iterate(it::DropLastWhile, state=(1, eltype(it)[], eltype(it)[], ()))
    i, trues, elements, state = state
    if i > length(elements)
        y = state === nothing ? nothing : iterate(it.xs, state...)
        y = iterate_droplastwhile(it, y, trues, elements)
        if i > length(elements)
            return nothing
        else
            state = y === nothing ? nothing : (y[2],)
        end
    end
    elements[i], (i+1, trues, elements, state)
end

last_traits.jl

include("./header.jl")

uncommon_length_support[] = true

### reverse Base iterators

reverse(itr::Take) = takelast(reverse(itr.xs), itr.n)
reverse(itr::Drop) = droplast(reverse(itr.xs), itr.n)
reverse(itr::TakeWhile) = takelastwhile(itr.pred, reverse(itr.xs))
reverse(itr::DropWhile) = droplastwhile(itr.pred, reverse(itr.xs))

### Type Declarations

struct DropLast{T}
    xs::T
    n::Int
end

struct TakeLast{T}
    xs::T
    n::Int
end

struct TakeLastWhile{T,F}
    pred::F
    xs::T
end

struct DropLastWhile{T,F}
    pred::F
    xs::T
end

### reverse new iterators

reverse(itr::TakeLast) = take(reverse(itr.xs), itr.n)
reverse(itr::DropLast) = drop(reverse(itr.xs), itr.n)
reverse(itr::TakeLastWhile) = takewhile(itr.pred, reverse(itr.xs))
reverse(itr::DropLastWhile) = dropwhile(itr.pred, reverse(itr.xs))

### constructor functions

function droplast(itr, n::Integer)
    DropLast(itr, n)
end
droplast(itr::TakeLast, n::Integer) =
  TakeLast(DropLast(itr.xs, Int(n)), max(0, Int(n) - itr.n))

function takelast(itr, n::Integer)
    TakeLast(itr, n)
end

function takelastwhile(pred, itr)
    TakeLastWhile(pred, itr)
end

function droplastwhile(pred, itr)
    DropLastWhile(pred, itr)
end


### length & trait functions

Base.length(it::DropLast) = Iterators._diff_length(it.xs, 1:it.n, IteratorSize(it.xs), Iterators.HasLength())
Base.length(it::TakeLast) = Iterators._min_length(it.xs, 1:it.n, IteratorSize(it.xs), Iterators.HasLength())

IteratorSize(::Type{DropLast{T}}) where T = Iterators.drop_iteratorsize(IteratorSize(T))
IteratorSize(::Type{TakeLast{T}}) where T = Iterators.take_iteratorsize(IteratorSize(T))
IteratorSize(::Type{TakeLastWhile{T,F}}) where {T,F} = Iterators.SizeUnknown()
IteratorSize(::Type{DropLastWhile{T,F}}) where {T,F} = Iterators.SizeUnknown()

IteratorEltype(::Type{DropLast{T}}) where T = IteratorEltype(T)
IteratorEltype(::Type{TakeLast{T}}) where T = IteratorEltype(T)
IteratorEltype(::Type{TakeLastWhile{T}}) where T = IteratorEltype(T)
IteratorEltype(::Type{DropLastWhile{T}}) where T = IteratorEltype(T)

include("./traits.jl")

### iterate

## TakeLast

function iterate(it::TakeLast, state...)
    xs = it.xs
    iterate_takelast(it, state...,
                     IteratorSize(xs), IteratorReversed(xs), IteratorIndexable(xs))
end

function iterate_takelast(it, ::FiniteLength, ::IteratorReversed, ::Indexable)
    xs = it.xs
    len = length(xs) - min(it.n, length(xs)) + 1
    len <= 0 && return nothing
    i = nth(eachindex(xs), len)
    xs[i], (nextind(xs, lastindex(xs)), (nextind(xs, i)))
end

function iterate_takelast(it, state, ::FiniteLength, ::IteratorReversed, ::Indexable)
    stop, i = state
    xs = it.xs
    if i == stop
        nothing
    else
        xs[i], (stop, nextind(xs, i))
    end
end

function iterate_takelast(it, ::FiniteLength, ::NotReversed, ::NotIndexable)
    elements = DropList{eltype(it)}()
    for element in it.xs
        push!(elements, element)
        if length(elements) > it.n
            popfirst!(elements)
        end
    end
    length(elements) == 0 && return nothing
    popfirst!(elements), elements
end

function iterate_takelast(it, state, ::FiniteLength, ::NotReversed, ::NotIndexable)
    if isempty(state)
        nothing
    else
        popfirst!(state), state
    end
end

function iterate_takelast(it, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    elements = collect(take(reverse(it.xs), it.n))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_takelast(it, state, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## DropLast

function iterate(it::DropLast, state...)
    iterate_droplast(it, state..., IteratorSize(it), IteratorReversed(it))
end

function iterate_droplast(it, ::HasLength, ::Reversed)
    elements = collect(drop(reverse(it.xs), it.n))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_droplast(it, state, ::HasLength, ::Reversed)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

function iterate_droplast(it, ::HasLength, ::NotReversed)
    n = length(it.xs) - it.n
    n <= 0 && return nothing
    y = iterate(it.xs)
    y[1], (y[2], n-1)
end

function iterate_droplast(it, state, ::HasLength, ::NotReversed)
    state, n = state
    n == 0 && return nothing
    y = iterate(it.xs, state)
    y[1], (y[2], n-1)
end

function iterate_droplast(it, ::IteratorSize, ::IteratorReversed)
    elements = DropList{eltype(it)}()
    state = ()
    for i in 1:(it.n+1)
        y = iterate(it.xs, state...)
        y == nothing && return nothing
        state = (y[2],)
        push!(elements, y[1])
    end
    popfirst!(elements), (state[1], elements)
end

function iterate_droplast(it, state, ::IteratorSize, ::IteratorReversed)
    state, elements = state
    y = iterate(it.xs, state)
    y === nothing && return nothing
    push!(elements, y[1])
    popfirst!(elements), (y[2], elements)
end

## TakeLastWhile

function iterate(it::TakeLastWhile, state...)
    xs = it.xs
    iterate_takelastwhile(it, state...,
                          IteratorSize(xs), IteratorReversed(xs), IteratorIndexable(xs))
end

function iterate_takelastwhile(it, ::FiniteLength, ::IteratorReversed, ::Indexable)
    local j = nothing
    for i in reverse(eachindex(it.xs))
        if it.pred(it.xs[i])
            j = i
        else
            break
        end
    end
    j === nothing && return nothing
    it.xs[j], (nextind(it.xs, lastindex(it.xs)), nextind(it.xs, j))
end

function iterate_takelastwhile(it, state, ::FiniteLength, ::IteratorReversed, ::Indexable)
    stop, i = state
    if i == stop
        nothing
    else
        it.xs[i], (stop, nextind(it.xs, i))
    end
end

function iterate_takelastwhile(it, ::FiniteLength, ::NotReversed, ::NotIndexable)
    elements = eltype(it)[]
    for element in it.xs
        if it.pred(element)
            push!(elements, element)
        else
            empty!(elements)
        end
    end
    isempty(elements) && return nothing
    elements[1], (2, elements)
end

function iterate_takelastwhile(it, state, ::FiniteLength, ::NotReversed, ::NotIndexable)
    i, elements = state
    if i > length(elements)
        nothing
    else
        elements[i], (i+1, elements)
    end
end

function iterate_takelastwhile(it, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    elements = collect(takewhile(it.pred, reverse(it.xs)))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_takelastwhile(it, state, ::IteratorSize, ::IteratorReversed, ::NotIndexable)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

## DropLastWhile

function iterate(it::DropLastWhile, state...)
    xs = it.xs
    iterate_droplastwhile(it, state...,
                          IteratorReversed(xs), IteratorSize(xs))
end

function iterate_droplastwhile(it, ::Reversed, ::FiniteLength)
    elements = collect(dropwhile(it.pred, reverse(it.xs)))
    isempty(elements) && return nothing
    len = length(elements)
    elements[len], (len-1, elements)
end

function iterate_droplastwhile(it, state, ::Reversed, ::FiniteLength)
    i, elements = state
    if i < 1
        nothing
    else
        elements[i], (i-1, elements)
    end
end

function iterate_droplastwhile(it, ::IteratorReversed, ::IteratorSize)
    trues = eltype(it)[]
    elements = eltype(it)[]
    iterate(it, (1, trues, elements, ()))
end

function iterate_droplastwhile(it, state, ::IteratorReversed, ::IteratorSize)
    i, trues, elements, state = state
    if i > length(elements)
        y = state === nothing ? nothing : iterate(it.xs, state...)
        y = _iterate_droplastwhile(it, y, trues, elements)
        if i > length(elements)
            return nothing
        else
            state = y === nothing ? nothing : (y[2],)
        end
    end
    elements[i], (i+1, trues, elements, state)
end

function _iterate_droplastwhile(it, y, trues, elements)
    while y !== nothing
        if it.pred(y[1])
            push!(trues, y[1])
        else
            if isempty(trues)
                push!(elements, y[1])
            else
                push!(trues, y[1])
                append!(elements, trues)
                empty!(trues)
            end
            break
        end
        y = iterate(it.xs, y[2])
    end
    return y
end

LICENSE.txt

Copyright © 2021 Fcard

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the “Software”), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

reverse.jl

include("./header.jl")
reverse(itr::Take) = drop(reverse(itr.xs), revn(itr.xs, itr.n))
reverse(itr::Drop) = take(reverse(itr.xs), revn(itr.xs, itr.n))
reverse(itr::TakeWhile) = drop(reverse(itr.xs), revn(itr.xs, countwhile(itr.pred, itr.xs)))
reverse(itr::DropWhile) = take(reverse(itr.xs), revn(itr.xs, countwhile(itr.pred, itr.xs)))

testall.sh

for file in *.jl; do
  case "$file" in
    header.jl|traits.jl|tests.jl) ;;
    *)
      echo "Testing $file"
      julia -L "$file" tests.jl
      ;;
  esac
done

tests.jl

using Test
import .Iterators: take, drop, takewhile, dropwhile, reverse, cycle, filter

@testset "Reverse Take/Drop" begin
    @testset "Reverse{<:Take}"  begin
        revtake(values, n) = collect(reverse(take(values, n)))
        @test revtake([1,2,3,4], 3) == [3,2,1]
        @test revtake([1,2,3,4,5,6], 5) == [5,4,3,2,1]
        @test revtake([1,2,3,4,5,6], 1) == [1]
        @test revtake([1,2,3],0) == []
        @test revtake([1,2,3],3) == [3,2,1]
        @test revtake([1,2,3],5) == [3,2,1]
    end

    @testset "Reverse{<:Drop}"  begin
        revdrop(values, n) = collect(reverse(drop(values, n)))
        @test revdrop([1,2,3,4], 1) == [4,3,2]
        @test revdrop([1,2,3,4,5,6], 1) == [6,5,4,3,2]
        @test revdrop([1,2,3,4,5,6], 5) == [6]
        @test revdrop([1,2,3],3) == []
        @test revdrop([1,2,3],5) == []
        @test revdrop([1,2,3],0) == [3,2,1]
    end

    @testset "Reverse{<:TakeWhile}"  begin
        revtakew(pred, values) = collect(reverse(takewhile(pred, values)))
        @test revtakew(<(3), [1,2,3,4]) == [2,1]
        @test revtakew(<(5), [1,2,3,4,5,6]) == [4,3,2,1]
        @test revtakew(<(2), [1,2,3,4,5,6]) == [1]
        @test revtakew(iseven, [2,2,3,3,4,4]) == [2,2]
        @test revtakew(isodd, [2,1,1,1,1,1]) == []
        @test revtakew(x->true, [1,2,3,4,5,6]) == [6,5,4,3,2,1]
    end

    @testset "Reverse{<:DropWhile}"  begin
        revdropw(pred, values) = collect(reverse(dropwhile(pred, values)))
        @test revdropw(<(3), [1,2,3,4]) == [4,3]
        @test revdropw(<(3), [1,2,3,4,5,6]) == [6,5,4,3]
        @test revdropw(<(6), [1,2,3,4,5,6]) == [6]
        @test revdropw(iseven, [2,2,3,3,4,4]) == [4,4,3,3]
        @test revdropw(iseven, [2,2,2,2,2,2]) == []
        @test revdropw(x->false, [1,2,3,4,5,6]) == [6,5,4,3,2,1]
    end
    if uncommon_length_support[]
        @testset "Reverse{...{<:Cycle}}" begin
            takecy(values,n) = collect(reverse(take(cycle(values), n)))
            dropcy(values,n,m) = collect(take(reverse(drop(Iterators.cycle(values), n)), m))
            takewcy(pred,values) = collect(reverse(takewhile(pred,cycle(values))))
            dropwcy(pred,values,n) = collect(take(reverse(dropwhile(pred,cycle(values))),n))
            takedrop(values,n,m) = collect(reverse(take(drop(cycle(values),n),m)))
            droptake(values,n,m) = collect(reverse(drop(take(cycle(values),n),m)))
            countn(n) = let x=n; i->(x-=1) >= 0 end
            @test takecy([1,2,3,4], 2) == [2,1]
            @test takecy([1,2,3,4,5,6], 4) == [4,3,2,1]
            @test takecy([1,2,3,4,5,6], 8) == [2,1,6,5,4,3,2,1]
            @test takecy([1,2,3,4,5,6], 0) == []

            @test dropcy([1,2,3,4,5,6], 2, 4) == [6,5,4,3]
            @test dropcy([1,2,3,4], 8, 4) == [4,3,2,1]

            @test takewcy(<(5), [1,2,3,4,5,6]) == [4,3,2,1]
            @test takewcy(countn(5), [1,2,3]) == [2,1,3,2,1]

            @test dropwcy(<(3), [1,2,3,4,5,6], 4) == [6,5,4,3]
            @test dropwcy(countn(2), [1,2,3], 5) == [3,2,1,3,2]

            @test takedrop([1,2,3,4], 1, 3) == [4,3,2]
            @test takedrop([1,2,3,4], 2, 2) == [4,3]
            @test droptake([1,2,3,4], 3, 1) == [3,2]
            @test droptake([1,2,3,4,5,6], 5, 2) == [5,4,3]
        end
        @testset "Reverse{...{<:Filter}}" begin
            takefl(pred,values,n) = collect(reverse(take(filter(pred, values), n)))
            dropfl(pred,values,n) = collect(reverse(drop(filter(pred, values), n)))
            takewfl(p1,p2,values) = collect(reverse(takewhile(p2,filter(p1, values))))
            dropwfl(p1,p2,values) = collect(reverse(dropwhile(p2,filter(p1, values))))
            @test takefl(iseven,[1,2,3,4,5,6],2) == [4,2]
            @test takefl(iseven,[1,2,3,4,5,6],1) == [2]
            @test takefl(iseven,[1,2,3,4,5,6],4) == [6,4,2]

            @test dropfl(iseven,[1,2,3,4,5,6],1) == [6,4]
            @test dropfl(iseven,[1,2,3,4,5,6],2) == [6]
            @test dropfl(iseven,[1,2,3,4,5,6],0) == [6,4,2]

            @test takewfl(iseven,<(6),[1,2,3,4,5,6]) == [4,2]
            @test takewfl(iseven,>(1),[1,2,3,4,5,6]) == [6,4,2]
            @test takewfl(iseven,<(0),[1,2,3,4,5,6]) == []

            @test dropwfl(iseven,<(6),[1,2,3,4,5,6]) == [6]
            @test dropwfl(iseven,>(1),[1,2,3,4,5,6]) == []
            @test dropwfl(iseven,<(0),[1,2,3,4,5,6]) == [6,4,2]
        end
    end
end

traits.jl

abstract type IteratorReverseIterable end
struct ReverseIterable <: IteratorReverseIterable end
struct NotReverseIterable <: IteratorReverseIterable end


IteratorReversable(::Type{<:}) = Reversable()
IteratorReversable(::Type{<:AbstractString}) = Reversable()
IteratorReversable(::Type{<:AbstractArray}) = Reversable()
IteratorReversable(::Type{<:Tuple}) = Reversable()
IteratorReversable(::Type{<:Reverse}) = Reversable()
IteratorReversable(::Type{Take{T}}) where T = IteratorReversable(T)
IteratorReversable(::Type{Drop{T}}) where T = IteratorReversable(T)
IteratorReversable(::Type{TakeWhile{T}}) where T = IteratorReversable(T)
IteratorReversable(::Type{DropWhile{T}}) where T = IteratorReversable(T)
IteratorReversable(::Type{Cycle{T}}) where T = IteratorReversable(T)
IteratorReversable(::Type{Filter{T}}) where T = IteratorReversable(T)
IteratorReversable(::Type{Enumerate{T}}) where T = IteratorReversable(T)
if isdefined(@__MODULE__, :TakeLast)
    IteratorReversable(::Type{TakeLast{T}}) where T = IteratorReversable(T)
    IteratorReversable(::Type{DropLast{T}}) where T = IteratorReversable(T)
    IteratorReversable(::Type{TakeLastWhile{T,P}}) where {T,P} = IteratorReversable(T)
    IteratorReversable(::Type{DropLastWhile{T,P}}) where {T,P} = IteratorReversable(T)
end

abstract type IteratorReversed end
struct Reversed <: IteratorReversed end
struct NotReversed <: IteratorReversed end

IteratorReversed(x) = find_reverse_type(x) === nothing ? NotReversed() : Reversed()

find_reverse_type(x) = find_reverse_type(typeof(x))
find_reverse_type(::Type) = nothing
find_reverse_type(T::Type{<:Reverse}) = T
find_reverse_type(::Type{Cycle{T}}) where T = find_reverse_type(T)
find_reverse_type(::Type{Filter{T}}) where T = find_reverse_type(T)
find_reverse_type(::Type{Enumerate{T}}) where T = find_reverse_type(T)

abstract type IteratorIndexable end
struct Indexable <: IteratorIndexable end
struct NotIndexable <: IteratorIndexable end

IteratorIndexable(x) = IteratorIndexable(typeof(x))
IteratorIndexable(::Type) = NotIndexable()
IteratorIndexable(::Type{<:IndexableItr}) = Indexable()