Homework SourseObjective The objective of this assignment is to implement a
Objective:
The objective of this assignment is to implement a Set as a linked list. Note that a Set does not have duplicates.
------------------------------
Tasks:
You are given a class called LinkedList that contains an inner class called Node. Download the LinkedList class containing Node here (https://codeshare.io/GA8vpa).
Your task is to implement a new class called Set that extends the given LinkedList class and implements the given interface called ISet. Download ISet here (https://codeshare.io/aVBjPa). You will declare your Set class as follows:
You may NOT use any existing Java Collections class including but not limited to ArrayList and HashSet.
The methods in ISet are as follows:
public void add(Object item):
This method adds an item to the set. A duplicate item is not added. Hint: Override the add method defined in the LinkedList class but use its functionality using super.
public boolean in(Object item):
This method returns true if the item is in the set, false otherwise.
public Object[] toArray():
This method returns a new array that contains all the items in the set. If the size of the set is 0, return an empty array. The objects in the set are unique (i.e., no duplicates), so the returned array cannot contain duplicates.
public ISet fromArray(Object[] elements):
This method creates and returns a new set from the items contained in the elements array. The array may contain duplicates, but the Set implementation should not contain duplicates. If the array is empty or null, return a set of size 0 with head referring to null. If duplicates of an item are present in the array, then ignore all the occurrences of this item after the first one.
public ISet intersection(ISet other):
This method returns a new set that contains only those items that are present in both \"this\" set and the other set. The order of items in the returned set does not matter. The other set and \"this\" set remain unchanged.
public ISet union(ISet other):
This method returns a new set that contains the union of the items that are present in \"this\" set and the other set. Obviously common elements should appear only once in the result. The order of items in the returned set does not matter. The other set and \"this\" set remain unchanged.
------------------------------
Testing:
You cannot change ISet, i.e., no method declarations may be added, deleted, or changed. You cannot change the implementation of LinkedList. Do not copy the methods from LinkedList to Set. You should only implement the new methods declared in ISet in Set. It is okay to add private helper methods to Set.
Test your program with test data in addition to what is already provided in the assignment below. Keep in mind that we will not test your main method -- the methods you implement will be tested directly. However, you should use your main to test the methods that you write. A barebones main for Set can include something like:
------------------------------
THANKYOUUUUUUUUUUUUUUUUUU:D
Solution
SOURCE CODE:
package Linked;
import java.util.Arrays;
public class Set extends LinkedList implements ISet {
@Override
public void add(Object item)
{
if(this.in(item) == false)
super.add(item);
}
@Override
public boolean in(Object item) {
boolean t = false;
Object[] obj = this.toArray();
for(int i=0;i<obj.length;i++)
if(obj[i].toString().equals(item.toString()))
t=true;
return t;
}
@Override
public Object[] toArray() {
Object[] ret=new Object[this.size];
int i=0;
for (Node current = head; current != null; current = current.getNext())
ret[i++] = current;
return ret;
}
@Override
public ISet fromArray(Object[] elements) {
Set s = new Set();
for(int i=0;i<elements.length;i++)
s.add(elements[i]);
return s;
}
@Override
public ISet intersection(ISet other) {
Object[] obj1 = other.toArray();
Object[] obj2 = this.toArray();
Set s = new Set();
for(int i=0;i<obj1.length;i++)
for(int j=0;j<obj2.length;j++)
if(obj1[i].toString().equals(obj2[j].toString())==true)
{
s.add(obj1[i]);
}
return s;
}
@Override
public ISet union(ISet other) {
Object[] obj1 = other.toArray();
Object[] obj2 = this.toArray();
int i=0,j=0;
Set s = new Set();
while(i<obj1.length && j<obj2.length)
{
s.add(obj1[i++]);
s.add(obj2[j++]);
}
while(i<obj1.length)
{
s.add(obj1[i++]);
}
while(j<obj2.length)
{
s.add(obj1[i++]);
}
return s;
}
@Override
public int size()
{
return super.size();
}
@Override
public Node head()
{
return super.head();
}
@Override
public void clear()
{
super.clear();
}
public static void main(String[] args) {
ISet tester = new Set();
String[] names = {\"Alex\", \"Hajar\", \"Asa\", \"Sudipto\", \"Koen\", \"Asa\"};
ISet s1 = tester.fromArray(names);
System.out.println(\"After creating set s1 from array:\ \" + s1);
System.out.println(\"Printing array from s1:\ \"+ Arrays.toString(s1.toArray()));
String[] otherNames = {\"Gareth\", \"Alex\", \"Swapnil\", \"Chris\", \"Asa\"};
ISet s2 = tester.fromArray(otherNames);
System.out.println(\"After creating set s2 from array:\ \" + s2);
ISet s3 = s1.intersection(s2);
System.out.println(\"Intersection of s1 and s2:\ \" + s3);
ISet s4 = s1.union(s2);
System.out.println(\"Union of s1 and s2:\ \" + s4);
}
}
-------------------------------------------------------------------------------------
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Linked;
public class LinkedList {
protected Node head; // refers to the first node in the linked list.
protected int size; // the number of elements in the linked list.
/*
* Constructor: creates an empty linked list
*/
public LinkedList() {
head = null;
size = 0;
}
/*
* Clears the contents of the current linked list
*/
public void clear() {
head = null;
size = 0;
}
/*
* Returns the reference of the head node in the current linked list
*/
public Node head() {
return head;
}
/*
* adds an item as a node at the end of the current list.
*/
public void add(Object item) {
if(head==null) {
head = new Node(item);
size = 1;
} else {
Node current = head;
while(current.getNext() != null) {
current = current.getNext();
}
current.setNext(new Node(item));
size++;
}
}
/*
* removes first node containing the given item
*/
public boolean remove(Object item) {
if (size == 0)
return false;
if (item.equals(head.getItem())) {
head = head.getNext();
size--;
return true;
} else {
// locate predecessor of node to be removed
Node curr = head;
while (curr.getNext() != null
&& !item.equals(curr.getNext().getItem())) {
curr = curr.getNext();
}
// if node is not in the list
if (curr.getNext() == null)
return false;
else {
curr.setNext(curr.getNext().getNext());
size--;
return true;
}
}
}
/*
* returns the number of nodes in the linked list
*/
public int size() {
return size;
}
/*
* returns true if there are no elements in the linked list. false otherwise.
*/
public boolean isEmpty() {
return size == 0;
}
/*
* returns the string representation of the linked list.
*/
@Override
public String toString() {
String res = \"[\" + size + \": \";
for (Node current = head; current != null; current = current.getNext())
res += current.getItem().toString() + \" \";
return res + \"]\";
}
/*
* Inner class used to represent each node.
*/
public class Node {
private Object item;
private Node next;
public Node(Object item) {
this.item = item;
this.next = null;
}
public Node(Object item, Node next) {
this.item = item;
this.next = next;
}
public void setNext(Node nextNode) {
next = nextNode;
}
public Node getNext() {
return next;
}
public Object getItem() {
return item;
}
public void setItem(Object item){
this.item = item;
}
public String toString(){
return item.toString();
}
}
}
------------------------------------------------------------------------------------------------
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Linked;
/*
* SetInterface declares the methods that you must implement in P7.
* You will implement a Set using a LinkedList.
* You will need to make sure that the Set contains no duplicates.
*/
public interface ISet {
/*
* Adds an item to the set. A duplicate item isn\'t added.
*/
public void add(Object item);
/*
* This method returns true if the item is in the set, false otherwise.
*/
public boolean in(Object item);
/*
* Return a new array that contains all the items in the set.
* If the size of the set is 0, return an empty array.
* The objects in the set are unique (i.e., no duplicates), so
* the returned array cannot contain duplicates.
*/
public Object[] toArray();
/*
* Create and return a new set from the items contained in the elements array.
* The array may contain duplicates, but the Set implementation should not
* contain duplicates. If the array is empty or null, return a set of size 0
* with head referring to null. If duplicates of an item are present
* in the array, then ignore all the occurrences of this item after the first one.
*/
public ISet fromArray(Object[] elements);
/*
* Return a new set that contains only those items
* that are present in both \"this\" set and the other set.
* The order of items in the returned set does not matter.
* The other set and \"this\" set remain unchanged.
*/
public ISet intersection(ISet other);
/*
* Return a new set that contains the union of the items
* that are present in \"this\" set and the other set. Obviously
* common elements will appear only once.
* The order of items in the returned set does not matter.
* The other set and \"this\" set remain unchanged.
*/
public ISet union(ISet other);
}
OUTPUT:
After creating set s1 from array:
[5: Alex Hajar Asa Sudipto Koen ]
Printing array from s1:
[Alex, Hajar, Asa, Sudipto, Koen]
After creating set s2 from array:
[5: Gareth Alex Swapnil Chris Asa ]
Intersection of s1 and s2:
[2: Alex Asa ]
Union of s1 and s2:
[8: Gareth Alex Hajar Swapnil Asa Chris Sudipto Koen ]
