sl@0: // Copyright (c) 1994-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: // All rights reserved.
sl@0: // This component and the accompanying materials are made available
sl@0: // under the terms of the License "Eclipse Public License v1.0"
sl@0: // which accompanies this distribution, and is available
sl@0: // at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: //
sl@0: // Initial Contributors:
sl@0: // Nokia Corporation - initial contribution.
sl@0: //
sl@0: // Contributors:
sl@0: //
sl@0: // Description:
sl@0: // e32test\buffer\bin_srch.cpp
sl@0: // 
sl@0: //
sl@0: 
sl@0: #include <e32test.h>
sl@0: #include <e32math.h>
sl@0: 
sl@0: GLREF_D RTest test;
sl@0: 
sl@0: #define KEEP_RUNNING	100
sl@0: 
sl@0: struct TestMe
sl@0: 	{
sl@0: 	TBuf<0x10>	name;
sl@0: 	TInt32		key1;
sl@0: 	TUint32		key2;
sl@0: 	};
sl@0: 
sl@0: LOCAL_C void fillArray(RArray<TestMe>& arr, TInt size)
sl@0: 	{
sl@0: 	TInt32 seed = 1 + Math::Random() % size;
sl@0: 	TestMe testMe;
sl@0: 	for(TInt i=0;i<size;i++)
sl@0: 		{
sl@0: 		testMe.key1 = seed;
sl@0: 		arr.Append(testMe);
sl@0: 		seed += 2 + Math::Random() % (2 + size%5);
sl@0: 		}
sl@0: 
sl@0: 	}
sl@0: 
sl@0: LOCAL_C void fillArray(RArray<TInt32>& arr, TInt size)
sl@0: 	{
sl@0: 	TInt32 seed = 1 + Math::Random() % size;
sl@0: 	for(TInt i=0;i<size;i++)
sl@0: 		{
sl@0: 		arr.Append(seed);
sl@0: 		seed += 2 + Math::Random() % (2 + size%5);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: LOCAL_C void fillArray(RArray<TInt32>& arr, RPointerArray<TUint32>& parr, TInt size)
sl@0: 	{
sl@0: 	TInt32 seed = 1 + Math::Random() % size;
sl@0: 	TInt i;
sl@0: 	for(i=0;i<size;i++)
sl@0: 		{
sl@0: 		arr.Append(seed);
sl@0: 		seed += 2 + Math::Random() % (2 + size%5);
sl@0: 		}
sl@0: 	for(i=0;i<size;i++)
sl@0: 		{
sl@0: 		parr.Append((const TUint32*)&arr[i]);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: LOCAL_C void fillArray(RPointerArray<TUint32>& arr, TInt size)
sl@0: 	{
sl@0: 	TUint32 seed = 1 + Math::Random() % size;
sl@0: 	TUint32 dummy;
sl@0: 	for(TInt i=0;i<size;i++)
sl@0: 		{
sl@0: 		arr.Append((&dummy) + seed);
sl@0: 		seed += 2 + Math::Random() % (2 + size%5);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: LOCAL_C TInt simpleOrder(const TInt32& a1, const TInt32& a2)
sl@0: 	{
sl@0: 	return a1 - a2;
sl@0: 	}
sl@0: 
sl@0: LOCAL_C TInt simpleOrder2(const TUint32& a1, const TUint32& a2)
sl@0: 	{
sl@0: 	return (a1==a2)?0:(a1>a2?1:-1);
sl@0: 	}
sl@0: 
sl@0: GLDEF_C void DoRArrayTests()
sl@0: 	{
sl@0: 	{
sl@0: 	RArray<TInt32>* rArr1 = new RArray<TInt32>(0x10);
sl@0: 	test(rArr1!=NULL);
sl@0: 	RPointerArray<TUint32>* rpArr1 = new RPointerArray<TUint32>(0x10);
sl@0: 	test(rpArr1!=NULL);
sl@0: 	TInt i;
sl@0: 	TInt size = 25;
sl@0: 	test.Next(_L("Testing RArray::FindInOrder, RPointerArray::FindInOrder, RArrayBase::BinarySearch and RPointerArrayBase::BinarySearch with arrays of different sizes\r\n"));
sl@0: 	for(i=0;i<KEEP_RUNNING;i++)
sl@0: 		{
sl@0: 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
sl@0: 		fillArray(*rArr1,*rpArr1,size);
sl@0: 		test(rArr1->Count()==rpArr1->Count());
sl@0: 		TInt index;
sl@0: 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
sl@0: 		test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](0)-1,index,TLinearOrder<TInt32>(simpleOrder)));
sl@0: 		test(index==0);
sl@0: 		TUint32 t = *rpArr1->operator[](0)-1;
sl@0: 		test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
sl@0: 		test(index==0);
sl@0: 		for(TInt k=0;k<rArr1->Count();k++)
sl@0: 			{
sl@0: 			test(KErrNone==rArr1->FindInOrder(rArr1->operator[](k),index,TLinearOrder<TInt32>(simpleOrder)));
sl@0: 			test(index==k);
sl@0: 			test(KErrNone==rpArr1->FindInOrder(rpArr1->operator[](k),index,TLinearOrder<TUint32>(simpleOrder2)));
sl@0: 			test(index==k);
sl@0: 			if(k<rArr1->Count()-1)
sl@0: 				{
sl@0: 				test(KErrNotFound==rArr1->FindInOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index,TLinearOrder<TInt32>(simpleOrder)));
sl@0: 				test(index==k+1);
sl@0: 				t = (*rpArr1->operator[](k)+*rpArr1->operator[](k+1))>>1;
sl@0: 				test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
sl@0: 				test(index==k+1);
sl@0: 				}
sl@0: 			}
sl@0: 		test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](rArr1->Count()-1)+5,index,TLinearOrder<TInt32>(simpleOrder)));
sl@0: 		test(index==rArr1->Count());
sl@0: 		t = *rpArr1->operator[](rpArr1->Count()-1) + 5;
sl@0: 		test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));
sl@0: 		test(index==rpArr1->Count());
sl@0: 		size += 2 + Math::Random() % (2 + size%5);
sl@0: 		rArr1->Reset();
sl@0: 		rpArr1->Reset();
sl@0: 		}
sl@0: 	delete rpArr1;
sl@0: 
sl@0: 	test.Next(_L("Testing RArray::FindInSignedKeyOrder and RArrayBase::BinarySignedSearch with arrays of different sizes\r\n"));	
sl@0: 	for(i=0;i<KEEP_RUNNING;i++)
sl@0: 		{
sl@0: 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
sl@0: 		fillArray(*rArr1,size);
sl@0: 		TInt index;
sl@0: 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
sl@0: 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](0)-1,index));
sl@0: 		test(index==0);
sl@0: 		for(TInt k=0;k<rArr1->Count();k++)
sl@0: 			{
sl@0: 			test(KErrNone==rArr1->FindInSignedKeyOrder(rArr1->operator[](k),index));
sl@0: 			test(index==k);
sl@0: 			if(k<rArr1->Count()-1)
sl@0: 				{
sl@0: 				test(KErrNotFound==rArr1->FindInSignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));
sl@0: 				test(index==k+1);
sl@0: 				}
sl@0: 			}
sl@0: 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
sl@0: 		test(index==rArr1->Count());
sl@0: 		size += 2 + Math::Random() % (2 + size%5);
sl@0: 		rArr1->Reset();
sl@0: 		}
sl@0: 
sl@0: 	size=25;
sl@0: 	test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));	
sl@0: 	for(i=0;i<KEEP_RUNNING;i++)
sl@0: 		{
sl@0: 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
sl@0: 		fillArray(*rArr1,size);
sl@0: 		TInt index;
sl@0: 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
sl@0: 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](0)-1,index));
sl@0: 		test(index==0);
sl@0: 		for(TInt k=0;k<rArr1->Count();k++)
sl@0: 			{
sl@0: 			test(KErrNone==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](k),index));
sl@0: 			test(index==k);
sl@0: 			if(k<rArr1->Count()-1)
sl@0: 				{
sl@0: 				test(KErrNotFound==rArr1->FindInUnsignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));
sl@0: 				test(index==k+1);
sl@0: 				}
sl@0: 			}
sl@0: 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
sl@0: 		test(index==rArr1->Count());
sl@0: 		size += 2 + Math::Random() % (2 + size%5);
sl@0: 		rArr1->Reset();
sl@0: 		}
sl@0: 	delete rArr1;
sl@0: 	}
sl@0: 
sl@0: 	{
sl@0: 	RArray<TestMe>* rArr1 = new RArray<TestMe>(0x10,_FOFF(TestMe,key1));
sl@0: 	test(rArr1!=NULL);
sl@0: 	TInt i;
sl@0: 	TInt size = 25;
sl@0: 	test.Next(_L("Testing RArray::FindInSignedOrder and RArrayBase::BinarySignedSearch with a structure + key\r\n"));
sl@0: 	TestMe testMe;
sl@0: 	for(i=0;i<KEEP_RUNNING;i++)
sl@0: 		{
sl@0: 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
sl@0: 		fillArray(*rArr1,size);
sl@0: 		TInt index;
sl@0: 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
sl@0: 		testMe=rArr1->operator[](0);
sl@0: 		testMe.key1 = rArr1->operator[](0).key1-1;
sl@0: 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
sl@0: 		test(index==0);
sl@0: 		for(TInt k=0;k<rArr1->Count();k++)
sl@0: 			{
sl@0: 			testMe.key1 = rArr1->operator[](k).key1;
sl@0: 			test(KErrNone==rArr1->FindInSignedKeyOrder(testMe,index));
sl@0: 			test(index==k);
sl@0: 			if(k<rArr1->Count()-1)
sl@0: 				{
sl@0: 				testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;
sl@0: 				test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
sl@0: 				test(index==k+1);
sl@0: 				}
sl@0: 			}
sl@0: 		testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;
sl@0: 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));
sl@0: 		test(index==rArr1->Count());
sl@0: 		size += 2 + Math::Random() % (2 + size%5);
sl@0: 		rArr1->Reset();
sl@0: 		}
sl@0: 
sl@0: 	size=25;
sl@0: 	test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));	
sl@0: 	for(i=0;i<KEEP_RUNNING;i++)
sl@0: 		{
sl@0: 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
sl@0: 		fillArray(*rArr1,size);
sl@0: 		TInt index;
sl@0: 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
sl@0: 		testMe.key1 = rArr1->operator[](0).key1-1;
sl@0: 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
sl@0: 		test(index==0);
sl@0: 		for(TInt k=0;k<rArr1->Count();k++)
sl@0: 			{
sl@0: 			testMe.key1 = rArr1->operator[](k).key1;
sl@0: 			test(KErrNone==rArr1->FindInUnsignedKeyOrder(testMe,index));
sl@0: 			test(index==k);
sl@0: 			if(k<rArr1->Count()-1)
sl@0: 				{
sl@0: 				testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;
sl@0: 				test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
sl@0: 				test(index==k+1);
sl@0: 				}
sl@0: 			}
sl@0: 		testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;
sl@0: 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));
sl@0: 		test(index==rArr1->Count());
sl@0: 		size += 2 + Math::Random() % (2 + size%5);
sl@0: 		rArr1->Reset();
sl@0: 		}
sl@0: 	delete rArr1;
sl@0: 	}
sl@0: 
sl@0: 	{
sl@0: 	RPointerArray<TUint32>* rArr1 = new RPointerArray<TUint32>(0x10);
sl@0: 	test(rArr1!=NULL);
sl@0: 	TInt i;
sl@0: 	TInt size = 25;
sl@0: 	test.Next(_L("Testing RPointerArray::FindInAddressOrder and RPointerArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));
sl@0: 	for(i=0;i<KEEP_RUNNING;i++)
sl@0: 		{
sl@0: 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);
sl@0: 		fillArray(*rArr1,size);
sl@0: 		TInt index;
sl@0: 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));
sl@0: 		test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](0)-1,index));
sl@0: 		test(index==0);
sl@0: 		for(TInt k=0;k<rArr1->Count();k++)
sl@0: 			{
sl@0: 			test(KErrNone==rArr1->FindInAddressOrder(rArr1->operator[](k),index));
sl@0: 			test(index==k);
sl@0: 			if(k<rArr1->Count()-1)
sl@0: 				{
sl@0: 				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));
sl@0: 				test(index==k+1);
sl@0: 				}
sl@0: 			}
sl@0: 		test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](rArr1->Count()-1)+5,index));
sl@0: 		test(index==rArr1->Count());
sl@0: 		size += 2 + Math::Random() % (2 + size%5);
sl@0: 		rArr1->Reset();
sl@0: 		}
sl@0: 
sl@0: 	delete rArr1;
sl@0: 	}
sl@0: 
sl@0: 	}