equivrecord.java

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

/* -*- tab-width: 4 -*-
 *
 * Electric(tm) VLSI Design System
 *
 * File: EquivRecord.java
 *
 * Copyright (c) 2003 Sun Microsystems and Static Free Software
 *
 * Electric(tm) is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Electric(tm) is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Electric(tm); see the file COPYING.  If not, write to
 * the Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, Mass 02111-1307, USA.
 */
// updated to new view of trees, 16 Jan 2004
// Annotated by Ivan Sutherland, 30 January 2004

package com.sun.electric.tool.ncc.trees;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import com.sun.electric.tool.generator.layout.LayoutLib;
import com.sun.electric.tool.ncc.NccGlobals;
import com.sun.electric.tool.ncc.lists.LeafList;
import com.sun.electric.tool.ncc.lists.RecordList;
import com.sun.electric.tool.ncc.netlist.NetObject;
import com.sun.electric.tool.ncc.processing.NewLocalPartitionWires;
import com.sun.electric.tool.ncc.result.EquivRecReport.EquivRecReportable;
import com.sun.electric.tool.ncc.result.NetObjReport.NetObjReportable;
import com.sun.electric.tool.ncc.strategy.Strategy;

/** Leaf EquivRecords hold Circuits. Internal EquivRecords hold offspring.
 * Every EquivRecord is assigned a pseudo random code at birth which it 
 * retains for life. 
 * <p>
 * A Leaf EquivRecord is "balanced" if all Circuits have the same number of 
 * NetObjects. "Matched" means balanced with each Circuit having one 
 * NetObject. "Mismatched" means unbalanced with some some Circuit having 
 * no NetObject. "Active" means not matched and not mismatched. */
public class EquivRecord implements EquivRecReportable {
	/** Get all NetObjects contained by an EquivRecord subtree. 
	 * The NetObjects found in matched EquivRecords are collected 
	 * separately from NetObjects found in not-matched EquivRecords. */
	private static class GetNetObjs extends Strategy {
		private int numDesigns = -1;
//		private NetObject.Type  type = null;
		private final List<List<NetObject>> matches = 
									new ArrayList<List<NetObject>>();
		private final List<List<NetObject>> notMatches = 
									new ArrayList<List<NetObject>>();
		
//		private void checkType(NetObject n) {
//			NetObject.Type t = n.getNetObjType();
//			if (type==null) type=t;
//			LayoutLib.error(type!=t, "different types in same EquivRecord");
//			LayoutLib.error(type!=NetObject.Type.PART &&
//					        type!=NetObject.Type.WIRE,
//					        "expecting only Parts or Wires");
//		}
		
		private void appendNetObjsFromCircuit(List<List<NetObject>> lists, 
				                              EquivRecord er) {
			int i=0;
			for (Iterator<Circuit> itC=er.getCircuits(); itC.hasNext(); i++) {
				Circuit ckt = (Circuit) itC.next();
				for (Iterator<NetObject> itN=ckt.getNetObjs(); itN.hasNext();) {
					lists.get(i).add(itN.next());
				}
			}
			LayoutLib.error(i!=numDesigns, "wrong number of circuits");
		}
		
		@Override public LeafList doFor(EquivRecord er) {
			if (er.isLeaf()) {
				if (numDesigns==-1) {
					// We've encountered the first leaf EquivRec. Now we
					// can initialize the Lists.
					numDesigns = er.numCircuits();
					for (int i=0; i<numDesigns; i++) {
						matches.add(new ArrayList<NetObject>());
						notMatches.add(new ArrayList<NetObject>());
					}
				}
				appendNetObjsFromCircuit(er.isMatched() ? matches : notMatches, er);
				return new LeafList();
			} else {
				return super.doFor(er);
			}
		}
		
		// ------------------------- intended interface -----------------------
		public GetNetObjs(EquivRecord er) {
			super(null);
			doFor(er);
		}
		
		/**  @return one list per Circuit. Each list contains all the matched
		 * NetObjects in that circuit. For all these lists, elements at the
		 * same index matched. */
		public List<List<NetObject>> getMatchedNetObjs() {return matches;}
		
		/** @return one list per Circuit. Each list contains all not-matched
		 * NetObjects in that circuit. */
		public List<List<NetObject>> getNotMatchedNetObjs() {
			return notMatches;
		}
		//public boolean hasParts() {return type==NetObject.Type.PART;}
	}

	// points toward root 	             
	private EquivRecord parent;
	
	// the immutable random code
	private int randCode;
	
	// int that distinguished this Record
	private int value;
	
