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 Apple Inc. All rights reserved.
6 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Library General Public
10 * License as published by the Free Software Foundation; either
11 * version 2 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16 * Library General Public License for more details.
17 *
18 * You should have received a copy of the GNU Library General Public License
19 * along with this library; see the file COPYING.LIB.  If not, write to
20 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21 * Boston, MA 02110-1301, USA.
22 *
23 */
24
25#include "config.h"
26#include "core/dom/NodeTraversal.h"
27
28#include "core/dom/ContainerNode.h"
29
30namespace blink {
31
32Node* NodeTraversal::previousIncludingPseudo(const Node& current, const Node* stayWithin)
33{
34    if (current == stayWithin)
35        return 0;
36    if (Node* previous = current.pseudoAwarePreviousSibling()) {
37        while (previous->pseudoAwareLastChild())
38            previous = previous->pseudoAwareLastChild();
39        return previous;
40    }
41    return current.parentNode();
42}
43
44Node* NodeTraversal::nextIncludingPseudo(const Node& current, const Node* stayWithin)
45{
46    if (Node* next = current.pseudoAwareFirstChild())
47        return next;
48    if (current == stayWithin)
49        return 0;
50    if (Node* next = current.pseudoAwareNextSibling())
51        return next;
52    for (Node* parent = current.parentNode(); parent; parent = parent->parentNode()) {
53        if (parent == stayWithin)
54            return 0;
55        if (Node* next = parent->pseudoAwareNextSibling())
56            return next;
57    }
58    return 0;
59}
60
61Node* NodeTraversal::nextIncludingPseudoSkippingChildren(const Node& current, const Node* stayWithin)
62{
63    if (current == stayWithin)
64        return 0;
65    if (Node* next = current.pseudoAwareNextSibling())
66        return next;
67    for (Node* parent = current.parentNode(); parent; parent = parent->parentNode()) {
68        if (parent == stayWithin)
69            return 0;
70        if (Node* next = parent->pseudoAwareNextSibling())
71            return next;
72    }
73    return 0;
74}
75
76Node* NodeTraversal::nextAncestorSibling(const Node& current)
77{
78    ASSERT(!current.nextSibling());
79    for (Node* parent = current.parentNode(); parent; parent = parent->parentNode()) {
80        if (parent->nextSibling())
81            return parent->nextSibling();
82    }
83    return 0;
84}
85
86Node* NodeTraversal::nextAncestorSibling(const Node& current, const Node* stayWithin)
87{
88    ASSERT(!current.nextSibling());
89    ASSERT(current != stayWithin);
90    for (Node* parent = current.parentNode(); parent; parent = parent->parentNode()) {
91        if (parent == stayWithin)
92            return 0;
93        if (parent->nextSibling())
94            return parent->nextSibling();
95    }
96    return 0;
97}
98
99Node* NodeTraversal::lastWithin(const ContainerNode& current)
100{
101    Node* descendant = current.lastChild();
102    for (Node* child = descendant; child; child = child->lastChild())
103        descendant = child;
104    return descendant;
105}
106
107Node& NodeTraversal::lastWithinOrSelf(Node& current)
108{
109    Node* lastDescendant = current.isContainerNode() ? NodeTraversal::lastWithin(toContainerNode(current)) : 0;
110    return lastDescendant ? *lastDescendant : current;
111}
112
113Node* NodeTraversal::previous(const Node& current, const Node* stayWithin)
114{
115    if (current == stayWithin)
116        return 0;
117    if (current.previousSibling()) {
118        Node* previous = current.previousSibling();
119        while (Node* child = previous->lastChild())
120            previous = child;
121        return previous;
122    }
123    return current.parentNode();
124}
125
126Node* NodeTraversal::previousSkippingChildren(const Node& current, const Node* stayWithin)
127{
128    if (current == stayWithin)
129        return 0;
130    if (current.previousSibling())
131        return current.previousSibling();
132    for (Node* parent = current.parentNode(); parent; parent = parent->parentNode()) {
133        if (parent == stayWithin)
134            return 0;
135        if (parent->previousSibling())
136            return parent->previousSibling();
137    }
138    return 0;
139}
140
141Node* NodeTraversal::nextPostOrder(const Node& current, const Node* stayWithin)
142{
143    if (current == stayWithin)
144        return 0;
145    if (!current.nextSibling())
146        return current.parentNode();
147    Node* next = current.nextSibling();
148    while (Node* child = next->firstChild())
149        next = child;
150    return next;
151}
152
153static Node* previousAncestorSiblingPostOrder(const Node& current, const Node* stayWithin)
154{
155    ASSERT(!current.previousSibling());
156    for (Node* parent = current.parentNode(); parent; parent = parent->parentNode()) {
157        if (parent == stayWithin)
158            return 0;
159        if (parent->previousSibling())
160            return parent->previousSibling();
161    }
162    return 0;
163}
164
165Node* NodeTraversal::previousPostOrder(const Node& current, const Node* stayWithin)
166{
167    if (Node* lastChild = current.lastChild())
168        return lastChild;
169    if (current == stayWithin)
170        return 0;
171    if (current.previousSibling())
172        return current.previousSibling();
173    return previousAncestorSiblingPostOrder(current, stayWithin);
174}
175
176} // namespace blink
177