1 // Copyright (c) 1994-2009 Nokia Corporation and/or its subsidiary(-ies).

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32test\buffer\bin_srch.cpp

    15 // 

    16 //

    17 

    18 #include <e32test.h>

    19 #include <e32math.h>

    20 

    21 GLREF_D RTest test;

    22 

    23 #define KEEP_RUNNING	100

    24 

    25 struct TestMe

    26 	{

    27 	TBuf<0x10>	name;

    28 	TInt32		key1;

    29 	TUint32		key2;

    30 	};

    31 

    32 LOCAL_C void fillArray(RArray<TestMe>& arr, TInt size)

    33 	{

    34 	TInt32 seed = 1 + Math::Random() % size;

    35 	TestMe testMe;

    36 	for(TInt i=0;i<size;i++)

    37 		{

    38 		testMe.key1 = seed;

    39 		arr.Append(testMe);

    40 		seed += 2 + Math::Random() % (2 + size%5);

    41 		}

    42 

    43 	}

    44 

    45 LOCAL_C void fillArray(RArray<TInt32>& arr, TInt size)

    46 	{

    47 	TInt32 seed = 1 + Math::Random() % size;

    48 	for(TInt i=0;i<size;i++)

    49 		{

    50 		arr.Append(seed);

    51 		seed += 2 + Math::Random() % (2 + size%5);

    52 		}

    53 	}

    54 

    55 LOCAL_C void fillArray(RArray<TInt32>& arr, RPointerArray<TUint32>& parr, TInt size)

    56 	{

    57 	TInt32 seed = 1 + Math::Random() % size;

    58 	TInt i;

    59 	for(i=0;i<size;i++)

    60 		{

    61 		arr.Append(seed);

    62 		seed += 2 + Math::Random() % (2 + size%5);

    63 		}

    64 	for(i=0;i<size;i++)

    65 		{

    66 		parr.Append((const TUint32*)&arr[i]);

    67 		}

    68 	}

    69 

    70 LOCAL_C void fillArray(RPointerArray<TUint32>& arr, TInt size)

    71 	{

    72 	TUint32 seed = 1 + Math::Random() % size;

    73 	TUint32 dummy;

    74 	for(TInt i=0;i<size;i++)

    75 		{

    76 		arr.Append((&dummy) + seed);

    77 		seed += 2 + Math::Random() % (2 + size%5);

    78 		}

    79 	}

    80 

    81 LOCAL_C TInt simpleOrder(const TInt32& a1, const TInt32& a2)

    82 	{

    83 	return a1 - a2;

    84 	}

    85 

    86 LOCAL_C TInt simpleOrder2(const TUint32& a1, const TUint32& a2)

    87 	{

    88 	return (a1==a2)?0:(a1>a2?1:-1);

    89 	}

    90 

    91 GLDEF_C void DoRArrayTests()

    92 	{

    93 	{

    94 	RArray<TInt32>* rArr1 = new RArray<TInt32>(0x10);

    95 	test(rArr1!=NULL);

    96 	RPointerArray<TUint32>* rpArr1 = new RPointerArray<TUint32>(0x10);

    97 	test(rpArr1!=NULL);

    98 	TInt i;

    99 	TInt size = 25;

   100 	test.Next(_L("Testing RArray::FindInOrder, RPointerArray::FindInOrder, RArrayBase::BinarySearch and RPointerArrayBase::BinarySearch with arrays of different sizes\r\n"));

   101 	for(i=0;i<KEEP_RUNNING;i++)

   102 		{

   103 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);

   104 		fillArray(*rArr1,*rpArr1,size);

   105 		test(rArr1->Count()==rpArr1->Count());

   106 		TInt index;

   107 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));

   108 		test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](0)-1,index,TLinearOrder<TInt32>(simpleOrder)));

   109 		test(index==0);

   110 		TUint32 t = *rpArr1->operator[](0)-1;

   111 		test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));

   112 		test(index==0);

   113 		for(TInt k=0;k<rArr1->Count();k++)

   114 			{

   115 			test(KErrNone==rArr1->FindInOrder(rArr1->operator[](k),index,TLinearOrder<TInt32>(simpleOrder)));

   116 			test(index==k);

   117 			test(KErrNone==rpArr1->FindInOrder(rpArr1->operator[](k),index,TLinearOrder<TUint32>(simpleOrder2)));

   118 			test(index==k);

   119 			if(k<rArr1->Count()-1)

   120 				{

   121 				test(KErrNotFound==rArr1->FindInOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index,TLinearOrder<TInt32>(simpleOrder)));

   122 				test(index==k+1);

   123 				t = (*rpArr1->operator[](k)+*rpArr1->operator[](k+1))>>1;

   124 				test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));

   125 				test(index==k+1);

   126 				}

   127 			}

   128 		test(KErrNotFound==rArr1->FindInOrder(rArr1->operator[](rArr1->Count()-1)+5,index,TLinearOrder<TInt32>(simpleOrder)));

   129 		test(index==rArr1->Count());

   130 		t = *rpArr1->operator[](rpArr1->Count()-1) + 5;

   131 		test(KErrNotFound==rpArr1->FindInOrder(&t,index,TLinearOrder<TUint32>(simpleOrder2)));

   132 		test(index==rpArr1->Count());

   133 		size += 2 + Math::Random() % (2 + size%5);

   134 		rArr1->Reset();

   135 		rpArr1->Reset();

   136 		}

   137 	delete rpArr1;

   138 

   139 	test.Next(_L("Testing RArray::FindInSignedKeyOrder and RArrayBase::BinarySignedSearch with arrays of different sizes\r\n"));	

   140 	for(i=0;i<KEEP_RUNNING;i++)

   141 		{

   142 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);

   143 		fillArray(*rArr1,size);

   144 		TInt index;

   145 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));

   146 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](0)-1,index));

   147 		test(index==0);

   148 		for(TInt k=0;k<rArr1->Count();k++)

   149 			{

   150 			test(KErrNone==rArr1->FindInSignedKeyOrder(rArr1->operator[](k),index));

   151 			test(index==k);

   152 			if(k<rArr1->Count()-1)

   153 				{

   154 				test(KErrNotFound==rArr1->FindInSignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));

   155 				test(index==k+1);

   156 				}

   157 			}

   158 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));

   159 		test(index==rArr1->Count());

   160 		size += 2 + Math::Random() % (2 + size%5);

   161 		rArr1->Reset();

   162 		}

   163 

   164 	size=25;

   165 	test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));	

   166 	for(i=0;i<KEEP_RUNNING;i++)

   167 		{

   168 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);

   169 		fillArray(*rArr1,size);

   170 		TInt index;

   171 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));

   172 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](0)-1,index));

   173 		test(index==0);

   174 		for(TInt k=0;k<rArr1->Count();k++)

   175 			{

   176 			test(KErrNone==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](k),index));

   177 			test(index==k);

   178 			if(k<rArr1->Count()-1)

   179 				{

   180 				test(KErrNotFound==rArr1->FindInUnsignedKeyOrder((rArr1->operator[](k)+rArr1->operator[](k+1))>>1,index));

   181 				test(index==k+1);

   182 				}

   183 			}

   184 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(rArr1->operator[](rArr1->Count()-1)+5,index));

   185 		test(index==rArr1->Count());

   186 		size += 2 + Math::Random() % (2 + size%5);

   187 		rArr1->Reset();

   188 		}

   189 	delete rArr1;

   190 	}

   191 

   192 	{

   193 	RArray<TestMe>* rArr1 = new RArray<TestMe>(0x10,_FOFF(TestMe,key1));

   194 	test(rArr1!=NULL);

   195 	TInt i;

   196 	TInt size = 25;

   197 	test.Next(_L("Testing RArray::FindInSignedOrder and RArrayBase::BinarySignedSearch with a structure + key\r\n"));

   198 	TestMe testMe;

   199 	for(i=0;i<KEEP_RUNNING;i++)

   200 		{

   201 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);

   202 		fillArray(*rArr1,size);

   203 		TInt index;

   204 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));

   205 		testMe=rArr1->operator[](0);

   206 		testMe.key1 = rArr1->operator[](0).key1-1;

   207 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));

   208 		test(index==0);

   209 		for(TInt k=0;k<rArr1->Count();k++)

   210 			{

   211 			testMe.key1 = rArr1->operator[](k).key1;

   212 			test(KErrNone==rArr1->FindInSignedKeyOrder(testMe,index));

   213 			test(index==k);

   214 			if(k<rArr1->Count()-1)

   215 				{

   216 				testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;

   217 				test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));

   218 				test(index==k+1);

   219 				}

   220 			}

   221 		testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;

   222 		test(KErrNotFound==rArr1->FindInSignedKeyOrder(testMe,index));

   223 		test(index==rArr1->Count());

   224 		size += 2 + Math::Random() % (2 + size%5);

   225 		rArr1->Reset();

   226 		}

   227 

   228 	size=25;

   229 	test.Next(_L("Testing RArray::FindInUnsignedKeyOrder and RArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));	

   230 	for(i=0;i<KEEP_RUNNING;i++)

   231 		{

   232 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);

   233 		fillArray(*rArr1,size);

   234 		TInt index;

   235 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));

   236 		testMe.key1 = rArr1->operator[](0).key1-1;

   237 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));

   238 		test(index==0);

   239 		for(TInt k=0;k<rArr1->Count();k++)

   240 			{

   241 			testMe.key1 = rArr1->operator[](k).key1;

   242 			test(KErrNone==rArr1->FindInUnsignedKeyOrder(testMe,index));

   243 			test(index==k);

   244 			if(k<rArr1->Count()-1)

   245 				{

   246 				testMe.key1 = (rArr1->operator[](k).key1+rArr1->operator[](k+1).key1)>>1;

   247 				test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));

   248 				test(index==k+1);

   249 				}

   250 			}

   251 		testMe.key1 = rArr1->operator[](rArr1->Count()-1).key1+5;

   252 		test(KErrNotFound==rArr1->FindInUnsignedKeyOrder(testMe,index));

   253 		test(index==rArr1->Count());

   254 		size += 2 + Math::Random() % (2 + size%5);

   255 		rArr1->Reset();

   256 		}

   257 	delete rArr1;

   258 	}

   259 

   260 	{

   261 	RPointerArray<TUint32>* rArr1 = new RPointerArray<TUint32>(0x10);

   262 	test(rArr1!=NULL);

   263 	TInt i;

   264 	TInt size = 25;

   265 	test.Next(_L("Testing RPointerArray::FindInAddressOrder and RPointerArrayBase::BinaryUnsignedSearch with arrays of different sizes\r\n"));

   266 	for(i=0;i<KEEP_RUNNING;i++)

   267 		{

   268 		test.Printf(_L("Testing with a random array of size %d \r\n"), size);

   269 		fillArray(*rArr1,size);

   270 		TInt index;

   271 		//test(KErrNotFound==rArr1->BinarySearch((TAny*)(rArr1->operator[](0)-1),index,(TGeneralLinearOrder)simpleOrder));

   272 		test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](0)-1,index));

   273 		test(index==0);

   274 		for(TInt k=0;k<rArr1->Count();k++)

   275 			{

   276 			test(KErrNone==rArr1->FindInAddressOrder(rArr1->operator[](k),index));

   277 			test(index==k);

   278 			if(k<rArr1->Count()-1)

   279 				{

   280 				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));

   281 				test(index==k+1);

   282 				}

   283 			}

   284 		test(KErrNotFound==rArr1->FindInAddressOrder(rArr1->operator[](rArr1->Count()-1)+5,index));

   285 		test(index==rArr1->Count());

   286 		size += 2 + Math::Random() % (2 + size%5);

   287 		rArr1->Reset();

   288 		}

   289 

   290 	delete rArr1;

   291 	}

   292 

   293 	}