Разрешающий алгоритм наследования классов

Question

У меня есть список пар с информацией о наследовании классов, как это

<code>
[
  [Person, null],
  [Person, SpecialPerson], // Person extends SpecialPerson
  [SpecialPerson, VerySpecialPerson], // SpecialPerson extends VerySpecialPerson
]

Есть ли какой-то конкретный алгоритм для сглаживания этой информации?

Как это:

Персона -> SpecialPerson -> VerySpecialPerson

Answer 1

В итоге все сводится к DAG (направленный ациклический граф).Поэтому вы должны выполнить поиск в ширину или поиск в глубину.Вам нужен только упрощенный случай для деревьев.

Пример (BFS, псевдокод, не проверен):

List<Array<Typespec>> flatten(Array<Pair<Typespec,Typespec>> input) {
  List<Array<Typespec>> result;
  Queue<Array<Typespec>*> q;

  var elem=&result.append([null]);
  q.append(elem);
  while (!q.empty()) {
    for (i in input) {
      if (i.first==q.front().back()) {
        var elem=&result.append(q.front().clone().append(i.second));
        q.append(elem);
      }
    }
    q.pop_front();
  }
  return result;
}

Предполагается, что вы имели в виду [null,Person], а не наоборот,Обратите внимание, что он выдает null в начале каждого результата, что отличается от вашего примера.