path: root/src/array.c

/*
Copyright 2015-2022 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.
*/

#include "array.h"
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "istring.h"
#include "definitions.cpp"

// init
int init_Int_Array(Int_Array* array, int memory){
  (*array).values=calloc(memory,sizeof(int));
  (*array).memory=memory;
  (*array).length=0;
  return(0);
}
int free_Int_Array(Int_Array array){
  free(array.values);
  return(0);
}

// copy
int int_array_cpy(Int_Array input, Int_Array* output){
  init_Int_Array(output,input.length);
  int_array_cpy_noinit(input,output);
  return(0);
}
int int_array_cpy_noinit(Int_Array input, Int_Array* output){
  int i;
  if((*output).memory<input.length){
    fprintf(stderr,"error: trying to copy an array of length %d to another with memory %d\n",input.length, (*output).memory);
    exit(-1);
  }
  for(i=0;i<input.length;i++){
    (*output).values[i]=input.values[i];
  }
  (*output).length=input.length;
  return(0);
}

// resize memory
int int_array_resize(Int_Array* array, int newsize){
  Int_Array new_array;
  init_Int_Array(&new_array, newsize);
  int_array_cpy_noinit(*array,&new_array);
  free_Int_Array(*array);
  *array=new_array;
  return(0);
}

// add a value
int int_array_append(int val, Int_Array* output){
  if((*output).length>=(*output).memory){
    int_array_resize(output,2*(*output).memory+1);
  }
  (*output).values[(*output).length]=val;
  (*output).length++;
  return(0);
}

// add a value only if it is not already present
int int_array_append_unique(int val, Int_Array* output){
  if(int_array_find(val,*output)<0){
    int_array_append(val,output);
  }
  return(0);
}

// concatenate
int int_array_concat(Int_Array input, Int_Array* output){
  int i;
  int offset=(*output).length;
  if((*output).length+input.length>(*output).memory){
    // make it longer than needed by (*output).length (for speed)
    int_array_resize(output,2*(*output).length+input.length);
  }
  for(i=0;i<input.length;i++){
    (*output).values[offset+i]=input.values[i];
  }
  (*output).length=offset+input.length;
  return(0);
}

// concat but only add values that are not already present in the array
int int_array_concat_unique(Int_Array input, Int_Array* output){
  int i;
  for(i=0;i<input.length;i++){
    int_array_append_unique(input.values[i],output);
  }
  return(0);
}

// find (does not assume the array is sorted)
int int_array_find(int val, Int_Array array){
  int i;
  for(i=0;i<array.length;i++){
    if(array.values[i]==val){
      return(i);
    }
  }
  return(-1);
}
int int_array_find_err(int val, Int_Array array){
  int i;
  for(i=0;i<array.length;i++){
    if(array.values[i]==val){
      return(i);
    }
  }
  fprintf(stderr,"error: value %d not found in array\n",val);
  exit(-1);
}

// sort
int int_array_sort(Int_Array array, int begin, int end){
  int i;
  int tmp;
  int index;
  // the pivot: middle of the array
  int pivot=(begin+end)/2;
  // if the array is non trivial
  if(begin<end){
    // send pivot to the end
    tmp=array.values[pivot];
    array.values[pivot]=array.values[end];
    array.values[end]=tmp;

    // loop over the others
    for(i=begin, index=begin;i<end;i++){
      // compare with pivot
      if(array.values[i]<array.values[end]){
	// if smaller, exchange with reference index
	tmp=array.values[index];
	array.values[index]=array.values[i];
	array.values[i]=tmp;
	// move reference index
	index++;
      }
    }
    // put pivot (which we had sent to the end) in the right place
    tmp=array.values[end];
    array.values[end]=array.values[index];
    array.values[index]=tmp;

    // recurse
    int_array_sort(array, begin, index-1);
    int_array_sort(array, index+1, end);
  }
  return(0);
}

// compare Int_Array's
int int_array_cmp(Int_Array array1, Int_Array array2){
  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(array1.values[i]<array2.values[i]){
      return(-1);
    }
    if(array1.values[i]>array2.values[i]){
      return(1);
    }
  }

  // if equal
  return(0);
}

