Renamed Trie to Tree for consistency.
This is in the context of SDN-IP's patricia tree.
Change-Id: I59437fb49580aba01a287e9bc0bf035c093c7b95
diff --git a/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTree.java b/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTree.java
new file mode 100644
index 0000000..1ef9eae
--- /dev/null
+++ b/src/main/java/net/onrc/onos/apps/bgproute/IPatriciaTree.java
@@ -0,0 +1,100 @@
+package net.onrc.onos.apps.bgproute;
+
+import java.util.Iterator;
+
+/**
+ * A PATRICIA tree is data structure for storing data where entries aggregate
+ * based on shared prefixes. They provide lookups in O(k) where k is the
+ * maximum length of the strings in the tree. They work well for storing IP
+ * addresses.
+ * <p/>
+ * SDN-IP uses a patricia tree to store routes learnt from BGPd. BGPd sends
+ * route updates in the form:
+ * {@code <prefix, next_hop>},
+ * e.g. {@code <192.168.1.0/24, 10.0.0.1>}
+ * <p/>
+ * These updates are stored in the patricia tree, which acts as a map from
+ * {@code prefix} to {@code next_hop}. {@code next_hop} values can be looked up
+ * by prefix.
+ *
+ * @param <V> The class of the data to stored in the patricia tree
+ *
+ * @see <a href="http://en.wikipedia.org/wiki/Patricia_tree">Patricia tree</a>
+ */
+public interface IPatriciaTree<V> {
+ /**
+ * Puts a new mapping into the patricia tree.
+ *
+ * @param prefix the Prefix which is the key for this entry
+ * @param value the value that maps to the Prefix
+ * @return the old value that was mapped to the Prefix, or null if there
+ * was no such mapping
+ */
+ public V put(Prefix prefix, V value);
+
+ /**
+ * Searches the tree for a prefix that exactly matches the argument. If an
+ * exact match for the prefix is found in the tree, the value it maps to is
+ * returned. Otherwise, null is returned.
+ *
+ * @param prefix the prefix to look up in the tree
+ * @return the value if the prefix was found, otherwise null
+ */
+ public V lookup(Prefix prefix);
+
+ /**
+ * Searches the tree for the closest containing prefix of the supplied
+ * argument. If an exact match is found, that will be returned. Otherwise,
+ * the value of the most specific prefix that contains the argument prefix
+ * will be returned. If no such prefix is found, null is returned.
+ *
+ * @param prefix the prefix to find the closest containing match for in the
+ * tree
+ * @return the value of the match if one was found, otherwise null
+ */
+ public V match(Prefix prefix);
+
+ /**
+ * Removes a prefix to value mapping from the tree. The prefix argument is
+ * first looked up in the same way as the {@link #lookup(Prefix)} method.
+ * If an exact match to the prefix is found in the tree, its value is
+ * is checked to see if it matches the supplied argument value. The prefix
+ * and value will be removed only if both the prefix and value arguments
+ * match a mapping in the tree.
+ *
+ * @param prefix the prefix to remove from the tree
+ * @param value the value that must be mapped to the prefix for it to be
+ * removed
+ * @return true if a mapping was removed, otherwise false
+ */
+ public boolean remove(Prefix prefix, V value);
+
+ /**
+ * Gets an iterator over all mappings in the tree.
+ *
+ * @return an iterator that will iterate over all entries in the tree
+ */
+ public Iterator<Entry<V>> iterator();
+
+ /**
+ * Represents an entry in the patricia tree. The {@code Entry} is a mapping
+ * from {@link Prefix} to a {@link V} value object.
+ *
+ * @param <V> the class of objects stored in the tree
+ */
+ interface Entry<V> {
+ /**
+ * Gets the {@link Prefix} object for this entry.
+ *
+ * @return the prefix for this entry
+ */
+ public Prefix getPrefix();
+
+ /**
+ * Gets the value of this entry.
+ *
+ * @return the value object of this entry
+ */
+ public V getValue();
+ }
+}