OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2013 Google Inc. All rights reserved. | 2 * Copyright (C) 2013 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions are | 5 * modification, are permitted provided that the following conditions are |
6 * met: | 6 * met: |
7 * | 7 * |
8 * * Redistributions of source code must retain the above copyright | 8 * * Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * * Redistributions in binary form must reproduce the above | 10 * * Redistributions in binary form must reproduce the above |
(...skipping 141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
152 if (NodeType* nextSibling = current.nextSibling()) | 152 if (NodeType* nextSibling = current.nextSibling()) |
153 return nextSibling; | 153 return nextSibling; |
154 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ | 154 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ |
155 if (NodeType* nextSibling = parent->nextSibling()) | 155 if (NodeType* nextSibling = parent->nextSibling()) |
156 return nextSibling; | 156 return nextSibling; |
157 } | 157 } |
158 | 158 |
159 return 0; | 159 return 0; |
160 } | 160 } |
161 | 161 |
162 template<class ContainerType> | |
163 inline ContainerType* traverseNext(const ContainerType& current) | |
164 { return traverseNext<ContainerType, ContainerType>(current); } | |
165 | |
166 template<class NodeType, class ContainerType> | 162 template<class NodeType, class ContainerType> |
167 inline NodeType* traverseNext(const ContainerType& current, const NodeType* stay
Within) | 163 inline NodeType* traverseNext(const ContainerType& current, const NodeType* stay
Within) |
168 { | 164 { |
169 if (NodeType* firstChild = current.firstChild()) | 165 if (NodeType* firstChild = current.firstChild()) |
170 return firstChild; | 166 return firstChild; |
171 if (¤t == stayWithin) | 167 if (¤t == stayWithin) |
172 return 0; | 168 return 0; |
173 if (NodeType* nextSibling = current.nextSibling()) | 169 if (NodeType* nextSibling = current.nextSibling()) |
174 return nextSibling; | 170 return nextSibling; |
175 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ | 171 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ |
176 if (parent == stayWithin) | 172 if (parent == stayWithin) |
177 return 0; | 173 return 0; |
178 if (NodeType* nextSibling = parent->nextSibling()) | 174 if (NodeType* nextSibling = parent->nextSibling()) |
179 return nextSibling; | 175 return nextSibling; |
180 } | 176 } |
181 | 177 |
182 return 0; | 178 return 0; |
183 } | 179 } |
184 | 180 |
185 template<class ContainerType> | |
186 inline ContainerType* traverseNext(const ContainerType& current, const Container
Type* stayWithin) | |
187 { return traverseNext<ContainerType, ContainerType>(current, stayWithin); } | |
188 | |
189 /* non-recursive post-order traversal */ | 181 /* non-recursive post-order traversal */ |
190 template<class NodeType, class ContainerType> | 182 template<class NodeType, class ContainerType> |
191 inline NodeType* traverseFirstPostOrder(const ContainerType& current) | 183 inline NodeType* traverseFirstPostOrder(const ContainerType& current) |
192 { | 184 { |
193 NodeType* first = current.here(); | 185 NodeType* first = current.here(); |
194 while (first->firstChild()) | 186 while (first->firstChild()) |
195 first = first->firstChild(); | 187 first = first->firstChild(); |
196 return first; | 188 return first; |
197 } | 189 } |
198 | 190 |
199 template<class ContainerType> | |
200 inline ContainerType* traverseFirstPostOrder(const ContainerType& current) | |
201 { return traverseFirstPostOrder<ContainerType, ContainerType>(current); } | |
202 | |
203 template<class NodeType, class ContainerType> | 191 template<class NodeType, class ContainerType> |
204 inline NodeType* traverseNextPostOrder(const ContainerType& current) | 192 inline NodeType* traverseNextPostOrder(const ContainerType& current) |
205 { | 193 { |
206 NodeType* nextSibling = current.nextSibling(); | 194 NodeType* nextSibling = current.nextSibling(); |
207 if (!nextSibling) | 195 if (!nextSibling) |
208 return current.parent(); | 196 return current.parent(); |
209 while (nextSibling->firstChild()) | 197 while (nextSibling->firstChild()) |
210 nextSibling = nextSibling->firstChild(); | 198 nextSibling = nextSibling->firstChild(); |
211 return nextSibling; | 199 return nextSibling; |
212 } | 200 } |
213 | 201 |
214 template<class ContainerType> | |
215 inline ContainerType* traverseNextPostOrder(const ContainerType& current) | |
216 { return traverseNextPostOrder<ContainerType, ContainerType>(current); } | |
217 | |
218 template<class NodeType, class ContainerType> | 202 template<class NodeType, class ContainerType> |
219 inline NodeType* traverseNextPostOrder(const ContainerType& current, const NodeT
ype* stayWithin) | 203 inline NodeType* traverseNextPostOrder(const ContainerType& current, const NodeT
ype* stayWithin) |
220 { | 204 { |
221 if (¤t == stayWithin) | 205 if (¤t == stayWithin) |
222 return 0; | 206 return 0; |
223 | 207 |
224 NodeType* nextSibling = current.nextSibling(); | 208 NodeType* nextSibling = current.nextSibling(); |
225 if (!nextSibling) | 209 if (!nextSibling) |
226 return current.parent(); | 210 return current.parent(); |
227 while (nextSibling->firstChild()) | 211 while (nextSibling->firstChild()) |
228 nextSibling = nextSibling->firstChild(); | 212 nextSibling = nextSibling->firstChild(); |
229 return nextSibling; | 213 return nextSibling; |
230 } | 214 } |
231 | 215 |
232 template<class ContainerType> | |
233 inline ContainerType* traverseNextPostOrder(const ContainerType& current, const
ContainerType* stayWithin) | |
234 { return traverseNextPostOrder<ContainerType, ContainerType>(current, stayWithin
); } | |
235 | |
236 /* non-recursive traversal skipping children */ | 216 /* non-recursive traversal skipping children */ |
237 template <class NodeType, class ContainerType> | 217 template <class NodeType, class ContainerType> |
238 inline NodeType* traverseNextSkippingChildren(const ContainerType& current) | 218 inline NodeType* traverseNextSkippingChildren(const ContainerType& current) |
239 { | 219 { |
240 if (current.nextSibling()) | 220 if (current.nextSibling()) |
241 return current.nextSibling(); | 221 return current.nextSibling(); |
242 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ | 222 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ |
243 if (NodeType* nextSibling = parent->nextSibling()) | 223 if (NodeType* nextSibling = parent->nextSibling()) |
244 return nextSibling; | 224 return nextSibling; |
245 } | 225 } |
246 | 226 |
247 return 0; | 227 return 0; |
248 } | 228 } |
249 | 229 |
250 template <class ContainerType> | |
251 inline ContainerType* traverseNextSkippingChildren(const ContainerType& current) | |
252 { return traverseNextSkippingChildren<ContainerType, ContainerType>(current); } | |
253 | |
254 template <class NodeType, class ContainerType> | 230 template <class NodeType, class ContainerType> |
255 inline NodeType* traverseNextSkippingChildren(const ContainerType& current, cons
t NodeType* stayWithin) | 231 inline NodeType* traverseNextSkippingChildren(const ContainerType& current, cons
t NodeType* stayWithin) |
256 { | 232 { |
257 if (current == stayWithin) | 233 if (current == stayWithin) |
258 return 0; | 234 return 0; |
259 if (current.nextSibling()) | 235 if (current.nextSibling()) |
260 return current.nextSibling(); | 236 return current.nextSibling(); |
261 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ | 237 for (NodeType* parent = current.parent(); parent; parent = parent->parent())
{ |
262 if (parent == stayWithin) | 238 if (parent == stayWithin) |
263 return 0; | 239 return 0; |
264 if (NodeType* nextSibling = parent->nextSibling()) | 240 if (NodeType* nextSibling = parent->nextSibling()) |
265 return nextSibling; | 241 return nextSibling; |
266 } | 242 } |
267 | 243 |
268 return 0; | 244 return 0; |
269 } | 245 } |
270 | 246 |
271 template <class ContainerType> | |
272 inline ContainerType* traverseNextSkippingChildren(const ContainerType& current,
const ContainerType* stayWithin) | |
273 { return traverseNextSkippingChildren<ContainerType, ContainerType>(current, sta
yWithin); } | |
274 | |
275 } // namespace WTF | 247 } // namespace WTF |
276 | 248 |
277 using WTF::TreeNode; | 249 using WTF::TreeNode; |
278 using WTF::traverseNext; | 250 using WTF::traverseNext; |
279 using WTF::traverseFirstPostOrder; | 251 using WTF::traverseFirstPostOrder; |
280 using WTF::traverseNextPostOrder; | 252 using WTF::traverseNextPostOrder; |
281 using WTF::traverseNextSkippingChildren; | 253 using WTF::traverseNextSkippingChildren; |
282 | 254 |
283 #endif // TreeNode_h | 255 #endif // TreeNode_h |
OLD | NEW |