// check whether an array is a sub-array of another
// allows for the elements to be separated by others, but the order must be respected
int int_array_is_subarray_ordered(Int_Array input, Int_Array test_array){
  int i;
  int matches=0;

  for(i=0;i<test_array.length && matches<input.length;i++){
    if(input.values[matches]==test_array.values[i]){
      matches++;
    }
  }
  if(matches==input.length){
    return(1);
  }
  else{
    return(0);
  }
}


// print array
int int_array_print(Int_Array array){
  int i;
  printf("(");
  for(i=0;i<array.length-1;i++){
    printf("%d,",array.values[i]);
  }
  if(array.length>0){
    printf("%d)",array.values[array.length-1]);
  }
  else{
    printf(")");
  }
  return(0);
}

// read array
int int_array_read(Char_Array str, Int_Array* array){
  char* buffer=calloc(str.length+1,sizeof(char));
  char* buffer_ptr=buffer;
  int i,j;
  int comment_mode=0;

  // alloc
  init_Int_Array(array,str.length);

  *buffer_ptr='\0';
  // loop over the input
  for(j=0;j<str.length;j++){
    if(comment_mode==1){
      if(str.str[j]=='\n'){
	comment_mode=0;
      }
    }
    else{
      switch(str.str[j]){
      // new term
      case ',':
	// write
	sscanf(buffer,"%d",&i);
	int_array_append(i,array);
	// reset buffer
	buffer_ptr=buffer;
	*buffer_ptr='\0';
	break;

      // ignore
      case '(':break;
      case ')':break;
      // comments
      case '#':
	comment_mode=1;
	break;

      default:
	// write to buffer
	buffer_ptr=str_addchar(buffer_ptr,str.str[j]);
	break;
      }
    }
  }

  // write
  sscanf(buffer,"%d",&i);
  int_array_append(i,array);

  free(buffer);
  return(0);
}


// ------------------- CharArray ------------------------

// init
int init_Char_Array(Char_Array* array, int memory){
  (*array).str=calloc(memory,sizeof(char));
  (*array).memory=memory;
  (*array).length=0;
  return(0);
}
int free_Char_Array(Char_Array array){
  free(array.str);
  return(0);
}

// copy
int char_array_cpy(Char_Array input, Char_Array* output){
  init_Char_Array(output,input.length+1);
  char_array_cpy_noinit(input,output);
  return(0);
}
int char_array_cpy_noinit(Char_Array input, Char_Array* output){
  int i;
  if((*output).memory<input.length){
    fprintf(stderr,"error: trying to copy an array of length %d to another with memory %d\n",input.length, (*output).memory);
    exit(-1);
  }
  for(i=0;i<input.length;i++){
    (*output).str[i]=input.str[i];
  }
  (*output).length=input.length;
  return(0);
}

// resize memory
int char_array_resize(Char_Array* array, int newsize){
  Char_Array new_array;
  init_Char_Array(&new_array, newsize);
  char_array_cpy_noinit(*array,&new_array);
  free_Char_Array(*array);
  *array=new_array;
  return(0);
}

// add a value
int char_array_append(char val, Char_Array* output){
  if((*output).length>=(*output).memory){
    char_array_resize(output,2*(*output).memory+1);
  }
  (*output).str[(*output).length]=val;
  (*output).length++;
  return(0);
}
// append a string
int char_array_append_str(char* str, Char_Array* output){
  char* ptr;
  for (ptr=str;*ptr!='\0';ptr++){
    char_array_append(*ptr, output);
  }
  return(0);
}

// concatenate
int char_array_concat(Char_Array input, Char_Array* output){
  int i;
  int offset=(*output).length;
  if((*output).length+input.length>(*output).memory){
    // make it longer than needed by (*output).length (for speed)
    char_array_resize(output,2*(*output).length+input.length);
  }
  for(i=0;i<input.length;i++){
    (*output).str[offset+i]=input.str[i];
  }
  (*output).length=offset+input.length;
  return(0);
}

// substring
int char_array_substring(Char_Array str, int begin, int end, Char_Array* substr){
  int i;
  if(begin>end || begin<0 || end>=str.length){
    fprintf(stderr,"error: cannot extract a substring [%d,%d] from a string of length %d\n", begin, end, str.length);
    exit(-1);
  }
  init_Char_Array(substr,end-begin);
  for(i=begin;i<=end;i++){
    char_array_append(str.str[i],substr);
  }
  return(0);
}


