Ralf Ullrich schrieb
Post by Ralf UllrichPost by Heiner KückerKönntest Du mal den Main-Code für die Messung posten.
Bitteschön. (Nicht vergessen neueste Trove4J-Jar (äh 2.0.1?) in den
Class-Path nehmen.)
Danke, Super.
Ich habe den Test für die Variante mit dem Trie die
ganze Nacht laufen lassen.
Grottenschlecht.
Von 20 mal so schlecht bis 1000 mal so schlecht
schwankt es.
Das hätte ich nicht gedacht.
Also das Standard-Java-API ist gar nicht so
leicht zu schlagen:
package de.jnana.dclj;
//import gnu.trove.TIntHashSet;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import util.collections.primitve.IntTrieSet;
public class UniqueIntArrayDemo {
public interface UniqueIntArrayFunction {
int[] unique(int[] a);
}
public static class Simple implements UniqueIntArrayFunction {
// @Override
public int[] unique(int[] a) {
if (a.length == 0) {
return a;
}
int[] b = a.clone();
Arrays.sort(b);
int j = 1;
int i = 1;
int v = b[0];
while (i < b.length) {
int w = b[i++];
if (v != w) {
b[j++] = v = w;
}
}
return Arrays.copyOf(b, j);
}
}
public static class HKImpl implements UniqueIntArrayFunction {
// @Override
public int[] unique(int[] a) {
Set<Integer> set = new HashSet<Integer>(a.length);
for (int v : a) {
set.add(v);
}
int[] rv = new int[set.size()];
int i = 0;
for (Integer v : set) {
rv[i++] = v;
}
return rv;
}
}
// public static class Trove implements UniqueIntArrayFunction {
// @Override
// public int[] unique(int[] a) {
// return new TIntHashSet(a).toArray();
// }
// }
public static class Trie implements UniqueIntArrayFunction {
//@Override
public int[] unique(int[] a) {
return new IntTrieSet(a).toArray();
}
}
public static class SRImpl implements UniqueIntArrayFunction {
public int[] unique(int[] a) {
boolean[] seen = new boolean[a.length + 2];
int[] rv = new int[a.length];
int size = 0;
for (int v : a) {
if (!seen[v]) {
rv[size++] = v;
seen[v] = true;
}
}
return Arrays.copyOf(rv, size);
}
}
public static class Heap implements UniqueIntArrayFunction {
// @Override
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = a.clone();
for (int i = (size - 1) / 2; i >= 0; i--) {
{
int k = i;
int v = q[k];
while (2 * k + 1 < size) {
int j = 2 * k + 1; // k < (size-1)/2
if ((j + 1 < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size;
int last = q[0];
q[0] = q[--size];
q[--pos] = last;
while (size > 0) {
{
int k = 0;
int v = q[k];
while (2 * k + 1 < size) {
int j = 2 * k + 1;
if ((j + 1 < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[0];
q[0] = q[--size];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
public static class HeapOrig implements UniqueIntArrayFunction {
// @Override
public int[] unique(final int[] a) {
if (a.length == 0) {
return a;
}
int size = a.length;
int[] q = new int[size + 1];
System.arraycopy(a, 0, q, 1, size);
for (int i = size / 2; i > 0; i--) {
{
int k = i;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
}
int pos = size + 1;
int last = q[1];
q[1] = q[size--];
q[--pos] = last;
while (size > 0) {
{
int k = 1;
int v = q[k];
while (k <= size / 2) {
int j = 2 * k;
if ((j < size) && (q[j] < q[j + 1])) {
j += 1;
}
if (v >= q[j]) {
break;
}
q[k] = q[j];
k = j;
}
q[k] = v;
}
int v = q[1];
q[1] = q[size--];
if (v < last) {
last = q[--pos] = v;
}
}
return Arrays.copyOfRange(q, pos, q.length);
}
}
static int[] testcase(int range, int size) {
Random r = new Random(0);
int[] rv = new int[size];
for (int i = 0; i < size; i++) {
rv[i] = r.nextInt(range);
}
return rv;
}
static boolean equalsUnordered(final int[] a, final int[] b) {
int[] aa = a.clone();
int[] bb = b.clone();
Arrays.sort(aa);
Arrays.sort(bb);
return Arrays.equals(aa, bb);
}
static void time(String msg, UniqueIntArrayFunction[] tests, int[]
data, int[] expect, int loop) {
if (expect == null) {
expect = new Simple().unique(data.clone());
}
StringBuilder sb = new StringBuilder(String.format("%-18s", msg));
for (UniqueIntArrayFunction fn : tests) {
int[] copy = data.clone();
long start = System.nanoTime();
int[] result;
int n = loop;
do {
result = fn.unique(copy);
} while (--n > 0);
long end = System.nanoTime();
boolean success = Arrays.equals(data, copy) &&
equalsUnordered(result, expect);
double seconds = (end - start) / 1000000000.0;
sb.append(String.format("%7.3fs %s %-6s", seconds, success ?
"OK" : "NO", fn.getClass().
getSimpleName()));
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
UniqueIntArrayFunction[] tests =
new UniqueIntArrayFunction[]{
new Simple(),
new HKImpl(),
//new Trove()
new Trie()
};
// , new SRImpl(), new Heap()
for (int warmup = 0; warmup < 10; warmup++) {
time("### Example", tests, new int[]{1, 2, 3, 4, 5, 5, 5, 6,
7}, new int[]{1, 2, 3, 4, 5, 6, 7},
1000000);
time("### 1/15", tests, testcase(1, 15), null, 1000000);
time("### 2/15", tests, testcase(2, 15), null, 1000000);
time("### 5/15", tests, testcase(5, 15), null, 1000000);
time("### 10/15", tests, testcase(10, 15), null, 1000000);
time("### 15/15", tests, testcase(15, 15), null, 1000000);
time("### 1/150", tests, testcase(1, 150), null, 100000);
time("### 10/150", tests, testcase(10, 150), null, 100000);
time("### 50/150", tests, testcase(50, 150), null, 100000);
time("### 100/150", tests, testcase(100, 150), null, 100000);
time("### 150/150", tests, testcase(150, 150), null, 100000);
time("### 10/1500", tests, testcase(10, 1500), null, 10000);
time("### 100/1500", tests, testcase(100, 1500), null, 10000);
time("### 500/1500", tests, testcase(500, 1500), null, 10000);
time("### 1000/1500", tests, testcase(1000, 1500), null,
10000);
time("### 1500/1500", tests, testcase(1500, 1500), null,
10000);
time("### 100/15000", tests, testcase(100, 15000), null, 1000);
time("### 1000/15000", tests, testcase(1000, 15000), null,
1000);
time("### 5000/15000", tests, testcase(5000, 15000), null,
1000);
time("### 10000/15000", tests, testcase(10000, 15000), null,
1000);
time("### 15000/15000", tests, testcase(15000, 15000), null,
1000);
}
}
}
package util.collections.primitve;
import java.util.Arrays;
import de.heinerkuecker.util.TestFailedException;
/**
* Diese experimentelle Klasse
* enthält ein Set von int-Werten
* (Primitiven) welches als
* Trie oder sogenannter
* Patricia-Baum aufgebaut ist.
*
* Dabei wird für jedes Bit
* der zu vermekenden int-Werte
* ein 2-stelliges boolean-Array
* angelegt.
*
* Begonnen wird mit dem
* niederwertigsten Bit.
*
* Je nach dem, ob das
* betrachtete Bit 0 oder
* 1 ist, wird im jeweiligen
* linken oder rechten
* Sub-Array weitergesucht.
*
* Ist das nächste Sub-Array
* null, so sind alle Werte
* ab diesem Bit nicht vorhanden.
*
* Wird das letzte Array erreicht,
* so entscheidet der Zustand
* des Boolean-Merkers, ob
* der entsprechende int-Wert
* vermerkt ist oder nicht.
*
* TODO statt Arrays mit je zwei Einträgen mal mit Arrays mit 4, 8 oder 16
Einträgen testen
*
* @author Heiner Kücker
*/
public class IntTrieSet
{
public static final int BIT_COUNT = 32;
private Object[] trieArr =
new Object[ 2 ];
private int size;
/**
* Constructor
*/
public IntTrieSet()
{
super();
}
/**
* Constructor
*/
public IntTrieSet(
final int[] pIntArr )
{
super();
addAll( pIntArr );
}
/**
* @param pIntArr
*/
public void addAll(
final int[] pIntArr )
{
for (int i = 0; i < pIntArr.length; i++ )
{
add( pIntArr[ i ] );
}
}
/**
* Zurückgeben der Anzahl vermerkter Werte
* @return Anzahl vermerkter Werte
* @see java.util.Set#size()
*/
public int size()
{
return this.size;
}
/**
* Alle vermerkten
* Werte löschen.
*/
public void clear()
{
this.size = 0;
this.trieArr[ 0 ] = null;
this.trieArr[ 1 ] = null;
}
/**
* Vermerken des übergebenen
* int-Wertes.
*
* @param pValue zu vermerkender Wert
* @return <tt>true</tt> if this set did not already contain the specified
* element.
* @see java.util.Set#add(E)
*/
public boolean add(
final int pValue )
{
Object[] runArr =
this.trieArr;
int bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
final Object[] preRunArr =
runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 1 ] =
runArr;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 0 ] =
runArr;
}
}
bitMask = ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 1 ] =
finalArr;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 0 ] =
finalArr;
}
}
bitMask = ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueNotAlreadyContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueNotAlreadyContain =
!finalArr[ 1 ];
finalArr[ 1 ] = true;
}
else
{
isValueNotAlreadyContain =
! finalArr[ 0 ];
finalArr[ 0 ] = true;
}
if ( isValueNotAlreadyContain )
{
this.size++;
}
return isValueNotAlreadyContain;
}
/**
* Prüfen, ob der übergebene
* int-Wert in diesem Set enthalten ist.
*
* @param pValue zu prüfender Wert
* @return <tt>true</tt> if this set contains the specified element.
* @see java.util.Set#contains(java.lang.Object)
*/
public boolean contains(
final int pValue )
{
Object[] runArr =
this.trieArr;
int bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueContain =
finalArr[ 1 ];
}
else
{
isValueContain =
finalArr[ 0 ];
}
return isValueContain;
}
/**
* Entfernen des übergebenen
* int-Wertes.
*
* @param pValue zu entfernender Wert
* @return true if the set contained the specified element.
* @see java.util.Set#remove(java.lang.Object)
*/
public boolean remove(
final int pValue )
{
Object[] runArr =
this.trieArr;
int bitMask = 1;
final PathElem[] pathArr =
new PathElem[ BIT_COUNT - 2 ];
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
if ( i > 0 )
{
pathArr[ i ] =
new PathElem(
// Achtung es ist wichtig, dass das gleiche
// Array referenziert wird und keine Kopie/Clone
runArr,
isBit ? 1 : 0 );
}
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValuePreviousContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValuePreviousContain =
finalArr[ 1 ];
finalArr[ 1 ] = false;
if ( finalArr[ 0 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
else
{
isValuePreviousContain =
finalArr[ 0 ];
finalArr[ 0 ] = false;
if ( finalArr[ 1 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
if ( isValuePreviousContain )
{
this.size--;
/*
* nicht benutzte Knoten Löschen um Speicher freizugeben
*/
for ( int i = pathArr.length - 1 ; i > 0 ; i-- )
{
final PathElem pathElem =
pathArr[ i ];
final Object[] pathTrieArr =
pathElem.trieArr;
final Object[] subPathTrieArr =
(Object[]) pathTrieArr[
pathElem.trieArrIndex ];
if ( subPathTrieArr[ 0 ] == null && subPathTrieArr[ 1 ] == null )
// das aktuelle Pfad Element ist leer und kann gelöscht werden
{
// final PathElem parentPathElem =
// pathArr[ i - 1 ];
//
// parentPathElem.trieArr[
// parentPathElem.trieArrIndex ]
// = null;
// break;
pathTrieArr[ pathElem.trieArrIndex ] = null;
}
}
}
return isValuePreviousContain;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Objekt-Array.
* @return Array mit allen enthaltenen Werten als Objekte
*/
public Integer[] toObjArray()
{
final int[] shortPrmvArr =
toArray();
final Integer[] retArr =
new Integer[ shortPrmvArr.length ];
for (int i = 0; i < shortPrmvArr.length; i++ )
{
final int tmp = shortPrmvArr[i];
retArr[ i ] =
new Integer( tmp );
}
return retArr;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Array.
* @return Array mit allen enthaltenen Werten
*/
public int[] toArray()
{
final ShortArrAndIndexVo vo =
new ShortArrAndIndexVo(
this.size );
innerToArray(
vo ,
this.trieArr ,
0 ,
0 );
final int[] retArr =
vo.shortArr;
Arrays.sort( retArr );
return retArr;
}
/**
* @param pVo Value-Objekt zum Sammeln der Werte
* @param pTrieArrNode aktueller zu prüfender Knoten
* @param pBitPos Position des aktuell bearbeiteten Bits
* @param pPreValue bisheriger Wert, der an der aktuellen bit-Position um
1 oder 0 erhöht werden muss
*/
private void innerToArray(
final ShortArrAndIndexVo pVo ,
final Object[] pTrieArrNode ,
final int pBitPos ,
final int pPreValue )
{
if ( pTrieArrNode == null )
// Pfad endet hier
{
return;
}
if ( pBitPos < BIT_COUNT - 2 )
// finales Merker-Array noch nicht erreicht
{
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 0 ] ,
pBitPos + 1 ,
pPreValue /* + 0 */ );
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 1 ] ,
pBitPos + 1 ,
pPreValue + (int) Math.pow( 2 , ( pBitPos ) ) );
}
else
// finales Merker-Array erreicht
{
{
final boolean[] finalArr0 =
(boolean[]) pTrieArrNode[ 0 ];
if ( finalArr0 != null )
{
final int preValue =
pPreValue + 0;
if ( finalArr0[ 0 ] )
{
pVo.add(
preValue );
}
if ( finalArr0[ 1 ] )
{
pVo.add(
(int) (
preValue +
Math.pow( 2 , ( BIT_COUNT - 1 ) ) ) );
}
}
}
{
final boolean[] finalArr1 =
(boolean[]) pTrieArrNode[ 1 ];
if ( finalArr1 != null )
{
final int preValue =
pPreValue +
(int) Math.pow( 2 , ( BIT_COUNT - 2 ) );
if ( finalArr1[ 0 ] )
{
pVo.add(
preValue );
}
if ( finalArr1[ 1 ] )
{
pVo.add(
(int) (
preValue +
Math.pow( 2 , BIT_COUNT - 1 ) ) );
}
}
}
}
}
/**
* Value-Objekt mit einem
* int-Array und einem
* Index.
*/
static final class ShortArrAndIndexVo
{
/**
* Array zum Sammeln der Werte
*/
final int[] shortArr;
/**
* aktueller Index
*/
int index;
/**
* Constructor
* @param pSize
*/
public ShortArrAndIndexVo(
final int pSize )
{
super();
this.shortArr =
new int[ pSize ];
}
/**
* Set value at index position
* and increment index.
* @param pValue
*/
public void add(
final int pValue )
{
this.shortArr[ this.index ] =
pValue;
this.index++;
}
}
/**
* Hilfsklasse für ein Element
* des Pfades zu einem Eintrag
* in einem {@link IntTrieSet}.
*
* Wird benutzt in
* {@link IntTrieSet#remove(int)}
*/
static final class PathElem
{
/**
* Sub-Array des Pfades
* innerhalb des Baumes
*/
final Object[] trieArr;
/**
* Index zum nächsten
* hierarchisch tiefergelegenen
* Sub-Array des Pfades
*/
final int trieArrIndex;
/**
* Constructor
* @param pTrieArr
* @param pTrieArrIndex
*/
public PathElem(Object[] pTrieArr, int pTrieArrIndex)
{
super();
// TODO Auto-generated constructor stub
this.trieArr = pTrieArr;
this.trieArrIndex = pTrieArrIndex;
}
/**
* debug output
* @see java.lang.Object#toString()
*/
@Override
public String toString()
{
return
"trieArr: " + Arrays.asList( this.trieArr ) +
"trieArrIndex: " + this.trieArrIndex;
}
}
/**
* @param args
*/
public static void main(
String[] args )
{
final IntTrieSet set = new IntTrieSet();
/*
* add 1
*/
boolean valPrvContain = ! set.add( 1 );
if ( valPrvContain || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 1 ) )
{
throw new TestFailedException();
}
String setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1]" ) )
{
throw new TestFailedException();
}
/*
* add 2
*/
valPrvContain = ! set.add( 2 );
if ( valPrvContain || set.size() != 2 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1, 2]" ) )
{
throw new TestFailedException();
}
/*
* remove 1
*/
valPrvContain = set.remove( 1 );
if ( ( ! valPrvContain ) || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[2]" ) )
{
throw new TestFailedException();
}
/*
* remove 2
*/
valPrvContain = set.remove( 2 );
if ( ( ! valPrvContain ) || set.size() != 0 )
{
throw new TestFailedException();
}
if ( set.contains( 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( 1 ) )
{
throw new TestFailedException();
}
if ( set.contains( 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[]" ) )
{
throw new TestFailedException();
}
}
}
package util.collections.primitve;
import java.util.Arrays;
import de.heinerkuecker.util.TestFailedException;
/**
* Diese experimentelle Klasse
* enthält ein Set von short-Werten
* (Primitiven) welches als
* Trie oder sogenannter
* Patricia-Baum aufgebaut ist.
*
* Dabei wird für jedes Bit
* der zu vermekenden short-Werte
* ein 2-stelliges boolean-Array
* angelegt.
*
* Begonnen wird mit dem
* niederwertigsten Bit.
*
* Je nach dem, ob das
* betrachtete Bit 0 oder
* 1 ist, wird im jeweiligen
* linken oder rechten
* Sub-Array weitergesucht.
*
* Ist das nächste Sub-Array
* null, so sind alle Werte
* ab diesem Bit nicht vorhanden.
*
* Wird das letzte Array erreicht,
* so entscheidet der Zustand
* des Boolean-Merkers, ob
* der entsprechende short-Wert
* vermerkt ist oder nicht.
*
* TODO statt Arrays mit je zwei Einträgen mal mit Arrays mit 4, 8 oder 16
Einträgen testen
*
* @author Heiner Kücker
*/
public class ShortTrieSet
{
public static final int BIT_COUNT = 16;
private Object[] trieArr =
new Object[ 2 ];
private int size;
/**
* Constructor
*/
public ShortTrieSet()
{
super();
}
/**
* Constructor
*/
public ShortTrieSet(
final short[] pShrtArr )
{
super();
addAll( pShrtArr );
}
/**
* @param pShrtArr
*/
public void addAll(
final short[] pShrtArr )
{
for (int i = 0; i < pShrtArr.length; i++ )
{
add( pShrtArr[ i ] );
}
}
/**
* Zurückgeben der Anzahl vermerkter Werte
* @return Anzahl vermerkter Werte
* @see java.util.Set#size()
*/
public int size()
{
return this.size;
}
/**
* Alle vermerkten
* Werte löschen.
*/
public void clear()
{
this.size = 0;
this.trieArr[ 0 ] = null;
this.trieArr[ 1 ] = null;
}
/**
* Vermerken des übergebenen
* short-Wertes.
*
* @param pValue zu vermerkender Wert
* @return <tt>true</tt> if this set did not already contain the specified
* element.
* @see java.util.Set#add(E)
*/
public boolean add(
final short pValue )
{
Object[] runArr =
this.trieArr;
short bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
final Object[] preRunArr =
runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 1 ] =
runArr;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
runArr =
new Object[ 2 ];
preRunArr[ 0 ] =
runArr;
}
}
bitMask = (short) ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 1 ] =
finalArr;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
finalArr =
new boolean[ 2 ];
runArr[ 0 ] =
finalArr;
}
}
bitMask = (short) ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueNotAlreadyContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueNotAlreadyContain =
!finalArr[ 1 ];
finalArr[ 1 ] = true;
}
else
{
isValueNotAlreadyContain =
! finalArr[ 0 ];
finalArr[ 0 ] = true;
}
if ( isValueNotAlreadyContain )
{
this.size++;
}
return isValueNotAlreadyContain;
}
/**
* Prüfen, ob der übergebene
* short-Wert in diesem Set enthalten ist.
*
* @param pValue zu prüfender Wert
* @return <tt>true</tt> if this set contains the specified element.
* @see java.util.Set#contains(java.lang.Object)
*/
public boolean contains(
final short pValue )
{
Object[] runArr =
this.trieArr;
short bitMask = 1;
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValueContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValueContain =
finalArr[ 1 ];
}
else
{
isValueContain =
finalArr[ 0 ];
}
return isValueContain;
}
/**
* Entfernen des übergebenen
* short-Wertes.
*
* @param pValue zu entfernender Wert
* @return true if the set contained the specified element.
* @see java.util.Set#remove(java.lang.Object)
*/
public boolean remove(
final short pValue )
{
Object[] runArr =
this.trieArr;
short bitMask = 1;
final PathElem[] pathArr =
new PathElem[ BIT_COUNT - 2 ];
// TODO umstellen auf abwärts zählen, weil Test auf 0 schneller sein
soll
for (int i = 0; i < BIT_COUNT - 2; i++ )
{
//System.out.println( "bitMask: " + bitMask );
final boolean isBit =
( pValue & bitMask ) != 0;
if ( i > 0 )
{
pathArr[ i ] =
new PathElem(
// Achtung es ist wichtig, dass das gleiche
// Array referenziert wird und keine Kopie/Clone
runArr,
isBit ? 1 : 0 );
}
// final Object[] preRunArr =
// runArr;
if ( isBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
runArr = (Object[]) runArr[ 1 ];
if ( runArr == null )
{
return false;
}
}
else
{
runArr = (Object[]) runArr[ 0 ];
if ( runArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
}
final boolean isPreLastBit =
( pValue & bitMask ) != 0;
boolean[] finalArr;
if ( isPreLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
finalArr = (boolean[]) runArr[ 1 ];
if ( finalArr == null )
{
return false;
}
}
else
{
finalArr = (boolean[]) runArr[ 0 ];
if ( finalArr == null )
{
return false;
}
}
bitMask = (short) ( bitMask << 1 );
final boolean isLastBit =
( pValue & bitMask ) != 0;
final boolean isValuePreviousContain;
if ( isLastBit )
// TODO index-Merker 0 - 1 statt if ( bit )
{
isValuePreviousContain =
finalArr[ 1 ];
finalArr[ 1 ] = false;
if ( finalArr[ 0 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
else
{
isValuePreviousContain =
finalArr[ 0 ];
finalArr[ 0 ] = false;
if ( finalArr[ 1 ] == false )
// beide Einträge sind false, Array kann gelöscht werden
{
runArr[ isPreLastBit ? 1 : 0 ] = null;
}
}
if ( isValuePreviousContain )
{
this.size--;
/*
* nicht benutzte Knoten Löschen um Speicher freizugeben
*/
for ( int i = pathArr.length - 1 ; i > 0 ; i-- )
{
final PathElem pathElem =
pathArr[ i ];
final Object[] pathTrieArr =
pathElem.trieArr;
final Object[] subPathTrieArr =
(Object[]) pathTrieArr[
pathElem.trieArrIndex ];
if ( subPathTrieArr[ 0 ] == null && subPathTrieArr[ 1 ] == null )
// das aktuelle Pfad Element ist leer und kann gelöscht werden
{
// final PathElem parentPathElem =
// pathArr[ i - 1 ];
//
// parentPathElem.trieArr[
// parentPathElem.trieArrIndex ]
// = null;
// break;
pathTrieArr[ pathElem.trieArrIndex ] = null;
}
}
}
return isValuePreviousContain;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Objekt-Array.
* @return Array mit allen enthaltenen Werten als Objekte
*/
public Short[] toObjArray()
{
final short[] shortPrmvArr =
toArray();
final Short[] retArr =
new Short[ shortPrmvArr.length ];
for (int i = 0; i < shortPrmvArr.length; i++ )
{
final short s = shortPrmvArr[i];
retArr[ i ] =
new Short( s );
}
return retArr;
}
/**
* Zurückgeben aller enthaltenen
* Werte als Array.
* @return Array mit allen enthaltenen Werten
*/
public short[] toArray()
{
final ShortArrAndIndexVo vo =
new ShortArrAndIndexVo(
this.size );
innerToArray(
vo ,
this.trieArr ,
0 ,
0 );
final short[] retArr =
vo.shortArr;
Arrays.sort( retArr );
return retArr;
}
/**
* @param pVo Value-Objekt zum Sammeln der Werte
* @param pTrieArrNode aktueller zu prüfender Knoten
* @param pBitPos Position des aktuell bearbeiteten Bits
* @param pPreValue bisheriger Wert, der an der aktuellen bit-Position um
1 oder 0 erhöht werden muss
*/
private void innerToArray(
final ShortArrAndIndexVo pVo ,
final Object[] pTrieArrNode ,
final int pBitPos ,
final int pPreValue )
{
if ( pTrieArrNode == null )
// Pfad endet hier
{
return;
}
if ( pBitPos < BIT_COUNT - 2 )
// finales Merker-Array noch nicht erreicht
{
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 0 ] ,
pBitPos + 1 ,
pPreValue /* + 0 */ );
innerToArray(
pVo ,
(Object[]) pTrieArrNode[ 1 ] ,
pBitPos + 1 ,
pPreValue + (int) Math.pow( 2 , ( pBitPos ) ) );
}
else
// finales Merker-Array erreicht
{
{
final boolean[] finalArr0 =
(boolean[]) pTrieArrNode[ 0 ];
if ( finalArr0 != null )
{
final int preValue =
pPreValue + 0;
if ( finalArr0[ 0 ] )
{
pVo.add(
(short) preValue );
}
if ( finalArr0[ 1 ] )
{
pVo.add(
(short) (
preValue +
Math.pow( 2 , ( BIT_COUNT - 1 ) ) ) );
}
}
}
{
final boolean[] finalArr1 =
(boolean[]) pTrieArrNode[ 1 ];
if ( finalArr1 != null )
{
final int preValue =
pPreValue +
(int) Math.pow( 2 , ( BIT_COUNT - 2 ) );
if ( finalArr1[ 0 ] )
{
pVo.add(
(short) preValue );
}
if ( finalArr1[ 1 ] )
{
pVo.add(
(short) (
preValue +
Math.pow( 2 , BIT_COUNT - 1 ) ) );
}
}
}
}
}
/**
* Value-Objekt mit einem
* short-Array und einem
* Index.
*/
static final class ShortArrAndIndexVo
{
/**
* Array zum Sammeln der Werte
*/
final short[] shortArr;
/**
* aktueller Index
*/
int index;
/**
* Constructor
* @param pSize
*/
public ShortArrAndIndexVo(
final int pSize )
{
super();
this.shortArr =
new short[ pSize ];
}
/**
* Set value at index position
* and increment index.
* @param pValue
*/
public void add(
final short pValue )
{
this.shortArr[ this.index ] =
pValue;
this.index++;
}
}
/**
* Hilfsklasse für ein Element
* des Pfades zu einem Eintrag
* in einem {@link ShortTrieSet}.
*
* Wird benutzt in
* {@link ShortTrieSet#remove(short)}
*/
static final class PathElem
{
/**
* Sub-Array des Pfades
* innerhalb des Baumes
*/
final Object[] trieArr;
/**
* Index zum nächsten
* hierarchisch tiefergelegenen
* Sub-Array des Pfades
*/
final int trieArrIndex;
/**
* Constructor
* @param pTrieArr
* @param pTrieArrIndex
*/
public PathElem(Object[] pTrieArr, int pTrieArrIndex)
{
super();
// TODO Auto-generated constructor stub
this.trieArr = pTrieArr;
this.trieArrIndex = pTrieArrIndex;
}
/**
* debug output
* @see java.lang.Object#toString()
*/
@Override
public String toString()
{
return
"trieArr: " + Arrays.asList( this.trieArr ) +
"trieArrIndex: " + this.trieArrIndex;
}
}
/**
* @param args
*/
public static void main(
String[] args )
{
final ShortTrieSet set = new ShortTrieSet();
/*
* add 1
*/
boolean valPrvContain = ! set.add( (short) 1 );
if ( valPrvContain || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
String setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1]" ) )
{
throw new TestFailedException();
}
/*
* add 2
*/
valPrvContain = ! set.add( (short) 2 );
if ( valPrvContain || set.size() != 2 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[1, 2]" ) )
{
throw new TestFailedException();
}
/*
* remove 1
*/
valPrvContain = set.remove( (short) 1 );
if ( ( ! valPrvContain ) || set.size() != 1 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
if ( ! set.contains( (short) 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[2]" ) )
{
throw new TestFailedException();
}
/*
* remove 2
*/
valPrvContain = set.remove( (short) 2 );
if ( ( ! valPrvContain ) || set.size() != 0 )
{
throw new TestFailedException();
}
if ( set.contains( (short) 0 ) )
{
throw new TestFailedException();
}
if ( set.contains( (short) 1 ) )
{
throw new TestFailedException();
}
if ( set.contains( (short) 2 ) )
{
throw new TestFailedException();
}
setStr = Arrays.asList( set.toObjArray() ).toString();
System.out.println( setStr );
if ( ! setStr.equals( "[]" ) )
{
throw new TestFailedException();
}
}
}
--
Heiner Kücker
www.heinerkuecker.de
www.control-and-command.de