Computer Science/61b/Homework/hw5/Set.java

This page contains computer code. Unlike all articles on the lensowiki, which are released under the GFDL, this code is released under the GPL.

Copyright 2006, 2007 Paul Borokhov. All rights reserved.

This code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

The code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

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