001: // This file is part of KeY - Integrated Deductive Software Design
002: // Copyright (C) 2001-2007 Universitaet Karlsruhe, Germany
003: // Universitaet Koblenz-Landau, Germany
004: // Chalmers University of Technology, Sweden
005: //
006: // The KeY system is protected by the GNU General Public License.
007: // See LICENSE.TXT for details.
008: //
009: //
010:
011: package de.uka.ilkd.key.collection;
012:
013: /** tests non-destructive list implementation with String */
014:
015: public class TestSLListOfString extends junit.framework.TestCase {
016:
017: String str[] = new String[] { "Dies", "ist", "ein", "Test" };
018:
019: public TestSLListOfString(String name) {
020: super (name);
021: }
022:
023: ListOfString a; // "A" "B" "C"
024: ListOfString a1; // "A" "B" "C"
025: ListOfString b; // "A" "B"
026: ListOfString c; // "A" "B" "C" "D"
027: ListOfString d; // "A" "B" "A"
028: ListOfString e; // "A" "B" null
029: ListOfString e1; // "A" "B" null
030:
031: public void setUp() {
032: a = SLListOfString.EMPTY_LIST.prepend("C").prepend("B")
033: .prepend("A");
034: a1 = SLListOfString.EMPTY_LIST.prepend("C").prepend("B")
035: .prepend("A");
036: b = SLListOfString.EMPTY_LIST.prepend("B").prepend("A");
037: c = SLListOfString.EMPTY_LIST.prepend("D").prepend("C")
038: .prepend("B").prepend("A");
039: d = SLListOfString.EMPTY_LIST.prepend("A").prepend("B")
040: .prepend("A");
041: e = SLListOfString.EMPTY_LIST.prepend((String) null).prepend(
042: "B").prepend("A");
043: e1 = SLListOfString.EMPTY_LIST.prepend((String) null).prepend(
044: "B").prepend("A");
045: }
046:
047: // tests prepend and implicitly iterator, size
048: public void testPrepend() {
049: ListOfString[] newList = new ListOfString[str.length + 1];
050: newList[0] = SLListOfString.EMPTY_LIST;
051:
052: for (int i = 1; i < str.length + 1; i++) {
053: newList[i] = newList[i - 1].prepend(str[i - 1]);
054: }
055: // Test elements in list
056: for (int i = 0; i < str.length + 1; i++) {
057: IteratorOfString it = newList[i].iterator();
058: int size = newList[i].size();
059: if (i > 0) { // list should have elements
060: assertTrue(it.hasNext());
061: assertTrue(size == i);
062: } else { // list is empty
063: assertTrue(!it.hasNext());
064: assertTrue(size == 0);
065: }
066: int nr = 0;
067: while (it.hasNext()) {
068: assertSame(it.next(), str[size - 1 - nr]);
069: nr++;
070: }
071: // list has right length
072: assertTrue(nr == size);
073: }
074: // prepend two lists
075: ListOfString prepList = newList[1].prepend(newList[2]);
076: assertTrue(prepList.size() == 3);
077: // right order
078: assertEquals(str[1], prepList.head());
079: assertEquals(str[0], prepList.tail().head());
080: assertEquals(str[0], prepList.tail().tail().head());
081: }
082:
083: // tests append and implicitly iterator, size
084: public void testAppend() {
085: ListOfString[] newList = new ListOfString[str.length + 1];
086: newList[0] = SLListOfString.EMPTY_LIST;
087:
088: for (int i = 1; i < str.length + 1; i++) {
089: newList[i] = newList[i - 1].append(str[i - 1]);
090: }
091: // Test elements in list
092: for (int i = 0; i < str.length + 1; i++) {
093: IteratorOfString it = newList[i].iterator();
094: int size = newList[i].size();
095: if (i > 0) { // list should have elements
096: assertTrue(it.hasNext());
097: assertTrue(size == i);
098: } else { // list is empty
099: assertTrue(!it.hasNext());
100: assertTrue(size == 0);
101: }
102: int nr = 0;
103: while (it.hasNext()) {
104: assertSame(it.next(), str[nr]);
105: nr++;
106: }
107: // list has right length
108: assertTrue(nr == size);
109: }
110:
111: // append two lists
112: ListOfString appList = newList[2].append(newList[1]);
113: assertTrue(appList.size() == 3);
114: // right order
115: assertEquals(str[0], appList.head());
116: assertEquals(str[1], appList.tail().head());
117: assertEquals(str[0], appList.tail().tail().head());
118: }
119:
120: // tests tail,head
121: public void testHeadTail() {
122: ListOfString[] newList = new ListOfString[str.length + 1];
123: newList[0] = SLListOfString.EMPTY_LIST;
124:
125: for (int i = 1; i < str.length + 1; i++) {
126: newList[i] = newList[i - 1].prepend(str[i - 1]);
127: }
128: // test cascading tail
129: for (int i = 0; i < str.length; i++) {
130: assertSame(newList[i + 1].tail(), newList[i]);
131: assertSame(newList[i + 1].head(), str[i]);
132: }
133: }
134:
135: // tests contains
136: public void testContains() {
137: ListOfString newList = SLListOfString.EMPTY_LIST;
138:
139: for (int i = 1; i < str.length + 1; i++) {
140: newList = newList.append(str[i - 1]);
141: }
142: // test cascading tail
143: for (int i = 0; i < str.length; i++) {
144: assertTrue(newList.contains(str[i]));
145: }
146: }
147:
148: // tests removeAll
149: public void testRemoveAll() {
150: ListOfString newList = SLListOfString.EMPTY_LIST;
151:
152: newList = newList.append(str[0]);
153: for (int i = 1; i < str.length + 1; i++) {
154: newList = newList.append(str[i - 1]);
155: }
156: newList = newList.append(str[0]);
157: newList = newList.removeAll(str[0]);
158: assertTrue("str[0] should have been removed", !newList
159: .contains(str[0]));
160:
161: }
162:
163: public void testRemoveFirst() {
164: ListOfString newList = SLListOfString.EMPTY_LIST;
165:
166: newList = newList.prepend(str[0]);
167: for (int i = 1; i < str.length + 1; i++) {
168: newList = newList.prepend(str[i - 1]);
169: }
170: newList = newList.prepend(str[0]);
171: int oldSize = newList.size();
172: newList = newList.removeFirst(str[0]);
173:
174: assertTrue("Only first occurrence should have been removed",
175: newList.head() != str[0]
176: && newList.size() == oldSize - 1);
177:
178: newList = newList.removeFirst(str[0]);
179: assertTrue("Only first occurrence should have been removed",
180: newList.size() == oldSize - 2);
181: newList = newList.removeFirst(str[0]);
182:
183: assertTrue("Only first occurrence should have been removed",
184: !(newList.contains(str[0]))
185: && newList.size() == oldSize - 3);
186:
187: }
188:
189: public void testEquals() {
190: assertTrue("a==a1", a.equals(a1));
191: assertTrue("a!=b", !a.equals(b));
192: assertTrue("a!=c", !a.equals(c));
193: assertTrue("a!=d", !a.equals(d));
194: assertTrue("a!=e", !a.equals(e));
195: assertTrue("e!=a", !e.equals(a));
196: assertTrue("e==e1", e.equals(e1));
197: }
198:
199: public void testToString() {
200: ListOfString newList = SLListOfString.EMPTY_LIST;
201: for (int i = 0; i < str.length; i++) {
202: newList = newList.append(str[i]);
203: }
204: assertEquals("[Dies,ist,ein,Test]", newList.toString());
205: }
206:
207: public static void performanceTest(int n) {
208: System.out.println("Performance Test for " + n + " elements");
209: ListOfString newList = SLListOfString.EMPTY_LIST;
210: System.out.println("Create list with prepend.");
211: long start = System.currentTimeMillis();
212: for (int i = 0; i < n; i++) {
213: newList = newList.prepend("" + i);
214: }
215: long end = System.currentTimeMillis();
216: System.out.println("Time:" + (end - start) + " ms");
217:
218: System.out.print("append:");
219: start = System.currentTimeMillis();
220: for (int i = 0; i < n; i++) {
221: newList = newList.append("" + i);
222: }
223: end = System.currentTimeMillis();
224: System.out.println((end - start) + " ms");
225:
226: System.out.print("contains:");
227: start = System.currentTimeMillis();
228: newList.contains("" + n);
229: end = System.currentTimeMillis();
230: System.out.println((end - start) + " ms");
231:
232: }
233:
234: public static void main(String[] args) {
235: ListOfString newList = SLListOfString.EMPTY_LIST;
236: newList.prepend("a");
237:
238: performanceTest(10);
239: performanceTest(100);
240: performanceTest(1000);
241: performanceTest(10000);
242: performanceTest(100000);
243: performanceTest(1000000);
244: }
245: }
|