Podstawy#

Przejścia#

DOM definiuje wiele sposobów pozwalających na dostęp do konkretnego węzła lub grupy węzłów w danym drzewie węzłów. Mogą to być chociażby metody ParentNode.getElementById(), Document.getElementsByTagName() czy Document.getElementsByClassName(). Wszystkie one zwracają jeden konkretny węzeł lub kolekcję węzłów spełniające wąskie kryteria.

Kolejnym sposobem o zdecydowanie większych możliwościach będzie wybieranie oparte na API selektorów, czyli np. metodzie ParentNode.querySelectorAll(). Dzięki niej w jednym poleceniu można uzyskać kolekcję spełniającą wiele różnych kryteriów.

Jeszcze jednym sposobem, który przychodzi mi do głowy, będzie po prostu przechodzenie w pętli po węzłach z wykorzystaniem pewnych ogólnych właściwości węzłów, np. Node.nextSibling. W tym przypadku można zastosować dowolny rodzaj filtracji:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<div id="box">
	<p>Pierwszy akapit.</p>
	<P>Drugi akapit.</p>
	<P>Trzeci akapit.</P>
</div>

<script>

	var el = document.getElementById("box").firstChild;

	document.write("Odczytane węzły w kontenerze DIV:" + "<br><br>");

	while (el){

		// Można wprowadzić szczegółowy rodzaj filtracji
		document.write(el.nodeName + "<br>");
		el = el.nextSibling;

	}

</script>

Ostatnie podejście daje największe możliwości dlatego w specyfikacji DOM Level 2 Traversal and Range (W3C) wprowadzono dwa gotowe mechanizmy, pozwalające przechodzi po drzewie węzłów z dowolnym filtrem i innymi usprawniającymi opcjami. Sposoby te zostały przeniesione do DOM4 z pewnymi modyfikacjami.

Mowa tutaj o dwóch bazowych interfejsach NodeIterator i TreeWalker oraz powiązanym interfejsie zwrotnym NodeFilter. Bazowe interfejsy implementowane są przez obiekt, który już na etapie tworzenia otrzymuje wszystkie najważniejsze dane inicjalizacyjne. Następnie za pomocą takiego obiektu możemy poruszać się między tymi węzłami, które będą spełniały określone kryteria. Tak naprawdę testowanie węzłów (zgodnie z kryteriami filtra) odbywa się dopiero w czasie kolejnego przejścia, dlatego takie rozwiązanie ma negatywny wpływ na wydajność.

Obiekty typu NodeIterator (tzw. iterator węzłowy) i TreeWalker (tzw. przemierzacz drzewa) są do siebie bardzo podobne. Tworzące je metody pobierają identyczne argumenty: korzeń, maskę bitów (opcjonalnie) oraz filtr (opcjonalnie). Jedyna różnica polega na późniejszym poruszaniu się po węzłach w korzeniu. NodeIterator tworzy płaską uporządkowaną listę węzłów, gdzie udostępnione jest jedynie poruszanie się w przód lub w tył. TreeWalker tworzy hierarchiczną strukturę (drzewo), gdzie możliwe są dodatkowe kierunki przejść, jak np. w górę i w dół.

Generalnie można założyć, że obiekt TreeWalker jest właściwszy do zadań, w których struktura dokumentu wokół wybranych węzłów będzie zmieniana, kiedy obiekt NodeIterator jest lepszy do zadań, które skupiają się na zawartości każdego wybranego węzła.

Prosty przykład:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<div id="box">
	<p>Pierwszy akapit.</p>
	<P>Drugi akapit.</p>
	<P>Trzeci akapit.</P>
</div>

<script>

	function filter(node){

		// Można wprowadzić szczegółowy rodzaj filtracji
		return NodeFilter.FILTER_ACCEPT;

	}

	var root = document.getElementById("box");
	var iterator = document.createNodeIterator(root, NodeFilter.SHOW_ALL, filter);

	var node = iterator.nextNode(); // pierwszy element w obiekcie 'iterator'

	document.write("Odczytane węzły w kontenerze DIV za pomocą NodeIterator:" + "<br><br>");

	while (node){

		document.write(node.nodeName + "<br>");
		node = iterator.nextNode();

	}

</script>

Widać wyraźnie, że w tym przykładzie zwróconych została większa liczba węzłów, niż miało to miejsce w przykładzie pierwszym. Dzieje się tak dlatego, że iteracja przebiega przez wszystkich węzłowych potomków w <div id="box">, w dodatku jako pierwszy zwrócony został także sam korzeń <div id="box">. Jest to wygodne, gdyż w przypadku zagnieżdżeń nie trzeba samemu obmyślać iteracji lub rekurencji, które byłyby konieczne w poprzednim przykładzie do osiągnięcia identycznego efektu.

