I am working on a linked list set project with an iterator. This is the first ti
ID: 3754755 • Letter: I
Question
I am working on a linked list set project with an iterator.
This is the first time I have to deal with stuff like generic and iterator. It is really confusing to me. Wish someone could help.
I have two java docs (LinkedNodeIterator.java and LinkedSet.java) that I have to work on and another two supportive java docs (LinkedNode.java and set.java).
The code also contains a JUnit test java doc which is PublicLinkedSetTest.java
I would rate your answers if they are helpful. Thanks.
Here are the java docs:
LinkedNodeIterator.java:
package sets;
import java.util.Iterator;
import java.util.NoSuchElementException;
class LinkedNodeIterator implements Iterator {
// TODO (1) define data variables
private LinkedNode Node;
// Constructors
public LinkedNodeIterator(LinkedNode head) {
// TODO (2) choose appropriate parameters and do the initialization
this.Node = head;
}
@Override
public boolean hasNext() {
// TODO (3)
}
@Override
public E next() {
// TODO (4)
}
@Override
public void remove() {
// Nothing to change for this method
throw new UnsupportedOperationException();
}
}
LinkedSet.java:
package sets;
import java.util.Iterator;
/**
* A LinkedList-based implementation of Set
*/
/********************************************************
* NOTE: Before you start, check the Set interface in
* Set.java for detailed description of each method.
*******************************************************/
/********************************************************
* NOTE: for this project you must use linked lists
* implemented by yourself. You are NOT ALLOWED to use
* Java arrays of any type, or any Collection-based class
* such as ArrayList, Vector etc. You will receive a 0
* if you use any of them.
*******************************************************/
/********************************************************
* NOTE: you are allowed to add new methods if necessary,
* but do NOT add new files (as they will be ignored).
*******************************************************/
public class LinkedSet implements Set {
private LinkedNode head = null;
// Constructors
public LinkedSet() {
}
public LinkedSet(E e) {
this.head = new LinkedNode(e, null);
}
private LinkedSet(LinkedNode head) {
this.head = head;
}
@Override
public int size() {
// TODO (1)
return 0;
}
@Override
public boolean isEmpty() {
// TODO (2)
return false;
}
@Override
public Iterator iterator() {
return new LinkedNodeIterator(this.head);
}
@Override
public boolean contains(Object o) {
// TODO (3)
return false;
}
@Override
public boolean isSubset(Set that) {
// TODO (4)
return false;
}
@Override
public boolean isSuperset(Set that) {
// TODO (5)
return false;
}
@Override
public Set adjoin(E e) {
// TODO (6)
return null;
}
@Override
public Set union(Set that) {
// TODO (7)
return null;
}
@Override
public Set intersect(Set that) {
// TODO (8)
return null;
}
@Override
public Set subtract(Set that) {
// TODO (9)
return null;
}
@Override
public Set remove(E e) {
// TODO (10)
return null;
}
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
if (! (o instanceof Set)) {
return false;
}
Set that = (Set)o;
return this.isSubset(that) && that.isSubset(this);
}
@Override
public int hashCode() {
int result = 0;
for (E e : this) {
result += e.hashCode();
}
return result;
}
}
LinkedNode.java:
package sets;
public class LinkedNode {
E data;
LinkedNode next;
public LinkedNode(E data, LinkedNode next) {
this.data = data;
this.next = next;
}
public E getData() {
return data;
}
public LinkedNode getNext() {
return next;
}
}
Set.java(Basically contains describtions about how to write every method in LinkedSet.java):
package sets;
import java.util.Iterator;
/**
* A collection that contains no duplicate elements. More formally,
* a set contains no pair of elements e1 and
* e2 such that e1.equals(e2) is true, and
* and at most one null element (for the simple reason that if it had
* contained two null elements, they would have been duplicates).
*/
public interface Set extends Iterable {
/**
* Returns the number of elements in this set (its cardinality).
*
* @return the number of elements in this set (its cardinality).
*/
int size();
/**
* Returns true if this set contains no elements.
*
* @return true if this set contains no elements.
*/
boolean isEmpty();
/**
* Returns an iterator over the elements in this set.
*
* @return an iterator over the elements in this set
*/
Iterator iterator();
/**
* Returns true if this set contains the specified element. More
* formally, returns true if and only if this set contains an
* element e such that (o==null ? e==null :
* o.equals(e)).
*
* @param o the element whose presence in this set is to be tested
* @return true if this set contains the specified element
*/
boolean contains(Object o);
/**
* Returns true if this set is a subset (or equal to) the given
* set. More formally, returns true if and only if every member of
* 'this' set is also contained in that set.
*
* @param that the set to check whether this is a subset of
* @return true if every member of this set is also a
* member of that
*/
boolean isSubset(Set that);
/**
* Returns true if this set is a superset (or equal to) the given
* set. This is equivalent to asking whether that set is a subset
* of this set.
*
* @param that the set to check whether this is a superset of
* @return true if every member of that is also a member of
* this set
*/
boolean isSuperset(Set that);
/**
* Adjoin a set with a new element. If the specified element is
* already in the set then returns the original Set. Otherwise,
* returns a new Set containing all of the elements of this set and
* also the specified new element.
*
* @param e the element to be added
* @return a Set containing all of the elements of this set that
* also contains e
*/
Set adjoin(E e);
/**
* Returns a new Set that is the union of this
* Set and that Set. This is intended to be the
* mathematical operation of union on sets.
*
* @param other the other Set to take the union with
* @return a Set containing the union of the two
* input Sets
*/
Set union(Set other);
/**
* Returns a new Set that is the intersection of
* this Set and that Set. This is
* intended to be the mathematical operation of intersection on
* sets.
*
* @param other the other Set to take the
* intersection with
* @return a Set containing the intersection of
* the two input Sets
*/
Set intersect(Set other);
/**
* Returns a new Set that is the difference of
* this Set and that Set, i.e.,
* this - that. This is intended to be the mathematical
* operation of difference on sets. Formally, the returned set
* contains every element e of this that
* is NOT an element of that.
*
* @param that the Set to subtract from this one
* @return a Set containing the difference of
* the two input Sets
*/
Set subtract(Set other);
/**
* Remove an element from a set. If this set does not contain the
* specified element then return the original set. Otherwise,
* return a new Set that is the same as this
* except that it does not contain the specified element.
*
* @param e the element to be removed
* @return a set similar to this but without
* e
*/
Set remove(E e);
/**
* Compares the specified object with this set for equality. Returns
* true if the specified object is also a set, the two sets have the
* same size, and every member of the specified set is contained in
* this set (or equivalently, every member of this set is contained
* in the specified set).
*
* @param o object to be compared for equality with this set
* @return true if the specified object is equal to this set
* @see java.lang.Object#hashCode()
*/
boolean equals(Object o);
/**
* Returns the hash code value for this set. The hash code of a set
* is defined to be the sum of the hash codes of the elements in the
* set, where the hash code of a null element is defined to be
* zero. This ensures that s1.equals(s2) implies that
* s1.hashCode() == s2.hashCode() for any two sets
* s1 and s2, as
* required by the general contract of Object.hashCode().
*
* @return the hash code value for this set
* @see java.lang.Object#equals(Object)
* @see equals(Object)
* @see java.lang.Object#hashCode()
*/
int hashCode();
}
PublicLinkedSetTest.java:
package sets;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
@SuppressWarnings("unused")
public class PublicLinkedSetTest {
Set<String> set0;
Set<String> set1;
Set<String> set2;
Set<String> set3;
Set<String> set4;
@Before
public void before() {
set0 = new LinkedSet<String>();
set1 = new LinkedSet<String>();
for (String e : new String[]{"c", "a", "d", "b", "e"}) {
set1 = set1.adjoin(e);
}
set2 = new LinkedSet<String>();
for (String e : new String[]{"b", "d", "a", "e", "c"}) {
set2 = set2.adjoin(e);
}
set3 = new LinkedSet<String>();
for (String e : new String[]{"a", "d", "b"}) {
set3 = set3.adjoin(e);
}
set4 = new LinkedSet<String>();
for (String e : new String[]{"x", "y", "z", "a", "b", "d"}) {
set4 = set4.adjoin(e);
}
}
@Test
public void testEmptySet() {
assertEquals(0, set0.size());
assertTrue(set0.isEmpty());
assertFalse(set0.contains("a"));
assertTrue(set0.isSubset(set0));
assertTrue(set0.isSubset(set1));
assertTrue(set0.isSubset(set2));
assertTrue(set0.isSubset(set3));
assertTrue(set0.isSuperset(set0));
assertFalse(set0.isSuperset(set1));
assertFalse(set0.isSuperset(set2));
assertFalse(set0.isSuperset(set3));
}
@Test
public void testIterator0() {
int count = 0;
for (String e : set0) {
count += 1;
}
assertEquals(0, count);
}
@Test
public void testIterator1() {
int count = 0;
for (String e : set1) {
count += 1;
}
assertEquals(5, count);
}
@Test
public void testIterator2() {
int count = 0;
for (String e : set2) {
count += 1;
}
assertEquals(5, count);
}
@Test
public void testIterator3() {
int count = 0;
for (String e : set3) {
count += 1;
}
assertEquals(3, count);
}
@Test
public void testIterator4() {
int count = 0;
for (String e : set4) {
count += 1;
}
assertEquals(6, count);
}
@Test
public void testUnorderedEquality() {
assertTrue(set1.equals(set2));
assertFalse(set1.equals(set3));
assertFalse(set2.equals(set3));
assertTrue(set2.equals(set1));
assertFalse(set3.equals(set1));
assertFalse(set3.equals(set2));
}
@Test
public void testContains() {
assertFalse(set0.contains("a"));
assertTrue(set1.contains("a"));
assertTrue(set2.contains("a"));
assertTrue(set3.contains("a"));
assertTrue(set1.contains("e"));
assertTrue(set2.contains("e"));
assertFalse(set3.contains("e"));
}
@Test
public void testIsSubset() {
assertTrue(set1.isSubset(set1));
assertTrue(set1.isSubset(set2));
assertFalse(set1.isSubset(set3));
assertFalse(set1.isSubset(set4));
assertTrue(set2.isSubset(set1));
assertTrue(set2.isSubset(set2));
assertFalse(set2.isSubset(set3));
assertFalse(set2.isSubset(set4));
assertTrue(set3.isSubset(set1));
assertTrue(set3.isSubset(set2));
assertTrue(set3.isSubset(set3));
assertTrue(set3.isSubset(set4));
}
@Test
public void testIsSuperset() {
assertTrue(set1.isSuperset(set1));
assertTrue(set2.isSuperset(set1));
assertFalse(set3.isSuperset(set1));
assertFalse(set4.isSuperset(set1));
assertTrue(set1.isSuperset(set2));
assertTrue(set2.isSuperset(set2));
assertFalse(set3.isSuperset(set2));
assertFalse(set4.isSuperset(set2));
assertTrue(set1.isSuperset(set3));
assertTrue(set2.isSuperset(set3));
assertTrue(set3.isSuperset(set3));
assertTrue(set4.isSuperset(set3));
}
@Test
public void testUnionWithSelf() {
assertEquals(set1, set1.union(set1));
}
@Test
public void testUnionWithEqual() {
assertEquals(set1, set1.union(set2));
}
@Test
public void testUnionWithSubset() {
assertEquals(set1, set1.union(set3));
}
@Test
public void testUnionWithOther() {
assertEquals(8, set1.union(set4).size());
}
@Test
public void testIntersectWithSelf() {
assertEquals(set1, set1.intersect(set1));
}
@Test
public void testIntersectWithEqual() {
assertEquals(set1, set1.intersect(set2));
}
@Test
public void testIntersectWithSubset() {
assertEquals(set3, set1.intersect(set3));
}
@Test
public void testIntersectWithOther() {
assertEquals(set3, set1.intersect(set4));
}
@Test
public void testSubtractSelf() {
assertEquals(set0, set1.subtract(set1));
}
@Test
public void testSubtractEqual() {
assertEquals(set0, set1.subtract(set2));
}
@Test
public void testSubtractWithSubset() {
assertEquals(set0.adjoin("c").adjoin("e"), set1.subtract(set3));
}
@Test
public void testSubtractWithOther() {
assertEquals(set0.adjoin("z").adjoin("y").adjoin("x"), set4.subtract(set1));
}
@Test
public void testRemove() {
assertEquals(set3.adjoin("e"), set1.remove("c"));
}
}
Explanation / Answer
Answer: See the code below:
1. Updated LinkedNode class: LinkedNode.java
-------------------------------------------
package sets;
public class LinkedNode<E> {
E data;
LinkedNode next;
public LinkedNode(E data, LinkedNode next) {
this.data = data;
this.next = next;
}
public E getData() {
return data;
}
public LinkedNode getNext() {
return next;
}
}
------------------------------------------
2. Updated LinkedNodeIterator class: LinkedNodeIterator.java
---------------------------------------
package sets;
import java.util.Iterator;
class LinkedNodeIterator<E> implements Iterator {
// TODO (1) define data variables
private LinkedNode Node;
// Constructors
public LinkedNodeIterator(LinkedNode head) {
// TODO (2) choose appropriate parameters and do the initialization
this.Node = head;
}
@Override
public boolean hasNext() {
if (this.Node.getNext()== null) {
} else {
return true;
}
return false;
}
@Override
public E next() {
return (E) this.Node.getNext().getData();
}
@Override
public void remove() {
// Nothing to change for this method
throw new UnsupportedOperationException();
}
}
-----------------------------------------
3. Updated LinkedSet class: LinkedSet.java
---------------------------------------
package sets;
import java.util.Iterator;
/**
*
* A LinkedList-based implementation of Set
*
*/
/**
* ****************************************************** *
* NOTE: Before you start, check the Set interface in *
* Set.java for detailed description of each method. *
******************************************************
*/
/**
* ****************************************************** *
* NOTE: for this project you must use linked lists *
* implemented by yourself. You are NOT ALLOWED to use *
* Java arrays of any type, or any Collection-based class *
* such as ArrayList, Vector etc. You will receive a 0 *
* if you use any of them. *
******************************************************
*/
/**
* ******************************************************
*
* NOTE: you are allowed to add new methods if necessary, *
* but do NOT add new files (as they will be ignored). *
******************************************************
*/
public class LinkedSet<E> implements Set {
private LinkedNode head = null;
private int numElements;
// Constructors
public LinkedSet() {
this.numElements = 0;
}
public LinkedSet(E e) {
this.head = new LinkedNode(e, null);
this.numElements = 0;
}
private LinkedSet(LinkedNode head) {
this.head = head;
this.numElements = 0;
}
@Override
public int size() {
return numElements;
}
@Override
public boolean isEmpty() {
return (this.head == null);
}
@Override
public Iterator iterator() {
return new LinkedNodeIterator(this.head);
}
@Override
public boolean contains(Object o) {
Iterator nodeIterator = this.iterator();
while(nodeIterator.hasNext())
{
Object e = nodeIterator.next();
return (o==null ? e==null : o.equals(e));
}
return false;
}
@Override
public boolean isSubset(Set that) {
boolean flag = false;
Iterator iterator = this.iterator();
while(iterator.hasNext())
{
Object e = iterator.next();
flag = that.contains(e);
}
return flag;
}
@Override
public boolean isSuperset(Set that) {
boolean flag = false;
Iterator iterator = that.iterator();
while(iterator.hasNext())
{
Object e = iterator.next();
flag = this.contains(e);
}
return flag;
}
@Override
public Set union(Set that) {
Set set = new LinkedSet(this.head);
Iterator iterator = this.iterator();
if (iterator.hasNext())
{
E e = (E) iterator.next();
set.adjoin(e);
}
Iterator iterator1 = that.iterator();
if (iterator1.hasNext())
{
E e = (E) iterator1.next();
set.adjoin(e);
}
return set;
}
@Override
public Set intersect(Set that) {
Set set = new LinkedSet();
Iterator iterator = this.iterator();
while(iterator.hasNext())
{
E e = (E) iterator.next();
if(that.contains(e))
{
set.adjoin(e);
}
}
return set;
}
@Override
public Set subtract(Set that) {
Set set = new LinkedSet();
Iterator iterator = this.iterator();
while(iterator.hasNext())
{
E e = (E) iterator.next();
if(!that.contains(e))
{
set.adjoin(e);
}
}
return set;
}
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
if (!(o instanceof Set)) {
return false;
}
Set that = (Set) o;
return this.isSubset(that) && that.isSubset(this);
}
@Override
public int hashCode() {
int result = 0;
for (Object e : this) {
result += e.hashCode();
}
return result;
}
@Override
public Set adjoin(Object e) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
@Override
public Set remove(Object e) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
}
--------------------------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.