Схема генерации
В данном разделе описан один из возможных подходов, использующих определённые ранее понятия. Тот генератор, который мы опишем, является итератором, то есть он строит деревья последовательно, по одному.
Как отмечалось раньше, для каждого типа вершин имеется свой генератор. Все эти генераторы появляются по требованию и зависят от уже построенной части дерева, то есть контекста.
Итак, опишем генератор вершин типа t. Контекст для строящейся вершины типа t - это внешний параметр генератора.
- Генератор создаёт вершину-заготовку, в которой поля не установлены.
- По контексту вершины генератор вычисляет граф зависимостей между полями вершины. Для этого он использует информацию из элементарных ограничений.
- Из графа зависимостей вычисляется порядок построения полей: f1 → f2 → … → fn.
- Далее строится комбинатор зависимых генераторов значений полей, у которого первая ось зависимости - генератор независимого поля f1, вторая ось зависимости - генератор поля f2, зависимого от поля f1, и т.д. При этом генераторы полей при переходе в новое состояние проставляют значение соответствующего поля вершины.
- Генератор значений конкретного поля fi создаётся так:
- Если поле - ребёнок c типа s, то генератор строит для него контекст, основываясь на контексте вершины-родителя и значений полей, от которых зависит поле fi. Для полученного контекста строится генератор вершин типа s, который используется в качестве генератора значений поля.
- Если поле - атрибут, то генератор значений для него строится так:
- Для всех элементарных ограничений, наложенных на данный атрибут, вычисляются множества допустимых значений M1, M2, …, Mk. Как было сказано ранее, они задаются итераторами.
- Строится итератор, перебирающий значения из объединения множеств M1, M2, …, Mk, которые удовлетворяют всем элементарным ограничениям, наложенным на данный атрибут. Этот итератор и будет генератором значений данного атрибута.
- Если поле - список, то для него строится комбинатор зависимых итераторов, у которого первая ось зависимости - итератор длины списка, вторая - итератор первого элемента списка, третья - итератор второго элемента списка, и т.д. Этот комбинатор используется в качестве генератора значений списка. Генераторы значений элементов списка строятся так же, как и генераторы значений полей.
Заметим, что при генерации должны своевременно обновляться все аспекты состояний вершин, которые могут использоваться в элементарных ограничениях для вычисления множества допустимых значений.
