/**
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Written by Raphaël Gertz <rapsys@rapsys.eu>
 */

/* exit EXIT_FAILURE EXIT_SUCCESS */
#include <stdlib.h>

/* printf */
#include <stdio.h>

/* stat S_ISREG */
#include <sys/stat.h>

/* access R_OK */
#include <unistd.h>

/* open O_RDONLY */
#include <fcntl.h>

/* strspn */
#include <string.h>

/* Zero ascii offset */
#define ZERO_OFFSET 48

/* Branch cell */
struct branch {
	unsigned key;
	struct branch *next;
	void *child;
};

/* Leaf cell */
struct leaf {
	unsigned key;
	struct leaf *next;
	unsigned count;
};

/* Lookup leaf function prototype */
struct leaf *lookupLeaf(void **, const char *, unsigned);

/* Freeing node function prototype */
void freeTree(void *, unsigned);

/* Main function */
int main(int argc, char **argv) {

	/* Stat struct */
	struct stat ss;

	/* File descriptor */
	int fd;

	/* Return value */
	int ret;

	/* Line buffer */
	char line[11] = { 0 };

	/* Current leaf */
	struct leaf *current;

	/* Tree root */
	struct branch *tree = NULL;

	/* Unique counter */
	unsigned unique = 0;

	/* Duplicated counter */
	unsigned duplicate = 0;


	/* Check argument count */
	if (argc < 2 || argc > 2) {
		fprintf(stderr, "Usage: %s sirens_fxt.txt\n", argv[0]);
		exit(EXIT_FAILURE);
	}

	/* Stat file */
	if (stat(argv[1], &ss) == -1) {
		perror("Stat failed");
		exit(EXIT_FAILURE);
	}

	/* Check it is a file */
	if (!S_ISREG(ss.st_mode)) {
		fprintf(stderr, "%s must be a valid file\n", argv[1]);
		exit(EXIT_FAILURE);
	}

	/* Check if readable */
	if (access(argv[1], R_OK)) {
		fprintf(stderr, "%s must be readable\n", argv[1]);
		exit(EXIT_FAILURE);
	}

	/* Open file */
	if ((fd = open(argv[1], O_RDONLY)) == -1) {
		perror("Open failed");
		exit(EXIT_FAILURE);
	}

	/* Read file */
	do {
		/* Try reading line and check line format */
		if ((ret = read(fd, &line, 10)) == 10 && strspn(line, "0123456789") == 9 && line[9] == '\n') {
			/* Terminate key */
			line[9] = '\0';
			/* Lookup matching leaf */
			current = lookupLeaf((void **)&tree, line, 0);
			/* Grow unique */
			if (current->count == 0) {
				unique++;
			} else if (current->count == 1) {
				unique--;
				duplicate++;
			}
			current->count++;
		/* Handle read error */
		} else if (ret == -1) {
			perror("Read failed");
			exit(EXIT_FAILURE);
		/* Handle partial read or invalid line format */
		} else if (ret > 0) {
			line[ret] = '\0';
			fprintf(stderr, "%s must be filled with lines matching [0-9]{9}LF format; got \"%s\" instead\n", argv[1], line);
			exit(EXIT_FAILURE);
		}
	/* Read until end of file */
	} while (ret != 0);

	/* Free tree */
	freeTree(tree, 0);

	/* Close file */
	if (close(fd) == -1) {
		perror("Close failed");
		exit(EXIT_FAILURE);
	}

	/* Print result */
	printf("Unique%s: %d, duplicate%s: %d\n", (unique > 1 ? "s" : ""), unique, (duplicate > 1 ? "s" : ""), duplicate);

	/* Successful end */
	exit(EXIT_SUCCESS);
}

/* Recursive freeing of node function */
void freeTree(void *base, unsigned index) {
	void *current = base, *next;
	if (base != NULL) {
		/* Branch level */
		if (index < 8) {
			/* Free horizontaly */
			do {
				/* Free children */
				if (((struct branch *)current)->child != NULL) {
					freeTree(((struct branch *)current)->child, index + 1);
				}
				/* Free current and switch to next */
				next = ((struct branch *)current)->next;
				free(current);
				current = next;
			} while (current != NULL);
		/* Leaf level */
		} else {
			/* Free horizontaly */
			do {
				/* Free current and switch to next */
				next = ((struct leaf *)current)->next;
				free(current);
				current = next;
			} while (current != NULL);
		}
	}
}

/* Recursive lookup and populate tree function */
struct leaf *lookupLeaf(void **base, const char *key, unsigned index) {
	/* Return leaf */
	struct leaf *ret;

	/* Insert node on empty level */
	if (*base == NULL) {
		/* Branch level */
		if (index < 8) {
			if ((*base = malloc(sizeof(struct branch))) == NULL) {
				perror("Malloc failed");
				exit(EXIT_FAILURE);
			}
			((struct branch *)*base)->key = key[index] - ZERO_OFFSET;
			((struct branch *)*base)->next = NULL;
			((struct branch *)*base)->child = NULL;
			ret = lookupLeaf(&(((struct branch *)*base)->child), key, index + 1);
		/* Leaf level */
		} else {
			if ((*base = malloc(sizeof(struct leaf))) == NULL) {
				perror("Malloc failed");
				exit(EXIT_FAILURE);
			}
			((struct leaf *)*base)->key = key[index] - ZERO_OFFSET;
			((struct leaf *)*base)->next = NULL;
			((struct leaf *)*base)->count = 0;
			ret = (struct leaf *)*base;
		}
	/* Search horizontaly next node */
	} else {
		/* Current node for horizontal search */
		void *current = *base, *prev;
		/* Branch level */
		if (index < 8) {
			/* Lookup node matching key or allocate it */
			while(((struct branch *)current)->key != key[index] - ZERO_OFFSET) {
				/* End of horizontal search */
				if (((struct branch *)current)->next == NULL) {
					/* Backup current in prev */
					prev = current;
					/* Create new branch with key */
					if ((current = malloc(sizeof(struct branch))) == NULL) {
						perror("Malloc failed");
						exit(EXIT_FAILURE);
					}
					((struct branch *)current)->key = key[index] - ZERO_OFFSET;
					((struct branch *)current)->next = NULL;
					((struct branch *)current)->child = NULL;
					((struct branch *)prev)->next = (struct branch *)current;
				} else {
					/* Pass to next one */
					current = ((struct branch *)current)->next;
				}
			}

			/* Lookup leaf or branch in next level */
			ret = lookupLeaf(&(((struct branch *)current)->child), key, index + 1);
		/* Leaf level */
		} else {
			/* Lookup node matching key or allocate it */
			while(((struct leaf *)current)->key != key[index] - ZERO_OFFSET) {
				/* End of horizontal search */
				if (((struct leaf *)current)->next == NULL) {
					/* Backup current in prev */
					prev = current;
					/* Create new leaf with key */
					if ((current = malloc(sizeof(struct leaf))) == NULL) {
						perror("Malloc failed");
						exit(EXIT_FAILURE);
					}
					((struct leaf *)current)->key = key[index] - ZERO_OFFSET;
					((struct leaf *)current)->next = NULL;
					((struct leaf *)current)->count = 0;
					((struct leaf *)prev)->next = (struct leaf *)current;
				} else {
					/* Pass to next one */
					current = ((struct leaf *)current)->next;
				}
			}

			/* Found leaf, return it */
			ret = (struct leaf *)current;
		}
	}

	/* Return leaf */
	return ret;
}