Source Code Cross Referenced for OrthogonalSearchRouterCore.java in  » IDE-Netbeans » api » org » netbeans » modules » visual » router » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » IDE Netbeans » api » org.netbeans.modules.visual.router 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


001:        /*
002:         * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003:         *
004:         * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005:         *
006:         * The contents of this file are subject to the terms of either the GNU
007:         * General Public License Version 2 only ("GPL") or the Common
008:         * Development and Distribution License("CDDL") (collectively, the
009:         * "License"). You may not use this file except in compliance with the
010:         * License. You can obtain a copy of the License at
011:         * http://www.netbeans.org/cddl-gplv2.html
012:         * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013:         * specific language governing permissions and limitations under the
014:         * License.  When distributing the software, include this License Header
015:         * Notice in each file and include the License file at
016:         * nbbuild/licenses/CDDL-GPL-2-CP.  Sun designates this
017:         * particular file as subject to the "Classpath" exception as provided
018:         * by Sun in the GPL Version 2 section of the License file that
019:         * accompanied this code. If applicable, add the following below the
020:         * License Header, with the fields enclosed by brackets [] replaced by
021:         * your own identifying information:
022:         * "Portions Copyrighted [year] [name of copyright owner]"
023:         *
024:         * Contributor(s):
025:         *
026:         * The Original Software is NetBeans. The Initial Developer of the Original
027:         * Software is Sun Microsystems, Inc. Portions Copyright 1997-2007 Sun
028:         * Microsystems, Inc. All Rights Reserved.
029:         *
030:         * If you wish your version of this file to be governed by only the CDDL
031:         * or only the GPL Version 2, indicate your decision by adding
032:         * "[Contributor] elects to include this software in this distribution
033:         * under the [CDDL or GPL Version 2] license." If you do not indicate a
034:         * single choice of license, a recipient has the option to distribute
035:         * your version of this file under either the CDDL, the GPL Version 2 or
036:         * to extend the choice of license to its licensees as provided above.
037:         * However, if you add GPL Version 2 code and therefore, elected the GPL
038:         * Version 2 license, then the option applies only if the new code is
039:         * made subject to such option by the copyright holder.
040:         */
041:        package org.netbeans.modules.visual.router;
042:
043:        import org.netbeans.api.visual.anchor.Anchor;
044:        import org.netbeans.api.visual.widget.Scene;
045:
046:        import java.awt.*;
047:        import java.util.ArrayList;
048:        import java.util.Arrays;
049:        import java.util.List;
050:
051:        /**
052:         * @author David Kaspar
053:         */
054:        final class OrthogonalSearchRouterCore {
055:
056:            private static final int MAXIMAL_DEPTH = 5; // 6 is too slow for 10+ nodes and 10+ links
057:            private static final int CORNER_LENGTH = 200;
058:            private static final boolean UPDATE_COLLISION_LISTS = true; // set true for faster computation but not optimal results
059:            private static final boolean UPDATE_COLLISION_LISTS_REMOVE = true;
060:            static final boolean IGNORE_LINKS_WITH_ACTUAL_PORTS = false; // cause links to try to merge as a bus, multilinks are merged too
061:            private static final boolean OPTIMALIZE_REGIONS = false;
062:
063:            private Scene scene;
064:            private ArrayList<Rectangle> verticalCollisions;
065:            private ArrayList<Rectangle> horizontalCollisions;
066:            private Point sourcePoint;
067:            private Anchor.Direction sourceDirection;
068:            private Point targetPoint;
069:            private Anchor.Direction targetDirection;
070:
071:            private Point sourceBoundaryPoint;
072:            private Point targetBoundaryPoint;
073:            private final OrthogonalSearchRouterRegion[] regions = new OrthogonalSearchRouterRegion[MAXIMAL_DEPTH + 1];
074:
075:            private Point[] bestControlPoints;
076:            private int bestControlPointsPrice;
077:
078:            public OrthogonalSearchRouterCore(Scene scene,
079:                    ArrayList<Rectangle> verticalCollisions,
080:                    ArrayList<Rectangle> horizontalCollisions,
081:                    Point sourcePoint, Anchor.Direction sourceDirection,
082:                    Point targetPoint, Anchor.Direction targetDirection) {
083:                this .scene = scene;
084:                this .verticalCollisions = verticalCollisions;
085:                this .horizontalCollisions = horizontalCollisions;
086:                this .sourcePoint = sourcePoint;
087:                this .sourceDirection = sourceDirection;
088:                this .targetPoint = targetPoint;
089:                this .targetDirection = targetDirection;
090:            }
091:
092:            public OrthogonalSearchRouter.Solution route() {
093:                sourceBoundaryPoint = findBoundaryPoint(sourcePoint,
094:                        sourceDirection);
095:                targetBoundaryPoint = findBoundaryPoint(targetPoint,
096:                        targetDirection);
097:
098:                search(new OrthogonalSearchRouterRegion(
099:                        /*null, */sourceBoundaryPoint.x,
100:                        sourceBoundaryPoint.y, 0, 0, sourceDirection, 0));
101:
102:                return bestControlPoints != null ? new OrthogonalSearchRouter.Solution(
103:                        bestControlPointsPrice, Arrays
104:                                .asList(bestControlPoints))
105:                        : null;
106:            }
107:
108:            private Point findBoundaryPoint(Point point,
109:                    Anchor.Direction direction) {
110:                point = new Point(point);
111:                ArrayList<Rectangle> collisions;
112:                switch (direction) {
113:                case LEFT:
114:                case RIGHT:
115:                    collisions = horizontalCollisions;
116:                    break;
117:                case BOTTOM:
118:                case TOP:
119:                    collisions = verticalCollisions;
120:                    break;
121:                default:
122:                    return point;
123:                }
124:
125:                boolean changed = true;
126:                while (changed) {
127:                    changed = false;
128:
129:                    switch (direction) {
130:                    case LEFT:
131:                        for (Rectangle rectangle : collisions) {
132:                            if (rectangle.contains(point)) {
133:                                point.x = rectangle.x - 1;
134:                                changed = true;
135:                            }
136:                        }
137:                        break;
138:                    case RIGHT:
139:                        for (Rectangle rectangle : collisions) {
140:                            if (rectangle.contains(point)) {
141:                                point.x = rectangle.x + rectangle.width;
142:                                changed = true;
143:                            }
144:                        }
145:                        break;
146:                    case BOTTOM:
147:                        for (Rectangle rectangle : collisions) {
148:                            if (rectangle.contains(point)) {
149:                                point.y = rectangle.y + rectangle.height;
150:                                changed = true;
151:                            }
152:                        }
153:                        break;
154:                    case TOP:
155:                        for (Rectangle rectangle : collisions) {
156:                            if (rectangle.contains(point)) {
157:                                point.y = rectangle.y - 1;
158:                                changed = true;
159:                            }
160:                        }
161:                        break;
162:                    }
163:                }
164:                return point;
165:            }
166:
167:            private void search(OrthogonalSearchRouterRegion region) {
168:                Rectangle inter = region.intersection(scene.getMaximumBounds());
169:                region = new OrthogonalSearchRouterRegion(inter.x, inter.y,
170:                        inter.width, inter.height, region.getDirection(),
171:                        region.getDepth());
172:
173:                if (region.width < 0 || region.height < 0)
174:                    return;
175:                assert region.x >= OrthogonalSearchRouterRegion.MIN_INT_REGION;
176:                assert region.y >= OrthogonalSearchRouterRegion.MIN_INT_REGION;
177:                assert region.x + region.width <= OrthogonalSearchRouterRegion.MAX_INT_REGION;
178:                assert region.y + region.height <= OrthogonalSearchRouterRegion.MAX_INT_REGION;
179:                //        System.out.println ("REG: " + region);
180:
181:                int depth = region.getDepth();
182:                if (depth >= MAXIMAL_DEPTH) // too deeply
183:                    return;
184:
185:                region.extendToInfinity();
186:                regions[depth] = region;
187:
188:                List<Rectangle> collisions = region.isHorizontal() ? horizontalCollisions
189:                        : verticalCollisions;
190:
191:                ArrayList<OrthogonalSearchRouterRegion> subRegions = region
192:                        .parseSubRegions(collisions);
193:
194:                boolean updatedCollissions = false;
195:                if (!region.isEmpty()) {
196:                    //            addRectangle (link, region);
197:                    if (UPDATE_COLLISION_LISTS) {
198:                        Rectangle updateCollisionsRect = new Rectangle(region);
199:                        horizontalCollisions.add(updateCollisionsRect);
200:                        verticalCollisions.add(updateCollisionsRect);
201:                        updatedCollissions = true;
202:                    }
203:                }
204:
205:                if (region.containsInsideEdges(targetBoundaryPoint)) {
206:                    // TODO - not true - point could lay on right or bottom edge ! - this is not checked yet
207:                    //            System.out.println ("FOUND");
208:                    constructControlPoints(depth);
209:                    // TODO
210:                    // if not correct direction then
211:                    //   reuse the same pathRegion rectangle and correct the direction
212:                    // return the path as the best
213:                } else {
214:
215:                    //        try left and/or right
216:                    if (region.getLength() > 0) {
217:                        search(region.cloneWithCounterClockwiseEdge());
218:                        search(region.cloneWithClockwiseEdge());
219:                    }
220:
221:                    //        tryNearestSubRegion and maybeOthersSubRegions
222:                    if (!subRegions.isEmpty()) {
223:                        //                OrthogonalLinkRouterRegion r0 = (OrthogonalLinkRouterRegion) subRegions.get (0);
224:                        //                if (subRegions.size () > 1) {
225:                        //                    int dist0 = r0.getDistance (targetBoundaryPoint);
226:                        //                    final OrthogonalLinkRouterRegion r1 = (OrthogonalLinkRouterRegion) subRegions.get (subRegions.size () - 1);
227:                        //                    int dist1 = r1.getDistance (targetBoundaryPoint);
228:                        //                    if (dist1 < dist0)
229:                        //                        r0 = r1;
230:                        //                    search (r0);
231:                        for (OrthogonalSearchRouterRegion subRegion : subRegions) {
232:                            //                        if (subRegion != r0)
233:                            search(subRegion);
234:                        }
235:                        //                } else
236:                        //                    search (r0);
237:                    }
238:                }
239:
240:                if (updatedCollissions && UPDATE_COLLISION_LISTS_REMOVE) {
241:                    horizontalCollisions
242:                            .remove(horizontalCollisions.size() - 1);
243:                    verticalCollisions.remove(verticalCollisions.size() - 1);
244:                }
245:            }
246:
247:            private void constructControlPoints(int depth) {
248:                Anchor.Direction desiredDirection;
249:                switch (targetDirection) {
250:                case LEFT:
251:                    desiredDirection = Anchor.Direction.RIGHT;
252:                    break;
253:                case RIGHT:
254:                    desiredDirection = Anchor.Direction.LEFT;
255:                    break;
256:                case TOP:
257:                    desiredDirection = Anchor.Direction.BOTTOM;
258:                    break;
259:                case BOTTOM:
260:                    desiredDirection = Anchor.Direction.TOP;
261:                    break;
262:                default:
263:                    throw new IllegalArgumentException();
264:                }
265:                if (desiredDirection != regions[depth].getDirection()) {
266:                    final OrthogonalSearchRouterRegion region = regions[depth];
267:                    depth++;
268:                    regions[depth] = new OrthogonalSearchRouterRegion(region.x,
269:                            region.y, region.width, region.height,
270:                            desiredDirection, depth);
271:                }
272:
273:                Point[] controlPoints = new Point[depth + 4];
274:                controlPoints[0] = new Point(sourcePoint);
275:                controlPoints[1] = new Point(sourceBoundaryPoint);
276:                for (int a = 2; a < depth + 2; a++)
277:                    controlPoints[a] = new Point();
278:                controlPoints[depth + 2] = new Point(targetBoundaryPoint);
279:                controlPoints[depth + 3] = new Point(targetPoint);
280:
281:                for (int a = 0; a < depth; a++) {
282:                    final OrthogonalSearchRouterRegion region = regions[a];
283:                    Point previousPoint = controlPoints[a + 1];
284:                    Point currentPoint = controlPoints[a + 2];
285:                    if (region.isHorizontal()) {
286:                        int yy;
287:                        if (a > 0) {
288:                            final int y1 = region.y;
289:                            final int y2 = region.y + region.height;
290:                            if (y1 <= OrthogonalSearchRouterRegion.MIN_INT_REGION
291:                                    && y2 < OrthogonalSearchRouterRegion.MAX_INT_REGION)
292:                                yy = y2 - OrthogonalSearchRouter.SPACING_EDGE;
293:                            else if (y1 > OrthogonalSearchRouterRegion.MIN_INT_REGION
294:                                    && y2 >= OrthogonalSearchRouterRegion.MAX_INT_REGION)
295:                                yy = y1 + OrthogonalSearchRouter.SPACING_EDGE;
296:                            else
297:                                yy = region.y + region.height / 2;
298:                        } else
299:                            yy = previousPoint.y;
300:                        previousPoint.y = currentPoint.y = yy;
301:                    } else {
302:                        int xx;
303:                        if (a > 0) {
304:                            final int x1 = region.x;
305:                            final int x2 = region.x + region.width;
306:                            if (x1 <= OrthogonalSearchRouterRegion.MIN_INT_REGION
307:                                    && x2 < OrthogonalSearchRouterRegion.MAX_INT_REGION)
308:                                xx = x2 - OrthogonalSearchRouter.SPACING_EDGE;
309:                            else if (x1 > OrthogonalSearchRouterRegion.MIN_INT_REGION
310:                                    && x2 >= OrthogonalSearchRouterRegion.MAX_INT_REGION)
311:                                xx = x1 + OrthogonalSearchRouter.SPACING_EDGE;
312:                            else
313:                                xx = region.x + region.width / 2;
314:                        } else
315:                            xx = previousPoint.x;
316:                        previousPoint.x = currentPoint.x = xx;
317:                    }
318:                }
319:
320:                if (regions[depth].isHorizontal())
321:                    controlPoints[depth + 1].y = controlPoints[depth + 2].y;
322:                else
323:                    controlPoints[depth + 1].x = controlPoints[depth + 2].x;
324:
325:                if (OPTIMALIZE_REGIONS) {
326:                    for (int a = depth; a > 0; a--) {
327:                        //                if (infiniteY[a]) {
328:                        final int newY = controlPoints[a + 3].y;
329:                        final OrthogonalSearchRouterRegion regionY = regions[a];
330:                        final OrthogonalSearchRouterRegion regionY1 = regions[a - 1];
331:                        if (newY >= regionY.y
332:                                && newY < regionY.y + regionY.height
333:                                && newY >= regionY1.y
334:                                && newY < regionY1.y + regionY1.height)
335:                            controlPoints[a + 1].y = controlPoints[a + 2].y = newY;
336:                        //                }
337:                        //                if (infiniteX[a]) {
338:                        final int newX = controlPoints[a + 3].x;
339:                        final OrthogonalSearchRouterRegion regionX = regions[a];
340:                        final OrthogonalSearchRouterRegion regionX1 = regions[a - 1];
341:                        if (newX >= regionX.x
342:                                && newX < regionX.x + regionX.width
343:                                && newX >= regionX1.x
344:                                && newX < regionX1.x + regionX1.width)
345:                            controlPoints[a + 1].x = controlPoints[a + 2].x = newX;
346:                        //                }
347:                    }
348:                }
349:
350:                int controlPointsLength = removeDuplicateControlPoints(controlPoints);
351:
352:                int price = calculatePrice(controlPointsLength, controlPoints);
353:
354:                if (bestControlPoints == null || bestControlPointsPrice > price) {
355:                    if (controlPointsLength < controlPoints.length) {
356:                        bestControlPoints = new Point[controlPointsLength];
357:                        System.arraycopy(controlPoints, 0, bestControlPoints,
358:                                0, controlPointsLength);
359:                    } else
360:                        bestControlPoints = controlPoints;
361:                    bestControlPointsPrice = price;
362:                    //            System.out.println ("BEST");
363:                    // DEBUG
364:                    //            if (SHOW_DEBUG_REGIONS) {
365:                    //                clearRectangle ();
366:                    //                for (int i = 0; i <= depth; i++)
367:                    //                    addRectangle (regions[i]);
368:                    //            }
369:                }
370:            }
371:
372:            private int removeDuplicateControlPoints(Point[] controlPoints) {
373:                int newPointsLength = 0;
374:                for (int a = 1; a < controlPoints.length - 1; a++) {
375:                    Point p0 = controlPoints[newPointsLength];
376:                    Point p1 = controlPoints[a];
377:                    Point p2 = controlPoints[a + 1];
378:
379:                    if (p0.x == p1.x && p1.x == p2.x)
380:                        continue;
381:                    if (p0.y == p1.y && p1.y == p2.y)
382:                        continue;
383:
384:                    newPointsLength++;
385:                    if (newPointsLength != a)
386:                        controlPoints[newPointsLength] = p1;
387:                }
388:                newPointsLength++;
389:                if (newPointsLength < controlPoints.length - 1)
390:                    controlPoints[newPointsLength++] = controlPoints[controlPoints.length - 1];
391:                return newPointsLength;
392:            }
393:
394:            private int calculatePrice(int controlPointsLength,
395:                    Point[] controlPoints) {
396:                int price = 0;
397:                for (int a = 1; a < controlPointsLength; a++) {
398:                    final Point p1 = controlPoints[a - 1];
399:                    final Point p2 = controlPoints[a];
400:                    price += Math.abs(p2.y - p1.y) + Math.abs(p2.x - p1.x)
401:                            + CORNER_LENGTH;
402:                }
403:                if (controlPointsLength > 0) {
404:                    int average = price / controlPointsLength;
405:                    int diff = 0;
406:                    for (int a = 1; a < controlPointsLength; a++) {
407:                        final Point p1 = controlPoints[a - 1];
408:                        final Point p2 = controlPoints[a];
409:                        diff += Math.abs(Math.abs(p2.y - p1.y)
410:                                + Math.abs(p2.x - p1.x) - average);
411:                    }
412:                    diff /= controlPointsLength;
413:                    price += diff;
414:                }
415:                //        price += depth * CORNER_LENGTH;
416:                return price;
417:            }
418:
419:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.