|
1
8 package org.apache.avalon.excalibur.collections.test;
9
10 import junit.framework.TestCase;
11 import org.apache.avalon.excalibur.collections.BinaryHeap;
12
13
17 public final class BinaryHeapTestCase
18 extends TestCase
19 {
20 private final static Integer  VAL1 = new Integer ( 1 );
21 private final static Integer VAL2 = new Integer ( 2 );
22 private final static Integer VAL3 = new Integer ( 3 );
23 private final static Integer VAL4 = new Integer ( 4 );
24 private final static Integer VAL5 = new Integer ( 5 );
25 private final static Integer VAL6 = new Integer ( 6 );
26 private final static Integer VAL7 = new Integer ( 7 );
27
28 public BinaryHeapTestCase()
29 {
30 this("Binary Heap Test Case");
31 }
32
33 public BinaryHeapTestCase( String name )
34 {
35 super( name );
36 }
37
38 public void testSimpleOrder()
39 {
40 final BinaryHeap heap = new BinaryHeap();
41
42 heap.clear();
43 heap.insert( VAL1 );
44 heap.insert( VAL2 );
45 heap.insert( VAL3 );
46 heap.insert( VAL4 );
47
48 assertTrue( VAL1 == heap.peek() );
49 assertTrue( VAL1 == heap.pop() );
50 assertTrue( VAL2 == heap.pop() );
51 assertTrue( VAL3 == heap.pop() );
52 assertTrue( VAL4 == heap.pop() );
53 }
54
55 public void testReverseOrder()
56 {
57 final BinaryHeap heap = new BinaryHeap();
58
59 heap.clear();
60 heap.insert( VAL4 );
61 heap.insert( VAL3 );
62 heap.insert( VAL2 );
63 heap.insert( VAL1 );
64
65 assertTrue( VAL1 == heap.peek() );
66 assertTrue( VAL1 == heap.pop() );
67 assertTrue( VAL2 == heap.pop() );
68 assertTrue( VAL3 == heap.pop() );
69 assertTrue( VAL4 == heap.pop() );
70 }
71
72 public void testMixedOrder()
73 {
74 final BinaryHeap heap = new BinaryHeap();
75
76 heap.clear();
77 heap.insert( VAL4 );
78 heap.insert( VAL2 );
79 heap.insert( VAL1 );
80 heap.insert( VAL3 );
81
82 assertTrue( VAL1 == heap.peek() );
83 assertTrue( VAL1 == heap.pop() );
84 assertTrue( VAL2 == heap.pop() );
85 assertTrue( VAL3 == heap.pop() );
86 assertTrue( VAL4 == heap.pop() );
87 }
88
89 public void testDuplicates()
90 {
91 final BinaryHeap heap = new BinaryHeap();
92
93 heap.clear();
94 heap.insert( VAL4 );
95 heap.insert( VAL2 );
96 heap.insert( VAL1 );
97 heap.insert( VAL1 );
98 heap.insert( VAL1 );
99 heap.insert( VAL1 );
100 heap.insert( VAL3 );
101
102 assertTrue( VAL1 == heap.peek() );
103 assertTrue( VAL1 == heap.pop() );
104 assertTrue( VAL1 == heap.pop() );
105 assertTrue( VAL1 == heap.pop() );
106 assertTrue( VAL1 == heap.pop() );
107 assertTrue( VAL2 == heap.pop() );
108 assertTrue( VAL3 == heap.pop() );
109 assertTrue( VAL4 == heap.pop() );
110 }
111
112 public void testMixedInsertPopOrder()
113 {
114 final BinaryHeap heap = new BinaryHeap();
115
116 heap.clear();
117 heap.insert( VAL1 );
118 heap.insert( VAL4 );
119 heap.insert( VAL2 );
120 heap.insert( VAL1 );
121 heap.insert( VAL1 );
122 heap.insert( VAL1 );
123 heap.insert( VAL3 );
124
125 assertTrue( VAL1 == heap.peek() );
126 assertTrue( VAL1 == heap.pop() );
127 assertTrue( VAL1 == heap.pop() );
128 assertTrue( VAL1 == heap.pop() );
129 assertTrue( VAL1 == heap.pop() );
130
131 heap.insert( VAL4 );
132 heap.insert( VAL2 );
133 heap.insert( VAL1 );
134 heap.insert( VAL1 );
135 heap.insert( VAL1 );
136 heap.insert( VAL1 );
137 heap.insert( VAL3 );
138
139 assertTrue( VAL1 == heap.peek() );
140 assertTrue( VAL1 == heap.pop() );
141 assertTrue( VAL1 == heap.pop() );
142 assertTrue( VAL1 == heap.pop() );
143 assertTrue( VAL1 == heap.pop() );
144 assertTrue( VAL2 == heap.pop() );
145 assertTrue( VAL2 == heap.pop() );
146 assertTrue( VAL3 == heap.pop() );
147 assertTrue( VAL3 == heap.pop() );
148 assertTrue( VAL4 == heap.pop() );
149 assertTrue( VAL4 == heap.pop() );
150 }
151
152 public void testReverseSimpleOrder()
153 {
154 final BinaryHeap heap = new BinaryHeap( false );
155
156 heap.clear();
157 heap.insert( VAL1 );
158 heap.insert( VAL2 );
159 heap.insert( VAL3 );
160 heap.insert( VAL4 );
161
162 assertTrue( VAL4 == heap.pop() );
163 assertTrue( VAL3 == heap.pop() );
164 assertTrue( VAL2 == heap.pop() );
165 assertTrue( VAL1 == heap.peek() );
166 assertTrue( VAL1 == heap.pop() );
167
168 }
169
170 public void testReverseReverseOrder()
171 {
172 final BinaryHeap heap = new BinaryHeap( false );
173
174 heap.clear();
175 heap.insert( VAL4 );
176 heap.insert( VAL3 );
177 heap.insert( VAL2 );
178 heap.insert( VAL1 );
179
180 assertTrue( VAL4 == heap.pop() );
181 assertTrue( VAL3 == heap.pop() );
182 assertTrue( VAL2 == heap.pop() );
183 assertTrue( VAL1 == heap.peek() );
184 assertTrue( VAL1 == heap.pop() );
185 }
186
187 public void testReverseMixedOrder()
188 {
189 final BinaryHeap heap = new BinaryHeap( false );
190
191 heap.clear();
192 heap.insert( VAL4 );
193 heap.insert( VAL2 );
194 heap.insert( VAL1 );
195 heap.insert( VAL3 );
196
197 assertTrue( VAL4 == heap.pop() );
198 assertTrue( VAL3 == heap.pop() );
199 assertTrue( VAL2 == heap.pop() );
200 assertTrue( VAL1 == heap.peek() );
201 assertTrue( VAL1 == heap.pop() );
202 }
203
204 public void testReverseDuplicates()
205 {
206 final BinaryHeap heap = new BinaryHeap( false );
207
208 heap.clear();
209 heap.insert( VAL4 );
210 heap.insert( VAL3 );
211 heap.insert( VAL2 );
212 heap.insert( VAL1 );
213 heap.insert( VAL1 );
214 heap.insert( VAL1 );
215 heap.insert( VAL1 );
216
217 assertTrue( VAL4 == heap.pop() );
218 assertTrue( VAL3 == heap.pop() );
219 assertTrue( VAL2 == heap.pop() );
220 assertTrue( VAL1 == heap.peek() );
221 assertTrue( VAL1 == heap.pop() );
222 assertTrue( VAL1 == heap.pop() );
223 assertTrue( VAL1 == heap.pop() );
224 assertTrue( VAL1 == heap.pop() );
225 }
226
227 public void testReverseMixedInsertPopOrder()
228 {
229 final BinaryHeap heap = new BinaryHeap( false );
230
231 heap.clear();
232 heap.insert( VAL1 );
233 heap.insert( VAL4 );
234 heap.insert( VAL2 );
235 heap.insert( VAL1 );
236 heap.insert( VAL1 );
237 heap.insert( VAL1 );
238 heap.insert( VAL3 );
239
240 assertTrue( VAL4 == heap.pop() );
241 assertTrue( VAL3 == heap.pop() );
242 assertTrue( VAL2 == heap.pop() );
243
244 heap.insert( VAL4 );
245 heap.insert( VAL2 );
246 heap.insert( VAL1 );
247 heap.insert( VAL1 );
248 heap.insert( VAL1 );
249 heap.insert( VAL1 );
250 heap.insert( VAL3 );
251
252 assertTrue( VAL4 == heap.pop() );
253 assertTrue( VAL3 == heap.pop() );
254 assertTrue( VAL2 == heap.pop() );
255 assertTrue( VAL1 == heap.peek() );
256 assertTrue( VAL1 == heap.pop() );
257 assertTrue( VAL1 == heap.peek() );
258 assertTrue( VAL1 == heap.pop() );
259 assertTrue( VAL1 == heap.pop() );
260 assertTrue( VAL1 == heap.pop() );
261 assertTrue( VAL1 == heap.pop() );
262 assertTrue( VAL1 == heap.pop() );
263 assertTrue( VAL1 == heap.pop() );
264 assertTrue( VAL1 == heap.pop() );
265 }
266 }
267 |
Popular Tags |
Java API By Example, From Geeks To Geeks.