PrefixConcurrentDictionary.java

/***************************************************************************
   Copyright 2013 Emily Estes

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
***************************************************************************/
package net.metanotion.util;


import java.util.Map;
import java.util.SortedMap;
import java.util.concurrent.ConcurrentSkipListMap;

/** A concurrency safe Dictionary(backed by java.util.concurrent.ConcurrentSkipListMap) that allows for searching for
the shortest key that starts with a given prefix.
For instance if the dictionary contains the following keys: [ a, abc, abd, abe, bb, ba ] and we search for "ab"
we will find "abc", but if we search for "a", we will find "a".
TO DO: The backing map should be replaced with a trie to get better degenerate search performance.
	@param <V> The type of values being stored in the dictionary.
*/
public final class PrefixConcurrentDictionary<V> implements Dictionary<String,V> {
	private final SortedMap<String,V> map = new ConcurrentSkipListMap<String,V>(new StringLengthComparator());

	/** Search for a prefix in the key set: the shortest key that starts with the prefix will be returned, or null if
		no such key can be found.
		@param prefix The prefix to search for.
		@return The shortest exact key that starts with prefix or null if no such key exists.
	*/
	public String findKey(final String prefix) {
		for(final Map.Entry<String,V> d: map.tailMap(prefix).entrySet()) {
			if(prefix.startsWith(d.getKey())) { return d.getKey(); }
		}
		return null;
	}

	/** Retrieve keys using the search method described in the class description(first key with a given prefix).
		This method uses the findKey method.
		@param prefix The prefix to search the dictionary for.
		@return The value assigned to the first key with prefix searched for, or null if no such key exists.
	*/
	@Override public V get(final String prefix) {
		final String k = findKey(prefix);
		if(k==null) { return null; }
		return map.get(k);
	}

	/** Remove a value from the dictionary.
		@param key The EXACT key to remove from the dictionary.
		@return The value assigned to the key(if any).
	*/
	public V remove(final String key) { return map.remove(key); }

	/** Store a value in the dictionary under a specific key.
		@param key The key to store the value under.
		@param val The value to store.
	*/
	public void put(final String key, final V val) { map.put(key, val); }
}