	// comment describing the metric used to partition my parent into my 
	// siblings and me
	private String partitionReason;
	
	// description of Wire PortInst connections
	private NewLocalPartitionWires.Signature wireSignature; 
	 
	// At any given time only one of this lists is non-null
	private RecordList offspring;
	private List<Circuit> circuits;

	private static void error(boolean pred, String msg) {
		LayoutLib.error(pred, msg);
	}

	/** For a leaf record, apply strategy to build one Map for each Circuit
	 * @param js
	 * @return list of Maps */
	private ArrayList<HashMap<Integer,List<NetObject>>> getOneMapPerCircuit(Strategy js) {
		ArrayList<HashMap<Integer,List<NetObject>>> mapPerCkt = new ArrayList<HashMap<Integer,List<NetObject>>>();
		for (Iterator<Circuit> it=getCircuits(); it.hasNext();) {
			Circuit ckt = it.next();
			HashMap<Integer,List<NetObject>> codeToNetObjs = js.doFor(ckt);
			mapPerCkt.add(codeToNetObjs);
		}
		return mapPerCkt;
	}

	/** Get all the keys of all the maps.
	 * @param mapPerCkt list of maps
	 * @return the set of all keys from all the maps */
	private Set<Integer> getKeysFromAllMaps(ArrayList<HashMap<Integer,List<NetObject>>> mapPerCkt) {
		Set<Integer> keys = new HashSet<Integer>();
		for (HashMap<Integer,List<NetObject>> map : mapPerCkt) {
			keys.addAll(map.keySet());
		}
		return keys;    	
	}

	/** Create a leaf record for all the Circuits corresponding to a
	 * given key. If a map has a list of NetObjects for the given key
	 * then create a Circuit containing those NetObjects.
	 * Otherwise, add an empty Circuit to the EquivRecord.
	 * @param mapPerCkt ArrayList of maps.  Each map maps: 
	 * (Integer -> ArrayList of NetObjects)
	 * @param key check each map for a List of NetObjects at this key 
	 * @return a EquivRecord */
	private EquivRecord makeEquivRecForKey(ArrayList<HashMap<Integer,List<NetObject>>> mapPerCkt, Integer key, NccGlobals globals) {
		List<Circuit> ckts = new ArrayList<Circuit>();
		for (HashMap<Integer,List<NetObject>> map : mapPerCkt) {
			ArrayList<NetObject> netObjs = (ArrayList<NetObject>) map.get(key);
			if (netObjs==null)  netObjs = new ArrayList<NetObject>();
			ckts.add(Circuit.please(netObjs));
		}
		return EquivRecord.newLeafRecord(key.intValue(), ckts, globals);												 	
	}

	/** constructor*/
	private EquivRecord(){}
	
	private void addOffspring(EquivRecord r) {
		offspring.add(r);
		r.setParent(this);
	}

	private LeafList applyToLeaf(Strategy js) {
		ArrayList<HashMap<Integer,List<NetObject>>> mapPerCkt = getOneMapPerCircuit(js);
		
		Set<Integer> keys = getKeysFromAllMaps(mapPerCkt);
		
		error(keys.size()==0, "must have at least one key");
		
		// If everything maps to one hash code then no offspring
		if (keys.size()==1) return new LeafList();
		
		// Change this record from leaf to internal
		circuits = null;
		offspring = new RecordList();
		
		for (Integer key : keys) {
			EquivRecord er = makeEquivRecForKey(mapPerCkt, key, js.globals); 
			addOffspring(er);
		}
		

		LeafList el = new LeafList();
		el.addAll(offspring);
		return el;
	}

	private LeafList applyToInternal(Strategy js) {
		LeafList offspring = new LeafList();
		for (Iterator<EquivRecord> it=getOffspring(); it.hasNext();) {
			EquivRecord jr= it.next();
			offspring.addAll(js.doFor(jr));
		}
		return offspring;
	}

	// --------------------------- public methods -----------------------------
	/** @return internal EquivRecord that contains me */
	public EquivRecord getParent() {return parent;}

	/** getCode returns the fixed hash code for this object.
	 * @return the int fixed hash code for this object. */
	public int getCode(){return isMismatched()? 0 : randCode;}

    public void checkMe(EquivRecord parent) {
    	error(getParent()!=parent, "wrong parent");
    	error(!(offspring==null ^ circuits==null), "bad lists");
    }

	public void setParent(EquivRecord x) {parent=x;}
	
	/** get the value that a strategy used to distinguish
	 * this EquivRecord.
	 * @return the int value that distinguished this EquivRecord */
	public int getValue(){return value;}