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?

Extract the elements of specific type in a collection

 

Problem statement

I have a collection to store apples, bananas, oranges and mangoes. Write a program to extract specific type of fruits from the collection.

 

Approach 1:

We can solve this problem by isInstance() method of java.lang.Class.

 

Signature

public native boolean isInstance(Object obj);

 

isInstace method return true, if the object is an instance of given class, else false. This method is the dynamic equivalent of the Java language instanceof operator.

 

Fruit.java

package com.sample.app.interfaces;

public interface Fruit {
    
    public String aboutMe();

}

Apple.java

package com.sample.app.dto;

import com.sample.app.interfaces.Fruit;

public class Apple implements Fruit{

    @Override
    public String aboutMe() {
        return "I am Apple";
    }

}

Banana.java

package com.sample.app.dto;

import com.sample.app.interfaces.Fruit;

public class Banana implements Fruit{

    @Override
    public String aboutMe() {
        return "I am Banana";
    }

}

Orange.java

package com.sample.app.dto;

import com.sample.app.interfaces.Fruit;

public class Orange implements Fruit{

    @Override
    public String aboutMe() {
        return "I am Orange";
    }

}

Mango.java

package com.sample.app.dto;

import com.sample.app.interfaces.Fruit;

public class Mango implements Fruit{

    @Override
    public String aboutMe() {
        return "I am Mango";
    }

}

App.java

package com.sample.app;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import com.sample.app.dto.Apple;
import com.sample.app.dto.Banana;
import com.sample.app.dto.Mango;
import com.sample.app.dto.Orange;
import com.sample.app.interfaces.Fruit;

public class App {

    private static List<Fruit> filterFruits(List<Fruit> fruits, Class clazz) {

        return fruits
                .stream()
                .filter(obj -> clazz.isInstance(obj))
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList() {
            {
                this.add(new Apple());
                this.add(new Orange());
                this.add(new Banana());
                this.add(new Mango());
                this.add(new Apple());
                this.add(new Banana());
                this.add(new Orange());
            }
        };
        
        filterFruits(fruits, Apple.class).forEach(fruit -> System.out.println(fruit.aboutMe()));

    }
}

Output

I am Apple
I am Apple

Looks fine, but there is one specific behavior with isInstace method that we need to consider. ‘isInstance’ method returns true if the specified Object argument is an instance of the represented class or of any of its subclasses.

 

Let’s define GreenApple class.

 

GreenApple.java

package com.sample.app.dto;

public class GreenApple extends Apple{

    @Override
    public String aboutMe() {
        return "I am green apple";
    }
}

Let’s update the collection by adding GreenApple instances and try to extract only Apple objects.

 

App.java

package com.sample.app;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import com.sample.app.dto.Apple;
import com.sample.app.dto.Banana;
import com.sample.app.dto.GreenApple;
import com.sample.app.dto.Mango;
import com.sample.app.dto.Orange;
import com.sample.app.interfaces.Fruit;

public class App {

    private static List<Fruit> filterFruits(List<Fruit> fruits, Class clazz) {

        return fruits
                .stream()
                .filter(obj -> clazz.isInstance(obj))
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList() {
            {
                this.add(new Apple());
                this.add(new Orange());
                this.add(new Banana());
                this.add(new Mango());
                this.add(new Apple());
                this.add(new Banana());
                this.add(new Orange());
                
                this.add(new GreenApple());
                this.add(new GreenApple());
            }
        };
        
        filterFruits(fruits, Apple.class).forEach(fruit -> System.out.println(fruit.aboutMe()));

    }
}

Output

I am Apple
I am Apple
I am green apple
I am green apple

This approach is fine, if you want to extract all the elements of this type and sub types, but if you want to extract exact type matching elements (not the sub classes), then you can do class comparison.

 

Example

clazz.equals(obj.getClass())

 

Approach 2: Using Class.isAssignableFrom method.

 

Signature

public native boolean isAssignableFrom(Class<?> cls)

Determines if the class or interface represented by this Class object is either the same as, or is a superclass or superinterface of, the class or interface represented by the specified Class parameter. It returns true if so; otherwise it returns false

 

Just like isInstace method, this method also do not filter subclass objects.

 

 

App.java

package com.sample.app;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import com.sample.app.dto.Apple;
import com.sample.app.dto.Banana;
import com.sample.app.dto.GreenApple;
import com.sample.app.dto.Mango;
import com.sample.app.dto.Orange;
import com.sample.app.interfaces.Fruit;

public class App {

    private static List<Fruit> filterFruits(List<Fruit> fruits, Class clazz) {

        return fruits
                .stream()
                .filter(obj -> clazz.isAssignableFrom(obj.getClass()))
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList() {
            {
                this.add(new Apple());
                this.add(new Orange());
                this.add(new Banana());
                this.add(new Mango());
                this.add(new Apple());
                this.add(new Banana());
                this.add(new Orange());
                
                this.add(new GreenApple());
                this.add(new GreenApple());
            }
        };
        
        filterFruits(fruits, Apple.class).forEach(fruit -> System.out.println(fruit.aboutMe()));

    }
}

Output

I am Apple
I am Apple
I am green apple
I am green apple

Approach 3: Using class comparison of the object.

private static List<Fruit> filterFruits(List<Fruit> fruits, Class clazz) {

    return fruits
            .stream()
            .filter(obj -> clazz.equals(obj.getClass()))
            .collect(Collectors.toList());
}

Find the below working application.

 

App.java

package com.sample.app;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import com.sample.app.dto.Apple;
import com.sample.app.dto.Banana;
import com.sample.app.dto.GreenApple;
import com.sample.app.dto.Mango;
import com.sample.app.dto.Orange;
import com.sample.app.interfaces.Fruit;

public class App {

    private static List<Fruit> filterFruits(List<Fruit> fruits, Class clazz) {

        return fruits
                .stream()
                .filter(obj -> clazz.equals(obj.getClass()))
                .collect(Collectors.toList());
    }

    public static void main(String[] args) {
        List<Fruit> fruits = new ArrayList() {
            {
                this.add(new Apple());
                this.add(new Orange());
                this.add(new Banana());
                this.add(new Mango());
                this.add(new Apple());
                this.add(new Banana());
                this.add(new Orange());
                
                this.add(new GreenApple());
                this.add(new GreenApple());
            }
        };
        
        filterFruits(fruits, Apple.class).forEach(fruit -> System.out.println(fruit.aboutMe()));

    }
}

Output

I am Apple
I am Apple

If you are interested in sub class objects too, then use either of approach1 and approach2, if you are interested only in given type of class (not the sub class objects), then use approach 3.

 

You may like

Interview Questions

How to check two double values for equality?

Why to do explicit type casting from double to float conversion?

When is a class or interface is initialized or loaded in Java?

How to check two float values equality?

How to check whether a class is loaded or not in Java?

How to get a random element from Set?