unsort program (C source)
Oscar M. Nierstrasz
oscar at utcsrgv.UUCP
Thu Nov 24 06:21:16 AEST 1983
/* FILE : UNSORT.C 831102 */
/* AUTHOR : Oscar Nierstrasz */
/* USAGE : unsort [file] ... */
/* */
/* Unsorts a file. The inverse of sort(1). unsort is a */
/* linear time unsorting program that reads the input */
/* lines into a linked list and then sets the links by */
/* randomly inserting each line into the list. */
/* */
#include <stdio.h>
#define MAXCHARS 100000
#define MAXLINES 10000
#define EOL '\n'
#define EOS '\0'
char buf [MAXCHARS], *s, *ebuf; /* file buffer */
int last;
struct item {
char *sval; /* pointer to one input line in buf */
int next;
} list [MAXLINES];
main(argc, argv)
int argc;
char **argv;
{
int i, j;
FILE *file;
ebuf = buf + MAXCHARS; /* the last spot in buf */
s = buf; /* current pointer */
last = 1; /* the last line */
list[last].sval = s;
/* read the input into buf */
if (argc == 1)
loadlines(stdin);
else {
for (i=1; i<argc; i++) {
if ((file = fopen(argv[i], "r")) == NULL) {
fprintf(stderr, "Cannot open %s\n", argv[i]);
exit(1);
}
loadlines(file);
fclose(file);
}
}
last--;
if (last == 0) {
fprintf(stderr, "Warning: no input\n");
exit(0);
}
/* initialize the linked list */
list[0].next = 1; /* dummy head of list */
list[1].next = 0; /* end of list */
srand(time()); /* set the random seed */
for (i=2; i<=last; i++) {
/* randomly insert into linked list */
j = rand() % i;
list[i].next = list[j].next;
list[j].next = i;
}
/* print the list */
i = list[0].next;
while (i != 0) {
printf("%s\n", list[i].sval);
i = list[i].next;
}
}
loadlines(file)
FILE *file;
{
while ((*s = fgetc(file)) != EOF) {
if (*s == EOL) { /* end of line */
*s = EOS;
s++;
last++;
if (last > MAXLINES) {
fprintf(stderr, "Too many lines\n");
exit(1);
}
list[last].sval = s;
}
else s++;
if (s >= ebuf) {
fprintf(stderr, "File too big\n");
exit(1);
}
}
}
--
UUCP { ihnp4 cornell decwrl watmath uw-beaver ubc-vision sask
garfield qucis linus mcgill-vision }!utcsrgv!oscar
or { allegra decvax duke floyd }!utzoo!utcsrgv!oscar
More information about the Comp.sources.unix
mailing list