test/loops/ListBash.java

/*
 * Written by Josh Bloch and Doug Lea with assistance from members of
 * JCP JSR-166 Expert Group and released to the public domain, as
 * explained at http://creativecommons.org/licenses/publicdomain
 */

import java.util.*;

public class ListBash {
    static boolean canRemove = true;
    static final Random rnd = new Random();
    static int numItr;
    static int listSize;
    static boolean synch;
    static Class cl;

    public static void main(String[] args) {
        numItr = Integer.parseInt(args[1]);
        listSize = Integer.parseInt(args[2]);
        cl = null;

        try {
            cl = Class.forName(args[0]);
        } catch(ClassNotFoundException e) {
            fail("Class " + args[0] + " not found.");
        }

        synch = (args.length>3);
        oneRun();
        oneRun();
        oneRun();
        oneRun();
        oneRun();
    }

    static void oneRun() {
        long startTime = System.nanoTime();
        for (int i=0; i<numItr; i++) {
            elementLoop();
        }
        List<Integer> s = newList(cl, synch);
        for (int i=0; i<listSize; i++)
            s.add(new Integer(i));
        if (s.size() != listSize)
            fail("Size of [0..n-1] != n");
        evenOdd(s);
        sublists(s);
        arrays();
        long elapsed = System.nanoTime() - startTime;
        System.out.println("Time: " + (elapsed/1000000000.0) + "s");
    }


    static void elementLoop() {
        List<Integer> s1 = newList(cl, synch);
        AddRandoms(s1, listSize);

        List<Integer> s2 = newList(cl, synch);
        AddRandoms(s2, listSize);

        sets(s1, s2);

        s1.clear();
        if (s1.size() != 0)
            fail("Clear didn't reduce size to zero.");

        s1.addAll(0, s2);
        if (!(s1.equals(s2) && s2.equals(s1)))
            fail("addAll(int, Collection) doesn't work.");
        // Reverse List
        for (int j=0, n=s1.size(); j<n; j++)
            s1.set(j, s1.set(n-j-1, s1.get(j)));
        // Reverse it again
        for (int j=0, n=s1.size(); j<n; j++)
            s1.set(j, s1.set(n-j-1, s1.get(j)));
        if (!(s1.equals(s2) && s2.equals(s1)))
            fail("set(int, Object) doesn't work");
        sums(s1, s2);
    }

    static void sums(List<Integer> s1, List<Integer> s2) {
        int sum = 0;
        for (int k = 0; k < listSize; ++k) {
            sum += (s1.get(k)).intValue();
            sum -= (s2.get(k)).intValue();
        }
        for (int k = 0; k < listSize; ++k) {
            sum += (s1.get(k)).intValue();
            s1.set(k, sum);
            sum -= (s2.get(k)).intValue();
            s1.set(k, -sum);
        }
        for (int k = 0; k < listSize; ++k) {
            sum += (s1.get(k)).intValue();
            sum -= (s2.get(k)).intValue();
        }
        if (sum == 0) System.out.print(" ");
    }    

    static void sets(List<Integer> s1, List<Integer> s2) {
        List<Integer> intersection = clone(s1, cl,synch);intersection.retainAll(s2);
        List<Integer> diff1 = clone(s1, cl, synch); diff1.removeAll(s2);
        List<Integer> diff2 = clone(s2, cl, synch); diff2.removeAll(s1);
        List<Integer> union = clone(s1, cl, synch); union.addAll(s2);

        if (diff1.removeAll(diff2))
            fail("List algebra identity 2 failed");
        if (diff1.removeAll(intersection))
            fail("List algebra identity 3 failed");
        if (diff2.removeAll(diff1))
            fail("List algebra identity 4 failed");
        if (diff2.removeAll(intersection))
            fail("List algebra identity 5 failed");
        if (intersection.removeAll(diff1))
            fail("List algebra identity 6 failed");
        if (intersection.removeAll(diff1))
            fail("List algebra identity 7 failed");

        intersection.addAll(diff1); intersection.addAll(diff2);
        if (!(intersection.containsAll(union) &&
              union.containsAll(intersection)))
            fail("List algebra identity 1 failed");

        Iterator e = union.iterator();
        while (e.hasNext())
            intersection.remove(e.next());
        if (!intersection.isEmpty())
            fail("Copy nonempty after deleting all elements.");

        e = union.iterator();
        while (e.hasNext()) {
            Object o = e.next();
            if (!union.contains(o))
                fail("List doesn't contain one of its elements.");
            if (canRemove) {
                try { e.remove();
                } catch (UnsupportedOperationException uoe) {
                    canRemove = false;
                }
            }
        }
        if (canRemove && !union.isEmpty())
            fail("List nonempty after deleting all elements.");
    }

