package de.lmu.ifi.dbs.algorithm;

import de.lmu.ifi.dbs.algorithm.result.AprioriResult;
import de.lmu.ifi.dbs.algorithm.result.Result;
import de.lmu.ifi.dbs.data.BitVector;
import de.lmu.ifi.dbs.database.Database;
import de.lmu.ifi.dbs.utilities.Description;
import de.lmu.ifi.dbs.utilities.optionhandling.OptionHandler;
import de.lmu.ifi.dbs.utilities.optionhandling.UnusedParameterException;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

/**
 * Provides the apriori algorithm.
 * 
 * @author Arthur Zimek (<a href="mailto:zimek@dbs.ifi.lmu.de">zimek@dbs.ifi.lmu.de</a>)
 */
public class APRIORI extends AbstractAlgorithm<BitVector>
{
//    /**
//     * A comparator for sorting of BitSets.
//     */
//    public static final Comparator<BitSet> bitSetComparator = new BitSetComparator();
    
    /**
     * Parameter minimum frequency.
     */
    public static final String MINIMUM_FREQUENCY_P = "minfreq";
    
    /**
     * Description for parameter frequency.
     */
    public static final String MINIMUM_FREQUENCY_D = "<double>minimum frequency (as percentage, i.e.: 0 <= minfreq <= 1)";

    /**
     * The minimum frequency.
     */
    private double minfreq;
    
    /**
     * The result.
     */
    private AprioriResult result;
    
    /**
     * Keeps the frequencies of all evaluated bitsets.
     */
    private Map<BitSet,Integer> frequencies;
    
    /**
     * Provides the apriori algorithm.
     */
    public APRIORI()
    {
        super();
        parameterToDescription.put(MINIMUM_FREQUENCY_P+OptionHandler.EXPECTS_VALUE,MINIMUM_FREQUENCY_D);
        optionHandler = new OptionHandler(parameterToDescription,APRIORI.class.getName());
    }

    /**
     * 
     * @see de.lmu.ifi.dbs.algorithm.Algorithm#run(de.lmu.ifi.dbs.database.Database)
     */
    public void run(Database<BitVector> database) throws IllegalStateException
    {
        frequencies = new Hashtable<BitSet,Integer>();
        List<BitSet> solution = new ArrayList<BitSet>();
        int size = database.size();
        if(size > 0)
        {
            int dim;
            try
            {
                dim = database.get(database.iterator().next()).getDimensionality();
            }
            catch(Exception e)
            {
                dim = 0;
            }
            BitSet[] candidates = new BitSet[dim];
            for(int i = 0; i < dim; i++)
            {
                candidates[i] = new BitSet();
                candidates[i].set(i);
            }
            while(candidates.length > 0)
            {
                BitSet[] frequentItemsets = frequentItemsets(candidates, database);
                for(BitSet bitSet : frequentItemsets)
                {
                    solution.add(bitSet);
                }
                BitSet[] joined = join(frequentItemsets);
                candidates = prune(joined,size);
            }
        }
        result = new AprioriResult(solution, frequencies, database);
    }
    
    /**
     * Prunes a given set of candidates to keep only
     * those BitSets where all subsets of bits flipping one bit
     * are frequent already.
     * 
     * 
     * @param candidates the candidates to be pruned
     * @param size size of the database
     * @return a set of BitSets where all subsets of bits flipping one bit
     * are frequent already
     */
    protected BitSet[] prune(BitSet[] candidates, int size)
    {
        List<BitSet> candidateList = new ArrayList<BitSet>();
        for(BitSet bitSet : candidates)
        {
            boolean unpruned = true;
            for(int i = bitSet.nextSetBit(0); i <= 0 && unpruned; i = bitSet.nextSetBit(i+1))
            {
                bitSet.clear(i);
                unpruned = (double) frequencies.get(bitSet) / size >= minfreq;
                bitSet.set(i);
            }
            if(unpruned)
            {
                candidateList.add(bitSet);
            }
        }
        return candidateList.toArray(new BitSet[candidateList.size()]);
    }
    
    /**
     * Returns a set of BitSets generated by joining
     * pairs of given BitSets (relying on the given BitSets
     * being sorted), increasing the length by 1.
     * 
     * @param frequentItemsets the BitSets to be joined
     * @return a set of BitSets generated by joining
     * pairs of given BitSets, increasing the length by 1
     */
    protected BitSet[] join(BitSet[] frequentItemsets)
    {
        List<BitSet> joined = new ArrayList<BitSet>();
        for(int i = 0; i < frequentItemsets.length; i++)
        {
            for(int j = i+1; j < frequentItemsets.length; j++)
            {
                BitSet b1 = (BitSet) frequentItemsets[i].clone();
                BitSet b2 = (BitSet) frequentItemsets[j].clone();
                int b1i = b1.length()-1;
                int b2i = b2.length()-1;
                b1.clear(b1i);
                b2.clear(b2i);
                if(b1.equals(b2))
                {
                    b1.set(b1i);
                    b1.set(b2i);
                    joined.add(b1);
                }
            }
        }
        return joined.toArray(new BitSet[joined.size()]);
    }

    /**
     * Returns the frequent BitSets out of the given BitSets
     * with respect to the given database.
     * 
     * @param candidates the candidates to be evaluated
     * @param database the database to evaluate the candidates on
     * @return the frequent BitSets out of the given BitSets
     * with respect to the given database
     */
    protected BitSet[] frequentItemsets(BitSet[] candidates, Database<BitVector> database)
    {
        for(BitSet bitSet : candidates)
        {
            if(frequencies.get(bitSet) == null)
            {
                frequencies.put(bitSet,0);
            }
        }
        for(Iterator<Integer> iter = database.iterator(); iter.hasNext();)
        {
            BitVector bv = database.get(iter.next());
            for(BitSet bitSet : candidates)
            {
                if(bv.contains(bitSet))
                {
                    frequencies.put(bitSet,frequencies.get(bitSet)+1);
                }
            }
        }
        List<BitSet> frequentItemsets = new ArrayList<BitSet>();
        for(BitSet bitSet : candidates)
        {
            if((double) frequencies.get(bitSet) / database.size() >= minfreq)
            {
                frequentItemsets.add(bitSet);
            }
        }
        return frequentItemsets.toArray(new BitSet[frequentItemsets.size()]);
    }
    
    /**
     * 
     * @see de.lmu.ifi.dbs.algorithm.Algorithm#getResult()
     */
    public Result getResult()
    {
        return result;
    }

    /**
     * 
     * @see de.lmu.ifi.dbs.algorithm.Algorithm#getDescription()
     */
    public Description getDescription()
    {
        // TODO reference
        return new Description("APRIORI", "APRIORI", "search for frequent itemsets", "...");
    }

    /**
     * 
     * 
     * @see de.lmu.ifi.dbs.utilities.optionhandling.Parameterizable#setParameters(java.lang.String[])
     */
    @Override
    public String[] setParameters(String[] args) throws IllegalArgumentException
    {
        String[] remainingParameters = super.setParameters(args);
        try
        {
            minfreq = Double.parseDouble(optionHandler.getOptionValue(MINIMUM_FREQUENCY_P));
        }
        catch(NumberFormatException e)
        {
            throw new IllegalArgumentException(e);
        }
        catch(UnusedParameterException e)
        {
            throw new IllegalArgumentException(e);
        }
        return remainingParameters;
    }

    
}

@@ -2238,44 +2238,9 @@
 ase.
-get(database.iterator().next()).getD
+d
 imen
@@ -2284,16 +2284,36 @@
   catch(
+UnsupportedOperation
 Exceptio

use of new method database.dimensionality()