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}