1/*
2 * Copyright (C) 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef CollectionTraversal_h
27#define CollectionTraversal_h
28
29#include "CollectionType.h"
30#include "ElementChildIterator.h"
31#include "ElementDescendantIterator.h"
32
33namespace WebCore {
34
35template <CollectionTraversalType traversalType>
36struct CollectionTraversal { };
37
38template <>
39struct CollectionTraversal<CollectionTraversalType::Descendants> {
40 using IteratorType = ElementDescendantIterator;
41
42 static ElementDescendantIterator end(ContainerNode&) { return ElementDescendantIterator(); }
43
44 template <typename CollectionClass>
45 static ElementDescendantIterator begin(const CollectionClass&, ContainerNode& rootNode);
46
47 template <typename CollectionClass>
48 static ElementDescendantIterator last(const CollectionClass&, ContainerNode& rootNode);
49
50 template <typename CollectionClass>
51 static void traverseForward(const CollectionClass&, ElementDescendantIterator& current, unsigned count, unsigned& traversedCount);
52
53 template <typename CollectionClass>
54 static void traverseBackward(const CollectionClass&, ElementDescendantIterator& current, unsigned count);
55};
56
57template <>
58struct CollectionTraversal<CollectionTraversalType::ChildrenOnly> {
59 using IteratorType = ElementChildIterator<Element>;
60
61 static ElementChildIterator<Element> end(ContainerNode& rootNode) { return ElementChildIterator<Element>(rootNode); }
62
63 template <typename CollectionClass>
64 static ElementChildIterator<Element> begin(const CollectionClass&, ContainerNode& rootNode);
65
66 template <typename CollectionClass>
67 static ElementChildIterator<Element> last(const CollectionClass&, ContainerNode& rootNode);
68
69 template <typename CollectionClass>
70 static void traverseForward(const CollectionClass&, ElementChildIterator<Element>& current, unsigned count, unsigned& traversedCount);
71
72 template <typename CollectionClass>
73 static void traverseBackward(const CollectionClass&, ElementChildIterator<Element>& current, unsigned count);
74};
75
76template <>
77struct CollectionTraversal<CollectionTraversalType::CustomForwardOnly> {
78 using IteratorType = Element*;
79
80 static Element* end(ContainerNode&) { return nullptr; }
81
82 template <typename CollectionClass>
83 static Element* begin(const CollectionClass&, ContainerNode&);
84
85 template <typename CollectionClass>
86 static Element* last(const CollectionClass&, ContainerNode&);
87
88 template <typename CollectionClass>
89 static void traverseForward(const CollectionClass&, Element*& current, unsigned count, unsigned& traversedCount);
90
91 template <typename CollectionClass>
92 static void traverseBackward(const CollectionClass&, Element*&, unsigned count);
93};
94
95template <typename CollectionClass>
96inline ElementDescendantIterator CollectionTraversal<CollectionTraversalType::Descendants>::begin(const CollectionClass& collection, ContainerNode& rootNode)
97{
98 auto descendants = elementDescendants(rootNode);
99 auto end = descendants.end();
100 for (auto it = descendants.begin(); it != end; ++it) {
101 if (collection.elementMatches(*it))
102 return it;
103 }
104 return end;
105}
106
107template <typename CollectionClass>
108inline ElementChildIterator<Element> CollectionTraversal<CollectionTraversalType::ChildrenOnly>::begin(const CollectionClass& collection, ContainerNode& rootNode)
109{
110 auto children = childrenOfType<Element>(rootNode);
111 auto end = children.end();
112 for (auto it = children.begin(); it != end; ++it) {
113 if (collection.elementMatches(*it))
114 return it;
115 }
116 return end;
117}
118
119template <typename CollectionClass>
120inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::begin(const CollectionClass& collection, ContainerNode&)
121{
122 return collection.customElementAfter(nullptr);
123}
124
125template <typename CollectionClass>
126inline ElementDescendantIterator CollectionTraversal<CollectionTraversalType::Descendants>::last(const CollectionClass& collection, ContainerNode& rootNode)
127{
128 auto descendants = elementDescendants(rootNode);
129 auto end = descendants.end();
130 for (auto it = descendants.last(); it != end; --it) {
131 if (collection.elementMatches(*it))
132 return it;
133 }
134 return end;
135}
136
137template <typename CollectionClass>
138inline ElementChildIterator<Element> CollectionTraversal<CollectionTraversalType::ChildrenOnly>::last(const CollectionClass& collection, ContainerNode& rootNode)
139{
140 auto children = childrenOfType<Element>(rootNode);
141 auto end = children.end();
142 ElementChildIterator<Element> last(rootNode, children.last());
143 for (auto it = last; it != end; --it) {
144 if (collection.elementMatches(*it))
145 return it;
146 }
147 return end;
148}
149
150template <typename CollectionClass>
151inline Element* CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::last(const CollectionClass&, ContainerNode&)
152{
153 ASSERT_NOT_REACHED();
154 return nullptr;
155}
156
157template <typename CollectionClass>
158inline void CollectionTraversal<CollectionTraversalType::Descendants>::traverseForward(const CollectionClass& collection, ElementDescendantIterator& current, unsigned count, unsigned& traversedCount)
159{
160 ASSERT(collection.elementMatches(*current));
161 auto end = collection.collectionEnd();
162 for (traversedCount = 0; traversedCount < count; ++traversedCount) {
163 do {
164 ++current;
165 if (current == end)
166 return;
167 } while (!collection.elementMatches(*current));
168 }
169}
170
171template <typename CollectionClass>
172inline void CollectionTraversal<CollectionTraversalType::ChildrenOnly>::traverseForward(const CollectionClass& collection, ElementChildIterator<Element>& current, unsigned count, unsigned& traversedCount)
173{
174 ASSERT(collection.elementMatches(*current));
175 auto end = collection.collectionEnd();
176 for (traversedCount = 0; traversedCount < count; ++traversedCount) {
177 do {
178 ++current;
179 if (current == end)
180 return;
181 } while (!collection.elementMatches(*current));
182 }
183}
184
185template <typename CollectionClass>
186inline void CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::traverseForward(const CollectionClass& collection, Element*& current, unsigned count, unsigned& traversedCount)
187{
188 Element* element = current;
189 for (traversedCount = 0; traversedCount < count; ++traversedCount) {
190 element = collection.customElementAfter(element);
191 if (!element) {
192 current = nullptr;
193 return;
194 }
195 }
196 current = element;
197}
198
199template <typename CollectionClass>
200inline void CollectionTraversal<CollectionTraversalType::Descendants>::traverseBackward(const CollectionClass& collection, ElementDescendantIterator& current, unsigned count)
201{
202 ASSERT(collection.elementMatches(*current));
203 auto end = collection.collectionEnd();
204 for (; count; --count) {
205 do {
206 --current;
207 if (current == end)
208 return;
209 } while (!collection.elementMatches(*current));
210 }
211}
212
213template <typename CollectionClass>
214inline void CollectionTraversal<CollectionTraversalType::ChildrenOnly>::traverseBackward(const CollectionClass& collection, ElementChildIterator<Element>& current, unsigned count)
215{
216 ASSERT(collection.elementMatches(*current));
217 auto end = collection.collectionEnd();
218 for (; count; --count) {
219 do {
220 --current;
221 if (current == end)
222 return;
223 } while (!collection.elementMatches(*current));
224 }
225}
226
227template <typename CollectionClass>
228inline void CollectionTraversal<CollectionTraversalType::CustomForwardOnly>::traverseBackward(const CollectionClass&, Element*&, unsigned count)
229{
230 UNUSED_PARAM(count);
231 ASSERT_NOT_REACHED();
232}
233
234} // namespace WebCore
235
236#endif // CollectionTraversal_h