Implementation of Bag data structure in Java

 

What is bag?

Bag is an unordered collection, which can contain duplicate elements.

 

Bag vs Set

Bag can contain duplicates, whereas set do not contain duplicates.

 

Bag vs List

Bag is an unordered collection, whereas list is a ordered collection.

 

You can considered a bag as unordered list or a set with duplicates.

 

Let’s implement following Bag methods using Java Map collection.

 

public int getCount(java.lang.Object o)

Return the number of occurrences of the given object currently in the bag. If the object does not exist in the bag, return 0.

 

public boolean add(java.lang.Object o)

Add the given object to the bag and keep a count. Return true if the object was not already added to the Bag.

 

public boolean add(java.lang.Object o, int i)

Add i copies of the given object to the bag and keep a count. Return true if the object was not already to the Bag.

 

public boolean remove(java.lang.Object o)

Remove all occurrences of the given object from the bag. Return true if this call changed the collection.

 

public boolean remove(java.lang.Object o, int i)

Remove the given number of occurrences from the bag. Return true if this call changed the collection.

 

public java.util.Set uniqueSet()

The Set of unique members that represent all members in the bag. Uniqueness is defined by equals method of objects.

 

public int size()

Returns the total number of items in the bag including duplicates.

 

public boolean removeAll(java.util.Collection c)

Remove all elements represented in the given collection, respecting cardinality. Return true if this call changed the collection.

 

public java.util.Iterator iterator()

Returns an Iterator over the entire set of members, including copies due to cardinality.  

 

public int countUniqueElements()

Return number of unique elements in the Bag.

 

Bag.java 

package com.sample.app.collections;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Bag<E> {

  private Map<E, Integer> map;

  /**
   * Return total elements including duplicates
   */
  private int totalElements;

  public Bag() {
    map = new HashMap<E, Integer>();
  }

  public int getCount(E obj) {
    if (obj == null) {
      return 0;
    }

    return map.get(obj);
  }

  public boolean add(E obj) {
    if (obj == null) {
      throw new IllegalArgumentException("null can't be added");
    }

    Integer count = map.get(obj);
    totalElements++;

    if (count == null) {
      map.put(obj, 1);
      return true;
    } else {
      count++;
      map.put(obj, count);
      return false;
    }

  }

  public boolean add(E obj, int noOfTimes) {
    if (obj == null) {
      throw new IllegalArgumentException("null can't be added");
    }

    if (noOfTimes <= 0) {
      throw new IllegalArgumentException("noOfTimes must be > 0");
    }

    Integer count = map.get(obj);
    totalElements += noOfTimes;

    if (count == null) {
      map.put(obj, noOfTimes);
      return true;
    } else {
      map.put(obj, count + noOfTimes);
      return false;
    }
  }

  public boolean remove(E obj) {
    if (obj == null) {
      throw new IllegalArgumentException("null can't be added");
    }

    Integer count = map.get(obj);

    if (count == null) {
      return false;
    }

    map.remove(obj);
    totalElements -= count;
    return true;
  }

  public boolean remove(E obj, int noOfTimes) {
    if (obj == null) {
      throw new IllegalArgumentException("null can't be added");
    }

    Integer count = map.get(obj);

    if (count == null) {
      return false;
    }

    if (noOfTimes >= count) {
      map.remove(obj);
      totalElements -= count;
    } else {
      count -= noOfTimes;
      totalElements -= noOfTimes;
      map.put(obj, count);
    }
    return true;

  }

  public java.util.Set<E> uniqueSet() {
    return map.keySet();
  }

  public int size() {
    return totalElements;
  }

  public boolean removeAll(Collection<E> collection) {
    int currentTotal = totalElements;

    for (E obj : collection) {
      if (obj == null) {
        continue;
      }

      this.remove(obj, 1);
    }

    int newTotal = totalElements;

    return (currentTotal != newTotal);
  }

  public Iterator<Map.Entry<E, Integer>> iterator() {
    return map.entrySet().iterator();
  }

  public int countUniqueElements() {
    return map.size();
  }

  @Override
  public String toString() {
    return "Bag [elements=" + map + ", totalElements=" + totalElements + "]";
  }

}

 

BagDemo.java

package com.sample.app;

import com.sample.app.collections.Bag;

public class BagDemo {

  public static void main(String[] args) {
    Bag<String> bag = new Bag<> ();
    
    // Add elements to the bag
    bag.add(new String("Hello"));
    bag.add(new String("Hi"));
    bag.add(new String("Hello"));
    bag.add(new String("Hi"));
    System.out.println(bag);
    
    // Add the element 'Hi' 3 times.
    bag.add(new String("Hi"), 3);
    System.out.println(bag);
    
    // Remove the element 'Hello' completely
    // Remove the element 'Hi' 2 times
    bag.remove(new String("Hello"));
    bag.remove(new String("Hi"), 2);
    System.out.println(bag);
    
  }
}

 

Output

Bag [elements={Hi=2, Hello=2}, totalElements=4]
Bag [elements={Hi=5, Hello=2}, totalElements=7]
Bag [elements={Hi=3}, totalElements=3]

 

 

You may like

Interview Questions

Method overloading ambiguity with null values in Java

Quick guide to load balancers

Constant folding in Java

Quick guide to assertions in Java

java.util.Date vs java.sql.Date

How to break out of nested loops in Java?