pathmap.java

jsr170接口的java实现。是个apache的开源项目。

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.jackrabbit.util;

import org.apache.jackrabbit.name.MalformedPathException;
import org.apache.jackrabbit.name.Path;
import org.apache.jackrabbit.name.QName;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Generic path map that associates information with the individual path elements
 * of a path.
 */
public class PathMap {

    /**
     * Root element
     */
    private final Element root = new Element(Path.ROOT.getNameElement());

    /**
     * Map a path to a child. If <code>exact</code> is <code>false</code>,
     * returns the last available item along the path that is stored in the map.
     * @param path path to map
     * @param exact flag indicating whether an exact match is required
     * @return child, maybe <code>null</code> if <code>exact</code> is
     *         <code>true</code>
     */
    public Element map(Path path, boolean exact) {
        Path.PathElement[] elements = path.getElements();
        Element current = root;

        for (int i = 1; i < elements.length; i++) {
            Element next = current.getChild(elements[i]);
            if (next == null) {
                if (exact) {
                    return null;
                }
                break;
            }
            current = next;
        }
        return current;
    }

    /**
     * Create an element given by its path. The path map will create any necessary
     * intermediate elements.
     * @param path path to child
     * @param obj object to store at destination
     */
    public Element put(Path path, Object obj) {
        Element element = put(path);
        element.obj = obj;
        return element;
    }

    /**
     * Put an element given by its path. The path map will create any necessary
     * intermediate elements.
     * @param path path to child
     * @param element element to store at destination
     */
    public void put(Path path, Element element) {
        Path.PathElement[] elements = path.getElements();
        Element current = root;

        for (int i = 1; i < elements.length - 1; i++) {
            Element next = current.getChild(elements[i]);
            if (next == null) {
                next = current.createChild(elements[i]);
            }
            current = next;
        }
        current.put(path.getNameElement(), element);
    }

    /**
     * Create an empty child given by its path.
     * @param path path to child
     */
    public Element put(Path path) {
        Path.PathElement[] elements = path.getElements();
        Element current = root;

        for (int i = 1; i < elements.length; i++) {
            Element next = current.getChild(elements[i]);
            if (next == null) {
                next = current.createChild(elements[i]);
            }
            current = next;
        }
        return current;
    }

    /**
     * Traverse the path map and call back requester. This method visits the root
     * first, then its children.
     * @param includeEmpty if <code>true</code> invoke call back on every child
     *                     regardless, whether the associated object is empty
     *                     or not; otherwise call back on non-empty children
     *                     only
     */
    public void traverse(ElementVisitor visitor, boolean includeEmpty) {
        root.traverse(visitor, includeEmpty);
    }

    /**
     * Internal class holding the object associated with a certain
     * path element.
     */
    public static class Element {

        /**
         * Parent element
         */
        private Element parent;

        /**
         * Map of immediate children
         */
        private Map children;

        /**
         * Number of non-empty children
         */
        private int childrenCount;

        /**
         * Object associated with this element
         */
        private Object obj;

        /**
         * QName associated with this element
         */
        private QName name;

        /**
         * 1-based index associated with this element where index=0 is
         * equivalent to index=1.
         */
        private int index;

        /**
         * Create a new instance of this class with a path element.
         * @param nameIndex path element of this child
         */
        private Element(Path.PathElement nameIndex) {
            this.name = nameIndex.getName();
            this.index = nameIndex.getIndex();
        }

        /**
         * Create a child of this node inside the path map.
         * @param nameIndex position where child is created
         * @return child
         */
        private Element createChild(Path.PathElement nameIndex) {
            Element element = new Element(nameIndex);
            put(nameIndex, element);
            return element;
        }

        /**
         * Insert an empty child. Will shift all children having an index
         * greater than or equal to the child inserted to the right.
         * @param nameIndex position where child is inserted
         */
        public void insert(Path.PathElement nameIndex) {
            // convert 1-based index value to 0-base value
            int index = getZeroBasedIndex(nameIndex);
            if (children != null) {
                ArrayList list = (ArrayList) children.get(nameIndex.getName());
                if (list != null && list.size() > index) {
                    for (int i = index; i < list.size(); i++) {
                        Element element = (Element) list.get(i);
                        if (element != null) {
                            element.index = element.getNormalizedIndex() + 1;
                        }
                    }
                    list.add(index, null);
                }
            }
        }

        /**
         * Return an element matching a name and index.
         * @param nameIndex position where child is located
         * @return element matching <code>nameIndex</code> or <code>null</code> if
         *         none exists.
         */
        private Element getChild(Path.PathElement nameIndex) {
            // convert 1-based index value to 0-base value
            int index = getZeroBasedIndex(nameIndex);
            Element element = null;

            if (children != null) {
                ArrayList list = (ArrayList) children.get(nameIndex.getName());
                if (list != null && list.size() > index) {
                    element = (Element) list.get(index);
                }
            }
            return element;
        }

        /**
         * Link a child of this node. Position is given by <code>nameIndex</code>.
         * @param nameIndex position where child should be located
         * @param element element to add
         */
        public void put(Path.PathElement nameIndex, Element element) {
            // convert 1-based index value to 0-base value
            int index = getZeroBasedIndex(nameIndex);
            if (children == null) {
                children = new HashMap();
            }
            ArrayList list = (ArrayList) children.get(nameIndex.getName());
            if (list == null) {
                list = new ArrayList();
                children.put(nameIndex.getName(), list);
            }
            while (list.size() < index) {
                list.add(null);
            }
            if (list.size() == index) {
                list.add(element);
            } else {
                list.set(index, element);
            }

            element.parent = this;
            element.name = nameIndex.getName();
            element.index = nameIndex.getIndex();

            childrenCount++;
        }

        /**
         * Remove a child. Will shift all children having an index greater than
         * the child removed to the left. If there are no more children left in
         * this element and no object is associated with this element, the
         * element itself gets removed.
         *
         * @param nameIndex child's path element
         * @return removed child, may be <code>null</code>
         */
        public Element remove(Path.PathElement nameIndex) {
            return remove(nameIndex, true, true);
        }

        /**
         * Remove a child. If <code>shift</code> is set to <code>true</code>,
         * will shift all children having an index greater than the child
         * removed to the left. If <code>removeIfEmpty</code> is set to
         * <code>true</code> and there are no more children left in
         * this element and no object is associated with this element, the
         * element itself gets removed.
         *
         * @param nameIndex child's path element
         * @param shift whether to shift same name siblings having a greater
         *              index to the left
         * @param removeIfEmpty remove this element itself if it contains
         *                      no more children and is not associated to
         *                      an element
         * @return removed child, may be <code>null</code>
         */
        private Element remove(Path.PathElement nameIndex, boolean shift,
                               boolean removeIfEmpty) {

            // convert 1-based index value to 0-base value
            int index = getZeroBasedIndex(nameIndex);
            if (children == null) {
                return null;
            }
            ArrayList list = (ArrayList) children.get(nameIndex.getName());
            if (list == null || list.size() <= index) {
                return null;
            }
            Element element = (Element) list.set(index, null);
            if (shift) {
                for (int i = index + 1; i < list.size(); i++) {
                    Element sibling = (Element) list.get(i);
                    if (sibling != null) {
                        sibling.index--;
                    }
                }
                list.remove(index);
            }
            if (element != null) {
                element.parent = null;
                childrenCount--;
            }
            if (removeIfEmpty && childrenCount == 0 && obj == null && parent != null) {
                parent.remove(getPathElement(), shift, true);
            }
            return element;
        }

        /**
         * Remove this element. Delegates the call to the parent item.
         * Index of same name siblings will be shifted!