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
#	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			* explained at http://creativecommons.org/licenses/publicdomain
5			*/
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			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			try {
23			cl = Class.forName(args[0]);
24			} catch(ClassNotFoundException e) {
25			fail("Class " + args[0] + " not found.");
26			}
27
28	dl	1.4	synch = (args.length>3);
29			oneRun();
30			oneRun();
31			oneRun();
32			oneRun();
33			oneRun();
34			}
35	dl	1.1
36	dl	1.4	static void oneRun() {
37			long startTime = System.nanoTime();
38	dl	1.1	for (int i=0; i<numItr; i++) {
39	dl	1.4	elementLoop();
40	dl	1.1	}
41	dl	1.4	List<Integer> s = newList(cl, synch);
42	dl	1.1	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	dl	1.4	evenOdd(s);
47			sublists(s);
48			arrays();
49			long elapsed = System.nanoTime() - startTime;
50			System.out.println("Time: " + (elapsed/1000000000.0) + "s");
51			}
52	dl	1.1
53	dl	1.4
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	dl	1.3
153			if (!canRemove)
154			all = clone(s, cl, synch);
155			else {
156			it = even.iterator();
157			while(it.hasNext())
158	dl	1.4	if((it.next()).intValue() % 2 == 1)
159	dl	1.3	it.remove();
160			it = even.iterator();
161			while(it.hasNext())
162	dl	1.4	if((it.next()).intValue() % 2 == 1)
163	dl	1.3	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	dl	1.4	int ii = (odd.get(i)).intValue();
169	dl	1.3	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	dl	1.4	ListIterator<Integer> itAll = all.listIterator(all.size());
181			ListIterator<Integer> itEven = even.listIterator(even.size());
182	dl	1.3	while (itEven.hasPrevious()) {
183			itAll.previous();
184			itAll.add(itEven.previous());
185			itAll.previous(); // ???
186			}
187			itAll = all.listIterator();
188			while (itAll.hasNext()) {
189	dl	1.4	Integer i = itAll.next();
190	dl	1.3	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	dl	1.1	}
198	dl	1.3	if (!all.equals(s))
199			fail("Failed to reconstruct ints with ListIterator.");
200	dl	1.4	}
201
202			static void sublists(List<Integer> s) {
203			List<Integer> all = clone(s, cl, synch);
204			Iterator it = all.listIterator();
205	dl	1.3	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	dl	1.1	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	dl	1.3	fail("subList/indexOf is screwy.");
217	dl	1.1	}
218			if (all.subList(0,i+1).lastIndexOf(o) != i) {
219			System.out.println("si" + all.subList(0,i+1).lastIndexOf(o));
220	dl	1.3	fail("subList/lastIndexOf is screwy.");
221	dl	1.1	}
222	dl	1.3	i++;
223			}
224	dl	1.4	}
225	dl	1.1
226	dl	1.4	static void arrays() {
227			List<Integer> l = newList(cl, synch);
228	dl	1.1	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	dl	1.4	static List<Integer> clone(List s, Class cl, boolean synch) {
246	dl	1.1	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	dl	1.4	return (List<Integer>)clone;
260	dl	1.1	}
261
262	dl	1.4	static List<Integer> newList(Class cl, boolean synch) {
263	dl	1.1	try {
264	dl	1.4	List<Integer> s = (List<Integer>)cl.newInstance();
265	dl	1.1	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	dl	1.4	static void AddRandoms(List<Integer> s, int n) {
277	dl	1.1	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			}