Repository: JuliaCollections/DataStructures.jl
Pull request #484 (2019-03-05 02:40:20)

Add support for range indexing into MutableLinkedLists
Thought this might be useful to have.

codecov[bot]: # [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=h1) Report
> Merging [#484](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/ccee82d8a51618815e531fada2929f6e8990873a?src=pr&el=desc) will **decrease** coverage by `0.47%`.
> The diff coverage is `0%`.

[![Impacted file tree graph](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484/graphs/tree.svg?width=650&token=7FHvoCSQ7k&height=150&src=pr)](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #484      +/-   ##
==========================================
- Coverage   90.44%   89.96%   -0.48%     
==========================================
  Files          30       30              
  Lines        2270     2282      +12     
==========================================
  Hits         2053     2053              
- Misses        217      229      +12
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/mutable\_list.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484/diff?src=pr&el=tree#diff-c3JjL211dGFibGVfbGlzdC5qbA==) | `71.52% <0%> (-6.18%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=footer). Last update [ccee82d...8167580](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/484?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

c-p-murphy: Tweaked a few things, but I think it's good to go now.
c-p-murphy: Tweaked a few things, but I think it's good to go now.
c-p-murphy: I tweaked a few things, but I think this is all set now.

Patch:
diff --git a/docs/src/mutable_linked_list.md b/docs/src/mutable_linked_list.md
index 5c5596a..fd900e7 100644
--- a/docs/src/mutable_linked_list.md
+++ b/docs/src/mutable_linked_list.md
@@ -20,12 +20,13 @@ map(f, l)                         # return list with f applied to elements
 filter(f, l)                      # return list of elements where f(el) == true
 reverse(l)                        # return reversed list
 copy(l)                           # return a copy of list
-getindex(l, idx)                  # get value at index
+getindex(l, idx)   || l[idx]      # get value at index
+getindex(l, range) || l[range]    # get values within range a:b
 setindex!(l, data, idx)           # set value at index to data
 append!(l1, l2)                   # attach l2 at the end of l1
 append!(l, elts...)               # attach elements at end of list
 delete!(l, idx)                   # delete element at index
-delete!(l, range)                 # delete elements within range [a,b]
+delete!(l, range)                 # delete elements within range a:b
 push!(l, data)                    # add element to end of list
 pushfirst!(l, data)               # add element to beginning of list
 pop!(l)                           # remove element from end of list
diff --git a/src/mutable_list.jl b/src/mutable_list.jl
index bdc44e7..15cccc3 100644
--- a/src/mutable_list.jl
+++ b/src/mutable_list.jl
@@ -4,8 +4,8 @@ mutable struct ListNode{T}
     next::ListNode{T}
     function ListNode{T}() where T
         node = new{T}()
-        node.prev = node
         node.next = node
+        node.prev = node
         return node
     end
     function ListNode{T}(data) where T
@@ -16,15 +16,13 @@ end
 
 mutable struct MutableLinkedList{T}
     len::Int
-    front::ListNode{T}
-    back::ListNode{T}
+    node::ListNode{T}
     function MutableLinkedList{T}() where T
         l = new{T}()
         l.len = 0
-        l.front = ListNode{T}()
-        l.back = ListNode{T}()
-        l.front.next = l.back
-        l.back.prev = l.front
+        l.node = ListNode{T}()
+        l.node.next = l.node
+        l.node.prev = l.node
         return l
     end
 end
@@ -40,23 +38,26 @@ function MutableLinkedList{T}(elts...) where T
 end
 
 iterate(l::MutableLinkedList) = begin
-    l.len == 0 ? nothing : (l.front.next.data, l.front.next.next)
+    l.len == 0 ? nothing : (l.node.next.data, l.node.next.next)
 end
 iterate(l::MutableLinkedList, n::ListNode) = begin
-    n.next == n ? nothing : (n.data, n.next)
+    n === l.node ? nothing : (n.data, n.next)
 end
 
 isempty(l::MutableLinkedList) = l.len == 0
 length(l::MutableLinkedList) = l.len
 collect(l::MutableLinkedList{T}) where T = T[x for x in l]
 eltype(l::MutableLinkedList{T}) where T = T
+lastindex(l::MutableLinkedList) = l.len
+
 function first(l::MutableLinkedList)
     isempty(l) && throw(ArgumentError("List is empty"))
-    return l.front.next.data
+    return l.node.next.data
 end
+
 function last(l::MutableLinkedList)
     isempty(l) && throw(ArgumentError("List is empty"))
-    return l.back.prev.data
+    return l.node.prev.data
 end
 
 ==(l1::MutableLinkedList{T}, l2::MutableLinkedList{S}) where {T,S} = false
@@ -120,16 +121,32 @@ end
 
 function getindex(l::MutableLinkedList, idx::Int)
     @boundscheck 0 < idx <= l.len || throw(BoundsError(l, idx))
-    node = l.front
+    node = l.node
     for i = 1:idx
         node = node.next
     end
     return node.data
 end
 
+function getindex(l::MutableLinkedList{T}, r::UnitRange) where T
+    @boundscheck 0 < first(r) < last(r) <= l.len || throw(BoundsError(l, r))
+    l2 = MutableLinkedList{T}()
+    node = l.node
+    for i = 1:first(r)
+        node = node.next
+    end
+    len = length(r)
+    for j in 1:len
+        push!(l2, node.data)
+        node = node.next
+    end
+    l2.len = len
+    return l2
+end
+
 function setindex!(l::MutableLinkedList{T}, data, idx::Int) where T
     @boundscheck 0 < idx <= l.len || throw(BoundsError(l, idx))
-    node = l.front
+    node = l.node
     for i = 1:idx
         node = node.next
     end
@@ -138,8 +155,8 @@ function setindex!(l::MutableLinkedList{T}, data, idx::Int) where T
 end
 
 function append!(l1::MutableLinkedList{T}, l2::MutableLinkedList{T}) where T
-    l1.back.prev.next = l2.front.next
-    l2.front.next.prev = l1.back.prev
+    l1.node.prev.next = l2.node.next
+    l2.node.next.prev = l1.node.prev
     l1.len += length(l2)
     return l1
 end
@@ -148,13 +165,12 @@ function append!(l::MutableLinkedList, elts...)
     for elt in elts
         push!(l, elt)
     end
-    l.len += length(elts)
     return l
 end
 
 function delete!(l::MutableLinkedList, idx::Int)
     @boundscheck 0 < idx <= l.len || throw(BoundsError(l, idx))
-    node = l.front
+    node = l.node
     for i = 1:idx
         node = node.next
     end
@@ -168,7 +184,7 @@ end
 
 function delete!(l::MutableLinkedList, r::UnitRange)
     @boundscheck 0 < first(r) < last(r) <= l.len || throw(BoundsError(l, r))
-    node = l.front
+    node = l.node
     for i = 1:first(r)
         node = node.next
     end
@@ -185,43 +201,43 @@ function delete!(l::MutableLinkedList, r::UnitRange)
 end
 
 function push!(l::MutableLinkedList{T}, data) where T
-    last = l.back.prev
+    oldlast = l.node.prev
     node = ListNode{T}(data)
-    node.next = l.back
-    node.prev = last
-    l.back.prev = node
-    last.next = node
+    node.next = l.node
+    node.prev = oldlast
+    l.node.prev = node
+    oldlast.next = node
     l.len += 1
     return l
 end
 
 function pushfirst!(l::MutableLinkedList{T}, data) where T
-    first = l.front.next
+    oldfirst = l.node.next
     node = ListNode{T}(data)
-    node.prev = l.front
-    node.next = first
-    l.front.next = node
-    first.prev = node
+    node.prev = l.node
+    node.next = oldfirst
+    l.node.next = node
+    oldfirst.prev = node
     l.len += 1
     return l
 end
 
 function pop!(l::MutableLinkedList)
     isempty(l) && throw(ArgumentError("List must be non-empty"))
-    last = l.back.prev.prev
-    data = l.back.prev.data
-    last.next = l.back
-    l.back.prev = last
+    last = l.node.prev.prev
+    data = l.node.prev.data
+    last.next = l.node
+    l.node.prev = last
     l.len -= 1
     return data
 end
 
 function popfirst!(l::MutableLinkedList)
     isempty(l) && throw(ArgumentError("List must be non-empty"))
-    first = l.front.next.next
-    data = l.front.next.data
-    first.prev = l.front
-    l.front.next = first
+    first = l.node.next.next
+    data = l.node.next.data
+    first.prev = l.node
+    l.node.next = first
     l.len -= 1
     return data
 end


Test patch:
diff --git a/test/test_mutable_list.jl b/test/test_mutable_list.jl
index 7e4137a..c92c563 100644
--- a/test/test_mutable_list.jl
+++ b/test/test_mutable_list.jl
@@ -2,8 +2,11 @@
 
     @testset "empty list" begin
         l1 = MutableLinkedList{Int}()
+        @test MutableLinkedList() == MutableLinkedList{Any}()
+        @test iterate(l1) === nothing
         @test isempty(l1)
         @test length(l1) == 0
+        @test lastindex(l1) == 0
         @test collect(l1) == Int[]
         @test eltype(l1) == Int
         @test_throws ArgumentError pop!(l1)
@@ -20,11 +23,26 @@
                 for i = 1:n
                     push!(l, i)
                     @test last(l) == i
+                    if i > 4
+                        @test getindex(l, i) == i
+                        @test getindex(l, 1:floor(Int, i/2)) == MutableLinkedList{Int}(1:floor(Int, i/2)...)
+                        @test l[1:floor(Int, i/2)] == MutableLinkedList{Int}(1:floor(Int, i/2)...)
+                        setindex!(l, 0, i - 2)
+                        @test l == MutableLinkedList{Int}(1:i-3..., 0, i-1:i...)
+                        setindex!(l, i - 2, i - 2)
+                    end
+                    @test lastindex(l) == i
                     @test length(l) == i
                     @test isempty(l) == false
                     for (j, k) in enumerate(l)
                         @test j == k
                     end
+                    if i > 3
+                        l1 = MutableLinkedList{Int32}(1:i...)
+                        io = IOBuffer()
+                        @test sprint(io -> show(io, iterate(l1))) == "(1, DataStructures.ListNode{Int32}(2))"
+                        @test sprint(io -> show(io, iterate(l1, l1.node.next.next))) == "(2, DataStructures.ListNode{Int32}(3))"
+                    end
                     cl = collect(l)
                     @test isa(cl, Vector{Int})
                     @test cl == collect(1:i)
@@ -79,6 +97,9 @@
                     l2 = MutableLinkedList{Int}(n+1:2n...)
                     append!(l, l2)
                     @test l == MutableLinkedList{Int}(1:2n...)
+                    l3 = MutableLinkedList{Int}(1:n...)
+                    append!(l3, n+1:2n...)
+                    @test l3 == MutableLinkedList{Int}(1:2n...)
                 end
 
                 @testset "delete" begin
@@ -110,12 +131,29 @@
                 @testset "map" begin
                     l = MutableLinkedList{Int}(1:n...)
                     @test map(x -> 2x, l) == MutableLinkedList{Int}(2:2:2n...)
+                    l2 = MutableLinkedList{Float64}()
+                    @test map(x -> x*im, l2) == MutableLinkedList{Complex{Float64}}()
+                    @test map(Int32, l2) == MutableLinkedList{Int32}()
+                    f(x) = x % 2 == 0 ? convert(Int8, x) : convert(Float16, x)
+                    @test typeof(map(f, l)) == MutableLinkedList{Real}
                 end
 
                 @testset "filter" begin
                     l = MutableLinkedList{Int}(1:n...)
                     @test filter(x -> x % 2 == 0, l) == MutableLinkedList{Int}(2:2:n...)
                 end
+
+                @testset "show" begin
+                    l = MutableLinkedList{Int32}(1:n...)
+                    io = IOBuffer()
+                    @test sprint(io -> show(io, l.node.next)) == "$(typeof(l.node.next))($(l.node.next.data))"
+                    io1 = IOBuffer()
+                    write(io1, "MutableLinkedList{Int32}(");
+                    write(io1, join(l, ", "));
+                    write(io1, ")")
+                    seekstart(io1)
+                    @test sprint(io -> show(io, l)) == read(io1, String)
+                end
             end
         end
     end