Skip to content
Permalink
0d82ff1dc4
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

HowToKB/src/kb/howtokb/utils/SortedMultiMap.java

Go to file
 
 
Cannot retrieve contributors at this time
364 lines (293 sloc) 10.1 KB
Raw Blame
package kb.howtokb.utils;
import java.sql.SQLException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Set;
import kb.howtokb.tools.NormalizationText;
/** Usage:
public static void main(String[] args) throws SQLException {
SortedMultiMap<String, String> m = new SortedMultiMap<>(3, true);
m.put("a", "a1", 1.0);
m.put("b", "a2", 0.9);
m.put("a", "a3", 0.95);
m.put("a", "a1", 0.96);
m.put("a", "a3", 0.96);
SortedMultiMap<String, String> m2 = new SortedMultiMap<>(3, true);
m2.put("a", "a1", 0.9);
m2.put("b", "a1", 1.0);
m2.put("b", "a2", 0.95);
m2.put("a", "a3", 1.0);
m.putAll(m2);
for (String e : m.keyset()) {
System.out.println(e + "\t" + Arrays.toString(m.get(e)));
}
}*/
/**
*
* @author ntandon
*
* @param <K>
* @param <V>
*/
public class SortedMultiMap<K, V> {
public static void main(String[] args) throws SQLException {
SortedMultiMap<Integer, Integer> m = new SortedMultiMap<>(3, true);
m.put(1, 1, 1.0);
m.put(2, 2, 0.9);
m.put(3, 3, 0.95);
m.put(4, 4, 0.96);
m.put(5, 5, 0.96);
for (Integer e : m.keyset()) {
System.out.println(e + "\t" + Arrays.toString(m.get(e)));
}
}
// //////////////////////////////////////////////////////////////
// //////////////////// Functionality/////////////////////
// ////////////////////////////////////////////////////////////
private int maxK;
private final boolean inDescOrder;
private AutoMap<K, PriorityQueue<QEntry<V>>> m;
/**
*
* @param maxK How many top "k" elements are required
* @param inDescOrder if set to false sorts in ascending order
* @throws SQLException
*/
public SortedMultiMap(int maxK, boolean inDescOrder) throws SQLException {
this.maxK = maxK;
this.inDescOrder = inDescOrder;
m = new AutoMap<>();
}
/**
* <PRE>
* boolean isDesc = true;
*
* AutoMap<String, PriorityQueue<QEntry<String>>> m = new AutoMap<>();
*
* expander.putSorted("niket", "c", 40, m, isDesc);
*
* expander.putSorted("niket", "p", 10, m, isDesc);
* expander.putSorted("niket", "b", 4, m, isDesc);
* expander.putSorted("niket", "m", 50, m, isDesc);
*
* expander.putSorted("anjali", "p", 90, m, isDesc);
* expander.putSorted("anjali", "c", 40, m, isDesc);
*
* expander.putSorted("anjali", "m", 20, m, isDesc);
* expander.putSorted("anjali", "b", 100, m, isDesc);
*
* for (Entry<String, PriorityQueue<QEntry<String>>> e : m.entrySet())
* for (QEntry<String> e2 : e.getValue())
* System.out.println(e.getKey() + "\t" + e2);
* @author ntandon
*
* @param <V>
*/
public static class QEntry<V> {
private V v;
public V getV() {
return v;
}
public double getN() {
return n;
}
public void setN(double nNew) {
n = nNew;
}
public void addToN(double nNew) {
n += nNew;
}
private double n;
public QEntry(V v, double n) {
this.v = v;
this.n = n;
}
@Override
public String toString() {
return new StringBuilder().append(v.toString()).append('\t')
.append(NormalizationText.format(n)).toString();
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((v == null) ? 0 : v.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
QEntry other = (QEntry) obj;
if (v == null) {
if (other.v != null)
return false;
} else if (!v.equals(other.v))
return false;
return true;
}
}
/**
* @deprecated because update on( "a 80, b 40" maxk=1) with (b, 50) would
* have already dropped b in the first round.
* @param key
* @param value
* @param n
*/
public void update(K key, V value, double n) {
if (!m.containsKey(key))
m.put(key, new PriorityQueue<QEntry<V>>(maxK,
new Comparator<QEntry<V>>() {
@Override
public int compare(QEntry<V> o1, QEntry<V> o2) {
return inDescOrder ? (o1.n > o2.n ? 1 : -1)
: (o2.n > o1.n ? 1 : -1);
}
}));
// key=animal; value=tiger, n=10.
// m: animal=> dog;50, tiger;45, cow;10
// Update if existing==> m: animal=> dog;50, tiger;55, cow;10
QEntry<V> qEntry = updatePriorityQueue(m.get(key), value, n);
PriorityQueue<QEntry<V>> qExisting = m.get(key);
/*
* Does the worst existing entry compare unfavorably to the entrytoadd?
*/
qExisting.add(qEntry);
if (qExisting.size() > maxK)
qExisting.poll(); // remove the head (contains the worst value).
}
// key=animal; value=tiger, n=50.
// m: animal=> dog;50, tiger;45, cow;10
// Replace in existing==> m: animal=> dog;50, tiger;*50*, cow;10
private boolean replaceInPriorityQueue(PriorityQueue<QEntry<V>> q, V value,
double n) {
V entryToRemove = null;
double newVal = 0.0;
for (QEntry<V> e : q) {
// if key already exists with a larger value, no operation
// if key already exists with a smaller value, replace
if (e.getV().equals(value) && e.getN() < n) {
entryToRemove = value;
newVal = Math.max(e.getN(), n);
break;
}
}
if (entryToRemove != null) {
q.remove(entryToRemove);
q.add(new QEntry<V>(entryToRemove, newVal));
return true;
}
return false;
}
// key=animal; value=tiger, n=10.
// m: animal=> dog;50, tiger;45, cow;10
// Update if existing==> m: animal=> dog;50, tiger;55, cow;10
private QEntry<V> updatePriorityQueue(PriorityQueue<QEntry<V>> q, V value,
double n) {
for (QEntry<V> e : q) {
if (e.getV().equals(value)) {
double newVal = e.getN() + n;
q.remove(e);
return new QEntry<V>(value, newVal);
}
}
return new QEntry<V>(value, n);
}
public void put(K key, V value, double n) {
if (!m.containsKey(key))
m.put(key, new PriorityQueue<QEntry<V>>(maxK,
new Comparator<QEntry<V>>() {
@Override
public int compare(QEntry<V> o1, QEntry<V> o2) {
return inDescOrder ? (o1.n > o2.n ? 1 : -1)
: (o2.n > o1.n ? 1 : -1);
}
}));
PriorityQueue<QEntry<V>> qExisting = m.get(key);
// if qExisting already has a QEntry containing the same key, retain the
// max value as n
boolean isValueUpdated = false;
for (QEntry<V> entry : qExisting) {
if (entry.v.equals(value)) {
entry.n = n > entry.n ? n : entry.n;
isValueUpdated = true;
break;
}
}
if (!isValueUpdated) {
QEntry<V> qEntry = new QEntry<V>(value, n);
/*
* Does the worst existing entry compare unfavorably to the
* entrytoadd?
*/
qExisting.add(qEntry);
if (qExisting.size() > maxK)
qExisting.poll(); // remove the head (contains the worst value).
}
}
public void remove(K key, V value) {
if (containsKey(key))
m.get(key).remove(value);
}
public boolean containsKey(K key) {
return m.containsKey(key);
}
public boolean containsKey(K key, V value) {
return value != null && containsKey(key) && m.get(key).contains(value);
}
public void remove(K key) {
if (m.containsKey(key))
m.remove(key);
}
private QEntry[] priorityQToOrderedArr(PriorityQueue<QEntry<V>> q) {
QEntry[] result = new QEntry[0];
if (q == null)
return null;
else
result = new QEntry[q.size()];
int reverseIndex = result.length;
QEntry<V> e = q.poll();
while (e != null) {
result[--reverseIndex] = e;
e = q.poll();
}
return result;
}
public QEntry[] get(K key) {
PriorityQueue<QEntry<V>> q =
key == null || !m.containsKey(key) ? null : m.get(key);
return priorityQToOrderedArr(new PriorityQueue<>(q));
}
public Map<V, Double> getAsMap(K key) {
Map<V, Double> mResult = new LinkedHashMap<>();
PriorityQueue<QEntry<V>> q =
key == null || !m.containsKey(key) ? null : m.get(key);
for (QEntry e : priorityQToOrderedArr(new PriorityQueue<>(q)))
mResult.put((V) e.getV(), e.getN());
return mResult;
}
public Set<K> keyset() {
return m.keySet();
}
public Set<Entry<K, PriorityQueue<QEntry<V>>>> entrySet() {
return m.entrySet();
}
// public void putAll(SortedMultiMap<K, V> addme) {
//
// for (Entry<K, PriorityQueue<QEntry<V>>> e : Util.nullableIter(addme
// .entrySet()))
// for (QEntry<V> e2 : e.getValue())
// put(e.getKey(), e2.getV(), e2.getN());
// }
public int size(){
return m!=null? m.size(): 0;
}
}