Initial commitv1.2

1 files changed, 628 insertions, 0 deletions

diff --git a/src/array.c b/src/array.c
new file mode 100644
index 0000000..11d14f7
--- /dev/null
+++ b/src/array.c
@@ -0,0 +1,628 @@
+/*
+Copyright 2015 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);
+}
+
+// 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);
+}
+
+// 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]);
+  }
+  printf("%d)",array.values[array.length-1]);
+  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);
+}
+
+
+
+// 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((*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);
+}
+
+
+// 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);
+}
+