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/publicdomain/zero/1.0/
 */

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 = l.toArray(new Integer[0]);
        if (!l.equals(Arrays.asList(ia)))
            fail("toArray(Object[]) is hosed (1)");
        ia = new Integer[listSize];
        Integer[] ib = 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 = 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.15
Committed:	Thu Dec 18 18:43:22 2014 UTC (9 years, 5 months ago) by jsr166
Branch:	MAIN
Changes since 1.14:	+3 -3 lines
Log Message:	fix some [rawtypes] warnings
#	User	Rev	Content
1	dl	1.2	/*
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	jsr166	1.12	* explained at http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.2	*/
6
7	dl	1.1	import java.util.*;
8
9			public class ListBash {
10	dl	1.4	static boolean canRemove = true;
11			static final Random rnd = new Random();
12			static int numItr;
13			static int listSize;
14			static boolean synch;
15	jsr166	1.15	static Class<?> cl;
16	dl	1.1
17			public static void main(String[] args) {
18	dl	1.4	numItr = Integer.parseInt(args[1]);
19			listSize = Integer.parseInt(args[2]);
20			cl = null;
21	dl	1.1
22	jsr166	1.10	try {
23			cl = Class.forName(args[0]);
24			} catch (ClassNotFoundException e) {
25			fail("Class " + args[0] + " not found.");
26			}
27	dl	1.1
28	jsr166	1.14	synch = (args.length > 3);
29	dl	1.4	oneRun();
30			oneRun();
31			oneRun();
32			}
33	dl	1.1
34	dl	1.4	static void oneRun() {
35			long startTime = System.nanoTime();
36	jsr166	1.14	for (int i = 0; i < numItr; i++) {
37	dl	1.4	elementLoop();
38	jsr166	1.10	}
39			List<Integer> s = newList(cl, synch);
40	jsr166	1.14	for (int i = 0; i < listSize; i++)
41	jsr166	1.10	s.add(new Integer(i));
42			if (s.size() != listSize)
43			fail("Size of [0..n-1] != n");
44	dl	1.4	evenOdd(s);
45			sublists(s);
46			arrays();
47			long elapsed = System.nanoTime() - startTime;
48			System.out.println("Time: " + (elapsed/1000000000.0) + "s");
49			}
50	dl	1.1
51	dl	1.4
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	jsr166	1.14	for (int j = 0, n = s1.size(); j < n; j++)
71	dl	1.4	s1.set(j, s1.set(n-j-1, s1.get(j)));
72			// Reverse it again
73	jsr166	1.14	for (int j = 0, n = s1.size(); j < n; j++)
74	dl	1.4	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	jsr166	1.6	}
98	dl	1.4
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	dl	1.3
151			if (!canRemove)
152			all = clone(s, cl, synch);
153			else {
154			it = even.iterator();
155	jsr166	1.7	while (it.hasNext())
156			if ((it.next()).intValue() % 2 == 1)
157	dl	1.3	it.remove();
158			it = even.iterator();
159	jsr166	1.7	while (it.hasNext())
160			if ((it.next()).intValue() % 2 == 1)
161	dl	1.3	fail("Failed to remove all odd nubmers.");
162	jsr166	1.6
163	dl	1.3	for (int i=0; i<(listSize/2); i++)
164			odd.remove(i);
165			for (int i=0; i<(listSize/2); i++) {
166	dl	1.4	int ii = (odd.get(i)).intValue();
167	jsr166	1.7	if (ii % 2 != 1)
168	dl	1.3	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	jsr166	1.6
177	jsr166	1.13	all = clone(odd, cl, synch);
178	dl	1.4	ListIterator<Integer> itAll = all.listIterator(all.size());
179			ListIterator<Integer> itEven = even.listIterator(even.size());
180	dl	1.3	while (itEven.hasPrevious()) {
181			itAll.previous();
182			itAll.add(itEven.previous());
183			itAll.previous(); // ???
184			}
185			itAll = all.listIterator();
186			while (itAll.hasNext()) {
187	dl	1.4	Integer i = itAll.next();
188	dl	1.3	itAll.set(new Integer(i.intValue()));
189			}
190			itAll = all.listIterator();
191			it = s.iterator();
192	jsr166	1.7	while (it.hasNext())
193			if (it.next()==itAll.next())
194	dl	1.3	fail("Iterator.set failed to change value.");
195	dl	1.1	}
196	dl	1.3	if (!all.equals(s))
197			fail("Failed to reconstruct ints with ListIterator.");
198	dl	1.4	}
199
200			static void sublists(List<Integer> s) {
201			List<Integer> all = clone(s, cl, synch);
202			Iterator it = all.listIterator();
203	dl	1.3	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	jsr166	1.13	if (all.subList(i, all.size()).indexOf(o) != 0) {
209	dl	1.1	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	dl	1.3	fail("subList/indexOf is screwy.");
215	dl	1.1	}
216			if (all.subList(0,i+1).lastIndexOf(o) != i) {
217			System.out.println("si" + all.subList(0,i+1).lastIndexOf(o));
218	dl	1.3	fail("subList/lastIndexOf is screwy.");
219	dl	1.1	}
220	dl	1.3	i++;
221			}
222	dl	1.4	}
223	dl	1.1
224	dl	1.4	static void arrays() {
225			List<Integer> l = newList(cl, synch);
226	dl	1.1	AddRandoms(l, listSize);
227	jsr166	1.9	Integer[] ia = l.toArray(new Integer[0]);
228	dl	1.1	if (!l.equals(Arrays.asList(ia)))
229			fail("toArray(Object[]) is hosed (1)");
230			ia = new Integer[listSize];
231	jsr166	1.9	Integer[] ib = l.toArray(ia);
232	dl	1.1	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	jsr166	1.9	ib = l.toArray(ia);
237	dl	1.1	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	jsr166	1.15	static List<Integer> clone(List s, Class<?> cl, boolean synch) {
244	dl	1.1	List a = Arrays.asList(s.toArray());
245			if (s.hashCode() != a.hashCode())
246			fail("Incorrect hashCode computation.");
247
248	jsr166	1.10	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	dl	1.1
257	jsr166	1.10	return (List<Integer>) clone;
258	dl	1.1	}
259
260	jsr166	1.15	static List<Integer> newList(Class<?> cl, boolean synch) {
261	jsr166	1.10	try {
262			List<Integer> s = (List<Integer>) cl.newInstance();
263	dl	1.1	if (synch)
264			s = Collections.synchronizedList(s);
265	jsr166	1.10	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	dl	1.1	}
273
274	dl	1.4	static void AddRandoms(List<Integer> s, int n) {
275	jsr166	1.14	for (int i = 0; i < n; i++) {
276	jsr166	1.10	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	jsr166	1.11	fail("Add failed.");
282	jsr166	1.10	int postSize = s.size();
283			if (postSize-preSize != 1)
284	jsr166	1.11	fail("Add didn't increase size by 1.");
285	jsr166	1.10	}
286	dl	1.1	}
287
288			static void fail(String s) {
289	jsr166	1.10	System.out.println(s);
290			System.exit(1);
291	dl	1.1	}
292			}