Szczegóły#

Stosowanie obiektów NodeIterator i TreeWalker (w połączeniu z filtrem węzłowym) na pierwszy rzut oka może wyglądać skomplikowanie, szczególnie dla osób zaczynających przygodę z DOM. Umieszczę w tym miejscu kilka podstawowych informacji, głównie pochodzących z poprzedniej specyfikacji DOM Level 2 Traversal and Range (W3C), które nie znalazły swojego miejsca w najnowszym DOM4, a które (przynajmniej w założeniu) powinny nieco rozjaśnić sprawę. Dzięki temu późniejsze opisy właściwych poleceń nie muszą być aż tak rozbudowane.

NodeIterator#

Iterator węzłowy to obiekt, który zapamiętuje ostatni stan iteracji między węzłami w danym korzeniu. Wartości tego stanu udostępniane są pod konkretnymi właściwościami iteratora. Iteracja odbywa się na zasadzie przejścia jedynie w przód lub w tył przy wykorzystaniu dedykowanych metod.

Zacznijmy od początku, czyli od utworzenia iteratora metodą Document.createNodeIterator(). Obiekt ten zawsze zostaje powiązany z pewnym węzłem (korzeniem). To właśnie na korzeniu oraz wszystkich jego potomkach będzie odbywało się przemieszczanie iteratora i wybieranie kolejnego węzła (który spełnia warunki filtracji).

Całość można zaprezentować na zasadzie płaskiego wykazu, gdzie duże litery wskazują na węzły spełniające kryteria filtracji, natomiast litery małe stanowią węzły pomijane:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
A B C d E F h H I

Nasz iterator węzłowy może zatem operować na następujących węzłach:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
A B C E F H I

Czyli w rzeczywistości dostępna jest jedynie pewna część faktycznego drzewa węzłów. W poprzedniej specyfikacji nasz pierwszy wykaz określano mianem widoku fizycznego # (physical view) a drugi wykaz stanowił widok logiczny # (logical view). Są to umowne pojęcia, tak samo jak nasze prezentacje płaskich wykazów, iterator operuje bezpośrednio na żywym drzewie węzłów, co może powodować pewne dziwne zachowania, ale omówimy to nieco później.

Iterator może znajdować się między dwoma węzłami, przed pierwszym węzłem lub za ostatnim węzłem. W czasie tworzenia iteratora jego pozycja ustawiana jest przed pierwszym węzłem. Załóżmy, że utworzyliśmy nowego iteratora, w którym brane pod uwagę będą następujące węzły:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
* [A] B C D E F G H I

Powyższa lista przedstawia nam taką sytuacje, gdzie startowa pozycja iteratora oznaczona została symbolem gwiazdki *. Węzeł referencyjny znajduje się w nawiasach klamrowych [], zatem właściwość referenceNode wskazuje na węzeł "A" (co na początku jest tożsame z korzeniem, czyli z właściwością root). Wartość właściwości pointerBeforeReferenceNode ustawiona zostaje na true, a to dlatego, że iterator znajduje się przed węzłem referencyjnym.

Pierwsze wywołanie nextNode() zmieni nam pozycję iteratora, właściwość pointerBeforeReferenceNode ustawiona zostaje na false, ale właściwość referenceNode dalej wskazuje na węzeł "A" (korzeń):

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
[A] * B C D E F G H I

Dopiero kolejne wywołania nextNode() zmienią nam węzeł referencyjny, chociaż właściwość pointerBeforeReferenceNode dalej będzie miała wartość false, co jest słuszne, gdyż iterator znajduje się za węzłem referencyjnym. Przykład dla potrójnego przejścia w przód:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * E F G H I

Sytuacja robi się ciekawa kiedy jednokrotnie wywołamy previousNode():

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C * [D] E F G H I

Teraz wskaźnik znowu znajduje się przed węzłem referencyjnym dlatego pointerBeforeReferenceNode ma wartość true, ale sam węzeł referencyjny nie uległ zmianie. Dopiero kolejne wywołanie previousNode() wybiera poprzedzający węzeł. Przykład dla potrójnego przejścia w tył:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
* [A] B C D E F G H I

