diff options
Diffstat (limited to 'src/array.c')
| -rw-r--r-- | src/array.c | 628 |
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); +} + |