diff --git a/c/rl.c b/c/rl.c new file mode 100644 index 0000000..4d02581 --- /dev/null +++ b/c/rl.c @@ -0,0 +1,155 @@ +/* + * rl: remove line(s) + */ + +/* + * Copyright (c) 2005 Andreas Jaggi + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include + +const char usagemsg[] = + "usage: rl [-t separator] [-n lines]\n" + "\n" + "options:\n" + " -t C use character C as separator instead of \\n\n" + " -n N remove N lines\n" + " also: rl -v show version\n" + " rl -h display this help\n" + " rl -l display (BSD) license\n" + ; + +const char versionmsg[] = "rl 0.6\n"; + +const char licensemsg[] = + "rl is copyright (c) 2005 Andreas Jaggi \n" + "All rights reserved.\n" + "\n" + "Redistribution and use in source and binary forms, with or without\n" + "modification, are permitted provided that the following conditions\n" + "are met:\n" + "1. Redistributions of source code must retain the above copyright\n" + " notice, this list of conditions and the following disclaimer.\n" + "2. Redistributions in binary form must reproduce the above copyright\n" + " notice, this list of conditions and the following disclaimer in the\n" + " documentation and/or other materials provided with the distribution.\n" + "3. The name of the author may not be used to endorse or promote products\n" + " derived from this software without specific prior written permission.\n" + "\n" + "THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\n" + "IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n" + "OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\n" + "IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\n" + "INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n" + "NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n" + "DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n" + "THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n" + "(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\n" + "THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n" + ; + +void usage(void); +void version(void); +void license(void); +void rl(int n, char sep); + +int main ( int argc, char *argv[] ) { + int n = 1; + int r = -1; + char sep = '\n'; + + while ( (r = getopt(argc, argv, "n:t:hlv")) != -1 ) { + switch ( r ) { + case 'h': + usage(); + exit(0); + case 'l': + license(); + exit(0); + case 'v': + version(); + exit(0); + case 'n': + n = atoi(optarg); + + if ( n < 0 ) { + usage(); + exit(1); + } + break; + case 't': + sep = optarg[0]; + + if ( optarg[1] != '\0' ) { + usage(); + exit(1); + } + break; + default: + usage(); + exit(1); + } + } + + rl(n, sep); + + exit(0); +} + +void rl(int n, char sep) { + char buf; + + if ( n > 0 ) { + do { + if ( getchar() == sep ) { + n--; + } + } while ( n > 0 && !feof(stdin) ); + } + + if ( !feof(stdin) ) { + buf = getchar(); + } + + while ( !feof(stdin) ) { + printf("%c",buf); + buf = getchar(); + } +} + +void usage(void) { + fprintf(stdout, usagemsg); +} + +void version(void) { + fprintf(stdout, versionmsg); +} + +void license(void) { + fprintf(stdout, licensemsg); +} diff --git a/c/rs.c b/c/rs.c new file mode 100644 index 0000000..d89cc50 --- /dev/null +++ b/c/rs.c @@ -0,0 +1,200 @@ +/* + * rs: reverse stream + */ + +/* + * Copyright (c) 2005 Andreas Jaggi + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include + +struct _cb; + +typedef struct _cb* cb; + +typedef struct _cb { + char *dat; + int n; + cb ne; +} _cb; + +const char usagemsg[] = + "usage: rs\n" + "\n" + "options:\n" + " -n N set size of internal buffer to N (default is 512)\n" + " also: rs -v show version\n" + " rs -h display this help\n" + " rs -l display (BSD) license\n" + ; + +const char versionmsg[] = "rs 0.7\n"; + +const char licensemsg[] = + "rs is copyright (c) 2005 Andreas Jaggi \n" + "All rights reserved.\n" + "\n" + "Redistribution and use in source and binary forms, with or without\n" + "modification, are permitted provided that the following conditions\n" + "are met:\n" + "1. Redistributions of source code must retain the above copyright\n" + " notice, this list of conditions and the following disclaimer.\n" + "2. Redistributions in binary form must reproduce the above copyright\n" + " notice, this list of conditions and the following disclaimer in the\n" + " documentation and/or other materials provided with the distribution.\n" + "3. The name of the author may not be used to endorse or promote products\n" + " derived from this software without specific prior written permission.\n" + "\n" + "THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\n" + "IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n" + "OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\n" + "IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\n" + "INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n" + "NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\n" + "DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\n" + "THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\n" + "(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\n" + "THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n" + ; + +void usage(void); +void version(void); +void license(void); +void rs1(void); +void rs(int ds); + +int main ( int argc, char *argv[] ) { + int ds = 512; + + switch ( getopt(argc, argv, "n:hlv") ) { + case 'h': + usage(); + break; + case 'l': + license(); + break; + case 'v': + version(); + break; + case 'n': + ds = atoi(optarg); + + if ( ds < 1 ) { + usage(); + exit(1); + } + case -1: + if ( ds == 1 ) { + rs1(); + } else { + rs(ds); + } + break; + default: + usage(); + exit(1); + } + exit(0); +} + +void rs1(void) { + long int an = 0; + char buf; + char *sp = NULL; + + buf = getchar(); + + while ( !feof(stdin) ) { + an++; + sp = (char*)realloc(sp, sizeof(char)*an); + *(sp+an) = buf; + buf = getchar(); + } + + while ( an > 0 ) { + printf("%c", *(sp+an)); + an--; + } + + free(sp); +} + +void rs(int ds) { + int cn = 0; + cb bl = (cb) NULL; + cb tl = (cb) NULL; + char *buf = (char*) NULL; + int lr = 0; + int i = 0; + + buf = (char*)malloc(sizeof(char)*ds); + + while ( !feof(stdin) ) { + cn++; + tl = bl; + bl = (cb) malloc(sizeof(_cb)); + lr = fread(buf, sizeof(char), ds, stdin); + bl->dat = (char*)malloc(sizeof(char)*ds); + + for ( i = 0; i < ds && i < lr; i++ ) { + *(bl->dat+i) = *(buf+i); + } + + bl->n = lr; + bl->ne = tl; + } + + while ( cn > 0 ) { + for ( i = bl->n; i > 0; i-- ) { + printf("%c", *(bl->dat+i-1)); + } + + free(bl->dat); + + tl = bl->ne; + + free(bl); + bl = tl; + + cn--; + } + + free(bl); +} + +void usage(void) { + fprintf(stdout, usagemsg); +} + +void version(void) { + fprintf(stdout, versionmsg); +} + +void license(void) { + fprintf(stdout, licensemsg); +} diff --git a/c/sort.c b/c/sort.c new file mode 100644 index 0000000..2462fcf --- /dev/null +++ b/c/sort.c @@ -0,0 +1,426 @@ +/* + * a collection of sort algorithms + */ + +/* + * Copyright (c) 2005 Andreas Jaggi + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include + +void gnomesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void insertionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void selectionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void shellsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void mergesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void merge(void *a1, void *a2, size_t n, size_t m, size_t size, int (* compar)(const void *, const void *)); +void bubblesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void quicksort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void heapsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void heapcreate(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)); +void siftdown(void *array, size_t count, size_t size, int (* compar)(const void *, const void *), int i); + +int cmpint ( void const * a, void const * b ); +int randcmp ( void const * a, void const * b ); +void plst (int *array, size_t size); + +int main ( int argc, char *argv[] ) { + int ls = 30; + int i; + int *lst = (int*) malloc(ls*sizeof(int)); + + for ( i = 0; i < ls; i++ ) { + *(lst+i) = i; + } + + srand(1); + + qsort((void*)lst, ls, sizeof(int), randcmp); + plst(lst, ls); + printf("\n\n"); + + printf("GnomeSort\n"); + gnomesort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("InsertionSort\n"); + insertionsort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("SelectionSort\n"); + selectionsort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("ShellSort\n"); + shellsort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("MergeSort\n"); + mergesort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("BubbleSort\n"); + bubblesort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("QuickSort\n"); + quicksort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + qsort((void*)lst, ls, sizeof(int), randcmp); + + printf("HeapSort\n"); + heapsort((void*)lst, ls, sizeof(int), cmpint); + + plst(lst, ls); + printf("\n\n"); + + free(lst); + + exit(0); +} + +void plst (int *array, size_t size) { + int i; + + for ( i = 0; i < size; i++ ) { + printf("%d, ", *(array+i)); + } +} + +int randcmp ( void const * a, void const * b ) { + return (int)(3.0*rand()/(RAND_MAX-1))-1; +} + +int cmpint ( void const * a, void const * b ) { + int const * const i = a; + int const * const j = b; + + if ( *i > *j ) { + return 1; + } else { + if ( *i < *j ) { + return -1; + } else { + return 0; + } + } +} + +void gnomesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int i = 1; + void *t = (void*) malloc(size); + + while ( i < count ) { + if ( compar(array+i*size, array+(i-1)*size) < 0 ) { + memcpy(t, array+i*size, size); + memcpy(array+i*size, array+(i-1)*size, size); + memcpy(array+(i-1)*size, t, size); + + if ( i > 1 ) { + i--; + } else { + i++; + } + } else { + i++; + } + } + + free(t); +} + +void insertionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int i,j; + void *t = (void*) malloc(size); + + for ( i = 1; i < count; i++ ) { + j = i-1; + memcpy(t, array+i*size, size); + + while ( compar(array+j*size, t) > 0 && j > -1 ) { + memcpy(array+(j+1)*size, array+j*size, size); + j--; + } + + memcpy(array+(j+1)*size, t, size); + } + + free(t); +} + +void selectionsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int i,min,j; + void *t = (void*) malloc(size); + + for ( i = 0; i < count-1; i++ ) { + min = i; + + for ( j = i+1; j < count; j++ ) { + if ( compar(array+j*size, array+min*size) < 0 ) { + min = j; + } + } + + if ( i != min ) { + memcpy(t, array+min*size, size); + memcpy(array+min*size, array+i*size, size); + memcpy(array+i*size, t, size); + } + } + + free(t); +} + +void shellsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int k,j,i; + void *t = (void*) malloc(size); + + for ( k = count; k > 0; k-- ) { + for ( i = k; i < count; i++ ) { + memcpy(t, array+i*size, size); + j = i; + + while ( j+1 > k && compar(array+(j-k)*size, t) > 0) { + memcpy(array+j*size, array+(j-k)*size, size); + j = j-k; + } + + memcpy(array+j*size, t, size); + } + } + + free(t); +} + +void mergesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int m; + + if ( count > 1 ) { + m = count/2; + + mergesort(array, m, size, compar); + mergesort(array+m*size, count-m, size, compar); + merge(array, array+m*size, m, count-m, size, compar); + } +} + +void merge(void *a1, void *a2, size_t n, size_t m, size_t size, int (* compar)(const void *, const void *)) { + int i,c; + int i1 = 0; + int i2 = 0; + void *s = (void*)malloc(size*(n+m)); + + for ( i = 0; i < n+m; i++ ) { + if ( compar(a1+size*i1, a2+size*i2) < 0 ) { + c = 1; + } else { + c = 0; + } + + if ((c && i1 == n) || (!c && i2 == m)) { + c = !c; + } + + if ( c ) { + memcpy(s+size*i, a1+size*i1, size); + i1++; + } else { + memcpy(s+size*i, a2+size*i2, size); + i2++; + } + } + + memcpy(a1, s, size*(n+m)); + + free(s); +} + +void bubblesort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int r,i; + int c = 1; + void *t = (void*) malloc(size); + + for ( r = count-1; c ; r-- ) { + c = 0; + + for ( i = 0; i < r; i++ ) { + if ( compar(array+i*size, array+(i+1)*size) > 0) { + memcpy(t, array+i*size, size); + memcpy(array+i*size, array+(i+1)*size, size); + memcpy(array+(i+1)*size, t, size); + c = 1; + } + } + } + + free(t); +} + +void quicksort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int q = 0; + int p = count-1; + void *t = (void*) NULL; + void *t2 = (void*) NULL; + + if ( count > 1 ) { + t = (void*) malloc(size); + t2 = (void*) malloc(size); + + memcpy(t, array+(count-1)*size, size); + + while ( p > q ) { + for ( ; p > 0 && compar(array+p*size, t) > -1; p-- ); + for ( ; q < count-1 && compar(array+q*size, t) < 1; q++ ); + + if ( p > q ) { + memcpy(t2, array+p*size, size); + memcpy(array+p*size, array+q*size, size); + memcpy(array+q*size, t2, size); + } + } + + memcpy(t2, array+q*size, size); + memcpy(array+q*size, array+(count-1)*size, size); + memcpy(array+(count-1)*size, t2, size); + + quicksort(array, q, size, compar); + quicksort(array+(q+1)*size, count-q-1, size, compar); + + free(t); + free(t2); + } +} + + +void heapsort(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int i,j,s,l; + void *t = (void*) malloc(size); + + heapcreate(array, count, size, compar); + + for ( i = count-1; i > 0; i-- ) { + memcpy(t, array, size); + memcpy(array, array+(i)*size, size); + memcpy(array+(i)*size, t, size); + s = 1; + j = 0; + + while ( s && j < i ) { + s = 0; + + if ( 2*j < count ) { + if ( 2*j+1 < count ) { + if ( compar(array+2*j*size, array+(2*j+1)*size) > 0 ) { + l = 2*j; + } else { + l = 2*j+1; + } + } else { + l = 2*j; + } + } else { + break; + } + + if ( l > i-1) { + break; + } + + if ( compar(array+l*size, array+j*size) > 0 ) { + memcpy(t, array+l*size, size); + memcpy(array+l*size, array+j*size, size); + memcpy(array+j*size, t, size); + j = l; + s = 1; + } + } + } + + free(t); +} + +void heapcreate(void *array, size_t count, size_t size, int (* compar)(const void *, const void *)) { + int i; + + for ( i = (count-2)/2; i > -1; i-- ) { + siftdown(array, count, size, compar, i); + } +} + +void siftdown(void *array, size_t count, size_t size, int (* compar)(const void *, const void *), int i) { + int j; + int s = 1; + void *t = (void*) malloc(size); + + while ( s && 2*i+1 < count ) { + s = 0; + + if ( compar(array+2*i*size, array+(2*i+1)*size) > 0) { + j = 2*i; + } else { + j = 2*i+1; + } + + if ( compar(array+j*size, array+i*size) > 0 ) { + memcpy(t, array+j*size, size); + memcpy(array+j*size, array+i*size, size); + memcpy(array+i*size, t, size); + i = j; + s = 1; + } + } + + free(t); +}