1 /*****************************************************************************
2 * algo.c : Algorithms test
3 *****************************************************************************
4 * Copyright (C) 2006 VideoLAN
5 * $Id: i18n.c 16157 2006-07-29 13:32:12Z zorglub $
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
20 *****************************************************************************/
22 #include "../pyunit.h"
25 /**********************************************************************
27 *********************************************************************/
29 TYPEDEF_ARRAY(long,long_array_t);
31 PyObject *arrays_test( PyObject *self, PyObject *args )
35 int number2 = 50000; /* For slow with memmove */
42 for( i = 0 ; i<number;i++) {
43 INSERT_ELEM(p_items,i_items, i_items, i+50);
46 printf( " Std array %i items appended in "I64Fi" µs\n", number,
48 for( i = number-1 ; i>=0; i--) {
49 REMOVE_ELEM( p_items, i_items, i );
52 printf( " Std array %i items removed in "I64Fi" µs\n", number,
55 for( i = 0 ; i<number2;i++) {
56 int pos = i_items == 0 ? 0 : rand() % i_items;
57 INSERT_ELEM(p_items, i_items, pos, pos + 50);
60 printf( " Std array %i items inserted in "I64Fi" µs\n", number2,
64 DECL_ARRAY(int) int_array;
66 ARRAY_INIT(int_array);
67 ASSERT(int_array.i_size == 0, "" );
68 ASSERT(int_array.i_alloc == 0, "" );
69 ASSERT(int_array.p_elems == 0, "" );
71 ARRAY_APPEND(int_array, 42 );
72 ASSERT(int_array.i_size == 1, "" );
73 ASSERT(int_array.i_alloc > 1, "" );
74 ASSERT(int_array.p_elems[0] == 42, "" );
75 ARRAY_REMOVE(int_array,0);
76 ASSERT(int_array.i_size == 0, "" );
79 for( i = 0 ; i<number;i++) {
80 ARRAY_APPEND(int_array, i+50);
83 printf( " New array %i items appended in "I64Fi" µs\n", number,
85 ASSERT(int_array.p_elems[1242] == 1292 , "");
86 for( i = number-1 ; i>=0; i--) {
87 ARRAY_REMOVE(int_array,i);
90 printf( " New array %i items removed in "I64Fi" µs\n", number,
93 /* Now random inserts */
94 for( i = 0 ; i<number2;i++) {
95 int pos = int_array.i_size == 0 ? 0 : rand() % int_array.i_size;
96 ARRAY_INSERT(int_array, pos+50, pos);
99 printf( " New array %i items inserted in "I64Fi" µs\n", number2,
110 /**********************************************************************
112 *********************************************************************/
114 PyObject *bsearch_direct_test( PyObject *self, PyObject *args )
116 #define DIRCHECK( size, initial, checked, expected ) { \
117 int array[size] = initial; \
119 BSEARCH( array, size, , int, checked, answer ); \
120 ASSERT( answer == expected , "" ); }
122 #define ORDERED10 {0,1,2,3,4,5,6,7,8,9}
123 DIRCHECK( 10, ORDERED10, 0, 0 );
124 DIRCHECK( 10, ORDERED10, 1, 1 );
125 DIRCHECK( 10, ORDERED10, 2, 2 );
126 DIRCHECK( 10, ORDERED10, 3, 3 );
127 DIRCHECK( 10, ORDERED10, 4, 4 );
128 DIRCHECK( 10, ORDERED10, 5, 5 );
129 DIRCHECK( 10, ORDERED10, 6, 6 );
130 DIRCHECK( 10, ORDERED10, 7, 7 );
131 DIRCHECK( 10, ORDERED10, 8, 8 );
132 DIRCHECK( 10, ORDERED10, 9,9 );
134 DIRCHECK( 10, ORDERED10, 10, -1 );
135 DIRCHECK( 10, ORDERED10, -1, -1 );
137 /* TODO: tests on unordered arrays, odd number of elements, 1 element, 2 */
143 struct bsearch_tester
148 /* Lighter test, we just check correct member access, all the real testing
149 * has been made already */
150 PyObject *bsearch_member_test( PyObject *self, PyObject *args )
152 struct bsearch_tester array[] =
154 { 0, 12 }, { 1, 22 } , { 2, 33 } , { 3, 68 } , { 4, 56 }
156 #define MEMBCHECK( checked, expected ) { \
158 BSEARCH( array, 5, .key , int, checked, answer ); \
159 ASSERT( answer == expected , "" ); }
172 /**********************************************************************
174 *********************************************************************/
175 DICT_TYPE( test, int );
177 static void DumpDict( dict_test_t *p_dict )
180 fprintf( stderr, "**** Begin Dump ****\n" );
181 for( i = 0 ; i < p_dict->i_entries; i++ )
183 fprintf( stderr, "Entry %i - hash %lli int %i string %s data %i\n",
184 i, p_dict->p_entries[i].i_hash,
185 p_dict->p_entries[i].i_int,
186 p_dict->p_entries[i].psz_string,
187 p_dict->p_entries[i].data );
189 fprintf( stderr, "**** End Dump ****\n" );
192 PyObject *dict_test( PyObject *self, PyObject *args )
194 int i42 = 42,i40 = 40,i12 = 12, i0 = 0, i00 = 0;
201 ASSERT( p_dict->i_entries == 0, "" );
202 ASSERT( p_dict->p_entries == NULL, "" );
204 DICT_INSERT( p_dict, 0, NULL, i42 );
205 ASSERT( p_dict->i_entries == 1, "" );
206 ASSERT( p_dict->p_entries[0].data == i42, "" );
208 DICT_INSERT( p_dict, 1, "42", i42 );
209 ASSERT( p_dict->i_entries == 2, "" );
211 DICT_LOOKUP( p_dict, 1, "42", answer );
212 DICT_GET( p_dict, 1, "42", answer );
213 ASSERT( answer == i42, "" );
214 DICT_LOOKUP( p_dict, 0, "42", answer ); ASSERT( answer == -1, "" );
215 DICT_LOOKUP( p_dict, 1, " 42", answer ); ASSERT( answer == -1, "" );
217 DICT_INSERT( p_dict, 1, "12", i12 );
218 DICT_GET( p_dict, 1, "12", answer ) ; ASSERT( answer == i12, "" );
220 DICT_INSERT( p_dict, 3, "40", i40 );
221 DICT_GET( p_dict, 1, "42", answer ); ASSERT( answer == i42, "" );
222 DICT_GET( p_dict, 3, "40", answer ); ASSERT( answer == i40, "" );
223 DICT_GET( p_dict, 1, "12", answer ); ASSERT( answer == i12, "" );
225 DICT_INSERT( p_dict, 12, "zero-1", i0 );
226 DICT_INSERT( p_dict, 5, "zero-0", i00 );
227 DICT_GET( p_dict, 12, "zero-1", answer ); ASSERT( answer == i0, "" );
228 DICT_GET( p_dict, 5, "zero-0", answer ); ASSERT( answer == i00, "" );
230 DICT_GET( p_dict, 12, "zero-0", answer ); ASSERT( answer == -1, "" );
231 DICT_GET( p_dict, 1, "12", answer ); ASSERT( answer == i12, "" );
233 DICT_INSERT( p_dict, 0, "zero", 17 );
234 DICT_GET( p_dict, 1, "12", answer ); ASSERT( answer == i12, "" );
235 DICT_GET( p_dict, 12, "zero-1", answer ); ASSERT( answer == i0, "" );
236 DICT_GET( p_dict, 0, "zero", answer ); ASSERT( answer == 17, "" );
238 DICT_INSERT( p_dict, 0, "12", i12 );
239 DICT_INSERT( p_dict, 0, "thisisaverylongstringwith12", i12 );
241 DICT_GET( p_dict, 0, "thisisaverylongstringwith12", answer );
242 ASSERT( answer == i12, "" );
244 DICT_GET( p_dict, 0, "thisisaverylongstringwith13", answer );
245 ASSERT( answer == -1, "" );
247 DICT_CLEAR( p_dict );