/* program to demonstrate use of pointers to pointers
 * in connection with a 2D array of strings,
 * and use of a NULL pointer as a sentinel to
 * end the list of pointers. Richard Kay, Jan 06 */

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

#define MAXNAMESIZE 50

char **get_names(void);
void print_names(char **names);
void sort_names(char **names);
void free_names(char **names);

int main(void){
	/* test code for other functions */
	char **names;
	names=get_names();
	sort_names(names);
	printf("\nThe sorted names are:\n");
	print_names(names);
	free_names(names);
	return 0;
}

char **get_names(void){
	/* inputs names into dynamically allocated storage */
	char **names,buff[MAXNAMESIZE];
	int num,i,lenname;
	printf("how many names ?\n");
	scanf("%d",&num);
	fflush(stdin);
	/* allocate space for array of pointers plus NULL terminator */
	names=(char**)malloc(sizeof(char*)*(num+1));
	printf("OK, enter %d names\n",num);
	for(i=0;i<num;i++){
		scanf("%s",buff); /* input name */
		lenname=strlen(buff); /* measure name length */
		names[i]=(char*)malloc(lenname+1); /* alloc space */
		strcpy(names[i],buff); /* copy name to allocated space */
	}
	names[num]=NULL; /* sentinel to mark end of list */
	return names; /* space for names is allocated by malloc 
			 so is not automatically freed */	 
}

void print_names(char **names){ /* prints set of names */
	char *name;
	int i=0;
	for(i=0;names[i];i++) /* loop terminates at NULL sentinel */
		printf("%s\n",names[i]);
}

void sort_names(char **names){
	/* sorts NULL terminated array of strings
	 * using bubble sort algorithm */
	int i,j=0,num=0;
	char *temp;
	/* count names */
	while(names[num++]);
	num--; /* num indexes last name */
	for(j=1;j<=num;j++) /* outer loop */
		for(i=0;i<num-j;i++) /* inner loop */
			if(strcmp(names[i],names[i+1])>0){
				/* swap pointers */
				temp=names[i];
				names[i]=names[i+1];
				names[i+1]=temp;
		}
}

void free_names(char **names){ /* frees all storage for names */
	int i;
	for(i=0;names[i];i++) /* loop ends at NULL */
		free(names[i]);
	free(names);
}