Пусть входящий документ представляет собой список объектов (элементов
item
), каждый из которых имеет имя (атрибут
name
) и источник (атрибут
source
). Требуется сгруппировать объекты по своим источникам и получить документ приблизительно следующего вида.
Листинг 8.20. Требуемый результат
<sources>
<source name="a">
<item source="a" name="A"/>
<item source="a" name="C"/>
<item source="a" name="H"/>
</source>
<source name="b">
<item source="b" name="B"/>
<item source="b" name="E"/>
<item source="b" name="F"/>
</source>
<source name="c">
<item source="c" name="D"/>
<item source="c" name="G"/>
</source>
</sources>
Первым
шагом на пути решения этой задачи является формулировка в терминах XSLT предложения "сгруппировать объекты по своим источникам". Источник каждого объекта определяется его атрибутом
source
, значит множество объектов, принадлежащих одному источнику
"а"
, будет определяться путем выборки
/items/item[@source='a']
Тогда для каждого элемента
item
в его группу войдут элементы, которые будут выбраны выражением
/items/item[@source=current/@source]
Попробуем использовать этот факт в следующем шаблоне:
Как и ожидалось, при применении этого правила к элементам
item
для каждого из них будет создана группа, принадлежащая тому же источнику, — уже хороший результат, но в условии требуется создать по группе не для каждого объекта, а для каждого источника. Чтобы достичь этого, можно создавать группу только для первого объекта, принадлежащего ей. Провести такую проверку опять же несложно: объект будет первым в группе тогда и только тогда, когда ему не предшествуют другие, элементы
item
, принадлежащие тому же источнику. Иначе говоря, создаем группы только для тех элементов, для которых выражение
preceding-sibling::item[@source-current/@source]
будет возвращать пустое множество.
С небольшими добавлениями искомое преобразование целиком будет иметь вид.
решение было несложным, но довольно громоздким. Самым же узким местом в этом преобразовании является обращение к элементам
item
источника текущего элемента посредством сравнения атрибутов
source
.
Проблема совершенно стандартна для многих преобразований: нужно выбирать узлы по определенным признакам, причем делать это нужно как можно более эффективно. Хорошо, что в нашем документе было всего восемь элементов
item
, но представьте себе ситуацию, когда элементов действительно много.
Проблема, которую мы подняли, достаточно серьезна. Она состоит в оптимизации поиска узлов с определенными свойствами в древовидно организованной структуре.
Попробуем разобраться в смысле фразы "узел обладает определенными свойствами". Очевидно, это означает, что для этого узла выполняется некое логическое условие, иначе говоря, некий предикат обращается в "истину".
Однако какого именно типа условия мы чаще всего проверяем? Анализируя различные классы задач, можно придти к выводу, что в большинстве случаев предикаты являются равенствами — выражениями, которые обращаются в "истину" тогда и только тогда, когда некоторый параметр узла, не зависящий от текущего контекста, равен определенному значению. В нашем примере смысл предиката на самом деле состоит не в том, чтобы проверить на истинность выражение
@source=current/@source
, а в том, чтобы проверить на равенство
@source
и
current/@source
.
Если переформулировать это для общего случая, то нам нужно выбрать не те узлы, для которых истинно выражение
A=B
, скорее нужно выбрать те, для которых значение
A
равно значению
B
. Иначе говоря, узел будет идентифицироваться значением в своего свойства
A
. И если мы заранее вычислим значения свойств
A
, проблема поиска узлов в дереве сведется к классической проблеме поиска элементов множества (в нашем случае — узлов дерева) по определенным значениям ключей (в нашем случае — значениями свойств