Как называется эта структура данных графа из компилятора карты Quake? И какие есть альтернативы Rust? ⇐ C++

[Anonymous]

Я наткнулся на эту структуру данных в исходном коде компилятора карты Quake (специально для генерации графов портала), конкретную реализацию и ее использование вы можете посмотреть там. Вот краткое описание:

Узлы соединены Порталом. Узел имеет указатель на связанный список порталов:

struct Node { Портал *порталы, // .. } Однако, поскольку портал подключен к двум узлам, он отслеживает два:

struct Portal { Узел *узлы[2], // .. } Узлы упорядочены как передний и задний, в зависимости от ориентации портала. (Существует детерминированный способ определить, какая сторона портала находится сзади, а какая спереди, но для данного обзора это не имеет значения.)

Поскольку портал используется как связанный список, он также отслеживает два следующих, по одному для каждого узла:

struct Portal { // .. Портал *следующий[2], } Чтобы перебрать список порталов в данном узле:

intside; for (портал = node.portals; портал; портал->nexts[сторона]) { // чтобы определить, какой следующий наш собственный сторона = портал->узлы[0] == узел? 0:1; // остальная часть кода } Пример графа портала, представленного этой структурой данных:

(Node_A) — Portal_1 — (Node_B) — Portal_5 — (Node_E) | | / Портал_2 Портал_3 спереди/сзади | | / (Узел_C) — Портал_4 — (Узел_D) Простая структура, подобная приведенной выше, представлена ​​следующим образом: (для простоты порталы отсортированы по номеру)

Node_A -> Portal_1 Узел_B -> Портал_1 Узел_C -> Портал_2 Узел_D -> Портал_3 Узел_E -> Портал_5 Портал_1 -> следующие: [Портал_2, Портал_3], узлы: [Узел_А, Узел_Б] Portal_2 -> следующее: [Null, Portal_4], узлы: [Node_A, Node_C] Портал_3 -> следующие: [Портал_5, Портал_4], узлы: [Узел_B, Узел_D] Portal_4 -> следующее: [Null, Null], узлы: [Node_C, Node_D] Portal_5 -> следующее: [Null, Null], узлы: [Node_B, Node_E] // Альтернативно, если я перегруппирую их как передние и задние (что, я думаю, будет легче понять): Портал_1 -> спереди: [Портал_2, Узел_А], сзади: [Портал_3, Узел_Б] Portal_2 -> спереди: [Null, Node_A], сзади: [Portal_4, Node_C] Портал_3 -> спереди: [Портал_5, Узел_B], сзади: [Портал_4, Узел_D] Portal_4 -> спереди: [Null, Node_C], сзади: [Null, Node_D] Portal_5 -> спереди: [Null, Node_B], сзади: [Null, Node_E] // читается как: передний узел — (nodes[front]), а следующий, принадлежащий этому узлу, — (nexts[front]) и т. д. Итак, мои вопросы:
[*]Есть ли имя для этой структуры данных? [*]Если бы мне пришлось реализовать что-то подобное в Rust для аналогичного варианта использования, как бы я мог это реализовать или какие есть жизнеспособные альтернативы? Похоже, именно эта структура данных была выбрана для исходного проекта, потому что ее легко отсоединить и разместить новые порталы, заглянуть на другую сторону и т. д. Я бы просто сохранил ее, если бы не тот факт, что ссылка списки не совсем подходят для Rust.