/*
* 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 extends AbstractMap implements SortedMap {
protected static class ComparableComparator implements Comparator {
public int compare(T a, T b) {
return a == null ? (b == null ? 0 : -1) : (b == null ? 1 : a.compareTo(b));
}
}
protected static class Entry implements Map.Entry {
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 e) {
this.key = e.getKey();
this.value = e.getValue();
}
public boolean equals(Map.Entry o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry) 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 implements Comparator {
private Comparator comparator;
public MapEntryKeyComparator(Comparator 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 getComparator() {
return this.comparator;
}
}
private MapEntryKeyComparator comparator = null;
protected List> list = new ArrayList>();
public FuzzyMap() {
comparator = new MapEntryKeyComparator(new ComparableComparator());
}
// ----------------------------------------------------------------------
public FuzzyMap(Comparator comparator) {
this.comparator = new MapEntryKeyComparator(comparator);
}
public FuzzyMap(Map map) {
loadFromMap(this, map);
}
@Override
public void clear() {
list.clear();
}
@Override
public Object clone() {
return loadFromMap(new FuzzyMap(comparator()), this);
}
@Override
public Comparator 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> entrySet() {
return new AbstractSet>() {
public Iterator> iterator() {
return list.iterator();
}
public int size() {
return list.size();
}
};
}
// ----------------------------------------------------------------------
@Override
public K firstKey() {
return ((Map.Entry) 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 entry = list.get(idx);
return entry.getValue();
}
public Map.Entry 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 headMap(K toKey) {
int idx = getIndex(toKey);
FuzzyMap fm = new FuzzyMap(comparator());
fm.list = list.subList(0, idx);
return fm;
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public K lastKey() {
return ((Map.Entry) list.get(list.size() - 1)).getKey();
}
protected FuzzyMap loadFromMap(FuzzyMap fm, Map map) {
for (Map.Entry entry : map.entrySet()) {
fm.put(entry.getKey(), entry.getValue());
}
return fm;
}
@Override
@SuppressWarnings("unchecked")
public V put(K key, V value) {
Entry entry = new Entry(key, value);
int idx = Collections.binarySearch((List) list, key, comparator);
if (idx >= 0) {
Map.Entry 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 entry = list.remove(idx);
return entry.getValue();
}
return null;
}
@Override
public int size() {
return list.size();
}
@Override
public SortedMap subMap(K fromKey, K toKey) {
int idx1 = getIndex(fromKey);
int idx2 = getIndex(toKey);
FuzzyMap fm = new FuzzyMap(comparator());
fm.list = list.subList(idx1, idx2);
return fm;
};
@Override
public SortedMap tailMap(K fromKey) {
int idx = getIndex(fromKey);
FuzzyMap fm = new FuzzyMap(comparator());
fm.list = list.subList(idx, list.size() - 1);
return fm;
}
}