#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <dirent.h>
#include "alphabetize.h"

struct node_t *get_head(struct node_t *list)
{
    if(!list)
	return NULL;

    while(list->prev)
	list=list->prev;

    return list;
}


struct node_t *get_tail(struct node_t *list)
{
    if(!list)
	return NULL;

    while(list->next)
	list=list->next;

    return list;
}


int get_count(struct node_t *list)
{
    int count=0;
    
    if(!list)
	return count;
    
    if((list->next == NULL) && (list->prev == NULL))
	count=1;
    else if((list->prev == NULL) && (list->next != NULL)) 
	for(; list; count++)
	    list=list->next;
    else
	return get_count(get_head(list));
    
    return count;
}


struct node_t *get_dir_list(char *dir_path)
{
    DIR *dstream=NULL;
    struct dirent *dir=NULL;
    struct node_t *tail=NULL;
    
    if(!(dstream=opendir(dir_path)))
	return NULL;

    while((dir=readdir(dstream)))
	if(dir->d_name[0] != '.')
	    if(!(tail=append_string(tail, dir->d_name)))
		return NULL;
    
    closedir(dstream);

    return get_head(tail);
}


struct node_t *append_string(struct node_t *list, char *str)
{
    struct node_t *traverser=NULL, *n=NULL;
    
    n=(struct node_t *)malloc(sizeof(struct node_t));
    if(n == NULL)
	return NULL;

    memset(n, 0, sizeof(n));

    if(str == NULL)
	n->string=NULL;
    else {
        n->string = (char *)malloc(strlen(str) + 1);
	if(n->string == NULL)
	    return NULL;
	
	memset(n->string, 0, strlen(str) + 1);
	memcpy(n->string, str, strlen(str));   
    }
    
    if(list) { 
       traverser = list;
    
       while(traverser->next)
	   traverser = traverser->next;
    
       traverser->next = n;
       n->prev=traverser;
    }
    else
       n->prev=NULL;
    
    n->next = NULL;

    return n;
}
    

struct node_t *alpha_mergesort(struct node_t *list)
{
    struct node_t *merged_list=list, *other_list=NULL;

    if(list && list->next) {
        other_list=divide_list(list);
        list=alpha_mergesort(list);
        other_list=alpha_mergesort(other_list);
        merged_list=alpha_merge(list, other_list);
    }

    return merged_list;
}


struct node_t *divide_list(struct node_t *list)
{
    struct node_t *mid=list;
    struct node_t *traverser=list->next->next;

    while(traverser) {
        traverser=traverser->next;
        mid=mid->next;

        if(traverser)
            traverser=traverser->next;
    }

    traverser=mid->next;
    traverser->prev=NULL;
    mid->next=NULL;

    return traverser;
}


struct node_t *alpha_merge(struct node_t *list1, struct node_t *list2)
{
    struct node_t *last_ref=NULL, *merged=NULL;

    if(strcmp(list1->string, list2->string) < 0) {
        merged=list1;
        list1=list1->next;
    }
    else {
        merged=list2;
        list2=list2->next;
    }

    merged->prev=NULL;
    last_ref=merged;

    while(list1 && list2) {
        if(strcmp(list1->string, list2->string) < 0) {
            last_ref->next=list1;
	    list1->prev=last_ref;
       	    last_ref=list1;
            list1=list1->next;
        }
        else {
            last_ref->next=list2;
	    list2->prev=last_ref;
            last_ref=list2;
            list2=list2->next;
        }
    }

    if(list1) {
        last_ref->next=list1;
	list1->prev=last_ref;
    }
    else {
        last_ref->next=list2;
	list2->prev=last_ref;
    }

    return merged;
}


void free_list(struct node_t *list) 
{
    if(!list)
	return;
    
    /* single node */
    if((list->next == NULL) && (list->prev == NULL)) {
        free(list->string);	
	free(list);
    }
    /* head */
    else if((list->next != NULL) && (list->prev == NULL)) { 
        for(list=list->next; list->next; list=list->next) {
	    free(list->prev->string);
	    free(list->prev);
	}

	free(list->prev->string);
	free(list->prev);
	free(list->string);
	free(list);
    }
    /* any other node */
    else 
	free_list(get_head(list));
}