Mega Code Archive
A SortedMap implementation for dealing with fuzzy keys A binary search is used to find the closest key to the i
<![CDATA[
/*
* Copyright 2010 The Scripps Research Institute
*
* 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 edu.scripps.fl.collections;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
/**
* A SortedMap implementation for dealing with fuzzy keys. A binary search is used to find the closest key to the input.
*
* @author Mark Southern (southern at scripps dot edu).
*/
public class FuzzyMap<K, V> extends AbstractMap<K, V> implements SortedMap<K, V> {
protected static class ComparableComparator<T extends Comparable> implements Comparator<T> {
public int compare(T a, T b) {
return a == null ? (b == null ? 0 : -1) : (b == null ? 1 : a.compareTo(b));
}
}
protected static class Entry<K, V> implements Map.Entry<K, V> {
private boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
K key;
V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public Entry(Map.Entry<K, V> e) {
this.key = e.getKey();
this.value = e.getValue();
}
public boolean equals(Map.Entry<K, V> o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K, V> e = (Map.Entry<K, V>) o;
return eq(getKey(), e.getKey()) && eq(getValue(), e.getValue());
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public int hashCode() {
return ((getKey() == null) ? 0 : getKey().hashCode()) ^ ((getValue() == null) ? 0 : getValue().hashCode());
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public String toString() {
return String.format("%s [%s=%s]", getClass().getName(), getKey(), getValue());
}
}
@SuppressWarnings("unchecked")
static class MapEntryKeyComparator<K> implements Comparator {
private Comparator<K> comparator;
public MapEntryKeyComparator(Comparator<K> comparator) {
this.comparator = comparator;
}
public int compare(Object o1, Object o2) {
Map.Entry e = (Map.Entry) o1;
int cmp = comparator.compare((K) e.getKey(), (K) o2);
return cmp;
}
public Comparator<K> getComparator() {
return this.comparator;
}
}
private MapEntryKeyComparator<K> comparator = null;
protected List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
public FuzzyMap() {
comparator = new MapEntryKeyComparator<K>(new ComparableComparator());
}
// ----------------------------------------------------------------------
public FuzzyMap(Comparator<K> comparator) {
this.comparator = new MapEntryKeyComparator<K>(comparator);
}
public FuzzyMap(Map<K, V> map) {
loadFromMap(this, map);
}
@Override
public void clear() {
list.clear();
}
@Override
public Object clone() {
return loadFromMap(new FuzzyMap<K, V>(comparator()), this);
}
@Override
public Comparator<K> comparator() {
return comparator.getComparator();
}
@Override
@SuppressWarnings("unchecked")
public boolean containsKey(Object key) {
int idx = Collections.binarySearch((List) list, key, comparator);
if (idx > 0)
return true;
else if (idx == 0)
return list.size() > 0 && list.get(0).getKey().equals(key) ? true : false;
else
return false;
}
// ----------------------------------------------------------------------
@Override
public Set<Map.Entry<K, V>> entrySet() {
return new AbstractSet<Map.Entry<K, V>>() {
public Iterator<Map.Entry<K, V>> iterator() {
return list.iterator();
}
public int size() {
return list.size();
}
};
}
// ----------------------------------------------------------------------
@Override
public K firstKey() {
return ((Map.Entry<K, V>) list.get(0)).getKey();
}
@Override
@SuppressWarnings("unchecked")
public V get(Object key) {
if (list.isEmpty())
return null;
int idx = Collections.binarySearch((List) list, key, comparator);
if (idx < 0) {
idx = -1 * idx - 2;
if (idx < 0)
idx = 0;
}
Map.Entry<K, V> entry = list.get(idx);
return entry.getValue();
}
public Map.Entry<K, V> getEntry(int index) {
return list.get(index);
}
@SuppressWarnings("unchecked")
protected int getIndex(K key) {
int idx = Collections.binarySearch((List) list, key, comparator);
if (idx < 0) {
idx = -1 * idx - 2;
if (idx < 0)
idx = 0;
}
return idx;
}
@Override
public SortedMap<K, V> headMap(K toKey) {
int idx = getIndex(toKey);
FuzzyMap<K, V> fm = new FuzzyMap<K, V>(comparator());
fm.list = list.subList(0, idx);
return fm;
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public K lastKey() {
return ((Map.Entry<K, V>) list.get(list.size() - 1)).getKey();
}
protected FuzzyMap<K, V> loadFromMap(FuzzyMap<K, V> fm, Map<K, V> map) {
for (Map.Entry<K, V> entry : map.entrySet()) {
fm.put(entry.getKey(), entry.getValue());
}
return fm;
}
@Override
@SuppressWarnings("unchecked")
public V put(K key, V value) {
Entry<K, V> entry = new Entry<K, V>(key, value);
int idx = Collections.binarySearch((List) list, key, comparator);
if (idx >= 0) {
Map.Entry<K, V> oldEntry = list.set(idx, entry);
return oldEntry.getValue();
} else {
idx = -1 * idx - 1;
list.add(idx, entry);
return null;
}
}
@Override
@SuppressWarnings("unchecked")
public V remove(Object key) {
if (list.isEmpty())
return null;
int idx = Collections.binarySearch((List) list, key, comparator);
if (idx >= 0) {
Map.Entry<K, V> entry = list.remove(idx);
return entry.getValue();
}
return null;
}
@Override
public int size() {
return list.size();
}
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey) {
int idx1 = getIndex(fromKey);
int idx2 = getIndex(toKey);
FuzzyMap<K, V> fm = new FuzzyMap<K, V>(comparator());
fm.list = list.subList(idx1, idx2);
return fm;
};
@Override
public SortedMap<K, V> tailMap(K fromKey) {
int idx = getIndex(fromKey);
FuzzyMap<K, V> fm = new FuzzyMap<K, V>(comparator());
fm.list = list.subList(idx, list.size() - 1);
return fm;
}
}
]]>