#W ostatnim przykładzie ponowne wywołanie metody previousNode() zwróci wartość null (brak poprzedzającego węzła), aczkolwiek właściwość referenceNode będzie dalej wskazywać na węzeł "A". Ta sama sytuacja wystąpi w chwili, kiedy iterator będzie znajdował się za ostatnim węzłem na liście i wywołamy metodę nextNode(). To są jedyne przypadki, gdzie wynik zwracany przez metodę previousNode() lub nextNode() nie pokrywa się z zapamiętanym węzłem referencyjnym.

Łatwo zauważyć, że zmiana stanu właściwości pointerBeforeReferenceNode z true na false (i na odwrót) zmienia pozycję iteratora, ale nie zmienia węzła referencyjnego. To właśnie od stanu tej właściwości zależy, czy przy wywołaniu metod nextNode() lub previousNode() wybierany jest kolejny węzeł, czy może testowany jest aktualny węzeł referencyjny. Takie zachowanie można łatwo przeoczyć w pętli, gdzie przejścia odbywają się automatycznie i dodatkowy krok na zmianę stanu wskaźnika (przy naprzemiennym wywoływaniu nextNode() i previousNode()) może umknąć naszej uwadze.

Właściwości pointerBeforeReferenceNode i referenceNode pierwotnie wprowadzono w silniku WebKiit, miały ułatwić testowanie i debugowanie kodu. Okazały się na tyle przydatne, że umieszczono je w specyfikacji DOM4. Nawet z punktu widzenia webmastera pozwalają na łatwiejsze zrozumienie tematu.

Zmiany w drzewie węzłów#

Nasze płaskie listy z przykładów to teoretyczne zobrazowanie zasady działania iteratora, ale jak wspomniałem wcześniej, iterator tak naprawdę pracuje na bieżącym drzewie węzłów. Obiekt iteracji ma ukryte powiązanie z kolekcją iteratora (zwanej też listą iteracyjną), która zawiera wszystkie węzły należące do korzenia iteratora. Jak dobrze wiemy, kolekcje z reguły są aktualne, czyli każda zmiana węzłów w drzewie węzłów będzie miała wpływ na stan tej kolekcji, co automatycznie może wpłynąć na parametry iteratora.

Zmiany obejmują głównie usuwanie lub dodawanie nowych węzłów do korzenia. Zmiany te nie unieważniają iteratora, w rzeczywistości iterator nigdy nie zostaje unieważniony. Aby było to możliwe iterator używa węzła odniesienia (węzła referencyjnego), aby utrzymać swoją pozycję. Stan iteracji zależy również od tego, czy iterator jest umieszczony przed lub po węźle referencyjnym. Omówiłem to szczegółowo wcześniej.

Jeśli zmiany na iterowanej liście nie usuwają węzła referencyjnego, to w żaden sposób nie wpływa to na stan iteratora. Przykładowo, stan iteratora nie ulega zmianie poprzez dodawanie nowych węzłów w pobliżu iteratora lub poprzez usuwanie węzłów innych niż węzeł referencyjny. Załóżmy, że zaczynamy od następującej pozycji:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * E F G H I

Usuwając węzeł "E" otrzymamy:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * F G H I

Jeśli nowy węzeł "X" zostanie dodany, to iterator wciąż pozostaje blisko węzła referencyjnego, więc jeśli nowy węzeł jest umieszczony pomiędzy węzły "D" i "F", to faktycznie pojawi się między iteratorem a węzłem "F":

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * X F G H I

Przenoszenie węzła jest równoważne z jego usunięciem a następnie wstawieniem. Przenosząc węzeł "I" przed węzeł "X" w rezultacie otrzymamy:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * I X F G H

Inaczej wygląda sytuacja w przypadku usuwania węzła referencyjnego. Jeśli węzeł referencyjny zostanie usunięty z listy iteracyjnej, to automatycznie wybrany zostanie inny węzeł referencyjny, ale zachowanie to będzie zależne od kilku czynników.

Jeśli węzeł referencyjny jest przed iteratorem, co zazwyczaj ma miejsce po wywołaniu metody nextNode(), to najbliższy węzeł przed iteratorem staje się nowym węzłem referencyjnym. Załóżmy, że usuwamy węzeł "D" w następującym przypadku:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * F G H I

Nowym węzłem referencyjnym zostaje węzeł "C", który jest najbliższym węzłem znajdującym się przed iteratorem.

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B [C] * F G H I

Jeśli węzeł referencyjny jest za iteratorem, co zazwyczaj ma miejsce po wywołaniu metody previousNode(), to najbliższy węzeł za iteratorem staje się nowym węzłem referencyjnym. Załóżmy, że usuwamy węzeł "E" w następującym przypadku:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C D * [E] F G H I

