1 /*
2 * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.
3 * 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 * 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 */
23
24 /**
25 @test
26 @summary
27 @summary com.apple.junit.java.util;
28 @run junit CollectionStress01
29 */
30
31 /*
32
33 This test generates a field of boolean values, then uses recursive checks to
34 attempt to find a minimal set of rectangles that contain only the false values.
35
36 Puts a fair bit of stress on the collection classes.
37
38 */
39
40 import junit.framework.*;
41
42 import java.awt.*;
43 import java.util.*;
44
45
46 public class CollectionStress01 extends TestCase {
47
48 static final boolean kDebug = false;
49 static final int kSeed = 12225;
50 static final int kPaintThreshold = 50000;
51 static final int kPauseTime = 5;
52 static final int kBooleanDensity = 25;
53 static final int kWidth = 32;
54 static final int kHeight = 36;
55 static final int kScale = 18;
56 static final Rectangle kBoolRect = new Rectangle( 0, 0, kWidth, kHeight);
57 static final Rectangle kDisplayRect = new Rectangle( 0, 0, kWidth*kScale, kHeight*kScale);
58
59 boolean[][] boolSpace = new boolean[kWidth][kHeight];
60
61 Frame displayFrame = null;
62 DisplayArea displayArea = new DisplayArea();
63 Random rand = new Random(kSeed);
64
65 HashMap<Rectangle,Vector<Rectangle>> cache = new HashMap<Rectangle,Vector<Rectangle>> ();
66
67 class DisplayArea extends Panel {
68 private static final long serialVersionUID = 1L;
69 Vector<Rectangle> currEmpties;
70 Vector<Rectangle> debugCases;
71 String debugInfo;
72 Rectangle currRect;
73 Point currPoint;
74
75 public Dimension getPreferredSize() {
76 return ( new Dimension(kDisplayRect.width, kDisplayRect.height) );
77 }
78
79 public void paint( Graphics g){
80 super.paint(g);
81 g.clearRect(0,0, kDisplayRect.width, kDisplayRect.height);
82
83 // representation of boolean field
84 g.setColor( Color.RED );
85 for(int i = 0; i < boolSpace.length; i+=1) {
86 for(int ii = 0; ii < boolSpace[i].length; ii+=1) {
87 if (boolSpace[i][ii]) {
88 g.fillRect(i*kScale, ii*kScale, kScale, kScale);
89 }
90 }
91 }
92
93 // draw the currPoint
94 g.setColor( Color.BLUE );
95 Point p = null;
96 synchronized (this) {
97 p = currPoint;
98 }
99 if (p != null) {
100 g.fillRect(p.x*kScale, p.y*kScale, kScale, kScale);
101 }
102
103 // draw the debugCases
104 g.setColor( new Color( 0x40, 0xFF, 0x40, 0x80 ));
105 Vector<Rectangle> dVect = null;
106 synchronized (this) {
107 dVect = debugCases;
108 }
109 if (dVect != null) {
110 for (Rectangle e : dVect) {
111 g.fillRoundRect((e.x*kScale)+1, (e.y*kScale)+1, (e.width*kScale)-2, (e.height*kScale) -2 , 15, 15);
112 }
113 }
114
115 // draw the currEmpties
116 g.setColor( Color.CYAN);
117 Vector<Rectangle> eVect = null;
118 synchronized (this) {
119 eVect = currEmpties;
120 }
121 if (eVect != null) {
122 for (Rectangle e : eVect) {
123 g.fillRoundRect((e.x*kScale)+1, (e.y*kScale)+1, (e.width*kScale)-2, (e.height*kScale) -2 , 15, 15);
124 }
125 }
126
127 // draw the currRect
128 g.setColor( Color.BLACK );
129 Rectangle r = null;
130 synchronized (this) {
131 r = currRect;
132 }
133 if (r != null) {
134 g.drawRect(r.x*kScale+2, r.y*kScale+2, r.width*kScale-4, r.height*kScale-4);
135 }
136
137 // draw debugInfo at currPoint
138 g.setColor(Color.BLACK);
139 String d = null;
140 synchronized (this) {
141 d = debugInfo;
142 }
143 if (d != null) {
144 if ( p != null ) {
145 g.drawString(d, p.x*kScale, p.y*kScale+10);
146 }
147 else {
148 g.drawString(d, 5, 15);
149 }
150 }
151 }
152
153 int paintCount = 0;
154 void tickle() {
155 if (paintCount > kPaintThreshold) {
156 paintCount = 0;
157 repaint();
158 try {
159 Thread.sleep(kPauseTime);
160 } catch (InterruptedException e) {
161 e.printStackTrace();
162 }
163 }
164 else {
165 paintCount +=1;
166 }
167
168 }
169
170 // setters which also (occasionally) redisplay
171 public void setCurrEmpties(Vector<Rectangle> currEmpties) {
172 synchronized (this) {
173 this.currEmpties = currEmpties;
174 }
175 tickle();
176 }
177
178 public void setCurrPoint(Point currPoint) {
179 synchronized (this) {
180 this.currPoint = currPoint;
181 }
182 tickle();
183 }
184
185 public void setCurrRect(Rectangle currRect) {
186 synchronized (this) {
187 this.currRect = currRect;
188 }
189 tickle();
190 }
191
192 public void setDebugCases(Vector<Rectangle> debugCases) {
193 synchronized (this) {
194 this.debugCases = debugCases;
195 }
196 tickle();
197 }
198
199 public void setDebugInfo(String debugInfo) {
200 synchronized (this) {
201 this.debugInfo = debugInfo;
202 }
203 tickle();
204 }
205
206 }
207
208 protected void setUp() throws Exception {
209 super.setUp();
210 displayFrame = new Frame();
211 displayFrame.setLocation(10,10);
212 displayFrame.add( displayArea );
213 displayFrame.pack();
214 }
215
216 protected void tearDown() throws Exception {
217 super.tearDown();
218 displayFrame.dispose();
219 }
220
221 public void xxtestSplit() throws Exception {
222 init();
223
224 assertNotNull(displayFrame);
225 displayFrame.setVisible(true);
226
227
228 for (int i = 0; i < 200; i+=1) {
229 int ww = rand.nextInt(1+kBoolRect.width);
230 int hh = rand.nextInt(1+kBoolRect.height);
231 int xx = rand.nextInt(1+kBoolRect.width-ww);
232 int yy = rand.nextInt(1+kBoolRect.height-hh);
233
234 Rectangle probe = new Rectangle(xx, yy, ww, hh);
235 displayArea.setCurrRect(probe);
236
237 Point p = split(probe);
238 displayArea.setCurrPoint(p);
239 displayArea.repaint();
240 // Thread.sleep(1250);
241 }
242
243 Thread.sleep(125);
244 }
245
246 public void testSubRects() throws Exception {
247 init();
248
249 assertNotNull(displayFrame);
250 // displayFrame.setVisible(true);
251
252 for (int i = 0; i < 10; i+=1) {
253 int x = kBoolRect.x + rand.nextInt( kBoolRect.width);
254 int y = kBoolRect.y + rand.nextInt( kBoolRect.height);
255
256 Point p = new Point(x,y);
257 displayArea.setCurrPoint(p);
258 for (int kind =0; kind< 8; kind++) {
259 Vector<Rectangle> caseRects = divideRectForSubcase(kBoolRect, p, kind);
260 displayArea.setDebugInfo( kind + " " + caseRects.size() );
261 displayArea.setDebugCases(caseRects);
262 }
263 }
264
265 displayArea.setCurrRect(kBoolRect);
266 displayArea.setDebugCases(null);
267
268 Thread.sleep(125);
269 }
270
271 public void testRecursiveStress() throws Exception {
272 init();
273
274 assertNotNull(displayFrame);
275 displayFrame.setVisible(true);
276
277 Vector<Rectangle> answer = findEmptyRects(kBoolRect, 0);
278 assertTrue( answer.size() < (kBoolRect.width * kBoolRect.height) );
279
280 //System.out.println(answer.size());
281
282 displayArea.setCurrPoint(null);
283 displayArea.setCurrRect(kBoolRect);
284 displayArea.setDebugCases(null);
285 displayArea.setCurrEmpties(answer);
286 displayArea.setDebugInfo( ""+ answer.size() );
287 displayArea.repaint();
288
289 Thread.sleep(125);
290 }
291
292 // initialize the boolean field to random values, and load 1,1 empties into cache
293 void init() {
294 for(int i = 0; i < boolSpace.length; i+=1) {
295 for(int ii = 0; ii < boolSpace[i].length; ii+=1) {
296 boolean val = (rand.nextInt(100)<= kBooleanDensity);
297 boolSpace[i][ii] = val;
298
299 if (!val) {
300 Rectangle r = new Rectangle(i,ii,1,1);
301 Vector<Rectangle> v = new Vector<Rectangle>();
302 v.add(r);
303 cache.put(r, v);
304 }
305 }
306 }
307 }
308
309 // text display of boolean field
310 void displayRaw() {
311 System.out.println();
312 for(int i = 0; i < boolSpace.length; i+=1) {
313 for(int ii = 0; ii < boolSpace[i].length; ii+=1) {
314 System.out.print( boolSpace[i][ii] ? " " : "X" );
315 }
316 System.out.println();
317 }
318 }
319
320
321 // return an OK fracture point, or null if rectangle is empty
322 // algorithm is correct for any fracture point, but will converge faster for central points
323 Point split(Rectangle r) {
324 Point result = null;
325
326 int midx = r.x + r.width/2;
327 int midy = r.y + r.height/2;
328 int score = Integer.MAX_VALUE;
329
330 for(int xoff = 0; (xoff < r.width); xoff+=1) {
331 for(int yoff = 0; (yoff < r.height); yoff+=1) {
332 int x = r.x + xoff;
333 int y = r.y + yoff;
334 displayArea.setCurrPoint( new Point(x,y));
335
336 if (boolSpace[x][y] ) {
337 int newscore = (x-midx)*(x-midx)+(y-midy)*(y-midy);
338 if (newscore < score) {
339 score = newscore;
340 result = new Point(x,y);
341 }
342 }
343 }
344 }
345
346 return result;
347 }
348
349 Vector<Rectangle> findEmptyRects( Rectangle r, int depth) throws Exception {
350 debug( depth, "findEmptyRects " + show(r));
351 displayArea.setCurrEmpties(null);
352 displayArea.setCurrRect(r);
353
354 if (r.width <= 0 || r.height <= 0) {
355 debug( depth, "Unexpected rectagle :" + r);
356 return null ;
357 }
358
359 if ( cache.containsKey(r) ) {
360 debug( depth, "C :" + show(r) + "--" + show( cache.get(r)));
361 return cache.get(r);
362 }
363
364 if (r.width == 1 && r.height == 1) {
365 debug( depth, "F :" + show(r) + "--");
366 assertTrue( boolSpace[r.x][r.y]);
367 return null;
368 }
369
370 // figure it out recursively
371 Vector<Rectangle> empties = new Vector<Rectangle>();
372
373 Point p = split( r );
374 displayArea.setCurrPoint(p);
375
376 if (p == null) {
377 debug( depth, "S :" + show(r) + "--" + show(r));
378 empties.add(r);
379 }
380 else {
381 debug( depth, "point :" + p.x + " "+ p.y);
382
383 Vector<Rectangle> bestEmpties = null;
384 // iterate through the 8 possible cases
385 for (int kind =0; kind< 8; kind++) {
386 debug( depth, "case :" + kind);
387 Vector<Rectangle> caseRects = divideRectForSubcase(r, p, kind);
388 displayArea.setCurrRect(r);
389 displayArea.setCurrEmpties(null);
390 displayArea.setDebugInfo(""+caseRects.size());
391 displayArea.setDebugCases(caseRects);
392
393 Vector<Rectangle> caseEmpties = new Vector<Rectangle>();
394 for ( Rectangle caseRect : caseRects) {
395 Vector<Rectangle> subEmpties = findEmptyRects( caseRect, depth+1 );
396 if (subEmpties != null) {
397 caseEmpties.addAll(subEmpties);
398 }
399 }
400 displayArea.setCurrEmpties(caseEmpties);
401 debug( depth, "totals :" + caseEmpties.size());
402
403
404 if ( (bestEmpties == null) || (bestEmpties.size() > caseEmpties.size())) {
405 debug( depth, "new best! :" + caseEmpties.size());
406 displayArea.setCurrEmpties(caseEmpties);
407 bestEmpties = caseEmpties;
408 }
409
410 if (caseRects.size() <= 2) {
411 break; // simple case, so exit early
412 }
413 }
414
415 debug(depth, "R : " + r + "--"+show(bestEmpties));
416 empties = bestEmpties;
417
418 }
419
420 cache.put(r, empties);
421 return empties;
422 }
423
424
425 Vector<Rectangle> divideRectForSubcase(Rectangle r, Point p, int i ) {
426 Vector<Rectangle> fullCase = new Vector<Rectangle>();
427
428 int topHeight = p.y - r.y;
429 int botHeight = (r.height - topHeight) -1;
430 int leftWidth = p.x - r.x;
431 int rightWidth = (r.width - leftWidth) -1;
432
433 switch(i) {
434 case 0:
435 fullCase.add(new Rectangle( r.x, r.y, r.width, topHeight));
436 fullCase.add(new Rectangle( r.x, p.y+1, r.width, botHeight));
437 fullCase.add(new Rectangle( r.x, p.y, leftWidth, 1));
438 fullCase.add(new Rectangle( p.x+1, p.y, rightWidth, 1));
439 break;
440 case 1:
441 fullCase.add(new Rectangle( r.x, r.y, leftWidth, r.height));
442 fullCase.add(new Rectangle( p.x, r.y, 1, topHeight));
443 fullCase.add(new Rectangle( p.x+1, r.y, rightWidth, r.height));
444 fullCase.add(new Rectangle( p.x, p.y+1, 1, botHeight));
445 break;
446 case 2:
447 fullCase.add(new Rectangle( r.x, r.y, leftWidth, topHeight+1));
448 fullCase.add(new Rectangle( p.x, r.y, 1, topHeight));
449 fullCase.add(new Rectangle( r.x, p.y+1, r.width, botHeight));
450 fullCase.add(new Rectangle( p.x+1, r.y, rightWidth, topHeight+1));
451 break;
452 case 3:
453 fullCase.add(new Rectangle( r.x, r.y, leftWidth, r.height));
454 fullCase.add(new Rectangle( p.x, r.y, rightWidth+1, topHeight));
455 fullCase.add(new Rectangle( p.x, p.y+1, rightWidth+1, botHeight));
456 fullCase.add(new Rectangle( p.x+1, p.y, rightWidth, 1));
457 break;
458 case 4:
459 fullCase.add(new Rectangle( r.x, r.y, r.width, topHeight));
460 fullCase.add(new Rectangle( r.x, p.y, leftWidth, botHeight+1));
461 fullCase.add(new Rectangle( p.x, p.y+1, 1, botHeight));
462 fullCase.add(new Rectangle( p.x+1, p.y, rightWidth, botHeight+1));
463 break;
464 case 5:
465 fullCase.add(new Rectangle( r.x, r.y, leftWidth+1, topHeight));
466 fullCase.add(new Rectangle( r.x, p.y, leftWidth, 1));
467 fullCase.add(new Rectangle( r.x, p.y+1, leftWidth+1, botHeight));
468 fullCase.add(new Rectangle( p.x+1, r.y, rightWidth, r.height));
469 break;
470 case 6:
471 fullCase.add(new Rectangle( r.x, r.y, leftWidth+1, topHeight));
472 fullCase.add(new Rectangle( r.x, p.y, leftWidth, botHeight+1));
473 fullCase.add(new Rectangle( p.x, p.y+1, rightWidth+1, botHeight));
474 fullCase.add(new Rectangle( p.x+1, r.y, rightWidth, topHeight+1));
475 break;
476 case 7:
477 fullCase.add(new Rectangle( r.x, r.y, leftWidth, topHeight+1));
478 fullCase.add(new Rectangle( r.x, p.y+1, leftWidth+1, botHeight));
479 fullCase.add(new Rectangle( p.x, r.y, rightWidth+1, topHeight));
480 fullCase.add(new Rectangle( p.x+1, p.y, rightWidth, botHeight+1));
481 break;
482 /* ### note that there are 8! more cases.... ### */
483
484 default:
485 System.out.println("Unexpected case!"); break;
486 }
487
488
489 Vector<Rectangle> result = new Vector<Rectangle>();
490 for (Rectangle rr : fullCase ) {
491 if (rr.width > 0 && rr.height > 0) {
492 result.add(rr);
493 }
494 }
495 return result;
496
497 }
498
499 // debugging utilities
500 static void debug( int depth, String s) {
501 if (kDebug) {
502 for(int i= 0; i<depth; i+=1) {
503 System.out.print("\t");
504 System.out.println(s);
505 }
506 }
507 }
508
509 static String show( Rectangle r) {
510 return "["+r.x+","+r.y+" "+r.width+"x"+r.height+"]";
511 }
512
513 static String show( Vector<Rectangle> rects) {
514 String result = "" + rects.size() + " ";
515 for( Rectangle r : rects) {
516 result = result + " " +show(r);
517 }
518 return result;
519 }
520
521
522 // boilerplate for running as a JUnit test
523 public static Test suite() {
524 return new TestSuite(CollectionStress01.class);
525 }
526
527 public static void main (String[] args) throws RuntimeException {
528 TestResult tr = junit.textui.TestRunner.run(suite());
529 if((tr.errorCount() != 0) || (tr.failureCount() != 0)) {
530 throw new RuntimeException("### Unexpected JUnit errors or failures.");
531 }
532 }
533 }
534