import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Linearization {
    private static void linearization(String clazz, List<String> result, Map<String, List<String>> class2Supers) {
        final List<String> supers = class2Supers.get(clazz);
        for (String sp : supers) {
            linearization(sp, result, class2Supers);
        }
        insertIfNotContained(result, clazz);
    }

    private static <T> void insertIfNotContained(List<T> list, T e) {
        if (!list.contains(e)) {
            list.add(0, e);
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> class2Supers = new HashMap<>();
        // 忽略了 AnyRef Any 简少继承信息填写
        class2Supers.put("Animal", Collections.emptyList());
        class2Supers.put("Furry", Arrays.asList("Animal"));
        class2Supers.put("HasLegs", Arrays.asList("Animal"));
        class2Supers.put("FourLegged", Arrays.asList("HasLegs"));
        class2Supers.put("Cat", Arrays.asList("Animal", "Furry", "FourLegged"));

        for (String clazz : Arrays.asList("Animal", "Furry", "FourLegged", "HasLegs", "Cat")) {
            List<String> result = new ArrayList<>();
            linearization(clazz, result, class2Supers);
            System.out.printf("%-10s: %s\n", clazz, result);
        }
    }
}

/*
输出:

Animal    : [Animal]
Furry     : [Furry, Animal]
FourLegged: [FourLegged, HasLegs, Animal]
HasLegs   : [HasLegs, Animal]
Cat       : [Cat, FourLegged, HasLegs, Furry, Animal]
*/