Nowym węzłem referencyjnym zostaje węzeł "F", który jest najbliższym węzłem znajdującym się za iteratorem.

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C D * [F] G H I

Jak wspomniano wyżej, przenoszenie węzła jest równoważne z jego usunięciem a następnie wstawieniem. Załóżmy, że przenosimy węzeł "D" na koniec listy w następującym przypadku:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * F G H I C

W konsekwencji otrzymamy wynik:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B [C] * F G H I D

Jest jeszcze jeden szczególny przypadek, kiedy węzeł referencyjny jest ostatnim węzłem na liście i zostaje usunięty. Załóżmy, że usuwamy węzeł "C" w następującym przypadku:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B * [C]

Zgodnie z opisanymi do tej pory regułami, nowym węzłem referencyjnym powinien zostać najbliższy węzeł za iteratorem, ale w tym wypadku taki węzeł nie istnieje. Ta sama sytuacja powstaje, gdy za pomocą metody previousNode() wrócimy do pierwszego węzła na liście, którego następnie usuniemy. Stąd: Jeśli nie ma węzła w pierwotnym kierunku węzła odniesienia, to najbliższy węzeł w przeciwnym kierunku zostaje wybrany jako węzeł referencyjny:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A [B] *

Jeśli iterator zostanie umieszczony wewnątrz bloku węzłów, które są usuwane, to powyższe zasady wyraźnie wskazują, co zostanie zrobione. Załóżmy, że węzeł "C" jest nadrzędny względem węzłów "D", "E" i "F", i usuwamy węzeł "C" w następującym przypadku:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B C [D] * E F G H I D

W konsekwencji otrzymamy wynik:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A [B] * G H I D

#Ostatnim wariantem będzie sytuacja, w której próbujemy usunąć korzeń iteratora z jego rodzica. Taka sytuacja w żaden sposób nie zmienia kolekcji iteratora (korzeń z całą zawartością wędruje w nowe miejsce), dlatego też nie ma wpływu na stan iteratora.

Wszystkie przypadki usuwania węzłów zawartych w kolekcji iteratora wyrażają kroki przed-usuwania, chociaż teoretyczne opisy niektórych z nich mogą ułatwić zrozumienie całości.

Widoczność węzłów#

Podstawowa struktura, która jest iterowana, może zawierać węzły, które nie są częścią widoku logicznego, a zatem nie będą one zwracane przez iterator węzłowy. Dla węzłów, które mają być wykluczone z powodu maski bitowej, metoda nextNode() zwróci następny widoczny węzeł, pomijając wykluczone "niewidzialne" węzły. Jeśli filtr NodeFilter jest obecny, to jest aplikowany przed zwróceniem węzła; jeśli filtr nie akceptuje węzła, to proces jest powtarzany do chwili, aż jakiś węzeł zostanie zaakceptowany przez filtr, a następnie zwrócony. Jeśli nie ma żadnych widocznych węzłów, to zwrócona zostanie wartość null, a iterator jest pozycjonowany na końcu listy. W tym przypadku węzeł referencyjny jest ostatnim węzłem w liście, niezależnie od stanu jego widoczności. Ta sama zasada dotyczy przeciwnego kierunku dla metody previousNode().

W poniższym przykładzie małe litery reprezentują węzły w strukturze danych, które nie są częścią widoku logicznego:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A [B] * c d E F G

Wywołanie metody nextNode() zwróci węzeł "E" i zmieni pozycję iteratora w następujący sposób:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B c d [E] * F G

Węzły, które nie są widoczne mogą być stosowane jako węzły referencyjne, nawet jeśli węzeł referencyjny zostanie usunięty. Załóżmy, że w powyższym przypadku usuniemy węzeł "E", w rezultacie otrzymamy wynik:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B c [d] * F G

Załóżmy teraz, że nowy węzeł "X" zostanie wstawiony przed węzeł "d", co w konsekwencji zwróci nam:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A B c X [d] * F G

Należy mieć na uwadze, że wywołanie metody previousNode() zwróci teraz węzeł "X". Ważnym jest, aby nie pomijać niewidocznych węzłów, kiedy węzeł referencyjny zostaje usunięty, ponieważ jeśli się tak stanie, jak w powyższym przypadku, to zwrócony zostałby niewłaściwy wynik. Kiedy usunęlibyśmy węzeł "E", a referencyjnym węzłem zostałby węzeł "B" zamiast węzła d, to wywołanie metody previousNode() nie zwróciłoby wstawionego węzła "X":

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<pun></pun>A [B] * c X d F G

