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