- The Java utility class
package edu.lmu.cs.rtoal.util;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* A collection of weird list utilities.
*/
public class ListUtil {
/**
* A representation of a function mapping two objects to a
* boolean.
*/
public static interface BinaryPredicate<S, T> {
boolean evaluate(S x, T y);
}
/**
* A representation of a function mapping two objects to an
* object.
*/
public static interface BinaryFunction<S, T, U> {
U evaluate(S x, T y);
}
// Utility class
private ListUtil() {}
/**
* partialFilter(p, x, a) returns the number of items y in a such
* that p(x, y) is true.
*/
public static <S, T> int partialFilter(BinaryPredicate<S, T> p, S x,
List<T> a) {
int result = 0;
for (T y : a) {
if (p.evaluate(x, y)) {
result++;
}
}
return result;
}
/**
* Returns a list of all items in the input list, except that where
* any of the items are themselves lists, these are flattened. For
* example flatten ([3, 1, 2], [3, [1, 1]], [9]) would return
* [3, 1, 2, 3, 1, 1, 9].
*/
public static List<?> flatten(final List<?> a) {
return flatten(a, new LinkedList<List<?>>(){{add(a);}});
}
// A helper method for flatten, to deal with self-referential
// lists. Note that use of a linked list, rather than a hash set,
// to manage the "ancestors" of a list element. The problem with
// using a hash set is that the hashCode() method on lists will
// go into an infinite loop, so just trying to place a self-referential
// list in a hash set causes a StackOverflowError. Also notice that
// the containment check in the ancestor list is manual, because
// List.contains() internally calls equals(), and that would
// cause a stack overflow, too.
private static List<?> flatten(List<?> a, LinkedList<List<?>> seen) {
List<Object> result = new ArrayList<Object>();
for (Object x : a) {
if (x instanceof List) {
for (Object y : seen) {
if (x == y) {
throw new IllegalArgumentException("Can't flatten" +
"recursive array");
}
}
seen.addFirst((List<?>)x);
result.addAll(flatten((List<?>)x, seen));
seen.removeFirst();
} else {
result.add(x);
}
}
return result;
}
/**
* Returns a map telling how many times each item occurs in a list.
* Example: countItems("dog", "owl", "dog") returns ("dog" => 2,
* "owl" => 1). How well this works depends on how well the
* equals() and hashCode() methods are defined for the classes
* to which the list members belong.
*/
public static <T> Map<T, Integer> histogram(List<T> a) {
Map<T, Integer> result = new HashMap<T, Integer>();
for (T item : a) {
int count = 1;
if (result.containsKey(item)) {
count = result.get(item) + 1;
}
result.put(item, count);
}
return result;
}
/**
* Returns the list that is the same as the list you would get
* if you repeated the following operation k times: remove the last
* element of a and put it on the front of a. Here rotating a
* list a negative number of times is the same as not rotating
* it at all.
*/
public static <T> List<T> rotate(int k, List<T> a) {
if (a.isEmpty() || k <= 0) {
return new ArrayList<T>(a);
}
k = a.size() - (k % a.size());
ArrayList<T> result = new ArrayList<T>();
result.addAll(a.subList(k, a.size()));
result.addAll(a.subList(0, k));
return result;
}
/**
* Returns the right reduction of binary function f over the
* list a, that is, rightReduce(f, [x0, x1, ..., xn]) returns
* f(x0, f(x1, ... f(xn-1, xn)))
*/
public static <T> T rightReduce(BinaryFunction<T, T, T> f, List<T> a) {
if (a.isEmpty()) {
throw new IllegalArgumentException("Cannot reduce empty list");
}
T result = a.get(a.size() - 1);
for (int i = a.size() - 2; i >= 0; i--) {
result = f.evaluate(a.get(i), result);
}
return result;
}
/**
* Returns a list containing the squares of the input list
* sorted in descending order. Example: If a = [9, -3, 5] then
* descendingIntegerSquares(x) returns [81, 25, 9].
*/
public static List<Integer> descendingIntegerSquares(List<Integer> a) {
List<Integer> result = new ArrayList<Integer>(a.size());
for (Integer x : a) {
result.add(x * x);
}
Collections.sort(result, Collections.reverseOrder());
return result;
}
}
- The Java unit test
package edu.lmu.cs.rtoal.util;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import org.junit.Test;
import edu.lmu.cs.rtoal.util.ListUtil.BinaryFunction;
import edu.lmu.cs.rtoal.util.ListUtil.BinaryPredicate;
/**
* A test for the crazy bunch of list utilities assigned for
* homework in a Programming Languages class.
*/
public class ListUtilTest {
private BinaryPredicate<Integer, Integer> lessThan =
new BinaryPredicate<Integer, Integer>() {
public boolean evaluate(Integer x, Integer y) {
return y < x;
}
};
private BinaryFunction<Integer, Integer, Integer> twoXplusY =
new BinaryFunction<Integer, Integer, Integer>() {
public Integer evaluate(Integer x, Integer y) {
return 2 * x + y;
}
};
@Test
public void testPartialFilter() {
List<Integer> a = Collections.emptyList();
assertEquals(ListUtil.partialFilter(lessThan, 6, a), 0);
a = Arrays.asList(4, 5, 6, 2);
assertEquals(ListUtil.partialFilter(lessThan, 6, a), 3);
assertEquals(ListUtil.partialFilter(lessThan, 10, a), 4);
assertEquals(ListUtil.partialFilter(lessThan, 1, a), 0);
assertEquals(ListUtil.partialFilter(lessThan, 5, a), 2);
}
@Test
public void testFlatten() {
List<?> empty = Collections.emptyList();
assertEquals(ListUtil.flatten(empty), empty);
List<String> dog = Collections.singletonList("dog");
assertEquals(ListUtil.flatten(dog), dog);
// [[1.0], 2, [3, 4, ['z', 6, [7]], "dog"]]
assertEquals(ListUtil.flatten(Arrays.asList(
Collections.singletonList(1.0), 2,
Arrays.asList(
3, 4,
Arrays.asList('z', 6, Collections.singletonList(7)),
"dog"))),
Arrays.asList(1.0, 2, 3, 4, 'z', 6, 7, "dog"));
}
@Test(expected=IllegalArgumentException.class)
public void testFlattenWithDirectlyRecursiveArray() {
List<Object> bad = new ArrayList<Object>();
bad.add("dog");
bad.add(bad);
ListUtil.flatten(bad);
}
@Test(expected=IllegalArgumentException.class)
public void testFlattenWithIndirectlyRecursiveArray() {
List<Object> a = new ArrayList<Object>();
List<Object> b = new ArrayList<Object>();
List<Object> c = new ArrayList<Object>();
a.add(b);
b.add(c);
c.add(a);
ListUtil.flatten(a);
}
@Test
public void testHistogram() {
assertEquals(ListUtil.histogram(Collections.emptyList()),
new HashMap<Object, Integer>());
assertEquals(
ListUtil.histogram(Arrays.asList(
"dog", 1500, "pig", 2.54, 1500, "pig", "dog", "dog",
"pig", "dog", "pig", 2.54, 1500, "pig", "dog", "dog",
"pig", "rat")),
new HashMap<Object, Integer>() {{
put("dog", 6);
put(1500, 3);
put("pig", 6);
put(2.54, 2);
put("rat", 1);}});
}
@Test
public void testRotate() {
List<String> x = new ArrayList<String>();
List<String> result = ListUtil.rotate(0, x);
assertEquals(x, Collections.emptyList());
assertEquals(result, Collections.emptyList());
x = Arrays.asList("a", "b", "c", "d", "e", "f", "g");
assertEquals(x, ListUtil.rotate(-6, x));
assertEquals(x, ListUtil.rotate(0, x));
assertEquals(x, ListUtil.rotate(7, x));
result = ListUtil.rotate(3, x);
List<String> y = Arrays.asList("e", "f", "g", "a", "b", "c", "d");
assertEquals(result, y);
result = ListUtil.rotate(700024, x);
assertEquals(result, y);
}
@Test
public void testRightReduce() {
List<Integer> x = Arrays.asList(4, 5, 6, 2);
assertEquals(ListUtil.rightReduce(twoXplusY, x), 32);
x = Collections.singletonList(4);
assertEquals(ListUtil.rightReduce(twoXplusY, x), 4);
}
@Test(expected=IllegalArgumentException.class)
public void testEmptyReduce() {
ListUtil.rightReduce(twoXplusY, new ArrayList<Integer>());
}
@Test
public void testDescendingIntegerSquares() {
List<Integer> x = new ArrayList<Integer>();
assertTrue(ListUtil.descendingIntegerSquares(x).isEmpty());
assertEquals(ListUtil.descendingIntegerSquares(
Arrays.asList(4, -5, 6, 2)),
Arrays.asList(36, 25, 16, 4));
}
}
- The SML structure
(*
* A structure with a weird bunch of operations on lists.
*)
structure ListUtil = struct
(*
* partial_filter p x a returns the number of items y in a
* such that p x y.
*)
fun partial_filter p x [] = 0
| partial_filter p x (y::t) =
(if p x y then 1 else 0) + partial_filter p x t;
(*
* flatten a, where a is a list of lists, appends each of the
* lists together.
*)
fun flatten [] = []
| flatten (h::t) = h @ flatten t;
(*
* histogram a returns an association list telling how many times
* each item occurs in list a. Example: histogram [4, 3, 1, 3, 3, 1]
* ==> [(4,1),(3,3),(1,2)].
*)
local
fun add_item x [] = [(x,1)]
| add_item x ((y,z)::t) =
if x = y then (x,z+1)::t else (y,z)::add_item x t
fun count [] result = result
| count (h::t) result = count t (add_item h result)
in
fun histogram a = count a []
end;
(*
* rotate k a returns the list equivalent to rotating the list
* a to the right k times. Values of k less than 0 are treated
* as 0.
*)
fun rotate n a =
if n <= 0 orelse length a = 0 then [] else
let
val k = length a - (n mod length a)
in
List.drop (a, k) @ List.take (a, k)
end;
(*
* right_reduce p [x1, x2, ..., xn] returns p(x1, p(x2, ... p(xn-1, xn))).
*)
fun right_reduce p [] = raise Empty
| right_reduce p [x] = x
| right_reduce p (x::y::t) = p(x, right_reduce p (y::t));
(*
* descending_integer_squares a returns the list containing the squares
* of each item in a, sorted from highest to lowest. Example:
* squares [3, 10, -9] ===> [9, 100, 81].
*)
local
fun rev_compare (x, y) =
if x < y then GREATER else if x > y then LESS else EQUAL
fun square x = x * x
in
val descending_integer_squares = (ListSort.sort rev_compare) o (map square)
end
end
- The SML unit test
(*
* Test script for the ListUtil structure.
*)
(* A little unit testing framework *)
val passes = ref 0 and failures = ref 0;
fun assert condition =
if condition then (print "."; passes := !passes + 1)
else failures := (print "F"; !failures + 1)
open ListUtil;
(* A handful of tests *)
fun eq x y = y = x;
fun le x y = y <= x;
fun ge x y = y >= x;
assert (descending_integer_squares [] = []);
assert (descending_integer_squares [20] = [400]);
assert (descending_integer_squares [4, 3, 2, 1, ~10] = [100, 16, 9, 4, 1]);
assert (partial_filter ge 7 [] = 0);
assert (partial_filter ge 7 [5, 8, 11, 20, 9, 1, 6, 10] = 5);
assert (partial_filter le 30 [5, 8, 11, 20, 9, 1, 6, 10] = 8);
assert (partial_filter le 19 [5, 8, 11, 20, 9, 1, 6, 10] = 7);
assert (partial_filter eq 5 [5, 8, 11, 5, 9, 1, 6, 10] = 2);
assert (histogram [] = []);
assert (histogram ["abc"] = [("abc", 1)]);
assert (histogram [4, 50, 6, 12, 4, 6, 12, 12, 12, 4]
= [(4,3),(50,1),(6,2),(12,4)]);
assert (rotate 0 [] = []);
assert (rotate 7 [] = []);
assert (rotate ~7 [] = []);
assert (rotate 1 ["dog"] = ["dog"]);
assert (rotate 7 [1, 2, 3, 4, 5, 6, 7, 8, 9] = [3, 4, 5, 6, 7, 8, 9, 1, 2]);
assert (rotate 900007 [1, 2, 3, 4, 5, 6, 7, 8, 9] = [3, 4, 5, 6, 7, 8, 9, 1, 2]);
assert (flatten [] = []);
assert (flatten [[100]] = [100]);
assert (flatten [[1], [2, 3], [], [4, 5, 6, 7]] = [1, 2, 3, 4, 5, 6, 7]);
assert (right_reduce op+ [4, 5, 6, 2] = 17);
assert (right_reduce op- [4, 5, 6, 2] = 3);
assert (right_reduce op+ [4] = 4);
assert (right_reduce op* [7, 2, 3, 10, 1] = 420);
assert (right_reduce op* [0] = 0);
let fun g(x, y) = 2 * x - y in
assert (right_reduce g [8, 2, 3, 9] = 9)
end;
(right_reduce op+ []; assert false) handle Empty => assert true;
(* Final report *)
print (makestring(!passes)
^ " passes, "
^ makestring(!failures)
^ " failures\n");