Quatro: формат линейного представления графа

Хранение информации в виде графа - это альтернатива табличному представлению данных. Опишу здесь формат записи связанных данных, который мне представляется наиболее оптимальным.

Связи хранятся в виде одного файла.
Файл содержит двоичные числа одинаковой разрядности.
Первое число - единица и одновременно является идентификатором первого узла. Это обстоятельство позволяет легко определить разрядность остальных чисел.
Файл не может содержать болше чисел, чем значение самого большого из них.
Признак идентификатора узла - нечётное число равное своему порядковому номеру в файле.
Признак связи - нечётное число отличное от своего порядкового номера в файле. Это число равно одному из имеющихся в файле идентификаторов узлов.
В узле без связей сразу после идентификатора записан ноль.
В узле со связями сразу после идентификатора следует число с порядковым номером связи в файле.
В последней связи узла сразу после идентификатора другого узла записан ноль.
В прочих связях узла после идентификатора другого узла записан порядковый номер следующей связи.
На месте удалённой связи записываются два числа со значением ноль. Предыдущая связь переключается на следующую за удалённой.


Значения хранятся в отдельных файлах. В качестве имени файла берётся идентификатор соответствующего узла.

Идентификатор узла определяется по хэшу значения.

Новые узлы и связи записываются в конец файла.  Добавление связи состоит из нескольких этапов:
1) последняя связь проверяется на возможность записи (ноль - в качастве ссылки на следующую связь)
2) связь блокируется (единица - в качастве ссылки на следующую связь)
3) в конец файла дописывается связь с другим узлом (и ноль - в качастве ссылки на следующую связь)
4) в последнюю связь записывается вместо единицы порядковый номер добавленной ссылки, после чего добавленная ссылка считается последней

Гонки

Старт

Здесь шумно. У линии старта толпятся болельщики. В воздухе запах жжёной резины. Покрышки моего автомобиля ещё горячие. Скоро начнётся второй заезд. Он определит победителя соревнований.

Уверен, что победа достанется мне. Почему я в этом уверен? Кто я такой? Я такой же гонщик, как и ты. Выгляни из окна. Мой жёлтый скоростной болид стоит слева от твоего автомобиля. Смотри, я машу тебе рукой.

Заметил, какой необычный корпус у моей машины? Обтекаемая форма позволяет мне нестись по трассе быстрее пули. Тебе будет трудно меня обогнать. Лучше закрой книгу и иди домой, посмотри мультики.

Не надо показывать мне кулак, это не спортивно. Будешь читать, дальше? Ну, ладно, давай потягаемся силою. Только учти, чтобы получить хоть один шанс на успех, тебе нужно пройти школу гонщиков.

Школа гонщиков

Добро пожаловать в нашу школу. Я твой учитель. Мой предмет называется "подготовить гонщика". Почему тебе это название кажется странным? Название как название.

Я обучу тебя приёмам экстремального вождения автомобиля. Ты спрашиваешь, как меня зовут? Тебе знать этого не положено. Гонщики не должны знать, кто их обучил. Меньше знаешь -- быстрее едешь! Всё равно, когда ты покинешь здание школы, ты сразу забудешь о её существовании.

Главное запомни, что я тебе сейчас скажу: "В игре есть машины и на них можно ехать быстро или медленно." Почему ты говоришь, что это чепуха. Это не чепуха. Лучше запиши себе в тетрадь, чтобы не забыть. Записал? Молодец, что записал. Теперь ты настоящий гонщик и можешь принять участие в соревнованиях.

Не веришь? Хорошо. Вот тебе учебный автомобиль. У него на двери кнопка. Читай, что на ней написано. Да, верно. Написано: "посадить гонщика". Жми, не бойся.

Так, теперь ты сидишь за рулём. Нет, руль вертеть не нужно. Это за тебя сделает компьютер. Да, согласен, это круче, чем коробка-автомат. Чтобы ехать быстро, жми на кнопку с надпистью "ехать быстро". Чтобы ехать медленно, жми на кнопку рядом. На ней так и написано: "ехать медленно".

Не буду спорить с тобой. Это и правда проще простого. По прямому участку трассы ты едешь быстро. На крутом вираже сбавляешь скорость и едешь медленно.

Ты спрашиваешь, где кнопка с надписью "остановиться"? Её нет. Это же спортивный автомобиль. Не беспокойся, в конце трассы компьютер остановит его автоматически. Ну, прощай! В добрый путь! Пока! Успехов!

Нет, отвечать на другие вопросы я не могу. У меня мало времени. Нужно успеть подготовить других гонщиков, а до началагонки осталось меньше секунды.

Ответы на вопросы

Скорее всего ты запутался, куда попал. Это не беда. Сейчас ты получишь ответы на все вопросы. Дело в том, что ты находишься внутри компьютерной игры. Прямо внутри микросхем компьютера, который исполняет программу. Программы пишут люди, а компьютеры их только исполняют.

Сами по себе компьютеры ленивы и глупы. Без программы, они вообще ничего не будут делать, сколько бы мы их не кормили электричеством. Но стоит дать какому-нибудь компьютеру программу, он тут же оживляется и начинает усердно исполнять все команды, которые есть в программе.

На нашем компьютере запущена игровая программа. Она не очень сложная. На экране появляется описание следующего участка гоночной трассы. Игрок должен решить, будет он газовать или, наоборот, сбавит скорость. Если делаешь правильный выбор, начинаешь опережать другие машины. Если ошибаешься, то они тебя обгоняют.

Прочитав эту книгу, ты узнаешь из каких частей состоит программа и сможешь сам начать программировать. А начинать нужно с самого интересного. С программирования гоночной машины!

Гоночная машина