Warto nadmienić, że w samym algorytmie usuwania węzła z kolekcji iteratora nie ma mowy o podziale na węzły widoczne i węzły niewidoczne przy zmianie węzła referencyjnego, co oznacza, że każdy rodzaj węzła jest brany pod uwagę i jest to zgodne z prezentowanymi tutaj przykładami.

TreeWalker#

Interfejs TreeWalker udostępnia wiele tych samych funkcjonalności, co interfejs NodeIterator. Podstawowa różnica między tymi interfejsami jest taka, że obiekt TreeWalker przedstawia widok poddrzewa węzłów bazujący na strukturze drzewiastej, w przeciwieństwie do widoku bazującego na płaskiej liście iteratora. Innymi słowy, iterator pozwala poruszać się do przodu i do tyłu, ale TreeWalker pozwala także przejść do rodzica węzła, do jednego z jego dzieci lub rodzeństwa.

Stosowanie TreeWalker jest bardzo podobne do bezpośredniego poruszania się po węzłach (implementujących ogólny interfejs Node), a sposoby nawigacyjne dla tych dwóch interfejsów są analogiczne. Zaletą TreeWalker będzie to, że użytkownik może w łatwy sposób wybrać odpowiedni widok drzewa. Można przykładowo wykorzystać maskę bitów do pokazania lub ukrycia komentarzy lub instrukcji przetwarzania, nie zapominając jednocześnie o możliwości stosowania dodatkowej funkcji filtrującej.

Przeanalizujmy przykładowe widoki dwóch drzew węzłów:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
root                                   root
      _ _ _ _ _|  | _ _ _ _ _              _ _ _ _ _ _|  |_ _ _ _ _ _
     |      |         |      |            |   |   |   |  |   |   |   |
     A      A         A      A            B   B   B   B  B   B   B   B
    _|_    _|_       _|_     _|_
   |   |  |   |     |   |   |   |
   B   B  B   B     B   B   B   B

Pierwszy diagram jest fizycznym widokiem drzewa, gdzie brane pod uwagę są wszystkie węzły. Drugi widok jest naszym obiektem typu TreeWalker, z filtracją pomijającą węzły "A". W pierwszym przykładzie odczyt ogólnej właściwości Node.firstChild dla węzła "root" zwróci pierwszy węzeł "A", natomiast w drugim przykładzie wywołanie metody firstChild() przeniesie nas z korzenia "root" na pierwszy węzeł "B". W zależności od sposobu filtracji możemy dowolnie modyfikować oryginalną strukturę danych tworząc nowy widok logiczny (w kontekście przemieszczania z jednego węzła na inny).

Zmiany w drzewie węzłów#

Podobnie jak obiekt NodeIterator, taki i TreeWalker może być aktywny w chwili, kiedy struktura danych jest modyfikowana, i musi zachować się odpowiednio w obliczu tych zmian. Dodawanie i usuwanie w podstawowej strukturze danych nie unieważnia TreeWalker, w rzeczywistości obiekt ten nigdy nie zostaje unieważniony.

Z drugiej jednak strony odpowiedź TreeWalker na te zmiany jest zupełnie inna niż w przypadku NodeIterator. Iterator reaguje na zmiany poprzez utrzymanie swojej pozycji na iterowanej liście, natomiast TreeWalker zostaje przywiązany do swojego bieżącego węzła, wskazywanego przez właściwość currentNode. Wszystkie metody nawigacyjne TreeWalker operują na pojęciu "kontekst bieżącego węzła" w chwili, kiedy zostają wywołane, niezależnie od tego, co się stało dookoła tego węzła, który został ostatnio udostępniony przez TreeWalker. Jest to prawdziwe nawet wtedy, kiedy bieżący węzeł jest przenoszony poza swoje oryginalne poddrzewo.

Dla przykładu rozważmy poniższy fragment dokumentu:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
...
<subtree>
	<twRoot>
		<currentNode/>
		<anotherNode/>
	</twRoot>
</subtree>
...

Załóżmy, że metodą Document.createTreeWalker() stworzyliśmy nowy obiekt typu TreeWalker, z korzeniem ustawionym na elemencie <twRoot/> i bieżącym węzłem w postaci elementu <currentNode/>. Niech maska bitowa i filtr akceptuje wszystkie rodzaje węzłów.

