Multimnožina (multiset, množina s opakováním, bag) je datový typ vycházející z množiny. Multimnožina slouží jako kontejner na entity, jenž negarantuje pořadí uložených prvků, a který může obsahovat jednotlivé prvky (hodnoty) vícekrát.
Implementace
Nejjednodušším způsobem implementace je použít list a zapomenout na pořadí. Tento způsob je ovšem velmi neefektivní z hlediska použité paměti, pokud se prvky často opakují. Druhou možností je využití dvojice seznamů, z nichž ten první obsahuje hodnoty a druhý zaznamenává počty jejich výskytů. Tento postup je efektivnější, ale stále vyžaduje poměrně náročnou operaci průchodu seznamem pro přístup k jednotlivým položkám (asymptotická složitost ). Z tohoto důvodu se pro efektivní implementaci využívá hashovací tabulka, která umožňuje přístup k položkám s očekávanou konstantní složitostí.
Kód
01.
/**
02.
* Multimnozina implementovana pomoci dvojice seznamu
03.
* @author Pavel Micka
04.
* @param <ENTITY> typovy parametr obsahu
05.
*/
06.
public
class
Multiset<VALUE> {
07.
08.
private
List<VALUE> values;
09.
private
List<Integer> occurences;
10.
11.
/**
12.
* Konstruktor
13.
* @param initialCapacity kapacita, se kterou je inicializovan podrizeny seznam
14.
*/
15.
public
Multiset(
int
initialCapacity) {
16.
values =
new
ArrayList<VALUE>(initialCapacity);
17.
occurences =
new
ArrayList<Integer>(initialCapacity);
18.
}
19.
20.
/**
21.
* Vlozi entitu do multimnoziny
22.
* @param val dana entita
23.
* @return pocet vyskytu entity po jejim pridani
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.
* Vrati nahodne nejaky prvek z mnoziny (a snizi pocet jeho vyskytu o 1)
40.
* @return prvek, @null pokud je mnozina prazdna
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.
* Odstrani z mnoziny danou entitu (snizi pocet vyskytu o 1)
59.
* @param val entita
60.
* @return pocet vyskytu po odstraneni dane entity
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.
*
77.
* Dotaz na pritomnost dane entity
78.
* @param val entita
79.
* @return pocet vyskytu dane entity
80.
*/
81.
public
int
contains(VALUE e) {
82.
int
index = values.indexOf(e);
83.
if
(index == -
1
)
return
0
;
84.
return
occurences.get(index);
85.
}
86.
87.
/**
88.
* Dotaz na velikost mnoziny (vcetne multiplicit)
89.
* @return pocet prvku
90.
*/
91.
public
int
size() {
92.
int
count =
0
;
93.
for
(Integer i : occurences){
94.
count += i;
95.
}
96.
return
count;
97.
}
98.
}