#include <stdio.h>
#include <stdlib.h>

// ɔopyleft Andreas Nordal

struct fil{
	char *name;
	FILE *fp;
	long reading;
	struct fil *next;
};

void destroy(struct fil *this){
	fclose(this->fp);
	free(this);
}

void list(struct fil *start){
	puts("---");
	struct fil *prev;
	do{
		puts(start->name);
		prev = start;
		start = start->next;
		destroy(prev);
	}while(start);
}

void debug(struct fil *start){
	do{
		printf("> %s\n", start->name);
		start = start->next;
	}while(start);
}

void readfiles(struct fil *cur){
	do{
		cur->reading = fgetc(cur->fp);
		cur = cur->next;
	}while(cur);
}

void group(struct fil *old_start){
	struct fil *new_start, *new_prev, *old_prev, *cur;
	int lookingfor;
	for(;;){
		cur = old_start;
		new_start = NULL;
		old_prev = old_start;
		lookingfor = old_start->reading;
		while(cur = cur->next){
			if(cur->reading == lookingfor){
				//cur remains in old list
				old_prev->next = cur;
				old_prev = cur;
				cur->reading = fgetc(cur->fp);
			}else{
				//move cur to new list
				if(new_start){
					new_prev->next = cur;
				}else{
					new_start = cur;
				}
				new_prev = cur;
			}
		}
		//Old list now contains identical files
		// (up to (current file position)-1 ).
		//The rest is in new list, which might be empty.
		if(new_start){
			//If not, old list is altered.
			old_prev->next = NULL;
			new_prev->next = NULL;
			if(new_start->next && old_start->next){
				//Outsource new list. Perhaps this
				// should be done in a new thread?
				group(new_start);
			}else{
				//If either list contains only one
				// file, discard it and do nothing
				// more with it.
				if(new_start->next == NULL
				&& old_start->next == NULL){
					destroy(new_start);
					destroy(old_start);
					break;
				}else if(new_start->next){
					destroy(old_start);
					old_start = new_start;
					continue;
				}else{
					destroy(new_start);
				}
			}
		}
		if(lookingfor == EOF){
			list(old_start);
			break;
		}
		//Since we skipped reading it:
		old_start->reading = fgetc(old_start->fp);
	}
}

int main(int argc, char *argv[]){
	int i = argc-1;
	if(i < 2){
		puts("Usage: fcmp file1 file2 ...\n"
		"Finds out which of the files are identical"
		" and lists them in groups.\n"
		"Show this help text instead if less than 2"
		" files are given.\n\n"
		"\tWarning:\n"
		"1) When this program has found some files "
		"to be identical, it doesn't mean that they"
		" are copies! A file can have multiple path"
		"s due to symlinks, hardlinks and filesyste"
		"m mount points. Even giving the same filen"
		"ame twice will make this program compare t"
		"hat file with itself.\n"
		"2) This program understands only regular f"
		"iles. Directories will be compared by file"
		"size, which is not useful.");
		return EXIT_FAILURE;
	}
	struct fil *last=NULL, *next, *current;
	while(i){
		current = malloc(sizeof(struct fil));
		if(!current){
			fputs("Out of memory!", stderr);
			break;
		}
		current->name = argv[i];
		current->fp = fopen(argv[i], "rb");
		if(current->fp){
			if(last){
				current->next = next;
			}else{
				last = current;
			}
			fseek(current->fp, 0, SEEK_END);
			current->reading = ftell(current->fp);
			fseek(current->fp, 0, SEEK_SET);
			next = current;
		}else{
			perror(current->name);
		}
		i--;
	}
	if(last){
		last->next = NULL;
		group(current);
	}
	
	return EXIT_SUCCESS;
}
/*todo: ignore directories,
 *	make group()'s call to itself a new thread,
 *	some options
 */