Question

Create a method that gets the difference for a linked bag and a resizable array:

Also, implement the methods in the interface and test out that the program works in the main class

//please comment what you are doing for the difference method for the linked bag and the array bag (also explain its time complexity in terms of Big O

EX: Bag 1 has : ABC

EX: Bag 2 has : ARC

the difference is "R"

BagInterface

public boolean add(T anEntry);

public T remove(); //if you need this method, include it, if not then no worries

public boolean remove(T anEntry);

public int getFrequencyOf(T anEntry); //if you need this method, include it, if not then no worries

public T[] toArray();

public boolean contains(T anEntry);

public BagInterface<T> difference(BagInterface<T> otherBag);

ResizeableArrayBag

public class ResizeableArrayBag<T> implements BagInterface<T> {

private T[] bag;

private static final int DEFAULT_CAPACITY = 25;

private int numberOfEntries;

//constructor

public ResizeableArrayBag() {

this(DEFAULT_CAPACITY);

}

//constructor

public ResizeableArrayBag(int desiredCapacity) {

@SuppressWarnings("unchecked")

T[] tempBag = (T[]) new Object[desiredCapacity];

bag = tempBag;

numberOfEntries = 0;

}

public boolean add(T anEntry){

//write code

}

public T remove(){

//if you need this method, include it, if not then, no worries

}

public boolean remove(T anEntry){

//write code

}

public int getFrequencyOf(T anEntry){

//if you need this method, include it, if not then no worries

}

public T[] toArray(){

//write code

}

public boolean contains(T anEntry){

//write code

}

public BagInterface<T> difference(BagInterface<T> otherBag){

//write code, explain what is being done and give time complexity in terms of Big O notation

}

}

ResizeableArrayBagDemo

public class ResizeableArrayBagDemo {

public static void main(String[] args) {

ResizeableArrayBag<String> bag1 = new ResizeableArrayBag<>(1);

ResizeableArrayBag<String> bag2 = new ResizeableArrayBag<>();

bag1.add("z");

bag1.add("y");

bag1.add("c");

bag1.add("d");

bag2.add("z");

bag2.add("y");

bag2.add("e");

bag2.add("f");

System.out.print("The Difference of Bag One and Bag Two is: ");

System.out.println(Arrays.toString(bag1.difference(bag2).toArray())); //this should display [c,d,e,f]

}

}

Node Class

public class Node<T> {

public T data;

public Node<T> next;

public Node(T dataPortion) {

//write code

}

public Node(T dataPortion, Node<T> nextNode) {

//write code

}

public T getData() {

//write code

}

public void setData(T newData) {

//write code

}

public Node<T> getNextNode(){

//write code

}

public void setNextNode(Node<T> nextNode) {

//write code

}

}

Linked Bag

private Node<T> firstNode;

private int numberOfEntries;

public LinkedBag() {

firstNode = null;

numberOfEntries = 0;

}

public boolean add(T anEntry){

//write code

}

public T remove(){

//if you need this method, include it, if not then, no worries

}

public boolean remove(T anEntry){

//write code

}

public int getFrequencyOf(T anEntry){

//if you need this method, include it, if not then no worries

}

public T[] toArray(){

//write code

}

public boolean contains(T anEntry){

//write code

}

public BagInterface<T> difference(BagInterface<T> otherBag){

//write code, explain what is being done and give time complexity in terms of Big O notation

}

Linked Bag Demo

public class LinkedBagTest {

public static void main(String[] args) {

BagInterface<String> bag1 = new LinkedBag<>();

BagInterface<String> bag2 = new LinkedBag<>();

bag1.add("z");

bag1.add("y");

bag1.add("c");

bag1.add("d");

bag2.add("z");

bag2.add("y");

bag2.add("e");

bag2.add("f");

System.out.print("The Difference of Bag One and Bag Two is: ");

System.out.println(Arrays.toString(bag1.difference(bag2).toArray())); //this should display [c,d,e,f]

}

}

Answer 1

Solution:

In the code below 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.

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));
        }
}