/*
 * model.h
 *
 *  Created on: 19/02/2009
 *      Author: mateu hunter
 */

#ifndef HELPERS_H_
#define HELPERS_H_

#include <string.h>
#define MAX_LIST_LENGTH 100

struct node {
    char *first_name;
    char *last_name;
    struct node *next;
    struct node *previous;
};

#define VERBOSE_HEADER 0
#define DEBUG_HEADER 0

/* Function Signatures */

int pointer_is_NULL(struct node *ptr);
int is_head(struct node *head);
int number_of_nodes(struct node *head);

struct node* create_initial_node(char *first_name, char *last_name);
struct node* add_node(struct node *head, char *first_name, char *last_name,
        int position);
struct node* add_node_head(struct node *head, char *first_name,
        char *last_name, int position);
struct node* add_node_tail(struct node *head, char *first_name,
        char *last_name, int position);
struct node* add_node_between(struct node *head, char *first_name,
        char *last_name, int position);

struct node* position_cursor(struct node *head, int position);
struct node* get_node(struct node *head, int position);
struct node* get_tail_node(struct node *head);

struct node* delete_node(struct node *head, int position);
struct node* delete_node_head(struct node *head);
struct node* delete_node_tail(struct node *head);
struct node* delete_node_between(struct node *head, int position);
struct node* free_all_nodes(struct node *head);
void search_nodes(struct node *head, char search_field, char *search_term);
struct node* reverse_nodes(struct node *head);
struct node* sort_nodes(struct node *head, int sort_type);

void print_all_nodes(struct node *head);
void not_head_message(void);
void pointer_is_NULL_message(void);

/* Since we are, by convention, passing and returning the head node
 * to most all these non-void arg functions, we are assuming we always have
 * access to head or the programmer screwed up.  Thus the first element,
 * head, is alway around, and I'm not going to write a function
 * head = get_head(head);
 */

/* Function Definitions */

struct node* create_initial_node(char *first_name, char *last_name) {
    struct node *tmp = (struct node*) malloc(sizeof(struct node));
    tmp->first_name = first_name;
    tmp->last_name = last_name;
    tmp->next = NULL;
    tmp->previous = NULL;
    return tmp;
}

struct node* add_node(struct node *head, char *first_name, char *last_name,
        int position) {

    /* insert at head */
    if (position == 0) {
        head = add_node_head(head, first_name, last_name, position);
    }
    /* insert at tail */
    else if (position == number_of_nodes(head)) {
        head = add_node_tail(head, first_name, last_name, position);
    }
    /* insert between two nodes */
    else if (position > 0 && position < number_of_nodes(head)) {
        head = add_node_between(head, first_name, last_name, position);
    } else {
        printf("Warning: you entered a position number out of range: %d.\n",
                position);
        printf("No action taken.\n");
        free(first_name);
        free(last_name);
        /* exit(-1); */
    }
    return head;
}

struct node* add_node_between(struct node *head, char *first_name,
        char *last_name, int position) {
    struct node *tmp = (struct node*) malloc(sizeof(struct node));
    struct node *cursor = NULL;
    if (is_head(head)) {
        cursor = position_cursor(head, position);
        if (VERBOSE_HEADER) {
            printf("We have a tween case.\n");
        }
        tmp->first_name = first_name;
        tmp->last_name = last_name;
        tmp->previous = cursor;
        tmp->next = cursor->next;
        cursor->next->previous = tmp;
        cursor->next = tmp;
        return head;
    } else {
        not_head_message();
        exit(-1);
    }
}
struct node* add_node_head(struct node *head, char *first_name,
        char *last_name, int position) {
    struct node *tmp = (struct node*) malloc(sizeof(struct node));
    if (is_head(head)) {
        if (VERBOSE_HEADER) {
            printf("We have a head case.\n");
        }
        tmp->first_name = first_name;
        tmp->last_name = last_name;
        tmp->next = NULL;
        tmp->previous = head;
        tmp->previous->next = tmp;
        /* tmp is new head */
        return tmp;
    } else {
        not_head_message();
        exit(-1);
    }
}

struct node* add_node_tail(struct node *head, char *first_name,
        char *last_name, int position) {
    struct node *tmp = (struct node*) malloc(sizeof(struct node));
    struct node *cursor = NULL;
    if (is_head(head)) {
        if (VERBOSE_HEADER) {
            printf("We have a tail case.\n");
        }
        cursor = position_cursor(head, position - 1);
        tmp->first_name = first_name;
        tmp->last_name = last_name;
        tmp->previous = NULL;
        tmp->next = cursor;
        tmp->next->previous = tmp;
        return head;
    } else {
        not_head_message();
        exit(-1);
    }
}

int pointer_is_NULL(struct node *ptr) {
    int the_truth;
    if (VERBOSE_HEADER) {
        printf("Is the pointer NULL?\n");
    }
    the_truth = ptr == NULL ? 1 : 0;
    return the_truth;
}

