001    package jcolibri.method.maintenance;
002    
003    import java.util.Collection;
004    import java.util.HashMap;
005    import java.util.Iterator;
006    import java.util.LinkedList;
007    import java.util.List;
008    
009    import jcolibri.cbrcore.CBRCase;
010    import jcolibri.method.retrieve.KNNretrieval.KNNConfig;
011    
012    /**
013     * Implements the CRR Maintenance Algorithm to remove 
014     * redundancy from the case base 
015     * 
016     * @author Lisa Cummins
017     */
018    public class CRRAlgorithm extends MaintenanceAlgorithm {
019    
020            /**
021             * Runs the CRR maintenance algorithm, returning the cases
022             * deleted by the algorithm
023             * @param cases The group of cases on which to perform maintenance
024             * @param simConfig The KNNConfig for these cases
025             * @return the list of cases deleted by the algorithm
026             */
027            public LinkedList<CBRCase> runMaintenance(Collection<CBRCase> cases, KNNConfig simConfig) 
028            {       /*
029                     * Conservative Redundancy Removal(CRR) Algorithm:
030                     * T, Training Set
031                     * 
032                     * Build case-base competence model
033                     * For each c in T
034                     *              CSet(c) = Coverage Set of c
035                     * End-For
036                     * 
037                     * Remove redundant cases from case-base
038                     * ESet = {}, (Edited Set)
039                     * TSet = T sorted in ascending order of CSet(c) size
040                     * c = first case in TSet
041                     * 
042                     * While TSet = {}
043                     *              ESet = ESet + {c}
044                     *              TSet = TSet – CSet(c)
045                     *              c = next case in TSet
046                     * End-While
047                     * 
048                     * Return TSet
049                     */
050                    List<CBRCase> localCases = new LinkedList<CBRCase>();
051                    for(CBRCase c: cases)
052                    {       localCases.add(c);
053                    }
054                    
055                    SetCalculator sc = new SetCalculator();
056                    HashMap<String, HashMap<CBRCase, LinkedList<CBRCase>>> sets = sc.calculateCRRSets(cases, simConfig);
057                    HashMap<CBRCase, LinkedList<CBRCase>> coverageSets = sets.get(SetCalculator.COVERAGE_SET);
058    
059                    LinkedList<CBRCase> tSet = new LinkedList<CBRCase>();
060                    
061                    LinkedList<CBRCase> sortedCases = new LinkedList<CBRCase>();
062                    LinkedList<Integer> coverageSetSizes = new LinkedList<Integer>();
063                    for(CBRCase c: localCases)
064                    {       tSet.add(c);
065                            
066                            LinkedList<CBRCase> currCoverageSet = coverageSets.get(c);
067                            if(sortedCases.size() == 0)
068                            {       sortedCases.add(c);
069                                    coverageSetSizes.add(currCoverageSet.size());
070                            }
071                            else
072                            {       int i;
073                                    for(i=0; i < sortedCases.size() && coverageSetSizes.get(i) < currCoverageSet.size(); i++);
074                                    if(i==0)
075                                    {       sortedCases.addFirst(c);
076                                            coverageSetSizes.addFirst(currCoverageSet.size());
077                                    }
078                                    else if(i==sortedCases.size())
079                                    {       sortedCases.addLast(c);
080                                            coverageSetSizes.addLast(currCoverageSet.size());
081                                    }
082                                    else
083                                    {       sortedCases.add(i-1, c);
084                                            coverageSetSizes.add(i-1, currCoverageSet.size());
085                                    }
086                            }
087                    }
088                    
089                    LinkedList<CBRCase> newCases = new LinkedList<CBRCase>();
090                    while(sortedCases.size() > 0)
091                    {       CBRCase c = sortedCases.get(0);
092                            newCases.add(c);
093                            sortedCases.remove(c);
094                            LinkedList<CBRCase> cCoverageSet = coverageSets.get(c);
095                            for(Iterator<CBRCase> cIter = cCoverageSet.iterator(); cIter.hasNext(); )
096                            {       CBRCase removed = cIter.next();
097                                    sortedCases.remove(removed);
098                            }
099                    }
100    
101                    LinkedList<CBRCase> allCasesToBeRemoved = new LinkedList<CBRCase>();
102                    for(CBRCase c: localCases)
103                    {       if(!newCases.contains(c))
104                                    allCasesToBeRemoved.add(c);
105                    }
106                    
107                    return allCasesToBeRemoved;
108            }
109    }