/*
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