int is_head(struct node *head) {
    if (VERBOSE_HEADER) {
        printf("Is head?\n");
    }
    if (head == NULL) {
        if (DEBUG_HEADER) {
            printf("pointer IS NULL.\n");
        }
        return 0;
    } else if (head->next == NULL) {
        if (DEBUG_HEADER) {
            printf("head->next is NULL, got head.");
        }
        return 1;
    } else {
        if (DEBUG_HEADER) {
            printf("head->next is not NULL, not got head.");
        }
        return 0;
    }
}

int number_of_nodes(struct node *head) {
    int number_of_nodes = 0;
    struct node *cursor = NULL;
    if (VERBOSE_HEADER) {
        printf("Calculating number of nodes...\n");
    }
    /* Make sure we got real head */
    if (is_head(head)) {
        cursor = head;
        number_of_nodes = 1;
        while ( (cursor = cursor->previous) ) {
            number_of_nodes++;
        }
    }
    return number_of_nodes;
}

/* Position is zero based (i.e. position 0 is for the 1st element) */
struct node* position_cursor(struct node *head, int position) {
    int i = 0;
    struct node *cursor = NULL;
    cursor = head;
    for (; (i < position) && (i < number_of_nodes(head)); i++) {
        cursor = cursor->previous;
    }
    return cursor;
}

struct node* get_tail_node(struct node *head) {
    return position_cursor(head, number_of_nodes(head) - 1);
}

struct node* get_node(struct node *head, int position) {
    return position_cursor(head, position);
}

struct node* delete_node(struct node *head, int position) {
    /* Handle NULL case with slight grace */
    if (head == NULL) {
        pointer_is_NULL_message();
    }
    /* delete head */
    if (position == 0) {
        /* printf("Deleting head.\n"); */
        head = delete_node_head(head);
    }
    /* delete tail */
    else if (position == number_of_nodes(head) - 1) {
        head = delete_node_tail(head);
    }
    /* delete a node between two nodes */
    else if (position > 0 && position < number_of_nodes(head) - 1) {
        head = delete_node_between(head, position);
    } else {
        printf(
                "Warning: you entered a position number out of range: %d.\nNo action taken.\n",
                position);
        /* exit(-1); */
    }
    return head;
}

struct node* delete_node_head(struct node *head) {
    if (number_of_nodes(head) == 0) {
        printf("Given empty list. You expecting something else?\n");
        return NULL;
    } else if (number_of_nodes(head) == 1) {
        if (VERBOSE_HEADER) {
            printf("Given one item list.\n");
        }
        free(head->first_name);
        free(head->last_name);
        free(head);
        return NULL;
    } else {
        struct node *cursor;

        if (VERBOSE_HEADER) {
            printf("Given multiple item list.\n");
        }
        cursor = head->previous;
        cursor->next = NULL;
        free(head->first_name);
        free(head->last_name);
        free(head);
        /* cursor is new head */
        return cursor;
    }
}
/* Delete nodes but not names */
struct node* delete_cursor_head(struct node *head) {
    if (number_of_nodes(head) == 0) {
        printf("Given empty list. You expecting something else?\n");
        return NULL;
    } else if (number_of_nodes(head) == 1) {
        if (VERBOSE_HEADER) {
            printf("Given one item list.\n");
        }
        free(head);
        return NULL;
    } else {
        struct node *cursor;

        if (VERBOSE_HEADER) {
            printf("Given multiple item list.\n");
        }
        cursor = head->previous;
        cursor->next = NULL;
        free(head);
        /* cursor is new head */
        return cursor;
    }
}
struct node* delete_node_tail(struct node *head) {
    if (head == NULL) {
        return NULL;
    } else if (number_of_nodes(head) == 1) {
        free(head->first_name);
        free(head->last_name);
        free(head);
        return NULL;
    } else {
        struct node *tail;
        struct node *cursor;
        tail = get_tail_node(head);
        cursor = tail->next;
        cursor->previous = NULL;
        free(tail->first_name);
        free(tail->last_name);
        free(tail);
        return head;
    }
}

/* use of tweener to label a node between two others
 * origins trivia:  a basketball player caught between two positions.
 * e.g D.J. may be a tweener in the NBA because he's not a
 * true power forward at that level, nor is he a small forward.
 */
struct node* delete_node_between(struct node *head, int position) {
    struct node *tweener_node = NULL;
    tweener_node = get_node(head, position);
    tweener_node->next->previous = tweener_node->previous;
    tweener_node->previous->next = tweener_node->next;
    free(tweener_node->first_name);
    free(tweener_node->last_name);
    free(tweener_node);
    return head;
}

struct node* free_all_nodes(struct node *head) {
    int i = 0;
    int total_number_of_nodes = number_of_nodes(head);

