001/*
002 * This library is part of OpenCms -
003 * the Open Source Content Management System
004 *
005 * Copyright (c) Alkacon Software GmbH & Co. KG (http://www.alkacon.com)
006 *
007 * This library is free software; you can redistribute it and/or
008 * modify it under the terms of the GNU Lesser General Public
009 * License as published by the Free Software Foundation; either
010 * version 2.1 of the License, or (at your option) any later version.
011 *
012 * This library is distributed in the hope that it will be useful,
013 * but WITHOUT ANY WARRANTY; without even the implied warranty of
014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 * Lesser General Public License for more details.
016 *
017 * For further information about Alkacon Software, please see the
018 * company website: http://www.alkacon.com
019 *
020 * For further information about OpenCms, please see the
021 * project website: http://www.opencms.org
022 *
023 * You should have received a copy of the GNU Lesser General Public
024 * License along with this library; if not, write to the Free Software
025 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
026 */
027
028package org.opencms.util;
029
030import java.util.Collection;
031import java.util.Collections;
032import java.util.Iterator;
033import java.util.List;
034import java.util.Map;
035
036import com.google.common.collect.Lists;
037import com.google.common.collect.Maps;
038
039/**
040 * Tree used to represent file system like data structures.<p>
041 *
042 * A tree consists of a (possibly empty) value and a map from child names to subtrees.<p>
043 *
044 * @param <P> the type of path components
045 * @param <V> the element type stored in the tree
046 *
047 */
048public class CmsPathTree<P, V> {
049
050    /** The map from child names to children. */
051    private Map<P, CmsPathTree<P, V>> m_children = Maps.newHashMap();
052
053    /** The value (may be null). */
054    private V m_value;
055
056    /**
057     * Collect all descendant  values in the given collection.<p>
058     *
059     * @param target the collection in which to store the descendant values
060     */
061    public void collectEntries(Collection<V> target) {
062
063        if (m_value != null) {
064            target.add(m_value);
065        }
066        for (CmsPathTree<P, V> child : m_children.values()) {
067            child.collectEntries(target);
068        }
069    }
070
071    /**
072     * Finds the node for the given path, and returns it or null if node was found.<p>
073     *
074     * @param path the path
075     * @return the node for the path
076     */
077    public CmsPathTree<P, V> findNode(List<P> path) {
078
079        List<P> pathToConsume = Lists.newLinkedList(path);
080        CmsPathTree<P, V> descendant = findNodeInternal(pathToConsume);
081        if (!pathToConsume.isEmpty()) {
082            return null;
083        } else {
084            return descendant;
085        }
086    }
087
088    /**
089     * Gets the child for the given path component.<p>
090     *
091     * @param pathPart the path component
092     *
093     * @return the child for the given path component (may be null)
094     */
095    public CmsPathTree<P, V> getChild(P pathPart) {
096
097        return m_children.get(pathPart);
098    }
099
100    /**
101     * Returns the values for the direct children of this node.<p>
102     *
103     * @return the values for the direct children
104     */
105    public List<V> getChildValues() {
106
107        List<V> result = Lists.newArrayList();
108        for (CmsPathTree<P, V> child : m_children.values()) {
109            if (child.m_value != null) {
110                result.add(child.m_value);
111            }
112        }
113        return result;
114    }
115
116    /**
117     * Gets the child values for the given path.<p>
118     *
119     * @param path the path
120     *
121     * @return the child values
122     */
123    public List<V> getChildValues(List<P> path) {
124
125        CmsPathTree<P, V> descendant = findNode(path);
126        if (descendant != null) {
127            return descendant.getChildValues();
128        } else {
129            return Collections.emptyList();
130        }
131    }
132
133    /**
134     * Gets the descendant values.<p>
135     *
136     * @param path the path
137     * @return the descendant values
138     */
139    public List<V> getDescendantValues(List<P> path) {
140
141        CmsPathTree<P, V> node = findNode(path);
142        List<V> result = Lists.newArrayList();
143        if (node != null) {
144            node.collectEntries(result);
145        }
146        return result;
147    }
148
149    /**
150     * Gets the value for this node (may be null).<p>
151     *
152     * @return the value
153     */
154    public V getValue() {
155
156        return m_value;
157    }
158
159    /**
160     * Gets the value for the sub-path given, starting from this node.<p>
161     *
162     * @param path the path
163     * @return the value for the node
164     */
165    public V getValue(List<P> path) {
166
167        CmsPathTree<P, V> node = findNode(path);
168        if (node != null) {
169            return node.m_value;
170        } else {
171            return null;
172        }
173    }
174
175    /**
176     * Sets the value for the sub-path given, starting from this node.<p>
177     *
178     * @param path the  path
179     * @param value the value to set
180     */
181    public void setValue(List<P> path, V value) {
182
183        ensureNode(path).setValue(value);
184
185    }
186
187    /**
188     * Sets the value for this node.<p>
189     *
190     * @param value the value for the node
191     */
192    public void setValue(V value) {
193
194        m_value = value;
195    }
196
197    /**
198     * Returns the node for the given path, creating all nodes on the way if they don't already exist.<p>
199     *
200     * @param path the path for which to make sure a node exists
201     *
202     * @return the node for the path
203     */
204    private CmsPathTree<P, V> ensureNode(List<P> path) {
205
206        List<P> pathToConsume = Lists.newLinkedList(path);
207        CmsPathTree<P, V> lastExistingNode = findNodeInternal(pathToConsume);
208        CmsPathTree<P, V> currentNode = lastExistingNode;
209        for (P pathPart : pathToConsume) {
210            CmsPathTree<P, V> child = new CmsPathTree<P, V>();
211            currentNode.m_children.put(pathPart, child);
212            currentNode = child;
213        }
214        return currentNode;
215    }
216
217    /**
218     * Tries to traverse the descendants of this node along the given path,
219     * and returns the last existing node along that path.<p>
220     *
221     * The given path is modified so that only the part of the path for which no nodes can be found
222     * remains.<p>
223     *
224     * @param pathToConsume the path to find (will be modified by this method)
225     * @return the last node found along the descendant chain for the path
226     */
227    private CmsPathTree<P, V> findNodeInternal(List<P> pathToConsume) {
228
229        Iterator<P> iter = pathToConsume.iterator();
230        CmsPathTree<P, V> currentNode = this;
231        while (iter.hasNext()) {
232            CmsPathTree<P, V> child = currentNode.getChild(iter.next());
233            if (child != null) {
234                iter.remove();
235                currentNode = child;
236            } else {
237                return currentNode;
238            }
239        }
240        return currentNode;
241    }
242
243}