/*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
*
* Distributable under the terms of either the Apache License (Version 2.0) or
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#ifndef _lucene_util_Arrays_
#define _lucene_util_Arrays_
#if defined(_LUCENE_PRAGMA_ONCE)
# pragma once
#endif
#include "clucene/util/voidlist.h"
CL_NS_DEF(util)
class Arrays{
public:
#if defined (__SYMBIAN32__) && defined (RVCT22_STATICS_WORKAROUND)
template<typename _type>
class _Arrays : LUCENE_BASE {
#else
template<typename _type>
class _Arrays {
#endif
protected:
//used by binarySearch to check for equality
virtual bool equals(_type a,_type b) const = 0;
virtual int32_t compare(_type a,_type b) const = 0;
public:
virtual ~_Arrays(){
}
void sort(_type* a, int32_t alen, int32_t fromIndex, int32_t toIndex) const{
CND_PRECONDITION(fromIndex < toIndex,"fromIndex >= toIndex");
CND_PRECONDITION(fromIndex >= 0,"fromIndex < 0");
// First presort the array in chunks of length 6 with insertion
// sort. A mergesort would give too much overhead for this length.
for (int32_t chunk = fromIndex; chunk < toIndex; chunk += 6)
{
int32_t end = min(chunk + 6, toIndex);
for (int32_t i = chunk + 1; i < end; i++)
{
if (compare(a[i - 1], a[i]) > 0)
{
// not already sorted
int32_t j = i;
_type elem = a[j];
do
{
a[j] = a[j - 1];
j--;
}
while (j > chunk && compare(a[j - 1], elem) > 0);
a[j] = elem;
}
}
}
int32_t len = toIndex - fromIndex;
// If length is smaller or equal 6 we are done.
if (len <= 6)
return;
_type* src = a;
_type* dest = _CL_NEWARRAY(_type,alen);
_type* t = NULL; // t is used for swapping src and dest
// The difference of the fromIndex of the src and dest array.
int32_t srcDestDiff = -fromIndex;
// The merges are done in this loop
for (int32_t size = 6; size < len; size <<= 1)
{
for (int32_t start = fromIndex; start < toIndex; start += size << 1)
{
// mid is the start of the second sublist;
// end the start of the next sublist (or end of array).
int32_t mid = start + size;
int32_t end = min(toIndex, mid + size);
// The second list is empty or the elements are already in
// order - no need to merge
if (mid >= end || compare(src[mid - 1], src[mid]) <= 0)
{
memcpy(dest + start + srcDestDiff, src+start, (end-start)*sizeof(_type));
}// The two halves just need swapping - no need to merge
else if (compare(src[start], src[end - 1]) > 0)
{
memcpy(dest+end-size+srcDestDiff, src+start, size * sizeof(_type));
memcpy(dest+start+srcDestDiff, src+mid, (end-mid) * sizeof(_type));
}else{
// Declare a lot of variables to save repeating
// calculations. Hopefully a decent JIT will put these
// in registers and make this fast
int32_t p1 = start;
int32_t p2 = mid;
int32_t i = start + srcDestDiff;
// The main merge loop; terminates as soon as either
// half is ended
while (p1 < mid && p2 < end)
{
dest[i++] = src[(compare(src[p1], src[p2]) <= 0
? p1++ : p2++)];
}
// Finish up by copying the remainder of whichever half
// wasn't finished.
if (p1 < mid)
memcpy(dest+i,src+p1, (mid-p1) * sizeof(_type));
else
memcpy(dest+i,src+p2, (end-p2) * sizeof(_type));
}
}
// swap src and dest ready for the next merge
t = src;
src = dest;
dest = t;
fromIndex += srcDestDiff;
toIndex += srcDestDiff;
srcDestDiff = -srcDestDiff;
}
// make sure the result ends up back in the right place. Note
// that src and dest may have been swapped above, so src
// contains the sorted array.
if (src != a)
{
// Note that fromIndex == 0.
memcpy(a+srcDestDiff,src,toIndex * sizeof(_type));
}
}
};
};
template <typename _kt, typename _comparator,
typename class1, typename class2>
class CLListEquals:
public CL_NS_STD(binary_function)<class1*,class2*,bool>
{
typedef typename class1::const_iterator _itr1;
typedef typename class2::const_iterator _itr2;
public:
CLListEquals(){
}
bool equals( class1* val1, class2* val2 ) const{
static _comparator comp;
if ( val1 == val2 )
return true;
size_t size = val1->size();
if ( size != val2->size() )
return false;
_itr1 itr1 = val1->begin();
_itr2 itr2 = val2->begin();
//while ( --size >= 0 ){
for(int i=0; i< size; i++){
if ( !comp(*itr1,*itr2) )
return false;
itr1++;
itr2++;
}
return true;
}
};
CL_NS_END
#endif