001/*
002 * This file is part of McIDAS-V
003 *
004 * Copyright 2007-2015
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    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}.<br>
115     * The cursor can return {@code Cursor.SelectStatus.CONTINUE} to
116     * continue traversing.<br>
117     * {@code Cursor.SelectStatus.REMOVE_AND_EXIT} 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}
129     * will be called on each entry.<p>
130     * The traversal will stop when the cursor returns {@code Cursor.SelectStatus.EXIT}.<br>
131     * {@code Cursor.SelectStatus.CONTINUE} is used to continue traversing.<br>
132     * {@code Cursor.SelectStatus.REMOVE} is used to remove the element that was
133     * selected and continue traversing.<br>
134     * {@code Cursor.SelectStatus.REMOVE_AND_EXIT} 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}. 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}
147     * what to do next.
148     * <p>
149     * {@code Cursor} 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, edu.wisc.ssec.mcidasv.util.trie.Trie.Cursor)}
159     * does not support {@code REMOVE}.
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} to finish the Trie operation,
169         * {@code CONTINUE} to look at the next entry, {@code REMOVE}
170         * to remove the entry and continue iterating, or
171         * {@code REMOVE_AND_EXIT} to remove the entry and stop iterating.
172         * Not all operations support {@code REMOVE}.
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