Multimnožina
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
/**
* Multimnozina implementovana pomoci dvojice seznamu
* @author Pavel Micka
* @param <ENTITY> typovy parametr obsahu
*/
public class Multiset<VALUE> {
private List<VALUE> values;
private List<Integer> occurences;
/**
* Konstruktor
* @param initialCapacity kapacita, se kterou je inicializovan podrizeny seznam
*/
public Multiset(int initialCapacity) {
values = new ArrayList<VALUE>(initialCapacity);
occurences = new ArrayList<Integer>(initialCapacity);
}
/**
* Vlozi entitu do multimnoziny
* @param val dana entita
* @return pocet vyskytu entity po jejim pridani
*/
public int put(VALUE val) {
int index = values.indexOf(val);
if (index == -1) {
values.add(val);
occurences.add(1);
return 1;
} else {
int currCount = occurences.get(index);
occurences.set(index, currCount + 1);
return currCount + 1;
}
}
/**
* Vrati nahodne nejaky prvek z mnoziny (a snizi pocet jeho vyskytu o 1)
* @return prvek, @null pokud je mnozina prazdna
*/
public VALUE pick() {
if (values.size() == 0) {
return null;
}
if (occurences.get(0) == 1) {
VALUE v = values.remove(0);
occurences.remove(0);
return v;
} else {
VALUE v = values.get(0);
occurences.set(0, occurences.get(0) - 1);
return v;
}
}
/**
* Odstrani z mnoziny danou entitu (snizi pocet vyskytu o 1)
* @param val entita
* @return pocet vyskytu po odstraneni dane entity
*/
public int remove(VALUE e) {
int index = values.indexOf(e);
int curr = occurences.get(index);
if (curr != 1) {
occurences.set(index, curr - 1);
return curr - 1;
} else {
values.remove(index);
occurences.remove(index);
return 0;
}
}
/**
*
* Dotaz na pritomnost dane entity
* @param val entita
* @return pocet vyskytu dane entity
*/
public int contains(VALUE e) {
int index = values.indexOf(e);
if(index == -1) return 0;
return occurences.get(index);
}
/**
* Dotaz na velikost mnoziny (vcetne multiplicit)
* @return pocet prvku
*/
public int size() {
int count = 0;
for(Integer i : occurences){
count += i;
}
return count;
}
}