// convert to char*
int char_array_to_str(Char_Array input, char** output){
  int i;
  (*output)=calloc(input.length+1,sizeof(char));
  for(i=0;i<input.length;i++){
    (*output)[i]=input.str[i];
  }
  if(input.length==0 ||  (*output)[input.length-1]!='\0'){
    (*output)[input.length]='\0';
  }
  return(0);
}
// noinit (changes the size of input if needed)
char* char_array_to_str_noinit(Char_Array* input){
  if((*input).str[(*input).length-1]!='\0'){
    if((*input).length==(*input).memory){
      char_array_resize(input,(*input).length+1);
    }
    // add final '\0'
    (*input).str[(*input).length]='\0';
  }
  return((*input).str);
}


// convert from char*
int str_to_char_array(char* str, Char_Array* output){
  char* ptr;
  init_Char_Array(output, str_len(str));
  for(ptr=str;*ptr!='\0';ptr++){
    char_array_append(*ptr,output);
  }
  return(0);
}

// compare char_array's
int char_array_cmp(Char_Array char_array1, Char_Array char_array2){
  int j;
  if(char_array1.length!=char_array2.length){
    return(0);
  }
  for(j=0;j<char_array1.length && j<char_array2.length;j++){
    if(char_array1.str[j]!=char_array2.str[j]){
      return(0);
    }
  }
  return(1);
}

// compare a char_array and a char*
int char_array_cmp_str(Char_Array char_array, char* str){
  int j;
  for(j=0;j<char_array.length && str[j]!='\0';j++){
    if(char_array.str[j]!=str[j]){
      return(0);
    }
  }
  if(j==char_array.length && str[j]=='\0'){
    return(1);
  }
  return(0);
}


// format strings
int char_array_snprintf(Char_Array* output, char* fmt, ...){
  size_t size=STR_SIZE;
  unsigned int extra_size;
  char* out_str=calloc(size,sizeof(char));
  char* ptr;
  va_list vaptr;

  // initialize argument list starting after fmt
  va_start(vaptr, fmt);
  // print format
  extra_size=vsnprintf(out_str, size, fmt, vaptr);
  va_end(vaptr);

  // if too large
  if(extra_size>size){
    // resize
    free(out_str);
    // +1 for '\0'
    size=extra_size+1;
    out_str=calloc(size,sizeof(char));
    // read format again
    va_start(vaptr, fmt);
    vsnprintf(out_str,size,fmt,vaptr);
    va_end(vaptr);
  }

  // write to char array
  for(ptr=out_str;*ptr!='\0';ptr++){
    char_array_append(*ptr, output);
  }

  free(out_str);

  return(0);
}


// replace '%' with given character
int replace_star(char c, Char_Array str, Char_Array* out){
  int i;
  init_Char_Array(out, str.length);
  for(i=0;i<str.length;i++){
    if(str.str[i]!='%'){
      char_array_append(str.str[i],out);
    }
    else{
      char_array_append(c,out);
    }
  }
  return(0);
}


// ------------------- Str_Array ------------------------

// init
int init_Str_Array(Str_Array* array, int memory){
  (*array).strs=calloc(memory,sizeof(Char_Array));
  (*array).memory=memory;
  (*array).length=0;
  return(0);
}
int free_Str_Array(Str_Array array){
  int i;
  for(i=0;i<array.length;i++){
    free_Char_Array(array.strs[i]);
  }
  free(array.strs);
  return(0);
}

// copy
int str_array_cpy(Str_Array input, Str_Array* output){
  init_Str_Array(output,input.length);
  str_array_cpy_noinit(input,output);
  return(0);
}
int str_array_cpy_noinit(Str_Array input, Str_Array* output){
  int i;
  if((*output).memory<input.length){
    fprintf(stderr,"error: trying to copy an array of length %d to another with memory %d\n",input.length, (*output).memory);
    exit(-1);
  }
  for(i=0;i<input.length;i++){
    char_array_cpy(input.strs[i],(*output).strs+i);
  }
  (*output).length=input.length;
  return(0);
}

// resize memory
int str_array_resize(Str_Array* array, int newsize){
  Str_Array new_array;
  init_Str_Array(&new_array, newsize);
  str_array_cpy_noinit(*array,&new_array);
  free_Str_Array(*array);
  *array=new_array;
  return(0);
}

