From 893e4a375873f4b98d8691ffafbba8a2ccb1b55d Mon Sep 17 00:00:00 2001 From: zlg Date: Sun, 15 Jun 2014 00:24:38 -0500 Subject: Solve Exercise 5-17: field sorting --- ch5/5-16_dir-order.c | 2 +- ch5/5-17_field-sort.c | 267 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 268 insertions(+), 1 deletion(-) create mode 100644 ch5/5-17_field-sort.c (limited to 'ch5') diff --git a/ch5/5-16_dir-order.c b/ch5/5-16_dir-order.c index 7533b3b..4610ea6 100644 --- a/ch5/5-16_dir-order.c +++ b/ch5/5-16_dir-order.c @@ -158,7 +158,7 @@ char *alloc(int n) { } /* sort input lines */ -int main (int argc, char *argv[]) { +int main(int argc, char *argv[]) { int nlines; /* number of input lines read */ if (argc > 1) { diff --git a/ch5/5-17_field-sort.c b/ch5/5-17_field-sort.c new file mode 100644 index 0000000..c086053 --- /dev/null +++ b/ch5/5-17_field-sort.c @@ -0,0 +1,267 @@ +#include +#include +#include +#include + +/* The C Programming Language: 2nd Edition + * + * Exercise 5-17: Add a field-handling capability, so sorting may be done on + * fields within lines, each field sorted according to an independent set of + * options. (The index of this book was sorted with -df for the index + * category and -s for the page numbers.) + * + * Notes: The directions for this exercise are ambiguous. Given that this book + * is meant to teach and keep things mostly simple, I opted for a program that + * allows you to sort its input by a single field, using any sorting option + * previously available. For the index, then, this program would need to be + * ran multiple times to get the desired result. Sorting multiple ways at once + * on different fields at once is a complexity level far beyond what's been + * covered at this point in the book, so I don't think that was the intended + * goal. Enough jabbering; code time! + */ + + +#define MAXLINES 5000 +#define MAXLEN 1000 +#define DEFAULT_LINES 10 +#define ALLOCSIZE 10000000 +#define DELIMITER '\t' + +char *lineptr[MAXLINES]; +static char allocbuf[ALLOCSIZE]; +static char *allocp = allocbuf; +int numeric = 0; /* 1 if numeric sort */ +int reverse = 0; /* 1 if reverse sort */ +int fold = 0; /* 1 if folding upper and lower case */ +int dir = 0; /* 1 if directory order */ +int fieldnum = 0; /* Field to sort by, starting with 0. (This only gets used with -F) */ + +char *alloc(int); +int field_len(const char *); +int field_start(const char *, int); +int fieldcmp(const char *, const char *); +int istrcmp(const char *, const char *); +int mystrcmp(const char *, const char *); +int numcmp(const char *, const char *); +int readlines(char *lineptr[], int nlines); +void my_qsort(void *lineptr[], int left, int right, int (*comp)(const char *, const char *)); +void reverse_set(char *lineptr[], int nlines); +void writelines(char *lineptr[], int nlines); + +int mygetline(char *line, int lim) { + int c, i; + for (i = 0; i < lim && (c = getchar()) != EOF && c != '\n'; i++) { + *(line++) = c; + } + if (c == '\n') { + i++; /* I count newlines; some don't */ + *(line++) = c; + } + *line = '\0'; + return i; +} + +void my_qsort(void *v[], int left, int right, int (*comp)(const char *, const char *)) { + int i, last; + void swap(void *v[], int, int); + + if (left >= right) { + return; + } + swap(v, left, (left + right) / 2); + last = left; + for (i = left + 1; i <= right; i++) { + if ((*comp)(v[i], v[left]) <= 0) { + swap(v, ++last, i); + } + } + swap(v, left, last); + my_qsort(v, left, last - 1, comp); + my_qsort(v, last + 1, right, comp); +} + +int numcmp(const char *s1, const char *s2) { + double v1, v2; + v1 = atof(s1); + v2 = atof(s2); + if (v1 < v2) { + return -1; + } else if (v1 > v2) { + return 1; + } else { + return 0; + } +} + +void swap(void *v[], int i, int j) { + void *temp; + temp = v[i]; + v[i] = v[j]; + v[j] = temp; +} + +int readlines(char *lineptr[], int maxlines) { + int len, nlines; + char *p, line[MAXLEN]; + nlines = 0; + while ((len = mygetline(line, MAXLEN)) > 0) { + if (nlines >= maxlines || (p = alloc(len)) == NULL) { + return -1; + } else { + line[len-1] = '\0'; + strcpy(p, line); + lineptr[nlines++] = p; + } + } + return nlines; +} + +void writelines(char *lineptr[], int nlines) { + int i = 0; + for (; i < nlines && lineptr[i] != NULL; i++) { + printf("%s\n", lineptr[i]); + } +} + +void reverse_set(char *lineptr[], int nlines) { + int i; + int j = nlines; + for (i = 0; i < (nlines / 2); i++, j--) { + if (i < nlines) { + swap((void **)lineptr, i, j); + } + } +} + +/* Ignore character case, then send results to qsort */ +int mystrcmp(const char *s1, const char *s2) { + if (dir) { + while (!isalpha(*s1) && !isspace(*s1) && isdigit(*s1)) { + s1++; + } + while (!isalpha(*s2) && !isspace(*s2) && isdigit(*s2)) { + s2++; + } + } + while ((fold ? (tolower(*s1) == tolower(*s2)) : (*s1 == *s2))) { + if (*s1 == '\0') { + return 0; + } + s1++; + s2++; + if (dir) { + while (!isalpha(*s1) && !isspace(*s1) && isdigit(*s1)) { + s1++; + } + while (!isalpha(*s2) && !isspace(*s2) && isdigit(*s2)) { + s2++; + } + } + } + return (fold ? (tolower(*s1) - tolower(*s2)) : (*s1 - *s2)); +} + +int field_start(const char *s, int fieldnum) { + if (fieldnum == 0) { + return 0; + } + int i; + for (i = 0; s[i] != '\0'; i++) { + if (s[i] == DELIMITER) { + fieldnum--; + if (fieldnum == 0) { + if (s[i+1] != '\0') { + return i+1; + } + } + } + } + return -1; +} + +int field_len(const char *s) { + int i = 0; + while (s[i] != '\0') { + if (s[i] == DELIMITER) { + return i; + } + i++; + } + return i; /* If we reach the end of the string, we should return */ +} + +/* Produces substring copies of the fields to be compared, then hands it off + * to a comparison function. + */ +int fieldcmp(const char *s1, const char *s2) { + char tmp1[MAXLEN]; + char tmp2[MAXLEN]; + int start1 = field_start(s1, fieldnum); + int start2 = field_start(s2, fieldnum); + int len1 = field_len(s1 + start1); + int len2 = field_len(s2 + start2); + /* It should be safe to use strncpy here since we've established the + * boundaries of the field within the extant source strings + */ + strncpy(tmp1, s1 + start1, len1); + tmp1[len1] = '\0'; + strncpy(tmp2, s2 + start2, len2); + tmp2[len2] = '\0'; + return (numeric ? numcmp(tmp1, tmp2) : (fold || dir) ? mystrcmp(tmp1, tmp2) : strcmp(tmp1, tmp2)); +} + +char *alloc(int n) { + if (allocbuf + ALLOCSIZE - allocp >= n) { + allocp += n; + return allocp - n; + } else { + return 0; + } +} + +/* sort input lines */ +int main(int argc, char *argv[]) { + int nlines; /* number of input lines read */ + if (argc > 1) { + int i, j; + for (i = 1, j = 0; --argc; i++) { + if (argv[i][j++] == '-') { + while (argv[i][j] != '\0') { + switch(argv[i][j]) { + case 'n': + numeric = 1; + break; + case 'r': + reverse = 1; + break; + case 'f': + fold = 1; + break; + case 'd': + dir = 1; + break; + case 'F': + if (isdigit(argv[i][++j])) { + fieldnum = (argv[i][j] - '0'); + } + break; + } + j++; + } + } + } + } + if ((nlines = readlines(lineptr, MAXLINES)) >= 0) { + /* The trick is to chain inline if-statements. This will point to the correct + function for comparison, which powers my_qsort */ + my_qsort((void **) lineptr, 0, nlines - 1, (int (*)(const char *, const char *))(fieldnum >= 0 ? fieldcmp : (numeric ? numcmp : (fold || dir ? mystrcmp : strcmp)))); + if (reverse == 1) { + reverse_set(lineptr, nlines - 1); + } + writelines(lineptr, nlines); + return 0; + } else { + printf("Input too big to sort\n"); + return 1; + } +} -- cgit v1.2.3-54-g00ecf e3 /path/to/vgstash.db 'DROP VIEW backlog;' vgstash init 2018-10-18Bump to 0.3beta2 for PyPIzlg1-3/+3 2018-10-18vgstash.DB.__init__: fix error output formattingzlg1-1/+1 2018-10-18README: fix inline <code> formattingzlg1-3/+4 2018-10-18cli: show msg if game to be deleted is not in DBzlg2-2/+12 2018-10-18README: expand on usage, cover shell quotingzlg1-7/+99 2018-10-18cli: Tell the user when a game lacks noteszlg2-3/+15 2018-10-18Catch when an invalid list filter is passedzlg4-3/+24 Before, vgstash.DB.list_games() would default to 'allgames' and silently hide it when a filter wasn't found. This commit ensures that the vgstash package and CLI both indicate when an invalid filter is passed to them: * vgstash.DB.list_games() will return False on a failure to match; * vgstash_cli uses Click's Choice object to enforce the constraint 2018-10-12cli: Add zero-game import/export messageszlg2-11/+18 2018-10-10Bump to 0.3beta1 for PyPIzlg1-1/+1 2018-10-10Move tests and data to dedicated directoryzlg7-10/+26 Also tweaked the export command to report correctly. 2018-10-10cli: Add "export" commandzlg2-5/+54 The export command is like the import command; currently supporting YAML output, but ready to be expanded as needed. 2018-10-10cli: Add "import" commandzlg5-1/+76 Currently the import command will only accept YAML files, but is ready for expansion to other formats as needed. 2018-10-09Bump to 0.3alpha6 for PyPIzlg1-1/+1 2018-10-09cli: Add "notes" commandzlg2-4/+74 The "notes" command will show the user what their notes for a particular game are. The output can be piped anywhere the user wants, such as a pager or a file. If "notes" is passed with the "--edit" or "-e" flag, vgstash will open a temporary file with the game's notes already inside and edit it using the program pointed to by the EDITOR environment variable. When the editor is closed (with a successful exit status), vgstash updates the game's notes and exits. The defaults for the testing environment ("cat" for non-interactive, "vim" for interactive) may need tweaking on other operating systems. Patches for these platforms are very welcome. 2018-10-09update_game: ensure notes are also savedzlg1-2/+2 2018-10-09cli: add 'update' commandzlg3-20/+92 Two helper functions were also added to the vgstash package to ease client workflows. This commit marks the final core function necessary to manipulate a vgstash DB on the command line. 2018-10-06cli: Add "delete" commandzlg2-0/+19 Unlike the old version of vgstash, the new one does not accept row IDs as arguments for removal. Instead, it accepts two mandatory arguments: the title of the game, and the system it's on. This is in line with the database itself, using the title and system as primary keys. 2018-10-06Remove ID field from DBzlg3-38/+46 The sqlite database already uses a game's title and system as the primary keys. Row IDs are redundant. 2018-10-06cli: change "Status" heading to "Progress"zlg2-36/+40 2018-09-29Bump to 0.3alpha5 for PyPIzlg1-1/+1 2018-09-29cli: Add pretty printing to 'list' commandzlg3-17/+107 Also add the "--width" option to specify the maximum width of the table. 2018-09-08setup.py: Bump to alpha4 for PyPIzlg1-1/+1 2018-09-08cli: add '--raw' option to list commandzlg2-9/+45 Add '--raw' option to the list command, in addition to proper note expansion. Newline characters in notes are escaped to be friendly to scripting. This option may be shortened to '-r' at the user's convenience. In raw output mode, the information is formatted in plain pipe-delimited strings, one line per row: title|system|ownership|progress|notes ownership and progress are printed in their numeric form, consistent with the OWNERSHIP and PROGRESS dictionaries in the vgstash package. An empty notes field will result in a line ending with a pipe and no whitespace following it. 2018-09-08Add remaining filters to vgstash packagezlg1-2/+11 2018-09-04Update LICENSE to match setup.pyzlg1-80/+67 Whoops. 2018-09-03Branch off from master with pytest, tox, clickzlg16-778/+779 This commit is huge, but contains everything needed for a "proper" build system built on pytest + tox and a CLI built with click. For now, this branch will contain all new vgstash development activity until it reaches feature parity with master. The CLI is installed to pip's PATH. Only the 'init', 'add', and 'list' commands work, with only two filters. This is pre-alpha software, and is therefore not stable yet. 2018-03-18Flesh out filter types and ownership statuszlg3-82/+144 It's time for a refactor to a module; the functionality and interface are clashing. 2018-03-18README.mdown: break line correctlyzlg1-1/+1 2018-03-18add 'playlog' list filterzlg2-2/+9 This filter is used to get an idea of which games you're currently playing through, so you can prioritize games to play when you're bored and detect it when you've beaten a game but haven't marked it as such. 2018-03-13Update helpers a bitzlg1-2/+9 At present, user modification is needed to make these seamless. vgup() may need to be axed in favor of telling the user to make an alias. 2018-03-13Make VGSTASH_DB_LOCATION point to a filezlg2-21/+20 It used to point to a directory, which would then look for .vgstash.db. This behavior was kind of backwards and I don't remember why I did it that way. This change gives users more control over where they put their DB. Be sure to update your environment variable if you have it set! 2016-11-18Remove settings from helpers.shZe Libertine Gamer1-5/+0 Sourcing them in .bash_profile screws up login if they're set. 2016-11-15Correct phrasing in README.Ze Libertine Gamer1-4/+4 2016-11-13DerpZe Libertine Gamer1-0/+1 2016-11-03Improve error handling in shell scriptsZe Libertine Gamer4-3/+23 2016-10-24Correct run_again, add recursionZe Libertine Gamer1-0/+4 Loops and functions -- oh my, what a useful combination. :) 2016-10-21Add quotes to correct behavior for arglistZe Libertine Gamer1-1/+1 2016-10-14updater.sh: add recursion, error handlingZe Libertine Gamer1-43/+101 2016-10-14Correct pipe-handling behaviorZe Libertine Gamer1-1/+9 2016-10-12Clarify a method to move between platformsZe Libertine Gamer1-2/+5 Also correct a typo.