Jeśli użyjemy metody Node.removeChild() do usunięcia elementu <currentNode/> z jego rodzica, to element dalej pozostaje bieżącym węzłem dla TreeWalker, nawet jeśli nie należy on już do poddrzewa węzłów w korzeniu. Możemy nadal korzystać z TreeWalker do poruszania się przez każde dziecko, które może posiadać osierocony bieżący węzeł, ale przejście na zewnątrz bieżącego węzła nie jest możliwe ponieważ rodzic nie jest dostępny.

Jeśli użyjemy metody insertBefore() lub appendChild(), aby <currentNode/> nadać nowego rodzica, to nawigacja TreeWalker będzie operować na nowej lokalizacji bieżącego węzła. Dla przykładu, kiedy wstawimy <currentNode/> bezpośrednio za element <anotherNode/>, to metoda previousSibling() z TreeWalker przeniesie nas z powrotem do <anotherNode/>, a kiedy wywołamy parentNode() przejdziemy do <twRoot/>.

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
...
<subtree>
	<twRoot>
		<anotherNode/>
		<currentNode/>
	</twRoot>
</subtree>
...

W kolejnym przykładzie wstawiamy bieżący węzeł do elementu <subtree/>:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
...
<subtree>
	<currentNode/>
	<twRoot>
		<anotherNode/>
	</twRoot>
</subtree>
...

Łatwo zauważyć, że przenieśliśmy bieżący węzeł poza korzeń w TreeWalker. To nie unieważnia naszego TreeWalker, może on być dalej używany do nawigacji względem bieżącego węzła. Wywołanie metody parentNode() przeniesie nas do elementu <subtree/>, mimo że znajduje się on poza oryginalnym korzeniem. Jednakże, jeśli nawigacja TreeWalker spowoduje powrotne przejście do oryginalnego korzenia poddrzewa, dla przykładu wywołując metodę nextNode() zamiast parentNode(), przesuwając tym samym TreeWalker na element <twRoot/>, korzeń zostanie "odzyskany" przez TreeWalker, i uniemożliwi przechodzenie na zewnątrz.

Sytuacja staje się bardziej skomplikowana, kiedy stosowane są filtry. Przeniesienie bieżącego węzła lub doraźna jego zmiana, a także zmiana warunków filtru, na których opiera się filtracja, może w rezultacie doprowadzić do posiadania przez TreeWalker bieżącego węzła, który w innym przypadku byłby niewidoczny w przefiltrowanym (logicznym) widoku dokumentu. Węzeł ten może być traktowany jako "przejściowy członek" tego widoku. Kiedy przejdziemy do takiego węzła to zostanie on potraktowany jakby był widoczny, ale powrotne przejście do niego może nie być możliwe, jeśli warunki filtracji nie ulegną zmianie i nie uczynią go widocznym ponownie.

Wszystkie te zawiłości opisują poszczególne algorytmy przeznaczone dla interfejsu TreeWalker, dlatego w razie konieczności warto do nich zajrzeć.

Filtracja (maska bitowa i NodeFilter)#

Obydwie metody tworzące obiekty typu NodeIterator oraz TreeWalker, tj. Document.createNodeIterator() i Document.createTreeWalker(), jako drugi argument przyjmują maskę bitową (oznaczaną parametrem whatToShow). Maska bitowa jest tak naprawdę wstępną filtracją węzłów, w której pod uwagę brany jest jedynie typ danego węzła. Bardziej szczegółowa filtracja odbywać się będzie za pomocą odpowiedniej metody filtracyjnej przekazywanej do metod tworzących jako trzeci argument.

Z maski bitowej korzystamy na podobnej zasadzie jak w przypadku omawiania porównywania położenia węzłów między sobą. Każdy bit w masce bitowej oznacza akceptację węzła danego typu.

Przykładowo, w celu uwzględnienia węzłów dowolnego rodzaju wystarczy przekazać do metody dziesiętną wartość 4294967295 lub postać szesnastkową 0xFFFFFFFF:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<script>

	var iterator1 = document.createNodeIterator(document, 4294967295, function(node){

	});

	var iterator2 = document.createNodeIterator(document, 0xFFFFFFFF, function(node){

	});

	document.write(iterator1.whatToShow); // 4294967295
	document.write("<br>");
	document.write(iterator2.whatToShow); // 4294967295

</script>

Jeśli będziemy chcieli brać pod uwagę jedynie węzły typu Element i Comment należy przekazać do metody wartość dziesiętną 129 (128 + 1) lub postać szesnastkową 0x81.

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<script>

	var iterator1 = document.createNodeIterator(document, 129, function(node){

	});

	var iterator2 = document.createNodeIterator(document, 0x81, function(node){

	});

	document.write(iterator1.whatToShow); // 129
	document.write("<br>");
	document.write(iterator2.whatToShow); // 129

