util/Deque/ChorusLine.java

/*
 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * @test
 * @bug 6324846
 * @summary Deque implementations must behave isomorphically
 * @author Martin Buchholz
 */

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class ChorusLine {
    private interface Tweaker {
        void run(Deque<Integer> deq);
    }

    private static final Tweaker[] tweakers = {
        new Tweaker() { public void run(Deque<Integer> deq) {
            for (int i = 0; i < 7; i++)
                deq.addLast(i);
            deq.removeFirst();
            deq.removeFirst();
            deq.addLast(7);
            deq.addLast(8);
            Iterator<Integer> it = deq.descendingIterator();
            equal(it.next(), 8);
            it.remove();

            try {it.remove();}
            catch (IllegalStateException e) {pass();}
            catch (Throwable t) {unexpected(t);}

            deq.addLast(9);
            it = deq.descendingIterator();
            equal(it.next(), 9);
            equal(it.next(), 7);
            it.remove();

            try {it.remove();}
            catch (IllegalStateException e) {pass();}
            catch (Throwable t) {unexpected(t);}

            equal(it.next(), 6);

            System.out.println(deq);
        }},
        new Tweaker() { public void run(Deque<Integer> deq) {
            deq.clear();
            check(deq.isEmpty());
            check(deq.size() == 0);
            check(! deq.iterator().hasNext());
            check(! deq.descendingIterator().hasNext());

            try {deq.iterator().next(); fail();}
            catch (NoSuchElementException e) {pass();}
            catch (Throwable t) {unexpected(t);}

            try {deq.descendingIterator().next(); fail();}
            catch (NoSuchElementException e) {pass();}
            catch (Throwable t) {unexpected(t);}
        }},
        new Tweaker() { public void run(Deque<Integer> deq) {
            for (int i = 0; i < 11; i++)
                deq.add(i);
            Iterator<Integer> it = deq.iterator();
            equal(it.next(), 0);
            equal(it.next(), 1);
            it.remove();
            deq.addFirst(-1);
            deq.addFirst(-2);
            it = deq.iterator();
            equal(it.next(), -2);
            equal(it.next(), -1);
            equal(it.next(), 0);
            it.remove();

            it = deq.descendingIterator();

            try {it.remove(); fail();}
            catch (IllegalStateException e) {pass();}
            catch (Throwable t) {unexpected(t);}

            equal(it.next(), 10);
            it.remove();

            try {it.remove(); fail();}
            catch (IllegalStateException e) {pass();}
            catch (Throwable t) {unexpected(t);}

            equal(it.next(), 9);
            equal(it.next(), 8);
            it.remove();
            System.out.println(deq);
        }},
        new Tweaker() { public void run(Deque<Integer> deq) {
            while (deq.size() > 1) {
                Iterator<Integer> it = deq.iterator();
                it.next(); it.remove();
                it = deq.descendingIterator();
                it.next(); it.remove();
            }
            System.out.println(deq);
        }}};

    private static void realMain(String[] args) throws Throwable {
        Collection<Deque<Integer>> deqs = new ArrayDeque<>(3);
        deqs.add(new ArrayDeque<Integer>());
        deqs.add(new LinkedList<Integer>());
        deqs.add(new LinkedBlockingDeque<Integer>());
        deqs.add(new ConcurrentLinkedDeque<Integer>());

        equal(deqs);

        for (Tweaker tweaker : tweakers) {
            for (Deque<Integer> deq : deqs)
                tweaker.run(deq);
            equal(deqs);
        }
    }

    private static void equal(Iterable<Deque<Integer>> deqs) {
        Deque<Integer> prev = null;
        for (Deque<Integer> deq : deqs) {
            if (prev != null) {
                equal(prev.isEmpty(), deq.isEmpty());
                equal(prev.size(), deq.size());
                equal(prev.toString(), deq.toString());
            }
            prev = deq;
        }

        Deque<Iterator<Integer>> its = new ArrayDeque<>();
        for (Deque<Integer> deq : deqs)
            its.addLast(deq.iterator());
        equal(its);

        Deque<Iterator<Integer>> dits = new ArrayDeque<>();
        for (Deque<Integer> deq : deqs)
            dits.addLast(deq.descendingIterator());
        equal(dits);
    }

    private static void equal(Deque<Iterator<Integer>> its) {
        Iterator<Integer> it0 = its.remove();
        while (it0.hasNext()) {
            Integer i = it0.next();
            for (Iterator<Integer> it : its)
                equal(it.next(), i);
        }
        for (Iterator<Integer> it : its) {
            check(! it.hasNext());

            try {it.next(); fail();}
            catch (NoSuchElementException e) {pass();}
            catch (Throwable t) {unexpected(t);}
        }
    }

    //--------------------- Infrastructure ---------------------------
    static volatile int passed = 0, failed = 0;
    static void pass() {passed++;}
    static void fail() {failed++; Thread.dumpStack();}
    static void fail(String msg) {System.out.println(msg); fail();}
    static void unexpected(Throwable t) {failed++; t.printStackTrace();}
    static void check(boolean cond) {if (cond) pass(); else fail();}
    static void equal(Object x, Object y) {
        if (x == null ? y == null : x.equals(y)) pass();
        else fail(x + " not equal to " + y);}
    public static void main(String[] args) throws Throwable {
        try {realMain(args);} catch (Throwable t) {unexpected(t);}
        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
        if (failed > 0) throw new AssertionError("Some tests failed");}
}
Revision:	1.7
Committed:	Wed Jan 4 04:46:19 2017 UTC (7 years, 5 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.6:	+3 -3 lines
Log Message:	convert to Diamond
#	User	Rev	Content
1	jsr166	1.1	/*
2	jsr166	1.5	* Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
3	jsr166	1.1	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4			*
5			* This code is free software; you can redistribute it and/or modify it
6			* under the terms of the GNU General Public License version 2 only, as
7			* published by the Free Software Foundation.
8			*
9			* This code is distributed in the hope that it will be useful, but WITHOUT
10			* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11			* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12			* version 2 for more details (a copy is included in the LICENSE file that
13			* accompanied this code).
14			*
15			* You should have received a copy of the GNU General Public License version
16			* 2 along with this work; if not, write to the Free Software Foundation,
17			* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18			*
19	jsr166	1.3	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20			* or visit www.oracle.com if you need additional information or have any
21			* questions.
22	jsr166	1.1	*/
23
24			/*
25			* @test
26			* @bug 6324846
27			* @summary Deque implementations must behave isomorphically
28			* @author Martin Buchholz
29			*/
30
31	jsr166	1.6	import java.util.ArrayDeque;
32			import java.util.Collection;
33			import java.util.Deque;
34			import java.util.Iterator;
35			import java.util.LinkedList;
36			import java.util.NoSuchElementException;
37			import java.util.concurrent.ConcurrentLinkedDeque;
38			import java.util.concurrent.LinkedBlockingDeque;
39	jsr166	1.1
40			public class ChorusLine {
41			private interface Tweaker {
42			void run(Deque<Integer> deq);
43			}
44
45	jsr166	1.4	private static final Tweaker[] tweakers = {
46	jsr166	1.1	new Tweaker() { public void run(Deque<Integer> deq) {
47			for (int i = 0; i < 7; i++)
48			deq.addLast(i);
49			deq.removeFirst();
50			deq.removeFirst();
51			deq.addLast(7);
52			deq.addLast(8);
53			Iterator<Integer> it = deq.descendingIterator();
54			equal(it.next(), 8);
55			it.remove();
56
57			try {it.remove();}
58			catch (IllegalStateException e) {pass();}
59			catch (Throwable t) {unexpected(t);}
60
61			deq.addLast(9);
62			it = deq.descendingIterator();
63			equal(it.next(), 9);
64			equal(it.next(), 7);
65			it.remove();
66
67			try {it.remove();}
68			catch (IllegalStateException e) {pass();}
69			catch (Throwable t) {unexpected(t);}
70
71			equal(it.next(), 6);
72
73			System.out.println(deq);
74			}},
75			new Tweaker() { public void run(Deque<Integer> deq) {
76			deq.clear();
77			check(deq.isEmpty());
78			check(deq.size() == 0);
79			check(! deq.iterator().hasNext());
80			check(! deq.descendingIterator().hasNext());
81
82			try {deq.iterator().next(); fail();}
83			catch (NoSuchElementException e) {pass();}
84			catch (Throwable t) {unexpected(t);}
85
86			try {deq.descendingIterator().next(); fail();}
87			catch (NoSuchElementException e) {pass();}
88			catch (Throwable t) {unexpected(t);}
89			}},
90			new Tweaker() { public void run(Deque<Integer> deq) {
91			for (int i = 0; i < 11; i++)
92			deq.add(i);
93			Iterator<Integer> it = deq.iterator();
94			equal(it.next(), 0);
95			equal(it.next(), 1);
96			it.remove();
97			deq.addFirst(-1);
98			deq.addFirst(-2);
99			it = deq.iterator();
100			equal(it.next(), -2);
101			equal(it.next(), -1);
102			equal(it.next(), 0);
103			it.remove();
104
105			it = deq.descendingIterator();
106
107			try {it.remove(); fail();}
108			catch (IllegalStateException e) {pass();}
109			catch (Throwable t) {unexpected(t);}
110
111			equal(it.next(), 10);
112			it.remove();
113
114			try {it.remove(); fail();}
115			catch (IllegalStateException e) {pass();}
116			catch (Throwable t) {unexpected(t);}
117
118			equal(it.next(), 9);
119			equal(it.next(), 8);
120			it.remove();
121			System.out.println(deq);
122			}},
123			new Tweaker() { public void run(Deque<Integer> deq) {
124			while (deq.size() > 1) {
125			Iterator<Integer> it = deq.iterator();
126			it.next(); it.remove();
127			it = deq.descendingIterator();
128			it.next(); it.remove();
129			}
130			System.out.println(deq);
131			}}};
132
133			private static void realMain(String[] args) throws Throwable {
134	jsr166	1.7	Collection<Deque<Integer>> deqs = new ArrayDeque<>(3);
135	jsr166	1.1	deqs.add(new ArrayDeque<Integer>());
136			deqs.add(new LinkedList<Integer>());
137			deqs.add(new LinkedBlockingDeque<Integer>());
138	jsr166	1.2	deqs.add(new ConcurrentLinkedDeque<Integer>());
139	jsr166	1.1
140			equal(deqs);
141
142			for (Tweaker tweaker : tweakers) {
143			for (Deque<Integer> deq : deqs)
144			tweaker.run(deq);
145			equal(deqs);
146			}
147			}
148
149			private static void equal(Iterable<Deque<Integer>> deqs) {
150			Deque<Integer> prev = null;
151			for (Deque<Integer> deq : deqs) {
152			if (prev != null) {
153			equal(prev.isEmpty(), deq.isEmpty());
154			equal(prev.size(), deq.size());
155			equal(prev.toString(), deq.toString());
156			}
157			prev = deq;
158			}
159
160	jsr166	1.7	Deque<Iterator<Integer>> its = new ArrayDeque<>();
161	jsr166	1.1	for (Deque<Integer> deq : deqs)
162			its.addLast(deq.iterator());
163			equal(its);
164
165	jsr166	1.7	Deque<Iterator<Integer>> dits = new ArrayDeque<>();
166	jsr166	1.1	for (Deque<Integer> deq : deqs)
167			dits.addLast(deq.descendingIterator());
168			equal(dits);
169			}
170
171			private static void equal(Deque<Iterator<Integer>> its) {
172			Iterator<Integer> it0 = its.remove();
173			while (it0.hasNext()) {
174			Integer i = it0.next();
175			for (Iterator<Integer> it : its)
176			equal(it.next(), i);
177			}
178			for (Iterator<Integer> it : its) {
179			check(! it.hasNext());
180
181			try {it.next(); fail();}
182			catch (NoSuchElementException e) {pass();}
183			catch (Throwable t) {unexpected(t);}
184			}
185			}
186
187			//--------------------- Infrastructure ---------------------------
188			static volatile int passed = 0, failed = 0;
189			static void pass() {passed++;}
190			static void fail() {failed++; Thread.dumpStack();}
191			static void fail(String msg) {System.out.println(msg); fail();}
192			static void unexpected(Throwable t) {failed++; t.printStackTrace();}
193			static void check(boolean cond) {if (cond) pass(); else fail();}
194			static void equal(Object x, Object y) {
195			if (x == null ? y == null : x.equals(y)) pass();
196			else fail(x + " not equal to " + y);}
197			public static void main(String[] args) throws Throwable {
198			try {realMain(args);} catch (Throwable t) {unexpected(t);}
199			System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
200			if (failed > 0) throw new AssertionError("Some tests failed");}
201			}