pribic's blog

By pribic, history, 3 years ago, In English

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.

I solved https://codeforces.com/contest/527/problem/C using this.

Submission — https://codeforces.com/contest/527/submission/116237858

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();
    }
  }
  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?