    if (number_of_nodes(head) == 1) {
        /* Just have head to free */
        free(head->first_name);
        free(head->last_name);
        free(head);
    } else {
        for (; i < total_number_of_nodes; i++) {
            /* Keep chopping of the head 'til there is no more.
             * Doesn't seem efficient since we really just need to
             * free all the nodes and not relink new head each time,
             * but delete_node() was already written and available
             * for reuse.
             * */
            if (DEBUG_HEADER) {
                printf("Head is %s %s.\n", head->first_name, head->last_name);
            }
            head = delete_node(head, 0);
        }
    }
    return head;
}

/* Used to free up node pointers but leave names around
 * Useful for reverse and could be used with sort.
 */
struct node* free_all_cursors(struct node *head) {
    int i = 0;
    int total_number_of_nodes = number_of_nodes(head);

    if (number_of_nodes(head) == 1) {
        /* Just have head to free */
        free(head);
    } else {
        for (; i < total_number_of_nodes; i++) {
            /* Keep chopping of the head 'til there is no more.
             * Doesn't seem efficient since we really just need to
             * free all the nodes and not relink new head each time,
             * but delete_node() was already written and available
             * for reuse.
             * */
            if (DEBUG_HEADER) {
                printf("Head is %s %s.\n", head->first_name, head->last_name);
            }
            head = delete_cursor_head(head);
        }
    }
    return head;
}
void search_nodes(struct node *head, char search_field, char *search_term) {
    struct node *cursor = NULL;
    int someone_found = 0;
    /* Do we have a proper list? */
    if (is_head(head)) {
        cursor = head;
        /* Handle search on first name */
        do {
            if (search_field == 'f') {
                if (strcmp(cursor->first_name, search_term) == 0) {
                    someone_found = 1;
                    printf("Found person with matching first name: %s %s\n",
                            cursor->first_name, cursor->last_name);
                }
            } else if (search_field == 'l') {
                if (strcmp(cursor->last_name, search_term) == 0) {
                    someone_found = 1;
                    printf("Found person with matching last name: %s %s\n",
                            cursor->first_name, cursor->last_name);
                }
            }
        } while ( (cursor = cursor->previous) );
    }
    if (!someone_found) {
        printf("No one found matching: %s\n", search_term);
    }
}

struct node * reverse_nodes(struct node *head) {
    struct node *new_head = NULL;
    struct node *cursor = NULL;
    struct node *tail = NULL;
    int i;

    /* return head when list has only one element */
    if (number_of_nodes(head) == 1) {
        return head;
    }
    tail = get_tail_node(head);
    cursor = tail;
    /* create one headed monster */
    new_head = create_initial_node(tail->first_name, tail->last_name);
    /* add tweener nodes */
    for (i = 1; i < number_of_nodes(head) - 1; i++) {
        cursor = cursor->next;
        new_head = add_node(new_head, cursor->first_name, cursor->last_name, i);
    }
    /* add new tail */
    new_head = add_node_tail(new_head, head->first_name, head->last_name,
            number_of_nodes(head) - 1);
    free_all_cursors(head);
    return new_head;
}

struct node * sort_nodes(struct node *head, int sort_type) {
    struct node *new_head = NULL;
    struct node *cursor = NULL;
    struct node *new_cursor = NULL;
    int i, j, node_sorted;

    /* return head when list has only one element */
    if (number_of_nodes(head) == 1) {
        return head;
    }
    cursor = head;
    /* create one headed monster */
    new_head = create_initial_node(head->first_name, head->last_name);
    /* add tweener nodes */
    for (i = 1; i < number_of_nodes(head) - 1; i++) {
        cursor = cursor->previous;
        new_cursor = new_head;
        node_sorted = 0;
        /* check current un-sorted node against sorted nodes */
        for (j = 0; j < number_of_nodes(new_head); j++) {
            if (strcmp(cursor->first_name, new_cursor->first_name) == -1) {
                new_head = add_node(new_head, cursor->first_name,
                        cursor->last_name, j);
                node_sorted = 1;
                break;
            }
            new_cursor = new_cursor->previous;
        }
        /* put node at tail if it's not less than any other */
        if (!node_sorted) {
            new_head = add_node_tail(new_head, cursor->first_name,
                    cursor->last_name, number_of_nodes(new_head));
        }
    }
    /* add new tail */
    free_all_cursors(head);
    return new_head;
}

/* Print functions */

void print_all_nodes(struct node *head) {
    struct node *cursor = NULL;
    cursor = head;
    do {
        printf("My name is %s %s.\n", cursor->first_name, cursor->last_name);
    } while ( (cursor = cursor->previous) );
}

void not_head_message(void) {
    printf("ERROR. You did not give head.\n");
}

void pointer_is_NULL_message(void) {
    printf(
            "Warning. Your node is empty.  Maybe you want a more interesting node?\n");
}
#endif /* HELPERS_H_ */

My tags:

 

Popular tags: