OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org) | 2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org) |
3 * (C) 1999 Antti Koivisto (koivisto@kde.org) | 3 * (C) 1999 Antti Koivisto (koivisto@kde.org) |
4 * (C) 2001 Dirk Mueller (mueller@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. | 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.t orchmobile.com/) | 6 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.t orchmobile.com/) |
7 * Copyright (C) 2014 Samsung Electronics. All rights reserved. | 7 * Copyright (C) 2014 Samsung Electronics. All rights reserved. |
8 * | 8 * |
9 * This library is free software; you can redistribute it and/or | 9 * This library is free software; you can redistribute it and/or |
10 * modify it under the terms of the GNU Library General Public | 10 * modify it under the terms of the GNU Library General Public |
(...skipping 13 matching lines...) Expand all Loading... | |
24 */ | 24 */ |
25 | 25 |
26 #ifndef NodeTraversal_h | 26 #ifndef NodeTraversal_h |
27 #define NodeTraversal_h | 27 #define NodeTraversal_h |
28 | 28 |
29 #include "core/dom/ContainerNode.h" | 29 #include "core/dom/ContainerNode.h" |
30 #include "core/dom/Node.h" | 30 #include "core/dom/Node.h" |
31 | 31 |
32 namespace blink { | 32 namespace blink { |
33 | 33 |
34 template <class Iterator> class TraversalRange; | |
35 template <class TraversalNext> class TraversalChildrenIterator; | |
36 template <class TraversalNext> class TraversalDescendantIterator; | |
37 template <class TraversalNext> class TraversalInclusiveDescendantIterator; | |
38 template <class TraversalNext> class TraversalNextIterator; | |
39 | |
34 class NodeTraversal { | 40 class NodeTraversal { |
35 public: | 41 public: |
42 using TraversalNodeType = Node; | |
36 // Does a pre-order traversal of the tree to find the next node after this o ne. | 43 // Does a pre-order traversal of the tree to find the next node after this o ne. |
37 // This uses the same order that tags appear in the source file. If the stay Within | 44 // This uses the same order that tags appear in the source file. If the stay Within |
38 // argument is non-null, the traversal will stop once the specified node is reached. | 45 // argument is non-null, the traversal will stop once the specified node is reached. |
39 // This can be used to restrict traversal to a particular sub-tree. | 46 // This can be used to restrict traversal to a particular sub-tree. |
40 static Node* next(const Node& current) { return traverseNextTemplate(current ); } | 47 static Node* next(const Node& current) { return traverseNextTemplate(current ); } |
41 static Node* next(const ContainerNode& current) { return traverseNextTemplat e(current); } | 48 static Node* next(const ContainerNode& current) { return traverseNextTemplat e(current); } |
42 static Node* next(const Node& current, const Node* stayWithin) { return trav erseNextTemplate(current, stayWithin); } | 49 static Node* next(const Node& current, const Node* stayWithin) { return trav erseNextTemplate(current, stayWithin); } |
43 static Node* next(const ContainerNode& current, const Node* stayWithin) { re turn traverseNextTemplate(current, stayWithin); } | 50 static Node* next(const ContainerNode& current, const Node* stayWithin) { re turn traverseNextTemplate(current, stayWithin); } |
44 | 51 |
45 // Like next, but skips children and starts with the next sibling. | 52 // Like next, but skips children and starts with the next sibling. |
46 static Node* nextSkippingChildren(const Node&); | 53 static Node* nextSkippingChildren(const Node&); |
47 static Node* nextSkippingChildren(const Node&, const Node* stayWithin); | 54 static Node* nextSkippingChildren(const Node&, const Node* stayWithin); |
48 | 55 |
56 static Node* firstWithin(const Node& current) { return current.firstChild(); } | |
57 | |
49 static Node* lastWithin(const ContainerNode&); | 58 static Node* lastWithin(const ContainerNode&); |
50 static Node& lastWithinOrSelf(Node&); | 59 static Node& lastWithinOrSelf(Node&); |
51 | 60 |
52 // Does a reverse pre-order traversal to find the node that comes before the current one in document order | 61 // Does a reverse pre-order traversal to find the node that comes before the current one in document order |
53 static Node* previous(const Node&, const Node* stayWithin = 0); | 62 static Node* previous(const Node&, const Node* stayWithin = 0); |
54 | 63 |
55 // Like previous, but skips children and starts with the next sibling. | 64 // Like previous, but skips children and starts with the next sibling. |
56 static Node* previousSkippingChildren(const Node&, const Node* stayWithin = 0); | 65 static Node* previousSkippingChildren(const Node&, const Node* stayWithin = 0); |
57 | 66 |
58 // Like next, but visits parents after their children. | 67 // Like next, but visits parents after their children. |
59 static Node* nextPostOrder(const Node&, const Node* stayWithin = 0); | 68 static Node* nextPostOrder(const Node&, const Node* stayWithin = 0); |
60 | 69 |
61 // Like previous, but visits parents before their children. | 70 // Like previous, but visits parents before their children. |
62 static Node* previousPostOrder(const Node&, const Node* stayWithin = 0); | 71 static Node* previousPostOrder(const Node&, const Node* stayWithin = 0); |
63 | 72 |
64 // Pre-order traversal including the pseudo-elements. | 73 // Pre-order traversal including the pseudo-elements. |
65 static Node* previousIncludingPseudo(const Node&, const Node* stayWithin = 0 ); | 74 static Node* previousIncludingPseudo(const Node&, const Node* stayWithin = 0 ); |
66 static Node* nextIncludingPseudo(const Node&, const Node* stayWithin = 0); | 75 static Node* nextIncludingPseudo(const Node&, const Node* stayWithin = 0); |
67 static Node* nextIncludingPseudoSkippingChildren(const Node&, const Node* st ayWithin = 0); | 76 static Node* nextIncludingPseudoSkippingChildren(const Node&, const Node* st ayWithin = 0); |
68 | 77 |
69 static Node* nextAncestorSibling(const Node&); | 78 static Node* nextAncestorSibling(const Node&); |
70 static Node* nextAncestorSibling(const Node&, const Node* stayWithin); | 79 static Node* nextAncestorSibling(const Node&, const Node* stayWithin); |
71 static Node& highestAncestorOrSelf(Node&); | 80 static Node& highestAncestorOrSelf(Node&); |
72 | 81 |
73 // Children traversal. | 82 // Children traversal. |
74 static Node* childAt(const Node& parent, unsigned index) { return childAtTem plate(parent, index); } | 83 static Node* childAt(const Node& parent, unsigned index) { return childAtTem plate(parent, index); } |
75 static Node* childAt(const ContainerNode& parent, unsigned index) { return c hildAtTemplate(parent, index); } | 84 static Node* childAt(const ContainerNode& parent, unsigned index) { return c hildAtTemplate(parent, index); } |
76 | 85 |
86 static Node* nextSibling(const Node& node) { return node.nextSibling(); } | |
87 | |
88 static TraversalRange<TraversalChildrenIterator<NodeTraversal>> childrenOf(c onst Node&); | |
89 static TraversalRange<TraversalDescendantIterator<NodeTraversal>> descendant sOf(const Node&); | |
90 static TraversalRange<TraversalInclusiveDescendantIterator<NodeTraversal>> i nclusiveDescendantsOf(const Node&); | |
91 static TraversalRange<TraversalNextIterator<NodeTraversal>> from(Node&); | |
92 | |
77 private: | 93 private: |
78 template <class NodeType> | 94 template <class NodeType> |
79 static Node* traverseNextTemplate(NodeType&); | 95 static Node* traverseNextTemplate(NodeType&); |
80 template <class NodeType> | 96 template <class NodeType> |
81 static Node* traverseNextTemplate(NodeType&, const Node* stayWithin); | 97 static Node* traverseNextTemplate(NodeType&, const Node* stayWithin); |
82 template <class NodeType> | 98 template <class NodeType> |
83 static Node* childAtTemplate(NodeType&, unsigned); | 99 static Node* childAtTemplate(NodeType&, unsigned); |
84 }; | 100 }; |
85 | 101 |
102 template <class Iterator> | |
103 class TraversalRange { | |
104 public: | |
105 TraversalRange(const Node& start) : m_start(start) { } | |
106 Iterator begin() { return Iterator(m_start); } | |
107 Iterator end() { return Iterator::end(); } | |
108 private: | |
109 const Node& m_start; | |
110 }; | |
111 | |
112 template <class TraversalNext> | |
113 class TraversalIteratorBase { | |
114 public: | |
115 using NodeType = typename TraversalNext::TraversalNodeType; | |
116 NodeType& operator*() { return *m_current; } | |
117 bool operator!=(const TraversalIteratorBase& rval) const { return m_current != rval.m_current ; } | |
118 protected: | |
119 TraversalIteratorBase(NodeType* current) : m_current(current) { }; | |
120 NodeType* m_current; | |
121 }; | |
122 | |
123 template <class TraversalNext> | |
124 class TraversalChildrenIterator : public TraversalIteratorBase<TraversalNext> { | |
125 public: | |
126 using TraversalIteratorBase<TraversalNext>::m_current; | |
127 TraversalChildrenIterator(const Node& start) : TraversalIteratorBase<Travers alNext>(TraversalNext::firstWithin(start)) { }; | |
128 void operator++() { m_current = TraversalNext::nextSibling(*m_current); }; | |
129 static TraversalChildrenIterator end() { return TraversalChildrenIterator(); }; | |
130 private: | |
131 TraversalChildrenIterator() : TraversalIteratorBase<TraversalNext>(nullptr) { }; | |
132 }; | |
133 | |
134 template <class TraversalNext> | |
135 class TraversalNextIterator : public TraversalIteratorBase<TraversalNext> { | |
136 public: | |
137 using TraversalIteratorBase<TraversalNext>::m_current; | |
138 TraversalNextIterator(const Node& start) : TraversalIteratorBase<TraversalNe xt>(TraversalNext::next(start)) { }; | |
139 void operator++() { m_current = TraversalNext::next(*m_current); } | |
140 static TraversalNextIterator end() { return TraversalNextIterator(); }; | |
141 private: | |
142 TraversalNextIterator() : TraversalIteratorBase<TraversalNext>(nullptr) { }; | |
143 }; | |
144 | |
145 template <class TraversalNext> | |
146 class TraversalDescendantIterator : public TraversalIteratorBase<TraversalNext> { | |
147 public: | |
148 using TraversalIteratorBase<TraversalNext>::m_current; | |
149 TraversalDescendantIterator(const Node& start) : TraversalIteratorBase<Trave rsalNext>(TraversalNext::firstWithin(start)), m_root(&start) { }; | |
esprehn
2014/10/16 17:43:25
need explicit on these classes
| |
150 void operator++() { m_current = TraversalNext::next(*m_current, m_root); } | |
151 static TraversalDescendantIterator end() { return TraversalDescendantIterato r(); }; | |
152 private: | |
153 TraversalDescendantIterator() : TraversalIteratorBase<TraversalNext>(nullptr ), m_root(nullptr) { }; | |
154 const Node* m_root; | |
155 }; | |
156 | |
157 template <class TraversalNext> | |
158 class TraversalInclusiveDescendantIterator : public TraversalIteratorBase<Traver salNext> { | |
159 public: | |
160 using NodeType = typename TraversalNext::TraversalNodeType; | |
161 using TraversalIteratorBase<TraversalNext>::m_current; | |
162 TraversalInclusiveDescendantIterator(const NodeType& start) : TraversalItera torBase<TraversalNext>(const_cast<NodeType*>(&start)), m_root(&start) { }; | |
163 void operator++() { m_current = TraversalNext::next(*m_current, m_root); } | |
164 static TraversalInclusiveDescendantIterator end() { return TraversalInclusiv eDescendantIterator(); }; | |
165 private: | |
166 TraversalInclusiveDescendantIterator() : TraversalIteratorBase<TraversalNext >(nullptr), m_root(nullptr) { }; | |
167 const Node* m_root; | |
168 }; | |
169 | |
170 inline TraversalRange<TraversalChildrenIterator<NodeTraversal>> NodeTraversal::c hildrenOf(const Node& parent) | |
171 { | |
172 return TraversalRange<TraversalChildrenIterator<NodeTraversal>>(parent); | |
173 } | |
174 | |
175 inline TraversalRange<TraversalDescendantIterator<NodeTraversal>> NodeTraversal: :descendantsOf(const Node& root) | |
176 { | |
177 return TraversalRange<TraversalDescendantIterator<NodeTraversal>>(root); | |
178 } | |
179 | |
180 inline TraversalRange<TraversalInclusiveDescendantIterator<NodeTraversal>> NodeT raversal::inclusiveDescendantsOf(const Node& root) | |
181 { | |
182 return TraversalRange<TraversalInclusiveDescendantIterator<NodeTraversal>>(r oot); | |
183 } | |
184 | |
185 inline TraversalRange<TraversalNextIterator<NodeTraversal>> NodeTraversal::from( Node& start) | |
186 { | |
187 return TraversalRange<TraversalNextIterator<NodeTraversal>>(start); | |
188 }; | |
189 | |
86 template <class NodeType> | 190 template <class NodeType> |
87 inline Node* NodeTraversal::traverseNextTemplate(NodeType& current) | 191 inline Node* NodeTraversal::traverseNextTemplate(NodeType& current) |
88 { | 192 { |
89 if (current.hasChildren()) | 193 if (current.hasChildren()) |
90 return current.firstChild(); | 194 return current.firstChild(); |
91 if (current.nextSibling()) | 195 if (current.nextSibling()) |
92 return current.nextSibling(); | 196 return current.nextSibling(); |
93 return nextAncestorSibling(current); | 197 return nextAncestorSibling(current); |
94 } | 198 } |
95 | 199 |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
134 { | 238 { |
135 Node* child = parent.firstChild(); | 239 Node* child = parent.firstChild(); |
136 while (child && index--) | 240 while (child && index--) |
137 child = child->nextSibling(); | 241 child = child->nextSibling(); |
138 return child; | 242 return child; |
139 } | 243 } |
140 | 244 |
141 } // namespace blink | 245 } // namespace blink |
142 | 246 |
143 #endif | 247 #endif |
OLD | NEW |