help on JOIN algorithm

Yupp, here is my implementations. merge=UNION, difference=NOT

public static Comparable[] mergeObjects(Comparable[] _o1, Comparable[] _o2){

//<check if any of the sets are empty>

if(_o1==null || _o1.length<=0) return _o2;

if(_o2==null || _o2.length<=0) return _o1;

Arrays.sort(_o1);

Arrays.sort(_o2);

return mergeSortedObjects(_o1,_o2);

}

public static Comparable[] mergeSortedObjects(Comparable[][] _objects){

if(_objects==null || _objects.length<=0) return null;

Comparable[] result=_objects[0];

for(int i=1; i<_objects.length; i++){

result=mergeSortedObjects(result, _objects[i]);

}

return result;

}

public static Comparable[] mergeSortedObjects(Comparable[] _o1, Comparable[] _o2){

//<check if any of the sets are empty>

if(_o1==null || _o1.length<=0) return _o2;

if(_o2==null || _o2.length<=0) return _o1;

//<declare new String[] to store result>

Comparable[] newData=new Comparable[_o1.length+_o2.length];

int nrNewData=0;

//<chose data with least maxValue>

int lowerPos=0;//lower

int lowerNrData;

Comparable[] lowerData;

int higherPos=0;//higher

int higherNrData;

Comparable[] higherData;

int lastCompare=_o1[_o1.length-1].compareTo(_o2[_o2.length-1]);

if(lastCompare<0){//_o1<_o2

lowerData=_o1;

lowerNrData=_o1.length;

higherData=_o2;

higherNrData=_o2.length;

}else{//_o1>=_02

lowerData=_o2;

lowerNrData=_o2.length;

higherData=_o1;

higherNrData=_o1.length;

}

//<parse through higherData and look at the lowerData

while(lowerPos><lowerNrData && higherPos><higherNrData){

int comp=higherData[higherPos].compareTo(lowerData[lowerPos]);

while(comp><0){

newData[nrNewData++]=higherData[higherPos++];

comp=higherData[higherPos].compareTo(lowerData[lowerPos]);

}

if(comp==0){//==

higherPos++;//match => take just one and skip this

}else{

//do nothing

}

newData[nrNewData++]= lowerData[lowerPos++];

}

//<take the rest from higherdata>

for(int i=higherPos; i<higherNrData; i++){

newData[nrNewData++]= higherData[i];

}

Class componentType=_o1[0].getClass();

Comparable[] res=(Comparable[])java.lang.reflect.Array.newInstance(componentType,nrNewData);

System.arraycopy(newData,0,res,0,nrNewData);

return res;

}

public static Comparable[] joinSortedObjects(Comparable[][] _objects){

if(_objects==null || _objects.length><=0) return null;

Comparable[] result=_objects[0];

for(int i=1; i<_objects.length; i++){

result=joinSorted(result, _objects[i]);

}

return result;

}

/**

* Objects in _o1 and _o2 should be unique

*/

public static Comparable[] join(Comparable[] _o1, Comparable[] _o2){

//<check if any of the sets are empty>

if(_o1==null || _o2==null) return null;

if(_o1.length<=0 || _o2.length<=0){

return (Comparable[])Array.newInstance(_o1.getClass().getComponentType(),0); //of the right Class

}

Arrays.sort(_o1);

Arrays.sort(_o2);

return joinSorted(_o1,_o2);

}

public static Comparable[] joinSorted(Comparable[] _o1, Comparable[] _o2){

if(_o1==null || _o2==null) return null;

if(_o1.length<=0 || _o2.length<=0){

return (Comparable[])Array.newInstance(_o1.getClass().getComponentType(),0); //of the right Class

}

//<declare new Comparable[] to store result>

Comparable[] newData=new Comparable[(_o1.length<_o2.length ? _o1.length : _o2.length)];

int nrNewData=0;

//<chose data with least maxValue>

int lowerPos=0;//lower

Comparable[] lowerData;

int higherPos=0;//higher

Comparable[] higherData;

if(_o1[_o1.length-1].compareTo(_o2[_o2.length-1])<0){//_o1<_o2

lowerData=_o1;

higherData=_o2;

}else{//_o1>=_02

lowerData=_o2;

higherData=_o1;

}

//<parse through higherData and look at the lowerData

while(lowerPos><lowerData.length && higherPos><higherData.length){

int comp=higherData[higherPos].compareTo(lowerData[lowerPos]);

while(comp><0){

comp=higherData[++higherPos].compareTo(lowerData[lowerPos]);

}

if(comp==0){//==

newData[nrNewData++]=higherData[higherPos];

higherPos++;//match => take one and skip to next position of higherData

}

lowerPos++;

}

//<skip the rest from higherdata>

//<return result>

Comparable[] result=(Comparable[])java.lang.reflect.Array.newInstance(_o1[0].getClass(),nrNewData); //of the right Class

System.arraycopy(newData,0,result,0,nrNewData);

return result;

}

/**

* Objects in _o1 and _o2 should be unique

* @return _o1-_o2

*/

public static Comparable[] difference(Comparable[] _o1, Comparable[] _o2){

//<check if any of the sets are empty>

if(_o1==null||_o1.length<=0) return _o1;

if(_o2==null || _o2.length<=0) return _o1;

Arrays.sort(_o1);

Arrays.sort(_o2);

//<declare new Comparable[] to store result>

Comparable[] newData=new Comparable[_o1.length];//max length

int nrNewData=0;

int o2Index=0;

int i=0;

for (; i < _o1.length; i++) {

int comp=_o1[i].compareTo(_o2[o2Index]);

while(comp>0){//o2 is less than o1

o2Index++;

if(o2Index<_o2.length){

comp=_o1[i].compareTo(_o2[o2Index]);

}else{

break;

}

}

if(o2Index<_o2.length){

if(comp<0){//else skip _o1[i]

newData[nrNewData++]=_o1[i];

}

}else{

break;

}

}

//take the rest

for(;i<_o1.length; i++){

newData[nrNewData++]=_o1[i];

}

//<return result>

Comparable[] result=(Comparable[])java.lang.reflect.Array.newInstance(_o1[0].getClass(),nrNewData); //of the right Class

System.arraycopy(newData,0,result,0,nrNewData);

return result;

}

Gil

gilroittoa at 2007-7-16 1:19:15 >