1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 package org.apache.commons.collections4.trie; 18 19 import java.util.Map; 20 21 import org.apache.commons.collections4.trie.analyzer.StringKeyAnalyzer; 22 23 /** 24 * Implements a PATRICIA Trie (Practical Algorithm to Retrieve Information 25 * Coded in Alphanumeric). 26 * <p> 27 * A PATRICIA {@link org.apache.commons.collections4.Trie} is a compressed 28 * {@link org.apache.commons.collections4.Trie}. Instead of storing 29 * all data at the edges of the {@link org.apache.commons.collections4.Trie} 30 * (and having empty internal nodes), PATRICIA stores data in every node. 31 * This allows for very efficient traversal, insert, delete, predecessor, 32 * successor, prefix, range, and {@link #select(Object)} 33 * operations. All operations are performed at worst in O(K) time, where K 34 * is the number of bits in the largest item in the tree. In practice, 35 * operations actually take O(A(K)) time, where A(K) is the average number of 36 * bits of all items in the tree. 37 * </p> 38 * <p> 39 * Most importantly, PATRICIA requires very few comparisons to keys while 40 * doing any operation. While performing a lookup, each comparison (at most 41 * K of them, described above) will perform a single bit comparison against 42 * the given key, instead of comparing the entire key to another key. 43 * </p> 44 * <p> 45 * The {@link org.apache.commons.collections4.Trie} can return operations in 46 * lexicographical order using the 'prefixMap', 'submap', or 'iterator' methods. 47 * The {@link org.apache.commons.collections4.Trie} can also 48 * scan for items that are 'bitwise' (using an XOR metric) by the 'select' method. 49 * Bitwise closeness is determined by the {@link KeyAnalyzer} returning true or 50 * false for a bit being set or not in a given key. 51 * </p> 52 * <p> 53 * This PATRICIA {@link org.apache.commons.collections4.Trie} supports both variable 54 * length & fixed length keys. Some methods, such as {@link org.apache.commons.collections4.Trie#prefixMap(Object)} 55 * are suited only to variable length keys. 56 * </p> 57 * 58 * @param <V> the type of the values in this map 59 * @see <a href="https://en.wikipedia.org/wiki/Radix_tree">Radix Tree</a> 60 * @see <a href="https://users.monash.edu/~lloyd/tildeAlgDS/Tree/PATRICIA/">PATRICIA</a> 61 * @see <a href="https://www.imperialviolet.org/binary/critbit.pdf">Crit-Bit Tree</a> 62 * @since 4.0 63 */ 64 public class PatriciaTrie<V> extends AbstractPatriciaTrie<String, V> { 65 66 private static final long serialVersionUID = 4446367780901817838L; 67 68 /** 69 * Constructs a new instance. 70 */ 71 public PatriciaTrie() { 72 super(StringKeyAnalyzer.INSTANCE); 73 } 74 75 /** 76 * Constructs a new instance. 77 * 78 * @param map mappings to be stored in this map. 79 */ 80 public PatriciaTrie(final Map<? extends String, ? extends V> map) { 81 super(StringKeyAnalyzer.INSTANCE, map); 82 } 83 84 }