    static void evenOdd(List<Integer> s) {
        List<Integer> even = clone(s, cl, synch);
        List<Integer> odd = clone(s, cl, synch);
        List<Integer> all;
        Iterator<Integer> it;

        if (!canRemove)
            all = clone(s, cl, synch);
        else {
            it = even.iterator();
            while(it.hasNext())
                if((it.next()).intValue() % 2 == 1)
                    it.remove();
            it = even.iterator();
            while(it.hasNext())
                if((it.next()).intValue() % 2 == 1)
                    fail("Failed to remove all odd nubmers.");
            
            for (int i=0; i<(listSize/2); i++)
                odd.remove(i);
            for (int i=0; i<(listSize/2); i++) {
                int ii = (odd.get(i)).intValue();
                if(ii % 2 != 1)
                    fail("Failed to remove all even nubmers. " + ii);
            }

            all = clone(odd, cl, synch);
            for (int i=0; i<(listSize/2); i++)
                all.add(2*i, even.get(i));
            if (!all.equals(s))
                fail("Failed to reconstruct ints from odds and evens.");
            
            all = clone(odd,  cl, synch);
            ListIterator<Integer> itAll = all.listIterator(all.size());
            ListIterator<Integer> itEven = even.listIterator(even.size());
            while (itEven.hasPrevious()) {
                itAll.previous();
                itAll.add(itEven.previous());
                itAll.previous(); // ???
            }
            itAll = all.listIterator();
            while (itAll.hasNext()) {
                Integer i = itAll.next();
                itAll.set(new Integer(i.intValue()));
            }
            itAll = all.listIterator();
            it = s.iterator();
            while(it.hasNext())
                if(it.next()==itAll.next())
                    fail("Iterator.set failed to change value.");
        }
        if (!all.equals(s))
            fail("Failed to reconstruct ints with ListIterator.");
    }

    static void sublists(List<Integer> s) {
        List<Integer> all = clone(s, cl, synch);
        Iterator it = all.listIterator();
        int i=0;
        while (it.hasNext()) {
            Object o = it.next();
            if (all.indexOf(o) != all.lastIndexOf(o))
                fail("Apparent duplicate detected.");
            if (all.subList(i,   all.size()).indexOf(o) != 0) {
                System.out.println("s0: " + all.subList(i,   all.size()).indexOf(o));
                fail("subList/indexOf is screwy.");
            }
            if (all.subList(i+1, all.size()).indexOf(o) != -1) {
                System.out.println("s-1: " + all.subList(i+1, all.size()).indexOf(o));
                fail("subList/indexOf is screwy.");
            }
            if (all.subList(0,i+1).lastIndexOf(o) != i) {
                System.out.println("si" + all.subList(0,i+1).lastIndexOf(o));
                fail("subList/lastIndexOf is screwy.");
            }
            i++;
        }
    }

    static void arrays() {
        List<Integer> l = newList(cl, synch);
        AddRandoms(l, listSize);
        Integer[] ia = (Integer[]) l.toArray(new Integer[0]);
        if (!l.equals(Arrays.asList(ia)))
            fail("toArray(Object[]) is hosed (1)");
        ia = new Integer[listSize];
        Integer[] ib = (Integer[]) l.toArray(ia);
        if (ia != ib || !l.equals(Arrays.asList(ia)))
            fail("toArray(Object[]) is hosed (2)");
        ia = new Integer[listSize+1];
        ia[listSize] = new Integer(69);
        ib = (Integer[]) l.toArray(ia);
        if (ia != ib || ia[listSize] != null
            || !l.equals(Arrays.asList(ia).subList(0, listSize)))
            fail("toArray(Object[]) is hosed (3)");
    }

