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

//#define LENGTH 26;

typedef struct dllist
{
    char word[26];
    struct dllist *next;
    struct dllist *prev;
}
dllnode;
// this will take more bytes of memory
// than a singly linked list
// don't use if you don't want to delete elements

// why can't you call it dllnode initially?


/*
singly linked lists are easy to add to, but hard to remove from
doubly linked lists resolve this issue

singly linked lists exted the ability to collect and organize data,
however they can only ever move in one direction through the list
this makes it difficult to delete a node

a doubly linked list allows moving forward and backward
through the list, all by adding one extra pointer to our
struct definition
*/

bool find(dllnode *head, char *string);

dllnode *dlinsert(dllnode *head, char *string)
{
    //dllnode *tmp = head->next;
    //dllnode *tmp = head;
    dllnode *input = malloc(sizeof(dllnode));

    for (int i = 0; string[i] != '\0'; i++)
    {
        input->word[i] = string[i];
    }
    input->next = head;
    head->prev = input;
    //input->next = head;
    //input->prev = NULL;
    return input;
    //free(input);
    // how to make sure I didn't run out of memory
    // have i inserted correctly?
    //will i orphan the entire list this way?... it would seem not
    // the old hea
}
/*

steps involved

a. dynamically allocate space for a new dllnode
b. check to make sure we didn't run out of memory.
    ... how to
c. populate and insert the node at the beginning of the linked list
d. fix the prev pointer of the old head of the linked list
    each node points to two nodes
    the old head of the linked list needs to point backwards
    to the new head of the linked list
e. return a pointer to the new head of the linked list

*/

unsigned int hash(const char *word)// to hash a-z 0-26, maybe use ascii value and subtract?
{

    char c;
    int val = 0;
    //int cval;
    for (int i = 0; word[i] != '\0'; i++)
    {
        c = word[i];
        if (isalpha(c))
        {
            if (isupper(c))
            {
                //c = word[i]
                val += c - 65;
            }
            if (islower(c))
            {
                val += c - 97;
            }
            if (c == 13)
            {
                continue;
            }
        }
        else
            continue;

    }
    return val%26;
}
/*
linked lists both sinly and doubly support efficient insertion and deletion of elements
    these operations can be done in constant time
the downside id the ability to randomly access list elements is gone... one must search
through the entire list and thus search is now linear time
*/
bool find(dllnode *head, char *string)
{
    dllnode *trav = head;
    bool found = false;

    for (int i = 0; trav != NULL; i++)
    {
        for (int j = 0; trav->word[j] != '\0'; j++)
        {
            if (trav->word[j] == string[j]) // this returns true if any of the characters match
            {
                found = true;
                //continue;?
            }
            else
                found = false;
        }
        trav=trav->next;
    }
    return found;
}

/*
deleting nodes is an advantage doubly linked lists offer over singly linked lists
deleting a linked node
steps involved
    a. fix the pointers of the surrounding nodes to "skip over" target
    b. free target

*/
void erase(dllnode *target)
{
    target->prev->next = target->next;
    target->next->prev = target->prev;
    free(target);
}

/*
void destroy(slnode* head)
{

}


steps involved
    a. if you've reached a null pointer, stop
    b. delete the rest of the list..... how to delete? in a loop? set the value to null? empty?
    c. free the current node

    recursion
    delete everyone else
    then delete me

    in order to work with linked lists effectively, there are a number of operations to understand
        1. create a linked list when it doesn't already exist
        2. search through a linked list to find an element
        3.insert a new node into the linked list.
        4. delete a single element from a linked list
            this is not easy as you need to keep two pointers
            doubly linked lists resolve this issue
        5. delete an entire linked list
*/
//make a function that will add an input string to the word field of a dllnode
dllnode *addstr(dllnode *node,char *string)
{
    node = malloc(sizeof(dllnode));
    for (int i = 0; string[i] != '\0';i++)
    {
        node->word[i] = string[i];
    }
    //for(int i = 0; string[i] != '\0'; i++)
    return node;
    //free(node);
}

