public class DecisionNode extends Node {

    private static final long serialVersionUID = 5241099508522414606L;

    private double support;

    /**
     *
     */
    public DecisionNode() {
    }

    /**
     *
     * @param text
     * @param support
     */
    public DecisionNode(String text, double support) {
        super(text);
        this.support = support;
    }

    /**
     *
     * @return
     */
    public double getSupport() {
        return support;
    }

    /**
     *
     * @param support
     */
    public void setSupport(double support) {
        this.support = support;
    }

    /**
     *
     * @return
     */
    @Override
    public boolean isLeaf() {
        return true;
    }

} public abstract class Node implements TreeItem {

    private static final long serialVersionUID = 7147528097960598493L;

    /**
     *
     */
    protected String text;
    private EdgeBase edge = null;

    /**
     *
     */
    protected int depth;

    /**
     *
     */
    public Node() {
    }

    /**
     *
     * @param text
     */
    public Node(String text) {
        this.text = text;
    }

    /**
     *
     * @param text
     */
    public void setText(String text) {
        this.text = text;
    }

    /**
     *
     * @return
     */
    @Override
    public String getText() {
        return text;
    }

    /**
     *
     * @return
     */
    public EdgeBase getEdge() {
        return edge;
    }

    /**
     *
     * @param edge
     */
    public void setEdge(EdgeBase edge) {
        this.edge = edge;
    }

    /**
     *
     * @return
     */
    public boolean isRoot() {
        return edge == null;
    }

    /**
     *
     * @return
     */
    public Node getParent() {
        if (!isRoot()) {
            return edge.getParent();
        }

        return null;
    }

    /**
     *
     * @return
     */
    public int getDepth() {
        return depth;
    }

    /**
     *
     * @param depth
     */
    public void setDepth(int depth) {
        this.depth = depth;
    }

    /**
     *
     * @return
     */
    public abstract boolean isLeaf();

    /**
     *
     * @return
     */
    @Override
    public String toString() {
        return text;
    }

} public class TrainableEdge extends EdgeBase {

    private static final long serialVersionUID = 1865428303994838795L;

    private double[] evidences;
    private HashMap<String, Double> classSupports = new HashMap<>();

    /**
     *
     */
    public TrainableEdge() {
    }
    
    /**
     *
     * @param edge
     */
    public TrainableEdge(TrainableEdge edge) {
        this.evidences = edge.evidences;
        this.ambiguity = edge.ambiguity;
        this.classSupports = edge.classSupports;
        this.text = edge.text;
    }

    /**
     *
     * @param text
     */
    public TrainableEdge(String text) {
        super(text);
    }

    /**
     *
     * @param className
     * @param support
     */
    public void setClassSupport(String className, double support) {
        classSupports.put(className, support);
    }

    /**
     *
     * @return
     */
    public HashMap<String, Double> getClassSupports() {
        return classSupports;
    }

    /**
     *
     * @return
     */
    public Tuple<String, Double> getBestClass() {
        double best = -1;
        String bestClass = "";
        for (String c : classSupports.keySet()) {
            if (classSupports.get(c) > best) {
                best = classSupports.get(c);
                bestClass = c;
            }
        }
        return new Tuple<>(bestClass, best);
    }

    /**
     *
     * @return
     */
    public double[] getEvidences() {
        return evidences;
    }

    /**
     *
     * @param evidences
     */
    public void setEvidences(double[] evidences) {
        this.evidences = evidences;
    }
    
    
} public class TrainableIntermediateNode extends IntermediateNodeBase {

    private static final long serialVersionUID = 8452734258033681941L;
    
    private Attribute attribute;

    /**
     *
     * @return
     */
    public Attribute getAttribute() {
        return attribute;
    }

    /**
     *
     * @param attribute
     */
    public void setAttribute(Attribute attribute) {
        this.attribute = attribute;
    }
      
    
} public class Attribute {

    /**
     * The name of the attribute.
     */
    private final String name;
    
    /**
     * The index of the attribute in the dataset.
     */
    int index;

    /**
     * The dictionary of the terms.
     */
    private final HashMap<String, Term> nameToTerm = new LinkedHashMap<>();
    
    /**
     * The list of the crisp values.
     */
    private final List<Double> crispValues = new ArrayList<>();
    
    /**
     * The list of the terms of the attribute.
     */
    private final List<Term> terms = new ArrayList<>();
    
    /**
     *
     * @param name
     */
    public Attribute(String name) {
        this.name = name;
    }

    /**
     *
     * @return
     */
    public String getName() {
        return name;
    }

    /**
     *
     * @param termName
     * @param fuzzySet
     */
    public void addTerm(String termName, FuzzySet fuzzySet) {
        addTerm(new Term(termName, fuzzySet));
    }

    /**
     *
     * @param termName
     */
    public void addTerm(String termName) {
        addTerm(new Term(termName));
    }

    /**
     *
     * @param term
     */
    public void addTerm(Term term) {
        term.index = terms.size();
        nameToTerm.put(term.getName(), term);
        terms.add(term);
    }

    /**
     *
     * @param index
     * @return
     */
    public double get(int index) {
        return crispValues.get(index);
    }

    /**
     *
     * @param index
     * @param value
     */
    public void set(int index, double value) {
        crispValues.set(index, value);
        terms.forEach(t -> {
            t.set(index, value);
        });
    }
    
    /**
     *
     * @param rowIndex
     * @param termName
     * @return
     */
    public double get(int rowIndex, String termName) {
        return nameToTerm.get(termName).get(rowIndex);
    }

    /**
     *
     * @param rowIndex
     * @param termName
     * @param value
     */
    public void set(int rowIndex, String termName, double value) {
        nameToTerm.get(termName).set(index, value);
    }

    /**
     *
     * @param rowIndex
     * @param termIndex
     * @return
     */
    public double get(int rowIndex, int termIndex) {
        return terms.get(termIndex).get(rowIndex);
    }

    /**
     *
     * @param rowIndex
     * @param termIndex
     * @param value
     */
    public void set(int rowIndex, int termIndex, double value) {
        terms.get(termIndex).set(index, value);
    }

    /**
     *
     * @param termName
     * @return
     */
    public Term getTerm(String termName) {
        return nameToTerm.get(termName);
    }

    /**
     *
     * @param index
     * @return
     */
    public Term getTerm(int index) {
        return terms.get(index);
    }

    /**
     *
     * @param value
     */
    public void add(double value) {
        crispValues.add(value);
        terms.forEach(t -> {
            t.add(value);
        });
    }

    /**
     *
     * @return
     */
    public int getIndex() {
        return index;
    }

    /**
     *
     * @param values
     */
    public void add(double[] values) {
        double s = 0;
        for (int i = 0; i < values.length; i++) {
            terms.get(i).add(values[i], true /*fuzzified*/);
            s += values[i];
        }
        s /= values.length;
        crispValues.add(s);
    }

    /**
     *
     * @return
     */
    public int size() {
        return crispValues.size();
    }

    /**
     *
     * @return
     */
    public List<Term> getTerms() {
        return terms;
    }

    /**
     *
     * @return
     */
    public double[] getValues() {
        return crispValues.stream().mapToDouble(d -> d).toArray();
    }

    /**
     *
     * @return
     */
    @Override
    public String toString() {

        return String.format("%s: [%s]", name, String.join(",", terms.stream()
                .map(t -> t.getName()).collect(Collectors.toList())));
    }

} public class Dataset {

    /**
     * A dictionary of the input attributes. The key is the attribute name and the value is the attribute.
     */
    private final HashMap<String, Attribute> nameToAttribute = new LinkedHashMap<>();
    
    /**
     * List of the attributes of the dataset.
     */
    private final List<Attribute> attributes = new LinkedList<>();
    
    /**
     * A dictionary to count the number of samples of each label in the dataset.
     */
    private final HashMap<Integer, Integer> labelCounts = new HashMap<>();
    
    /**
     * To track the indices of the rows of each label.
     */
    private final HashMap<Integer, List<Integer>> labelSamples = new HashMap<>();

    /**
     * The name of the dataset, e.g., train-set.
     */
    private final String name;
    
    /**
     * The name of the attribute that represents the target, e.g., DR.
     */
    private String className;

    private final Random rng = new Random();

    /**
     *
     * @param name
     * @param className
     */
    public Dataset(String name, String className) {
        this.name = name;
        this.className = className;
    }

    /**
     *
     * @param className
     */
    public Dataset(String className) {
        this.name = UUID.randomUUID().toString();
        this.className = className;
    }

    /**
     *
     * @param attribute
     */
    public void addAttribute(Attribute attribute) {
        attribute.index = attributes.size();
        nameToAttribute.put(attribute.getName(), attribute);
        attributes.add(attribute);
    }

    /**
     *
     * @param values
     */
    public void addRow(double[] values) {

        int targetIndex = getTarget().index;
        int j = (int) values[targetIndex];
        int v = labelCounts.getOrDefault(j, 0);
        labelCounts.put(j, v + 1);
        List<Integer> l = labelSamples.getOrDefault(j, new ArrayList<>());
        l.add(getNumberOfRows());
        labelSamples.put(j, l);

        for (int i = 0; i < values.length; i++) {
            attributes.get(i).add(values[i]);
        }
    }

    /**
     *
     * @param values
     */
    public void addRow(double[][] values) {
        for (int i = 0; i < values.length; i++) {
            attributes.get(i).add(values[i]);
        }
    }

    /**
     *
     * @return
     */
    public int getNumberOfRows() {
        return attributes.get(0).size();
    }

    /**
     *
     * @return
     */
    public int getNumberOfAttributes() {
        return attributes.size();
    }

    /**
     *
     * @return
     */
    public Attribute getTarget() {
        return nameToAttribute.get(className);
    }

    /**
     *
     * @return
     */
    public List<Attribute> getInputs() {
        return nameToAttribute
                .entrySet()
                .stream()
                .filter(es -> !es.getKey().equals(className))
                .map(es -> es.getValue())
                .collect(Collectors.toList());
    }

    /**
     *
     * @param index
     * @return
     */
    public Attribute getAttribute(int index) {
        return attributes.get(index);
    }

    /**
     *
     * @param attributeName
     * @return
     */
    public Attribute getAttribute(String attributeName) {
        return nameToAttribute.get(attributeName);
    }

    /**
     *
     * @param index
     * @return
     */
    public double[] get(int index) {
        double[] values = new double[attributes.size()];
        for (int i = 0; i < values.length; i++) {
            values[i] = attributes.get(i).get(index);
        }
        return values;
    }

    /**
     *
     * @param attributeName
     * @return
     */
    public Dataset dropAttribute(String attributeName) {
        Dataset dataset = new Dataset(String.format("%s\\wo-%s", name, attributeName), className);
        attributes
                .stream()
                .filter((attribute) -> (!attribute.getName().equals(attributeName)))
                .forEachOrdered((attribute) -> {
                    dataset.addAttribute(attribute);
                });

        return dataset;
    }

    /**
     * @deprecated 
     * @param numberOfSamples
     * @return 
     */
    public Dataset bagging(int numberOfSamples) {
        Dataset dataset = new Dataset(String.format("bootstrapped-%s", UUID.randomUUID().toString()), className);

        attributes.stream().map((attr) -> {
            Attribute newAttr = new Attribute(attr.getName());
            attr.getTerms().forEach((term) -> {
                newAttr.addTerm(term.getName(), term.getFuzzySet());
            });
            return newAttr;
        }).forEachOrdered((newAttr) -> {
            dataset.addAttribute(newAttr);
        });

        for (int i = 0; i < numberOfSamples; i++) {
            int j = rng.nextInt(getNumberOfRows());
            dataset.addRow(this.get(j));
        }

        return dataset;
    }

    /**
     * This function is used to perfprm the bagging step. 
     * @param samplingRate
     * @return 
     */
    public Tuple<Dataset, Dataset> bagging2(double samplingRate) {

        Dataset dataset = new Dataset(String.format("bootstrapped-%s", UUID.randomUUID().toString()), className);
        Dataset oobDataset = new Dataset(String.format("oob-%s", UUID.randomUUID().toString()), className);

        attributes.stream().map((attr) -> {
            Attribute newAttr = new Attribute(attr.getName());
            attr.getTerms().forEach((term) -> {
                newAttr.addTerm(term.getName(), term.getFuzzySet());
            });
            return newAttr;
        }).forEachOrdered((newAttr) -> {
            dataset.addAttribute(newAttr);
        });

        attributes.stream().map((attr) -> {
            Attribute newAttr = new Attribute(attr.getName());
            attr.getTerms().forEach((term) -> {
                newAttr.addTerm(term.getName(), term.getFuzzySet());
            });
            return newAttr;
        }).forEachOrdered((newAttr) -> {
            oobDataset.addAttribute(newAttr);
        });

        int size = this.getNumberOfRows();

        int samplingSize = (int) Math.round(size * samplingRate);
        
        double [] Q = new double[size];
        Arrays.fill(Q, 1);
        
        IntStream.range(0, size).forEach(i -> Q[i] += i);
        
        for (int i = 0; i < samplingSize; i++) {
            double p = size * RandomFactory.nextDouble();
            int idx = (int)p;
            if(p < Q[idx]) {
                dataset.addRow(this.get(idx));
            }
            else {
                oobDataset.addRow(this.get(idx));
            }
        }

        return new Tuple<>(dataset, oobDataset);
    }

    /**
     * @deprecated 
     * @param samplingRate
     * @return 
     */
    public Tuple<Dataset, Dataset> bagging(double samplingRate) {

        Dataset dataset = new Dataset(String.format("bootstrapped-%s", UUID.randomUUID().toString()), className);
        Dataset oobDataset = new Dataset(String.format("oob-%s", UUID.randomUUID().toString()), className);

        attributes.stream().map((attr) -> {
            Attribute newAttr = new Attribute(attr.getName());
            attr.getTerms().forEach((term) -> {
                newAttr.addTerm(term.getName(), term.getFuzzySet());
            });
            return newAttr;
        }).forEachOrdered((newAttr) -> {
            dataset.addAttribute(newAttr);
        });

        attributes.stream().map((attr) -> {
            Attribute newAttr = new Attribute(attr.getName());
            attr.getTerms().forEach((term) -> {
                newAttr.addTerm(term.getName(), term.getFuzzySet());
            });
            return newAttr;
        }).forEachOrdered((newAttr) -> {
            oobDataset.addAttribute(newAttr);
        });

        int size = labelCounts
                .entrySet()
                .stream()
                .map(e -> e.getValue())
                .mapToInt(Integer::intValue)
                .min()
                .orElse(0);

        size = (int) Math.round(size * samplingRate);

        for (int l : labelCounts.keySet()) {

            List<Integer> indexes = labelSamples.get(l);

            int[] permutation = RandomFactory.getPermutation(indexes.size());

            int[] bag = Arrays.stream(permutation).limit(size).toArray();
            int[] oob = Arrays.stream(permutation).skip(size).toArray();

            for (int i : bag) {
                int j = indexes.get(i);
                dataset.addRow(this.get(j));
            }

            for (int i : oob) {
                int j = indexes.get(i);
                oobDataset.addRow(this.get(j));
            }

        }

        return new Tuple<>(dataset, oobDataset);
    }

    /**
     *
     * @param className
     */
    public void setClassName(String className) {
        this.className = className;
    }

    /**
     * To create an empty dataset that has the same structure.
     * @param clonedName
     * @return 
     */
    public Dataset cloneWithNoRows(String clonedName) {

        if (clonedName == null) {
            clonedName = String.format("Data_%s", UUID.randomUUID().toString());
        }
        Dataset dataset = new Dataset(clonedName, className);

        attributes.stream().map((attr) -> {
            Attribute newAttr = new Attribute(attr.getName());
            attr.getTerms().forEach((term) -> {
                newAttr.addTerm(term.getName(), term.getFuzzySet());
            });
            return newAttr;
        }).forEachOrdered((newAttr) -> {
            dataset.addAttribute(newAttr);
        });

        return dataset;
    }

    /**
     *
     * @return
     */
    public String getClassName() {
        return className;
    }

    /**
     *
     * @return
     */
    public String getName() {
        return name;
    }

    /**
     *
     * @return
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(name);
        sb.append(" {\n");
        attributes.stream().map((a) -> {
            sb.append("\t");
            sb.append(a);
            return a;
        }).forEachOrdered((_item) -> {
            sb.append(";\n");
        });
        sb.append("}");
        return sb.toString();
    }

    /**
     *
     * @return
     */
    public HashMap<String, Attribute> getNameToAttribute() {
        return nameToAttribute;
    }
    
    

} public class Term {
    
    /**
     * The list of the fuzzy values.
     */
    private final List<Double> storage = new ArrayList<>();
    
    /**
     * The term name.
     */
    private final String name;
    
    /**
     * The fuzzy set of the term that will be used to convert the crisp value into a fuzzy membership value.
     */
    private FuzzySet fuzzySet = new IdentityFuzzySet();
    
    /**
     * The index of the term.
     */
    int index;

    /**
     *
     * @param name
     */
    public Term(String name) {
        this.name = name;
    }

    /**
     *
     * @param name
     * @param fuzzySet
     */
    public Term(String name, FuzzySet fuzzySet) {
        this.name = name;
        this.fuzzySet = fuzzySet;
    }

    /**
     *
     * @param x
     */
    public void add(double x) {
        storage.add(fuzzySet.getMembership(x));
    }  
    
    /**
     *
     * @param x
     * @param fuzzified
     */
    public void add(double x, boolean fuzzified) {
        if(!fuzzified) {
            x = fuzzySet.getMembership(x);
        }
        storage.add(x);
    }      
    
    /**
     *
     * @return
     */
    public double [] getValues() {
        return storage.stream().mapToDouble(d -> d).toArray(); 
    }
    
    /**
     *
     * @param index
     * @return
     */
    public double get(int index) {
        return storage.get(index);
    }
    
    /**
     *
     * @param index
     * @param x
     */
    public void set(int index, double x) {
        storage.set(index, fuzzySet.getMembership(x));
    }

    /**
     *
     * @return
     */
    public String getName() {
        return name;
    }

    /**
     *
     * @return
     */
    public FuzzySet getFuzzySet() {
        return fuzzySet;
    }

    /**
     *
     * @return
     */
    @Override
    public String toString() {
        return name;
    }

    /**
     *
     * @param obj
     * @return
     */
    @Override
    public boolean equals(Object obj) {
        if(obj == this) return true;
        if(obj instanceof Term) {
            return name.equals(((Term)obj).name);
        }
        return false;
    }

    /**
     *
     * @return
     */
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 71 * hash + Objects.hashCode(this.name);
        return hash;
    }
    
    
    
} public class RandomFactory {

    private static Random seedRNG = new Random();
    private static HashSet<Long> seeds = new HashSet<>();
//    private static final org.slf4j.Logger logger = org.slf4j.LoggerFactory.getLogger(RandomFactory.class);

    private static ThreadLocal<Random> random = new ThreadLocal<Random>() {
        protected synchronized Random initialValue() {
            // For the first RNG, we use the default seed so that we can
            // get repeatable results for random algorithms.
            // Note that this may or may not be the main thread.
            long seed = 19650218L;

            // Make sure other threads not to use the same seed.
            // This is very important for some algorithms such as random forest.
            // Otherwise, all trees of random forest are same except the main thread one.
            if (!seeds.isEmpty()) {
                do {
                    seed = probablePrime(19650218L, 256, seedRNG);
                } while (seeds.contains(seed));
            }

//            logger.info(String.format("Set RNG seed %d for thread %s", seed, Thread.currentThread().getName()));
            seeds.add(seed);
            return new Random(seed);
        }
    };

    /**
     *
     */
    public static void setSeed() {
        java.security.SecureRandom sr = new java.security.SecureRandom();
        byte[] bytes = sr.generateSeed(Long.BYTES);
        long seed = 0;
        for (int i = 0; i < Long.BYTES; i++) {
            seed <<= 8;
            seed |= (bytes[i] & 0xFF);
        }

        setSeed(seed);
    }

    /**
     *
     * @param seed
     */
    public static void setSeed(long seed) {
        if (seeds.isEmpty()) {
            seedRNG.setSeed(seed);
            random.get().setSeed(seed);
            seeds.clear();
            seeds.add(seed);
        } else {
            random.get().setSeed(seed);
            seeds.add(seed);
        }
    }

    /**
     * Returns a probably prime number greater than n.
     *
     * @param n the returned value should be greater than n.
     * @param k a parameter that determines the accuracy of the primality test
     * @return 
     */
    public static long probablePrime(long n, int k) {
        return probablePrime(n, k, random.get());
    }

    /**
     * Returns a probably prime number.
     */
    private static long probablePrime(long n, int k, Random rng) {
        long seed = n + rng.nextInt(899999963); // The largest prime less than 9*10^8
        for (int i = 0; i < 4096; i++) {
            if (isProbablePrime(seed, k, rng)) {
                break;
            }
            seed = n + rng.nextInt(899999963);
        }

        return seed;
    }

    /**
     * Returns a stream of prime numbers to be used as RNG seeds.
     *
     * @param n the returned value should be greater than n.
     * @param k a parameter that determines the accuracy of the primality test
     * @return 
     */
    public static LongStream seeds(long n, int k) {
        return LongStream.generate(() -> probablePrime(n, k, seedRNG));
    }

    /**
     * Returns true if x is a power of 2.
     * @param x
     * @return 
     */
    public static boolean isPower2(int x) {
        return x > 0 && (x & (x - 1)) == 0;
    }

    /**
     * Returns true if n is probably prime, false if it's definitely composite.
     * This implements Miller-Rabin primality test.
     *
     * @param n an odd integer to be tested for primality
     * @param k a parameter that determines the accuracy of the test
     * @return 
     */
    public static boolean isProbablePrime(long n, int k) {
        return isProbablePrime(n, k, random.get());
    }

    /**
     * Returns true if n is probably prime, false if it's definitely composite.
     * This implements Miller-Rabin primality test.
     *
     * @param n an odd integer to be tested for primality
     * @param k a parameter that determines the accuracy of the test
     * @param rng random number generator
     */
    private static boolean isProbablePrime(long n, int k, Random rng) {
        if (n <= 1 || n == 4) {
            return false;
        }
        if (n <= 3) {
            return true;
        }

        // Find r such that n = 2^d * r + 1 for some r >= 1
        int s = 0;
        long d = n - 1;
        while (d % 2 == 0) {
            s++;
            d = d / 2;
        }

        for (int i = 0; i < k; i++) {
            long a = 2 + rng.nextLong() % (n - 4);
            long x = power(a, d, n);
            if (x == 1 || x == n - 1) {
                continue;
            }

            int r = 0;
            for (; r < s; r++) {
                x = (x * x) % n;
                if (x == 1) {
                    return false;
                }
                if (x == n - 1) {
                    break;
                }
            }

            // None of the steps made x equal n-1.
            if (r == s) {
                return false;
            }
        }
        return true;
    }

    private static long power(long x, long y, long p) {
        long res = 1;      // Initialize result
        x = x % p;  // Update x if it is more than or
        // equal to p
        while (y > 0) {
            // If y is odd, multiply x with result
            if ((y & 1) == 1) {
                res = (res * x) % p;
            }

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
    
    /**
     *
     * @param n
     * @return
     */
    public static int[] getPermutation(int n) {
        return random.get().getPermutation(n);
    }
    
    /**
     *
     * @return
     */
    public static double nextDouble() {
        return random.get().nextDouble();
    }
    
    /**
     *
     * @return
     */
    public static double nextGaussian() {
        return random.get().nextGaussian();
    }
    
    /**
     *
     * @param scale
     * @param offset
     * @return
     */
    public static double nextGaussian(double scale, double offset) {
        return random.get().nextGaussian() * scale + offset;
    }    
} public class Tuple<T1, T2> {
    private T1 first;
    private T2 second;

    /**
     *
     */
    public Tuple() {
    }

    /**
     *
     * @param first
     * @param second
     */
    public Tuple(T1 first, T2 second) {
        this.first = first;
        this.second = second;
    }

    /**
     *
     * @return
     */
    public T1 getFirst() {
        return first;
    }

    /**
     *
     * @return
     */
    public T2 getSecond() {
        return second;
    }

    /**
     *
     * @param first
     */
    public void setFirst(T1 first) {
        this.first = first;
    }

    /**
     *
     * @param second
     */
    public void setSecond(T2 second) {
        this.second = second;
    }

    /**
     *
     * @return
     */
    @Override
    public String toString() {
        return String.format("(%s, %s)", first, second);
    }
    
    
} public class Utils {

    /**
     *
     */
    public static double EPSILON = 1e-9;

    /**
     *
     * @param target
     * @param source
     * @return
     */
    public static double[] sortBy(double[] target, double[] source) {

        Tuple<Integer, Double>[] map = new Tuple[source.length];
        for (int i = 0; i < source.length; i++) {
            map[i] = new Tuple<>(i, source[i]);
        }

        Arrays.sort(map, (a, b) -> b.getSecond().compareTo(a.getSecond()));

        double[] sortedTarget = new double[target.length];

        for (int i = 0; i < target.length; i++) {
            sortedTarget[i] = target[map[i].getFirst()];
        }

        return sortedTarget;
    }

    /**
     *
     * @param condition
     * @param conclusion
     * @return
     */
    public static double subsethood(double[] condition, double[] conclusion) {

        double s = Arrays.stream(condition).boxed().mapToDouble(Double::doubleValue).sum();
//        if(s == 0) {
//            return 1;
//        }
        double ret = Streams.zip(
                Arrays.stream(condition).boxed(),
                Arrays.stream(conclusion).boxed(),
                (c1, c2) -> Math.min(c1, c2)
        ).mapToDouble(Double::doubleValue).sum() / s;

        return ret;
    }

    /**
     *
     * @param a
     * @return
     */
    public static boolean embpty(double[] a) {
        double s = Arrays.stream(a).sum();
//        System.out.println(s + " " + (s == 0));
        return s == 0;
    }

    /**
     *
     * @param distribution
     * @param normalize
     * @return
     */
    public static double ambiguity(double[] distribution, Optional<Boolean> normalize) {

        //Eqs (2, 3, 4)
        Supplier<Stream<Double>> streamSupplier = () -> Arrays.stream(distribution).boxed();
        Stream<Double> dStream = streamSupplier.get();

        if (normalize.orElse(Boolean.TRUE)) {
            double maxValue = streamSupplier
                    .get()
                    .mapToDouble(Double::doubleValue)
                    .max()
                    .getAsDouble() + EPSILON;
            dStream = streamSupplier.get().map((t) -> t / maxValue);
        }

        List<Double> distributionList = dStream.sorted(Comparator.reverseOrder()).collect(Collectors.toList());

        distributionList.add(0d);
        Supplier<Stream<Double>> streamSupplier2 = () -> distributionList.stream();
        List<Tuple<Double, Double>> collected = Streams.zip(streamSupplier2.get().limit(distributionList.size() - 1),
                streamSupplier2.get().skip(1), (u, t) -> new Tuple<>(u, t)).collect(Collectors.toList());

        double g = IntStream.range(0, collected.size())
                .mapToDouble(i -> Math.log(i + 1) * (collected.get(i).getFirst() - collected.get(i).getSecond())).sum();

        return g;

    }
    
    /**
     *
     * @param model
     */
    public static void printTree(InferenceModelSpec model) {
        System.out.println(getStringTree(model.getTree(), ""));
    }
    private static String getStringTree(Node node, String prefix) {
        
        String s = "";
        
        if(node.isLeaf()) {
            s += String.format("%s\t\t[%s (%.3f)]\n", prefix, node.getText(), ((DecisionNode)node).getSupport());
        }
        else {
            s += String.format("%s|%s, %.3f, %.3f|\n", prefix, node.getText(), ((IntermediateNode)node).getAmbiguity(), ((IntermediateNode)node).getLambda());
            for(EdgeBase e : ((IntermediateNode) node).getEdges()) {
                s += String.format("%s\t<%s, %.3f>\n", prefix, e.getText(), e.getAmbiguity());
                s += getStringTree(e.getChild(), "\t\t" + prefix);
            }
        }
        return s;

    }

    /**
     *
     * @param model
     */
    public static void printRules(InferenceModelSpec model) {
        for (DecisionSet s : model.getDecisionSets()) {
            for(DecisionNode leaf : s.getDecisionNodes()) {
                printRule(leaf);
            }
        }
    }
    
    private static void printRule(DecisionNode leaf) {
        List<String> conditions = new ArrayList<>();
        fdt.core.Node node2 = leaf.getParent();
        fdt.core.Node node = leaf;
        while(node2 != null) {
            conditions.add(0, String.format("%s IS %s", node2.getText(), node.getEdge().getText()));
            node = node2;
            node2 = node2.getParent();
        }
        String cond = String.join(" AND ", conditions);
        
        System.out.println(String.format("IF %s THEN %s [%.3f, %.3f]", cond, leaf.getText(), leaf.getSupport(), ((IntermediateNode) leaf.getParent()).getAmbiguity()));
    }

    /**
     *
     * @param confusionMatrix
     * @return
     */
    public static double printClassificationReport(HashMap<String, HashMap<String, Integer>> confusionMatrix) {
        System.out.println(String.format("\t\t\t%s", String.join("\t", confusionMatrix.keySet())));

        confusionMatrix.keySet().stream().map((c) -> {
            System.out.println(String.format("%s\t\t:", c));
            return c;
        }).map((c) -> {
            confusionMatrix.keySet().forEach((c2) -> {
                System.out.print(String.format("\t%d\t", confusionMatrix.get(c).get(c2)));
            });
            System.out.print(String.format("\t%d\t", confusionMatrix.get(c).get("UnKnown")));

            return c;
        }).forEachOrdered((__) -> {
            System.out.println("");
        });

        double sensitivity = (confusionMatrix.get("Class0").get("Class0") * 1.0) / ((double) confusionMatrix.get("Class0").get("Class0") + confusionMatrix.get("Class0").get("Class1"));
        double specifity = (confusionMatrix.get("Class1").get("Class1") * 1.0) / ((double) confusionMatrix.get("Class1").get("Class1") + confusionMatrix.get("Class1").get("Class0"));

        double npv = (confusionMatrix.get("Class0").get("Class0") * 1.0) / ((double) confusionMatrix.get("Class0").get("Class0") + confusionMatrix.get("Class1").get("Class0"));
        double accuracy = (confusionMatrix.get("Class0").get("Class0") * 1.0 + confusionMatrix.get("Class1").get("Class1"))
                / ((double) confusionMatrix.get("Class0").get("Class0")
                + confusionMatrix.get("Class1").get("Class1")
                + confusionMatrix.get("Class1").get("Class0")
                + confusionMatrix.get("Class0").get("Class1"));

        double precision = (confusionMatrix.get("Class1").get("Class1") * 1.0) / ((double) confusionMatrix.get("Class1").get("Class1") + confusionMatrix.get("Class0").get("Class1"));

        double hm = 2 * (specifity * sensitivity) / (specifity + sensitivity);

        DecimalFormat df = new DecimalFormat("0.000");
        System.out.println(String.format("Accuracy: %s", df.format(accuracy)));
        System.out.println(String.format("Specifity: %s", df.format(specifity)));
        System.out.println(String.format("Sensitivity: %s", df.format(sensitivity)));
        System.out.println(String.format("HM: %s", df.format(hm)));
        System.out.println(String.format("Precision: %s", df.format(precision)));
        System.out.println(String.format("Negative Predicted Value (NPV): %s", df.format(npv)));
        return hm;

    }

    /**
     *
     * @param dataset
     * @param inferenceEngine
     * @return
     */
    public static double evaluate(Dataset dataset, InferenceEngine inferenceEngine) {

        Attribute targetAttr = dataset.getTarget();

        HashMap<String, HashMap<String, Integer>> confusionMatrix = new HashMap<>();

        targetAttr.getTerms().stream().map((term1) -> {
            HashMap<String, Integer> entry = new HashMap<>();
            confusionMatrix.put(term1.getName(), entry);
            return entry;
        }).forEachOrdered((entry) -> {
            targetAttr.getTerms().forEach((term2) -> {
                entry.put(term2.getName(), 0);
            });
            entry.put("UnKnown", 0);
        });

        //IntStream.range(0, dataset.getNumberOfRows()).parallel().forEach(i ->{
        
        for (int i = 0; i < dataset.getNumberOfRows(); i++) {
            HashMap<String, Double> inputSpec = new HashMap<>();
            for (Attribute att : dataset.getInputs()) {
                for (Term term : att.getTerms()) {
                    String k = String.format("%s.%s", att.getName(), term.getName());
                    inputSpec.put(k, term.get(i));
                }
            }

            PredictionResult res = inferenceEngine.predict(inputSpec);
            int classIndex = (int) targetAttr.get(i);
            String expectedClass = targetAttr.getTerm(classIndex).getName();
            HashMap<String, Integer> map = confusionMatrix.get(expectedClass);
            int v = map.get(res.getClassName());
            confusionMatrix.get(expectedClass).put(res.getClassName(), v + 1);
        //});
        
        }
        return printClassificationReport(confusionMatrix);
    }

    /**
     *
     * @param x
     * @param i
     * @param j
     */
    public static void swap(int[] x, int i, int j) {
        int s = x[i];
        x[i] = x[j];
        x[j] = s;
    }

    /**
     *
     * @param x
     * @param i
     * @param j
     */
    public static void swap(float[] x, int i, int j) {
        float s = x[i];
        x[i] = x[j];
        x[j] = s;
    }

    /**
     *
     * @param x
     * @param i
     * @param j
     */
    public static void swap(double[] x, int i, int j) {
        double s = x[i];
        x[i] = x[j];
        x[j] = s;
    }

    /**
     *
     * @param x
     * @param i
     * @param j
     */
    public static void swap(String[] x, int i, int j) {
        String s = x[i];
        x[i] = x[j];
        x[j] = s;
    }

    /**
     *
     * @param coefficients
     * @return
     */
    public static Complex_F64[] findRoots(double[] coefficients) {
        int n = coefficients.length - 1;

        // Construct the companion matrix
        DMatrixRMaj c = new DMatrixRMaj(n, n);

        double a = coefficients[n];
        for (int i = 0; i < n; i++) {
            c.set(i, n - 1, -coefficients[i] / a);
        }
        for (int i = 1; i < n; i++) {
            c.set(i, i - 1, 1);
        }

        // use generalized eigenvalue decomposition to find the roots
        EigenDecomposition_F64<DMatrixRMaj> evd = DecompositionFactory_DDRM.eig(n, false);

        evd.decompose(c);

        Complex_F64[] roots = new Complex_F64[n];

        for (int i = 0; i < n; i++) {
            roots[i] = evd.getEigenvalue(i);
        }

        return roots;
    }
    
    /**
     *
     * @param a
     * @param b
     * @return
     */
    public static double cosineSimilarity(double [] a, double [] b) {
        double s1 = 0, s2 = 0, s3 = 0;
        
        for(int i = 0; i < a.length; i++) {
            s1 += a[i] * b[i];
            s2 += a[i] * a[i];
            s3 += b[i] * b[i];
        }
        
        return s1 / (Math.sqrt(s2) * Math.sqrt(s3));
    }
    
    /**
     *
     * @param a
     * @param b
     * @return
     */
    public static double getNormalizedSimilarity(double [] a, double [] b) {
        double s = cosineSimilarity(a, b);
        s += 1;
        s /= 2;
        return s;
    }
    
    /**
     *
     * @param vec
     * @param numberOfSamples
     * @param scales
     * @param offsets
     * @param sampleAroundInstance
     * @return
     */
    public double [][] getSamples(double [] vec, int numberOfSamples, double [] scales, double [] offsets, boolean sampleAroundInstance) {
        
        
        double [][] samples = new double[numberOfSamples][vec.length];
        
        double [] weights = new double[numberOfSamples];
        
        for(int i = 0; i < numberOfSamples; i++) {
            for(int j = 0; j < vec.length; j++) {
                double v = RandomFactory.nextGaussian() * scales[j];
                v += sampleAroundInstance ? vec[j] : offsets[j];
                samples[i][j] = v;
            }
            double w = getNormalizedSimilarity(vec, samples[i]);
            weights[i] = w;
        }
        
        
        
        return samples;
    }
}
import com.google.common.collect.Streams;
import fdt.core.DecisionNode;
import fdt.core.Node;
import fdt.core.TrainableEdge;
import fdt.core.TrainableIntermediateNode;
import fdt.data.Attribute;
import fdt.data.Dataset;
import fdt.data.Term;
import fdt.utils.RandomFactory;
import fdt.utils.Tuple;
import fdt.utils.Utils;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

package fdt.estimators;


/**
 *
 * @author Mohammed Jabreel
 */

/**
 * This class is used to train a fuzzy decision tree. 
 
 */
public class TreeEstimator implements Estimator {

    /**
     * The significance level parameter (alpha). 
     * It is used to filter out the fuzzy partitions 
     * that have values less than alpha (i.e., the significance level) 
     * by setting these values to zero.
     */
    private double significanceLevel = 0.5;
    
    /**
     * The level of truth parameter (beta).
     * It is used to stop the growing and determine the leaves nodes.
     * A node is a leaf if it has a classification support greater or equal to beta.
     */
    private double levelOfTruth = 0.7;
    
    /**
     * The maximum depth of the tree. The value -1 means this parameter is not used.
     */
    private int depthMax = -1;
    
    /**
     * To specify the number of attributes that can be used in the growing process to chose the best attribute.
     * The value -1 means, we use all the attributes.
     */
    private int attributesSamplingSize = -1;
    
    

   /**
   * Constructor that sets default parameters' values.
   */    
    public TreeEstimator() {
    }

    /**
     *
     * @param significanceLevel
     * @param levelOfTruth
     */
    public TreeEstimator(double significanceLevel, double levelOfTruth) {
        this.significanceLevel = significanceLevel;
        this.levelOfTruth = levelOfTruth;
    }

    /**
     * This function is used to train a fuzzy decision tree on a dataset.
     * @param dataset: the training dataset to be used. @see fdt.data.Dataset
     * @return an instance of fdt.core.Node represents the root of the obtained tree.
     */
    public Node fit(Dataset dataset) {
        Attribute targetAttribute = dataset.getTarget();
        Tuple<Attribute, Double> bestAttributeValues = getBestAttribute(dataset, null);
        if (bestAttributeValues != null) {

            TrainableIntermediateNode root = new TrainableIntermediateNode();