MultiSet for java (using TreeMap / HashMap)

Правка en1, от UniversalAdmin, 2021-09-26 20:39:42

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский UniversalAdmin 2021-09-26 20:39:42 3874 Initial revision (published)