</script>

Tworzenie maski bitów jest proste i będzie zależne jedynie od preferencji danego programisty (sposobu przechodzenia z jednego systemu liczbowego na inny). Można po prostu dodać do siebie dziesiętne wartości z tabelki (stałe dla maski bitowej) i w takiej postaci przekazać do metody, można też zamienić wynik na wartość HEX. Innym często stosowanym rozwiązaniem jest wykonanie binarnego dodawania na liczbach za pomocą javascriptowego operatora |:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<script>

	var iterator1 = document.createNodeIterator(document, 128 + 1, function(node){

	});

	var iterator2 = document.createNodeIterator(document, 0x80 | 0x1, function(node){

	});

	document.write(iterator1.whatToShow); // 129
	document.write("<br>");
	document.write(iterator2.whatToShow); // 129

</script>

#Ostatnie prezentowane już rozwiązanie jest najwygodniejsze gdyż pozwala operować bezpośrednio na stałych z interfejsu NodeFilter. Takie podejście może zapewnić większą przenośność kodu ponieważ operujemy na identycznych nazwach stałych, chociaż wartości kryjące się pod każdą z nich mogą być różne w poszczególnych programach. Przykładowo, dawniej w przeglądarce Chrome stała NodeFilter.SHOW_ALL miała wartość dziesiętną -1 (postać szesnastkowa to 0xFFFFFFFFFFFFFFFF):

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<script>

	var iterator1 = document.createNodeIterator(document, NodeFilter.SHOW_ELEMENT | NodeFilter.SHOW_COMMENT, function(node){

	});

	var iterator2 = document.createNodeIterator(document, NodeFilter.SHOW_ALL, function(node){

	});

	document.write(iterator1.whatToShow); // 129
	document.write("<br>");
	document.write(iterator2.whatToShow); // 4294967295 (nawet w starym Chrome), w IE11 -1

	document.write("<br><br>");

	document.write(NodeFilter.SHOW_ALL); // 4294967295 (w starym Chrome -1)
	document.write("<br>");
	document.write(NodeFilter.SHOW_ALL == iterator2.whatToShow); // true (w starym Chrome i IE11 false)

	document.write("<br><br><br>" + "WYKAZ WSZYSTKICH STAŁYCH I ICH WARTOŚCI:" + "<br>");

	var allConst = [
		"SHOW_ALL", "SHOW_ELEMENT", "SHOW_ATTRIBUTE", "SHOW_TEXT", "SHOW_CDATA_SECTION",
		"SHOW_ENTITY_REFERENCE", "SHOW_ENTITY", "SHOW_PROCESSING_INSTRUCTION", "SHOW_COMMENT", "SHOW_DOCUMENT",
		"SHOW_DOCUMENT_TYPE", "SHOW_DOCUMENT_FRAGMENT", "SHOW_NOTATION",
		"FILTER_ACCEPT", "FILTER_REJECT", "FILTER_SKIP"
	];

	for (var i = 0; i < allConst.length; i++){
		document.write("<br>" + allConst[i] + ": " + NodeFilter[allConst[i]]);
	}

</script>

Akurat w tym prostym przykładzie różnica między programami nie stwarzała żadnego problemu, Chrome jedynie obcinał wartość przekazaną do metody z 0xFFFFFFFFFFFFFFFF na 0xFFFFFFFF (bity dla wszystkich rodzajów węzłów dalej miały wartość 1). W przypadku IE do dnia dzisiejszego występują bardzo podobne zachowania. Trzeba sobie po prostu zdawać sprawę, że takich drobnych niuansów (różnic) w całym DOM między przeglądarkami może być więcej.

Rekursywne wywołania#

Obiekty NodeIterator i TreeWalker można wywoływać rekursywnie z poziomu funkcji filtrującej. Będzie to miało miejsce wtedy, kiedy w filtrze umieścimy kolejną metodę zmieniającą stan wspomnianych obiektów. Pierwotnie zachowanie to było blokowane za pomocą specjalnej flagi aktywności występującej w algorytmie przefiltrowania. Tak właśnie zachowują się przeglądarki Firefox i Opera (Presto), gdzie próba rekursywnego wywołania przejść zrzuca wyjątek "InvalidStateError".

