// Copyright (c) 1994-2009 Nokia Corporation and/or its subsidiary(-ies).
// All rights reserved.
// This component and the accompanying materials are made available
// under the terms of the License "Eclipse Public License v1.0"
// which accompanies this distribution, and is available
// at the URL "http://www.eclipse.org/legal/epl-v10.html".
//
// Initial Contributors:
// Nokia Corporation - initial contribution.
//
// Contributors:
//
// Description:
// e32test\buffer\bin_srch.cpp
// 
//

#include <e32test.h>
#include <e32math.h>

GLREF_D RTest test;

#define KEEP_RUNNING	100

struct TestMe
	{
	TBuf<0x10>	name;
	TInt32		key1;
	TUint32		key2;
	};

LOCAL_C void fillArray(RArray<TestMe>& arr, TInt size)
	{
	TInt32 seed = 1 + Math::Random() % size;
	TestMe testMe;
	for(TInt i=0;i<size;i++)
		{
		testMe.key1 = seed;
		arr.Append(testMe);
		seed += 2 + Math::Random() % (2 + size%5);
		}

	}

LOCAL_C void fillArray(RArray<TInt32>& arr, TInt size)
	{
	TInt32 seed = 1 + Math::Random() % size;
	for(TInt i=0;i<size;i++)
		{
		arr.Append(seed);
		seed += 2 + Math::Random() % (2 + size%5);
		}
	}

LOCAL_C void fillArray(RArray<TInt32>& arr, RPointerArray<TUint32>& parr, TInt size)
	{
	TInt32 seed = 1 + Math::Random() % size;
	TInt i;
	for(i=0;i<size;i++)
		{
		arr.Append(seed);
		seed += 2 + Math::Random() % (2 + size%5);
		}
	for(i=0;i<size;i++)
		{
		parr.Append((const TUint32*)&arr[i]);
		}
	}

LOCAL_C void fillArray(RPointerArray<TUint32>& arr, TInt size)
	{
	TUint32 seed = 1 + Math::Random() % size;
	TUint32 dummy;
	for(TInt i=0;i<size;i++)
		{
		arr.Append((&dummy) + seed);
		seed += 2 + Math::Random() % (2 + size%5);
		}
	}

LOCAL_C TInt simpleOrder(const TInt32& a1, const TInt32& a2)
	{
	return a1 - a2;
	}

LOCAL_C TInt simpleOrder2(const TUint32& a1, const TUint32& a2)
	{
	return (a1==a2)?0:(a1>a2?1:-1);
	}

