package cn.edu.bjut.textmining.chapter5;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import cn.edu.bjut.textmining.util.TextVectorizer;

/** 自底向上平均连接；每步比较所有现存簇对。 */
public final class AverageLinkage {
    private AverageLinkage() {}

    public static double distance(List<Integer> a, List<Integer> b, double[][] vectors) {
        double total = 0;
        for (int i : a) {
            for (int j : b) {
                total += TextVectorizer.cosineDistance(vectors[i], vectors[j]);
            }
        }
        return total / ((double) a.size() * b.size());
    }

    public static int[] fit(double[][] vectors, int k, boolean printSteps) {
        KMeansEngine.validate(vectors);
        if (k < 1 || k > vectors.length) {
            throw new IllegalArgumentException("目标簇数无效");
        }
        List<List<Integer>> clusters = new ArrayList<>();
        for (int i = 0; i < vectors.length; i++) {
            clusters.add(new ArrayList<>(Collections.singletonList(i)));
        }
        int step = 0;
        while (clusters.size() > k) {
            double minimum = Double.POSITIVE_INFINITY;
            int a = -1, b = -1;
            for (int i = 0; i < clusters.size(); i++) {
                for (int j = i + 1; j < clusters.size(); j++) {
                    double d = distance(clusters.get(i), clusters.get(j), vectors);
                    if (d < minimum) {
                        minimum = d;
                        a = i;
                        b = j;
                    }
                }
            }
            if (printSteps) {
                System.out.printf(
                        "第%d步：%s + %s，平均距离=%.9f%n",
                        ++step, names(clusters.get(a)), names(clusters.get(b)), minimum);
            }
            clusters.get(a).addAll(clusters.get(b));
            clusters.remove(b);
        }
        int[] labels = new int[vectors.length];
        for (int c = 0; c < clusters.size(); c++) {
            for (int i : clusters.get(c)) {
                labels[i] = c;
            }
        }
        return labels;
    }

    private static String names(List<Integer> values) {
        List<String> names = new ArrayList<>();
        for (int value : values) {
            names.add("N" + (value + 1));
        }
        return names.toString();
    }
}