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;
}
}