1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
|
/*
Copyright 2016 Ian Jauslin
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
/*
Base functions for arrays
see polynomial_*.h for the values taken by ARRAY_FUNC, etc...
*/
// init
int ARRAY_FUNC(init) (ARRAY_TYPENAME* array, unsigned int memory){
array->values=calloc(memory,sizeof(ARRAY_VAL_TYPE));
array->memory=memory;
array->length=0;
return(0);
}
int ARRAY_FUNC(free) (ARRAY_TYPENAME array){
#ifdef ARRAY_VAL_FREE
unsigned int i;
for(i=0;i<array.length;i++){
ARRAY_VAL_FREE(array.values[i]);
}
#endif
free(array.values);
return(0);
}
// do not free values, only free calloc'ed memory
int ARRAY_FUNC(free_vects) (ARRAY_TYPENAME array){
free(array.values);
return(0);
}
// resize memory
int ARRAY_FUNC(resize) (ARRAY_TYPENAME* array, unsigned int newsize){
unsigned int i;
ARRAY_TYPENAME new_array;
ARRAY_FUNC(init) (&new_array, newsize);
for(i=0;i<array->length;i++){
ARRAY_VAL_SET(new_array.values[i], array->values[i]);
}
free(array->values);
*array=new_array;
return(0);
}
// add a value
int ARRAY_FUNC(append) (ARRAY_VAL_TYPE val, ARRAY_TYPENAME* output){
if(output->length >= output->memory){
ARRAY_FUNC(resize) (output,2*output->memory+1);
}
ARRAY_VAL_CPY(val, output->values[output->length]);
output->length++;
return(0);
}
// do not copy the value, instead let the last element of the array point to 'val'
// only if the value requires initializing
#ifdef ARRAY_VAL_FREE
int ARRAY_FUNC(append_noinit) (ARRAY_VAL_TYPE val, ARRAY_TYPENAME* output){
if(output->length >= output->memory){
ARRAY_FUNC(resize) (output,2*output->memory+1);
}
ARRAY_VAL_SET(output->values[output->length], val);
output->length++;
return(0);
}
#endif
// add a value only if it is not already present
#ifdef ARRAY_VAL_IFEQ
int ARRAY_FUNC(append_unique) (ARRAY_VAL_TYPE val, ARRAY_TYPENAME* output){
if(ARRAY_FUNC(find) (val, *output)<0){
ARRAY_FUNC(append) (val, output);
}
return(0);
}
#endif
// copy
int ARRAY_FUNC(cpy) (ARRAY_TYPENAME input, ARRAY_TYPENAME* output){
ARRAY_FUNC(init) (output, input.length);
ARRAY_FUNC(cpy_noinit) (input, output);
return(0);
}
// do not init output array
int ARRAY_FUNC(cpy_noinit) (ARRAY_TYPENAME input, ARRAY_TYPENAME* output){
unsigned int i;
if(output->memory<input.length){
return(LIBINUM_ERROR_SIZE_MISMATCH);
}
for(i=0;i<input.length;i++){
ARRAY_VAL_CPY(input.values[i], output->values[i]);
}
output->length=input.length;
return(0);
}
// concatenate
int ARRAY_FUNC(concat) (ARRAY_TYPENAME input, ARRAY_TYPENAME* output){
unsigned int i;
for(i=0;i<input.length;i++){
ARRAY_FUNC(append) (input.values[i], output);
}
return(0);
}
// concat but only add values that are not already present in the array
#ifdef ARRAY_VAL_IFEQ
int ARRAY_FUNC(concat_unique) (ARRAY_TYPENAME input, ARRAY_TYPENAME* output){
unsigned int i;
for(i=0;i<input.length;i++){
ARRAY_FUNC(append_unique) (input.values[i], output);
}
return(0);
}
#endif
// sub-array
int ARRAY_FUNC(subarray) (ARRAY_TYPENAME array, unsigned int begin, unsigned int end, ARRAY_TYPENAME* subarray){
unsigned int i;
if(begin>end || end>=array.length){
return(LIBINUM_ERROR_ILLEGAL_MEMORY_ACCESS);
}
ARRAY_FUNC(init) (subarray,end-begin);
for(i=begin;i<=end;i++){
ARRAY_FUNC(append) (array.values[i], subarray);
}
return(0);
}
// find (does not assume the array is sorted)
#ifdef ARRAY_VAL_IFEQ
int ARRAY_FUNC(find) (ARRAY_VAL_TYPE val, ARRAY_TYPENAME array){
unsigned int i;
for(i=0;i<array.length;i++){
if(ARRAY_VAL_IFEQ(array.values[i], val)){
return(i);
}
}
return(-1);
}
#endif
// sort (quicksort)
#ifdef ARRAY_VAL_IFLT
int ARRAY_FUNC(sort) (ARRAY_TYPENAME array){
if(array.length>1){
ARRAY_FUNC(sort_sub) (array, 0, array.length-1);
}
return(0);
}
// sort a sub-array
int ARRAY_FUNC(sort_sub) (ARRAY_TYPENAME array, unsigned int begin, unsigned int end){
unsigned int i;
unsigned int index;
ARRAY_VAL_TYPE tmp;
// the pivot: middle of the array
unsigned int pivot=(begin+end)/2;
// if the array is non trivial
if(begin<end){
// send pivot to the end
ARRAY_VAL_SET(tmp, array.values[pivot]);
ARRAY_VAL_SET(array.values[pivot], array.values[end]);
ARRAY_VAL_SET(array.values[end], tmp);
// loop over the others
for(i=begin, index=begin;i<end;i++){
// compare with pivot
if(ARRAY_VAL_IFLT(array.values[i], array.values[end])){
// if smaller, exchange with reference index
ARRAY_VAL_SET(tmp, array.values[index]);
ARRAY_VAL_SET(array.values[index], array.values[i]);
ARRAY_VAL_SET(array.values[i], tmp);
// move reference index
index++;
}
}
// put pivot (which we had sent to the end) in the right place
ARRAY_VAL_SET(tmp, array.values[end]);
ARRAY_VAL_SET(array.values[end], array.values[index]);
ARRAY_VAL_SET(array.values[index], tmp);
// recurse
if(index>0){
ARRAY_FUNC(sort_sub) (array, begin, index-1);
}
ARRAY_FUNC(sort_sub) (array, index+1, end);
}
return(0);
}
#endif
// compare arrays
#if defined ARRAY_VAL_IFLT && defined ARRAY_VAL_IFGT
int ARRAY_FUNC(cmp) (ARRAY_TYPENAME array1, ARRAY_TYPENAME array2){
unsigned int i;
// compare lengths
if(array1.length<array2.length){
return(-1);
}
if(array1.length>array2.length){
return(1);
}
// compare terms
for(i=0;i<array1.length;i++){
if(ARRAY_VAL_IFLT(array1.values[i], array2.values[i])){
return(-1);
}
if(ARRAY_VAL_IFGT(array1.values[i], array2.values[i])){
return(1);
}
}
// if equal
return(0);
}
#endif
// print array
#ifdef ARRAY_VAL_PRINT
int ARRAY_FUNC(print) (ARRAY_TYPENAME array){
unsigned int i;
printf("(");
for(i=0;i<array.length;i++){
ARRAY_VAL_PRINT(array.values[i]);
if(i<array.length-1){
printf(", ");
}
}
printf(")");
return(0);
}
#endif
// allocate memory for values until there are at least 'n' alloacted values
#ifdef ARRAY_VAL_INIT
int ARRAY_FUNC(alloc_tmps) (unsigned int n, ARRAY_TYPENAME* array){
unsigned int i;
// resize if needed
if(array->memory<n){
ARRAY_FUNC(resize)(array, n);
}
for (i=array->length; i<n; i++){
ARRAY_VAL_INIT(array->values+i, 2);
(array->length)++;
}
return(0);
}
#endif
|
