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