Ian Jauslin
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIan Jauslin <ian.jauslin@roma1.infn.it>2015-06-14 00:52:45 +0000
committerIan Jauslin <ian.jauslin@roma1.infn.it>2015-06-14 00:52:45 +0000
commitaa0f3ae2988d372b190b9bde2e75a6d17e744e93 (patch)
tree14482245c2fca27fcdad3078e97d0871352d52a7 /src/array.c
Initial commitv1.2
Diffstat (limited to 'src/array.c')
-rw-r--r--src/array.c628
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);
+}
+