1 /* Taken 2008 from Limewire -project under the following terms:
2 *
3 * This program is free software: you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation, either version 3 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 */
16 package net.sf.eos.trie;
17
18 import java.util.Map;
19 import java.util.SortedMap;
20
21 /**
22 * Defines the interface for a prefix tree, an ordered tree data structure. For
23 * more information, see <a href= "http://en.wikipedia.org/wiki/Trie">Tries</a>.
24 * <p><strong>Note:</strong> Taken from
25 * <a href='http://www.limewire.org/'>Limewire</a> sourcecode and repackaged by
26 * Sascha Kohlmann.</p>
27 * @author Roger Kapsi
28 * @author Sam Berlin
29 */
30 public interface Trie<K, V> extends SortedMap<K, V> {
31
32 /**
33 * Returns a view of this Trie of all elements that are
34 * prefixed by the given key.
35 * <p>
36 * In a fixed-keysize Trie, this is essentially a 'get' operation.
37 * <p>
38 * For example, if the Trie contains 'Lime', 'LimeWire',
39 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
40 * a lookup of 'Lime' would return 'Lime', 'LimeRadio', and 'LimeWire'.
41 */
42 public SortedMap<K, V> getPrefixedBy(K key);
43
44 /**
45 * Returns a view of this Trie of all elements that are
46 * prefixed by the length of the key.
47 * <p>
48 * Fixed-keysize Tries will not support this operation
49 * (because all keys will be the same length).
50 * <p>
51 * For example, if the Trie contains 'Lime', 'LimeWire',
52 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
53 * a lookup of 'LimePlastics' with a length of 4 would
54 * return 'Lime', 'LimeRadio', and 'LimeWire'.
55 */
56 public SortedMap<K, V> getPrefixedBy(K key, int length);
57
58 /**
59 * Returns a view of this Trie of all elements that are prefixed
60 * by the key, starting at the given offset and for the given length.
61 * <p>
62 * Fixed-keysize Tries will not support this operation
63 * (because all keys are the same length).
64 * <p>
65 * For example, if the Trie contains 'Lime', 'LimeWire',
66 * 'LimeRadio', 'Lax', 'Later', 'Lake', and 'Lovely', then
67 * a lookup of 'The Lime Plastics' with an offset of 4 and a
68 * length of 4 would return 'Lime', 'LimeRadio', and 'LimeWire'.
69 */
70 public SortedMap<K, V> getPrefixedBy(K key, int offset, int length);
71
72 /**
73 * Returns a view of this Trie of all elements that are prefixed
74 * by the number of bits in the given Key.
75 * <p>
76 * Fixed-keysize Tries can support this operation as a way to do
77 * lookups of partial keys. That is, if the Trie is storing IP
78 * addresses, you can lookup all addresses that begin with
79 * '192.168' by providing the key '192.168.X.X' and a length of 16
80 * would return all addresses that begin with '192.168'.
81 */
82 public SortedMap<K, V> getPrefixedByBits(K key, int bitLength);
83
84 /**
85 * Returns the value for the entry whose key is closest in a bitwise
86 * XOR metric to the given key. This is NOT lexicographic closeness.
87 * For example, given the keys:<br>
88 * D = 1000100 <br>
89 * H = 1001000 <br>
90 * L = 1001100 <br>
91 * <p>
92 * If the Trie contained 'H' and 'L', a lookup of 'D' would return 'L',
93 * because the XOR distance between D & L is smaller than the XOR distance
94 * between D & H.
95 */
96 public V select(K key);
97
98 /**
99 * Iterates through the Trie, starting with the entry whose bitwise
100 * value is closest in an XOR metric to the given key. After the closest
101 * entry is found, the Trie will call select on that entry and continue
102 * calling select for each entry (traversing in order of XOR closeness,
103 * NOT lexicographically) until the cursor returns
104 * <code>Cursor.SelectStatus.EXIT</code>.<br>
105 * The cursor can return <code>Cursor.SelectStatus.CONTINUE</code> to
106 * continue traversing.<br>
107 * <code>Cursor.SelectStatus.REMOVE_AND_EXIT</code> is used to remove the current element
108 * and stop traversing.
109 * <p>
110 * Note: The {@link Cursor.SelectStatus#REMOVE} operation is not supported.
111 *
112 * @return The entry the cursor returned EXIT on, or null if it continued
113 * till the end.
114 */
115 public Map.Entry<K,V> select(K key, Cursor<? super K, ? super V> cursor);
116
117 /**
118 * Traverses the Trie in lexicographical order. <code>Cursor.select</code>
119 * will be called on each entry.<p>
120 * The traversal will stop when the cursor returns <code>Cursor.SelectStatus.EXIT</code>.<br>
121 * <code>Cursor.SelectStatus.CONTINUE</code> is used to continue traversing.<br>
122 * <code>Cursor.SelectStatus.REMOVE</code> is used to remove the element that was
123 * selected and continue traversing.<br>
124 * <code>Cursor.SelectStatus.REMOVE_AND_EXIT</code> is used to remove the current element
125 * and stop traversing.
126 *
127 * @return The entry the cursor returned EXIT on, or null if it continued
128 * till the end.
129 */
130 public Map.Entry<K,V> traverse(Cursor<? super K, ? super V> cursor);
131
132 /**
133 * An interface used by a {@link Trie}. A {@link Trie} selects items by
134 * closeness and passes the items to the <code>Cursor</code>. You can then
135 * decide what to do with the key-value pair and the return value
136 * from {@link #select(java.util.Map.Entry)} tells the <code>Trie</code>
137 * what to do next.
138 * <p>
139 * <code>Cursor</code> returns status/selection status might be:
140 * <table cellspace="5">
141 * <tr><td><b>Return Value</b></td><td><b>Status</b></td></tr>
142 * <tr><td>EXIT</td><td>Finish the Trie operation</td></tr>
143 * <tr><td>CONTINUE</td><td>Look at the next element in the traversal</td></tr>
144 * <tr><td>REMOVE_AND_EXIT</td><td>Remove the entry and stop iterating</td></tr>
145 * <tr><td>REMOVE</td><td>Remove the entry and continue iterating</td></tr>
146 * </table>
147
148 * Note: {@link Trie#select(Object, net.sf.eos.trie.Trie.Cursor)} does
149 * not support <code>REMOVE</code>.
150 *
151 * @param <K> Key Type
152 * @param <V> Key Value
153 */
154 public static interface Cursor<K, V> {
155
156 /**
157 * Notification that the Trie is currently looking at the given entry.
158 * Return <code>EXIT</code> to finish the Trie operation,
159 * <code>CONTINUE</code> to look at the next entry, <code>REMOVE</code>
160 * to remove the entry and continue iterating, or
161 * <code>REMOVE_AND_EXIT</code> to remove the entry and stop iterating.
162 * Not all operations support <code>REMOVE</code>.
163 *
164 */
165 public SelectStatus select(Map.Entry<? extends K, ? extends V> entry);
166
167 /** The mode during selection. */
168 public static enum SelectStatus {
169 EXIT, CONTINUE, REMOVE, REMOVE_AND_EXIT;
170 }
171 }
172 }
173