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();
    }

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