Since using HashMap/TreeMap in java as a multiset requires a lot of typing I made these templates to make the code shorter and more readable.
You can use the HashMap implementation if you don't want to keep your elements sorted while you can use TreeMap implementation if you want to keep them sorted and be able to use binary search.
Note -> Both of these templates use generics and have long type for counting the number of elements.
Note -> These templates are only for competitive programming purpose so I have not added code to handle potential out of bounds or null pointer errors feel free to add those if you want.
Note -> Only use del function if you know for sure that the element is present in the set otherwise you will get a null pointer exception.
HashMap template ->
static class hm <T extends Comparable<T>>{
HashMap<T, Long> hm = new HashMap<>();
long sz = 0;
public boolean c(T elem) {return hm.containsKey(elem);}
public void rep(T elem, long i) {hm.replace(elem, hm.get(elem)+i);}
public void add(T elem) {
if(c(elem))rep(elem, 1L);
else { hm.put(elem, 1L);}
sz++;
}
public void del(T elem) {
if(c(elem)) rep(elem, -1L);
if(hm.get(elem)==0L) { hm.remove(elem);}
sz--;
}
public long uniqueSz() {return hm.size();}
public long sz() {return sz;}
public Set<T> ks() { return hm.keySet();}
public Collection<Long> val() {return hm.values();}
}
TreeMap template ->
static class tm <T extends Comparable<T>>{
static class tm <T extends Comparable<T>>{
TreeMap<T, Long> tm = new TreeMap<>();
long sz = 0;
public boolean c(T elem) {return tm.containsKey(elem);}
public void rep(T elem, long i) {tm.replace(elem, tm.get(elem)+i);}
public void add(T elem) {
if(c(elem))rep(elem, 1L);
else { tm.put(elem, 1L);}
sz++;
}
public void del(T elem) {
if(c(elem)) rep(elem, -1L);
if(tm.get(elem)==0L) {tm.remove(elem);}
sz--;
}
public long uniqueSize() {return tm.size();}
public long sz() {return sz;}
public Set<T> ks () { return tm.keySet(); }
public Collection<Long> val() {return tm.values();}
public T lb(T elem) {return tm.ceilingKey(elem);}
public T ub(T elem) {return tm.higherKey(elem);}
public T floor(T elem) {return tm.floorKey(elem);}
public T lower(T elem) {return tm.lowerKey(elem);}
public T least(T elem) {return tm.firstKey();}
public T highest(T elem) {return tm.lastKey();}
}
Description of methods and variables ->
uniqueSz -> returns the number of unique elements in the set
sz -> return the total number of elements in the set
c -> checks if the set contains the provided element
rep -> Replaces the freq of provided element by provided number
add -> Adds the element to set
del -> removes the element from set
ks -> returns the set of all keys
Methods unique to TreeMap implementation ->
Note -> return null if there is no matching element found
lb -> lowerBound
ub -> upperBound
floor -> returns the first key lower than or equal to provided element
lower -> returns the first key strictly lower than the provided element
least -> returns the least key in set
highest -> returns the highest key in set
Note ->
All the methods in HashMap implementation are of constant time complexity
Whereas methods in TreeMap such as add, del, rep and searching methods have logarithmic time complexity
Regards,
Please comment any corrections if needed and any more functionality that can be added to these templates.
or you can use C++