listset.java

The package enables mergesort using immutable list.

package listset;


/**
 * 
 * Using ImmutableLists to implement the Set Interface
 * 
*/

public class ListSet implements Set{

	private ImmutableList values;

	private ImmutableList ll;

	public ListSet(){
		this.values=ImmutableList.NIL;
	}


	public int size() {
		return this.values.length();
	}

	public boolean isEmpty() {	
		return this.values.isEmpty();
	}

	public boolean isMember(Comparable e) {
		ImmutableList b=values;
		for(;b!=null&&e.compareTo(b.head())!=0;b=b.tail())
			continue;
		if(b==null){
			return false;
		}
		else{
			return true;
		}
	}


	public void include(Comparable e) {
		values = values.push(e);
	}
	public void exclude(Comparable e) {
		values = values.delete(e);
	}


	public Set union(Set that) {
		Set result=this.copy();
		for(Comparable e=that.first();e!=null;e=that.next()){
			result.include(e);
		}
		return result;
	}



	public Set intersection(Set that) {
		Set result=this.empty();
		for(Comparable e=that.first();e!=null;e=that.next())
			if(this.isMember(e))result.include(e);
		return result;
	}


	public Comparable first() {
		ll = values;
		return (Comparable) ll.head();
	} 


	public Comparable next() {
		ll = ll.tail();
		return (Comparable) ll.head();
	}


	public Set copy() {
		ListSet ls = new ListSet();
		ls.values = this.values;
		return ls;
	}


	public Set empty() {
		return new ListSet();
	}

	public String toString () {

		String result = "{";

		for (Comparable e = this.first(); e != null; e = this.next()) 

			result += " " + e;

		result += " }";

		return result;

	}
}