001/*
002 * Configurate
003 * Copyright (C) zml and Configurate contributors
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 *    http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package ninja.leaping.configurate.util;
018
019import com.google.common.collect.AbstractIterator;
020import com.google.common.collect.Iterators;
021import ninja.leaping.configurate.ConfigurationNode;
022import ninja.leaping.configurate.transformation.NodePath;
023import org.checkerframework.checker.nullness.qual.NonNull;
024
025import java.util.ArrayDeque;
026import java.util.Arrays;
027import java.util.Collections;
028import java.util.Deque;
029import java.util.Iterator;
030import java.util.Objects;
031import java.util.Queue;
032import java.util.function.BiConsumer;
033
034/**
035 * Represents a method for "walking" or traversing a {@link ConfigurationNode configuration}
036 * structure.
037 *
038 * @deprecated Use ScopedConfigurationNode#visit(ConfigurationVisitor) instead
039 */
040@Deprecated
041public abstract class ConfigurationNodeWalker {
042
043    /**
044     * A {@link ConfigurationNodeWalker} that implements a breadth-first traversal over
045     * the configuration.
046     *
047     * <p>See <a href="https://en.wikipedia.org/wiki/Breadth-first_search">here</a> for more
048     * info.
049     */
050    public static final ConfigurationNodeWalker BREADTH_FIRST = new ConfigurationNodeWalker() {
051        @NonNull
052        @Override
053        public <T extends ConfigurationNode> Iterator<VisitedNode<T>> walkWithPath(@NonNull T start) {
054            return new BreadthFirstIterator<>(start);
055        }
056    };
057
058    /**
059     * A {@link ConfigurationNodeWalker} that implements a depth-first pre-order traversal over
060     * the configuration.
061     *
062     * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">here</a> for more
063     * info.
064     */
065    public static final ConfigurationNodeWalker DEPTH_FIRST_PRE_ORDER = new ConfigurationNodeWalker() {
066        @NonNull
067        @Override
068        public <T extends ConfigurationNode> Iterator<VisitedNode<T>> walkWithPath(@NonNull T start) {
069            return new DepthFirstPreOrderIterator<>(start);
070        }
071    };
072
073    /**
074     * A {@link ConfigurationNodeWalker} that implements a depth-first post-order traversal over
075     * the configuration.
076     *
077     * <p>See <a href="https://en.wikipedia.org/wiki/Depth-first_search">here</a> for more
078     * info.
079     */
080    public static final ConfigurationNodeWalker DEPTH_FIRST_POST_ORDER = new ConfigurationNodeWalker() {
081        @NonNull
082        @Override
083        public <T extends ConfigurationNode> Iterator<VisitedNode<T>> walkWithPath(@NonNull T start) {
084            return new DepthFirstPostOrderIterator<>(start);
085        }
086    };
087
088    /**
089     * Returns an iterator which will iterate over all paths and nodes in the
090     * configuration, in the order defined by the walker.
091     *
092     * @param start The node to start at
093     * @param <T> The node type
094     * @return An iterator of {@link VisitedNode}s
095     */
096    @NonNull
097    public abstract <T extends ConfigurationNode> Iterator<VisitedNode<T>> walkWithPath(@NonNull T start);
098
099
100    /**
101     * Returns an iterator which will iterate over all nodes in the
102     * configuration, in the order defined by the walker.
103     *
104     * @param start The node to start at
105     * @param <T> The node type
106     * @return An iterator of {@link ConfigurationNode}s
107     */
108    @NonNull
109    public <T extends ConfigurationNode> Iterator<T> walk(@NonNull T start) {
110        return Iterators.transform(walkWithPath(start), VisitedNode::getNode);
111    }
112
113    /**
114     * Walks the configuration, and calls the {@code consumer} for each path and node
115     * visited, in the order defined by the walker.
116     *
117     * @param start The node to start at
118     * @param consumer The consumer to accept the visited nodes
119     * @param <T> The node type
120     */
121    public <T extends ConfigurationNode> void walk(@NonNull T start, @NonNull BiConsumer<? super NodePath, ? super T> consumer) {
122        Iterator<VisitedNode<T>> it = walkWithPath(start);
123        while (it.hasNext()) {
124            VisitedNode<T> next = it.next();
125            consumer.accept(next.getPath(), next.getNode());
126        }
127    }
128
129    /**
130     * Encapsulates a given {@link ConfigurationNode node} visited during a
131     * traversal.
132     *
133     * @param <T> The node type
134     */
135    public interface VisitedNode<T extends ConfigurationNode> {
136
137        /**
138         * Gets the node that was visited.
139         *
140         * @return The visited node
141         */
142        @NonNull
143        T getNode();
144
145        /**
146         * Gets the path of the node that was visited.
147         *
148         * <p>Equivalent to calling {@link ConfigurationNode#getPath()} - except
149         * this method is likely to be more more efficient.</p>
150         *
151         * @return The path of the visited node
152         */
153        @NonNull
154        NodePath getPath();
155
156    }
157
158    private static Object[] calculatePath(Object[] path, Object childKey) {
159        if (path.length == 1 && path[0] == null) {
160            return new Object[]{childKey};
161        }
162
163        Object[] childPath = Arrays.copyOf(path, path.length + 1);
164        childPath[childPath.length - 1] = childKey;
165
166        return childPath;
167    }
168
169    private static <T extends ConfigurationNode> Iterator<VisitedNodeImpl<T>> getChildren(VisitedNodeImpl<T> from) {
170        T node = from.getNode();
171        switch (node.getValueType()) {
172            case LIST: {
173                Object[] path = from.getRawPath();
174                return Iterators.transform(node.getChildrenList().iterator(), child -> {
175                    Objects.requireNonNull(child);
176
177                    @SuppressWarnings("unchecked")
178                    T castedChild = ((T) child);
179                    Object[] childPath = calculatePath(path, child.getKey());
180
181                    return new VisitedNodeImpl<>(childPath, castedChild);
182                });
183            }
184            case MAP: {
185                Object[] path = from.getRawPath();
186                return Iterators.transform(node.getChildrenMap().entrySet().iterator(), child -> {
187                    Objects.requireNonNull(child);
188
189                    @SuppressWarnings("unchecked")
190                    T castedChild = ((T) child.getValue());
191                    Object[] childPath = calculatePath(path, child.getKey());
192
193                    return new VisitedNodeImpl<>(childPath, castedChild);
194                });
195            }
196            default:
197                return Collections.emptyIterator();
198        }
199    }
200
201    private static final class BreadthFirstIterator<N extends ConfigurationNode> implements Iterator<VisitedNode<N>> {
202        private final Queue<VisitedNodeImpl<N>> queue = new ArrayDeque<>();
203
204        BreadthFirstIterator(N root) {
205            this.queue.add(new VisitedNodeImpl<>(root.getPath(), root));
206        }
207
208        @Override
209        public boolean hasNext() {
210            return !this.queue.isEmpty();
211        }
212
213        @Override
214        public VisitedNode<N> next() {
215            VisitedNodeImpl<N> current = this.queue.remove();
216            Iterators.addAll(this.queue, getChildren(current));
217            return current;
218        }
219    }
220
221    private static final class DepthFirstPreOrderIterator<N extends ConfigurationNode> implements Iterator<VisitedNode<N>> {
222        private final Deque<Iterator<VisitedNodeImpl<N>>> stack = new ArrayDeque<>();
223
224        DepthFirstPreOrderIterator(N root) {
225            this.stack.push(Iterators.singletonIterator(new VisitedNodeImpl<>(root.getPath(), root)));
226        }
227
228        @Override
229        public boolean hasNext() {
230            return !this.stack.isEmpty();
231        }
232
233        @Override
234        public VisitedNode<N> next() {
235            Iterator<VisitedNodeImpl<N>> iterator = this.stack.getLast();
236            VisitedNodeImpl<N> result = iterator.next();
237            if (!iterator.hasNext()) {
238                this.stack.removeLast();
239            }
240            Iterator<VisitedNodeImpl<N>> childIterator = getChildren(result);
241            if (childIterator.hasNext()) {
242                this.stack.addLast(childIterator);
243            }
244            return result;
245        }
246    }
247
248    private static final class DepthFirstPostOrderIterator<N extends ConfigurationNode> extends AbstractIterator<VisitedNode<N>> {
249        private final ArrayDeque<NodeAndChildren> stack = new ArrayDeque<>();
250
251        DepthFirstPostOrderIterator(N root) {
252            this.stack.addLast(new NodeAndChildren(null, Iterators.singletonIterator(new VisitedNodeImpl<>(root.getPath(), root))));
253        }
254
255        @Override
256        protected VisitedNode<N> computeNext() {
257            while (!this.stack.isEmpty()) {
258                NodeAndChildren tail = this.stack.getLast();
259                if (tail.children.hasNext()) {
260                    VisitedNodeImpl<N> child = tail.children.next();
261                    this.stack.addLast(new NodeAndChildren(child, getChildren(child)));
262                } else {
263                    this.stack.removeLast();
264                    if (tail.node != null) {
265                        return tail.node;
266                    }
267                }
268            }
269            return endOfData();
270        }
271
272        private final class NodeAndChildren {
273            final VisitedNodeImpl<N> node;
274            final Iterator<VisitedNodeImpl<N>> children;
275
276            NodeAndChildren(VisitedNodeImpl<N> node, Iterator<VisitedNodeImpl<N>> children) {
277                this.node = node;
278                this.children = children;
279            }
280        }
281    }
282
283    private static final class VisitedNodeImpl<T extends ConfigurationNode> implements VisitedNode<T>, NodePath {
284        private final Object[] path;
285        private final T node;
286
287        VisitedNodeImpl(Object[] path, T node) {
288            this.path = path;
289            this.node = node;
290        }
291
292        Object[] getRawPath() {
293            return this.path;
294        }
295
296        // implement VisitedNode
297
298        @NonNull
299        public T getNode() {
300            return this.node;
301        }
302
303        @NonNull
304        @Override
305        public NodePath getPath() {
306            return this;
307        }
308
309        // implement NodePath
310
311        @Override
312        public Object get(int i) {
313            return this.path[i];
314        }
315
316        @Override
317        public int size() {
318            return this.path.length;
319        }
320
321        @Override
322        public Object[] getArray() {
323            return Arrays.copyOf(this.path, this.path.length);
324        }
325
326        @NonNull
327        @Override
328        public Iterator<Object> iterator() {
329            return Iterators.forArray(this.path);
330        }
331    }
332
333}