http://www.programming-algorithms.net/article/41868/Multiset
https://dzone.com/articles/google-guava-multisets
The easiest way to implement a multiset is to use a list a forget its ordering. But this approach is very memory inefficient, because it needs to store all instances of repeating items. A better solution uses two lists – one for data and second for storing numbers of occurrences of corresponding items. This implementation performs better, but is still not optimal, because the contains operation needs to iterate over the whole array, which takes steps, where is number of distinct elements stored. The optimal implementation uses for storing items ahash table structure, which guarantees average access time for all elements.
06.
public
class
Multiset<VALUE> {
07.
08.
private
List<VALUE> values;
09.
private
List<Integer> occurences;
10.
11.
/**
12.
* Constructor
13.
* @param initialCapacity initial capacity of underlying lists
14.
*/
15.
public
Multiset(
int
initialCapacity) {
16.
values =
new
ArrayList<VALUE>(initialCapacity);
17.
occurences =
new
ArrayList<Integer>(initialCapacity);
18.
}
19.
20.
/**
21.
* Inserts a value into the multiset
22.
* @param val value
23.
* @return number of occurences of the value in the set after the addition
24.
*/
25.
public
int
put(VALUE val) {
26.
int
index = values.indexOf(val);
27.
if
(index == -
1
) {
28.
values.add(val);
29.
occurences.add(
1
);
30.
return
1
;
31.
}
else
{
32.
int
currCount = occurences.get(index);
33.
occurences.set(index, currCount +
1
);
34.
return
currCount +
1
;
35.
}
36.
}
37.
38.
/**
39.
* Returns and deletes (decrements number of uccurences) some value from the multiset
40.
* @return value, null if the multiset is empty
41.
*/
42.
public
VALUE pick() {
43.
if
(values.size() ==
0
) {
44.
return
null
;
45.
}
46.
if
(occurences.get(
0
) ==
1
) {
47.
VALUE v = values.remove(
0
);
48.
occurences.remove(
0
);
49.
return
v;
50.
}
else
{
51.
VALUE v = values.get(
0
);
52.
occurences.set(
0
, occurences.get(
0
) -
1
);
53.
return
v;
54.
}
55.
}
56.
57.
/**
58.
* Deletes a given value from the multiset (removes one occurrence)
59.
* @param val value
60.
* @return number of occurences of the value in the set after the deletion
61.
*/
62.
public
int
remove(VALUE e) {
63.
int
index = values.indexOf(e);
64.
int
curr = occurences.get(index);
65.
if
(curr !=
1
) {
66.
occurences.set(index, curr -
1
);
67.
return
curr -
1
;
68.
}
else
{
69.
values.remove(index);
70.
occurences.remove(index);
71.
return
0
;
72.
}
73.
}
74.
75.
/**
76.
* Query, if the multiset contains a given value
77.
* @param val value
78.
* @return number of occurences of the given value in the set
79.
*/
80.
public
int
contains(VALUE e) {
81.
int
index = values.indexOf(e);
82.
if
(index == -
1
)
return
0
;
83.
return
occurences.get(index);
84.
}
85.
86.
/**
87.
* Size of the multiset (including all multiplicities)
88.
* @return number of stored entities (values*occurences)
89.
*/
90.
public
int
size() {
91.
int
count =
0
;
92.
for
(Integer i : occurences){
93.
count += i;
94.
}
95.
return
count;
96.
}
97.
}
Have you ever written code like the following:
Map<MyClass,Integer> objectCounts = new HashMap<MyClass,Integer>(); public void incrementCount(MyClass obj) { Integer count = objectCounts.get(obj); if (count == null) { objectCounts.put(obj,0); } else { objectCounts.put(obj,count++); } } public int getCount(MyClass obj) { Integer count = objectCounts.get(obj); if (count == null) { return 0; } else { return count; } }
Bit unwieldy? Lets see how we might use a Multiset instead:
Multiset<MyClass> myMultiset = HashMultiset.create(); MyClass myObject = new MyClass(); myMultiset.add(myObject); myMultiset.add(myObject); // add it a second time. System.out.println(myMultiset.count(myObject)); // 2 myMultiset.remove(myObject); System.out.println(myMultiset.count(myObject)); // 1