    // Done inefficiently so as to exercise toArray
    static List<Integer> clone(List s, Class cl, boolean synch) {
        List a = Arrays.asList(s.toArray());
        if (s.hashCode() != a.hashCode())
            fail("Incorrect hashCode computation.");

        List clone = newList(cl, synch);
        clone.addAll(a);
        if (!s.equals(clone))
            fail("List not equal to copy.");
        if (!s.containsAll(clone))
            fail("List does not contain copy.");
        if (!clone.containsAll(s))
            fail("Copy does not contain list.");

        return (List<Integer>)clone;
    }

    static List<Integer> newList(Class cl, boolean synch) {
        try {
            List<Integer> s = (List<Integer>)cl.newInstance();
            if (synch)
                s = Collections.synchronizedList(s);
            if (!s.isEmpty())
                fail("New instance non empty.");
            return s;
        } catch(Throwable t) {
            fail("Can't instantiate " + cl + ": " + t);
        }
        return null; //Shut up compiler.
    }

    static void AddRandoms(List<Integer> s, int n) {
        for (int i=0; i<n; i++) {
            int r = rnd.nextInt() % n;
            Integer e = new Integer(r < 0 ? -r : r);

            int preSize = s.size();
            if (!s.add(e))
                fail ("Add failed.");
            int postSize = s.size();
            if (postSize-preSize != 1)
                fail ("Add didn't increase size by 1.");
        }
    }

