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: import java.util.Arrays;
016: import java.util.Random;
017:
018: import de.uka.ilkd.key.logic.*;
019: import de.uka.ilkd.key.util.ExtList;
020:
021: public class TestLeftistHeapOfInteger extends junit.framework.TestCase {
022:
023: public TestLeftistHeapOfInteger(String name) {
024: super (name);
025: }
026:
027: ListOfInteger a;
028: ListOfInteger b;
029:
030: Random rand = new Random();
031:
032: public void setUp() {
033: a = SLListOfInteger.EMPTY_LIST.prepend(new Integer(13))
034: .prepend(new Integer(20)).prepend(new Integer(5))
035: .prepend(new Integer(7)).prepend(new Integer(16))
036: .prepend(new Integer(60)).prepend(new Integer(20))
037: .prepend(new Integer(-34));
038: b = SLListOfInteger.EMPTY_LIST.prepend(new Integer(-1000))
039: .prepend(new Integer(1000)).prepend(new Integer(8));
040: }
041:
042: public void testInsertElements() {
043: HeapOfInteger h = LeftistHeapOfInteger.EMPTY_HEAP;
044: assertTrue("Empty heap should be empty", h.isEmpty()
045: && h.size() == 0);
046:
047: h.insert(new Integer(1));
048: assertTrue("Empty heap should be empty", h.isEmpty()
049: && h.size() == 0);
050:
051: h = h.insert(new Integer(1));
052: assertTrue("Heap should contain one element", !h.isEmpty()
053: && h.size() == 1 && h.findMin().intValue() == 1);
054:
055: h = h.deleteMin();
056: assertTrue("Empty heap should be empty", h.isEmpty()
057: && h.size() == 0
058: && h == LeftistHeapOfInteger.EMPTY_HEAP);
059:
060: h = h.insert(new Integer(1)).insert(new Integer(2));
061: assertTrue("Heap should contain two elements", !h.isEmpty()
062: && h.size() == 2 && h.findMin().intValue() == 1);
063: h = h.deleteMin();
064: assertTrue("Heap should contain one element", !h.isEmpty()
065: && h.size() == 1 && h.findMin().intValue() == 2);
066: h = h.deleteMin();
067: assertTrue("Empty heap should be empty", h.isEmpty()
068: && h.size() == 0
069: && h == LeftistHeapOfInteger.EMPTY_HEAP);
070: }
071:
072: private ListOfInteger removeFirst(ListOfInteger list,
073: Integer element) {
074: ListOfInteger remainder = SLListOfInteger.EMPTY_LIST;
075: Integer i;
076:
077: while (true) {
078: assertTrue("Cannot remove element from list",
079: list != SLListOfInteger.EMPTY_LIST);
080:
081: i = list.head();
082: list = list.tail();
083:
084: if (i.equals(element))
085: break;
086:
087: remainder = remainder.prepend(i);
088: }
089:
090: return list.prepend(remainder);
091: }
092:
093: private boolean equals(IteratorOfInteger t0, IteratorOfInteger t1) {
094: ExtList l0 = new ExtList(), l1 = new ExtList();
095:
096: while (t0.hasNext())
097: l0.add(t0.next());
098:
099: while (t1.hasNext())
100: l1.add(t1.next());
101:
102: Object[] a0 = (Object[]) l0.collect(Object.class);
103: Object[] a1 = (Object[]) l1.collect(Object.class);
104:
105: Arrays.sort(a0);
106: Arrays.sort(a1);
107:
108: return Arrays.equals(a0, a1);
109: }
110:
111: private void checkHeap(ListOfInteger elements, HeapOfInteger h) {
112: assertTrue("Heap has incorrect size", h.size() == elements
113: .size()
114: && (h.size() == 0) == h.isEmpty());
115:
116: assertTrue(
117: "Unsorted heap iterator does not return the right elements",
118: equals(h.iterator(), elements.iterator()));
119:
120: IteratorOfInteger t0 = h.sortedIterator();
121: Integer lastElement = null;
122: Integer element;
123:
124: while (t0.hasNext()) {
125: element = t0.next();
126: if (lastElement != null)
127: assertTrue(
128: "Elements returned by sorted iterator should be sorted",
129: lastElement.compareTo(element) <= 0);
130: lastElement = element;
131: }
132:
133: assertTrue(
134: "Unsorted heap iterator does not return the right elements",
135: equals(h.sortedIterator(), elements.iterator()));
136:
137: ListOfInteger list = SLListOfInteger.EMPTY_LIST;
138: lastElement = null;
139:
140: while (!h.isEmpty()) {
141: element = h.findMin();
142: list = list.prepend(element);
143: if (lastElement != null)
144: assertTrue(
145: "Elements returned by findMin() should be sorted",
146: lastElement.compareTo(element) <= 0);
147: lastElement = element;
148: h = h.deleteMin();
149: }
150:
151: assertTrue("findMin does not return the right elements",
152: equals(list.iterator(), elements.iterator()));
153: }
154:
155: private HeapOfInteger removeAll(HeapOfInteger h,
156: IteratorOfInteger elements) {
157: while (elements.hasNext())
158: h = h.removeAll(elements.next());
159: return h;
160: }
161:
162: public void testInsertIterator() {
163: HeapOfInteger h = LeftistHeapOfInteger.EMPTY_HEAP;
164:
165: h = h.insert(SLListOfInteger.EMPTY_LIST.iterator());
166: checkHeap(SLListOfInteger.EMPTY_LIST, h);
167: assertTrue("Empty heap should be empty", h.isEmpty()
168: && h.size() == 0
169: && h == LeftistHeapOfInteger.EMPTY_HEAP);
170:
171: h = h.insert(a.iterator());
172: checkHeap(a, h);
173:
174: h = h.insert(a.iterator());
175: checkHeap(a.prepend(a), h);
176:
177: h = h.insert(SLListOfInteger.EMPTY_LIST.iterator());
178: checkHeap(a.prepend(a), h);
179:
180: h = h.insert(h.iterator());
181: checkHeap(a.prepend(a).prepend(a).prepend(a), h);
182:
183: h = h.insert(h.sortedIterator());
184: checkHeap(a.prepend(a).prepend(a).prepend(a).prepend(a)
185: .prepend(a).prepend(a).prepend(a), h);
186: }
187:
188: public void testInsertHeap() {
189: HeapOfInteger h = LeftistHeapOfInteger.EMPTY_HEAP;
190:
191: h = h.insert(a.iterator());
192: checkHeap(a, h);
193:
194: h = h.insert(LeftistHeapOfInteger.EMPTY_HEAP);
195: checkHeap(a, h);
196:
197: h = h.insert(h);
198: checkHeap(a.prepend(a), h);
199:
200: h = h.insert(LeftistHeapOfInteger.EMPTY_HEAP
201: .insert(new Integer(123)));
202: checkHeap(a.prepend(a).prepend(new Integer(123)), h);
203: }
204:
205: public void testRemoveAll() {
206: HeapOfInteger h = LeftistHeapOfInteger.EMPTY_HEAP;
207:
208: // Test removal of all elements (from empty heap)
209: checkHeap(SLListOfInteger.EMPTY_LIST,
210: removeAll(h, a.iterator()));
211:
212: h = h.insert(a.iterator());
213: checkHeap(a, h);
214:
215: // Test removal of arbitrary elements
216: checkHeap(a.removeAll(a.head()), h.removeAll(a.head()));
217:
218: // Test removal of all elements
219: checkHeap(SLListOfInteger.EMPTY_LIST,
220: removeAll(h, a.iterator()));
221:
222: // Test removal of non-existing elements
223: assertSame("Heap should not be different", h, removeAll(h, b
224: .iterator()));
225: }
226:
227: public void testLargeHeap() {
228: HeapOfInteger h = LeftistHeapOfInteger.EMPTY_HEAP;
229: ListOfInteger l = SLListOfInteger.EMPTY_LIST;
230:
231: int i = 1000;
232: while (i-- != 0)
233: l = l.prepend(new Integer(rand.nextInt(1000000)));
234:
235: h = h.insert(l.iterator());
236:
237: checkHeap(l, h);
238: }
239:
240: }
|