1,277
edits
Changes
no edit summary
{{code}}
/* Set.java */
import list.*;
/**
* A Set is a collection of Comparable elements stored in sorted order.
* Duplicate elements are not permitted in a Set.
**/
public class Set {
/* Fill in the data fields here. */
protected List set;
/**
* Set ADT invariants:
* 1) The Set's elements must be precisely the elements of the List.
* 2) The List must always contain Comparable elements, and those elements
* must always be sorted in ascending order.
* 3) No two elements in the List may be equals().
**/
/**
* Constructs an empty Set.
*
* Performance: runs in O(1) time.
**/
public Set() {
set = new DList();
}
/**
* cardinality() returns the number of elements in this Set.
*
* Performance: runs in O(1) time.
**/
public int cardinality() {
return set.length();
}
/**
* insert() inserts a Comparable element into this Set.
*
* Sets are maintained in sorted order. The ordering is specified by the
* compareTo() method of the java.lang.Comparable interface.
*
* Performance: runs in O(this.cardinality()) time.
**/
public void insert(Comparable c) {
ListNode curnode = null;
try {
curnode = set.front();
while (((Comparable) curnode.item()).compareTo(c) < 0) {
curnode = curnode.next();
} if (((Comparable) curnode.item()).compareTo(c) == 0) {
// the items are the same: do nothing
} else {
curnode.insertBefore(c);
}
} catch (InvalidNodeException e) { // list is empty, or we reached the end of it w/out finding a number greater than the one we're inserting
set.insertBack(c);
}
}
/**
* union() modifies this Set so that it contains all the elements it
* started with, plus all the elements of s. The Set s is NOT modified.
* Make sure that duplicate elements are not created.
*
* Performance: Must run in O(this.cardinality() + s.cardinality()) time.
*
* Your implementation should NOT copy elements of s or "this", though it
* will copy _references_ to the elements of s. Your implementation will
* create new _nodes_ for the elements of s that are added to "this", but
* you should reuse the nodes that are already part of "this".
*
* DO NOT MODIFY THE SET s.
* DO NOT ATTEMPT TO COPY ELEMENTS; just copy ''references'' to them.
**/
public void union(Set s) {
ListNode insertion = set.front();
ListNode retrieval = s.set.front();
try {
while (true) {
try {
while (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) < 0) {
insertion = insertion.next();
} if (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) > 0) {
insertion.insertBefore(retrieval.item());
}
} catch (InvalidNodeException x) {
// the item we want to insert is greater than all the items in this set, so go ahead and insert the rest of the elements of s.
try {
while (true) {
set.insertBack(retrieval.item());
retrieval = retrieval.next();
}
} catch (InvalidNodeException e) { // reached end of s, so we're done here
} // it would be cool if this try just cascaded down, but it doesn't
}
retrieval = retrieval.next(); // let's insert the next item
}
} catch (InvalidNodeException x) { // reached end of s, so we're done here
}
}
/**
* intersect() modifies this Set so that it contains the intersection of
* its own elements and the elements of s. The Set s is NOT modified.
*
* Performance: Must run in O(this.cardinality() + s.cardinality()) time.
*
* Do not construct any new ListNodes during the execution of intersect.
* Reuse the nodes of "this" that will be in the intersection.
*
* DO NOT MODIFY THE SET s.
* DO NOT CONSTRUCT ANY NEW NODES.
* DO NOT ATTEMPT TO COPY ELEMENTS.
**/
public void intersect(Set s) {
ListNode insertion = set.front();
ListNode retrieval = s.set.front();
try {
while (true) {
while (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) < 0) {
insertion = insertion.next();
insertion.prev().remove();
} if (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) > 0) {
retrieval = retrieval.next();
} else { // we have an intersection - now move both pointers one element forward
insertion = insertion.next();
retrieval = retrieval.next();
}
}
} catch (InvalidNodeException x) { // we've reached the end of some set, so we're done
}
}
/**
* toString() returns a String representation of this Set. The String must
* have the following format:
* { } for an empty Set. No spaces before "{" or after "}"; two spaces
* between them.
* { 1 2 3 } for a Set of three Integer elements. No spaces before
* "{" or after "}"; two spaces before and after each element.
* Elements are printed with their own toString method, whatever
* that may be. The elements must appear in sorted order, from
* lowest to highest according to the compareTo() method.
*
* WARNING: THE AUTOGRADER EXPECTS YOU TO PRINT SETS IN ''EXACTLY'' THIS
* FORMAT, RIGHT UP TO THE TWO SPACES BETWEEN ELEMENTS. ANY
* DEVIATIONS WILL LOSE POINTS.
**/
public String toString() {
String string = "{";
ListNode curnode = set.front();
try {
while (true) { // loop until we throw an exception
string = string + " " + curnode.item();
curnode = curnode.next();
}
} catch (InvalidNodeException e) { // we hit the end of the set or it's empty
string = string + " }";
}
return string;
}
public static void main(String[] argv) {
Set s = new Set();
s.insert(new Integer(3));
s.insert(new Integer(4));
s.insert(new Integer(3));
System.out.println("Set s = " + s);
Set s2 = new Set();
s2.insert(new Integer(4));
s2.insert(new Integer(5));
s2.insert(new Integer(5));
System.out.println("Set s2 = " + s2);
Set s3 = new Set();
s3.insert(new Integer(5));
s3.insert(new Integer(3));
s3.insert(new Integer(8));
System.out.println("Set s3 = " + s3);
s.union(s2);
System.out.println("After s.union(s2), s = " + s);
s.intersect(s3);
System.out.println("After s.intersect(s3), s = " + s);
System.out.println("s.cardinality() = " + s.cardinality());
// You may want to add more (ungraded) test code here.
Set c = new Set();
System.out.println(c);
}
}
/* Set.java */
import list.*;
/**
* A Set is a collection of Comparable elements stored in sorted order.
* Duplicate elements are not permitted in a Set.
**/
public class Set {
/* Fill in the data fields here. */
protected List set;
/**
* Set ADT invariants:
* 1) The Set's elements must be precisely the elements of the List.
* 2) The List must always contain Comparable elements, and those elements
* must always be sorted in ascending order.
* 3) No two elements in the List may be equals().
**/
/**
* Constructs an empty Set.
*
* Performance: runs in O(1) time.
**/
public Set() {
set = new DList();
}
/**
* cardinality() returns the number of elements in this Set.
*
* Performance: runs in O(1) time.
**/
public int cardinality() {
return set.length();
}
/**
* insert() inserts a Comparable element into this Set.
*
* Sets are maintained in sorted order. The ordering is specified by the
* compareTo() method of the java.lang.Comparable interface.
*
* Performance: runs in O(this.cardinality()) time.
**/
public void insert(Comparable c) {
ListNode curnode = null;
try {
curnode = set.front();
while (((Comparable) curnode.item()).compareTo(c) < 0) {
curnode = curnode.next();
} if (((Comparable) curnode.item()).compareTo(c) == 0) {
// the items are the same: do nothing
} else {
curnode.insertBefore(c);
}
} catch (InvalidNodeException e) { // list is empty, or we reached the end of it w/out finding a number greater than the one we're inserting
set.insertBack(c);
}
}
/**
* union() modifies this Set so that it contains all the elements it
* started with, plus all the elements of s. The Set s is NOT modified.
* Make sure that duplicate elements are not created.
*
* Performance: Must run in O(this.cardinality() + s.cardinality()) time.
*
* Your implementation should NOT copy elements of s or "this", though it
* will copy _references_ to the elements of s. Your implementation will
* create new _nodes_ for the elements of s that are added to "this", but
* you should reuse the nodes that are already part of "this".
*
* DO NOT MODIFY THE SET s.
* DO NOT ATTEMPT TO COPY ELEMENTS; just copy ''references'' to them.
**/
public void union(Set s) {
ListNode insertion = set.front();
ListNode retrieval = s.set.front();
try {
while (true) {
try {
while (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) < 0) {
insertion = insertion.next();
} if (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) > 0) {
insertion.insertBefore(retrieval.item());
}
} catch (InvalidNodeException x) {
// the item we want to insert is greater than all the items in this set, so go ahead and insert the rest of the elements of s.
try {
while (true) {
set.insertBack(retrieval.item());
retrieval = retrieval.next();
}
} catch (InvalidNodeException e) { // reached end of s, so we're done here
} // it would be cool if this try just cascaded down, but it doesn't
}
retrieval = retrieval.next(); // let's insert the next item
}
} catch (InvalidNodeException x) { // reached end of s, so we're done here
}
}
/**
* intersect() modifies this Set so that it contains the intersection of
* its own elements and the elements of s. The Set s is NOT modified.
*
* Performance: Must run in O(this.cardinality() + s.cardinality()) time.
*
* Do not construct any new ListNodes during the execution of intersect.
* Reuse the nodes of "this" that will be in the intersection.
*
* DO NOT MODIFY THE SET s.
* DO NOT CONSTRUCT ANY NEW NODES.
* DO NOT ATTEMPT TO COPY ELEMENTS.
**/
public void intersect(Set s) {
ListNode insertion = set.front();
ListNode retrieval = s.set.front();
try {
while (true) {
while (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) < 0) {
insertion = insertion.next();
insertion.prev().remove();
} if (((Comparable) insertion.item()).compareTo(((Comparable) retrieval.item())) > 0) {
retrieval = retrieval.next();
} else { // we have an intersection - now move both pointers one element forward
insertion = insertion.next();
retrieval = retrieval.next();
}
}
} catch (InvalidNodeException x) { // we've reached the end of some set, so we're done
}
}
/**
* toString() returns a String representation of this Set. The String must
* have the following format:
* { } for an empty Set. No spaces before "{" or after "}"; two spaces
* between them.
* { 1 2 3 } for a Set of three Integer elements. No spaces before
* "{" or after "}"; two spaces before and after each element.
* Elements are printed with their own toString method, whatever
* that may be. The elements must appear in sorted order, from
* lowest to highest according to the compareTo() method.
*
* WARNING: THE AUTOGRADER EXPECTS YOU TO PRINT SETS IN ''EXACTLY'' THIS
* FORMAT, RIGHT UP TO THE TWO SPACES BETWEEN ELEMENTS. ANY
* DEVIATIONS WILL LOSE POINTS.
**/
public String toString() {
String string = "{";
ListNode curnode = set.front();
try {
while (true) { // loop until we throw an exception
string = string + " " + curnode.item();
curnode = curnode.next();
}
} catch (InvalidNodeException e) { // we hit the end of the set or it's empty
string = string + " }";
}
return string;
}
public static void main(String[] argv) {
Set s = new Set();
s.insert(new Integer(3));
s.insert(new Integer(4));
s.insert(new Integer(3));
System.out.println("Set s = " + s);
Set s2 = new Set();
s2.insert(new Integer(4));
s2.insert(new Integer(5));
s2.insert(new Integer(5));
System.out.println("Set s2 = " + s2);
Set s3 = new Set();
s3.insert(new Integer(5));
s3.insert(new Integer(3));
s3.insert(new Integer(8));
System.out.println("Set s3 = " + s3);
s.union(s2);
System.out.println("After s.union(s2), s = " + s);
s.intersect(s3);
System.out.println("After s.intersect(s3), s = " + s);
System.out.println("s.cardinality() = " + s.cardinality());
// You may want to add more (ungraded) test code here.
Set c = new Set();
System.out.println(c);
}
}