001 /*
002 * $Id: Trie.java,v 1.3 2012/02/19 17:35:52 davep Exp $
003 *
004 * This file is part of McIDAS-V
005 *
006 * Copyright 2007-2012
007 * Space Science and Engineering Center (SSEC)
008 * University of Wisconsin - Madison
009 * 1225 W. Dayton Street, Madison, WI 53706, USA
010 * https://www.ssec.wisc.edu/mcidas
011 *
012 * All Rights Reserved
013 *
014 * McIDAS-V is built on Unidata's IDV and SSEC's VisAD libraries, and
015 * some McIDAS-V source code is based on IDV and VisAD source code.
016 *
017 * McIDAS-V is free software; you can redistribute it and/or modify
018 * it under the terms of the GNU Lesser Public License as published by
019 * the Free Software Foundation; either version 3 of the License, or
020 * (at your option) any later version.
021 *
022 * McIDAS-V is distributed in the hope that it will be useful,
023 * but WITHOUT ANY WARRANTY; without even the implied warranty of
024 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
025 * GNU Lesser Public License for more details.
026 *
027 * You should have received a copy of the GNU Lesser Public License
028 * along with this program. If not, see http://www.gnu.org/licenses.
029 */
030 package edu.wisc.ssec.mcidasv.util.trie;
031
032 import java.util.Map;
033 import java.util.SortedMap;
034
035 /**
036 * Defines the interface for a prefix tree, an ordered tree data structure. For
037 * more information, see <a href= "http://en.wikipedia.org/wiki/Trie">Tries</a>.
038 *
039 * @author Roger Kapsi
040 * @author Sam Berlin
041 */
042 public interface Trie<K, V> extends SortedMap<K, V> {
043
044 /**
045 * Returns a view of this Trie of all elements that are
046 * prefixed by the given key.
047 * <p>
048 * In a fixed-keysize Trie, this is essentially a 'get' operation.
049 * <p>
050 * For example, if the Trie contains 'Lime', 'LimeWire',
051 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
052 * a lookup of 'Lime' would return 'Lime', 'LimeRadio', and 'LimeWire'.
053 */
054 public SortedMap<K, V> getPrefixedBy(K key);
055
056 /**
057 * Returns a view of this Trie of all elements that are
058 * prefixed by the length of the key.
059 * <p>
060 * Fixed-keysize Tries will not support this operation
061 * (because all keys will be the same length).
062 * <p>
063 * For example, if the Trie contains 'Lime', 'LimeWire',
064 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
065 * a lookup of 'LimePlastics' with a length of 4 would
066 * return 'Lime', 'LimeRadio', and 'LimeWire'.
067 */
068 public SortedMap<K, V> getPrefixedBy(K key, int length);
069
070 /**
071 * Returns a view of this Trie of all elements that are prefixed
072 * by the key, starting at the given offset and for the given length.
073 * <p>
074 * Fixed-keysize Tries will not support this operation
075 * (because all keys are the same length).
076 * <p>
077 * For example, if the Trie contains 'Lime', 'LimeWire',
078 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
079 * a lookup of 'The Lime Plastics' with an offset of 4 and a
080 * length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'.
081 */
082 public SortedMap<K, V> getPrefixedBy(K key, int offset, int length);
083
084 /**
085 * Returns a view of this Trie of all elements that are prefixed
086 * by the number of bits in the given Key.
087 * <p>
088 * Fixed-keysize Tries can support this operation as a way to do
089 * lookups of partial keys. That is, if the Trie is storing IP
090 * addresses, you can lookup all addresses that begin with
091 * '192.168' by providing the key '192.168.X.X' and a length of 16
092 * would return all addresses that begin with '192.168'.
093 */
094 public SortedMap<K, V> getPrefixedByBits(K key, int bitLength);
095
096 /**
097 * Returns the value for the entry whose key is closest in a bitwise
098 * XOR metric to the given key. This is NOT lexicographic closeness.
099 * For example, given the keys:<br>
100 * D = 1000100 <br>
101 * H = 1001000 <br>
102 * L = 1001100 <br>
103 * <p>
104 * If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L',
105 * because the XOR distance between D & L is smaller than the XOR distance
106 * between D & H.
107 */
108 public V select(K key);
109
110 /**
111 * Iterates through the Trie, starting with the entry whose bitwise
112 * value is closest in an XOR metric to the given key. After the closest
113 * entry is found, the Trie will call select on that entry and continue
114 * calling select for each entry (traversing in order of XOR closeness,
115 * NOT lexicographically) until the cursor returns
116 * <code>Cursor.SelectStatus.EXIT</code>.<br>
117 * The cursor can return <code>Cursor.SelectStatus.CONTINUE</code> to
118 * continue traversing.<br>
119 * <code>Cursor.SelectStatus.REMOVE_AND_EXIT</code> is used to remove the current element
120 * and stop traversing.
121 * <p>
122 * Note: The {@link Cursor.SelectStatus#REMOVE} operation is not supported.
123 *
124 * @return The entry the cursor returned EXIT on, or null if it continued
125 * till the end.
126 */
127 public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor);
128
129 /**
130 * Traverses the Trie in lexicographical order. <code>Cursor.select</code>
131 * will be called on each entry.<p>
132 * The traversal will stop when the cursor returns <code>Cursor.SelectStatus.EXIT</code>.<br>
133 * <code>Cursor.SelectStatus.CONTINUE</code> is used to continue traversing.<br>
134 * <code>Cursor.SelectStatus.REMOVE</code> is used to remove the element that was
135 * selected and continue traversing.<br>
136 * <code>Cursor.SelectStatus.REMOVE_AND_EXIT</code> is used to remove the current element
137 * and stop traversing.
138 *
139 * @return The entry the cursor returned EXIT on, or null if it continued
140 * till the end.
141 */
142 public Map.Entry<K,V> traverse(Cursor<? super K, ? super V> cursor);
143
144 /**
145 * An interface used by a {@link Trie}. A {@link Trie} selects items by
146 * closeness and passes the items to the <code>Cursor</code>. You can then
147 * decide what to do with the key-value pair and the return value
148 * from {@link #select(java.util.Map.Entry)} tells the <code>Trie</code>
149 * what to do next.
150 * <p>
151 * <code>Cursor</code> returns status/selection status might be:
152 * <table cellspace="5">
153 * <tr><td><b>Return Value</b></td><td><b>Status</b></td></tr>
154 * <tr><td>EXIT</td><td>Finish the Trie operation</td></tr>
155 * <tr><td>CONTINUE</td><td>Look at the next element in the traversal</td></tr>
156 * <tr><td>REMOVE_AND_EXIT</td><td>Remove the entry and stop iterating</td></tr>
157 * <tr><td>REMOVE</td><td>Remove the entry and continue iterating</td></tr>
158 * </table>
159
160 * Note: {@link Trie#select(Object, org.limewire.collection.Trie.Cursor)} does
161 * not support <code>REMOVE</code>.
162 *
163 * @param <K> Key Type
164 * @param <V> Key Value
165 */
166 public static interface Cursor<K, V> {
167
168 /**
169 * Notification that the Trie is currently looking at the given entry.
170 * Return <code>EXIT</code> to finish the Trie operation,
171 * <code>CONTINUE</code> to look at the next entry, <code>REMOVE</code>
172 * to remove the entry and continue iterating, or
173 * <code>REMOVE_AND_EXIT</code> to remove the entry and stop iterating.
174 * Not all operations support <code>REMOVE</code>.
175 *
176 */
177 public SelectStatus select(Map.Entry<? extends K, ? extends V> entry);
178
179 /** The mode during selection. */
180 public static enum SelectStatus {
181 EXIT, CONTINUE, REMOVE, REMOVE_AND_EXIT;
182 }
183 }
184 }
185