001/*
002 * This file is part of McIDAS-V
003 *
004 * Copyright 2007-2016
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 */
028package edu.wisc.ssec.mcidasv.util.trie;
029
030import java.util.Map;
031import 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 */
040public 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     * @param key Key to search for within the trie.
053     *
054     * @return {@code Map} containing keys matching the given prefix and their
055     * values.
056     */
057    SortedMap<K, V> getPrefixedBy(K key);
058    
059    /**
060     * Returns a view of this Trie of all elements that are
061     * prefixed by the length of the key.
062     * <p>
063     * Fixed-keysize Tries will not support this operation
064     * (because all keys will be the same length).
065     * <p>
066     * For example, if the Trie contains 'Lime', 'LimeWire', 
067     * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
068     * a lookup of 'LimePlastics' with a length of 4 would
069     * return 'Lime', 'LimeRadio', and 'LimeWire'.
070     *
071     * @param key Key to search for within the trie.
072     * @param length Length of {@code key}. Ignored for tries with a fixed key
073     *               size.
074     *
075     * @return {@code Map} containing keys matching the given prefix and their
076     * values.
077     */
078    SortedMap<K, V> getPrefixedBy(K key, int length);
079    
080    /**
081     * Returns a view of this Trie of all elements that are prefixed
082     * by the key, starting at the given offset and for the given length.
083     * <p>
084     * Fixed-keysize Tries will not support this operation
085     * (because all keys are the same length).
086     * <p>
087     * For example, if the Trie contains 'Lime', 'LimeWire', 
088     * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
089     * a lookup of 'The Lime Plastics' with an offset of 4 and a 
090     * length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'.
091     *
092     * @param key Key to search for within the trie.
093     * @param offset Offset to begin search at.
094     * @param length Length of {@code key}. Ignored for tries with a fixed key
095     *               size.
096     *
097     * @return {@code Map} containing keys matching the given prefix and their
098     * values.
099     */
100    SortedMap<K, V> getPrefixedBy(K key, int offset, int length);
101    
102    /**
103     * Returns a view of this Trie of all elements that are prefixed
104     * by the number of bits in the given Key.
105     * <p>
106     * Fixed-keysize Tries can support this operation as a way to do
107     * lookups of partial keys.  That is, if the Trie is storing IP
108     * addresses, you can lookup all addresses that begin with
109     * '192.168' by providing the key '192.168.X.X' and a length of 16
110     * would return all addresses that begin with '192.168'.
111     *
112     * @param key Key to search for within the trie.
113     * @param bitLength Length of {@code key} in bits.
114     *
115     * @return {@code Map} containing keys matching the given prefix and their
116     * values.
117     */
118    SortedMap<K, V> getPrefixedByBits(K key, int bitLength);
119    
120    /**
121     * Returns the value for the entry whose key is closest in a bitwise
122     * XOR metric to the given key.  This is NOT lexicographic closeness.
123     * For example, given the keys:<br>
124     *  D = 1000100 <br>
125     *  H = 1001000 <br> 
126     *  L = 1001100 <br>
127     * <p>
128     * If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L',
129     * because the XOR distance between D and L is smaller than the XOR distance
130     * between D and H.
131     *
132     * @param key Key to search for within the trie.
133     *
134     * @return Value associated with {@code key}.
135     */
136    V select(K key);
137    
138    /**
139     * Iterates through the Trie, starting with the entry whose bitwise
140     * value is closest in an XOR metric to the given key.  After the closest
141     * entry is found, the Trie will call select on that entry and continue
142     * calling select for each entry (traversing in order of XOR closeness,
143     * NOT lexicographically) until the cursor returns 
144     * {@code Cursor.SelectStatus.EXIT}.<br>
145     * The cursor can return {@code Cursor.SelectStatus.CONTINUE} to
146     * continue traversing.<br>
147     * {@code Cursor.SelectStatus.REMOVE_AND_EXIT} is used to remove the current element
148     * and stop traversing.
149     * <p>
150     * Note: The {@link Cursor.SelectStatus#REMOVE} operation is not supported.
151     *
152     * @param key Key to match.
153     * @param cursor Cursor being used to traverse the trie.
154     *
155     * @return The entry the cursor returned EXIT on, or null if it continued
156     *         till the end.
157     */
158    Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor);
159    
160    /**
161     * Traverses the Trie in lexicographical order. {@code Cursor.select}
162     * will be called on each entry.<p>
163     * The traversal will stop when the cursor returns {@code Cursor.SelectStatus.EXIT}.<br>
164     * {@code Cursor.SelectStatus.CONTINUE} is used to continue traversing.<br>
165     * {@code Cursor.SelectStatus.REMOVE} is used to remove the element that was
166     * selected and continue traversing.<br>
167     * {@code Cursor.SelectStatus.REMOVE_AND_EXIT} is used to remove the current element
168     * and stop traversing.
169     *
170     * @param cursor Cursor being used to traverse the trie.
171     *   
172     * @return The entry the cursor returned EXIT on, or null if it continued
173     *         till the end.
174     */
175    Map.Entry<K,V> traverse(Cursor<? super K, ? super V> cursor);
176    
177    /**
178     * An interface used by a {@link Trie}. A {@link Trie} selects items by 
179     * closeness and passes the items to the {@code Cursor}. You can then
180     * decide what to do with the key-value pair and the return value 
181     * from {@link #select(java.util.Map.Entry)} tells the {@code Trie}
182     * what to do next.
183     * <p>
184     * {@code Cursor} returns status/selection status might be:
185     * <table summary="The various Cursor status values">
186     * <tr><td><b>Return Value</b></td><td><b>Status</b></td></tr>
187     * <tr><td>EXIT</td><td>Finish the Trie operation</td></tr>
188     * <tr><td>CONTINUE</td><td>Look at the next element in the traversal</td></tr>
189     * <tr><td>REMOVE_AND_EXIT</td><td>Remove the entry and stop iterating</td></tr>
190     * <tr><td>REMOVE</td><td>Remove the entry and continue iterating</td></tr>
191     * </table>
192
193     * Note: {@link Trie#select(Object, edu.wisc.ssec.mcidasv.util.trie.Trie.Cursor)}
194     * does not support {@code REMOVE}.
195     *
196     * @param <K> Key Type
197     * @param <V> Key Value
198     */
199    interface Cursor<K, V> {
200        
201        /**
202         * Notification that the Trie is currently looking at the given entry.
203         * Return {@code EXIT} to finish the Trie operation,
204         * {@code CONTINUE} to look at the next entry, {@code REMOVE}
205         * to remove the entry and continue iterating, or
206         * {@code REMOVE_AND_EXIT} to remove the entry and stop iterating.
207         * Not all operations support {@code REMOVE}.
208         *
209         * @param entry Entry that will be operated upon.
210         *
211         * @return Status of cursor after trie operation.
212         */
213        SelectStatus select(Map.Entry<? extends K, ? extends V> entry);
214     
215        /** The mode during selection. */
216        enum SelectStatus { EXIT, CONTINUE, REMOVE, REMOVE_AND_EXIT }
217    }
218}
219