Ogólne#

Traversal#

W tym miejscu umieszczam powtarzające się specyficzne pojęcia i algorytmy w dziale TRAVERSAL, czyli mogą mieć one zastosowanie dla wszystkich interfejsów z tego działu.

Pojęcia#

Obiekty typu NodeIterator oraz TreeWalker mogą zostać użyte do filtracji oraz przechodzenia po węzłach w drzewie węzłów.

active flag

Każdy obiekt typu NodeIterator oraz TreeWalker ma przypisaną flagę aktywności # (active flag) zapobiegającą rekursywnym wywołaniom. Jest ona domyślnie nieaktywna (kwestia nierozstrzygnięta).

root

whatToShow

filter

Każdy obiekt typu NodeIterator oraz TreeWalker jest także skojarzony z węzłem będącym korzeniem # (root), maską bitów # (whatToShow) oraz zwrotnym filtrem # (filter).

iterator collection

Każdy obiekt typu NodeIterator jest skojarzony z kolekcją iteratora # (iterator collection), która jest kolekcją zakorzenioną na korzeniu z filtrem pasującym do każdego węzła.

Algorytmy#

pre-removing steps

Kroki przed-usuwania # (pre-removing steps) węzła toBeRemovedNode z iteratora węzłowego nodeIterator są następujące:

Kroki te będą używane przez ogólny algorytm usuwania węzła, który musi sprawdzić, czy usuwany węzeł może mieć wpływ na stan wszystkich iteratorów węzłowych (opis teoretyczny).

  1. Jeśli toBeRemovedNode nie jest przodkiem obejmującym dla wartości atrybutu referenceNode w nodeIterator, to pomiń kolejne kroki.

  2. Jeśli wartością atrybutu pointerBeforeReferenceNode w nodeIterator jest boolowskie true to uruchom poniższe podkroki:

    1. Niech next będzie pierwszym węzłem następującym dla toBeRemovedNode, który jest potomkiem obejmującym dla korzenia w nodeIterator i nie jest potomkiem obejmującym dla toBeRemovedNode, lub wartością null jeśli nie będzie takiego węzła.
    2. Jeśli next nie jest wartością null, to ustaw atrybut referenceNode w nodeIterator na next i pomiń kolejne kroki.

    3. W przeciwnym razie ustaw wartość atrybut pointerBeforeReferenceNode w nodeIterator na boolowske false.

      W tym momencie kolejne kroki nie zostają przerwane.

  3. Ustaw atrybut referenceNode w nodeIterator na potomka obejmującego dla ostatniego (zgodnie z porządkiem drzewa) brata poprzedzającego względem toBeRemovedNode, jeśli brat poprzedzający dla toBeRemovedNode nie jest wartością null, w przeciwnym razie na rodzica w toBeRemovedNode.

filter

Aby przefiltrować # (filter) węzeł node należy wykonać następujące kroki:

  1. Jeśli flaga aktywności jest ustawiona, to zrzuć wyjątek "InvalidStateError".
  2. Niech n będzie wartością atrybutu nodeType w node minus 1.
  3. Jeśli n-ty bit (gdzie 0 jest najmniej znaczącym bitem) w masce bitowej nie jest ustawiony, to zwróć FILTER_SKIP.
  4. Jeśli filtr ma wartość null, to zwróć FILTER_ACCEPT.
  5. Ustaw flagę aktywności.
  6. Niech result będzie wartością zwracaną przez wywołanie metody acceptNode() w filtrze, gdzie node jest pierwszym przekazanym argument.
  7. Usuń flagę aktywności.
  8. Jeśli jakiś wyjątek został zrzucony, to ponownie zrzuć wyjątek.
  9. Zwróć result.

traverse

