Implement Multiset in Java

Multiset is similar to a Set, but it allows duplicate elements. Repetition of the elements in Multiset is explicitly counted.

 

For example,

 

a.   The set {1, 2} contains only elements 1 and 2, each having multiplicity 1 when {1, 2} is seen as a multiset.

b.   In the multiset {1, 1, 2}, the element 1 has multiplicity 2, and 2 has multiplicity 1.

c.    In the multiset {1, 1, 1, 2, 2, 2}, 1 and 2 both have multiplicity 3.

 

Following are the common operations to be performed in MultiSet.

a.   Adding elements,

b.   Removing elements,

c.    Counting occurrences, and

d.   Computing unions or intersections.

 

We can implement Multiset using Maps in Java.

 

Find the below working application.

 

Multiset.java

package com.sample.app.collections;

import java.util.Collection;
import java.util.Map;
import java.util.StringJoiner;
import java.util.concurrent.ConcurrentHashMap;

public class Multiset<T> {

	private final Map<T, Integer> elementCountMap = new ConcurrentHashMap<>();

	public void add(T t) {
		add(t, 1);
	}

	/**
	 * Add given key count times.
	 * 
	 * @param key
	 * @param count
	 */
	public void add(T key, int count) {
		if (count <= 0) {
			throw new IllegalArgumentException("count is <= 0");
		}
		Integer elementCount = elementCountMap.get(key);
		if (elementCount == null) {
			elementCount = 0;
		}
		elementCount += count;
		elementCountMap.put(key, elementCount);
	}

	public void remove(T t) {
		remove(t, 1);
	}

	/**
	 * if multiplicity(key) is < count, then it removes all the entries of the key
	 * 
	 * @param key
	 * @param count
	 */
	public void remove(T key, int count) {
		if (count <= 0) {
			throw new IllegalArgumentException("count is <= 0");
		}

		if (multiplicity(key) <= count) {
			elementCountMap.remove(key);
			return;
		}
		Integer elementCount = elementCountMap.get(key);
		if (elementCount == null || elementCount == 0) {
			return;
		}
		elementCount -= count;
		elementCountMap.put(key, elementCount);
	}

	public int multiplicity(T key) {
		Integer value = elementCountMap.get(key);
		return (value == null) ? 0 : value;
	}

	public Collection<T> distinctKeys() {
		return elementCountMap.keySet();
	}

	public long totalKeys() {
		long size = 0;
		for (T k : distinctKeys()) {
			size += multiplicity(k);
		}
		return size;
	}

	@Override
	public String toString() {

		StringBuilder builder = new StringBuilder();
		builder.append("{");

		StringJoiner joiner = new StringJoiner(",");

		for (Map.Entry<T, Integer> entry : elementCountMap.entrySet()) {
			T key = entry.getKey();
			Integer val = entry.getValue();

			for (int i = 0; i < val; i++) {
				joiner.add(key.toString());
			}
		}

		builder.append(joiner.toString());

		builder.append("}");
		return builder.toString();
	}

	public void stats() {
		System.out.println("distinctKeys : " + distinctKeys());
		System.out.println("totalKeys : " + totalKeys());
		System.out.println("elements : " + toString());
	}
}

MultisetDemo.java

package com.sample.app;

import com.sample.app.collections.Multiset;

public class MultisetDemo {

	public static void main(String[] args) {
		Multiset<Integer> multiSet = new Multiset<>();
		multiSet.stats();

		System.out.println("\nAdd 1 ad 2 to the Multiset\n");
		multiSet.add(1);
		multiSet.add(2);
		multiSet.stats();

		System.out.println("\nAdd 1 two times and 2 three times\n");
		multiSet.add(1, 2);
		multiSet.add(2, 3);
		multiSet.stats();

		System.out.println("\nRemove 1\n");
		multiSet.remove(1);
		multiSet.stats();

		System.out.println("\nRemove 2 five times\n");
		multiSet.remove(2, 5);
		multiSet.stats();

	}

}

Output

distinctKeys : []
totalKeys : 0
elements : {}

Add 1 ad 2 to the Multiset

distinctKeys : [1, 2]
totalKeys : 2
elements : {1,2}

Add 1 two times and 2 three times

distinctKeys : [1, 2]
totalKeys : 7
elements : {1,1,1,2,2,2,2}

Remove 1

distinctKeys : [1, 2]
totalKeys : 6
elements : {1,1,2,2,2,2}

Remove 2 five times

distinctKeys : [1]
totalKeys : 2
elements : {1,1}

 

You may like

Interview Questions

Collection programs in Java

Array programs in Java

LinkedHashTable implementation in Java

Get the enumeration from a Collection

Get the enumeration from an Iterator in Java

Get a map from enum in Java

Construct a map from array of objects using streams