← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/electric/jaunty

« back to all changes in this revision

Viewing changes to com/sun/electric/tool/generator/layout/fill/StitchFillJob.java

  • Committer: Bazaar Package Importer
  • Author(s): Onkar Shinde
  • Date: 2009-01-08 02:05:08 UTC
  • mfrom: (1.1.2 upstream) (3.1.4 sid)
  • Revision ID: james.westby@ubuntu.com-20090108020508-0h3li7zt9mu5gf0i
Tags: 8.08-1
New upstream version.

Show diffs side-by-side

added added

removed removed

Lines of Context:
com/sun/electric/tool/generator/layout/fill/StitchFillJob.java
 
1
/* -*- tab-width: 4 -*-
 
2
 *
 
3
 * Electric(tm) VLSI Design System
 
4
 *
 
5
 * File: StitchFillJob.java
 
6
 *
 
7
 * Copyright (c) 2008 Sun Microsystems and Static Free Software
 
8
 *
 
9
 * Electric(tm) is free software; you can redistribute it and/or modify
 
10
 * it under the terms of the GNU General Public License as published by
 
11
 * the Free Software Foundation; either version 3 of the License, or
 
12
 * (at your option) any later version.
 
13
 *
 
14
 * Electric(tm) is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 * GNU General Public License for more details.
 
18
 *
 
19
 * You should have received a copy of the GNU General Public License
 
20
 * along with Electric(tm); see the file COPYING.  If not, write to
 
21
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 
22
 * Boston, Mass 02111-1307, USA.
 
23
 */
 
24
package com.sun.electric.tool.generator.layout.fill;
 
25
 
 
26
import com.sun.electric.tool.Job;
 
27
import com.sun.electric.tool.JobException;
 
28
import com.sun.electric.tool.user.CellChangeJobs;
 
29
import com.sun.electric.tool.user.ExportChanges;
 
30
import com.sun.electric.tool.user.ui.WindowFrame;
 
31
import com.sun.electric.tool.routing.*;
 
32
import com.sun.electric.database.hierarchy.Cell;
 
33
import com.sun.electric.database.hierarchy.Export;
 
34
import com.sun.electric.database.hierarchy.Library;
 
35
import com.sun.electric.database.hierarchy.View;
 
36
import com.sun.electric.database.topology.*;
 
37
import com.sun.electric.database.geometry.EPoint;
 
38
import com.sun.electric.database.geometry.DBMath;
 
39
import com.sun.electric.database.geometry.PolyBase;
 
40
import com.sun.electric.database.geometry.Orientation;
 
41
import com.sun.electric.database.prototype.NodeProto;
 
42
import com.sun.electric.database.prototype.PortCharacteristic;
 
43
import com.sun.electric.database.prototype.PortProto;
 
44
import com.sun.electric.database.network.Network;
 
45
import com.sun.electric.database.network.Netlist;
 
46
import com.sun.electric.technology.Layer;
 
47
import com.sun.electric.technology.ArcProto;
 
48
import com.sun.electric.technology.Technology;
 
49
import com.sun.electric.technology.PrimitiveNode;
 
50
 
 
51
import java.util.*;
 
52
import java.awt.geom.Rectangle2D;
 
53
import java.awt.geom.Area;
 
54
import java.awt.geom.Point2D;
 
55
 
 
56
/**
 
57
 * Fill Generator working on unconnected arcs
 
58
 * User: Gilda Garreton
 
59
 * Date: Nov 4, 2008
 
60
 */
 
61
public class StitchFillJob extends Job
 
