Repository: JuliaCollections/DataStructures.jl
Pull request #485 (2019-03-08 14:28:28)

Add Fenwick Tree
This PR adds the feature of a fairly simple, but quite powerful DS. 

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

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

```diff
@@            Coverage Diff            @@
##           master    #485      +/-   ##
=========================================
- Coverage   90.44%   89.8%   -0.64%     
=========================================
  Files          30      31       +1     
  Lines        2270    2286      +16     
=========================================
  Hits         2053    2053              
- Misses        217     233      +16
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/fenwick.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485/diff?src=pr&el=tree#diff-c3JjL2ZlbndpY2suamw=) | `0% <0%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485?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/485?src=pr&el=footer). Last update [ccee82d...4263cc0](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

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

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

```diff
@@            Coverage Diff            @@
##           master    #485      +/-   ##
=========================================
- Coverage   90.44%   89.8%   -0.64%     
=========================================
  Files          30      31       +1     
  Lines        2270    2286      +16     
=========================================
  Hits         2053    2053              
- Misses        217     233      +16
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/fenwick.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485/diff?src=pr&el=tree#diff-c3JjL2ZlbndpY2suamw=) | `0% <0%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485?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/485?src=pr&el=footer). Last update [ccee82d...4263cc0](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/485?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


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/DataStructures.jl b/src/DataStructures.jl
index 8117cc1..fe2ca55 100644
--- a/src/DataStructures.jl
+++ b/src/DataStructures.jl
@@ -11,7 +11,7 @@ module DataStructures
                  ReverseOrdering, Reverse, Lt,
                  isless, union, intersect, symdiff, setdiff, issubset,
                  searchsortedfirst, searchsortedlast, in,
-                 eachindex, keytype, valtype, minimum, maximum
+                 eachindex, keytype, valtype, minimum, maximum, size
 
     using OrderedCollections
     import OrderedCollections: filter, filter!, isordered
@@ -28,6 +28,8 @@ module DataStructures
     export classified_lists, classified_sets, classified_counters
 
     export IntDisjointSets, DisjointSets, num_groups, find_root, in_same_set, root_union!
+    
+    export FenwickTree, length, inc!, dec!, incdec!, prefixsum
 
     export AbstractHeap, compare, extract_all!
     export BinaryHeap, BinaryMinHeap, BinaryMaxHeap, nlargest, nsmallest
@@ -73,6 +75,8 @@ module DataStructures
 
     include("int_set.jl")
 
+    include("fenwick.jl")
+
     include("list.jl")
     include("mutable_list.jl")
     include("balanced_tree.jl")
diff --git a/src/fenwick.jl b/src/fenwick.jl
new file mode 100644
index 0000000..4ce2219
--- /dev/null
+++ b/src/fenwick.jl
@@ -0,0 +1,95 @@
+"""
+    FenwickTree{T}(n)
+    
+Constructs a [`FenwickTree`](https://en.wikipedia.org/wiki/Fenwick_tree) of length `n`.
+ 
+"""
+struct FenwickTree{T}
+    bi_tree::Vector{T} #bi_tree is shorthand for Binary Indexed Tree, an alternative name for Fenwick Tree
+    n::Int
+end
+
+FenwickTree{T}(n::Integer) where T = FenwickTree{T}(zeros(T, n), n)
+
+"""
+    FenwickTree(arr::AbstractArray) 
+    
+Constructs a [`FenwickTree`](https://en.wikipedia.org/wiki/Fenwick_tree) from an array of `counts`
+ 
+"""
+function FenwickTree(a::AbstractVector{U}) where U
+    n = length(a)
+    tree = FenwickTree{U}(n)
+    @inbounds for i = 1:n
+        inc!(tree, i, a[i])
+    end
+    tree
+end
+
+length(ft::FenwickTree) = ft.n
+
+"""
+    inc!(ft::FenwickTree{T}, ind, val)
+
+Increases the value of the [`FenwickTree`] by `val` from the index `ind` upto the length of the Fenwick Tree.
+
+""" 
+function inc!(ft::FenwickTree{T}, ind::Integer, val = 1) where T
+    val0 = convert(T, val)
+    i = ind
+    n = ft.n
+    @boundscheck 1 <= i <= n || throw(ArgumentError("$i should be in between 1 and $n"))
+    @inbounds while i <= n
+        ft.bi_tree[i] += val0
+        i += i&(-i)
+    end
+end
+
+"""
+    dec!(ft::FenwickTree, ind, val)
+
+Decreases the value of the [`FenwickTree`] by `val` from the index `ind` upto the length of the Fenwick Tree.
+
+""" 
+dec!(ft::FenwickTree, ind::Integer, val = 1 ) = inc!(ft, ind, -val)
+
+"""
+    incdec!(ft::FenwickTree{T}, left, right, val)
+
+Increases the value of the [`FenwickTree`] by `val` from the indices from `left` and decreases it from the `right`.
+
+"""    
+function incdec!(ft::FenwickTree{T}, left::Integer, right::Integer, val = one(T)) where T
+    val0 = convert(T, val)
+    inc!(ft, left, val0)
+    dec!(ft, right, val0)
+end
+
+"""
+    prefixsum(ft::FenwickTree{T}, ind)
+    
+Return the cumulative sum from index 1 upto `ind` of the [`FenwickTree`](@ref)
+
+# Examples
+```
+julia> f = FenwickTree{Int}(6)
+julia> inc!(f, 2, 5)
+julia> prefixsum(f, 1)
+ 0
+julia> prefixsum(f, 3)
+ 5
+```
+"""
+function prefixsum(ft::FenwickTree{T}, ind::Integer) where T
+    sum = zero(T)
+    i = ind
+    n = ft.n
+    @boundscheck 1 <= i <= n || throw(ArgumentError("$i should be in between 1 and $n"))
+    @inbounds while i > 0 
+        sum += ft.bi_tree[i]
+        i -= i&(-i)
+    end
+    sum
+end
+
+getindex(ft::FenwickTree{T}, ind::Integer) where T = prefixsum(ft, ind)
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/runtests.jl b/test/runtests.jl
index a9ebbf9..df24b9d 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -26,7 +26,8 @@ tests = ["int_set",
          "multi_dict",
          "circular_buffer",
          "sorting",
-         "priority_queue"
+         "priority_queue", 
+         "fenwick"
         ]
 
 if length(ARGS) > 0
diff --git a/test/test_fenwick.jl b/test/test_fenwick.jl
new file mode 100644
index 0000000..144e5eb
--- /dev/null
+++ b/test/test_fenwick.jl
@@ -0,0 +1,37 @@
+@testset "Fenwick Tree" begin
+    @testset "initialisation" begin
+        f1 = FenwickTree{Float64}(5)
+        @test f1.bi_tree == zeros(5)
+        @test length(f1) == 5
+        
+        arr = [1.2, 8.7, 7.2, 3.5]
+        f3 = FenwickTree(arr)
+        @test f3[1] == 1.2
+        @test length(f3) == length(arr)
+    end
+    
+    @testset "Point update and Point queries" begin
+        f1 = FenwickTree{Int}(10)
+        inc!(f1, 10, 5)
+        @test prefixsum(f1, 10) == 5
+        @test prefixsum(f1, 9) == 0
+        @test prefixsum(f1, 1) == 0
+        inc!(f1, 5, 7)
+        @test prefixsum(f1, 8) == 7
+        @test prefixsum(f1, 10) == 12
+        @test prefixsum(f1, 5) == 7
+        @test prefixsum(f1, 4) == 0
+        
+        dec!(f1, 7, 2)
+        @test prefixsum(f1, 8) == 5
+        @test prefixsum(f1, 6) == 7
+        
+        incdec!(f1, 2, 6, 3)
+        @test prefixsum(f1, 3) == 3
+        @test prefixsum(f1, 7) == 5
+        
+        @test_throws ArgumentError inc!(f1, 11)
+        @test_throws ArgumentError inc!(f1, 0)
+    end
+    
+end
\ No newline at end of file
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