001package org.clafer.ast.analysis;
002
003import gnu.trove.list.array.TIntArrayList;
004import java.util.Arrays;
005import java.util.HashMap;
006import java.util.Map;
007import org.clafer.ast.AstAbstractClafer;
008import org.clafer.ast.AstClafer;
009import org.clafer.ast.AstConcreteClafer;
010import org.clafer.ast.Card;
011
012/**
013 *
014 * @author jimmy
015 */
016public class PartialSolutionAnalyzer implements Analyzer {
017
018    @Override
019    public Analysis analyze(Analysis analysis) {
020        Map<AstClafer, PartialSolution> partialSolutionMap = new HashMap<>();
021
022        partialSolutionMap.put(analysis.getModel(), new PartialSolution(new boolean[]{true}, new int[0][]));
023        for (AstConcreteClafer child : analysis.getModel().getChildren()) {
024            analyze(child, analysis, partialSolutionMap);
025        }
026        for (AstAbstractClafer abstractClafer : analysis.getAbstractClafers()) {
027            analyze(abstractClafer, analysis, partialSolutionMap);
028        }
029
030        return analysis.setPartialSolutionMap(partialSolutionMap);
031    }
032
033    private static void analyze(
034            AstAbstractClafer clafer,
035            Analysis analysis,
036            Map<AstClafer, PartialSolution> partialSolutionMap) {
037        Card globalCard = analysis.getGlobalCard(clafer);
038        boolean[] solution = new boolean[analysis.getScope(clafer)];
039        int[][] parents = new int[globalCard.getHigh()][];
040        for (AstClafer sub : clafer.getSubs()) {
041            int offset = analysis.getOffsets(clafer).getOffset(sub);
042
043            PartialSolution partialSubSolution = partialSolutionMap.get(sub);
044            // This is possible for partialSubSolution to be null if a child of an abstract
045            // extends the abstract. Assume the worst possible case by assuming it is empty.
046            if (partialSubSolution != null) {
047                System.arraycopy(partialSubSolution.getSolution(), 0, solution, offset, partialSubSolution.size());
048            }
049        }
050        partialSolutionMap.put(clafer, new PartialSolution(solution, parents));
051
052        for (AstConcreteClafer child : clafer.getChildren()) {
053            analyze(child, analysis, partialSolutionMap);
054        }
055    }
056
057    private static void analyze(
058            AstConcreteClafer clafer,
059            Analysis analysis,
060            Map<AstClafer, PartialSolution> partialSolutionMap) {
061        Card globalCard = analysis.getGlobalCard(clafer);
062        Format format = analysis.getFormat(clafer);
063
064        boolean[] solution = new boolean[analysis.getScope(clafer)];
065        TIntArrayList[] parents = new TIntArrayList[globalCard.getHigh()];
066        for (int i = 0; i < parents.length; i++) {
067            parents[i] = new TIntArrayList();
068        }
069
070        PartialSolution partialParentSolution = partialSolutionMap.get(clafer.getParent());
071        Card card = analysis.getCard(clafer);
072        int lowCard = card.getLow();
073        int highCard = card.getHigh();
074        switch (format) {
075            case LowGroup:
076                Arrays.fill(solution, 0, globalCard.getLow(), true);
077                int low = 0;
078                int high = highCard;
079                for (int i = 0; i < partialParentSolution.size(); i++) {
080                    for (int j = low; j < high && j < parents.length; j++) {
081                        parents[j].add(i);
082                    }
083                    if (partialParentSolution.hasClafer(i)) {
084                        low += lowCard;
085                    }
086                    high += highCard;
087                }
088                break;
089            case ParentGroup:
090                assert lowCard == highCard;
091                for (int i = 0; i < partialParentSolution.size(); i++) {
092                    for (int j = 0; j < lowCard; j++) {
093                        solution[i * lowCard + j] = partialParentSolution.hasClafer(i);
094                        parents[i * lowCard + j].add(i);
095                    }
096                }
097                break;
098            default:
099                throw new AnalysisException();
100        }
101        partialSolutionMap.put(clafer, new PartialSolution(solution, toArray(parents)));
102
103        for (AstConcreteClafer child : clafer.getChildren()) {
104            analyze(child, analysis, partialSolutionMap);
105        }
106    }
107
108    private static int[][] toArray(TIntArrayList[] list) {
109        int[][] array = new int[list.length][];
110        for (int i = 0; i < array.length; i++) {
111            array[i] = list[i].toArray();
112        }
113        return array;
114    }
115}