62
{
 
63
    private Cell topCell;
 
64
    private Library outLibrary;
 
65
    private List<Cell> generatedCells = new ArrayList<Cell>();
 
66
 
 
67
//    private static final boolean doFill = false;
 
68
 
 
69
    public StitchFillJob(Cell cell, Library lib, boolean doItNow)
 
70
    {
 
71
        super("Fill generator job", null, Type.CHANGE, null, null, Priority.USER);
 
72
        this.topCell = cell;
 
73
        this.outLibrary = lib;
 
74
 
 
75
        if (doItNow) // call from regressions
 
76
        {
 
77
            try
 
78
            {
 
79
                if (doIt())
 
80
                    terminateOK();
 
81
 
 
82
            } catch (JobException e)
 
83
            {
 
84
                e.printStackTrace();
 
85
            }
 
86
        }
 
87
        else
 
88
            startJob(); // queue the job
 
89
    }
 
90
 
 
91
    public boolean doIt() throws JobException
 
92
    {
 
93
        Point2D center = new Point2D.Double(0, 0);
 
94
 
 
95
        // Get cells from EditWindows
 
96
        if (topCell == null)
 
97
        {
 
98
            Technology tech = null;
 
99
            List<NodeInst> fillCells = new ArrayList<NodeInst>();
 
100
            List<Geometric> fillGeoms = new ArrayList<Geometric>();
 
101
            String fillCellName = "NewFill{lay}";
 
102
 
 
103
            Library lib = Library.getCurrent();
 
104
            if (lib == null)
 
105
            {
 
106
                System.out.println("No current library available.");
 
107
                return false;
 
108
            }
 
109
 
 
110
            
 
111
            Cell oldCell = lib.findNodeProto(fillCellName);
 
112
            // Delete previous version
 
113
            if (oldCell != null)
 
114
                oldCell.kill();
 
115
            Cell newCell = Cell.makeInstance(lib, fillCellName);
 
116
 
 
117
            for (Iterator<WindowFrame> itW = WindowFrame.getWindows(); itW.hasNext();)
 
118
            {
 
119
                WindowFrame w = itW.next();
 
120
                Cell c = w.getContent().getCell();
 
121
 
 
122
                if (c == null)
 
123
                {
 
124
                    System.out.println("No cell in window '" + w.getTitle() + "'");
 
125
                    continue;
 
126
                }
 
127
                if (c.getView() != View.LAYOUT)
 
128
                {
 
129
                    System.out.println("Cell '" + c + "' is not a layout cell");
 
130
                    continue;
 
131
                }
 
132
 
 
133
                Technology t = c.getTechnology();
 
134
                if (tech == null) tech = t;
 
135
                else if (tech != t)
 
136
                    System.out.println("Mixing technologies in fill generator: " +
 
137
                        tech.getTechName() + " " + t.getTechName());
 
138
 
 
139
                NodeInst ni = NodeInst.makeInstance(c, center, c.getDefWidth(), c.getDefHeight(), newCell);
 
140
                fillCells.add(ni);
 
141
                fillGeoms.add(ni);
 
142
            }
 
143
            // actual fill gen
 
144
            doTheJob(newCell, fillCellName, fillCells, fillGeoms, null, false, this);
 
145
            return true; // done at this point
 
146
        }
 
147
 
 
148
        String[] instructions = topCell.getTextViewContents();
 
149
 
 
150
        if (instructions == null)
 
151
        {
 
152
            System.out.println("No fill instructions found.");
 
153
            return false;
 
154
        }
 
155
        for (String line : instructions)
 
156
        {
 
157
            if (line.startsWith("//"))
 
158
                continue; // commented line
 
159
            
 
160
            StringTokenizer parse = new StringTokenizer(line, ":", false);
 
161
            int count = 0;
 
162
            String fillCellName = null, rest = null;
 
163
 
 
164
            while (parse.hasMoreTokens())
 
165
            {
 
166
                assert(count < 2);
 
167
                String value = parse.nextToken();
 
168
                switch (count)
 
169
                {
 
170
                    case 0: fillCellName = value;
 
171
                        break;
 
172
                    default:
 
173
                        rest = value;
 
174
                        break;
 
175
                }
 
176
                count++;
 
177
            }
 
178
            if (fillCellName == null) continue; // no parsing matching
 
179
 
 
180
            // getting possible options like "w" or "2x4"
 
181
            int index = fillCellName.indexOf("(");
 
182
            boolean wideOption = false;
 
183
            List<TileInfo> tileList = new ArrayList<TileInfo>();
 
184
            
 
185
            if (index != -1)
 
186
            {
 
187
                // Getting options like (W)
 
188
                String options = fillCellName.substring(index);
 
189
                fillCellName = fillCellName.substring(0, index);
 
190
                parse = new StringTokenizer(options, "(), ", false);
 
191
                while (parse.hasMoreTokens())
 
192
                {
 
193
                    String option = parse.nextToken();
 
194
                    String lowerCase = option.toLowerCase();
 
195
                    // wide option where exports are added in lowest layer
 
196
                    if (lowerCase.equals("w"))
 
197
                    {
 
198
                        wideOption = true;
 
199
                        fillCellName += "W";
 
200
                    }
 
201
                    else if (lowerCase.contains("x"))
 
202
                    {
 
203
                        index = lowerCase.indexOf("x");
 
204
                        String str = lowerCase.substring(0, index);
 
205
                        int x = Integer.valueOf(str);
 
206
                        str = lowerCase.substring(index+1, lowerCase.length());
 
207
                        int y = Integer.valueOf(str);
 
208
                        // tile information
 
209
                        TileInfo tile = new TileInfo(x, y);
 
210
                        tileList.add(tile);
 
211
                    }
 
212
                }
 
213
            }
 
214
 
 
215
//            Library lib = topCell.getLibrary();
 
216
 
 
217
            // extracting fill subcells
 
218
            parse = new StringTokenizer(rest, " ,", false);
 
219
            String newName = fillCellName+"{lay}";
 
220
            Cell oldCell = outLibrary.findNodeProto(newName);
 
221
            // Delete previous version
 
222
            if (oldCell != null)
 
223
            {
 
224
                oldCell.kill();
 
225
            }
 
226
            Cell newCell = Cell.makeInstance(outLibrary, newName);
 
227
            Technology tech = null;
 
228
            List<NodeInst> fillCells = new ArrayList<NodeInst>();
 
229
            List<Geometric> fillGeoms = new ArrayList<Geometric>();
 
230
 
 
231
            while (parse.hasMoreTokens())
 
232
            {
 
233
                String fillCell = parse.nextToken();
 
234
                index = fillCell.indexOf("("); // options like (I)
 
235
                boolean instanceFlag = false;
 
236
                if (index != -1)
 
237
                {
 
238
                    instanceFlag = fillCell.toLowerCase().indexOf("(i") != -1; // only (I) option for now
 
239
                    fillCell = fillCell.substring(0, index);
 
240
                }
 
241
                Cell c = topCell.getLibrary().findNodeProto(fillCell); // +"{lay}");
 
242
 
 
243
                if (c == null)
 
244
                {
 
245
                    System.out.println("Cell '" + fillCell + "' does not exist");
 
246
                    continue;
 
247
                }
 
248
                if (c.getView() != View.LAYOUT)
 
249
                {
 
250
                    System.out.println("Cell '" + c + "' is not a layout cell");
 
251
                    continue;
 
252
                }
 
253
                Technology t = c.getTechnology();
 
254
 
 
255
                if (tech == null) tech = t;
 
256
                else if (tech != t)
 
257
                    System.out.println("Mixing technologies in fill generator: " + tech.getTechName() + " " + t.getTechName());
 
258
                NodeInst ni = NodeInst.makeInstance(c, center, c.getDefWidth(), c.getDefHeight(), newCell);
 
259
                if (!instanceFlag)
 
260
                    fillCells.add(ni);
 
261
                fillGeoms.add(ni);
 
262
            }
 
263
            newCell.setTechnology(tech);
 
264
            generatedCells.add(newCell);
 
265
 
 
266
            // actual fill gen
 
267
            doTheJob(newCell, fillCellName, fillCells, fillGeoms, tileList, wideOption, this);
 
268
        }
 
269
        return true;
 
270
    }
 
271
 
 
272
    public List<Cell> getGeneratedCells() {return generatedCells;}
 
273
 
 
274
    /**
 
275
     * Method that executes the different functions to get the tool working
 
276
     * @param newCell
 
277
     * @param fillCellName
 
278
     * @param fillCells
 
279
     * @param fillGeoms
 
280
     * @param tileList
 
281
     * @param wideOption
 
282
     * @param job
 
283
     */
 
284
    private static void doTheJob(Cell newCell, String fillCellName, List<NodeInst> fillCells,
 
285
                                 List<Geometric> fillGeoms, List<TileInfo> tileList, boolean wideOption, Job job)
 
286
    {
 
287
        // Re-exporting
 
288
        ExportChanges.reExportNodes(newCell, fillGeoms, false, true, false, true);
 
289
//        if (!doFill) return;
 
290
 
 
291
        // Flatting subcells
 
292
        new CellChangeJobs.ExtractCellInstances(newCell, fillCells, Integer.MAX_VALUE, true, true);
 
293
 
 
294
        // generation of master fill
 
295
        generateFill(newCell, wideOption);
 
296
 
 
297
        // tiles generation. Flat generation for now
 
298
        generateTiles(newCell, fillCellName, tileList, job);
 
299
    }
 
300
 
 
301
    /**
 
302
     * Class to store tile information
 
303
     */
 
304
    private class TileInfo
 
305
    {
 
306
        int x, y; // size in x and y axes
 
307
 
 
308
        TileInfo(int a, int b)
 
309
        {
 
310
            x = a;
 
311
            y = b;
 
312
        }
 
313
    }
 
314
 
 
315
    /**
 
316
     * Method to generate tiles of a given cell according to the description provided.
 
317
     * The function will use the auto stitch tool so no hierarchy is expected.
 
318
     * @param template Cell to use as template
 
319
     * @param fillCellName Root name of the template cell
 
320
     * @param tileList List of dimensions to create
 
321
     * @param job Job running the task
 
322
     */
 
323
    private static void generateTiles(Cell template, String fillCellName, List<TileInfo> tileList, Job job)
 
324
    {
 
325
        if (tileList == null) return; // nothing to tile
 
326
        
 
327
        // tiles generation. Flat generation for now
 
328
        for (TileInfo info : tileList)
 
329
        {
 
330
            String newTileName = fillCellName + info.x + "x" + info.y + "{lay}";
 
331
            Cell newTile = Cell.makeInstance(template.getLibrary(), newTileName);
 
332
            // generate the array
 
333
            List<NodeInst> niList = new ArrayList<NodeInst>();
 
334
            Rectangle2D rect = template.getBounds();
 
335
            double width = rect.getWidth();
 
336
            double height = rect.getHeight();
 
337
            double xPos = 0, yPos;
 
338
 
 
339
            for (int i = 0; i < info.x; i++)
 
340
            {
 
341
                yPos = 0;
 
342
                for (int j = 0; j < info.y; j++)
 
343
                {
 
344
                    NodeInst newNi = NodeInst.makeInstance(template,
 
345
                    new Point2D.Double(xPos, yPos), width, height, newTile, Orientation.IDENT, null, 0);
 
346
                    niList.add(newNi);
 
347
                    yPos += height;
 
348
                }
 
349
                xPos += width;
 
350
            }
 
351
            AutoStitch.runAutoStitch(newTile, niList, null, job, null, null, true, true, true);
 
352
        }
 
353
    }
 
354
 
 
355
    /**
 
356
     * Main class to auto-stitch metal layers found in given cell
 
357
     * @param theCell Cell with the metal layer information
 
358
     * @param wideOption True if exports in the lowest layer will be added
 
359
     * @return True if auto-stitch ran without errors
 
360
     */
 
361
    private static boolean generateFill(Cell theCell, boolean wideOption)
 
362
    {                           
 
363
        InteractiveRouter router  = new SimpleWirer();
 
364
        List<Layer> listOfLayers = new ArrayList<Layer>(12);
 
365
 
 
366
        for (Iterator<Layer> itL = theCell.getTechnology().getLayers(); itL.hasNext(); )
 
367
        {
 
368
            Layer l = itL.next();
 
369
            if (!l.getFunction().isMetal()) continue;  // only metals
 
370
            listOfLayers.add(l);
 
371
        }
 
372
 
 
373
        Collections.sort(listOfLayers, Layer.layerSortByName);
 
374
                Map<ArcProto,Integer> arcsCreatedMap = new HashMap<ArcProto,Integer>();
 
375
                Map<NodeProto,Integer> nodesCreatedMap = new HashMap<NodeProto,Integer>();
 
376
        boolean evenHorizontal = true; // even metal layers are horizontal. Basic assumption
 
377
        List<Route> routeList = new ArrayList<Route>();
 
378
        Layer[] topLayers = new Layer[2];
 
379
        Layer bottomLayer = null;
 
380
        Map<String,Area> totalAreas = new HashMap<String,Area>();
 
381
 
 
382
        for (int i = 0; i < listOfLayers.size() - 1; i++)
 
383
        {
 
384
            Layer bottom = listOfLayers.get(i);
 
385
            boolean horizontal = isLayerHorizontal(bottom, evenHorizontal);
 
386
 
 
387
            List<ArcInst> arcs = getArcsInGivenLayer(theCell.getArcs(), horizontal, bottom, null, null);
 
388
            Layer top = listOfLayers.get(i+1);
 
389
            Map<String,Area> remainingGeos = new HashMap<String,Area>();
 
390
 
 
391
            for (ArcInst ai : arcs)
 
392
            {
 
393
                // Picking only 1 export and considering the root name`
 
394
                Netlist netlist = theCell.getNetlist(); // getting new version of netlist after every routing.
 
395
                String bottomName = getExportRootName(ai, netlist);
 
396
 
 
397
                if (bottomName == null) continue; // nothing to export
 
398
 
 
399
                List<PinsArcPair> pairs = new ArrayList<PinsArcPair>();
 
400
                Rectangle2D bounds = ai.getBounds();
 
401
                Area bottomA = new Area(bounds);
 
402
 
 
403
                if (bottomLayer == null || bottom == bottomLayer) // only for the bottom layer, the first one
 
404
                {
 
405
                    Area totalA = totalAreas.get(bottomName);
 
406
                    if (totalA == null)
 
407
                    {
 
408
                        totalA = new Area();
 
409
                        totalAreas.put(bottomName, totalA);
 
410
                    }
 
411
                    totalA.add(bottomA);
 
412
                }
 
413
                
 
414
                for(Iterator<RTBounds> it = theCell.searchIterator(bounds); it.hasNext(); )
 
415
                {
 
416
                    Geometric nGeom = (Geometric)it.next();
 
417
 
 
418
                    if (!(nGeom instanceof ArcInst))
 
419
                    {
 
420
                        continue; // only arcs
 
421
                    }
 
422
 
 
423
                    ArcInst nai = (ArcInst)nGeom;
 
424
 
 
425
                    // Checking arc orientation with respect to layer
 
426
                    // If the orientation is not correct, then ignore it
 
427
                    // Must be perpendicular to the reference layer (bottom)
 
428
                    if (!isArcAligned(nai, !horizontal))
 
429
                        continue;
 
430
 
 
431
                    Layer nl = nai.getProto().getLayer(0);
 
432
 
 
433
                    if (nl != top) continue; // ascending order is easy
 
434
 
 
435
                    String topName = getExportRootName(nai, netlist);
 
436
 
 
437
                    if (topName == null || !topName.equals(bottomName)) continue; // no export matching
 
438
 
 
439
                    Rectangle2D nBnds = nai.getBounds();
 
440
                    Area topA = new Area(nBnds);
 
441
                    topA.intersect(bottomA);
 
442
                    Rectangle2D resultBnd = topA.getBounds2D();
 
443
 
 
444
                    // checking for full overlap. If horizontal -> width must be 100%
 
445
                    boolean fullCoverageX = (horizontal) ? DBMath.areEquals(resultBnd.getWidth(), nBnds.getWidth()) :
 
446
                        DBMath.areEquals(resultBnd.getHeight(), nBnds.getHeight());
 
447
                    boolean fullCoverageY = (horizontal) ? DBMath.areEquals(resultBnd.getHeight(), bounds.getHeight()) :
 
448
                        DBMath.areEquals(resultBnd.getWidth(), bounds.getWidth());
 
449
 
 
450
                    if (!fullCoverageX || !fullCoverageY)
 
451
                    {
 
452
                        // adding to list of pieces of geometries
 
453
                        Area a = remainingGeos.get(bottomName);
 
454
                        if (a == null)
 
455
                        {
 
456
                            a = new Area();
 
457
                            remainingGeos.put(bottomName, a);
 
458
                        }
 
459
                        a.add(topA);
 
460
                        continue; // skipping this case
 
461
                    }
 
462
 
 
463
                    EPoint insert = new EPoint(resultBnd.getCenterX(), resultBnd.getCenterY());
 
464
                    pairs.add(new PinsArcPair(nai, insert, resultBnd));
 
465
                }
 
466
 
 
467
                Collections.sort(pairs, pinsArcSort);
 
468
                ArcInst mostLeft = ai;
 
469
                routeList.clear();
 
470
 
 
471
                if (bottomLayer == null)
 
472
                    bottomLayer = bottom;
 
473
 
 
474
                // Mark the layer as possible one of the top ones
 
475
                if (!pairs.isEmpty())
 
476
                {
 
477
                    topLayers[0] = bottom;
 
478
                    topLayers[1] = top;
 
479
                }
 
480
 
 
481
                Area a = remainingGeos.get(bottomName);
 
482
                for (PinsArcPair pair : pairs)
 
483
                {
 
484
                    //SplitContainter bottomSplit = splitArcAtPoint(mostLeft, pair.insert);
 
485
                    //SplitContainter topSplit = splitArcAtPoint(pair.topArc, pair.insert);
 
486
                    Route r = router.planRoute(theCell,  mostLeft, pair.topArc, pair.insert, null, true, true, pair.cut);
 
487
                    //mostLeft = bottomSplit.rightArc;
 
488
                    routeList.add(r);
 
489
 
 
490
                    // Extract area from possible remaining geometry. This will happen
 
491
                    // when the wires are in zig-zag
 
492
                    if (a != null) // there is a remainig area
 
493
                    {
 
494
                        Area remove = new Area(pair.cut);
 
495
                        a.subtract(remove);
 
496
                    }
 
497
                }
 
498
                for (Route r : routeList)
 
499
                {
 
500
                    Router.createRouteNoJob(r, theCell, false, arcsCreatedMap, nodesCreatedMap);
 
501
                }
 
502
            }
 
503
 
 
504
            // Adding remaining contacts due to non-100% overlap with original arcs
 
505
            for (Map.Entry<String,Area> e : remainingGeos.entrySet())
 
506
            {
 
507
                Area a = e.getValue();
 
508
                Netlist netlist = theCell.getNetlist();
 
509
                List<PolyBase> list = PolyBase.getPointsInArea(a, bottom, false, false);
 
510
                List<ArcInst> at = getArcsInGivenLayer(theCell.getArcs(), !horizontal, top,  e.getKey(), netlist);
 
511
                List<PinsArcPair> pairs = new ArrayList<PinsArcPair>(2);
 
512
 
 
513
                // Add extra contacts. All points should be aligned in same horizontal or vertical line
 
514
                // first the top arcs. They should be less in number (less number of splits)
 
515
                for (PolyBase p : list)
 
516
                {
 
517
                    Rectangle2D resultBnd = p.getBounds2D();
 
518
 
 
519
                    // look for the first pair of arcs in bottom/top arcs that overlap with geometry
 
520
                    ArcInst topA = getArcInstOverlappingWithArea(resultBnd, at, horizontal, true); // perferct if fully contains the arc
 
521
 
 
522
                    if (topA != null)
 
523
                    {
 
524
                        EPoint insert = new EPoint(resultBnd.getCenterX(), resultBnd.getCenterY());
 
525
                        pairs.add(new PinsArcPair(topA, insert, resultBnd));
 
526
                    }
 
527
                }
 
528
                // Sort the new pairs from left/top to right/bottom
 
529
                Collections.sort(pairs, pinsArcSort);
 
530
 
 
531
                // Look for bottomLayer arcs for those given positions
 
532
                List<ArcInst> ab = getArcsInGivenLayer(theCell.getArcs(), horizontal, bottom, e.getKey(), netlist);
 
533
                routeList.clear();
 
534
 
 
535
                for (PinsArcPair pair : pairs)
 
536
                {
 
537
                    ArcInst bottomA = getArcInstOverlappingWithArea(pair.cut, ab, horizontal, false);
 
538
                    if (bottomA != null)
 
539
                    {
 
540
                        //SplitContainter bottomSplit = splitArcAtPoint(bottomA, pair.insert);
 
541
                        //SplitContainter topSplit = splitArcAtPoint(pair.topArc, pair.insert);
 
542
                        Route r = router.planRoute(theCell,  bottomA, pair.topArc, pair.insert, null, true, true, pair.cut);
 
543
                        // remove the old one and add new arc
 
544
                        ab.remove(bottomA);
 
545
                        //ab.add(bottomSplit.rightArc);
 
546
                        topLayers[0] = bottom;
 
547
                        topLayers[1] = top;
 
548
                        routeList.add(r);
 
549
                    }
 
550
                    else if (Job.getDebug())
 
551
                    {
 
552
                         bottomA = getArcInstOverlappingWithArea(pair.cut, ab, horizontal, false);
 
553
                        System.out.println("AFG: It couldn't find bottom layer for " + pair.cut);
 
554
                    }
 
555
                }
 
556
                for (Route r : routeList)
 
557
                {
 
558
                    Router.createRouteNoJob(r, theCell, false, arcsCreatedMap, nodesCreatedMap);
 
559
                }
 
560
            }
 
561
        }
 
562
 
 
563
        Netlist netlist = theCell.getNetlist();
 
564
        // Connect cell instances
 
565
        for (Iterator<NodeInst> itNi = theCell.getNodes(); itNi.hasNext();)
 
566
        {
 
567
            NodeInst ni = itNi.next();
 
568
 
 
569
            // only cell instances
 
570
            if (!ni.isCellInstance()) continue;
 
571
 
 
572
            // Checking if the export overlaps with
 
573
            // Checking if there are exports overlapping with the arc
 
574
            List<String> doneExports = new ArrayList<String>();
 
575
            routeList.clear();
 
576
            SimpleWirer niRouter = new SimpleWirer();
 
577
 
 
578
            for (Iterator<Export> itE = ni.getExports(); itE.hasNext(); )
 
579
            {
 
580
                Export ex = itE.next();
 
581
                String exportName = ex.getName();
 
582
                String rootName = extractRootName(exportName);
 
583
 
 
584
                if (doneExports.contains(rootName))   // exportName
 
585
                    continue; // export for this given NodeInst was done
 
586
 
 
587
                PrimitiveNode n = ex.getBasePort().getParent();
 
588
                Layer layer = n.getLayerIterator().next(); // assuming only 1
 
589
                PortInst pi = ex.getOriginalPort();
 
590
                PortProto epi = pi.getPortProto();
 
591
                EPoint exportCenter = pi.getCenter();
 
592
                NodeProto np = epi.getParent();
 
593
                if (!(np instanceof Cell))
 
594
                    continue; // not good for now.
 
595
                Cell c = (Cell)np;
 
596
                Netlist netl = c.getNetlist();
 
597
                Network jExp = netl.getNetwork((Export)epi, 0);
 
598
                Area expA = new Area();
 
599
 
 
600
                // Look for all arcs in the cell instances that are on the given layer and netwoek
 
601
                for (Iterator<ArcInst> itA = jExp.getArcs(); itA.hasNext();)
 
602
                {
 
603
                    ArcInst ai = itA.next();
 
604
                    Layer l = ai.getProto().getLayer(0);
 
605
 
 
606
                    if (l != layer) continue;
 
607
                    expA.add(new Area(ai.getBounds()));
 
608
                }
 
609
 
 
610
                // Algorithm will look for the closest connection.
 
611
                Rectangle2D bestCut = null; // represents the best cut
 
612
                ArcInst bestArc = null;
 
613
                Point2D bestCenter = null;
 
614
                double bestDistance = Double.MAX_VALUE;
 
615
                List<Network> netList = getNetworkFromName(netlist, rootName);
 
616
//                        jNet = getNetworkFromName(netlist, rootName);
 
617
 
 
618
                for (Network jNet : netList)
 
619
                {
 
620
                    for (Iterator<ArcInst> itA = jNet.getArcs(); itA.hasNext();)
 
621
                    {
 
622
                        ArcInst ai = itA.next();
 
623
                        Layer l = ai.getProto().getLayer(0);
 
624
 
 
625
                        if (l == layer)
 
626
                            System.out.println("found in same layer");
 
627
                        else if (Math.abs(l.getIndex() - layer.getIndex()) <=1)
 
628
                        {
 
629
                            // Not selecting the closest element yet
 
630
                            Area bnd = new Area(ai.getBounds());
 
631
                            bnd.intersect(expA);
 
632
                            if (!bnd.isEmpty())
 
633
                            {
 
634
                                Rectangle2D cut = bnd.getBounds2D();
 
635
                                Point2D center = new EPoint(cut.getCenterX(), cut.getCenterY());
 
636
                                double dist = DBMath.distBetweenPoints(center, exportCenter);
 
637
                                if (bestCenter == null || DBMath.isLessThan(dist, bestDistance))
 
638
                                {
 
639
                                    // first time or the new distance is shorter
 
640
                                    bestCenter = center;
 
641
                                    bestCut = cut;
 
642
                                    bestArc = ai;
 
643
                                    bestDistance = dist;
 
644
                                }
 
645
                            }
 
646
                        }
 
647
                    }
 
648
                }
 
649
                if (bestCut != null) // best location found
 
650
                {
 
651
                    Route r = niRouter.planRoute(theCell,  bestArc, pi, bestCenter, null, true, true, bestCut);
 
652
                    routeList.add(r);
 
653
                    doneExports.add(rootName);
 
654
                }
 
655
            }
 
656
 
 
657
 
 
658
            for (Route r : routeList)
 
659
            {
 
660
                Router.createRouteNoJob(r, theCell, false, arcsCreatedMap, nodesCreatedMap);
 
661
            }
 
662
        }
 
663
 
 
664
        // Remove exports in lower layers
 
665
        Set<Export> toDelete = new HashSet<Export>();
 
666
        Map<String,Export> inBottomLayer = new HashMap<String,Export>(); // enough with 1 export stored
 
667
 
 
668
        // find the highest level metal for a given network
 
669
        Map<Network,Layer> maximumLayer = new HashMap<Network,Layer>();
 
670
        for (Iterator<Export> itE = theCell.getExports(); itE.hasNext();) {
 
671
            Export exp = itE.next();
 
672
            PrimitiveNode n = exp.getBasePort().getParent();
 
673
            Network net = netlist.getNetwork(exp, 0);
 
674
            Layer l = maximumLayer.get(net);
 
675
            for (Iterator<Layer> itL = n.getLayerIterator(); itL.hasNext();)
 
676
            {
 
677
                Layer lnew = itL.next();
 
678
                if (l == null) {
 
679
                    l = lnew;
 
680
                    continue;
 
681
                }
 
682
                if (lnew.getFunction().getLevel() > l.getFunction().getLevel()) {
 
683
                    l = lnew;
 
684
                }
 
685
            }
 
686
            maximumLayer.put(net, l);
 
687
        }
 
688
 
 
689
        for (Iterator<Export> itE = theCell.getExports(); itE.hasNext();)
 
690
        {
 
691
            Export exp = itE.next();
 
692
            PrimitiveNode n = exp.getBasePort().getParent();
 
693
            boolean found = false;
 
694
            String rootName = extractRootName(exp.getName());
 
695
 
 
696
            Layer topLayer = maximumLayer.get(netlist.getNetwork(exp, 0));
 
697
            int levelMax = topLayer.getFunction().getLevel();
 
698
            for (Iterator<Layer> itL = n.getLayerIterator(); itL.hasNext();)
 
699
            {
 
700
                Layer l = itL.next();
 
701
                int level = l.getFunction().getLevel();
 
702
                if (level == levelMax || level == (levelMax-1)) {
 
703
                    found = true;
 
704
                } else {
 
705
                    inBottomLayer.put(rootName, exp); // put the last one in the network.
 
706
                }
 
707
            }
 
708
            if (!found) // delete the export
 
709
                toDelete.add(exp);
 
710
        }
 
711
 
 
712
        // Add extra export in the middle of the botoom layer.
 
713
        if (wideOption)
 
714
        {
 
715
            Map<String,List<PinsArcPair>> newExports = new HashMap<String,List<PinsArcPair>>();
 
716
            boolean horizontal = isLayerHorizontal(bottomLayer, evenHorizontal);
 
717
 
 
718
            // For each export 1 export in the bottom layer should be insert
 
719
            for (Map.Entry<String,Export> e : inBottomLayer.entrySet())
 
720
            {
 
721
                Export exp = e.getValue();
 
722
                String rootName = extractRootName(exp.getName());
 
723
                Network net = netlist.getNetwork(exp, 0);
 
724
                // Collect first all the arcs in that layer
 
725
                List<ArcInst> arcs = getArcsInGivenLayer(net.getArcs(), horizontal, bottomLayer, null, null);
 
726
                Area area = totalAreas.get(rootName);
 
727
                List<PinsArcPair> l = new ArrayList<PinsArcPair>();
 
728
 
 
729
                // It could be multiple areas disconnected.
 
730
                List<PolyBase> list = PolyBase.getPointsInArea(area, bottomLayer, false, false);
 
731
                if (list == null) continue; // no matching export on bottom level
 
732
                for (PolyBase b : list)
 
733
                {
 
734
                    Rectangle2D resultBnd = b.getBounds2D();
 
735
                    EPoint insert = new EPoint(resultBnd.getCenterX(), resultBnd.getCenterY());
 
736
                    PinsArcPair split; // looking for the first arc where the center is contained.
 
737
                    for (ArcInst ai : arcs)
 
738
                    {
 
739
                        Rectangle2D bnd = ai.getBounds();
 
740
                        if (bnd.contains(insert.getX(), insert.getY()))
 
741
                        {
 
742
                            split = new PinsArcPair(ai, insert, null);
 
743
                            l.add(split);
 
744
                            break;
 
745
                        }
 
746
                    }
 
747
                }
 
748
                newExports.put(rootName, l);
 
749
            }
 
750
 
 
751
            for (Map.Entry<String,List<PinsArcPair>> e : newExports.entrySet())
 
752
            {
 
753
                List<PinsArcPair> pairs = e.getValue();
 
754
                for (PinsArcPair pair : pairs)
 
755
                {
 
756
                    SplitContainter split = splitArcAtPoint(pair.topArc, pair.insert);
 
757
                    Export.newInstance(theCell, split.splitPin.getPortInst(0), e.getKey(), PortCharacteristic.UNKNOWN);
 
758
                }
 
759
            }
 
760
        }
 
761
 
 
762
        // Delete after dealing with the wide option
 
763
        // At least one connection was done otherwise it will keep the original exports.
 
764
        // Option is mostly for debugging purposes.
 
765
        if (topLayers[0] != null || topLayers[1] != null)
 
766
            theCell.killExports(toDelete);
 
767
 
 
768
        // make sure at least one export on a network is the root name
 
769
        netlist = theCell.getNetlist();
 
770
        for (Iterator<Network> itN = netlist.getNetworks(); itN.hasNext(); ) {
 
771
            Network net = itN.next();
 
772
            if (!net.isExported()) continue;
 
773
            String name = net.getName();
 
774
            String rootName = extractRootName(name);
 
775
            if (!name.equals(rootName)) {
 
776
                Export exp = net.getExports().next();
 
777
                exp.rename(rootName);
 
778
            }
 
779
        }
 
780
        return true;
 
781
    }
 
782
 
 
783
    private static ArcInst getArcInstOverlappingWithArea(Rectangle2D resultBnd, List<ArcInst> at, boolean horizontal, boolean topLayer)
 
784
    {
 
785
        Area topArea = new Area(resultBnd);
 
786
        for (ArcInst ai : at)
 
787
        {
 
788
            Rectangle2D r = ai.getBounds();
 
789
 
 
790
            // test if the current ai inserts with the given area
 
791
            // and it is fully contained along the axis the arc is aligned
 
792
            if (r.intersects(resultBnd))
 
793
            {
 
794
                Area rArea = new Area(r);
 
795
                rArea.intersect(topArea);
 
796
                Rectangle2D rect = rArea.getBounds2D();
 
797
                boolean validArc;
 
798
 
 
799
                if (horizontal && topLayer || !horizontal && !topLayer)  // top arc is aligned along Y or bottom arc along Y
 
800
                {
 
801
                    validArc = DBMath.areEquals(rect.getWidth(), r.getWidth());
 
802
                }
 
803
                else // top arc is aligned along X
 
804
                {
 
805
                    validArc = DBMath.areEquals(rect.getHeight(), r.getHeight());
 
806
                }
 
807
 
 
808
                if (validArc)
 
809
                {
 
810
                    // found
 
811
                    return ai;
 
812
                }
 
813
            }
 
814
        }
 
815
        return null;
 
816
    }
 
817
 
 
818
    /**
 
819
     * Method to get Network from a given network root name
 
820
     * @param netlist Netlist containing the network information
 
821
     * @param rootName Root name of the network
 
822
     * @return Network
 
823
     */
 
824
    private static List<Network> getNetworkFromName(Netlist netlist, String rootName)
 
825
    {
 
826
        List<Network> list = new ArrayList<Network>();
 
827
 
 
828
        for (Iterator<Network> it = netlist.getNetworks(); it.hasNext();)
 
829
        {
 
830
            Network net = it.next();
 
831
            if (net.getName().startsWith(rootName))
 
832
                list.add(net);
 
833
        }
 
834
        return list;
 
835
    }
 
836
 
 
837
    /**
 
838
     * Method to determine if Layer is aligned horizontally
 
839
     * @param layer Given Layer
 
840
     * @param evenHorizontal True if even layers are horizontal
 
841
     * @return True of layer is horizontal
 
842
     */
 
843
    private static boolean isLayerHorizontal(Layer layer, boolean evenHorizontal)
 
844
    {
 
845
        int metalNumber = layer.getFunction().getLevel();
 
846
        return (evenHorizontal && metalNumber%2==0) || (!evenHorizontal && metalNumber%2==1);
 
847
    }
 
848
 
 
849
    /**
 
850
     * Method to collect arcs in a given layer with a given export name from an iterator
 
851
     * @param itAi Arcs iterator
 
852
     * @param horizontal Variable to determine if the arc mus be aligned horizontally
 
853
     * @param layer Given layer
 
854
     * @param exportName Given export name. If null, any export name is valid
 
855
     * @param netlist  Given Netlist to find exports
 
856
     * @return List of ArcInsts
 
857
     */
 
858
    private static List<ArcInst> getArcsInGivenLayer(Iterator<ArcInst> itAi, boolean horizontal,
 
859
                                                     Layer layer, String exportName, Netlist netlist)
 
860
    {
 
861
        List<ArcInst> arcs = new ArrayList<ArcInst>();
 
862
 
 
863
        for (; itAi.hasNext();)
 
864
        {
 
865
            ArcInst ai = itAi.next();
 
866
 
 
867
            // Checking arc orientation with respect to layer
 
868
            // If the orientation is not correct, then ignore it
 
869
            if (!isArcAligned(ai, horizontal))
 
870
                continue;
 
871
 
 
872
            Layer l = ai.getProto().getLayer(0);
 
873
            if (l != layer)
 
874
                continue;
 
875
            if (exportName != null)
 
876
            {
 
877
                Network jNet = netlist.getNetwork(ai, 0);
 
878
                Iterator<Export> itE = jNet.getExports();
 
879
                if (!itE.hasNext())
 
880
                {
 
881
                    if (Job.getDebug())
 
882
                        System.out.println("AFG: No export name associated to ArcInst '" + ai.getName() + "'");
 
883
                    continue; // no export
 
884
                }
 
885
                Export exp = itE.next(); // first is enough
 
886
                String expName = extractRootName(exp.getName());
 
887
                if (!expName.equals(exportName))
 
888
                    continue; // no match
 
889
            }
 
890
            arcs.add(ai);
 
891
        }
 
892
        return arcs;
 
893
    }
 
894
 
 
895
    /**
 
896
     * Method to check whether a given arc is properly oriented with respect to the expected input
 
897
     * @param ai the given ArcInst
 
898
     * @param horizontal True if the arc must be horizontal
 
899
     * @return True if the arc is aligned with the given direction
 
900
     */
 
901
    private static boolean isArcAligned(ArcInst ai, boolean horizontal)
 
902
    {
 
903
        EPoint head = ai.getHeadLocation();
 
904
        EPoint tail = ai.getTailLocation();
 
905
        if (horizontal)
 
906
            return (DBMath.areEquals(head.getY(), tail.getY()));
 
907
        return (DBMath.areEquals(head.getX(), tail.getX()));
 
908
    }
 
909
 
 
910
    /**
 
911
     * Method to extract the export root name from a given name
 
912
     * @param name String containing the export name
 
913
     * @return String containing the root name of the export
 
914
     */
 
915
    private static String extractRootName(String name)
 
916
    {
 
917
        int index = name.indexOf("_");
 
918
        if (index != -1) // remove any character after _
 
919
            name = name.substring(0, index);
 
920
        return name;
 
921
    }
 
922
 
 
923
    /**
 
924
     * Methot to extrac root name of the export in a given arc
 
925
     * @param ai arc with the export
 
926
     * @param netlist Given network to search in
 
927
     * @return Non-null string with the root name. Null if no export was found.
 
928
     */
 
929
    private static String getExportRootName(ArcInst ai, Netlist netlist)
 
930
    {
 
931
        Network jNet = netlist.getNetwork(ai, 0);
 
932
        // Picking only 1 export and considering the root name`
 
933
        // Assuming at 1 export per arc
 
934
        if (jNet == null)
 
935
            return null;
 
936
        assert(jNet != null);
 
937
        Iterator<String> exportNames = jNet.getExportedNames();
 
938
        if (!exportNames.hasNext())
 
939
            return null; // no export
 
940
        return extractRootName(exportNames.next());
 
941
    }
 
942
 
 
943
    /**
 
944
     * Method to split an arc at a given point
 
945
     * @param ai arc to split
 
946
     * @param insert point to split at
 
947
     * @return SplitContainter representing the split pin and new arcs
 
948
     */
 
949
    private static SplitContainter splitArcAtPoint(ArcInst ai, EPoint insert)
 
950
    {
 
951
        // create the break pins
 
952
        ArcProto ap = ai.getProto();
 
953
        NodeProto np = ap.findPinProto();
 
954
        if (np == null) return null;
 
955
        NodeInst ni = NodeInst.makeInstance(np, insert, np.getDefWidth(), np.getDefHeight(), ai.getParent());
 
956
        if (ni == null)
 
957
        {
 
958
            System.out.println("Cannot create pin " + np.describe(true));
 
959
            return null;
 
960
        }
 
961
 
 
962
        SplitContainter container = new SplitContainter();
 
963
        container.splitPin = ni;
 
964
 
 
965
        // get location of connection to these pins
 
966
        PortInst pi = ni.getOnlyPortInst();
 
967
 
 
968
        // now save the arc information and delete it
 
969
        PortInst headPort = ai.getHeadPortInst();
 
970
        PortInst tailPort = ai.getTailPortInst();
 
971
        Point2D headPt = ai.getHeadLocation();
 
972
        Point2D tailPt = ai.getTailLocation();
 
973
        double width = ai.getLambdaBaseWidth();
 
974
//        String arcName = ai.getName();
 
975
 
 
976
        // create the new arcs
 
977
        ArcInst newAi1 = ArcInst.makeInstanceBase(ap, width, headPort, pi, headPt, insert, null);
 
978
        ArcInst newAi2 = ArcInst.makeInstanceBase(ap, width, pi, tailPort, insert, tailPt, null);
 
979
        newAi1.setHeadNegated(ai.isHeadNegated());
 
980
        newAi1.setHeadExtended(ai.isHeadExtended());
 
981
        newAi1.setHeadArrowed(ai.isHeadArrowed());
 
982
        newAi1.setTailNegated(ai.isTailNegated());
 
983
        newAi1.setTailExtended(ai.isTailExtended());
 
984
        newAi1.setTailArrowed(ai.isTailArrowed());
 
985
 
 
986
        newAi2.setHeadNegated(ai.isHeadNegated());
 
987
        newAi2.setHeadExtended(ai.isHeadExtended());
 
988
        newAi2.setHeadArrowed(ai.isHeadArrowed());
 
989
        newAi2.setTailNegated(ai.isTailNegated());
 
990
        newAi2.setTailExtended(ai.isTailExtended());
 
991
        newAi2.setTailArrowed(ai.isTailArrowed());
 
992
 
 
993
        // Determining which arc is left/top
 
994
        if (isLeftTop(headPt, tailPt))
 
995
        {
 
996
            container.leftArc = newAi1;
 
997
            container.rightArc = newAi2;
 
998
        }
 
999
        else
 
1000
        {
 
1001
            container.leftArc = newAi2;
 
1002
            container.rightArc = newAi1;
 
1003
        }
 
1004
        ai.kill();
 
1005
//        if (arcName != null)
 
1006
//        {
 
1007
//            if (headPt.distance(insert) > tailPt.distance(insert))
 
1008
//            {
 
1009
//                newAi1.setName(arcName);
 
1010
//                newAi1.copyTextDescriptorFrom(ai, ArcInst.ARC_NAME);
 
1011
//            } else
 
1012
//            {
 
1013
//                newAi2.setName(arcName);
 
1014
//                newAi2.copyTextDescriptorFrom(ai, ArcInst.ARC_NAME);
 
1015
//            }
 
1016
//        }
 
1017
        return container;
 
1018
    }
 
1019
 
 
1020
    /**
 
1021
     * Internal class to keep potential connections
 
1022
     */
 
1023
    private static class PinsArcPair
 
1024
    {
 
1025
        private ArcInst topArc;
 
1026
        private EPoint insert;
 
1027
        private Rectangle2D cut;
 
1028
 
 
1029
        PinsArcPair(ArcInst topA, EPoint point, Rectangle2D c)
 
1030
        {
 
1031
            topArc = topA;
 
1032
            insert = point;
 
1033
            cut = c;
 
1034
        }
 
1035
    }
 
1036
 
 
1037
    private static boolean isLeftTop(Point2D p1, Point2D p2)
 
1038
    {
 
1039
        if (DBMath.areEquals(p1.getX(), p2.getX()))
 
1040
        {
 
1041
            return (!DBMath.isGreaterThan(p1.getY(), p2.getY()));
 
1042
        }
 
1043
        else if (DBMath.areEquals(p1.getY(), p2.getY()))
 
1044
        {
 
1045
            return (!DBMath.isGreaterThan(p1.getX(), p2.getX()));
 
1046
        }
 
1047
        else
 
1048
            System.out.println("Case not considered in FillJob:isLeftTop");
 
1049
//            assert(false); // not considered yet
 
1050
        return false;
 
1051
    }
 
1052
 
 
1053
    /**
 
1054
     * Class to store temp info
 
1055
     */
 
1056
    private static class SplitContainter
 
1057
    {
 
1058
        NodeInst splitPin;
 
1059
        ArcInst leftArc, rightArc; // to keep track of new arcs after the original one was split
 
1060
    }
 
1061
 
 
1062
    /**
 
1063
     * To sort PinsArcPair
 
1064
     */
 
1065
    private static final PinsArcPairSort pinsArcSort = new PinsArcPairSort();
 
1066
 
 
1067
    /**
 
1068
     * Comparator class for sorting PinsArcPair by their insertion point
 
1069
     */
 
1070
    private static class PinsArcPairSort implements Comparator<PinsArcPair>
 
1071
    {
 
1072
        /**
 
1073
         * Method to compare two PinsArcPair objects by their insertion point.
 
1074
         * @param l1 one PinsArcPair.
 
1075
         * @param l2 another PinsArcPair.
 
1076
         * @return an integer indicating their sorting order.
 
1077
         */
 
1078
        public int compare(PinsArcPair l1, PinsArcPair l2)
 
1079
        {
 
1080
            EPoint p1 = l1.insert;
 
1081
            EPoint p2 = l2.insert;
 
1082
            return (isLeftTop(p2, p1)?1:-1);
 
1083
        }
 
1084
    }
 
1085
 
 
1086
}