Inne przeglądarki, takie jak Chrome lub IE, nie są aż tak restrykcyjne i pozwalają na pewną liczbę rekurencji, ale po przekroczeniu limitu zrzucany będzie javascriptowy błąd (RangeError lub Error):

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<script>

	var i = 0;

	var iterator = document.createNodeIterator(document, NodeFilter.SHOW_ALL, function(){

		i++;
		iterator.nextNode();
		iterator.previousNode();
		return NodeFilter.FILTER_ACCEPT;

	}, false);

	try{
		iterator.nextNode();
	}
	catch(e){

		document.write("Ilość rekurencji: " + i); // Chrome 20, IE ok. 1234
		document.write("<br>");
		document.write(e); // opis zależny od przeglądarki
		document.write("<br>");
		document.write(e.constructor); // Chrome: function RangeError() { [native code] }, IE: function Error() { [native code] }

	}

</script>

Rekurencja nie jest niczym szczególnym, istnieje wiele miejsc gdzie jest dozwolona, a ewentualne problemy z długotrwałym zawieszeniem środowiska rozwiązują limity narzucane przez przeglądarki. W związku z tym jedna z poprawek DOM4 znosi blokadę rekurencji dla przejść usuwając z algorytmów flagę aktywności. Problem w tym, że samo zezwolenie na rekursywne wywołania w przejściach nie oznacza wcale, że w efekcie uzyskamy identyczny rezultat w przeglądarkach, które na to zezwalały do tej pory:

  1. —
  2. L
  3. K
  4. T'
  5. T
  6. A
  7. O
  8. Z'
  9. Z
  10. #
<div id="box">
	<p>Pierwszy akapit.</p>
	<P>Drugi akapit.</p>
	<P>Trzeci akapit.</P>
	<hr>
</div>

<script>

	var root = document.getElementById("box");
	var i = 0; //  licznik wywołania filtra
	var iterator = document.createNodeIterator(root, NodeFilter.SHOW_ELEMENT, function(){

		i++;

		if (i < 4){

			(function(i){

				var node = iterator.nextNode();
				document.write(i + " rekurencja");
				document.write("<br>");
				document.write("iterator.nextNode(): " + node);
				document.write("<br>");
				document.write("iterator.nextNode().textContent: " + node.textContent);
				document.write("<br><br>");

			})(i);

		}

		return NodeFilter.FILTER_ACCEPT;

	}, false);

	document.write("Licznik wywołania filtra przed init: " + i);
	document.write("<br><br>");
	document.write("init: " + iterator.nextNode());
	document.write("<br><br>");
	document.write("Licznik wywołania filtra za init: " + i);

</script>

Wydaje się, że w tej chwili Chrome działa właściwie, aczkolwiek przetestowałem tylko jedną metodę NodeIterator.nextNode(). Nie jestem przekonany co do słuszności tej poprawki, prawidłowa implementacja w przeglądarkach i skrupulatne przetestowanie wszystkiego może zająć więcej czasu niż całkowita blokada rekurencji w funkcji filtrującej. Z uwagi na wymienione niespójności wstrzymuję się z naniesieniem drobnych korekt w moim kursie do chwili, kiedy sytuacja ulegnie większej krystalizacji (DOM - Bug 25412).

Wydajność NodeIterator i TreeWalker#

Według różnych wpisów i testów interfejsy te są wolne (w porównaniu z innym metodami selekcji węzłów) i powinny być stosowane w ostateczności. Powód jest oczywisty, w chwili poruszania się po drzewie węzłów brane pod uwagę są wszystkie węzły, na których dopiero uruchamiane są testy. Stosowanie funkcji filtrującej jeszcze bardziej obniża efektywność, gdyż będzie ona wywoływana całkowicie po stronie JS. Filtracja za pomocą wbudowanych metod zaimplementowanych w C++, takich jak Document.getElementsByTagName() czy ParentNode.querySelectorAll(), jest zdecydowanie wydajniejsza.

Trzeba sobie zdawać sprawę z tego, że obydwa rozwiązania są niezwykle rzadko stosowane. W związku z niewielką popularnością można przypuszczać, że ich implementacje nie zostały dostatecznie zoptymalizowane.

Pasek społecznościowy

SPIS TREŚCI AKTUALNEJ STRONY

Podstawy (H1) Przejścia (H2) Szczegóły (H3) NodeIterator (H4) Zmiany w drzewie węzłów (H5) Widoczność węzłów (H5) TreeWalker (H4) Zmiany w drzewie węzłów (H5) Filtracja (maska bitowa i NodeFilter) (H4) Rekursywne wywołania (H3) Wydajność NodeIterator i TreeWalker (H3)