Repository: JuliaCollections/DataStructures.jl
Pull request #475 (2019-01-03 18:37:43)

Define multiset operations
needs tests
needs docs

Solves #474 

when documented will solve #133 

https://en.wikipedia.org/wiki/Multiset#Basic_properties_and_operations


It is tempting to define `zero(A::Type(<:Accumulator)=A()`
which would give us a group (in the mathematical sense).
If we are willing to think of `merge` and `setdiff` as the same operation, but one of which creating the inverse element.

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

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

```diff
@@            Coverage Diff             @@
##           master     #475      +/-   ##
==========================================
- Coverage   67.52%   66.68%   -0.84%     
==========================================
  Files          28       28              
  Lines        2069     2095      +26     
==========================================
  Hits         1397     1397              
- Misses        672      698      +26
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/accumulator.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475/diff?src=pr&el=tree#diff-c3JjL2FjY3VtdWxhdG9yLmps) | `56.92% <3.7%> (-37.95%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475?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/475?src=pr&el=footer). Last update [26e0229...3060cf3](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475?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/475?src=pr&el=h1) Report
> Merging [#475](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475?src=pr&el=desc) into [master](https://codecov.io/gh/JuliaCollections/DataStructures.jl/commit/26e0229ac243079c071d4a47d16366fca40e4cdc?src=pr&el=desc) will **decrease** coverage by `0.83%`.
> The diff coverage is `3.7%`.

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

```diff
@@            Coverage Diff             @@
##           master     #475      +/-   ##
==========================================
- Coverage   67.52%   66.68%   -0.84%     
==========================================
  Files          28       28              
  Lines        2069     2095      +26     
==========================================
  Hits         1397     1397              
- Misses        672      698      +26
```


| [Impacted Files](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [src/accumulator.jl](https://codecov.io/gh/JuliaCollections/DataStructures.jl/pull/475/diff?src=pr&el=tree#diff-c3JjL2FjY3VtdWxhdG9yLmps) | `56.92% <3.7%> (-37.95%)` | :arrow_down: |

------

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

oxinabox: No longer needs tests.
Still needs docs.
oxinabox: I want merge 
https://github.com/JuliaCollections/DataStructures.jl/pull/476
 first before I write the docs.
to decrease chance of conflicts

Patch:
diff --git a/README.md b/README.md
index 9183e30..4930b3a 100644
--- a/README.md
+++ b/README.md
@@ -17,7 +17,7 @@ This package implements a variety of data structures, including
 -   CircularDeque
 -   Stack
 -   Queue
--   Accumulators and Counters
+-   Accumulators and Counters (i.e. Multisets / Bags)
 -   Disjoint Sets
 -   Binary Heap
 -   Mutable Binary Heap
diff --git a/docs/src/accumulators.md b/docs/src/accumulators.md
index 753677c..fdcfd03 100644
--- a/docs/src/accumulators.md
+++ b/docs/src/accumulators.md
@@ -41,7 +41,6 @@ a[x]             # get the current value/count for x,
 
 a[x] = v         # sets the current value/count for `x` to `v`
 
-
 inc!(a, x)       # increment the value/count for x by 1
 inc!(a, x, v)    # increment the value/count for x by v
 
@@ -51,8 +50,36 @@ dec!(a, x, v)    # decrement the value/count for x by v
 reset!(a, x)     # remove a key x from a, and return its current value
 
 merge!(a, a2)    # add all counts from a2 to a1
-merge(a, a2)     # return a new accumulator/counter that combines (sums) the
-                 # values/counts in both a and a2.
+merge(a, a2)     # return a new accumulator/counter that combines the
+                 # values/counts in both a and a2
+                 # `a[v] + a2[v]` over all `v` in the universe
 ```
 
+`merge` is the multiset sum operation (sometimes written ⊎).
+
+## Use as a multiset
+
+An `Accumulator{T, <:Integer} where T` such as is returned by `counter`,
+is a [multiset](https://en.wikipedia.org/wiki/Multiset) or Bag, of objects of type `T`.
+If the count type is not an integer but a more general real number, then this is a form of fuzzy multiset.
+We support a number of operations supporting the use of `Accumulator`s as multisets.
 
+
+Note that these operations will throw an error if the accumulator has negative or zero counts for any items.
+
+```julia
+
+setdiff(a1, a2)          # The opposite of `merge` (i.e. multiset sum),
+                         # returns a new multiset with the count of items in `a2` removed from `a1`, down to a minimum of zero
+                         # `max(a1[v] - a2[v], 0)` over all `v` in the universe
+
+
+union(a1, a2)            # multiset union (sometimes called maximum, or lowest common multiple)
+                         # returns a new multiset with the counts being the higher of those in `a1` or `a2`.
+                         # `max(a1[v], a2[v])` over all `v` in the universe
+
+intersect(a1, a2)        # multiset intersection (sometimes called infimum or greatest common divisor)
+                         # returns a new multiset with the counts being the lowest of those in `a1` or `a2`.
+                         # Note that this means things not occurring in both with be removed (count zero).
+                         # `min(a1[v], a2[v])` over all `v` in the universe
+```
diff --git a/src/accumulator.jl b/src/accumulator.jl
index a3758b2..89dc642 100644
--- a/src/accumulator.jl
+++ b/src/accumulator.jl
@@ -32,7 +32,6 @@ function eltype_for_accumulator(seq::T) where {T<:Base.Generator}
 end
 
 
-
 copy(ct::Accumulator) = Accumulator(copy(ct.map))
 
 length(a::Accumulator) = length(a.map)
@@ -130,7 +129,7 @@ end
 Resets the count of `x` to zero.
 Returns its former count.
 """
-reset!(ct::Accumulator, x) = pop!(ct.map, x)
+reset!(ct::Accumulator{<:Any,V}, x) where V = haskey(ct.map, x) ? pop!(ct.map, x) : zero(V)
 
 """
      nlargest(acc::Accumulator, [n])
@@ -182,4 +181,59 @@ nsmallest(acc::Accumulator, n) = partialsort!(collect(acc), 1:n, by=last, rev=fa
 @deprecate pop!(ct::Accumulator, x) reset!(ct, x)
 @deprecate push!(ct1::Accumulator, ct2::Accumulator) merge!(ct1,ct2)
 
+###########################################################
+## Multiset operations
+
+struct MultiplicityException{K,V} <: Exception
+    k::K
+    v::V
+end
+
+function Base.showerror(io::IO, err::MultiplicityException)
+    print(io, "When using an `Accumulator` as a multiset, all elements must have positive multiplicity")
+    print(io, " element `$(err.k)` has multiplicity $(err.v)")
+end
+
+drop_nonpositive!(a::Accumulator, k) = (a[k] > 0 || delete!(a.map, k))
+
+
+function Base.setdiff(a::Accumulator, b::Accumulator)
+    ret = copy(a)
+    for (k, v) in b
+        v > 0 || throw(MultiplicityException(k, v))
+        dec!(ret, k, v)
+        drop_nonpositive!(ret, k)
+    end
+    return ret
+end
+
+Base.issubset(a::Accumulator, b::Accumulator) = all(b[k] >= v for (k, v) in a)
+
+Base.union(a::Accumulator, b::Accumulator, c::Accumulator...) = union(union(a,b), c...)
+Base.union(a::Accumulator, b::Accumulator) = union!(copy(a), b)
+function Base.union!(a::Accumulator, b::Accumulator)
+    for (kb, vb) in b
+        va = a[kb]
+        vb >= 0 || throw(MultiplicityException(kb, vb))
+        va >= 0 || throw(MultiplicityException(kb, va))
+        a[kb] = max(va, vb)
+    end
+    return a
+end
+
+
+Base.intersect(a::Accumulator, b::Accumulator, c::Accumulator...) = insersect(intersect(a,b), c...)
+Base.intersect(a::Accumulator, b::Accumulator) = intersect!(copy(a), b)
+function Base.intersect!(a::Accumulator, b::Accumulator)
+    for k in union(keys(a), keys(b)) # union not interection as we want to check both multiplicties
+        va = a[k]
+        vb = b[k]
+        va >= 0 || throw(MultiplicityException(k, va))
+        vb >= 0 || throw(MultiplicityException(k, vb))
+        
+        a[k] = min(va, vb)
+        drop_nonpositive!(a, k) # Drop any that ended up zero
+    end
+    return a
+end
 


Test patch:
diff --git a/test/runtests.jl b/test/runtests.jl
index daf11c8..229f3c3 100644
--- a/test/runtests.jl
+++ b/test/runtests.jl
@@ -5,7 +5,7 @@ using Serialization
 
 import DataStructures: IntSet
 
-@test isempty(detect_ambiguities(Base, Core, DataStructures))
+@test [] == detect_ambiguities(Base, Core, DataStructures)
 
 tests = ["int_set",
          "deque",
diff --git a/test/test_accumulator.jl b/test/test_accumulator.jl
index d1d7380..2a83c64 100644
--- a/test/test_accumulator.jl
+++ b/test/test_accumulator.jl
@@ -174,6 +174,71 @@
 
         @test_throws BoundsError nsmallest(counter("a"),2)
     end
+    
+    @testset "reset!" begin
+        ct = counter("abbbcddddda") # ['d'=>5, 'b'=>3, 'a'=>2, 'c'=>1]
+        @test reset!(ct, 'b') == 3
+        @test ct == counter("acddddda")
+        
+        @test reset!(ct, 'x') == 0
+    end
+
+    @testset "copy" begin
+        orig = counter("aabbbcccc")
+        dup = copy(orig)
+        @test orig == dup
+        
+        # Modifying copy should not modify original
+        inc!(orig, 'a')
+        @test orig != dup
+    end
+    
+    @testset "Multiset" begin
+        @testset "issubset" begin
+            @test issubset(counter([1,2,3]), counter([1,2,3]))
+            @test !issubset(counter([1,2,3,4]), counter([1,2,3]))
+            @test issubset(counter([1,2]), counter([1,2,3]))
+            
+            @test issubset(counter([1,2,3]), counter([1,2,3,3]))
+            @test !issubset(counter([1,2,3,3]), counter([1,2,3]))
+        end
+        
+        @testset "setdiff" begin
+            @test setdiff(counter([1,2,3]), counter([2, 4])) == counter([3, 1])
+            @test setdiff(counter([1,2,3]), counter([2,2,4])) == counter([3, 1])
+            @test setdiff(counter([1,2,2,2,3]), counter([2,2,4])) == counter([1,2,3])
+            
+            nonmultiset = counter(Dict([('a',-10), ('b',20)]))
+            @test_throws DataStructures.MultiplicityException setdiff(counter("aabbcc"), nonmultiset)
+        end
+        
+        @testset "union" begin
+            @test ∪(counter([1,2,3]), counter([1,2,3])) == counter([1,2,3])
+            @test ∪(counter([1,2,3]), counter([1,2,2,3])) == counter([1,2,2,3])
+            @test ∪(counter([1,3]), counter([2,2])) == counter([1,2,2,3])
+            @test ∪(counter([1,2,3]), counter(Int[])) == counter([1,2,3])
+            
+            nonmultiset = counter(Dict([('a',-10), ('b',20)]))
+            @test_throws DataStructures.MultiplicityException (counter("aabbcc") ∪ nonmultiset)
+            @test_throws DataStructures.MultiplicityException (nonmultiset ∪ counter("aabbcc"))
+        end
+ 
+        @testset "intersect" begin
+            @test ∩(counter([1,2,3]), counter([1,2,3])) == counter([1,2,3])
+            @test ∩(counter([1,2,3]), counter([1,2,2,3])) == counter([1,2,3])
+            @test ∩(counter([1,3]), counter([2,2])) == counter(Int[])
+            @test ∩(counter([1,2,3]), counter(Int[])) == counter(Int[])
+            
+            
+            nonmultiset = counter(Dict([('a',-10), ('b',20)]))
+            @test_throws DataStructures.MultiplicityException (counter("aabbcc") ∩ nonmultiset)
+            @test_throws DataStructures.MultiplicityException (nonmultiset ∩ counter("aabbcc"))
+        end
+
+
+    
+
+    end
 
 end # @testset Accumulators