Java MultiSet

Revision en1, by pribic, 2021-05-15 10:36:20

Since we don't have multisets in Java, tried my luck to build one.

Reviews and feedbacks are welcome.

Basic idea is we keep another frequency map for each object. Whenever, we add an element, we update this frequency map as well. Whenever we remove, we check if that element now has frequency 0, if yes then only we remove it from set. Also we are using TreeSet so all the elements will be sorted and all TreeSet features are available out of the box.

static class MultiSet<T> extends TreeSet<T> {
    Map<T, Integer> frequency;

    public MultiSet() {
      this.frequency = new HashMap<>();
    }

    @Override
    public boolean add(T t) {
      frequency.put(t, frequency.getOrDefault(t, 0) + 1);
      return super.add(t);
    }


    @Override
    public boolean remove(Object o) {
      if (!frequency.containsKey(o))
        return false;
      frequency.put((T) o, frequency.getOrDefault(o, 1) - 1);
      if (frequency.get(o) == 0) {
        frequency.remove(o);
        super.remove(o);
      }
      return true;
    }

    @Override
    public String toString() {
      return new StringJoiner(", ", MultiSet.class.getSimpleName() + "[", "]")
        .add("frequency=" + frequency)
        .add(super.toString())
        .toString();
    }
  }
Tags #multiset, #java, #dsa

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pribic 2021-05-15 10:41:55 146
en1 English pribic 2021-05-15 10:36:20 1339 Initial revision (published)