immutablelist.java

The package enables mergesort using immutable list.

package listset;

/**
 * 
 * Added with purge and sort method;
 * sort method has private methods: mergesort and merge
 * 
*/

public class ImmutableList  {

	private final Object data;

	private final ImmutableList next;

	public static final ImmutableList NIL = new ImmutableList();



	private ImmutableList (Object d, ImmutableList n) { data = d; next = n; }

	private ImmutableList () {  data = null; next = null; }



	public ImmutableList nil () {

		return NIL;

	}



	public ImmutableList push (Object d) {

		return new ImmutableList(d, this); 

	}



	public Object head () { return data; }

	public ImmutableList tail () { return next; }



	public boolean isEmpty () { 

		return this == nil();

	}



	public int length () { 

		return this.isEmpty() ? 0 : 1 + this.tail().length(); 

	}



	public ImmutableList find (Object d) { 

		return this.isEmpty() || d.equals(this.head()) ? this : this.tail().find(d); 

	}



	public ImmutableList append (ImmutableList a) { 

		return this.isEmpty() ? a : this.tail().append(a).push(this.head()); 

	}



	public ImmutableList reverse () { 

		return this.isEmpty() ? this : this.tail().reverse().append(nil().push(this.head())); 

	}



	public Object nth (int n) {

		if (this.isEmpty() || n < 0) return null;

		return n == 0 ? this.head() : this.tail().nth(n - 1);

	}



	public ImmutableList delete (Object d) {

		if (this.isEmpty()) return this;

		if (d.equals(this.head())) return this.tail().delete(d);

		return this.tail().delete(d).push(this.head());

	}



	public String toString () {

		return this.isEmpty() ? "()" : "(" + this.head().toString() + 

				(this.tail().isEmpty() ? "" : " ") + this.tail().toString().substring(1);

	}



	public static ImmutableList parseIntImmutableList (String s) {

		int openBracket = s.indexOf('(');

		int closeBracket = s.indexOf(')');

		if (openBracket != 0 || closeBracket != s.length() - 1) throw new IllegalArgumentException(s);

		String[] intStrings = s.substring(openBracket + 1, closeBracket).split(" ");

		ImmutableList result = NIL;

		for (int i = intStrings.length - 1; i >= 0; i--) 

			result = result.push(Integer.parseInt(intStrings[i]));

		return result;  

	}




	public ImmutableList insert (Comparable d) {

		return this.isEmpty() || d.compareTo(this.head()) < 0 ? 

				this.push(d) : 

					this.tail().insert(d).push(this.head());

	}



	public ImmutableList powerSet () { return powerSet(nil()); }



	public ImmutableList powerSet (ImmutableList selected) {

		if (this.isEmpty()) return NIL.push(selected); // notice use of NIL as opposed to nil()

		// this is because a powerSet is always a List, not

		// the potential subclass

		return this.tail().powerSet(selected).append(this.tail().powerSet(selected.push(this.head())));

	}
	
	//purge method: delete duplicate objects

	public ImmutableList purge(){

		ImmutableList newList=NIL;
		ImmutableList a=this;

		while(!a.isEmpty()){
			ImmutableList b=newList;
			for( ;b!=null && ! a.head().equals(b.head()); b=b.tail()){
			}
			if(b==null){
				newList = newList.push(a.head());
			}
			a=a.tail();
			b=newList;
		}

		return newList;


	}

	//implement mergesort with ImmutableList

	private static ImmutableList mergesort(ImmutableList top, ImmutableList out){
		int z=top.length()-out.length();
		ImmutableList mid=top;
		
		ImmutableList a, b;
		if(z == 1){
			return NIL.push(top.head());
		}
		else if(z==0)
			return NIL;
		else {
			for(int i=0;i<z/2;i++){
				mid=mid.tail();
			}
			a = mergesort(top, mid);
			b = mergesort(mid, out);
			return merge(a, b);
		}
	}


	public static ImmutableList merge(ImmutableList top1, ImmutableList top2){

		ImmutableList start=top1;
		ImmutableList out1=top2;
		ImmutableList temp=NIL;

		ImmutableList topRemaining = NIL;
		
		while(start!=NIL&&out1!=NIL){

			if(((Comparable)start.head()).compareTo(out1.head())<0){

				temp = temp.append(NIL.push(start.head()));
				start=start.tail();

			}
			else{
				temp = temp.append(NIL.push(out1.head()));
				out1=out1.tail();
			}
		}
		if(start==NIL){		
			topRemaining=out1;
		}
		else{ 
			topRemaining=start;
		}
		
		return temp.append(topRemaining);	
	}

	public ImmutableList sort(){
		return mergesort(this, NIL);
	}

}