1 /* 2 * Copyright (C) 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.android.libcore.timezone.tzlookup.zonetree; 17 18 import java.util.ArrayList; 19 import java.util.List; 20 21 /** 22 * An abstract base class for a general tree node. Each tree node has an id, a link to its parent 23 * and zero or more child nodes. 24 * 25 * @param <V> the type of the TreeNode subclass 26 */ 27 abstract class TreeNode<V extends TreeNode<V>> { 28 29 private V parent; 30 private final String id; 31 private final List<V> children = new ArrayList<>(); 32 TreeNode(String id)33 public TreeNode(String id) { 34 this.id = id; 35 } 36 getId()37 public final String getId() { 38 return id; 39 } 40 41 @SuppressWarnings("unchecked") getThis()42 protected final V getThis() { 43 return (V) this; 44 } 45 getParent()46 public final V getParent() { 47 return parent; 48 } 49 50 /** For use by {@link #addChild(TreeNode)} and {@link #removeChild(TreeNode)} only. */ setParent(V newParent)51 protected final void setParent(V newParent) { 52 parent = newParent; 53 } 54 55 /** 56 * Adds the child and sets the parent of the child. The child must not already have a parent. 57 */ addChild(V e)58 public final void addChild(V e) { 59 if (e.getParent() != null) { 60 throw new IllegalStateException("Node already attached"); 61 } 62 children.add(e); 63 e.setParent(getThis()); 64 } 65 getChildren()66 public final List<V> getChildren() { 67 return new ArrayList<>(children); 68 } 69 getChildrenCount()70 public final int getChildrenCount() { 71 return children.size(); 72 } 73 74 /** 75 * Recursively visit this node and then all children. 76 */ visitSelfThenChildrenRecursive(Visitor<V> visitor)77 public final void visitSelfThenChildrenRecursive(Visitor<V> visitor) { 78 visitor.visit(getThis()); 79 for (V child : getChildren()) { 80 child.visitSelfThenChildrenRecursive(visitor); 81 } 82 } 83 84 /** 85 * Remove a single child. {@link Object#equals(Object)} is used to 86 * identify the child node to remove. The parent of the node to be removed is set to null. 87 * 88 * <p>Returns the node removed, or {@code null} if the node could not be removed. 89 */ removeChild(V toRemove)90 public final V removeChild(V toRemove) { 91 for (int i = 0; i < children.size(); i++) { 92 V candidate = children.get(i); 93 if (toRemove.equals(candidate)) { 94 toRemove.setParent(null); 95 children.remove(i); 96 return toRemove; 97 } 98 } 99 return null; 100 } 101 isRoot()102 public final boolean isRoot() { 103 return getParent() == null; 104 } 105 isLeaf()106 public final boolean isLeaf() { 107 return getChildrenCount() == 0; 108 } 109 110 /** 111 * A visitor of {@link TreeNode}. 112 * @param <N> the type of tree node 113 */ 114 public interface Visitor<N extends TreeNode<N>> { visit(N node)115 void visit(N node); 116 } 117 } 118