river.java

The ElectricTM VLSI Design System is an open-source Electronic Design Automation (EDA) system that c

		// ports invalid
		if (!checkPoints(listR, width, space)) return false;
		structurePoints(listR);				// put in left/right
		if (!checkStructuredPoints(rightP, leftP, cellOff1, width, space)) return false;
		if (processRight(width, layerDesc, rightP, cellOff1, space, -1)) return false;
		if (processLeft(width, layerDesc, leftP, cellOff1, space, 1)) return false;
		Double dHeight = calculateHeightAndProcess(rightP, leftP, width, cellOff2);
		if (dHeight == null) return false;
		calculateBB(rightP, leftP);
		height = dHeight.doubleValue();
		return true;
	}

	private void calculateBB(List<RDESC> right, List<RDESC> left)
	{
		routBoundLX = routBoundLY = Double.MAX_VALUE;
		routBoundHX = routBoundHY = Double.MIN_VALUE;
		for(RDESC rRight : right)
		{
			for(RPOINT rvp = rRight.path.pathDesc; rvp != null; rvp = rvp.next)
			{
				routBoundLX = Math.min(routBoundLX, rvp.x);
				routBoundLY = Math.min(routBoundLY, rvp.y);
				routBoundHX = Math.max(routBoundHX, rvp.x);
				routBoundHY = Math.max(routBoundHY, rvp.y);
			}
		}
		for(RDESC lLeft : left)
		{
			for(RPOINT rvp = lLeft.path.pathDesc; rvp != null; rvp = rvp.next)
			{
				routBoundLX = Math.min(routBoundLX, rvp.x);
				routBoundLY = Math.min(routBoundLY, rvp.y);
				routBoundHX = Math.max(routBoundHX, rvp.x);
				routBoundHY = Math.max(routBoundHY, rvp.y);
			}
		}
	}

	private Double calculateHeightAndProcess(List<RDESC> right, List<RDESC> left, double width, double co2)
	{
		double minHeight = 0;
		double maxHeight = Double.MIN_VALUE;
		for(RDESC rd : right)
		{
			maxHeight = Math.max(maxHeight, rd.path.lastP.second);
		}
		for(RDESC rd : left)
		{
			maxHeight = Math.max(maxHeight, rd.path.lastP.second);
		}

		if (minHeight != 0) maxHeight = Math.max(minHeight, maxHeight+(width/2)+co2);
			else maxHeight = maxHeight+(width/2)+co2;
		maxHeight = Math.max(maxHeight, toLine);

		// make sure its at least where the coordinates are
		for(RDESC rd : right)
		{
			RPOINT lastP = rd.path.lastP;
			if (lastP.side != RPOINT.SIDE2)
			{
				lastP.next = new RPOINT(rd.path, lastP.first, maxHeight, null);
			}
			remapPoints(rd.path.pathDesc, xfInverse);
		}
		for(RDESC rd : left)
		{
			RPOINT lastP = rd.path.lastP;
			if (lastP.side != RPOINT.SIDE4)
			{
				lastP.next = new RPOINT(rd.path, lastP.first, maxHeight, null);
			}
			remapPoints(rd.path.pathDesc, xfInverse);
		}
		toLine = remapSecond(toLine, xfInverse);
		fromLine = remapSecond(fromLine, xfInverse);
		return new Double(remapSecond(maxHeight, xfInverse));
	}

	/**
	 * calculate the height of the channel, and remap the points back into the
	 * original coordinate system
	 */
	private void remapPoints(RPOINT rp, TRANSFORM matrix)
	{
		for(; rp != null; rp = rp.next)
		{
			rp.x = (rp.first*matrix.t11) + (rp.second*matrix.t21);
			rp.y = (rp.first*matrix.t12) + (rp.second*matrix.t22);
		}
	}

	private double remapSecond(double sec, TRANSFORM matrix)
	{
		if (routDirection == ROUTEINY) return sec * matrix.t22;
		return sec * matrix.t12;
	}

	private boolean processLeft(double width, ArcProto ptype, List<RDESC> rout, double co1, double space, double dir)
	{
		boolean firstTime = true;
		RPATH lastP = null;
		double offset = startRight;
		for(RDESC rd : rout)
		{
			if (rd.from.side != RPOINT.SIDE2)
			{
				if (firstTime)
				{
					rd.path = makeOrigPath(width, ptype, co1, rd.from, rd.to);
					if (rd.path == null) return true;
					firstTime = false;
				} else
					rd.path = addPath(lastP, width, ptype, rd.from, rd.to, space, co1, dir);
				if (rd.path == null) return true;
			} else
			{
				if (firstTime)
				{
					rd.path = makeSideOrigPath(width, ptype, offset, rd.from, rd.to);
					if (rd.path == null) return true;
					firstTime = false;
				} else
				{
					rd.path = sideAddPath(lastP, width, ptype, rd.from, rd.to, space, offset, dir);
					if (rd.path == null) return true;
				}
				offset += space+width;
			}
			lastP = rd.path;
		}
		return false;
	}

	private boolean processRight(double width, ArcProto ptype, List<RDESC> rout, double co1, double space, int dir)
	{
		boolean firstTime = true;
		RPATH lastP = null;
		double offset = startLeft;

		reverse(rout);
		for(RDESC rd : rout)
		{
			if (rd.from.side != RPOINT.SIDE4)
			{
				// starting from bottom (side1)
				if (firstTime)
				{
					rd.path = makeOrigPath(width, ptype, co1, rd.from, rd.to);
					if (rd.path == null) return true;
					firstTime = false;
				} else
					rd.path = addPath(lastP, width, ptype, rd.from, rd.to, space, co1, dir);
				if (rd.path == null) return true;
			} else
			{
				if (firstTime)
				{
					rd.path = makeSideOrigPath(width, ptype, offset, rd.from, rd.to);
					if (rd.path == null) return true;
					firstTime = false;
				} else
				{
					rd.path = sideAddPath(lastP, width, ptype, rd.from, rd.to, space, offset, dir);
					if (rd.path == null) return true;
				}
				offset += space+width;
			}
			lastP = rd.path;
		}
		reverse(rout);  // return to normal
		return false;
	}

	private RPATH sideAddPath(RPATH path, double width, ArcProto ptype, RPOINT b, RPOINT t,
		double space, double offset, double dir)
	{
		RPATH rp = new RPATH(width, ptype);
		rp.pathDesc = new RPOINT(rp, b.first, offset, null);

		double minFirst = Math.min(b.first, t.first);
		double maxFirst = Math.max(b.first, t.first);
		RPOINT lp = path.pathDesc;
		RPOINT lastP = rp.lastP;

		double newfirst = lp.first+dir*(space+rp.width);
		while (lp != null && minFirst <= newfirst && newfirst <= maxFirst)
		{
			// if first point then inconsistent second(y) offset 
			if (lp == path.pathDesc)
				lastP.next = new RPOINT(rp, newfirst, Math.min(lastP.second, offset), null);
			else
				lastP.next = new RPOINT(rp, newfirst, Math.max(lp.second+space+rp.width, offset), null);
			lastP = lastP.next;   lp = lp.next;
			if (lp != null) newfirst = lp.first+dir*(space+rp.width);
		}
		lastP.next = new RPOINT(rp, t.first, lastP.second, null);
		rp.lastP.side = t.side;
		return(rp);
	}

	private RPATH addPath(RPATH path, double width, ArcProto ptype, RPOINT b, RPOINT t,
		double space, double co1, double dir)
	{
		RPATH rp = new RPATH(width, ptype);
		RPOINT i1 = new RPOINT(rp, b.first, b.second+(rp.width/2)+co1, null);
		rp.pathDesc = new RPOINT(rp, b.first, b.second, i1);
		double minFirst = Math.min(b.first, t.first);
		double maxFirst = Math.max(b.first, t.first);
		RPOINT lp = path.pathDesc;
		RPOINT lastP = rp.lastP;

		double newfirst = lp.first+dir*(space+rp.width);
		while (lp != null && minFirst <= newfirst && newfirst <= maxFirst)
		{
			// if first point then inconsistent second(y) offset
			if (lp == path.pathDesc)
				lastP.next = new RPOINT(rp, newfirst, lastP.second, null); else
					lastP.next = new RPOINT(rp, newfirst, lp.second+space+rp.width, null);
			lastP = lastP.next;   lp = lp.next;
			if (lp != null) newfirst = lp.first+dir*(space+rp.width);
		}
		lastP.next = new RPOINT(rp, t.first, lastP.second, null);
		rp.lastP.side = t.side;
		return rp;
	}

	private RPATH makeOrigPath(double width, ArcProto ptype, double co1, RPOINT b, RPOINT t)
	{
		RPATH rp = new RPATH(width, ptype);

		RPOINT i1 = new RPOINT(rp, t.first, b.second+(width/2)+co1, null);
		RPOINT i2 = new RPOINT(rp, b.first, b.second+(width/2)+co1, i1);
		rp.pathDesc = new RPOINT(rp, b.first, b.second, i2);
		rp.lastP.side = t.side;
		return rp;
	}

	private RPATH makeSideOrigPath(double width, ArcProto ptype, double startoff, RPOINT b, RPOINT t)
	{
		RPATH rp = new RPATH(width, ptype);
		RPOINT i1 = new RPOINT(rp, t.first, startoff, null);
		rp.pathDesc = new RPOINT(rp, b.first, startoff, i1);
		rp.lastP.side = t.side;
		return rp;
	}

	private void reverse(List<RDESC> p)
	{
		int total = p.size();
		if (total <= 1) return;

		for(int i=0; i<total/2; i++)
		{
			int otherI = total - i - 1;
			RDESC early = p.get(i);
			RDESC late = p.get(otherI);
			p.set(i, late);
			p.set(otherI, early);
		}
	}

	private boolean checkStructuredPoints(List<RDESC> right, List<RDESC> left, double co1, double width, double space)
	{
		boolean fromSide1 = false;
		boolean toSide2 = false;
		double botOffs2 = 0;

		// ensure ordering is correct
		for(RDESC r : right)
		{
			switch (r.from.side)
			{
				case RPOINT.SIDE1:
					fromSide1 = true;
					break;
				case RPOINT.SIDE4:
					if (fromSide1)
					{
						System.out.println("River router: Improper ordering of bottom right ports");
						return false;
					}
					break;
				default:
					System.out.println("River router: Improper sides for bottom right ports (" + RPOINT.sideName(r.from.side) + ")");
					return false;
			}
			switch (r.to.side)
			{
				case RPOINT.SIDE2:
					if (!toSide2) botOffs2 = fromLine+co1+(width/2);
						else botOffs2 += space+width;
					toSide2 = true;
					break;
				case RPOINT.SIDE3:
					if (toSide2)
					{
						System.out.println("River router: Improper ordering of top right ports");
						return false;
					}
					break;
				default:
					System.out.println("River router: Improper sides for top right ports");
					return false;
			}
		}

		boolean fromSide2 = false;   boolean toSide3 = false;   boolean toSide4 = false;   double botOffs4 = 0;
		for(RDESC l : left)
		{
			switch (l.from.side)
			{
				case RPOINT.SIDE1:
					if (fromSide2)
					{
						System.out.println("River router: Improper Ordering of Bottom Left Ports");
						return false;
					}
					break;
				case RPOINT.SIDE2:
					fromSide2 = true;
					break;
				default:
					System.out.println("River router: Improper sides for Bottom Left Ports");
					return false;
			}
			switch (l.to.side)
			{
				case RPOINT.SIDE3:
					toSide3 = true;
					break;
				case RPOINT.SIDE4:
					if (!toSide3)
					{
						if (!toSide4) botOffs4 = fromLine+co1+(width/2);
							else botOffs4 += space+width;
					} else
					{
						System.out.println("River router: Improper Ordering of Top Left Ports");
						return false;
					}
					toSide4 = true;
					break;
				default:
					System.out.println("River router: Improper sides for Top Left Ports");
					return false;
			}
		}
		if (botOffs2 == 0) startRight = fromLine+co1+(width/2);
			else	       startRight = botOffs2+space+width;
	
		if (botOffs4 == 0) startLeft = fromLine+co1+(width/2);
			else	       startLeft = botOffs4+space+width;
		return true;
	}

	private void structurePoints(List<RDESC> listr)
	{
		rightP = new ArrayList<RDESC>();
		leftP = new ArrayList<RDESC>();
		for(RDESC rd : listr)
		{
			if (rd.to.first >= rd.from.first) rightP.add(rd);
				else leftP.add(rd);
		}
	}

	private boolean checkPoints(List<RDESC> rdescList, double width, double space)
	{
		int numRDesc = rdescList.size();
		if (numRDesc == 0)
		{
			// need at least one point
			System.out.println("River router: Not enought points");
			return false;
		}

		RDESC listLast = rdescList.get(numRDesc-1);
		if (listLast.from == null || listLast.to == null)
		{
			System.out.println("River router: Not the same number of points");
			return false;
		}

		// decide route orientation
		RDESC listP = rdescList.get(0);
		TRANSFORM tMatrix = null;
		double val1 = 0, val2 = 0;
		if (routDirection == ROUTEINX)
		{
			// route in x direction
			if (listP.to.x >= listP.from.x)
			{											// x2>x1
				if (listLast.from.y >= listP.from.y)
					tMatrix = xfRot90MirrorX;			// Y increasing
						else tMatrix = xfRot90;			// Y decreasing
			} else
			{											// x2<x1
				if (listLast.from.y >= listP.from.y)
					tMatrix = xfRot270;					// Y increasing
						else tMatrix = xfMirrorXRot90;	// Y decreasing
			}
			val1 = fromLine = fromLine * tMatrix.t12;
			val2 = toLine = toLine * tMatrix.t12;
		} else if (routDirection == ROUTEINY)
		{
			// route in y direction
			if (listP.to.y >= listP.from.y)
			{											// y2>y1
				if (listLast.from.x >= listP.from.x)
					tMatrix = xfNoRot;					// X increasing
						else tMatrix = xfMirrorX;		// X decreasing
			} else
			{											// y2<y1
				if (listLast.from.x >= listP.from.x)
					tMatrix = xfMirrorY;				// X increasing
						else tMatrix = xfRot180;		// X decreasing
			}
			val1 = fromLine = fromLine * tMatrix.t22;
			val2 = toLine = toLine * tMatrix.t22;
		} else
		{
			System.out.println("River router: Not between two parallel lines");
			return false;		// not on manhattan parallel lines
		}

		// check ordering of coordinates
		for(int i=0; i<numRDesc-1; i++)
		{
			RDESC lList = rdescList.get(i);
			RDESC lListNext = rdescList.get(i+1);

			// make sure there are no crossings
			if (routDirection == ROUTEINY)
			{
				if ((lList.from.x > lListNext.from.x && lList.to.x < lListNext.to.x) ||
					(lList.from.x < lListNext.from.x && lList.to.x > lListNext.to.x))
				{
					System.out.println("River router: Connections may not cross");
					return false;
				}
			} else
			{
				if ((lList.from.y > lListNext.from.y && lList.to.y < lListNext.to.y) ||
					(lList.from.y < lListNext.from.y && lList.to.y > lListNext.to.y))
				{
					System.out.println("River router: Connections may not cross");
					return false;
				}
			}
		}

		double bound1 = routBoundLX * tMatrix.t11 + routBoundLY * tMatrix.t21;
		double bound2 = routBoundHX * tMatrix.t11 + routBoundHY * tMatrix.t21;
		if (bound2 < bound1)
		{
			double temp = bound2;   bound2 = bound1;   bound1 = temp;
		}
		RPOINT lastFrom = null;   RPOINT lastTo = null;

		// transform points and clip to boundary
		for(RDESC lList : rdescList)
		{
			lList.from.first = (lList.from.x * tMatrix.t11) + (lList.from.y * tMatrix.t21);
			lList.from.second = (lList.from.x * tMatrix.t12) + (lList.from.y * tMatrix.t22);
			lList.to.first = (lList.to.x * tMatrix.t11) + (lList.to.y * tMatrix.t21);
			lList.to.second = (lList.to.x * tMatrix.t12) + (lList.to.y * tMatrix.t22);
			if (lList.from.second != val1) clipWire(lList.from, bound1, bound2);
			if (lList.to.second != val2) clipWire(lList.to, bound1, bound2);

			if (lastFrom != null && lList.from.side == RPOINT.SIDE1)
			{
				double diff1 = Math.abs(lastFrom.first - lList.from.first);
				if (diff1 < width+space)
				{
					System.out.println("River router: Ports not design rule distance apart");
					return false;
				}
			}
			if (lastTo != null && lList.to.side == RPOINT.SIDE3)
			{
				double diff2 = Math.abs(lastTo.first - lList.to.first);
				if (diff2 < width+space)