Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utcsrgv.UUCP
Path: utzoo!utcsrgv!oscar
From: oscar@utcsrgv.UUCP (Oscar M. Nierstrasz)
Newsgroups: net.sources
Subject: unsort program (C source)
Message-ID: <2803@utcsrgv.UUCP>
Date: Wed, 23-Nov-83 15:21:16 EST
Article-I.D.: utcsrgv.2803
Posted: Wed Nov 23 15:21:16 1983
Date-Received: Wed, 23-Nov-83 16:50:53 EST
Organization: CSRG, University of Toronto
Lines: 98

/*	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