gistfile1.java

/**
	 * isSubset(a,b) determines whether Set a is a subset of Set b
	 * 
	 * @param a
	 *            - the first set
	 * @param b
	 *            - the second set
	 * @return - true or false
	 */
	public static boolean isSubset(Set a, Set b) {

		/*
		 * a smart optimisation would be to check if b >= a first. If not you
		 * can return false immediately
		 */
		
		if (a.isEmpty()) {
			return true;
		}
		if (b.isEmpty()) { // we already know that a is not empty
			return false;
		}

		if (a.getHead() == b.getHead()) {
			return isSubset((Set) a.getTail(), (Set) b.getTail());
		} else {
			// this is convoluted and ugly
			Set aHead = new Set();
			aHead = Set.cons(a.getHead(), aHead);
			return isSubset((Set) a.getTail(), b) && isSubset(aHead, (Set) b.getTail());
		}
	}