/*
 * Leon Dague
 * Problem 1(c), Homework #1, ENEE 620 Fall 2007
 *
 * From Example 1 of the notes, show all families of increasing
 * sequences of sets.
 *
 * $Id: hw1.c,v 1.4 2007/09/11 15:48:25 ldague1 Exp ldague1 $
 */

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

#define STRINGLEN 6

void ps(char *s, unsigned subset);
int lt(int a, int b);
struct family *mkfam(int n, unsigned *v);
void printfam(struct family *fp);
void print_list(struct family *fp);

struct family {
	int n;
	unsigned subset[5];
	struct family *next;
};

int main()
{
	unsigned subset[16];
	unsigned i, j;
	struct family *f2=NULL, *f2cur=NULL;
	struct family *f3=NULL, *f3cur=NULL;
	struct family *f4=NULL, *f4cur=NULL;
	struct family *f5=NULL, *f5cur=NULL;

#if 0
	struct family *p;
char temp[STRINGLEN];

ps(temp, 0x01);
printf("%s\n", temp);

return 0;
#endif

	for (i=0; i<16; i++) {
		subset[i]=i;
	}
/* 2-element families */
	for (i=0; i<16; i++) {

		for (j=0; j<16; j++) {
			if (lt(subset[i], subset[j])) {
				unsigned temp[5];
				struct family *fp;

				temp[0]=subset[i];
				temp[1]=subset[j];
				fp=mkfam(2, temp);
				if (f2 == NULL)
					f2=f2cur=fp;
				else {
					f2cur->next = fp;
					f2cur = f2cur->next;
				}
			}
		}
	}

/* 3-element families */
	for (i = 0; i<16; i++) {
		f2cur=f2;
		while (f2cur) {
			unsigned u = f2cur->subset[1];
			if (lt(u, subset[i])) {
				unsigned temp[5];
				struct family *fp;

				temp[0]=f2cur->subset[0];
				temp[1]=u;
				temp[2]=subset[i];
				fp=mkfam(3, temp);
				if (f3 == NULL)
					f3=f3cur=fp;
				else {
					f3cur->next = fp;
					f3cur = f3cur->next;
				}
			}
			f2cur=f2cur->next;
		}
	}

/* 4-element families */
	for (i = 0; i<16; i++) {
		f3cur=f3;
		while (f3cur) {
			unsigned u = f3cur->subset[2];
			if (lt(u, subset[i])) {
				unsigned temp[5];
				struct family *fp;

				temp[0]=f3cur->subset[0];
				temp[1]=f3cur->subset[1];
				temp[2]=u;
				temp[3]=subset[i];
				fp=mkfam(4, temp);
				if (f4 == NULL)
					f4=f4cur=fp;
				else {
					f4cur->next = fp;
					f4cur = f4cur->next;
				}
			}
			f3cur=f3cur->next;
		}
	}

/* 4-element families */
	for (i = 0; i<16; i++) {
		f4cur=f4;
		while (f4cur) {
			unsigned u = f4cur->subset[2];
			if (lt(u, subset[i])) {
				unsigned temp[5];
				struct family *fp;

				temp[0]=f4cur->subset[0];
				temp[1]=f4cur->subset[1];
				temp[2]=f4cur->subset[2];
				temp[3]=u;
				temp[4]=subset[i];
				fp=mkfam(5, temp);
				if (f5 == NULL)
					f5=f5cur=fp;
				else {
					f5cur->next = fp;
					f5cur = f5cur->next;
				}
			}
			f4cur=f4cur->next;
		}
	}

	print_list(f2);
#if 0
	print_list(f3);
	print_list(f4);
	print_list(f5);
#endif
}

void print_list(struct family *fp)
{
	while (fp) {
		printfam(fp);
		fp=fp->next;
	}
}

struct family *mkfam(int n, unsigned *v)
{
	struct family *fp = malloc(sizeof(struct family));

	if (fp==NULL) {
		fprintf(stderr, "cannot get memory\n");
		exit(1);
	}
	fp->next = NULL;
	fp->n = n;
	while (--n)
		fp->subset[n] = v[n];
	return fp;
}

void ps(char *s, unsigned subset)
{
	int i;

	if (subset==0) {
		snprintf(s, STRINGLEN, "null");
		return;
	}

	for (i=0; i<4; i++) {
		if (subset & 1) {
			snprintf(s, 2, "%d", i+1);
			s++;
		}
		subset >>= 1;
	}
}

int lt(int a, int b)
{
	int i;

	if (a==b) return 0;
	for (i=0; i<4; i++) {
		int az, bz;
		az = a & 1;
		bz = b & 1;
		if (az==1 && bz==0)
			return 0;
		a >>= 1;
		b >>= 1;
	}
	return 1;
}

void printfam(struct family *fp)
{
	int i, first=0;
	char s[STRINGLEN];

	for (i=0; i<(fp->n); i++) {
		if (first==0)
			first=1;
		else printf(", ");
		ps(s, fp->subset[i]);
		printf("%s", s);
	}
	printf("\n");
}