Aby przejść # (traverse) w kierunku direction należy wykonać następujące kroki:

  1. Niech node będzie wartością atrybutu referenceNode w obiekcie kontekstu.
  2. Niech before node będzie wartością atrybutu pointerBeforeReferenceNode w obiekcie kontekstu.
  3. Wykonaj poniższe podkroki:
    1. Jeśli direction jest następujący

      Jeśli before node ma boolowską wartość false, to ustaw node na pierwszy węzeł następujący po node w kolekcji iteratora skojarzonej z obiektem kontekstu. Jeśli nie będzie takiego węzła, to zwróć wartość null.

      Jeśli before node ma boolowską wartość true, to ustaw go na boolowską wartość false.

      Jeśli direction jest poprzedzający

      Jeśli before node ma boolowską wartość true, to ustaw node na pierwszy węzeł poprzedzający przed node w kolekcji iteratora skojarzonej z obiektem kontekstu. Jeśli nie będzie takiego węzła, to zwróć wartość null.

      Jeśli before node ma boolowską wartość false, to ustaw go na boolowską wartość true.

    2. Przefiltruj node i niech result będzie zwracaną wartością.

    3. Jeśli result ma wartość FILTER_ACCEPT, to idź do następnego kroku w ogólnym zestawie kroków.

      W przeciwnym razie uruchom te podkroki ponownie.

  4. Ustaw wartość atrybutu referenceNode w obiekcie kontekstu na node, ustaw wartość atrybutu pointerBeforeReferenceNode w obiekcie kontekstu na before node i zwróć node.

traverse children

Aby przejść przez dzieci # (traverse children) z typem type należy wykonać następujące kroki:

  1. Niech node będzie wartością atrybutu currentNode w obiekcie kontekstu.
  2. Ustaw node na pierwsze dziecko w node jeśli type to pierwszy, i ostatnie dziecko w node jeśli type to ostatni.
  3. Jeśli node ma wartość null, to zwróć wartość null.

  4. Główna #: Wykonuj poniższe podkroki:

    1. Przefiltruj node i niech result będzie zwracaną wartością.
    2. Jeśli result ma wartość FILTER_ACCEPT, to ustaw atrybut currentNode w obiekcie kontekstu na node i zwróć node.

    3. Jeśli result ma wartość FILTER_SKIP, to uruchom wewnętrzne podkroki:

      1. Niech child będzie pierwszym dzieckiem w node jeśli type to pierwszy, i ostatnim dzieckiem w node jeśli type to ostatni.
      2. Jeśli child nie ma wartości null, to ustaw node na child i przejdź do (goto) Główna.

    4. Powtarzaj poniższe wewnętrzne podkroki:

      1. Niech sibling będzie bratem następującym względem node jeśli type to pierwszy, i bratem poprzedzającym jeśli type to ostatni.
      2. Jeśli sibling nie ma wartości null, to ustaw node na sibling i przejdź do (goto) Główna.
      3. Niech parent będzie rodzicem w node.
      4. Jeśli parent ma wartość null, parent jest korzeniem skojarzonym z obiektem kontekstu, lub parent jest wartością atrybutu currentNode w obiekcie kontekstu, to zwróć wartość null.
      5. W przeciwnym razie ustaw node na parent.

traverse siblings

Aby przejść przez braci # (traverse siblings) z typem type należy wykonać następujące kroki:

  1. Niech node będzie wartością atrybutu currentNode w obiekcie kontekstu.
  2. Jeśli node jest korzeniem skojarzonym z obiektem kontekstu, to zwróć wartości null.

  3. Wykonaj poniższe podkroki:

    1. Niech sibling będzie bratem następującym względem node jeśli type to następujący, i bratem poprzedzającym jeśli type to poprzedzający.

    2. Dopóki (while) sibling nie ma wartości null, to uruchom wewnętrzne podkroki:

      1. Ustaw node na sibling.
      2. Przefiltruj node i niech result będzie zwracaną wartością.
      3. Jeśli result ma wartość FILTER_ACCEPT, to ustaw atrybut currentNode w obiekcie kontekstu na node i zwróć node.
      4. Ustaw sibling na pierwsze dziecko w node jeśli type to następujący, i ostatnie dziecko w node jeśli type to poprzedzający.
      5. Jeśli result ma wartość FILTER_REJECT lub sibling ma wartość null, to ustaw sibling na brata następującego względem node jeśli type to następujący, i brata poprzedzającego jeśli type to poprzedzający.
    3. Ustaw node na swojego rodzica.
    4. Jeśli node ma wartość null lub jest korzeniem skojarzonym z obiektem kontekstu, to zwróć wartość null.
    5. Przefiltruj node i jeśli zwracaną wartością jest FILTER_ACCEPT, to zwróć wartość null.
    6. Uruchom te podkroki ponownie.
Pasek społecznościowy

SPIS TREŚCI AKTUALNEJ STRONY

Ogólne (H1) Traversal (H2) Pojęcia (H3) active flag (H4) root (H4) whatToShow (H4) filter (H4) iterator collection (H4) Algorytmy (H3) pre-removing steps (H4) removed (H4) filter (H4) traverse (H4) traverse children (H4) traverse siblings (H4)