// add a value
int str_array_append(Char_Array val, Str_Array* output){
  if((*output).length>=(*output).memory){
    str_array_resize(output,2*(*output).memory+1);
  }
  char_array_cpy(val, (*output).strs+(*output).length);
  (*output).length++;
  return(0);
}
int str_array_append_noinit(Char_Array val, Str_Array* output){
  if((*output).length>=(*output).memory){
    str_array_resize(output,2*(*output).memory+1);
  }
   (*output).strs[(*output).length]=val;
  (*output).length++;
  return(0);
}

// concatenate
int str_array_concat(Str_Array input, Str_Array* output){
  int i;
  int offset=(*output).length;
  if((*output).length+input.length>(*output).memory){
    // make it longer than needed by (*output).length (for speed)
    str_array_resize(output,2*(*output).length+input.length);
  }
  for(i=0;i<input.length;i++){
    char_array_cpy(input.strs[i],(*output).strs+offset+i);
  }
  (*output).length=offset+input.length;
  return(0);
}
int str_array_concat_noinit(Str_Array input, Str_Array* output){
  int i;
  int offset=(*output).length;
  if((*output).length+input.length>(*output).memory){
    // make it longer than needed by (*output).length (for speed)
    str_array_resize(output,2*(*output).length+input.length);
  }
  for(i=0;i<input.length;i++){
    (*output).strs[offset+i]=input.strs[i];
  }
  (*output).length=offset+input.length;

  // free input arrays
  free(input.strs);
  return(0);
}


// ------------------- Labels ------------------------

// allocate memory
int init_Labels(Labels* labels,int size){
  (*labels).labels=calloc(size,sizeof(Char_Array));
  (*labels).indices=calloc(size,sizeof(int));
  (*labels).length=0;
  (*labels).memory=size;
  return(0);
}

// free memory
int free_Labels(Labels labels){
  int i;
  for(i=0;i<labels.length;i++){
    free_Char_Array(labels.labels[i]);
  }
  free(labels.labels);
  free(labels.indices);

  return(0);
}

// resize the memory allocated to a labels table
int resize_labels(Labels* labels,int new_size){
  Labels new_labels;
  int i;

  init_Labels(&new_labels,new_size);
  for(i=0;i<(*labels).length;i++){
    new_labels.labels[i]=(*labels).labels[i];
    new_labels.indices[i]=(*labels).indices[i];
  }
  new_labels.length=(*labels).length;

  free((*labels).labels);
  free((*labels).indices);

  *labels=new_labels;
  return(0);
}

// copy a labels table
int labels_cpy(Labels input, Labels* output){
  init_Labels(output,input.length);
  labels_cpy_noinit(input,output);
  return(0);
}
int labels_cpy_noinit(Labels input, Labels* output){
  int i;
  if((*output).memory<input.length){
    fprintf(stderr,"error: trying to copy a labels collection of length %d to another with memory %d\n",input.length,(*output).memory);
    exit(-1);
  }
  for(i=0;i<input.length;i++){
    char_array_cpy(input.labels[i],(*output).labels+i);
    (*output).indices[i]=input.indices[i];
  }
  (*output).length=input.length;
  
  return(0);
}

// append an element to a labels
int labels_append(Char_Array label, int index, Labels* output){
  int offset=(*output).length;

  if((*output).length>=(*output).memory){
    resize_labels(output,2*(*output).memory);
  }

  // copy and allocate
  char_array_cpy(label,(*output).labels+offset);
  (*output).indices[offset]=index;
  // increment length
  (*output).length++;
  return(0);
}
// append an element to a labels without allocating memory
int labels_append_noinit(Char_Array label, int index, Labels* output){
  int offset=(*output).length;

  if((*output).length>=(*output).memory){
    resize_labels(output,2*(*output).memory);
  }

  // copy without allocating
  (*output).labels[offset]=label;
  (*output).indices[offset]=index;
  // increment length
  (*output).length++;
  return(0);
}

// concatenate two labels tables
int labels_concat(Labels input, Labels* output){
  int i;
  for(i=0;i<input.length;i++){
    labels_append(input.labels[i],input.indices[i],output);
  }
  return(0);
}