001    package jcolibri.method.maintenance.algorithms;
002    
003    import java.util.Collection;
004    import java.util.Iterator;
005    import java.util.LinkedList;
006    import java.util.List;
007    import java.util.ListIterator;
008    
009    import jcolibri.cbrcore.CBRCase;
010    import jcolibri.exception.InitializingException;
011    import jcolibri.method.maintenance.AbstractCaseBaseEditMethod;
012    import jcolibri.method.maintenance.CaseResult;
013    import jcolibri.method.maintenance.CompetenceModel;
014    import jcolibri.method.maintenance.solvesFunctions.CBESolvesFunction;
015    import jcolibri.method.reuse.classification.KNNClassificationConfig;
016    
017    import org.apache.commons.logging.LogFactory;
018    
019    /**
020     * Provides the ability to run the CRR case base editing algorithm 
021     * on a case base to eliminate redundancy.
022     * 
023     * @author Lisa Cummins
024     * @author Derek Bridge
025     * 18/05/07
026     */
027    public class CRRRedundancyRemoval extends AbstractCaseBaseEditMethod {
028    
029            /**
030             * Simulates the CRR case base editing algorithm, returning the cases
031             * that would be deleted by the algorithm.
032             * @param cases The group of cases on which to perform editing.
033             * @param simConfig The similarity configuration for these cases.
034             * @return the list of cases that would be deleted by the 
035             * CRR algorithm.
036             */
037            @SuppressWarnings("unchecked")
038            public List<CBRCase> retrieveCasesToDelete(Collection<CBRCase> cases, KNNClassificationConfig simConfig)
039            {       /*
040                     * Conservative Redundancy Removal(CRR) Algorithm:
041                     * T, Training Set
042                     * 
043                     * Build case-base competence model
044                     * For each c in T
045                     *              CSet(c) = Coverage Set of c
046                     * End-For
047                     * 
048                     * Remove redundant cases from case-base
049                     * ESet = {}, (Edited Set)
050                     * TSet = T sorted in ascending order of CSet(c) size
051                     * c = first case in TSet
052                     * 
053                     * While TSet != {}
054                     *              ESet = ESet + {c}
055                     *              TSet = TSet – CSet(c)
056                     *              c = next case in TSet
057                     * End-While
058                     * 
059                     * Return TSet
060                     */
061                    jcolibri.util.ProgressController.init(this.getClass(), "Conservative Redundancy Removal(CRR)", jcolibri.util.ProgressController.UNKNOWN_STEPS);
062                    List<CBRCase> localCases = new LinkedList<CBRCase>();
063                    for(CBRCase c: cases)
064                    {       localCases.add(c);
065                    }
066                    
067                    CompetenceModel sc = new CompetenceModel();
068                    sc.computeCompetenceModel(new CBESolvesFunction(), simConfig, localCases);
069                    //Map<CBRCase, Collection<CBRCase>> coverageSets = sc.getCoverageSets();
070    
071                    LinkedList<CBRCase> tSet = new LinkedList<CBRCase>();
072                    
073                    List<CaseResult> caseCoverageSetSizes = new LinkedList<CaseResult>();
074                    for(CBRCase c: localCases)
075                    {       tSet.add(c);
076                            Collection<CBRCase> currCoverageSet = null;
077                            try
078                            {   currCoverageSet = sc.getCoverageSet(c);
079                                caseCoverageSetSizes.add(new CaseResult(c, currCoverageSet.size()));
080                            } catch (InitializingException e)
081                            {   LogFactory.getLog(this.getClass()).error(e);
082                            }
083                            jcolibri.util.ProgressController.step(this.getClass());
084                    }
085                    
086                    caseCoverageSetSizes = CaseResult.sortResults(true, caseCoverageSetSizes);
087                    List<CBRCase> newCases = new LinkedList<CBRCase>();
088                    List<CBRCase> allCasesToBeRemoved = new LinkedList<CBRCase>();
089                    
090                    while(caseCoverageSetSizes.size() > 0)
091                    {       List<CBRCase> removeThese = new LinkedList<CBRCase>();
092                            CBRCase c = caseCoverageSetSizes.get(0).getCase();
093                            newCases.add(c);
094                            try
095                            {   Collection<CBRCase> cCoverageSet = sc.getCoverageSet(c);
096                                for(Iterator<CBRCase> cIter = cCoverageSet.iterator(); cIter.hasNext(); )
097                                {   CBRCase removed = cIter.next();
098                                    if(!removed.equals(c) && !allCasesToBeRemoved.contains(removed))
099                                    {       allCasesToBeRemoved.add(removed);
100                                    }
101                                    removeThese.add(removed);
102                                }
103                                ListIterator<CaseResult> iter = null;
104                                for(iter = caseCoverageSetSizes.listIterator(); iter.hasNext() && removeThese.size() > 0; )
105                                {   CaseResult cResult = iter.next();
106                                            if(removeThese.contains(cResult.getCase()))
107                                    {       iter.remove();
108                                            removeThese.remove(cResult.getCase());
109                                    }
110                                }
111                                caseCoverageSetSizes = CaseResult.sortResults(true, caseCoverageSetSizes);
112                            } catch (InitializingException e)
113                            {   LogFactory.getLog(this.getClass()).error(e);
114                            }
115                            jcolibri.util.ProgressController.step(this.getClass());
116                    }       
117                    jcolibri.util.ProgressController.finish(this.getClass());
118                    return allCasesToBeRemoved;
119            }
120    }