Question

[JAVA]

Please make sure there are FIVE (5) different source codes. Do not copy your answers or someone’s else answers from different Cheggs. I did not post this question to see the same answers. All information that was given is included. Thank you. I will upvote if you do it properly.

Task 1: Add three methods: union, intersection, and difference to the interface BagInterface for the ADT bag.

Task 2: Implement the three methods, union, intersection, and difference, for the class ResizeableArrayBag. Note: the class ResizeableArrayBag presents an implementation of the ADT bag using a resizable array.

Task 3: Implement the three methods, union, intersection, and difference, for the class LinkedBag. Note: the class LinkedBag presents an implementation of the ADT bag using a linked chain.

Task 4: Write a client program, “ArrayBagTest.java”, which contains a main method to test the three methods (union, intersection, and difference) you implemented for the class ResizeableArrayBag.

Task 5: Write a client program, “LinkedBagTest.java”, which contains a main method to test the three methods (union, intersection, and difference) you implemented for the class LinkedBag.

• • Union

The union of two collections consists of their contents combined into a new collection. Add a method union to the interface BagInterface for the ADT bag that returns as a new bag the union of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.

Note that the union of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the union of these bags contains x seven times. Specifically, suppose that bag1 and bag2 are Bag objects, where Bag implements BagInterface; bag1 contains the String objects a, b, and c; and bag2 contains the String objects b, b, d, and e. After the statement

BagInterface everything = bag1.union(bag2);

executes, the bag everything contains the strings a, b, b, b, c, d, and e. Note that union does not affect the contents of bag1 and bag2.

• • Intersection

The intersection of two collections is a new collection of the entries that occur in both collections. That is, it contains the overlapping entries. Add a method intersection to the interface BagInterface for the ADT bag that returns as a new bag the intersection of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method. 3

Note that the intersection of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the intersection of these bags contains x twice. Specifically, suppose that bag1 and bag2 are Bag objects, where Bag implements BagInterface; bag1 contains the String objects a, b, and c; and bag2 contains the String objects b, b, d, and e. After the statement

BagInterface commonItems = bag1.intersection(bag2);

executes, the bag commonItems contains only the string b. If b had occurred in bag1 twice, commonItems would have contained two occurrences of b, since bag2 also contains two occurrences of b. Note that intersection does not affect the contents of bag1 and bag2.

• • Difference

The difference of two collections is a new collection of the entries that would be left in one collection after removing those that also occur in the second. Add a method difference to the interface BagInterface for the ADT bag that returns as a new bag the difference of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.

Note that the difference of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the difference of these bags contains x three times. Specifically, suppose that bag1 and bag2 are Bag objects, where Bag implements BagInterface; bag1 contains the String objects a, b, and c; and bag2 contains the String objects b, b, d, and e. After the statement

BagInterface leftOver1 = bag1.difference(bag2);

executes, the bag leftOver1 contains the strings a and c. After the statement

BagInterface leftOver2 = bag2.difference(bag1);

executes, the bag leftOver2 contains the strings b, d, and e. Note that difference does not affect the contents of bag1 and bag2.

Answer 1

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

// TODO could be well documented java doc
// and classes can be put into different files

// bag contract
// custom type T should implement equals and hashcode
// data order in the bag does not matter 
abstract class Bag<T> {
        
        // this list has to initialized as per implementation strategy
        protected List<T> data;
        
        // add collections of data
        public void addAll(Collection<T> data) {
                this.data.addAll(data);
        }
        
        // add data one by one
        public void add(T ... data) {
                for(T d : data) {
                        this.data.add(d);
                }
        }
        
        // union of two bags
        public final Bag<T> union(Bag<T> bag) {
                // union with another bag
                // here new bag data order does not matter
                Bag<T> newbag = new ResizableArrayBag<T>();
                newbag.addAll(this.data);
                newbag.addAll(bag.data);
                return newbag;
        }
        
        // internal usage
        Map<T, Integer> map(Bag<T> bag) {
                Map<T, Integer> elements = new HashMap<>(); // track duplicate elements
                for(T d : bag.data) {
                        if(elements.containsKey(d)) {
                                elements.put(d, elements.get(d) + 1);
                        } else {
                                elements.put(d, 1);
                        }
                }
                return elements;
        }
        
        // intersection of two bags
        public final Bag<T> intersection(Bag<T> bag) {
                Map<T, Integer> elements = map(this);
                // intersection
                // here new bag data order does not matter
                Bag<T> newbag = new ResizableArrayBag<T>();
                for(T d : bag.data) {
                        if(elements.containsKey(d)) {
                                // common
                                int c = elements.get(d);
                                newbag.add(d);
                                c--;
                                // track common elements
                                if(c == 0) {
                                        elements.remove(d);
                                } else {
                                        elements.put(d, c);
                                }
                        }
                }
                return newbag;
        }
        
        // difference of two bags
        public final Bag<T> difference(Bag<T> bag) {
                Map<T, Integer> elements = map(bag);
                // difference
                // here new bag data order does not matter
                Bag<T> newbag = new ResizableArrayBag<T>();
                for(T d : this.data) {
                        if(elements.containsKey(d)) {
                                int c = elements.get(d);
                                c--;
                                // remove common elements from another bag
                                if(c == 0) {
                                        elements.remove(d);
                                } else {
                                        elements.put(d, c);
                                }
                        } else {
                                // can be put into new bag directly
                                newbag.add(d);
                        }
                }
                return newbag;
        }
        
        // text representation
        @Override
        public String toString() {
                StringBuilder text = new StringBuilder();
                text.append('[');
                int s = data.size();
                if(s > 0) {
                        text.append(data.get(0));
                        for(int i = 1; i < s; i++) {
                                text.append(", ").append(data.get(i));
                        }
                }
                text.append(']');
                
                return text.toString();
        }
}

// one implementation using array-list
class ResizableArrayBag<T> extends Bag<T> {
        // constructor
        public ResizableArrayBag() {
                this.data = new ArrayList<T>();
        }
}

// another implementation is based on linked list
class LinkedBag<T> extends Bag<T> {
        public LinkedBag() {
                this.data = new LinkedList<T>();
        }
}

// collection bag implementations
public class CollectionBag {
        
        // test method (instead of client program and putting all test cases into main method)
        public static void main(String[] args) {
                // resizable array bag
                Bag<Character> bag1 = new ResizableArrayBag<Character>();
                bag1.add('a', 'b', 'b', 'c');
                Bag<Character> bag2 = new ResizableArrayBag<Character>();
                bag2.add('b', 'b', 'b', 'c', 'd', 'e');
                
                // test 3 methods
                System.out.println(bag1.union(bag2));
                System.out.println(bag1.intersection(bag2));
                System.out.println(bag1.difference(bag2));
                
                // linked bag
                bag1 = new LinkedBag<Character>();
                bag1.add('a', 'b', 'b', 'c');
                bag2 = new LinkedBag<Character>();
                bag2.add('b', 'b', 'b', 'c', 'd', 'e');
                
                // test 3 methods
                System.out.println(bag1.union(bag2));
                System.out.println(bag1.intersection(bag2));
                System.out.println(bag1.difference(bag2));
        }
}

I created one java file and there is a main class and all other utility classes are defined there. All utility classes could be defined in different files. And I didn't create ArrayBagTest.java and LinkedBagTest.java instead I put all test cases into the main method of the main class.