/*
 * ARX: Powerful Data Anonymization
 * Copyright (C) 2012 - 2014 Florian Kohlmayer, Fabian Prasser
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

package org.deidentifier.arx.metric;

import org.deidentifier.arx.framework.check.groupify.HashGroupifyEntry;
import org.deidentifier.arx.framework.check.groupify.IHashGroupify;
import org.deidentifier.arx.framework.lattice.Node;

/**
 * This class provides an implementation of the (normalized) average equivalence class size metric.
 * We dont normailze the metric as proposed in the original publication [1], as this would only be possible for k-anonymity.
 * [1] LeFevre K, DeWitt DJ, Ramakrishnan R. Mondrian Multidimensional K-Anonymity. IEEE; 2006:25-25.
 * 
 * @author Fabian Prasser
 * @author Florian Kohlmayer
 */
public class MetricAECS extends MetricDefault {

    private static final long serialVersionUID = -532478849890959974L;

    protected MetricAECS() {
        super(false, false);
    }

    @Override
    public String toString() {
        return "Average Equivalence Class Size";
    }

    @Override
    protected InformationLossDefault evaluateInternal(final Node node, final IHashGroupify g) {

        // Is the transformation anonymous
        boolean anonymous = g.isAnonymous();
        // The total number of groups
        int groups = 0;
        // The total number of tuples
        int tuples = 0;
        // Are there suppressed tuples
        boolean suppressed = false;
        
        HashGroupifyEntry m = g.getFirstEntry();
        while (m != null) {
            if (m.count > 0) {
                tuples += m.count;
                groups += !anonymous || m.isNotOutlier ? 1 : 0;
                suppressed |= !m.isNotOutlier && anonymous;
            }
            m = m.nextOrdered;
        }
        
        // If there are suppressed tuples, they form one additional group
        groups += suppressed ? 1 : 0;
        
        // Compute AECS
        return new InformationLossDefault((double)tuples / (double)groups);
    }
}

@@ -788,16 +788,45 @@
 etric;%0A%0A
+import java.util.Map.Entry;%0A%0A
 import o
@@ -889,16 +889,16 @@
 yEntry;%0A
-
 import o
@@ -957,16 +957,78 @@
 oupify;%0A
+import org.deidentifier.arx.framework.check.history.MRUCache;%0A
 import o
@@ -1646,24 +1646,1213 @@
 alse);%0A    %7D
+%0A    %0A    /** A MRU cache for estimating lower bounds*/%0A    private MRUCache%3CNode%3E cache = new MRUCache%3CNode%3E(200);%0A    %0A    @Override%0A    public InformationLossDefault getLowerBound(Node node) %7B%0A        %0A        while (cache.size()%3E200) %7B%0A            getCache().remove(cache.removeHead());%0A        %7D%0A%0A        InformationLossDefault maximum = null;%0A        for (Entry%3CNode, InformationLossDefault%3E entry : getCache().entrySet()) %7B%0A            if (isPredecessor(node, entry.getKey()))%7B%0A                if (maximum == null %7C%7C maximum.compareTo(entry.getValue())%3C0) %7B%0A                    maximum = entry.getValue();%0A                    cache.touch(entry.getKey());%0A                %7D%0A            %7D%0A        %7D%0A        return maximum;%0A    %7D%0A    %0A    /**%0A     * Is node2 a predecessor of or equal to node1?%0A     */%0A    private boolean isPredecessor(final Node node1, final Node node2) %7B%0A        for (int i = 0; i %3C node2.getTransformation().length; i++) %7B%0A            if (node1.getTransformation()%5Bi%5D %3C node2.getTransformation()%5Bi%5D) %7B return false; %7D%0A        %7D%0A        return true;%0A    %7D%0A    %0A    @Override%0A    public void freeCache() %7B%0A        this.cache.clear();%0A        super.freeCache();%0A    %7D
 %0A%0A    @Overr
@@ -3178,16 +3178,33 @@
 f groups
+ with suppression
 %0A       
@@ -3771,16 +3771,16 @@
 l group%0A
-
         
@@ -3810,32 +3810,188 @@
 1 : 0;%0A        %0A
+        // Fill the cache%0A        cache.append(node);%0A        getCache().put(node, new InformationLossDefault((double)tuples / (double)g.size()));%0A        %0A
         // Compu

Implement first version of estimating lower bounds in AECS