RangeMap
Heiner Kücker
ich habe gerade so einen Gedanken für eine Datenstruktur.
Gegeben sei folgendes Problem:
Es gibt konkrete Nummern (Gerätenummer) die jeweils zu
einem Nummernband gehören.
Es werden clusterweise wechselnd Geräte hergestellt, die
jeweils ein zusammengehörendes Band von laufenden Nummern
bekommen.
Die Nummernbänder überlappen sich nicht.
Es sollte nicht vorkommen, dass kein Treffer gefunden wird.
Es ergibt sich folgende Datenstruktur:
ITEM_FROM NUMBER
ITEM_TO NUMBER
ITEM_TYP NUMBER
Ich will also anhand der Geräte-Nummer die Artikel-Nummer (Geräte-Typ)
herausbekommen.
Das alles soll ziemlich performant sein.
Von der Datenbank hole ich den passenden Datensatz per
SELECT ... WHERE ITEM_FROM <= ? AND ITEM_TO >= ?
Ein WHERE IN ... hilft mir hier nicht.
Ich weiss nicht, ob mir hier ein Index auf der DB hilft.
Beim Clipper gab es einen
SET SOFTSEEK ON
der den nächst passenden Treffer aus dem Index brachte.
Zwischen meiner Businesslogik und der DB-Schicht liegt natürlich ein Cache.
Normalerweise arbeitet ein cache mit einer Key-Value-Kombination,
also HashMap.
Das klappt in meinem Fall nicht.
Also brauche ich eine RangeMap.
Bei der Eingabe von 'rangemap java source' im Google kommt
einiges Internetrauschen heraus. Ist aber nicht so das perfekt
richtige.
Also ich habe eine Struktur mit einem Key von-bis und einem Value.
Wie schon gesagt, HashMap hilft hier nicht.
Ich dachte mir nun, nehme ich eine TreeMap. Die Suche erfolgt binär
und nicht linear (was ziemlich langsam wäre).
Der Baum wird von der JDK-Klasse balanciert, Klasse.
Nur muss ich die Methoden compareTo und equals so ummodeln,
dass beim Einfügen in die Map (put) nach der Range sortiert wird.
Beim get muss aber nach Range und wert verglichen werden.
Nun wollte ich aber die JDK-Klasse nicht aufdröseln oder neu implementieren.
Vielleicht sollte ich eine Klasse machen, die entweder eine Range oder ein Key
sein kann und in compareTo und equals per instanceof entscheiden, wie der
Vergleich ausgeht:
equals liefert true, wenn Key in Range.
compareTo liefert
0, wenn Key in Range.
-1, wenn Key kleiner als Range from.
1, wenn Key grösser als Range to.
Vielleicht habt Ihr eine bessere Idee.
Da es algorithmisch interessant ist,
werde ich eventuell eine Lösung als Util-Klasse auf meine Home-Page stellen.
--
Heiner Kücker
Internet: http://www.heinerkuecker.de http://www.heiner-kuecker.de
JSP WorkFlow PageFlow Page Flow FlowControl Navigation: http://www.control-and-command.de
Java Expression Formula Parser: http://www.heinerkuecker.de/Expression.html
Domain Specific Languages http://www.heinerkuecker.de/DomainParser.html
Heiner Kücker
> Also brauche ich eine RangeMap.
>
> Wie schon gesagt, HashMap hilft hier nicht.
Die Begeisterung in diesem Thread überschlägt sich,
scheinbar braucht niemand so was.
Ich kanns nicht lassen, hier mal ein schnell getippter Prototyp,
nicht getestet und noch nicht bezüglich Performance bewertet,
vielleicht gibt es ja doch irgendwelche Interessenten:
//package xxx;
import java.util.TreeMap;
/**
* Eine Map, deren Key ein Bereich zwischen zwei
* int-Werten ('from' und 'to') ist.
* Der Value ist wie üblich ein Objekt.
*
* @author Heiner Kücker www.heinerkuecker.de
*/
public class RangeMap
{
/** inner map */
private TreeMap treeMap = new TreeMap();
/**
* put wrapped.
*
* @param pFrom
* @param pTo
* @param pValue
*/
public void put( // --
final int pFrom, // --
final int pTo, // --
final Object pValue)
{
Range range = new Range(pFrom, pTo);
treeMap.put(range, pValue);
}
/**
* get wrapped.
*
* @param pKey
* @return
*/
public Object get(final int pKey)
{
return treeMap.get(new Point(pKey));
}
/**
* Help class for Range-Key or Point-Key.
*/
private abstract static class RangeOrPoint implements Comparable
{
/**
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(Object o)
{
int retVal;
if (this instanceof Range)
{
//System.out.println( "this Range" );
retVal = compareRangeToPoint((Range) this, o);
}
else if (this instanceof Point)
{
//System.out.println( "this Point" );
retVal = comparePointToRange((Point) this, o);
}
else
{
throw new IllegalArgumentException(o.getClass().getName());
}
//System.out.println("retVal: " + retVal );
return retVal;
}
/**
* Compare Range with Object.
*
* @param range
* @param o
* @return
*/
private static int compareRangeToPoint(Range pRange, Object o)
{
if (o instanceof Range)
{
Range oRange = (Range) o;
if (pRange.from == oRange.from && pRange.to == oRange.to)
{
return 0;
}
else if (pRange.from < oRange.from)
{
return -1;
}
return 1;
}
else if (o instanceof Point)
{
Point oPoint = (Point) o;
if (pRange.from <= oPoint.point && pRange.to >= oPoint.point)
{
return 0;
}
else if (pRange.to < oPoint.point)
{
return -1;
}
return 1;
}
else
{
throw new IllegalArgumentException(o.getClass().getName());
}
}
/**
* Compare Point with Object.
*
* @param point
* @param o
* @return
*/
private static int comparePointToRange(Point pPoint, Object o)
{
if (o instanceof Range)
{
//System.out.println( "o Range" );
Range oRange = (Range) o;
//System.out.println( "oRange.from: " + oRange.from + " oRange.to: " + oRange.to );
if (oRange.from <= pPoint.point && oRange.to >= pPoint.point)
{
return 0;
}
else if (pPoint.point < oRange.to)
{
return -1;
}
return 1;
}
else if (o instanceof Point)
{
//System.out.println( "o Point" );
Point oPoint = (Point) o;
if (pPoint.point == oPoint.point)
{
return 0;
}
else if (pPoint.point < oPoint.point)
{
return -1;
}
return 1;
}
else
{
throw new IllegalArgumentException(o.getClass().getName());
}
}
}
/**
* Helper class for range key.
*/
private static class Range extends RangeOrPoint
{
private int from;
private int to;
public Range( // --
final int pFrom, // --
final int pTo)
{
from = pFrom;
to = pTo;
}
}
/**
* Helper class for 'point in range' key.
*/
private static class Point extends RangeOrPoint
{
private int point;
public Point( // --
final int pTopic)
{
point = pTopic;
}
}
/**
* Test.
*
* @param args
*/
public static void main(String[] args)
{
RangeMap rangeMap = new RangeMap();
rangeMap.put( 0, 10, " 0-10");
rangeMap.put(20, 30, "20-30");
test(rangeMap, -1, false);
test(rangeMap, 0, true);
test(rangeMap, 1, true);
test(rangeMap, 2, true);
test(rangeMap, 3, true);
test(rangeMap, 4, true);
test(rangeMap, 5, true);
test(rangeMap, 6, true);
test(rangeMap, 7, true);
test(rangeMap, 8, true);
test(rangeMap, 9, true);
test(rangeMap, 10, true);
test(rangeMap, 11, false);
test(rangeMap, 19, false);
test(rangeMap, 20, true);
test(rangeMap, 31, false);
}
/**
* @param pRangeMap
*/
private static void test(// --
final RangeMap pRangeMap, // --
final int pKey, // --
final boolean pHit)
{
Object o = pRangeMap.get(pKey);
System.out.println("o[" + pKey + "]: " + o);
if (pHit ^ (o != null)) // XOR
{
throw new RuntimeException("" + o);
}
}
}
--
Heiner Kücker
Frank Dreyer
comparePointToRange direkt in die jeweilige Subklasse?
> throw new RuntimeException("" + o);
[ ] Du kennst String.valueOf()
Ansonsten wäre das aber auch mein Lösungsansatz gewesen. Ich würde aber
auf jeden fall noch das besondere Verhalten deiner equals bzw. compareTo
Methode dokumentieren, damit später keine Überraschungen aufkommen.
Heiner Kücker
> Warum packst du nicht den Code von compareRangeToPoint bzw.
> comparePointToRange direkt in die jeweilige Subklasse?
So weit hatte ich es zu diesem Zeitpunkt noch nicht überblickt.
Kann man machen.
> Ansonsten wäre das aber auch mein Lösungsansatz gewesen. Ich würde aber
> auf jeden Fall noch das besondere Verhalten deiner equals bzw. compareTo
> Methode dokumentieren, damit später keine Überraschungen aufkommen.
Ja. Aber eigentlich sind die private, gehören also nicht zum API.
--
Heiner Kücker
Internet: http://www.heinerkuecker.de http://www.heiner-kuecker.de