int main(int argc, char *argv[])
{

    //make a function that will add an input string to the word field of a dllnode

    dllnode *fruit1 = malloc(sizeof(dllnode));
    dllnode *fruit2 = malloc(sizeof(dllnode));
    dllnode *fruit3 = malloc(sizeof(dllnode));

    addstr(fruit1, "apple");
    /*
    char *f1 = "apple";
    char *f2 = "avocado";
    char *f3 = "papaya";

    for (int i = 0; f1[i] != '\0'; i++)
    {
        fruit1->word[i] = f1[i];
    }
    */
    fruit1->next = fruit2;
    fruit1->prev = NULL;
    /*
    for (int i = 0; f2[i] != '\0'; i++)
    {
        fruit2->word[i] = f2[i];
    }
    */
    addstr(fruit2, "avocado");
    fruit2->next = fruit3;
    fruit2->prev = fruit1;
    /*
    for (int i = 0; f3[i] != '\0'; i++)
    {
        fruit3->word[i] = f3[i];
    }
    */
    addstr(fruit3, "papaya");
    fruit3->next = NULL;
    fruit3->prev = fruit2;

    printf("\n\nnow printing linked list of fruits: \n\n");
    printf("fruit1->word prints:  %s\n",fruit1->word);
    printf("fruit1->next->word prints:  %s\n",fruit1->next->word);
    printf("fruit1->prev->word prints:  %s\n",fruit1->prev->word);
    printf("fruit2->word prints:  %s\n",fruit2->word);
    printf("fruit2->next->word prints:  %s\n",fruit2->next->word);
    printf("fruit2->prev->word prints:  %s\n",fruit2->prev->word);
    printf("fruit3->next->word prints:  %s\n\n",fruit3->next->word);
    printf("fruit3->word prints:  %s\n\n",fruit3->word);
    printf("fruit3->prev->word prints:  %s\n\n",fruit3->prev->word);

    dllnode *band1 = malloc(sizeof(dllnode));
    dllnode *band2 = malloc(sizeof(dllnode));
    dllnode *band3 = malloc(sizeof(dllnode));

    char *b1 = "Soundgarden"; // points to nirvana next
    char *b2 = "Nirvana"; // points to mudhoney next
    char *b3 = "Mudhoney";

    for (int i = 0; b1[i] != '\0'; i++)
    {
        band1->word[i] = b1[i];
    }
    band1->next = band2;
    band1->prev = NULL;

    for (int i = 0; b2[i] != '\0'; i++)
    {
        band2->word[i] = b2[i];
    }
    band2->next = band3;
    band2->prev = band1;

    for (int i = 0; b3[i] != '\0'; i++)
    {
        band3->word[i] = b3[i];
    }
    band3->next = NULL;
    band3->prev = band2;

    printf("band1->word prints %s\n", band1->word);
    printf("band1->next->word prints %s\n", band1->next->word);

    dllnode *prog1 = malloc(sizeof(dllnode));
    dllnode *prog2 = malloc(sizeof(dllnode));
    dllnode *prog3 = malloc(sizeof(dllnode));

    char *p1 = "Photoshop";
    char *p2 = "Maya";
    char *p3 = "Zbrush";

    // copy characters from pointers to word field

    for (int i = 0; p1[i] != '\0'; i++)
    {
        prog1->word[i] = p1[i];
    }
    prog1->next = prog2;
    prog1->prev = NULL;

    for (int i = 0; p2[i] != '\0'; i++)
    {
        prog2->word[i] = p2[i];
    }
    prog2->next = prog3;
    prog2->prev = prog1;

    for (int i = 0; p3[i] != '\0'; i++)
    {
        prog3->word[i] = p3[i];
    }
    prog3->next = NULL;
    prog3->prev = prog2;



    //node *table[N] = malloc(N*sizeof(node));

    dllnode *table[3];
    table[0] = fruit1;
    table[1] = band1;
    table[2] = prog1;

    for (int i = 0; i < 3; i++)
    {
        printf("table[%i]->word prints: %s\n",i,table[i]->word);
        printf("table[%i]->next->word prints: %s\n",i,table[i]->next->word);
        printf("table[%i]->next->next->word prints: %s\n",i,table[i]->next->next->word);

    }


    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; table[i]->word[j] != '\0'; j++)
        {

            if (table[i]->word[j] == '\0')
            {
                printf("%c \n",table[i]->word[j]);
            }
            else
            {
                printf("%c \n", table[i]->word[j]);
            }
        }
    }

    printf("\n\n");

    printf("cursor word loop forwards\n");
    for (int i = 0; i < 3; i++) // how do i know how big table is?
    {
        dllnode *cursor = table[i];
        //for (int j = 0; cursor->next != NULL; j++)
        for (int j = 0; cursor != NULL; j++)
        {
            printf("%s ", cursor->word);
            cursor = cursor->next;
        }
    }
    printf("\n\n");

    printf("cursor word loop backwards\n");
    for (int i = 2; i >= 0; i--) // how do i know how big table is?
    {
        dllnode *cursor = table[i]->next->next;
        //for (int j = 0; cursor->next != NULL; j++)
        for (int j = 0; cursor != NULL; j++)
        {
            printf("%s ", cursor->word);
            cursor = cursor->prev;
        }
    }
    printf("\n\n");

    //bool found = false;
    printf("testing the find function");

    bool resultm = find(table[2],"Maya");
    printf("now looking for a word with the find() function\n");
    printf("does the word maya appear in the table[2]?\n");
    printf("looking for the word Maya in table[2]\n");
    printf("find(table[2],resultm) prints: \n");
    printf("%d\n",resultm);
    printf("resultm prints:\n");
    if (resultm)
    {
        printf("Found!\n\n");
    }
    else
        printf("Not Found :(\n\n");

    printf("searching table[1] for papaya\n");
    bool resultp = find(table[0], "papaya");
    if (resultp)
    {
       printf("papaya found!\n");
    }
    else
        printf("papaya not found :(");

    bool results = find(table[1], "stairs");
    if (results)
    {
       printf("stairs found!\n");
    }
    else
        printf("stairs not found :(\n");

    printf("the words in table[1] are:\n\n");

    dllnode *cursor = table[1];
    for (int j = 0; cursor != NULL; j++)
    {
        printf("%s ", cursor->word);
        cursor = cursor->next;
    }
    printf("\n");

    printf("does the word boobs appear in table[1]?\n");
    bool resultb = find(table[1], "boobs");
    if (resultb)
    {
       printf("boobs found!\n");
    }
    else
        printf("boobs not found :(\n");

    printf("testing the dlinsert function:\n");

    printf("the words in table[0] before dlinsert() are:\n\n");

    dllnode *traverse = table[0];
    for (int j = 0; traverse != NULL; j++)
    {
        printf("%s ", traverse->word);
        traverse = traverse->next;
    }
    printf("\n\n");

    /*
    dllnode *insertnod = malloc(sizeof(dllnode));

    char *insword = "hereiam!";
    for (int i = 0; insword[i] != '\0'; i++)
    {
        insertnod->word[i] = insword[i];
    }
    */

    char *insword = "hereiam!";
    char *outword = table[0]->next->word;

    table[0] = dlinsert(table[0], insword);


    printf("the words in table[0] after dlinsert() are:\n\n");

    traverse = table[0];
    for (int j = 0; traverse != NULL; j++)
    {
        printf("%s ", traverse->word);
        traverse = traverse->next;
    }
    printf("\n\n");

    printf("testing the erase function:\n");
    printf("trying to erase the node stored at table[0]->next\n");
    erase(table[0]->next);
    printf("the words in table[0] after erase() are: \n"); // delete is a key word and shouldn't be used?

    //table[0] = erase(table[0]->next);

    traverse = table[0];
    for (int j = 0; traverse != NULL; j++)
    {
        printf("%s ", traverse->word);
        traverse = traverse->next;
    }
    printf("\n\n");





    free(prog1);
    free(prog2);
    free(prog3);
    free(band1);
    free(band2);
    free(band3);
    free(fruit1);
    free(fruit2);
    free(fruit3);
    //free(input);
}