1 files changed, 249 insertions, 0 deletions
diff --git a/src/array_base.c b/src/array_base.c
new file mode 100644
index 0000000..a70bd86
--- /dev/null
+++ b/src/array_base.c
@@ -0,0 +1,249 @@
+/*
+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