    static void fail(String s) {
        System.out.println(s);
        System.exit(1);
    }
}
Revision:	1.4
Committed:	Sun Sep 25 13:10:45 2005 UTC (18 years, 7 months ago) by dl
Branch:	MAIN
Changes since 1.3:	+144 -93 lines
Log Message:	Add timings
#	Content
1	/*
2	* Written by Josh Bloch and Doug Lea with assistance from members of
3	* JCP JSR-166 Expert Group and released to the public domain, as
4	* explained at http://creativecommons.org/licenses/publicdomain
5	*/
6
7	import java.util.*;
8
9	public class ListBash {
10	static boolean canRemove = true;
11	static final Random rnd = new Random();
12	static int numItr;
13	static int listSize;
14	static boolean synch;
15	static Class cl;
16
17	public static void main(String[] args) {
18	numItr = Integer.parseInt(args[1]);
19	listSize = Integer.parseInt(args[2]);
20	cl = null;
21
22	try {
23	cl = Class.forName(args[0]);
24	} catch(ClassNotFoundException e) {
25	fail("Class " + args[0] + " not found.");
26	}
27
28	synch = (args.length>3);
29	oneRun();
30	oneRun();
31	oneRun();
32	oneRun();
33	oneRun();
34	}
35
36	static void oneRun() {
37	long startTime = System.nanoTime();
38	for (int i=0; i<numItr; i++) {
39	elementLoop();
40	}
41	List<Integer> s = newList(cl, synch);
42	for (int i=0; i<listSize; i++)
43	s.add(new Integer(i));
44	if (s.size() != listSize)
45	fail("Size of [0..n-1] != n");
46	evenOdd(s);
47	sublists(s);
48	arrays();
49	long elapsed = System.nanoTime() - startTime;
50	System.out.println("Time: " + (elapsed/1000000000.0) + "s");
51	}
52
53
54
55	static void elementLoop() {
56	List<Integer> s1 = newList(cl, synch);
57	AddRandoms(s1, listSize);
58
59	List<Integer> s2 = newList(cl, synch);
60	AddRandoms(s2, listSize);
61
62	sets(s1, s2);
63
64	s1.clear();
65	if (s1.size() != 0)
66	fail("Clear didn't reduce size to zero.");
67
68	s1.addAll(0, s2);
69	if (!(s1.equals(s2) && s2.equals(s1)))
70	fail("addAll(int, Collection) doesn't work.");
71	// Reverse List
72	for (int j=0, n=s1.size(); j<n; j++)
73	s1.set(j, s1.set(n-j-1, s1.get(j)));
74	// Reverse it again
75	for (int j=0, n=s1.size(); j<n; j++)
76	s1.set(j, s1.set(n-j-1, s1.get(j)));
77	if (!(s1.equals(s2) && s2.equals(s1)))
78	fail("set(int, Object) doesn't work");
79	sums(s1, s2);
80	}
81
82	static void sums(List<Integer> s1, List<Integer> s2) {
83	int sum = 0;
84	for (int k = 0; k < listSize; ++k) {
85	sum += (s1.get(k)).intValue();
86	sum -= (s2.get(k)).intValue();
87	}
88	for (int k = 0; k < listSize; ++k) {
89	sum += (s1.get(k)).intValue();
90	s1.set(k, sum);
91	sum -= (s2.get(k)).intValue();
92	s1.set(k, -sum);
93	}
94	for (int k = 0; k < listSize; ++k) {
95	sum += (s1.get(k)).intValue();
96	sum -= (s2.get(k)).intValue();
97	}
98	if (sum == 0) System.out.print(" ");
99	}
100
101	static void sets(List<Integer> s1, List<Integer> s2) {
102	List<Integer> intersection = clone(s1, cl,synch);intersection.retainAll(s2);
103	List<Integer> diff1 = clone(s1, cl, synch); diff1.removeAll(s2);
104	List<Integer> diff2 = clone(s2, cl, synch); diff2.removeAll(s1);
105	List<Integer> union = clone(s1, cl, synch); union.addAll(s2);
106
107	if (diff1.removeAll(diff2))
108	fail("List algebra identity 2 failed");
109	if (diff1.removeAll(intersection))
110	fail("List algebra identity 3 failed");
111	if (diff2.removeAll(diff1))
112	fail("List algebra identity 4 failed");
113	if (diff2.removeAll(intersection))
114	fail("List algebra identity 5 failed");
115	if (intersection.removeAll(diff1))
116	fail("List algebra identity 6 failed");
117	if (intersection.removeAll(diff1))
118	fail("List algebra identity 7 failed");
119
120	intersection.addAll(diff1); intersection.addAll(diff2);
121	if (!(intersection.containsAll(union) &&
122	union.containsAll(intersection)))
123	fail("List algebra identity 1 failed");
124
125	Iterator e = union.iterator();
126	while (e.hasNext())
127	intersection.remove(e.next());
128	if (!intersection.isEmpty())
129	fail("Copy nonempty after deleting all elements.");
130
131	e = union.iterator();
132	while (e.hasNext()) {
133	Object o = e.next();
134	if (!union.contains(o))
135	fail("List doesn't contain one of its elements.");
136	if (canRemove) {
137	try { e.remove();
138	} catch (UnsupportedOperationException uoe) {
139	canRemove = false;
140	}
141	}
142	}
143	if (canRemove && !union.isEmpty())
144	fail("List nonempty after deleting all elements.");
145	}
146
147	static void evenOdd(List<Integer> s) {
148	List<Integer> even = clone(s, cl, synch);
149	List<Integer> odd = clone(s, cl, synch);
150	List<Integer> all;
151	Iterator<Integer> it;
152
153	if (!canRemove)
154	all = clone(s, cl, synch);
155	else {
156	it = even.iterator();
157	while(it.hasNext())
158	if((it.next()).intValue() % 2 == 1)
159	it.remove();
160	it = even.iterator();
161	while(it.hasNext())
162	if((it.next()).intValue() % 2 == 1)
163	fail("Failed to remove all odd nubmers.");
164
165	for (int i=0; i<(listSize/2); i++)
166	odd.remove(i);
167	for (int i=0; i<(listSize/2); i++) {
168	int ii = (odd.get(i)).intValue();
169	if(ii % 2 != 1)
170	fail("Failed to remove all even nubmers. " + ii);
171	}
172
173	all = clone(odd, cl, synch);
174	for (int i=0; i<(listSize/2); i++)
175	all.add(2*i, even.get(i));
176	if (!all.equals(s))
177	fail("Failed to reconstruct ints from odds and evens.");
178
179	all = clone(odd, cl, synch);
180	ListIterator<Integer> itAll = all.listIterator(all.size());
181	ListIterator<Integer> itEven = even.listIterator(even.size());
182	while (itEven.hasPrevious()) {
183	itAll.previous();
184	itAll.add(itEven.previous());
185	itAll.previous(); // ???
186	}
187	itAll = all.listIterator();
188	while (itAll.hasNext()) {
189	Integer i = itAll.next();
190	itAll.set(new Integer(i.intValue()));
191	}
192	itAll = all.listIterator();
193	it = s.iterator();
194	while(it.hasNext())
195	if(it.next()==itAll.next())
196	fail("Iterator.set failed to change value.");
197	}
198	if (!all.equals(s))
199	fail("Failed to reconstruct ints with ListIterator.");
200	}
201
202	static void sublists(List<Integer> s) {
203	List<Integer> all = clone(s, cl, synch);
204	Iterator it = all.listIterator();
205	int i=0;
206	while (it.hasNext()) {
207	Object o = it.next();
208	if (all.indexOf(o) != all.lastIndexOf(o))
209	fail("Apparent duplicate detected.");
210	if (all.subList(i, all.size()).indexOf(o) != 0) {
211	System.out.println("s0: " + all.subList(i, all.size()).indexOf(o));
212	fail("subList/indexOf is screwy.");
213	}
214	if (all.subList(i+1, all.size()).indexOf(o) != -1) {
215	System.out.println("s-1: " + all.subList(i+1, all.size()).indexOf(o));
216	fail("subList/indexOf is screwy.");
217	}
218	if (all.subList(0,i+1).lastIndexOf(o) != i) {
219	System.out.println("si" + all.subList(0,i+1).lastIndexOf(o));
220	fail("subList/lastIndexOf is screwy.");
221	}
222	i++;
223	}
224	}
225
226	static void arrays() {
227	List<Integer> l = newList(cl, synch);
228	AddRandoms(l, listSize);
229	Integer[] ia = (Integer[]) l.toArray(new Integer[0]);
230	if (!l.equals(Arrays.asList(ia)))
231	fail("toArray(Object[]) is hosed (1)");
232	ia = new Integer[listSize];
233	Integer[] ib = (Integer[]) l.toArray(ia);
234	if (ia != ib \|\| !l.equals(Arrays.asList(ia)))
235	fail("toArray(Object[]) is hosed (2)");
236	ia = new Integer[listSize+1];
237	ia[listSize] = new Integer(69);
238	ib = (Integer[]) l.toArray(ia);
239	if (ia != ib \|\| ia[listSize] != null
240	\|\| !l.equals(Arrays.asList(ia).subList(0, listSize)))
241	fail("toArray(Object[]) is hosed (3)");
242	}
243
244	// Done inefficiently so as to exercise toArray
245	static List<Integer> clone(List s, Class cl, boolean synch) {
246	List a = Arrays.asList(s.toArray());
247	if (s.hashCode() != a.hashCode())
248	fail("Incorrect hashCode computation.");
249
250	List clone = newList(cl, synch);
251	clone.addAll(a);
252	if (!s.equals(clone))
253	fail("List not equal to copy.");
254	if (!s.containsAll(clone))
255	fail("List does not contain copy.");
256	if (!clone.containsAll(s))
257	fail("Copy does not contain list.");
258
259	return (List<Integer>)clone;
260	}
261
262	static List<Integer> newList(Class cl, boolean synch) {
263	try {
264	List<Integer> s = (List<Integer>)cl.newInstance();
265	if (synch)
266	s = Collections.synchronizedList(s);
267	if (!s.isEmpty())
268	fail("New instance non empty.");
269	return s;
270	} catch(Throwable t) {
271	fail("Can't instantiate " + cl + ": " + t);
272	}
273	return null; //Shut up compiler.
274	}
275
276	static void AddRandoms(List<Integer> s, int n) {
277	for (int i=0; i<n; i++) {
278	int r = rnd.nextInt() % n;
279	Integer e = new Integer(r < 0 ? -r : r);
280
281	int preSize = s.size();
282	if (!s.add(e))
283	fail ("Add failed.");
284	int postSize = s.size();
285	if (postSize-preSize != 1)
286	fail ("Add didn't increase size by 1.");
287	}
288	}
289
290	static void fail(String s) {
291	System.out.println(s);
292	System.exit(1);
293	}
294	}