GLDEF_C void DoRArrayTests()
	{
	{
	RArray<TInt32>* rArr1 = new RArray<TInt32>(0x10);
	test(rArr1!=NULL);
	RPointerArray<TUint32>* rpArr1 = new RPointerArray<TUint32>(0x10);
	test(rpArr1!=NULL);
	TInt i;
	TInt size = 25;
	test.Next(_L("Testing RArray::FindInOrder, RPointerArray::FindInOrder, RArrayBase::BinarySearch and RPointerArrayBase::BinarySearch with arrays of different sizes\r\n"));
	for(i=0;i<KEEP_RUNNING;i++)
		{
		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
		fillArray(*rArr1,*rpArr1,size);
		test(rArr1->Count()==rpArr1->Count());
		TInt index;
		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
		test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](0)-1,index,TLinearOrder<TInt32>(simpleOrder)));
		test(index==0);
		TUint32 t = *rpArr1->operator[](0)-1;
		test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
		test(index==0);
		for(TInt k=0;k<rArr1->Count();k++)
			{
			test(KErrNone==rArr1->FindInOrder(rArr1->operator[](k),index,TLinearOrder<TInt32>(simpleOrder)));
			test(index==k);
			test(KErrNone==rpArr1->FindInOrder(rpArr1->operator[](k),index,TLinearOrder<TUint32>(simpleOrder2)));
			test(index==k);
			if(k<rArr1->Count()-1)
				{
				test(KErrNotFound==rArr1->FindInOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index,TLinearOrder<TInt32>(simpleOrder)));
				test(index==k+1);
				t = (*rpArr1->operator[](k)+*rpArr1->operator[](k+1))>>1;
				test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
				test(index==k+1);
				}
			}
		test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](rArr1->Count()-1)+5,index,TLinearOrder<TInt32>(simpleOrder)));
		test(index==rArr1->Count());
		t = *rpArr1->operator[](rpArr1->Count()-1) + 5;
		test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
		test(index==rpArr1->Count());
		size += 2 + Math::Random() % (2 + size%5);
		rArr1->Reset();
		rpArr1->Reset();
		}
	delete rpArr1;

	test.Next(_L("Testing RArray::FindInSignedKeyOrder and RArrayBase::BinarySignedSearch with arrays of different sizes\r\n"));	
	for(i=0;i<KEEP_RUNNING;i++)
		{
		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
		fillArray(*rArr1,size);
		TInt index;
		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
		test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](0)-1,index));
		test(index==0);
		for(TInt k=0;k<rArr1->Count();k++)
			{
			test(KErrNone==rArr1->FindInSignedKeyOrder(rArr1->operator[](k),index));
			test(index==k);
			if(k<rArr1->Count()-1)
				{
				test(KErrNotFound==rArr1->FindInSignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));
				test(index==k+1);
				}
			}
		test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
		test(index==rArr1->Count());
		size += 2 + Math::Random() % (2 + size%5);
		rArr1->Reset();
		}

	size=25;
	test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));	
	for(i=0;i<KEEP_RUNNING;i++)
		{
		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
		fillArray(*rArr1,size);
		TInt index;
		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](0)-1,index));
		test(index==0);
		for(TInt k=0;k<rArr1->Count();k++)
			{
			test(KErrNone==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](k),index));
			test(index==k);
			if(k<rArr1->Count()-1)
				{
				test(KErrNotFound==rArr1->FindInUnsignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));
				test(index==k+1);
				}
			}
		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
		test(index==rArr1->Count());
		size += 2 + Math::Random() % (2 + size%5);
		rArr1->Reset();
		}
	delete rArr1;
	}

	{
	RArray<TestMe>* rArr1 = new RArray<TestMe>(0x10,_FOFF(TestMe,key1));
	test(rArr1!=NULL);
	TInt i;
	TInt size = 25;
	test.Next(_L("Testing RArray::FindInSignedOrder and RArrayBase::BinarySignedSearch with a structure + key\r\n"));
	TestMe testMe;
	for(i=0;i<KEEP_RUNNING;i++)
		{
		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
		fillArray(*rArr1,size);
		TInt index;
		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
		testMe=rArr1->operator[](0);
		testMe.key1 = rArr1->operator[](0).key1-1;
		test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
		test(index==0);
		for(TInt k=0;k<rArr1->Count();k++)
			{
			testMe.key1 = rArr1->operator[](k).key1;
			test(KErrNone==rArr1->FindInSignedKeyOrder(testMe,index));
			test(index==k);
			if(k<rArr1->Count()-1)
				{
				testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;
				test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
				test(index==k+1);
				}
			}
		testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;
		test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
		test(index==rArr1->Count());
		size += 2 + Math::Random() % (2 + size%5);
		rArr1->Reset();
		}

	size=25;
	test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));	
	for(i=0;i<KEEP_RUNNING;i++)
		{
		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
		fillArray(*rArr1,size);
		TInt index;
		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
		testMe.key1 = rArr1->operator[](0).key1-1;
		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
		test(index==0);
		for(TInt k=0;k<rArr1->Count();k++)
			{
			testMe.key1 = rArr1->operator[](k).key1;
			test(KErrNone==rArr1->FindInUnsignedKeyOrder(testMe,index));
			test(index==k);
			if(k<rArr1->Count()-1)
				{
				testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;
				test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
				test(index==k+1);
				}
			}
		testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;
		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
		test(index==rArr1->Count());
		size += 2 + Math::Random() % (2 + size%5);
		rArr1->Reset();
		}
	delete rArr1;
	}

	{
	RPointerArray<TUint32>* rArr1 = new RPointerArray<TUint32>(0x10);
	test(rArr1!=NULL);
	TInt i;
	TInt size = 25;
	test.Next(_L("Testing RPointerArray::FindInAddressOrder and RPointerArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));
	for(i=0;i<KEEP_RUNNING;i++)
		{
		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
		fillArray(*rArr1,size);
		TInt index;
		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
		test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](0)-1,index));
		test(index==0);
		for(TInt k=0;k<rArr1->Count();k++)
			{
			test(KErrNone==rArr1->FindInAddressOrder(rArr1->operator[](k),index));
			test(index==k);
			if(k<rArr1->Count()-1)
				{
				test(KErrNotFound==rArr1->FindInAddressOrder((const TUint32*)(((TUint32)rArr1->operator[](k))/2+((TUint32)rArr1->operator[](k+1))/2 + (((TUint32)rArr1->operator[](k))%2 + ((TUint32)rArr1->operator[](k+1))%2)/2),index));
				test(index==k+1);
				}
			}
		test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
		test(index==rArr1->Count());
		size += 2 + Math::Random() % (2 + size%5);
		rArr1->Reset();
		}

	delete rArr1;
	}

	}