1/*
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4 *           (C) 2001 Dirk Mueller (mueller@kde.org)
5 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
6 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
7 * Copyright (C) 2014 Samsung Electronics. All rights reserved.
8 *
9 * This library is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Library General Public
11 * License as published by the Free Software Foundation; either
12 * version 2 of the License, or (at your option) any later version.
13 *
14 * This library is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * Library General Public License for more details.
18 *
19 * You should have received a copy of the GNU Library General Public License
20 * along with this library; see the file COPYING.LIB.  If not, write to
21 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
22 * Boston, MA 02110-1301, USA.
23 *
24 */
25
26#ifndef ElementTraversal_h
27#define ElementTraversal_h
28
29#include "core/dom/Element.h"
30#include "core/dom/NodeTraversal.h"
31
32namespace blink {
33
34template <class ElementType>
35class Traversal {
36public:
37    // First or last ElementType child of the node.
38    static ElementType* firstChild(const ContainerNode& current) { return firstChildTemplate(current); }
39    static ElementType* firstChild(const Node& current) { return firstChildTemplate(current); }
40    template <class MatchFunc>
41    static ElementType* firstChild(const ContainerNode&, MatchFunc);
42    static ElementType* lastChild(const ContainerNode& current) { return lastChildTemplate(current); }
43    static ElementType* lastChild(const Node& current) { return lastChildTemplate(current); }
44    template <class MatchFunc>
45    static ElementType* lastChild(const ContainerNode&, MatchFunc);
46
47    // First ElementType ancestor of the node.
48    static ElementType* firstAncestor(const Node& current);
49    static ElementType* firstAncestorOrSelf(Node& current) { return firstAncestorOrSelfTemplate(current); }
50    static ElementType* firstAncestorOrSelf(Element& current) { return firstAncestorOrSelfTemplate(current); }
51    static const ElementType* firstAncestorOrSelf(const Node& current) { return firstAncestorOrSelfTemplate(const_cast<Node&>(current)); }
52    static const ElementType* firstAncestorOrSelf(const Element& current) { return firstAncestorOrSelfTemplate(const_cast<Element&>(current)); }
53
54    // First or last ElementType descendant of the node.
55    // For Elements firstWithin() is always the same as firstChild().
56    static ElementType* firstWithin(const ContainerNode& current) { return firstWithinTemplate(current); }
57    static ElementType* firstWithin(const Node& current) { return firstWithinTemplate(current); }
58    template <typename MatchFunc>
59    static ElementType* firstWithin(const ContainerNode&, MatchFunc);
60    static ElementType* lastWithin(const ContainerNode& current) { return lastWithinTemplate(current); }
61    static ElementType* lastWithin(const Node& current) { return lastWithinTemplate(current); }
62    template <class MatchFunc>
63    static ElementType* lastWithin(const ContainerNode&, MatchFunc);
64
65    // Pre-order traversal skipping non-element nodes.
66    static ElementType* next(const ContainerNode& current) { return nextTemplate(current); }
67    static ElementType* next(const Node& current) { return nextTemplate(current); }
68    static ElementType* next(const ContainerNode& current, const Node* stayWithin) { return nextTemplate(current, stayWithin); }
69    static ElementType* next(const Node& current, const Node* stayWithin) { return nextTemplate(current, stayWithin); }
70    template <class MatchFunc>
71    static ElementType* next(const ContainerNode& current, const Node* stayWithin, MatchFunc);
72    static ElementType* previous(const Node&);
73    static ElementType* previous(const Node&, const Node* stayWithin);
74    template <class MatchFunc>
75    static ElementType* previous(const ContainerNode& current, const Node* stayWithin, MatchFunc);
76
77    // Like next, but skips children.
78    static ElementType* nextSkippingChildren(const Node&);
79    static ElementType* nextSkippingChildren(const Node&, const Node* stayWithin);
80
81    // Pre-order traversal including the pseudo-elements.
82    static ElementType* previousIncludingPseudo(const Node&, const Node* stayWithin = 0);
83    static ElementType* nextIncludingPseudo(const Node&, const Node* stayWithin = 0);
84    static ElementType* nextIncludingPseudoSkippingChildren(const Node&, const Node* stayWithin = 0);
85
86    // Utility function to traverse only the element and pseudo-element siblings of a node.
87    static ElementType* pseudoAwarePreviousSibling(const Node&);
88
89    // Previous / Next sibling.
90    static ElementType* previousSibling(const Node&);
91    template <class MatchFunc>
92    static ElementType* previousSibling(const Node&, MatchFunc);
93    static ElementType* nextSibling(const Node&);
94    template <class MatchFunc>
95    static ElementType* nextSibling(const Node&, MatchFunc);
96
97private:
98    template <class NodeType>
99    static ElementType* firstChildTemplate(NodeType&);
100    template <class NodeType>
101    static ElementType* lastChildTemplate(NodeType&);
102    template <class NodeType>
103    static ElementType* firstAncestorOrSelfTemplate(NodeType&);
104    template <class NodeType>
105    static ElementType* firstWithinTemplate(NodeType&);
106    template <class NodeType>
107    static ElementType* lastWithinTemplate(NodeType&);
108    template <class NodeType>
109    static ElementType* nextTemplate(NodeType&);
110    template <class NodeType>
111    static ElementType* nextTemplate(NodeType&, const Node* stayWithin);
112};
113
114typedef Traversal<Element> ElementTraversal;
115
116// Specialized for pure Element to exploit the fact that Elements parent is always either another Element or the root.
117template <>
118template <class NodeType>
119inline Element* Traversal<Element>::firstWithinTemplate(NodeType& current)
120{
121    return firstChildTemplate(current);
122}
123
124template <>
125template <class NodeType>
126inline Element* Traversal<Element>::nextTemplate(NodeType& current)
127{
128    Node* node = NodeTraversal::next(current);
129    while (node && !node->isElementNode())
130        node = NodeTraversal::nextSkippingChildren(*node);
131    return toElement(node);
132}
133
134template <>
135template <class NodeType>
136inline Element* Traversal<Element>::nextTemplate(NodeType& current, const Node* stayWithin)
137{
138    Node* node = NodeTraversal::next(current, stayWithin);
139    while (node && !node->isElementNode())
140        node = NodeTraversal::nextSkippingChildren(*node, stayWithin);
141    return toElement(node);
142}
143
144// Generic versions.
145template <class ElementType>
146template <class NodeType>
147inline ElementType* Traversal<ElementType>::firstChildTemplate(NodeType& current)
148{
149    Node* node = current.firstChild();
150    while (node && !isElementOfType<const ElementType>(*node))
151        node = node->nextSibling();
152    return toElement<ElementType>(node);
153}
154
155template <class ElementType>
156template <class MatchFunc>
157inline ElementType* Traversal<ElementType>::firstChild(const ContainerNode& current, MatchFunc isMatch)
158{
159    ElementType* element = Traversal<ElementType>::firstChild(current);
160    while (element && !isMatch(*element))
161        element = Traversal<ElementType>::nextSibling(*element);
162    return element;
163}
164
165template <class ElementType>
166inline ElementType* Traversal<ElementType>::firstAncestor(const Node& current)
167{
168    ContainerNode* ancestor = current.parentNode();
169    while (ancestor && !isElementOfType<const ElementType>(*ancestor))
170        ancestor = ancestor->parentNode();
171    return toElement<ElementType>(ancestor);
172}
173
174template <class ElementType>
175template <class NodeType>
176inline ElementType* Traversal<ElementType>::firstAncestorOrSelfTemplate(NodeType& current)
177{
178    if (isElementOfType<const ElementType>(current))
179        return &toElement<ElementType>(current);
180    return firstAncestor(current);
181}
182
183template <class ElementType>
184template <class NodeType>
185inline ElementType* Traversal<ElementType>::lastChildTemplate(NodeType& current)
186{
187    Node* node = current.lastChild();
188    while (node && !isElementOfType<const ElementType>(*node))
189        node = node->previousSibling();
190    return toElement<ElementType>(node);
191}
192
193template <class ElementType>
194template <class MatchFunc>
195inline ElementType* Traversal<ElementType>::lastChild(const ContainerNode& current, MatchFunc isMatch)
196{
197    ElementType* element = Traversal<ElementType>::lastChild(current);
198    while (element && !isMatch(*element))
199        element = Traversal<ElementType>::previousSibling(*element);
200    return element;
201}
202
203template <class ElementType>
204template <class NodeType>
205inline ElementType* Traversal<ElementType>::firstWithinTemplate(NodeType& current)
206{
207    Node* node = current.firstChild();
208    while (node && !isElementOfType<const ElementType>(*node))
209        node = NodeTraversal::next(*node, &current);
210    return toElement<ElementType>(node);
211}
212
213template <class ElementType>
214template <typename MatchFunc>
215inline ElementType* Traversal<ElementType>::firstWithin(const ContainerNode& current, MatchFunc isMatch)
216{
217    ElementType* element = Traversal<ElementType>::firstWithin(current);
218    while (element && !isMatch(*element))
219        element = Traversal<ElementType>::next(*element, &current, isMatch);
220    return element;
221}
222
223template <class ElementType>
224template <class NodeType>
225inline ElementType* Traversal<ElementType>::lastWithinTemplate(NodeType& current)
226{
227    Node* node = NodeTraversal::lastWithin(current);
228    while (node && !isElementOfType<const ElementType>(*node))
229        node = NodeTraversal::previous(*node, &current);
230    return toElement<ElementType>(node);
231}
232
233template <class ElementType>
234template <class MatchFunc>
235inline ElementType* Traversal<ElementType>::lastWithin(const ContainerNode& current, MatchFunc isMatch)
236{
237    ElementType* element = Traversal<ElementType>::lastWithin(current);
238    while (element && !isMatch(*element))
239        element = Traversal<ElementType>::previous(*element, &current, isMatch);
240    return element;
241}
242
243template <class ElementType>
244template <class NodeType>
245inline ElementType* Traversal<ElementType>::nextTemplate(NodeType& current)
246{
247    Node* node = NodeTraversal::next(current);
248    while (node && !isElementOfType<const ElementType>(*node))
249        node = NodeTraversal::next(*node);
250    return toElement<ElementType>(node);
251}
252
253template <class ElementType>
254template <class NodeType>
255inline ElementType* Traversal<ElementType>::nextTemplate(NodeType& current, const Node* stayWithin)
256{
257    Node* node = NodeTraversal::next(current, stayWithin);
258    while (node && !isElementOfType<const ElementType>(*node))
259        node = NodeTraversal::next(*node, stayWithin);
260    return toElement<ElementType>(node);
261}
262
263template <class ElementType>
264template <class MatchFunc>
265inline ElementType* Traversal<ElementType>::next(const ContainerNode& current, const Node* stayWithin, MatchFunc isMatch)
266{
267    ElementType* element = Traversal<ElementType>::next(current, stayWithin);
268    while (element && !isMatch(*element))
269        element = Traversal<ElementType>::next(*element, stayWithin);
270    return element;
271}
272
273template <class ElementType>
274inline ElementType* Traversal<ElementType>::previous(const Node& current)
275{
276    Node* node = NodeTraversal::previous(current);
277    while (node && !isElementOfType<const ElementType>(*node))
278        node = NodeTraversal::previous(*node);
279    return toElement<ElementType>(node);
280}
281
282template <class ElementType>
283inline ElementType* Traversal<ElementType>::previous(const Node& current, const Node* stayWithin)
284{
285    Node* node = NodeTraversal::previous(current, stayWithin);
286    while (node && !isElementOfType<const ElementType>(*node))
287        node = NodeTraversal::previous(*node, stayWithin);
288    return toElement<ElementType>(node);
289}
290
291template <class ElementType>
292template <class MatchFunc>
293inline ElementType* Traversal<ElementType>::previous(const ContainerNode& current, const Node* stayWithin, MatchFunc isMatch)
294{
295    ElementType* element = Traversal<ElementType>::previous(current, stayWithin);
296    while (element && !isMatch(*element))
297        element = Traversal<ElementType>::previous(*element, stayWithin);
298    return element;
299}
300
301template <class ElementType>
302inline ElementType* Traversal<ElementType>::nextSkippingChildren(const Node& current)
303{
304    Node* node = NodeTraversal::nextSkippingChildren(current);
305    while (node && !isElementOfType<const ElementType>(*node))
306        node = NodeTraversal::nextSkippingChildren(*node);
307    return toElement<ElementType>(node);
308}
309
310template <class ElementType>
311inline ElementType* Traversal<ElementType>::nextSkippingChildren(const Node& current, const Node* stayWithin)
312{
313    Node* node = NodeTraversal::nextSkippingChildren(current, stayWithin);
314    while (node && !isElementOfType<const ElementType>(*node))
315        node = NodeTraversal::nextSkippingChildren(*node, stayWithin);
316    return toElement<ElementType>(node);
317}
318
319template <class ElementType>
320inline ElementType* Traversal<ElementType>::previousIncludingPseudo(const Node& current, const Node* stayWithin)
321{
322    Node* node = NodeTraversal::previousIncludingPseudo(current, stayWithin);
323    while (node && !isElementOfType<const ElementType>(*node))
324        node = NodeTraversal::previousIncludingPseudo(*node, stayWithin);
325    return toElement<ElementType>(node);
326}
327
328template <class ElementType>
329inline ElementType* Traversal<ElementType>::nextIncludingPseudo(const Node& current, const Node* stayWithin)
330{
331    Node* node = NodeTraversal::nextIncludingPseudo(current, stayWithin);
332    while (node && !isElementOfType<const ElementType>(*node))
333        node = NodeTraversal::nextIncludingPseudo(*node, stayWithin);
334    return toElement<ElementType>(node);
335}
336
337template <class ElementType>
338inline ElementType* Traversal<ElementType>::nextIncludingPseudoSkippingChildren(const Node& current, const Node* stayWithin)
339{
340    Node* node = NodeTraversal::nextIncludingPseudoSkippingChildren(current, stayWithin);
341    while (node && !isElementOfType<const ElementType>(*node))
342        node = NodeTraversal::nextIncludingPseudoSkippingChildren(*node, stayWithin);
343    return toElement<ElementType>(node);
344}
345
346template <class ElementType>
347inline ElementType* Traversal<ElementType>::pseudoAwarePreviousSibling(const Node& current)
348{
349    Node* node = current.pseudoAwarePreviousSibling();
350    while (node && !isElementOfType<const ElementType>(*node))
351        node = node->pseudoAwarePreviousSibling();
352    return toElement<ElementType>(node);
353}
354
355template <class ElementType>
356inline ElementType* Traversal<ElementType>::previousSibling(const Node& current)
357{
358    Node* node = current.previousSibling();
359    while (node && !isElementOfType<const ElementType>(*node))
360        node = node->previousSibling();
361    return toElement<ElementType>(node);
362}
363
364template <class ElementType>
365template <class MatchFunc>
366inline ElementType* Traversal<ElementType>::previousSibling(const Node& current, MatchFunc isMatch)
367{
368    ElementType* element = Traversal<ElementType>::previousSibling(current);
369    while (element && !isMatch(*element))
370        element = Traversal<ElementType>::previousSibling(*element);
371    return element;
372}
373
374template <class ElementType>
375inline ElementType* Traversal<ElementType>::nextSibling(const Node& current)
376{
377    Node* node = current.nextSibling();
378    while (node && !isElementOfType<const ElementType>(*node))
379        node = node->nextSibling();
380    return toElement<ElementType>(node);
381}
382
383template <class ElementType>
384template <class MatchFunc>
385inline ElementType* Traversal<ElementType>::nextSibling(const Node& current, MatchFunc isMatch)
386{
387    ElementType* element = Traversal<ElementType>::nextSibling(current);
388    while (element && !isMatch(*element))
389        element = Traversal<ElementType>::nextSibling(*element);
390    return element;
391}
392
393} // namespace blink
394
395#endif
396