pdfbox-trunk/pdfbox/src/main/java/org/apache/pdfbox/util/filetypedetector/ByteTrie.java
/*
 * 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.pdfbox.util.filetypedetector;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Drew Noakes
 *
 * code taken from https://github.com/drewnoakes/metadata-extractor
 *
 * 2016-01-04
 *
 * latest commit number 73f1a48
 *
 * Stores values using a prefix tree (aka 'trie', i.e. reTRIEval data structure).
 *
 * @param <T> the type of value to store for byte sequences
 */
class ByteTrie<T>
{
    /**
     * A node in the trie. Has children and may have an associated value.
     */
    static class ByteTrieNode<T>
    {
        private final Map<Byte, ByteTrieNode<T>> children = new HashMap<>();
        private T value = null;

        public void setValue(T value)
        {
            if (this.value != null)
            {
                throw new IllegalStateException("Value already set for this trie node");
            }
            this.value = value;
        }

        public T getValue()
        {
            return value;
        }
    }

    private final ByteTrieNode<T> root = new ByteTrieNode<>();
    private int maxDepth;

    /**
     * Return the most specific value stored for this byte sequence. If not found, returns
     * <code>null</code> or a default values as specified by calling
     * {@link ByteTrie#setDefaultValue}.
     * @param bytes
     * @return 
     */
    public T find(byte[] bytes)
    {
        ByteTrieNode<T> node = root;
        T val = node.getValue();
        for (byte b : bytes)
        {
            ByteTrieNode<T> child = node.children.get(b);
            if (child == null)
            {
                break;
            }
            node = child;
            if (node.getValue() != null)
            {
                val = node.getValue();
            }
        }
        return val;
    }

    /**
     * Store the given value at the specified path.
     * @param value
     * @param parts
     */
    public void addPath(T value, byte[]... parts)
    {
        int depth = 0;
        ByteTrieNode<T> node = root;
        for (byte[] part : parts)
        {
            for (byte b : part)
            {
                ByteTrieNode<T> child = node.children.get(b);
                if (child == null)
                {
                    child = new ByteTrieNode<>();
                    node.children.put(b, child);
                }
                node = child;
                depth++;
            }
        }
        node.setValue(value);
        maxDepth = Math.max(maxDepth, depth);
    }

    /**
     * Sets the default value to use in {@link ByteTrie#find(byte[])} when no path matches.
     * @param defaultValue
     */
    public void setDefaultValue(T defaultValue)
    {
        root.setValue(defaultValue);
    }

    /**
     * Gets the maximum depth stored in this trie.
     * @return 
     */
    public int getMaxDepth()
    {
        return maxDepth;
    }
}
