source: branches/dev-jw-2590/Compiler/ModelicaMiddleEnd/src/jastadd/structural/Graphs.jadd @ 13960

Last change on this file since 13960 was 13960, checked in by jwedin, 4 weeks ago

Changed so the template sets no longer are static. The memberSets field of the HomotopyContributor is now unmodifiable. #5865

File size: 77.9 KB
Line 
1/*
2    Copyright (C) 2009 Modelon AB
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, version 3 of the License.
7
8    This program is distributed in the hope that it will be useful,
9    but WITHOUT ANY WARRANTY; without even the implied warranty of
10    GNU General Public License for more details.
11
12    You should have received a copy of the GNU General Public License
13    along with this program.  If not, see <http://www.gnu.org/licenses/>.
14*/
15
16import java.util.ArrayList;
17import java.util.Collection;
18import java.util.Collections;
19import java.util.Iterator;
20import java.util.LinkedHashMap;
21import java.util.LinkedHashSet;
22import java.util.LinkedList;
23import java.util.ListIterator;
24import java.util.Map;
25import java.util.TreeMap;
26import java.util.Random;
27import java.util.Set;
28import java.util.Stack;
29import java.util.EnumSet;
30
31import org.jmodelica.util.collections.ListMap;
32import org.jmodelica.util.collections.LinkedHashListMap;
33import org.jmodelica.util.collections.FilteredIterator;
34import org.jmodelica.util.collections.HashStack;
35
36import org.jmodelica.util.tarjan.Tarjan;
37import org.jmodelica.util.tarjan.SimpleTarjan;
38import org.jmodelica.util.tarjan.TarjanComponent;
39
40aspect Graphs {
41
42public abstract class AbstractBiPGraph<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>> {
43
44    private static final String DEFAULT_EQ_PREFIX = "eq_";
45    private static final String DEFAULT_EQ_SUBFIX = "";
46   
47    protected Map<String, V> variableMap = new LinkedHashMap<String, V>();
48    protected Map<String, E> equationMap = new LinkedHashMap<String, E>();
49    protected ListMap<FAbstractEquation, E> equationIndexMap = new LinkedHashListMap<FAbstractEquation, E>();
50    private boolean initialSystem = false;
51    private Enumerator enumerator = new Enumerator(1);
52
53    public AbstractBiPGraph() {
54    }
55
56    public <E_OTHER extends AbstractEq<E_OTHER, V_OTHER>, V_OTHER extends AbstractVar<E_OTHER, V_OTHER>> AbstractBiPGraph(Collection<E_OTHER> eqs, Collection<V_OTHER> vars) {
57        for (E_OTHER oldE : eqs)
58            addEquation(oldE.getEquation(), oldE.groupNumber(), oldE.variability(), oldE.type(), oldE.isMeta(), oldE.getName());
59        for (V_OTHER oldV : vars)
60            addVariable(oldV.getName(), oldV.getVariable());
61        for (E_OTHER oldE : eqs) {
62            E e = getEquation(oldE.getName());
63            for (V_OTHER oldV : oldE.getVariables()) {
64                V v = getVariable(oldV.getName());
65                if (v != null)
66                    addInsidence(e, v);
67            }
68        }
69    }
70
71    public <E_OTHER extends AbstractEq<E_OTHER, V_OTHER>, V_OTHER extends AbstractVar<E_OTHER, V_OTHER>> AbstractBiPGraph(Collection<E_OTHER> block, boolean isInitial) {
72        this(block, collectMatchingVariables(block));
73        initialSystem = isInitial;
74        for (E_OTHER e : block) {
75            if (!e.isMeta()) {
76                match(getEquation(e.getName()), getVariable(e.getMatching().getName()));
77            }
78        }
79    }
80
81    private static <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<V> collectMatchingVariables(Collection<E> eqns) {
82        Collection<V> vars = new ArrayList<V>();
83        for (E e : eqns) {
84            if (!e.isMeta()) {
85                vars.add(e.getMatching());
86            }
87        }
88        return vars;
89    }
90
91    public boolean isComplete() {
92        return getUnmatchedVariables().size() == 0 && getUnmatchedEquations().size() == 0;
93    }
94
95    public Collection<E> getEquations() {
96        return equationMap.values();
97    }
98
99    public Collection<V> getVariables() {
100        return variableMap.values();
101    }
102
103    public E getEquation(String name) {
104        return equationMap.get(name);
105    }
106
107    public void setAsInitialSystem() {
108        initialSystem = true;
109        for (E eqn : getEquations()) {
110            if (eqn.groupNumber() != 0) {
111                continue;
112            }
113            for (V var : lookupVars(eqn.getEquation().findInitUniqueDAEVarUsesInTree())) {
114                for (E groupEqn : eqn.getGroupMembers()) {
115                    addEdge(groupEqn, var);
116                }
117            }
118        }
119    }
120
121    public boolean isInitialSystem() {
122        return initialSystem;
123    }
124   
125    public java.util.List<E> getEquations(FAbstractEquation eqn) {
126        return equationIndexMap.getList(eqn);
127    }
128
129    private E addEquation(FAbstractEquation eqn, int groupNumber, TypePrefixVariability variability, FType type, boolean isMeta, String prefix, String subfix, Enumerator enumerator) {
130        String name;
131        do {
132            name = prefix + enumerator.next() + subfix;
133        } while (getEquation(name) != null);
134        return addEquation(eqn, groupNumber, variability, type, isMeta, name);
135    }
136
137    protected E addEquation(FAbstractEquation eqn, int groupNumber, Collection<E> groupMemberList, TypePrefixVariability variability, FType type, String name) {
138        return addEquation(eqn, groupNumber, groupMemberList, variability, type, false, name);
139    }
140
141    protected E addEquation(FAbstractEquation eqn, int groupNumber, TypePrefixVariability variability, FType type, boolean isMeta, String name) {
142        return addEquation(eqn, groupNumber, equationIndexMap.getList(eqn, true), variability, type, isMeta, name);
143    }
144
145    protected E addEquation(FAbstractEquation eqn, int groupNumber, Collection<E> groupMemberList, TypePrefixVariability variability, FType type, boolean isMeta, String name) {
146        E e = equationMap.get(name);
147        if (e != null)
148            throw new IllegalArgumentException("Equation with the name '" + name + "' already exists:\n" + e.getEquation() + "\nNew equation:\n" + eqn);
149        e = createEq(name, eqn, groupNumber, groupMemberList, variability, type, isMeta);
150        equationMap.put(name,e);
151        insertIntoEquationIndexMap(eqn,e);
152        return e;
153    }
154
155    protected abstract E createEq(String name, FAbstractEquation eqn, int groupNumber, Collection<E> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta);
156
157    public V addVariable(FVariable var) {
158        return addVariable(var.name(), var);
159    }
160
161    public V addVariable(String name, FVariable var) {
162        V v = variableMap.get(name);
163        if (v==null) {
164            v = createVar(name, var);
165            variableMap.put(name,v);
166        }       
167        return v;
168    }
169
170    protected abstract V createVar(String name, FVariable var);
171
172    public void removeEquation(E e) {
173        for (V v : e.getVariables()) {
174            if (v.getMatching() == e) {
175                v.setMatching(null);
176            }
177        }
178        e.setMatching(null);
179        e.getVariables().clear();
180        equationMap.remove(e.getName());
181        removeFromEquationIndexMap(e.getEquation(),e);
182    }
183
184    public void removeVariable(V v) {
185        for (E e : getEquations()) {
186            if (e.getMatching() == v) {
187                e.setMatching(null);
188            }
189            e.getVariables().remove(v);
190        }
191        v.setMatching(null);
192        variableMap.remove(v.getName());
193    }
194
195    public void removeVariables(Collection<? extends FVariable> fVars) {
196        for (FVariable fVar : fVars) {
197            V var = getVariable(fVar.name());
198            if (var != null)
199                removeVariable(var);
200        }
201    }
202   
203    public V getVariable(String name) {
204        return variableMap.get(name);
205    }
206
207    public final boolean addEdge(String equationName, String variableName) {
208        return addEdge(getEquation(equationName), getVariable(variableName));
209    }
210
211    public boolean addEdge(E e, V v) {
212        if (v==null || e==null)
213            return false;
214        if (e.getVariables().contains(v))
215            return false;
216        e.addVariable(v);
217        return true;
218    }
219
220    public enum VarType {
221        DERIVATIVE_VARIABLES { 
222            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.derivativeVariables(); }
223            public boolean isOk(TypePrefixVariability variability)               { return variability.continuousVariability(); }
224        },
225        DIFFERENTIATED_VARIABLES { 
226            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.allDifferentiatedRealVariables(); }
227            public boolean isOk(TypePrefixVariability variability)               { return variability.continuousVariability(); }
228        }, 
229        ALGEBRAIC_VARIABLES { 
230            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.normalAlgebraicVariables(); }
231        }, 
232        CONTINUOUS_ALGEBRAIC_VARIABLES { 
233            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.normalAlgebraicContinousRealVariables(); }
234            public boolean isOk(TypePrefixVariability variability)               { return variability.continuousVariability(); }
235        }, 
236        DISCRETE_ALGEBRAIC_VARIABLES { 
237            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.discreteVariables(); }
238            public boolean isOk(TypePrefixVariability variability)               { return variability.discreteVariability(); }
239        }, 
240        DISCRETE_PRE_VARIABLES { 
241            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.discretePreVariables(); }
242            public boolean isOk(TypePrefixVariability variability)               { return variability.discreteVariability(); }
243        },
244        NON_FIXED_PARAMETERS {
245            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.initialParameters(); }
246            public boolean isOk(TypePrefixVariability variability)               { return variability.parameterVariability(); }
247        };
248
249        public abstract Collection<? extends FVariable> variables(BLTVariables c);
250        public boolean isOk(TypePrefixVariability e) { return true; }
251    }
252
253    public void addVariables(BLTVariables variables, EnumSet<VarType> variableTypes) {
254        for (VarType t : variableTypes) {
255            for (FVariable fv : t.variables(variables)) {
256                addVariable(fv.name(), fv);
257            }
258        }
259        for (FVariable fv : variables.extraVariables()) {
260            addVariable(fv.name(), fv);
261        }
262    }
263
264    public void addEquations(Iterable<FAbstractEquation> eqns, EnumSet<VarType> variableTypes) {
265        do_addEquations(eqns, variableTypes, DEFAULT_EQ_PREFIX, enumerator);
266    }
267
268    public void addEquations(Iterable<FAbstractEquation> eqns, EnumSet<VarType> variableTypes, String eqNamePrefix, Enumerator enumerator) {
269        if (eqNamePrefix.equals(DEFAULT_EQ_PREFIX))
270            throw new IllegalArgumentException("The equation name prefix '" + eqNamePrefix + "' is reserved!");
271        do_addEquations(eqns, variableTypes, eqNamePrefix, enumerator);
272    }
273
274    private void do_addEquations(Iterable<FAbstractEquation> eqns, EnumSet<VarType> variableTypes, String eqNamePrefix, Enumerator enumerator) {
275        Set<FVariable> emptySet = Collections.emptySet();
276        for (FAbstractEquation e : eqns) {
277           
278            IncidenceMap incMap = e.createIncidenceMap(this, variableTypes);
279            int n_eq = incMap.numEqs();
280           
281            Collection<E> groupMembers = getEquations(e);
282            int n_existing = 0;
283            int n_existing_meta = 0;
284            for (E eqn : groupMembers) {
285                n_existing += 1;
286                if (eqn.isMeta()) {
287                    n_existing_meta++;
288                }
289            }
290            if (n_existing != 0 && (n_existing - n_existing_meta) != n_eq) {
291                throw new IllegalArgumentException("Equation already exist in BiPGraph but with different number of scalars, previously " + n_existing + ", now " + n_eq + ", equation:\n" + e);
292            }
293            if (n_existing == 0) {
294                groupMembers = new ArrayList<E>();
295                Enumerator subEnumerator = enumerator;
296                String prefix = eqNamePrefix;
297                String subfix = "";
298                if (n_eq > 1) {
299                    subEnumerator = new Enumerator(1);
300                    prefix += enumerator.next() + "[";
301                    subfix = "]";
302                }
303                if (n_eq == 0) {
304                    E eqn = addEquation(e, 0, incMap.variability(0), incMap.type(0), true, prefix, subfix, subEnumerator);
305                    groupMembers.add(eqn);
306                } else {
307                    for (int i = n_eq - 1; 0 <= i; i--) { // During tarjan the order will be reversed,
308                        // need to reverse here to preserve the initial order.
309                        E eqn = addEquation(e, i, incMap.variability(i), incMap.type(i), false, prefix, subfix, subEnumerator);
310                        groupMembers.add(eqn);
311                    }
312                }
313            }
314            for (E eqn : groupMembers) {
315                incMap.addEdges(eqn, false);
316            }
317        }
318    }
319   
320    protected CommonAccessExpLookupVisitor<FAccessExp> getCommonAccessExpLookupVisitor() {
321        if (isInitialSystem()) {
322            return InitDAEVarUseLookupVisitor.instance;
323        } else {
324            return DAEVarUseLookupVisitor.instance;
325        }
326    }
327   
328    /**
329     * Handles incidences between variables in an FAbstractEquation.
330     * The base case is a scalar equation where all variables are
331     * dependent on each other.
332     */
333    protected class IncidenceMap {
334        private Set<V> vars = null;
335        protected final FAbstractEquation equation;
336        protected final VariableResolver<E, V> resolver;
337       
338        public IncidenceMap(FAbstractEquation e, VariableResolver<E, V> resolver) {
339            equation = e;
340            this.resolver = resolver;
341        }
342       
343        protected Set<V> vars() {
344            if (vars == null) {
345                vars = resolver.lookupVars(equation.findCommonAccessExpsInTree(getCommonAccessExpLookupVisitor()));
346            }
347            return vars;
348        }
349       
350        public TypePrefixVariability variability(int i) {
351            return equation.variability();
352        }
353       
354        public FType type(int i) {
355            return equation.type();
356        }
357       
358        public void addEdges(E eqn, boolean log) {
359            for (V var : vars()) {
360                if (log) {
361                    getStepLogger().logVerbose("*** %s", var);
362                }
363                addEdge(eqn, var);
364            }
365        }
366       
367        public int numEqs() {
368            return equation.numScalarEquations();
369        }
370    }
371   
372    /**
373     * An interface that should be implemented by all IncidenceMap classes that
374     * represent an equation which only has one or more variables on the left hand
375     * side (one variable on the left hand side per scalar equation)
376     */
377    protected interface AssignmentIncidenceMap {
378        public Iterable<FAccessExp> rhs(String assignedLHS);
379        public Collection<FAccessExp> assigned();
380    }
381   
382    /**
383     * Handles normal equations which are on the form "x = ...".
384     */
385    protected class SingleAssignmentIncidenceMap extends IncidenceMap implements AssignmentIncidenceMap {
386        private final FAccessExp assigned;
387        private Collection<FAccessExp> rhsUses;
388       
389        public SingleAssignmentIncidenceMap(FEquation eqn, VariableResolver<E, V> resolver) {
390            super(eqn, resolver);
391            assigned = eqn.getLeft().asFAccessExp();
392           
393        }
394       
395        private Collection<FAccessExp> rhsUses() {
396            if (rhsUses == null) {
397                rhsUses = equation.FAccessExpsInRHS(getCommonAccessExpLookupVisitor());
398            }
399            return rhsUses;
400        }
401       
402        @Override
403        public Iterable<FAccessExp> rhs(String assignedLHS) {
404            if (assignedLHS.equals(assigned.name())) {
405                return rhsUses();
406            } else {
407                return Collections.emptyList();
408            }
409        }
410       
411        @Override
412        public Collection<FAccessExp> assigned() {
413            return Collections.singletonList(assigned);
414        }
415    }
416   
417    /**
418     * Handles incidences between variables in a non-scalar FAbstractEquation.
419     * Isolates LHS variables from each other.
420     */
421    protected abstract class MultiIncidenceMap extends IncidenceMap {
422        private Map<Integer, V> lhs = null;
423        private Set<FAccessExp> lhsUses = null;
424        protected final EnumSet<VarType> variableTypes;
425       
426        public MultiIncidenceMap(FAbstractEquation e, VariableResolver<E, V> resolver, EnumSet<VarType> variableTypes) {
427            super(e, resolver);
428            this.variableTypes = variableTypes;
429        }
430       
431        protected Set<FAccessExp> lhsUses() {
432            if (lhsUses == null) {
433                lhsUses = equation.FAccessExpsInLHS(getCommonAccessExpLookupVisitor());
434            }
435            return lhsUses;
436        }
437       
438        protected abstract void computeLHS(Map<Integer, V> lhs);
439       
440        protected Map<Integer, V> lhs() {
441            if (lhs == null) {
442                Map<Integer, V> lhsTmp = new HashMap<Integer, V>();
443                computeLHS(lhsTmp);
444                lhs = lhsTmp;
445            }
446            return lhs;
447        }
448       
449        protected void buildLhsFunction(Map<Integer, V> lhs, EnumSet<VarType> variableTypes) {
450            int i = 0;
451            for (FAccessExp use : lhsUses()) {
452                if (variableTypes != null) {
453                    FAbstractVariable fv = use.myFV();
454                    if (fv != null && !addLhs(fv, variableTypes)) {
455                        continue;
456                    }
457                }
458                buildLhsFunction(lhs, use, i++);
459            }
460        }
461       
462        protected void buildLhsFunction(Map<Integer, V> lhs, FAccessExp use, int i) {
463            V var = getVariable(use.name());
464            lhs.put(i, var);
465        }
466       
467        protected boolean addLhs(FAbstractVariable fv, EnumSet<VarType> variableTypes) {
468            for (VarType t : variableTypes) {
469                if (t.isOk(variability(fv))) {
470                    return true;
471                }
472            }
473            return false;
474        }
475       
476        @Override
477        public TypePrefixVariability variability(int i) {
478            V var = lhs().get(i);
479            if (var == null) {
480                return super.variability(i);
481            }
482            return variability(var.getVariable());
483        }
484       
485        private TypePrefixVariability variability(FAbstractVariable fv) {
486            TypePrefixVariability v = fv.variability();
487            if (v.parameterOrLess()) {
488                v = fv.type().funcOutputVariability();
489            }
490            return v;
491        }
492       
493        @Override
494        public FType type(int i) {
495            V var = lhs().get(i);
496            if (var == null) {
497                return super.type(i);
498            }
499            return var.type();
500        }
501       
502        @Override
503        public void addEdges(E eqn, boolean log) {
504            int i = eqn.groupNumber();
505            V lhsVar = lhs().get(i);
506            for (V var : vars()) {
507                if (var == lhsVar || rhs(i).contains(var)) {
508                    addEdge(eqn, var);
509                }
510            }
511        }
512
513        protected abstract Set<V> rhs(int i);
514
515        @Override
516        public int numEqs() {
517            return lhs().size();
518        }
519    }
520   
521    /**
522     * Handles incidences between variables in a non-scalar FAbstractEquation.
523     * Isolates LHS variables from each other.
524     * Assumes all LHS variables are dependent on all RHS variables.
525     */
526    protected class ManyIncidenceMap extends MultiIncidenceMap {
527       
528        private Set<V> rhs = null;
529       
530        public ManyIncidenceMap(FAbstractEquation e, VariableResolver<E, V> resolver, EnumSet<VarType> variableTypes) {
531            super(e, resolver, variableTypes);
532        }
533       
534        protected Set<V> rhs() {
535            if (rhs == null) {
536                rhs = resolver.lookupVars(equation.FAccessExpsInRHS());
537                if (equation instanceof FAlgorithm) {
538                    rhs.removeAll(resolver.lookupVars(lhsUses()));
539                }
540            }
541            return rhs;
542        }
543       
544        protected void computeLHS(Map<Integer, V> lhs) {
545            if (equation instanceof FFunctionCallEquation) {
546                buildLhsFunction(lhs, variableTypes);
547            } else {
548                buildLhsOther(lhs, variableTypes);
549            }
550        }
551       
552        private void buildLhsOther(Map<Integer, V> lhs, EnumSet<VarType> variableTypes) {
553            int i = 0;
554            for (FAbstractVariable fv : ASTNode.lookupFVariablesInSet(lhsUses())) {
555                if (variableTypes != null) {
556                    if (!addLhs(fv, variableTypes)) {
557                        continue;
558                    }
559                }
560               
561                V var = getVariable(fv.name());
562                lhs.put(i++, var);
563            }
564        }
565       
566        @Override
567        protected Set<V> rhs(int i) {
568            return rhs();
569        }
570    }
571   
572    /**
573     * Handles incidences between variables in a non-scalar FAbstractEquation.
574     * Isolates LHS variables from each other.
575     * Computes RHS dependencies for LHS.
576     */
577    protected class SplitIncidenceMap extends MultiIncidenceMap implements AssignmentIncidenceMap {
578        protected ArrayList<Set<V>> splitMap;
579        protected Map<FAccessExp, Collection<FAccessExp>> resolvedDependencies;
580        private Map<String, FAccessExp> nameToAssignedMap;
581       
582        public SplitIncidenceMap(FFunctionCallEquation e, VariableResolver<E, V> resolver, EnumSet<VarType> variableTypes) {
583            super(e, resolver, variableTypes);
584        }
585       
586        private Map<FAccessExp, Collection<FAccessExp>> sortDependencies(Map<FAccessExp, Set<FAccessExp>> unsortedDependencies) {
587            final Map<String, Integer> varToPosMap = new HashMap<String, Integer>();
588            int counter = 0;
589            for (FAccessExp use : equation.FAccessExpsInRHS()) {
590                if (!varToPosMap.containsKey(use.name())) {
591                    varToPosMap.put(use.name(), counter++);
592                }
593            }
594            Map<FAccessExp, Collection<FAccessExp>> resolvedDependencies = new HashMap<>();
595            for (Map.Entry<FAccessExp, Set<FAccessExp>> entry : unsortedDependencies.entrySet()) {
596                ArrayList<FAccessExp> uses = new ArrayList<>(entry.getValue());
597                Collections.sort(uses, new Comparator<FAccessExp>() {
598                    public int compare(FAccessExp a, FAccessExp b) {
599                        return varToPosMap.get(a.name()) - varToPosMap.get(b.name());
600                    }
601                });
602                resolvedDependencies.put(entry.getKey(), uses);
603            }
604            return resolvedDependencies;
605        }
606       
607        protected Map<FAccessExp, Collection<FAccessExp>> resolvedDependencies() {
608            if (resolvedDependencies == null) {
609                DependencyVariableEvaluator pve = new DependencyVariableEvaluator();
610                FFunctionCallEquation equation = (FFunctionCallEquation) this.equation;
611                try {
612                    equation.getCall().evaluate(pve);
613                    Map<FAccessExp, Set<FAccessExp>> unsortedDependencies = pve.resolveDependencies(equation);
614                    resolvedDependencies = sortDependencies(unsortedDependencies);
615                } catch (ConstantEvaluationException e) {
616                    ASTNode.log.debug("SplitIncidenceMap failed to compute dependency information, falling back to normal heuristics!");
617                    resolvedDependencies = new HashMap<FAccessExp, Collection<FAccessExp>>();
618                    Collection<FAccessExp> rhs = equation.FAccessExpsInRHS();
619                    for (FAccessExp lhs : lhsUses()) {
620                        resolvedDependencies.put(lhs, rhs);
621                    }
622                }
623            }
624            return resolvedDependencies;
625        }
626       
627        protected Map<String, FAccessExp> nameToAssignedMap() {
628            if (nameToAssignedMap == null) {
629                nameToAssignedMap = new HashMap<>();
630                for (FAccessExp use : lhsUses()) {
631                    FAccessExp old = nameToAssignedMap.put(use.name(), use);
632                    if (old != null) {
633                        throw new UnsupportedOperationException("The following equation assignes the same variable twice, " + old + ", this class doesn't handle that:\n" + equation);
634                    }
635                }
636            }
637            return nameToAssignedMap;
638        }
639       
640   
641        @Override
642        protected void computeLHS(Map<Integer, V> lhs) {
643            splitMap = new ArrayList<Set<V>>();
644            buildLhsFunction(lhs, variableTypes);
645        }
646       
647        @Override
648        protected void buildLhsFunction(Map<Integer, V> lhs, FAccessExp use, int i) {
649            super.buildLhsFunction(lhs, use, i);
650            Set<V> s = resolver.lookupVars(resolvedDependencies().get(use));
651            splitMap.add(s);
652        }
653
654        @Override
655        protected Set<V> rhs(int i) {
656            lhs(); // Just ensure that splitMap is computed.
657           return splitMap.get(i);
658        }
659
660        @Override
661        public Collection<FAccessExp> assigned() {
662            return lhsUses();
663        }
664
665        @Override
666        public final Iterable<FAccessExp> rhs(String assignedLHS) {
667            FAccessExp use = nameToAssignedMap().get(assignedLHS);
668            if (use == null) {
669                return Collections.emptyList();
670            } else {
671                return resolvedDependencies().get(use);
672            }
673        }
674       
675    }
676   
677   
678    public boolean match(E e, V v) {
679        if (!canMatch(e, v))
680            return false;
681        if (e.getMatching() != null)
682            e.getMatching().setMatching(null);
683        if (v.getMatching() != null)
684            v.getMatching().setMatching(null);
685        v.setMatching(e);
686        e.setMatching(v);
687        return true;
688    }
689
690    public boolean canMatch(E e, V v) {
691        if (e.isMeta())
692            return false;
693       
694        FAbstractEquation equation = e.getEquation();
695        FVariable variable = v.getVariable();
696       
697        if (!variable.isReal() && !equation.isSolved(variable).isAnalyticallySolvable()) {
698            return false;
699        }
700       
701        if (initialSystem)
702            return true;
703       
704        if (equation instanceof FAlgorithm)
705            return true;
706       
707        // Discrete variables can only be matched to discrete equations.
708        // Except discrete reals in initial system.
709        return variable.isContinuous() || e.variability().discreteVariability() || equation.isInitial();
710    }
711
712    public void addInsidence(E e, V v) {
713        e.addVariable(v);
714    }
715
716    public Collection<E> greedyMatching() {
717        Collection<E> unmatched = new ArrayList<E>();
718        for (E e : getEquations()) {
719            if (e.getMatching() != null)
720                continue;
721            for (V v : e.getVariables()) {
722                if (v.getMatching()==null) {
723                    match(e, v);
724                    break;
725                }
726            }
727            if (e.getMatching() == null)
728                unmatched.add(e);
729        }
730        return unmatched;
731    }
732
733    /**
734     * Comparator that is used during matching of variables to equations. We
735     * need to use a comparator during this since we wan't to prioritize
736     * matching of certain variables. For example, when matching the initial
737     * system, there is usually more variables than equations. In that case it
738     * is better to leave a variable with start value unmatched since we then
739     * can use the start value as an extra initial condition (equation).
740     */
741    private static class VarMatchingComparator implements Comparator<AbstractVar<?,?>> {
742        private Set<FAbstractVariable> hasExtraStartConditions;
743        private VarMatchingComparator(Set<FAbstractVariable> hasExtraStartConditions) {
744            if (hasExtraStartConditions == null)
745                hasExtraStartConditions = Collections.emptySet();
746            this.hasExtraStartConditions = hasExtraStartConditions;
747        }
748       
749        /**
750         * Variable o1 will be prefered over o2 by returning a negative number.
751         * This means that o1 will be matched (if possible) before o2, which
752         * means that we wan't to return a positive number for the variables
753         * that we wan't to be unmatched (and used as initial conditions).
754         */
755        @Override
756        public int compare(AbstractVar<?,?> o1, AbstractVar<?,?> o2) {
757            FVariable v1 = o1.getVariable();
758            FVariable v2 = o2.getVariable();
759           
760            // Variables that has an extra start condition (equation already in
761            // the system) should be matched last
762            boolean b1 = (v1.isPreVariable() && hasExtraStartConditions.contains(v1.myNonPreVariable())) || hasExtraStartConditions.contains(v1);
763            boolean b2 = (v2.isPreVariable() && hasExtraStartConditions.contains(v2.myNonPreVariable())) || hasExtraStartConditions.contains(v2);
764            int diff = (b1 ? 1 : 0) - (b2 ? 1 : 0);
765            if (diff != 0)
766                return diff;
767           
768            // Discrete pre() and continuous variables with start value should
769            // be matched last
770            b1 = (v1.isDiscrete() && v1.isPreVariable() || v1.isContinuous()) && v1.startAttributeSet();
771            b2 = (v2.isDiscrete() && v2.isPreVariable() || v2.isContinuous()) && v2.startAttributeSet();
772            diff = (b1 ? 1 : 0) - (b2 ? 1 : 0);
773            if (diff != 0)
774                return diff;
775           
776            // pre() variables should be matched last (why?)
777            diff = (v1.isPreVariable() ? 1 : 0) - (v2.isPreVariable() ? 1 : 0);
778            if (diff != 0)
779                return diff;
780           
781            // Make the sorting deterministic by comparing the names
782            return o1.getName().compareTo(o2.getName());
783        }
784    }
785
786    public java.util.List<Map<V, Set<E>>> bfs(Collection<E> startingNodes, Comparator<? super V> varComparator) {
787        java.util.List<Map<V, Set<E>>> Lv = new ArrayList<Map<V, Set<E>>>();
788        Set<E> Le_current = new LinkedHashSet<E>();
789        Set<E> Le_next = new LinkedHashSet<E>();
790       
791        Le_current.addAll(startingNodes);
792        // Reset nodes
793        lightReset();
794       
795        int layer = 0;
796        boolean freeVarNodeFound = false;
797        //System.out.println("************** BFS ************* starting nodes: " + startingNodes);
798       
799        while (Le_current.size() > 0 && !freeVarNodeFound) {
800            //System.out.println("*** layer: " + layer);
801            //System.out.println(Lv);
802            //System.out.println(Le_current);
803            Lv.add(new TreeMap<V, Set<E>>(varComparator));
804           
805            for (E s : Le_current) {
806                //System.out.println(" eq: " + s);
807                for (V t : s.getVariables()) {
808                    if (!canMatch(s, t))
809                        continue;
810                    //System.out.println("  " + t + " layer: " + t.getLayer());
811                    if (t.getLayer() >= layer) {
812                        //System.out.println("    adding " + t);
813                        t.setLayer(layer);
814                        Set<E> h = Lv.get(layer).get(t);
815                        if (h == null) {
816                            h = new LinkedHashSet<E>();
817                            Lv.get(layer).put(t, h);
818                        }
819                        h.add(s);
820                        E u = t.getMatching();
821                        if (u != null) {
822                            //System.out.println("     " + t + "'s matching is " + u);
823                            u.setLayer(layer);
824                            Le_next.add(u);
825                        } else {
826                            //System.out.println("     " + t + "has no matching");
827                            freeVarNodeFound = true;
828                        }
829                    }
830                }
831            }
832            layer++;
833            Le_current = Le_next;
834            Le_next = new LinkedHashSet<E>();
835        }
836       
837        java.util.List<V> delQueue = new ArrayList<V>();
838        for (V v : Lv.get(Lv.size() - 1).keySet()) {
839            if (v.getMatching() != null) {
840                delQueue.add(v);
841            }
842        }
843        for (V v : delQueue) {
844            Lv.get(Lv.size() - 1).remove(v);
845        }
846        //System.out.println(Lv);
847        //System.out.println("************** BFS ends *************");
848        return Lv;
849    }
850
851    public java.util.List<java.util.List<Edge>> dfs(java.util.List<Map<V, Set<E>>> Lv) {
852        lightReset();
853        java.util.List<java.util.List<Edge>> P = new ArrayList<java.util.List<Edge>>();
854       
855        boolean found_path = true;
856        for (V v : Lv.get(Lv.size() - 1).keySet()) {
857            ArrayList<Edge> P_tmp = new ArrayList<Edge>();
858           
859            ListIterator<Map<V, Set<E>>> iter = Lv.listIterator(Lv.size());
860            while (iter.hasPrevious()) {
861                Map<V, Set<E>> l = iter.previous();
862                v.setVisited(true);
863                if (!found_path) {
864                    break;
865                }
866                found_path = false;
867                for (E e : l.get(v)) {
868                    if (!e.isVisited() && canMatch(e, v)) {
869                        e.setVisited(true);
870                        P_tmp.add(new Edge(e, v));
871                        v = e.getMatching();
872                        found_path = true;
873                        break;
874                    }
875                }
876            }
877            if (P_tmp.size() == Lv.size()) {
878                P.add(P_tmp);
879            }
880        }
881        //System.out.println(P);
882        return P;
883    }
884
885    public void reassign(java.util.List<java.util.List<Edge>> P) {
886        for (java.util.List<Edge> l : P) {
887            for (Edge ed : l) {
888                match(ed.getEquation(), ed.getVariable());
889            }
890        }
891    }
892
893    public void maximumMatching(boolean resetMatching) {
894        maximumMatching(resetMatching, null);
895    }
896
897    public void maximumMatching(boolean resetMatching, Set<FAbstractVariable> hasExtraStartConditions) {
898        if (resetMatching) {
899            reset();
900            greedyMatching();
901        }
902       
903        // Initialize set of free equations
904        Set<E> startingNodes = new LinkedHashSet<E>();
905        for (E e : getEquations()) {
906            if (e.getMatching()==null) {
907                startingNodes.add(e);
908            }
909        }
910       
911        Set<E> unmatchedEquations = new LinkedHashSet<E>(getUnmatchedEquations());
912       
913        java.util.List<Map<V, Set<E>>> Lv = null;
914        java.util.List<java.util.List<Edge>> P = null;
915        Comparator<? super V> varComparator = new VarMatchingComparator(hasExtraStartConditions);
916       
917        while (unmatchedEquations.size()>0) {
918           
919            Lv = bfs(unmatchedEquations, varComparator);
920            P = dfs(Lv);
921           
922            if (Lv.get(Lv.size()-1).size()==0) {
923                break;
924            }
925           
926            reassign(P);
927           
928            for (java.util.List<Edge> l : P) {
929                unmatchedEquations.remove(l.get(l.size()-1).getEquation());
930            }
931        }
932    }
933
934    protected class UnmatchedEquationsCriteria implements Criteria<E> {
935        @Override
936        public boolean test(E elem) {
937            return elem.getMatching() == null && !elem.isMeta();
938        }
939    }
940
941    public Iterator<E> unmatchedEquationsIterator() {
942        return new FilteredIterator<E>(getEquations().iterator(), new UnmatchedEquationsCriteria());
943    }
944
945    public Iterable<E> unmatchedEquationsIterable() {
946        return new Iterable<E>() {
947            @Override
948            public Iterator<E> iterator() {
949                return unmatchedEquationsIterator();
950            }
951        };
952    }
953
954    public Collection<E> getUnmatchedEquations() {
955        java.util.List<E> l = new ArrayList<E>();
956        for (E e : unmatchedEquationsIterable())
957            l.add(e);
958        return l;
959    }
960
961    protected class UnmatchedVariablesCriteria implements Criteria<AbstractVar<?,?>> {
962        @Override
963        public boolean test(AbstractVar<?,?> elem) {
964            return elem.getMatching() == null;
965        }
966    }
967
968    public Iterator<V> unmatchedVariablesIterator() {
969        return new FilteredIterator<V>(getVariables().iterator(), new UnmatchedVariablesCriteria());
970    }
971
972    public Iterable<V> unmatchedVariablesIterable() {
973        return new Iterable<V>() {
974            @Override
975            public Iterator<V> iterator() {
976                return unmatchedVariablesIterator();
977            }
978        };
979    }
980
981    public Collection<V> getUnmatchedVariables() {
982        java.util.List<V> l = new ArrayList<V>();
983        for (V v : unmatchedVariablesIterable())
984            l.add(v);
985        return l;
986    }
987
988    public java.util.List<E> getMatchedEquations() {
989        java.util.List<E> l = new ArrayList<E>();
990        for (E e : getEquations()) {
991            if (e.getMatching()!=null) {
992                l.add(e);
993            }
994        }
995        return l;
996    }
997
998    public java.util.List<V> getMatchedVariables() {
999        java.util.List<V> l = new ArrayList<V>();
1000        for (V v : getVariables()) {
1001            if (v.getMatching()!=null) {
1002                l.add(v);
1003            }
1004        }
1005        return l;
1006    }
1007
1008    public Collection<E> getVisitedEquations() {
1009        Collection<E> l = new ArrayList<E>();
1010        for (E e: getEquations()) {
1011            if (e.isVisited())
1012                l.add(e);
1013        }
1014        return l;
1015    }
1016
1017    public Collection<V> getVisitedVariables() {
1018        Collection<V> l = new ArrayList<V>();
1019        for (V v: getVariables()) {
1020            if (v.isVisited())
1021                l.add(v);
1022        }
1023        return l;
1024    }
1025
1026    private static Collection<SCCContributor> SCCContributors;
1027
1028    /**
1029     * Adds a new strongly connected component contributor to the list of
1030     * contributors.
1031     */
1032    private static <T extends SCCContributor> T addSCCContributor(T contributor) {
1033        if (SCCContributors == null)
1034            SCCContributors = new ArrayList<SCCContributor>();
1035        SCCContributors.add(contributor);
1036        return contributor;
1037    }
1038
1039    /**
1040     * Retrieves the list of strongly connected component contributors.
1041     * This method should always be used since it ensures that the list is
1042     * initialized properly.
1043     */
1044    public static Collection<SCCContributor> getSCCContributors() {
1045        if (SCCContributors == null)
1046            SCCContributors = new ArrayList<SCCContributor>();
1047        return SCCContributors;
1048    }
1049   
1050    /**
1051     * Abstract class for describing arc contributors to Tarjan's strongly
1052     * connected components algorithm.
1053     */
1054    public static abstract class SCCContributor {
1055        private final String option;
1056       
1057        private SCCContributor() {
1058            option = null;
1059        }
1060
1061        private SCCContributor(String option) {
1062            this.option = option;
1063        }
1064
1065        public boolean isActive(StepUtil stepUtil) {
1066            return option == null || stepUtil != null && stepUtil.getOptionRegistry().getBooleanOption(option);
1067        }
1068
1069        /**
1070         * This method returns a list of equations that the supplied equation
1071         * depend on. This method is implemented by the overriding class.
1072         *
1073         * Surounding BiPGraph is provided for convenience
1074         */
1075        public abstract <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> members(E equation, AbstractBiPGraph<E, V, ?> graph);
1076
1077        /**
1078         * This method returns a list of equations that the supplied equation
1079         * should be in the same group as. It is important that there is a
1080         * symmetry in the lists returned. If A return a list containing B and
1081         * C. Then the list for B should contain A and C, finally the list for
1082         * C should contain A and B. Unexepected behaviour otherwise! The list
1083         * for A may contain A itself. This method is implemented by the
1084         * overriding class.
1085         *
1086         * Use this method instead of members() when it is known from the start
1087         * that the lists are symetric. The implementation that backs this
1088         * method is way more efficient for large lists.
1089         *
1090         * Surounding BiPGraph is provided for convenience
1091         */
1092        public abstract <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> sameBlockMembers(E equation, AbstractBiPGraph<E, V, ?> graph);
1093
1094        /**
1095         * This method returns a map that map an equation to a list of object
1096         * identifiers. All equations that are associated with the same object
1097         * identifier are kept in the same block.
1098         *
1099         * Surounding BiPGraph is provided for convenience
1100         */
1101        public abstract <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Map<E, Collection<? extends Object>> memberSets(E equation, AbstractBiPGraph<E, V, ?> graph);
1102       
1103        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>> Collection<C> mergeComponents(Collection<C> components, AbstractBiPGraph<E, V, ?> graph) {
1104            return components;
1105        }
1106    }
1107   
1108    private static final GroupMemberContributor GROUP_MEMBER_CONTRIBUTOR = new GroupMemberContributor();
1109   
1110    /**
1111     * Contributor that describes the relationship between BiPGrah equations
1112     * that link to the same AST equation, for example FFunctionCallEquations.
1113     */
1114    private static class GroupMemberContributor extends SCCContributor {
1115       
1116        @Override
1117        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> members(E equation, AbstractBiPGraph<E, V, ?> graph) {
1118            return Collections.emptyList();
1119        }
1120       
1121        @Override
1122        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> sameBlockMembers(E equation, AbstractBiPGraph<E, V, ?> graph) {
1123            return equation.getGroupMembers();
1124        }
1125
1126       
1127        @Override
1128        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Map<E, Collection<? extends Object>> memberSets(E equation, AbstractBiPGraph<E, V, ?> graph) {
1129            return Collections.emptyMap();
1130        }
1131    }
1132   
1133   
1134    private static final HomotopyContributor HOMOTOPY_CONTRIBUTOR = addSCCContributor(new HomotopyContributor());
1135   
1136    /**
1137     * Contributor that ensures that all equations with homotopy are computed in the same block.
1138     */
1139    private static class HomotopyContributor extends SCCContributor {
1140       
1141        private static final Collection<? extends Object> memberSets = Collections.unmodifiableList(Arrays.asList("homotopy"));
1142       
1143        @Override
1144        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> members(E equation, AbstractBiPGraph<E, V, ?> graph) {
1145            return Collections.emptyList();
1146        }
1147
1148        @Override
1149        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> sameBlockMembers(E equation, AbstractBiPGraph<E, V, ?> graph) {
1150            return Collections.emptyList();
1151        }
1152
1153        @Override
1154        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Map<E, Collection<? extends Object>> memberSets(E equation, AbstractBiPGraph<E, V, ?> graph) {
1155            if (!graph.isInitialSystem() || graph.insideHomotopySimplified() || !equation.getEquation().containsFHomotopyExp()) {
1156                return Collections.emptyMap();
1157            }
1158            Map<E, Collection<? extends Object>> eqsIdentMap = new HashMap<E, Collection<? extends Object>>();
1159            eqsIdentMap.put(equation, memberSets);
1160            return eqsIdentMap;
1161        }
1162    }
1163   
1164    protected abstract C createComponentBlock();
1165
1166    public Collection<C> tarjan(boolean forceGroupMembersIntoSameBlock) {
1167        return tarjan(null, forceGroupMembersIntoSameBlock);
1168    }
1169   
1170
1171    public Collection<C> tarjan(StepUtil stepUtil, boolean forceGroupMembersIntoSameBlock) {
1172        return tarjan(stepUtil, Collections.<SCCContributor>emptyList(), forceGroupMembersIntoSameBlock);
1173    }
1174
1175    public Collection<C> tarjan(StepUtil stepUtil, Collection<SCCContributor> extraContributors,
1176            boolean forceGroupMembersIntoSameBlock) {
1177        tarjanReset();
1178       
1179        Collection<SCCContributor> groupMemberContributors;
1180        if (forceGroupMembersIntoSameBlock) {
1181            groupMemberContributors = Collections.<SCCContributor>singletonList(GROUP_MEMBER_CONTRIBUTOR);
1182        } else {
1183            groupMemberContributors = Collections.<SCCContributor>emptyList();
1184        }
1185       
1186        Collection<SCCContributor> contributors = new ArrayList<SCCContributor>();
1187        for (SCCContributor contributor : new ChainedIterable<SCCContributor>(getSCCContributors(), groupMemberContributors, extraContributors)) {
1188            if (!contributor.isActive(stepUtil))
1189                continue;
1190            contributors.add(contributor);
1191        }
1192       
1193       
1194        BiPTarjan tarjan = new BiPTarjan(contributors);
1195        Collection<C> components = tarjan.tarjan(getEquations());
1196//        for (SCCContributor contributor : contributors) {
1197//            components = contributor.mergeComponents(components, this);
1198//        }
1199        return components;
1200    }
1201
1202    private class BiPTarjan extends Tarjan<E, C> {
1203       
1204        private final Collection<SCCContributor> contributors;
1205        Map<E, Collection<Collection<E>>> keepTogetherMap = new LinkedHashMap<E, Collection<Collection<E>>>();
1206       
1207        public BiPTarjan(Collection<SCCContributor> contributors) {
1208            this.contributors = contributors;
1209            Map<Object, Collection<E>> memberSetsMap = new HashMap<Object, Collection<E>>();
1210            for (SCCContributor contributor : contributors) {
1211                for (E equation : getEquations()) {
1212                    for (Map.Entry<E, Collection<? extends Object>> eqIdent : contributor.memberSets(equation, AbstractBiPGraph.this).entrySet()) {
1213                        for (Object identifier : eqIdent.getValue()) {
1214                            Collection<E> memberSet = memberSetsMap.get(identifier);
1215                            if (memberSet == null) {
1216                                memberSet = new ArrayList<E>();
1217                                memberSetsMap.put(identifier, memberSet);
1218                            }
1219                            Collection<Collection<E>> keepTogetherLists = keepTogetherMap.get(eqIdent.getKey());
1220                            if (keepTogetherLists == null) {
1221                                keepTogetherLists = new ArrayList<Collection<E>>();
1222                                keepTogetherMap.put(eqIdent.getKey(), keepTogetherLists);
1223                            }
1224                            memberSet.add(eqIdent.getKey());
1225                            keepTogetherLists.add(memberSet);
1226                        }
1227                    }
1228                }
1229            }
1230        }
1231
1232        @Override
1233        protected boolean visited(E e) {
1234            return e.isVisited();
1235        }
1236
1237        @Override
1238        protected void setVisited(E e, boolean val) {
1239            e.setVisited(val);
1240        }
1241
1242        @Override
1243        protected boolean shouldVisit(E e) {
1244            return e.tarjanVisit();
1245        }
1246
1247        @Override
1248        protected void addPredecessors(E e, Collection<E> predecessors) {
1249            for (V v : e.getVariables()) {
1250                E ee = v.getMatching();
1251                if (ee != null && e != ee && v.tarjanVisit())
1252                    predecessors.add(ee);
1253            }
1254            for (SCCContributor contributor : contributors)
1255                for (E ee : contributor.members(e, AbstractBiPGraph.this))
1256                    if (e != ee && ee.tarjanVisit())
1257                        predecessors.add(ee);
1258        }
1259
1260        @Override
1261        protected int getIndex(E e) {
1262            return e.getTarjanNbr();
1263        }
1264
1265        @Override
1266        protected void setIndex(E e, int val) {
1267            e.setTarjanNbr(val);
1268        }
1269
1270        @Override
1271        protected int getLowLink(E e) {
1272            return e.getTarjanLowLink();
1273        }
1274
1275        @Override
1276        protected void setLowLink(E e, int val) {
1277            e.setTarjanLowLink(val);
1278        }
1279
1280        @Override
1281        protected void forceIntoSame(E e, Set<E> members) {
1282            members.remove(e); // Added later
1283            forceIntoSameInternal(e, members);
1284        }
1285
1286        private void forceIntoSameInternal(E e, Set<E> members) {
1287            if (members.contains(e)) {
1288                return;
1289            }
1290            members.add(e);
1291            Collection<Collection<E>> keepTogetherLists = keepTogetherMap.get(e);
1292            if (keepTogetherLists != null) {
1293                for (Collection<E> keepTogether : keepTogetherLists) {
1294                    for (E ee : keepTogether) {
1295                        forceIntoSameInternal(ee, members);
1296                    }
1297                }
1298            }
1299            for (SCCContributor contributor : contributors) {
1300                for (E member : contributor.sameBlockMembers(e, AbstractBiPGraph.this)) {
1301                    forceIntoSameInternal(member, members);
1302                }
1303            }
1304        }
1305
1306        @Override
1307        protected C createComponent() {
1308            return createComponentBlock();
1309        }
1310       
1311    }
1312
1313    public void reset() {
1314        for (E e : getEquations()) {
1315            e.reset();
1316        }
1317        for (V v : getVariables()) {
1318            v.reset();
1319        }
1320    }
1321
1322    public void lightReset() {
1323        for (E e : getEquations()) {
1324            e.lightReset();
1325        }
1326        for (V v : getVariables()) {
1327            v.lightReset();
1328        }
1329    }
1330
1331    public void tarjanReset() {
1332        for (E e : getEquations()) {
1333            e.tarjanReset();
1334        }
1335    }
1336
1337    public void insertIntoEquationIndexMap(FAbstractEquation eqn, E e) {
1338        equationIndexMap.add(eqn, e);
1339    }
1340
1341    public void removeFromEquationIndexMap(FAbstractEquation eqn, E e) {
1342        equationIndexMap.removeFirst(eqn, e);
1343    }
1344
1345    public String printMatching() {
1346        StringBuffer str = new StringBuffer();
1347        str.append("----------------------------------------\n");
1348        str.append("BiPGraph matching:\n");
1349        for (E e : getEquations()) {
1350            if (e.getMatching()!=null) {
1351                str.append(e);
1352                str.append(" : ");
1353                str.append(e.getMatching());
1354                str.append("\n");
1355            }
1356        }       
1357        str.append("Unmatched equations: {");
1358        for (E e : unmatchedEquationsIterable()) {
1359            str.append(e + " ");
1360        }
1361        str.append("}\n");
1362       
1363        str.append("Unmatched variables: {");
1364        for (V v : unmatchedVariablesIterable()) {
1365            str.append(v + " ");
1366        }
1367        str.append("}\n");
1368       
1369        str.append("----------------------------------------\n");
1370        return str.toString();
1371    }
1372
1373    public Object printMatchingObj() {
1374        return new Object() {
1375            @Override
1376            public String toString() {
1377                return printMatching();
1378            }
1379        };
1380    }
1381
1382    public String toString() {
1383        StringBuffer str = new StringBuffer();
1384        str.append("BiPGraph (" + getEquations().size() + " equations, " + variableMap.size() + " variables)\n");
1385        str.append("Variables: {");
1386        for (String vName : variableMap.keySet()) {
1387            V v = variableMap.get(vName);
1388            str.append(v);
1389            str.append(" ");
1390        }
1391        str.append("}\n");
1392        Map<FAbstractEquation, E> printedMap = new HashMap<FAbstractEquation, E>();
1393        for (E e : getEquations()) {
1394            str.append(e);
1395            str.append(" : ");
1396            for (V v : e.getVariables()) {
1397                str.append(v);
1398                str.append(canMatch(e, v) ? '@' : '#');
1399                if (v.getMatching() == e || e.getMatching() == v) {
1400                    str.append('M');
1401                }
1402                str.append(' ');
1403            }
1404            String previousPrintLabel = null;
1405            if (e.getGroupMembers().size() > 1) {
1406                E previous = printedMap.get(e.getEquation());
1407               
1408                if (previous == null) {
1409                    printedMap.put(e.getEquation(), e);
1410                } else {
1411                    previousPrintLabel = previous.getName();
1412                }
1413            }
1414            if (previousPrintLabel == null) {
1415                str.append("// " + e.printEquation() + "\n");
1416            } else {
1417                str.append("// Already printed, see " + previousPrintLabel + "\n");
1418            }
1419        }
1420        return str.toString();
1421    }
1422
1423    public class Edge {
1424        private V variable;
1425        private E equation;
1426
1427        public Edge(E e, V v) {
1428            this.equation = e;
1429            this.variable = v;
1430        }
1431
1432        public V getVariable() {
1433            return variable;
1434        }
1435
1436        public void setVariable(V variable) {
1437            this.variable = variable;
1438        }
1439
1440        public E getEquation() {
1441            return equation;
1442        }
1443
1444        public void setEquation(E equation) {
1445            this.equation = equation;
1446        }
1447
1448        public String toString() {
1449            return "(" + equation + "," + variable + ")";
1450        }
1451
1452    }
1453   
1454    public Map<V, Collection<E>> computeVariableToEquationMap() {
1455        Map<V, Collection<E>> map = new HashMap<V, Collection<E>>();
1456        for (E eqn : getEquations()) {
1457            for (V var : eqn.getVariables()) {
1458                Collection<E> eqns = map.get(var);
1459                if (eqns == null) {
1460                    eqns = new ArrayList<E>();
1461                    map.put(var, eqns);
1462                }
1463                eqns.add(eqn);
1464            }
1465        }
1466        return map;
1467    }
1468
1469    public int countNumberOfIncidences() {
1470        int count = 0;
1471        for (E e : getEquations()) {
1472            count += e.getVariables().size();
1473        }
1474        return count;
1475    }
1476}
1477
1478    public class DAEVarUseLookupVisitor extends FAccessExpLookupVisitor {
1479        public static final DAEVarUseLookupVisitor instance = new DAEVarUseLookupVisitor();
1480       
1481        @Override
1482        public void visit(ASTNode<? extends ASTNode> node, Set<FAccessExp> set) {
1483            node.findDAEVarUsesInTree(set, this);
1484        }
1485    }
1486
1487    public class InitDAEVarUseLookupVisitor extends FAccessExpLookupVisitor {
1488        public static final InitDAEVarUseLookupVisitor instance = new InitDAEVarUseLookupVisitor();
1489       
1490        @Override
1491        public void visit(ASTNode<? extends ASTNode> node, Set<FAccessExp> set) {
1492            node.findInitDAEVarUsesInTree(set, this);
1493        }
1494    }
1495   
1496    public class InitUniqueDAEVarUseLookupVisitor extends FAccessExpLookupVisitor {
1497        public static final InitUniqueDAEVarUseLookupVisitor instance = new InitUniqueDAEVarUseLookupVisitor();
1498       
1499        @Override
1500        public void visit(ASTNode<? extends ASTNode> node, Set<FAccessExp> set) {
1501            node.findInitUniqueDAEVarUsesInTree(set, this);
1502        }
1503    }
1504   
1505
1506    public void ASTNode.findDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1507        findCommonAccessExpsInTree(set, visitor);
1508    }
1509
1510    @Override
1511    public void FHomotopyExp.findDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1512        visitor.visit(getActual(), set);
1513    }
1514
1515    public void ASTNode.findInitDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1516        findCommonAccessExpsInTree(set, visitor);
1517    }
1518
1519    public Set<FAccessExp> ASTNode.findInitUniqueDAEVarUsesInTree() {
1520        return findCommonAccessExpsInTree(InitUniqueDAEVarUseLookupVisitor.instance);
1521    }
1522
1523    public void ASTNode.findInitUniqueDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1524        for (ASTNode n : this) {
1525            visitor.visit(n, set);
1526        }
1527    }
1528
1529    public void FHomotopyExp.findInitUniqueDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1530        visitor.visit(getActual(), set);
1531        DefaultFAccessExpLookupVisitor.instance.visit(getSimplified(), set);
1532    }
1533   
1534
1535
1536/**
1537 * This class represent a component result from Tarjan's strongly connected
1538 * components algorithm.
1539 * It is basically a list of equations that depends on eachother and a list of
1540 * equations that they depend upon.
1541 */
1542public class SCCBlock<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> extends TarjanComponent<E> {
1543    private boolean containsHomotopy = false;
1544
1545    public void addMember(E member) {
1546        super.addMember(member);
1547        if (!containsHomotopy && member.getEquation().containsFHomotopyExp())
1548            containsHomotopy = true;
1549    }
1550   
1551    public boolean containsHomotopy() {
1552        return containsHomotopy;
1553    }
1554   
1555    public AbstractEquationBlock createEquationBlock(BlockProducer producer, StepUtil stepUtil, boolean isInitial) {
1556        return EquationBlockFactory.createEquationBlock(this, producer, stepUtil, isInitial);
1557    }
1558}
1559
1560public class BiPGraph extends AbstractBiPGraph<Eq, Var, SCCBlock<Eq, Var>> {
1561
1562    public BiPGraph() {
1563        super();
1564    }
1565
1566    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> BiPGraph(Collection<E> block, boolean isInitial) {
1567        super(block, isInitial);
1568    }
1569
1570    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> BiPGraph(Collection<E> eqns, Collection<V> vars) {
1571        super(eqns, vars);
1572    }
1573
1574    @Override
1575    protected Eq createEq(String name, FAbstractEquation eqn, int groupNumber, Collection<Eq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1576        return new Eq(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1577    }
1578
1579    @Override
1580    protected Var createVar(String name, FVariable var) {
1581        return new Var(name, var);
1582    }
1583   
1584    @Override
1585    protected SCCBlock<Eq, Var> createComponentBlock() {
1586        return new SCCBlock<Eq, Var>();
1587    }
1588}
1589
1590public class Eq extends AbstractEq<Eq, Var> {
1591
1592    public Eq(String name, FAbstractEquation eqn, int groupNumber, Collection<Eq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1593        super(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1594    }
1595
1596}
1597
1598public class Var extends AbstractVar<Eq, Var> {
1599
1600    public Var(String name, FVariable v) {
1601        super(name, v);
1602    }
1603
1604}
1605
1606
1607public class SolvingBiPGraph extends AbstractBiPGraph<SolvingEq, SolvingVar, SCCBlock<SolvingEq, SolvingVar>> {
1608
1609    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> SolvingBiPGraph(Collection<E> eqns, Collection<V> vars) {
1610        super(eqns, vars);
1611    }
1612
1613    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> SolvingBiPGraph(Collection<E> block, boolean isInitial) {
1614        super(block, isInitial);
1615    }
1616
1617    @Override
1618    public boolean canMatch(SolvingEq e, SolvingVar v) {
1619        return super.canMatch(e, v) && isSolved(e, v).isSolvable();
1620    }
1621
1622    public Solvability isSolved(SolvingEq e, SolvingVar v) {
1623        return e.getEquation().isSolved(v.getVariable(), true);
1624    }
1625
1626    @Override
1627    public void addInsidence(SolvingEq e, SolvingVar v) {
1628        super.addInsidence(e, v);
1629        v.occurrence();
1630        if (e.isReal() != v.isReal())
1631            return;
1632        e.sameTypeOccurrence();
1633        v.sameTypeOccurrence();
1634        Solvability solvability = isSolved(e, v);
1635        switch (solvability) {
1636        case ANALYTICALLY_SOLVABLE:
1637            e.addAnalyticallySolvableVariable(v);
1638            v.analyticallySolvableOccurrence();
1639            break;
1640        case NUMERICALLY_SOLVABLE:
1641            e.addNumericallySolvableVariable(v);
1642            v.numericallySolvableOccurrence();
1643            break;
1644        }
1645    }
1646
1647    @Override
1648    protected SolvingEq createEq(String name, FAbstractEquation eqn, int groupNumber, Collection<SolvingEq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1649        return new SolvingEq(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1650    }
1651
1652    @Override
1653    protected SolvingVar createVar(String name, FVariable var) {
1654        return new SolvingVar(name, var);
1655    }
1656
1657    @Override
1658    public void removeVariable(SolvingVar v) {
1659        for (SolvingEq e : getEquations())
1660            e.getSolvableVariables().remove(v);
1661        super.removeVariable(v);
1662    }
1663
1664    @Override
1665    protected SCCBlock<SolvingEq, SolvingVar> createComponentBlock() {
1666        return new SCCBlock<SolvingEq, SolvingVar>();
1667    }
1668}
1669
1670public class SolvingEq extends AbstractEq<SolvingEq, SolvingVar> implements Comparable<SolvingEq> {
1671
1672    private java.util.List<SolvingVar> solvableVariables = new ArrayList<SolvingVar>();
1673    private int analyticallySolvableOccurrences = 0;
1674    private int numericallySolvableOccurrences = 0;
1675    private int sameTypeOccurrences = 0;
1676    private boolean isRes = false;
1677
1678    public SolvingEq(String name, FAbstractEquation eqn, int groupNumber, Collection<SolvingEq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1679        super(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1680    }
1681
1682    public void sameTypeOccurrence(){
1683        sameTypeOccurrences++;
1684    }
1685
1686    public int getNbrSameTypeOccurrences(){
1687        return sameTypeOccurrences;
1688    }
1689
1690    public void addAnalyticallySolvableVariable(SolvingVar v) {
1691        solvableVariables.add(v);
1692        analyticallySolvableOccurrences++;
1693    }
1694
1695    public void addNumericallySolvableVariable(SolvingVar v) {
1696        solvableVariables.add(v);
1697        numericallySolvableOccurrences++;
1698    }
1699
1700    public java.util.List<SolvingVar> getSolvableVariables() {
1701        return solvableVariables;
1702    }
1703
1704    public void isRes(boolean bol){
1705        isRes = bol;
1706    }
1707
1708    public boolean isRes(){
1709        return isRes;
1710    }
1711
1712    public boolean tarjanVisit() {
1713        return !isRes();
1714    }
1715
1716    /**
1717     * Returns integer greater than zero if this equation suites better as residual
1718     * equation than the <code>other</code> equation. Zero is returned if they are equal
1719     * and less than zero is returned if the <code>other</code> variable is better.
1720     */
1721    @Override
1722    public int compareTo(SolvingEq other) {
1723        int diff = (isReal() ? 1 : 0) - (other.isReal() ? 1 : 0);
1724        if (diff != 0)
1725            return diff;
1726        diff = getNbrSameTypeOccurrences() - other.getNbrSameTypeOccurrences();
1727        if (diff != 0)
1728            return diff;
1729        diff = numericallySolvableOccurrences - other.numericallySolvableOccurrences;
1730        if (diff != 0)
1731            return diff;
1732        diff = other.analyticallySolvableOccurrences - analyticallySolvableOccurrences;
1733        if (diff != 0)
1734            return diff;
1735        return 0;
1736    }
1737
1738}
1739
1740public class SolvingVar extends AbstractVar<SolvingEq, SolvingVar> implements Comparable<SolvingVar> {
1741
1742    private int occurrences = 0;
1743    private int sameTypeOccurrences = 0;
1744    private int analyticallySolvableOccurrences = 0;
1745    private int numericallySolvableOccurrences = 0;
1746    private boolean isIter = false;
1747
1748    public SolvingVar(String name, FVariable v) {
1749        super(name, v);
1750    }
1751
1752    public void occurrence(){
1753        occurrences++;
1754    }
1755
1756    public void sameTypeOccurrence(){
1757        sameTypeOccurrences++;
1758    }
1759
1760    public void analyticallySolvableOccurrence(){
1761        analyticallySolvableOccurrences++;
1762    }
1763
1764    public void numericallySolvableOccurrence(){
1765        numericallySolvableOccurrences++;
1766    }
1767
1768    public int getNbrOccurrences(){
1769        return occurrences;
1770    }
1771
1772    public int getNbrSameTypeOccurrences(){
1773        return sameTypeOccurrences;
1774    }
1775
1776    public int getNbrAnalyticallySolvableOccurrences(){
1777        return analyticallySolvableOccurrences;
1778    }
1779
1780    public int getNbrNumericallySolvableOccurrences(){
1781        return numericallySolvableOccurrences;
1782    }
1783
1784    public void isIter(boolean bol){
1785        isIter = bol;
1786    }
1787
1788    public boolean isIter(){
1789        return isIter;
1790    }
1791
1792    public boolean tarjanVisit() {
1793        return !isIter();
1794    }
1795
1796    /**
1797     * Returns integer greather than zero if this variable sutes better as iteration
1798     * variable than the <code>other</code> variable. Zero is returned if they are equal
1799     * and <0 is returned if the <code>other</code> variable is better.
1800     */
1801    @Override
1802    public int compareTo(SolvingVar other) {
1803        int diff = (isReal() ? 1 : 0) - (other.isReal() ? 1 : 0);
1804        if (diff != 0)
1805            return diff;
1806        diff = (other.getVariable().isTemporary() ? 1 : 0) - (getVariable().isTemporary() ? 1 : 0);
1807        if (diff != 0)
1808            return diff;
1809        diff = getNbrSameTypeOccurrences() - other.getNbrSameTypeOccurrences();
1810        if (diff != 0)
1811            return diff;
1812        diff = getNbrNumericallySolvableOccurrences() - other.getNbrNumericallySolvableOccurrences();
1813        if (diff != 0)
1814            return diff;
1815        diff = other.getNbrAnalyticallySolvableOccurrences() - getNbrAnalyticallySolvableOccurrences();
1816        if (diff != 0)
1817            return diff;
1818        diff = (getVariable().attributeSet(FAttribute.START) ? 1 : 0) - (other.getVariable().attributeSet(FAttribute.START) ? 1 : 0);
1819        if (diff != 0)
1820            return diff;
1821        diff = other.getVariable().getFAccess().numDots() - getVariable().getFAccess().numDots();
1822        if (diff != 0)
1823            return diff;
1824        return 0;
1825    }
1826}
1827
1828
1829public abstract class AbstractEq<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> {
1830
1831    private final String name;
1832    private final FAbstractEquation eqn;
1833    private final int groupNumber;
1834    private final TypePrefixVariability variability;
1835    private final FType type;
1836    private final boolean isMeta;
1837    private java.util.List<V> variables = new ArrayList<V>();
1838    private V matching = null;
1839    private boolean visited = false;
1840    private int layer = 1000000;
1841    private int tarjanNbr = 0;
1842    private int tarjanLowLink = 0;
1843    private int depth = 1;
1844    /** In some cases, equations needs to be treated as a group, e.g., in the
1845     * case when several equations are generated from a function call equation.
1846     * In this case, all the "scalar" equations generated for the function call
1847     * equation are members of each such equation. Note that every equation is
1848     * member of its own group: scalar equations therefor has one member:
1849     * itself. This approach makes handling of equation groups more consistent,
1850     * e.g., when a function call equation needs to be differentiated.
1851     */
1852    private final Collection<E> groupMembers;
1853
1854    public AbstractEq(String name, FAbstractEquation eqn, int groupNumber, Collection<E> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1855        this.name = name;
1856        this.eqn = eqn;
1857        this.groupNumber = groupNumber;
1858        this.groupMembers = Collections.unmodifiableCollection(groupMembers);
1859        this.variability = variability;
1860        this.type = type;
1861        this.isMeta = isMeta;
1862    }
1863
1864    public boolean isMeta() {
1865        return isMeta;
1866    }
1867
1868    public void addVariable(V v) {
1869        variables.add(v);
1870    }
1871
1872    public void reset() {
1873        setMatching(null);
1874        setVisited(false);
1875        setLayer(1000000);
1876    }
1877
1878    public void lightReset() {
1879        setVisited(false);
1880        setLayer(1000000);
1881    }
1882
1883    public void tarjanReset() {
1884        setTarjanLowLink(0);
1885        setTarjanNbr(0);
1886        setVisited(false);
1887    }
1888
1889    public String getName() {
1890        return name;
1891    }
1892
1893    public FAbstractEquation getEquation() {
1894        return eqn;
1895    }
1896
1897    public int groupNumber() {
1898        return groupNumber;
1899    }
1900
1901    public java.util.List<V> getVariables() {
1902        return variables;
1903    }
1904
1905    public V getMatching() {
1906        return matching;
1907    }
1908
1909    public void setMatching(V matching) {
1910        this.matching = matching;
1911    }
1912
1913    public boolean isVisited() {
1914        return visited;
1915    }
1916
1917    public void setVisited(boolean visited) {
1918        this.visited = visited;
1919    }
1920
1921    public boolean tarjanVisit() {
1922        return true;
1923    }
1924
1925    public int getLayer() {
1926        return layer;
1927    }
1928
1929    public void setLayer(int layer) {
1930        this.layer = layer;
1931    }
1932
1933    public int getTarjanNbr() {
1934        return tarjanNbr;
1935    }
1936
1937    public void setTarjanNbr(int tarjanNbr) {
1938        this.tarjanNbr = tarjanNbr;
1939    }
1940
1941    public int getTarjanLowLink() {
1942        return tarjanLowLink;
1943    }
1944
1945    public void setTarjanLowLink(int tarjanLowLink) {
1946        this.tarjanLowLink = tarjanLowLink;
1947    }
1948
1949    public String toString() {
1950        return getName();
1951    }
1952
1953    public String printEquation() {
1954        return getEquation().toString();
1955    }
1956
1957    public boolean isReal() {
1958        return type.isReal();
1959    }
1960
1961    public FType type() {
1962        return type;
1963    }
1964
1965    public int getDepth(){
1966        return this.depth;
1967    }
1968
1969    public void setDepth(int d){
1970        this.depth = d;
1971    }
1972
1973    public Collection<E> getGroupMembers() {
1974        return groupMembers;
1975    }
1976
1977    public V getVariable(String name) {
1978        for (V var : variables) {
1979            if (var.getName().equals(name)) {
1980                return var;
1981            }
1982        }
1983        return null;
1984    }
1985
1986    public TypePrefixVariability variability() {
1987        return variability;
1988    }
1989
1990    @Override
1991    public boolean equals(Object o) {
1992        if (!(o instanceof AbstractEq))
1993            return false;
1994        AbstractEq other = (AbstractEq)o;
1995        return getName().equals(other.getName());
1996    }
1997
1998    @Override
1999    public int hashCode() {
2000        return getName().hashCode();
2001    }
2002   
2003    public void removeIncidencesNotInSet(Set<V> vars) {
2004        Iterator<V> it = variables.iterator();
2005        while (it.hasNext()) {
2006            V var = it.next();
2007            if (!vars.contains(var))
2008                it.remove();
2009        }
2010    }
2011
2012}
2013
2014public abstract class AbstractVar<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> {
2015
2016    private final String name;
2017    private final FVariable v;
2018    private E matching = null;
2019    private boolean visited = false;
2020    private int layer = 1000000;
2021
2022    public AbstractVar(String name, FVariable v) {
2023        this.name = name;
2024        this.v = v;
2025    }
2026
2027    public void reset() {
2028        setMatching(null);
2029        setVisited(false);
2030        setLayer(1000000);
2031    }
2032
2033    public void lightReset() {
2034        setVisited(false);
2035        setLayer(1000000);
2036    }
2037
2038    public String getName() {
2039        return name;
2040    }
2041
2042    public FVariable getVariable() {
2043        return v;
2044    }
2045
2046    public E getMatching() {
2047        return matching;
2048    }
2049
2050    public void setMatching(E matching) {
2051        this.matching = matching;
2052    }
2053
2054    public boolean isVisited() {
2055        return visited;
2056    }
2057
2058    public void setVisited(boolean visited) {
2059        this.visited = visited;
2060    }
2061
2062    public boolean tarjanVisit() {
2063        return true;
2064    }
2065
2066    public int getLayer() {
2067        return layer;
2068    }
2069
2070    public void setLayer(int layer) {
2071        this.layer = layer;
2072    }
2073
2074    public String toString() {
2075        return v.displayName();
2076    }
2077
2078    public boolean isReal() {
2079        return type().isReal();
2080    }
2081
2082    public FType type() {
2083        return getVariable().type();
2084    }
2085
2086    @Override
2087    public boolean equals(Object o) {
2088        if (!(o instanceof AbstractVar))
2089            return false;
2090        AbstractVar other = (AbstractVar)o;
2091        return getName().equals(other.getName());
2092    }
2093
2094    @Override
2095    public int hashCode() {
2096        return getName().hashCode();
2097    }
2098}
2099
2100public class AbstractBiPGraph {
2101    protected static interface VariableResolver<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> {
2102        public Set<V> lookupVars(Iterable<FAccessExp> set);
2103    }
2104}
2105
2106public VariableResolver<E, V> AbstractBiPGraph.defaultVariableResolver() {
2107    return new VariableResolver<E,V>() {
2108        public Set<V> lookupVars(Iterable<FAccessExp> set) {
2109            return AbstractBiPGraph.this.lookupVars(set);
2110        }
2111    };
2112}
2113
2114public Set<V> AbstractBiPGraph.lookupVars(Iterable<FAccessExp> set) {
2115    Set<V> res = new LinkedHashSet<V>();
2116    for (FAccessExp use : set) {
2117        V var = getVariable(use.name());
2118        if (var != null)
2119            res.add(var);
2120    }
2121    return res;
2122}
2123
2124    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2125    AbstractBiPGraph<E, V, C>.IncidenceMap
2126    FAbstractEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes) {
2127        return createIncidenceMap(g, variableTypes, g.defaultVariableResolver());
2128    }
2129   
2130    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2131    AbstractBiPGraph<E, V, C>.IncidenceMap
2132    FAbstractEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2133            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2134        return g.new IncidenceMap(this, resolver);
2135    }
2136
2137    @Override
2138    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2139    AbstractBiPGraph<E, V ,C>.IncidenceMap
2140    FAlgorithm.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2141            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2142        return g.new ManyIncidenceMap(this, resolver, variableTypes);
2143    }
2144
2145    @Override
2146    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2147    AbstractBiPGraph<E, V, C>.IncidenceMap
2148    FIfEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2149            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2150        return g.new ManyIncidenceMap(this, resolver, variableTypes);
2151    }
2152
2153    @Override
2154    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>> 
2155    AbstractBiPGraph<E, V, C>.IncidenceMap
2156    FFunctionCallEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2157            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2158        if (myOptions().getStringOption("function_incidence_computation").equals("all")) {
2159            try {
2160                AbstractBiPGraph<E, V, C>.SplitIncidenceMap splitIncidenceMap = g.new SplitIncidenceMap(this, resolver, variableTypes);
2161                splitIncidenceMap.lhs(); // trigger cache calculations
2162                return splitIncidenceMap;
2163            } catch (ConstantEvaluationException e) {
2164               
2165            }
2166        }
2167        return g.new ManyIncidenceMap(this, resolver, variableTypes);
2168    }
2169   
2170
2171}
2172
2173aspect AugmentingPath {
2174   
2175    public abstract class AbstractBiPGraph {
2176        private final Enumerator visitEnumerator = new Enumerator(1);
2177        public abstract class AugmentingPathAlgorithm<R> {
2178            private final R TRUE_VALUE;
2179
2180            protected AugmentingPathAlgorithm(R TRUE_VALUE) {
2181                this.TRUE_VALUE = TRUE_VALUE;
2182            }
2183
2184            public R augmentingPath(E e) {
2185                return augmentingPath(e, Collections.<V>emptyList());
2186            }
2187
2188            public R augmentingPath(E e, Collection<V> preVisit) {
2189                int visitNum = visitEnumerator.next();
2190                for (V var : preVisit)
2191                    var.augmentingPathVisit(visitNum);
2192                return visitEqn(e, visitNum);
2193            }
2194           
2195            private final R visitEqn(E eqn, int num) {
2196                R res = startValue(eqn);
2197                if (!eqn.augmentingPathVisit(num))
2198                    return res;
2199                for (V var : visitVariables(eqn)) {
2200                    if (!shouldVisit(eqn, var))
2201                        continue;
2202                    if (var.getMatching() == null) {
2203                        match(eqn, var);
2204                        return TRUE_VALUE;
2205                    } else if (var.augmentingPathVisit(num)) {
2206                        R subRes = visitEqn(var.getMatching(), num);
2207                        if (subRes == TRUE_VALUE) {
2208                            match(eqn, var);
2209                            return TRUE_VALUE;
2210                        }
2211                        res = mergeSubRes(res, subRes, eqn);
2212                    }
2213                }
2214                return res;
2215            }
2216
2217            protected void match(E eqn, V var) {
2218                AbstractBiPGraph.this.match(eqn, var);
2219            }
2220
2221            protected abstract R startValue(E eqn);
2222
2223            protected abstract R mergeSubRes(R res, R subRes, E eqn);
2224
2225            protected boolean shouldVisit(E eqn, V var) {
2226                return canMatch(eqn, var);
2227            }
2228
2229            protected Iterable<V> visitVariables(E eqn) {
2230                return eqn.getVariables();
2231            }
2232
2233            public R trueValue() {
2234                return TRUE_VALUE;
2235            }
2236        }
2237
2238        private final StandardAugmentingPath STANDARD_AUGMENTING_PATH = new StandardAugmentingPath();
2239
2240        public class StandardAugmentingPath extends AugmentingPathAlgorithm<Boolean> {
2241            public StandardAugmentingPath() {
2242                super(true);
2243            }
2244
2245            @Override
2246            protected Boolean startValue(E eqn) {
2247                return false;
2248            }
2249
2250            @Override
2251            protected Boolean mergeSubRes(Boolean res, Boolean subRes, E eqn) {
2252                return false;
2253            }
2254        }
2255    }
2256   
2257    private int AbstractEq.augmentingPathVisitNumber = 0;
2258    public boolean AbstractEq.augmentingPathVisit(int num) {
2259        boolean res = num > augmentingPathVisitNumber;
2260        augmentingPathVisitNumber = num;
2261        return res;
2262    }
2263   
2264    private int AbstractVar.augmentingPathVisitNumber = 0;
2265    public boolean AbstractVar.augmentingPathVisit(int num) {
2266        boolean res = num > augmentingPathVisitNumber;
2267        augmentingPathVisitNumber = num;
2268        return res;
2269    }
2270   
2271    public boolean AbstractBiPGraph.augmentPath(E e) {
2272        e.setVisited(true);
2273        for (V v : e.getVariables()) {
2274            if (!canMatch(e, v))
2275                continue;
2276            if (v.getMatching()==null) {
2277                match(e, v);
2278                return true;
2279            } else if (!v.isVisited()) {
2280                v.setVisited(true);
2281                if (augmentPath(v.getMatching())) {
2282                    match(e, v);
2283                    return true;
2284                }
2285            }
2286        }
2287        return false;
2288    }
2289
2290}
Note: See TracBrowser for help on using the repository browser.