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