001 package edu.harvard.deas.hyperenc.util;
002
003 import java.util.SortedMap;
004 import java.util.TreeMap;
005
006 import org.apache.log4j.Logger;
007
008 /**
009 * A collection of objects and associated integer keys, with support for
010 * nearest-neighbor lookups. In other words, this is a {@link java.util.Map}
011 * with integer keys, and the <code>get(int key)</code> method retrieves the
012 * object whose key is numerically closest to <code>key</code>.
013 */
014 public class NNLookup<V>
015 {
016 private static final Logger logger = Logger.getLogger(NNLookup.class);
017
018 private static final long serialVersionUID = 1L;
019
020 private SortedMap<Integer,V> myMap = new TreeMap<Integer,V>();
021
022 /**
023 * Add the object <code>object</code> using <code>key</code> as its index.
024 *
025 * @param key
026 * The key to associated with <code>object</code>.
027 * @param object
028 * The object to be stored.
029 */
030 synchronized public void add(int key, V object)
031 {
032 myMap.put(key, object);
033 logger.trace("Added item " + object + " with key " + key);
034 }
035
036 /**
037 * Gets the object using this exact key. If no object has key <i>equal</i> to
038 * <code>key</code>, returns <code>null</code>. This is the normal Map behavior.
039 *
040 * @param key
041 * The integer key value to search for.
042 * @return The data of the object with the <b>exact</b> key. Should be null
043 * iff the lookup table is empty.
044 */
045 synchronized public V getExact(int key)
046 {
047 return myMap.get(key); // use the original TreeMap get method
048 }
049
050 /**
051 * Get an object using the key <code>key</code>. Gets the object whose key is
052 * numerically closest to the one passed in.
053 *
054 * @param key
055 * The integer key value to search for.
056 * @return the object with the <i>closest</i> key, or <code>null</code> iff
057 * the lookup table is empty.
058 */
059 synchronized public V get(int key)
060 {
061 Integer k = getClosestKey(key);
062
063 logger.trace("Attempting to get object with key " + key
064 + " -- the closest key is " + k);
065 if (k != null)
066 return myMap.get(k);
067 else
068 return null;
069 }
070
071 /** Deletes the object with the key nearest to the specified key.
072 @param key The key value you want to delete.
073 @return The value mapped to the key deleted. */
074 synchronized public V delete(int key)
075 {
076 Integer k = getClosestKey(key);
077
078 if (k != null)
079 return myMap.remove(k);
080 else
081 return null;
082 }
083
084 /** Deletes the object with the specified key.
085 @param key The key value you want to delete.
086 @return The value mapped to the key deleted. */
087 synchronized public Object deleteExact(int key)
088 {
089 return myMap.remove(new Integer(key));
090 }
091
092 /** Get the key closest to the one passed in.
093 @param key The key value to search for.
094 @return The object with the closest key. Should be null iff
095 the lookup table is empty. Currently this is an Integer. */
096 synchronized public Integer getClosestKey(int key)
097 {
098 if (myMap.containsKey(key)) {
099 return key;
100 } else {
101 Integer closestAbove = null;
102 Integer closestBelow = null;
103
104 // Check keys greater than or equal to key
105 SortedMap<Integer,V> m = myMap.tailMap(key);
106 if (!m.isEmpty()) {
107 closestAbove = m.firstKey();
108 }
109
110 // Check keys less than or equal to key
111 m = myMap.headMap(key);
112 if (!m.isEmpty()) {
113 closestBelow = m.lastKey();
114 }
115
116 if (closestAbove == null) {
117 return closestBelow;
118 } else if (closestBelow == null) {
119 return closestAbove;
120 } else if (key - closestBelow.intValue() < closestAbove.intValue() - key) {
121 return closestBelow;
122 } else {
123 return closestAbove;
124 }
125 }
126 }
127
128 /**
129 * Returns the number of key-value pairs stored in this map.
130 * @return the size of this map
131 */
132 public int size() {
133 return myMap.size();
134 }
135 }
136
137
138
139
140
141