/***************************************************************************
*   Copyright (C) 2006 by Kessia Pinheiro                                 *
*   kessiapinheiro@gmail.com                                              *
*                                                                         *
*   This program is free software; you can redistribute it and/or modify  *
*   it under the terms of the GNU General Public License as published by  *
*   the Free Software Foundation; either version 2 of the License, or     *
*   (at your option) any later version.                                   *
*                                                                         *
*   This program is distributed in the hope that it will be useful,       *
*   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
*   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
*   GNU General Public License for more details.                          *
*                                                                         *
*   You should have received a copy of the GNU General Public License     *
*   along with this program; if not, write to the                         *
*   Free Software Foundation, Inc.,                                       *
*   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "include/trabalho_t.h"

int hash(char *s1);
int getNumber(void);
ListAlpha * newNodeDLink(void);
ParagList * newNodePgLink(void);
ListWord * newNodeTree(char *s);
void startVet(VetList *vet);
void insertWordTree(ListWord **rootTree, char *s);
void insertAlpha(ListAlpha **alphaf, ListAlpha **alphab, char *s);
void insertParag(ParagList **parag, int number);
void insertLine(ParagList **parag, char *s, int nline);
ListWord ** searchNodeTree(ListWord **rootTree, char *s);
void searchPredNodeTree(ListWord *rootT, ListWord **rootTN);
void deleteNodeTree(ListWord **noder, ListWord **rootTree);
void deleteNodeList(ListAlpha **alphaf, ListAlpha **alphab, char *s);
void printTreeVet(ListWord *rootT);
void printRange(ListAlpha *alphaF, ListAlpha *alphaB, char *ch, char *s1, char *s2);
void startPath(ListWord *rootT, int level);
void listLevelTree(ListWord *rootT, char *path[], int pathLevel, int level);
void listLines(ParagList *parag, char *s);
void listPosLines(ParagList *parag, char *s);
void lineParag(ParagList *parag, int np, int nl);
void listLinesPos(ParagList *parag, int np, int nl, int pos);
void listNumWords(ParagList *parag, char *s);

int main(void) {
    int k, ihash, nline, pg, posicao, np, nl;
    int NUM_LINHAS;
    char comand[1];
    char texto[DIM_LINHA];
    char word[DIM_WORD];
    char w1[DIM_WORD];
    char w2[DIM_WORD];
    char w3[DIM_WORD];
    char *ptexto, *ltexto, *pcomand, *pword, *ps1, *ps2;
    VetList vet;
    ParagList *paragHead = NULL;
    ListAlpha *alphaHeadF = NULL;
    ListAlpha *alphaHeadB = NULL;
    ListWord *rootTree = NULL; /*root of tree*/
    ListWord **noder = NULL;

    NUM_LINHAS = getNumber();
    startVet(&vet);

    pg = 1;
    nline = 1;
    insertParag(&paragHead, pg);

    for (k = 0;k < NUM_LINHAS; k++) {
        fgets(texto, DIM_LINHA - 1, stdin);
        if (texto[0] == '\n') {
            pg++;
            nline = 0;
            insertParag(&paragHead, pg);
        } else {
            ltexto = strtok (texto, "\n"); /* remove o '\n' do final da linha */
            insertLine(&paragHead, ltexto, nline); /* insere a a string texto[DIM_LINHA] na lista de linhas*/
            ptexto = strtok (texto, " .,;:!-\n");
            while (ptexto != NULL) {
                if (strlen(ptexto) < 30) {
                    ihash = hash(ptexto) % MAX;
                    insertWordTree(&(vet.VetL[ihash]), ptexto);
                    insertAlpha(&alphaHeadF, &alphaHeadB, ptexto);
                    ptexto = strtok (NULL, " .,;:!-\n");
                } else
                    return EXIT_FAILURE;
            }
        }
        nline++;
    }

    do {
        do{
            fgets(comand, DIM_WORD - 1, stdin);
            pcomand = strtok (comand, "\n");
        } while(pcomand == NULL);
        switch (*pcomand) {
        case 'o':        /* Questão 1 */
            fgets(w1, DIM_WORD - 1, stdin);
            pword = strtok (w1, "\n");
            fgets(w2, DIM_WORD, stdin);
            ps1 = strtok (w2, "\n");
            fgets(w3, DIM_WORD, stdin);
            ps2 = strtok (w3, "\n");
            printRange(alphaHeadF, alphaHeadB, pword, ps1, ps2);
            break;
        case 'a':        /* Questão 2 */
            posicao = getNumber();
            rootTree = vet.VetL[posicao];
            if(posicao >= 0 && posicao < MAX){
                if (rootTree != NULL){
                    printTreeVet(rootTree);
                    printf("\n");
                }
            }
            break;
        case 'l':        /* Questão 3 */
            fgets(word, DIM_WORD, stdin);
            pword = strtok (word, "\n");
            listLines(paragHead, pword);
            break;
        case 'n':        /* Questão 4 */
            np = getNumber();
            nl = getNumber();
            if(nl > 0 && nl < MAX)
                lineParag(paragHead, np, nl);
            break;
        case 'p':        /* Questão 5 */
            fgets(word, DIM_WORD, stdin);
            pword = strtok (word, "\n");
            listPosLines(paragHead, pword);
            break;
        case 'q':        /* Questão 6 */
            nl = getNumber();
            np = getNumber();
            if(nl > 0 && nl < MAX){
                posicao = getNumber();
                listLinesPos(paragHead, np, nl, posicao);
            }
            break;
        case 'v':        /* Questão 7 */
            fgets(word, DIM_WORD, stdin);
            pword = strtok (word, "\n");
            listNumWords(paragHead, pword);
            break;
        case 'm':       /* Questão 1 - Trab2 */
            posicao = getNumber();
            nl = getNumber();
            if(posicao >= 0 && posicao < MAX){
                if(nl > 0){
                    rootTree = vet.VetL[posicao];
                    startPath(rootTree, nl);
                }
            }
            break;
        case 'r':
            fgets(word, DIM_WORD, stdin);
            pword = strtok (word, "\n");
            posicao = hash(pword) % MAX;
            rootTree = vet.VetL[posicao];
            noder = searchNodeTree(&rootTree, pword);
            deleteNodeTree(noder, &rootTree);
            if(rootTree == NULL)
                vet.VetL[posicao] = NULL;
            deleteNodeList(&alphaHeadF, &alphaHeadB, pword);
        }
    } while (*pcomand != 'e');
    return EXIT_SUCCESS;
}

int hash(char *s1) {
    int k, i = 0;
    char c = s1[i];
    int valor = 0;

    if (isalpha(c)) {
        while (c != '\0') {
            k = (((int) c) - 96);
            valor += k;
            i++;
            c = s1[i];
        }
    } else
        if (isalnum(c))
            valor = atoi(s1);
    return valor;
}

int getNumber(void) {
    char number[20];
    int valor;
    if (fgets(number, sizeof(number), stdin) != NULL) {
        char * newline = strchr(number, '\n'); /* search for newline character */
        if (newline != NULL) {
            *newline = '\0'; /* overwrite trailing newline */
        }
        if (sscanf(number, "%d", &valor) == 1) {
            return (valor);
        }
    }
}

ListAlpha * newNodeDLink(void) { /*create a node for a double linked list, only with NULL pointers*/
    ListAlpha * node;
    /*create a new node with two null pointers*/
    node = (ListAlpha *) malloc(sizeof(ListAlpha));
    if (node == NULL) { /*test if malloc was a sucess*/
        exit(EXIT_FAILURE);
    }
    node->pnextWord = NULL;
    node->pbackWord = NULL;

    return (node);
}

ParagList * newNodePgLink(void) { /*create a node with two null pointers,, one for a single list of lines fand other for a sigle list of paragraphs*/
    ParagList * node;
    /*create a new node with two null pointers*/
    node = (ParagList *) malloc(sizeof(ParagList));

    if (node == NULL) { /*test if malloc was a sucess*/
        exit (EXIT_FAILURE);
    }

    /*create a new node*/
    node->pnextParagraph = NULL;
    node->pnodeParagraph = NULL;

    return (node);
}

ListWord * newNodeTree(char *s) {
    ListWord * node;
    node = (ListWord *) malloc(sizeof(ListWord));

    if (node == NULL) { /*test if malloc was a sucess*/
        exit (EXIT_FAILURE);
    }

    /*create a new node*/
    node->pleftWord = NULL;
    node->prightWord = NULL;
    strcpy(node->word, s);

    return (node);
}

void startVet(VetList *vet) {
    int i;
    for (i = 0;i < MAX; i++)
        vet->VetL[i] = NULL; /*start vector positions with NULL pointer*/
}

void insertWordTree(ListWord **rootTree, char *s) {
    ListWord *rootT = *rootTree;
    if (rootT == NULL) {
        *rootTree = newNodeTree(s);
    } else {
        /*if (hash (s) <= hash(rootT->word)) {*/
        if(strcmp(s,rootT->word) <= 0) {
            if(strcmp(s,rootT->word) == 0)
                return;
            insertWordTree(&(rootT->pleftWord), s);
        } else
            /*if (hash(s) > hash (rootT->word))*/
            if(strcmp(s,rootT->word) > 0)
                insertWordTree(&((rootT)->prightWord), s);
    }

}

void insertAlpha(ListAlpha **alphaf, ListAlpha **alphab, char *s) { /*insert word in alphabetical double linked list*/
    ListAlpha *aux, *aux2, *node;
    aux = *alphaf;
    aux2 = NULL;

    node = newNodeDLink();
    strcpy(node->word, s);

    if (aux == NULL) { /*test if list is empty*/
        /*refresh head pointers*/
        *alphaf = node;
        *alphab = node;
        return ;
    }

    while ((aux != NULL) && (strcmp(node->word, aux->word) >= 0)) { /*cover the list even to find where put string*/
        if (strcmp(node->word, aux->word) == 0) {
            return ;
        }
        aux2 = aux;
        aux = aux->pnextWord;
    }

    if (aux == NULL) { /*end of list is find!*/
        node->pbackWord = aux2;
        aux2->pnextWord = node;
        *alphab = node;
        return ;
    }

    if (aux->pbackWord == NULL) { /*start of list is find!*/
        aux->pbackWord = node;
        node->pnextWord = aux;
        *alphaf = node; /*refresh head pointer in vector*/
        return ;
    }

    if (aux->pbackWord != NULL) { /*is in middle of list!*/
        aux->pbackWord->pnextWord = node;
        node->pbackWord = aux->pbackWord;
        node->pnextWord = aux;
        aux->pbackWord = node;
        return ;
    }
}

void insertParag(ParagList **parag, int number) { /*insert a new pagrapgh in list, enumerating*/
    ParagList * aux, *aux2, *node;
    aux = *parag;
    aux2 = NULL;

    node = newNodePgLink();
    node->paragraph = number;

    if (aux == NULL) { /*test if list is empty*/
        /*refresh head pointers*/
        *parag = node;
        return ;
    }

    while (aux != NULL) { /*cover the list even the end*/
        aux2 = aux;
        aux = aux->pnextParagraph;
    }

    if (aux == NULL) { /*end of list is find!*/
        aux2->pnextParagraph = node;
        return ;
    }
}

void insertLine(ParagList **parag, char *s, int nline) { /*insert a new line with content in one list inside each paragraph*/
    ListLine * aux, *aux2, *node;
    ParagList *auxp = *parag;
    aux2 = NULL;
    node = (ListLine *) malloc(sizeof(ListLine));

    if (node == NULL) { /*test if malloc was a sucess*/
        exit(EXIT_FAILURE);
    }

    while (auxp->pnextParagraph != NULL)        /*cover even the last paragraph*/
        auxp = auxp->pnextParagraph;

    aux = auxp->pnodeParagraph; /*start to move in lines list*/

    /*create a new node*/
    node->pnextLine = NULL;
    node->line = nline;
    strcpy(node->caracter, s);

    if (aux == NULL) { /*test if lines list is empty*/
        auxp->pnodeParagraph = node;
        return ;
    }

    while (aux != NULL) { /*cover in line list even to the end of*/
        aux2 = aux;
        aux = aux->pnextLine;
    }

    if (aux == NULL) { /*find end of lines list*/
        aux2->pnextLine = node;
        return ;
    }
}

ListWord ** searchNodeTree(ListWord **rootTree, char *s) {
    ListWord **rootT = rootTree;
    if (rootTree == NULL)
        return (NULL);

    while(rootT != NULL){
        int comp = strcmp(s, (*rootT)->word);
        if(comp < 0)
            rootT = &(*rootT)->pleftWord;
        else
            if(comp > 0)
                rootT = &(*rootT)->prightWord;
        else
            break;
    }
    return (rootT);
}

void searchPredNodeTree(ListWord *rootT, ListWord **rootTN){
    if(rootT->pleftWord != NULL){
        if((*rootTN)->prightWord != NULL){
            searchPredNodeTree(rootT, &(*rootTN)->prightWord);
            return;
        }
    }
    else{
        if(rootT->prightWord != NULL){
            if((*rootTN)->pleftWord != NULL){
                searchPredNodeTree(rootT, &(*rootTN)->pleftWord);
                return;
            }
        }
    }
    if(*rootTN != NULL)
        strcpy(rootT->word,(*rootTN)->word);
    rootT = *rootTN;
    if(*rootTN != NULL){
        if((*rootTN)->pleftWord != NULL)
            *rootTN = (*rootTN)->pleftWord;
        else if((*rootTN)->prightWord != NULL)
            *rootTN = (*rootTN)->prightWord;
        else
            *rootTN = NULL;
    }
    free(rootT);
}

void deleteNodeTree(ListWord **noder, ListWord **rootTree) {
    ListWord *old_noder = *noder;

    if(*noder == NULL)
        return;
    else{
        if(*rootTree == *noder)
            if(((*rootTree)->pleftWord == NULL) && ((*rootTree)->prightWord == NULL)){
                *rootTree = NULL;
                free(old_noder);
                return;
            }
        if((*noder)->pleftWord == NULL){
            if(rootTree == noder)
                searchPredNodeTree(*noder, &((*noder)->prightWord));
            else{
                *noder = (*noder)->prightWord;
                free(old_noder);
            }
        }
        else{
            if((*noder)->prightWord == NULL){
                if(rootTree == noder)
                    searchPredNodeTree(*noder, &((*noder)->pleftWord));
                else
                    *noder = (*noder)->pleftWord;
                free(old_noder);
            }
            else{
                if((*noder)->pleftWord != NULL)
                    searchPredNodeTree(*noder, &((*noder)->pleftWord));
                else
                    searchPredNodeTree(*noder, &((*noder)->prightWord));
            }
        }
    }
}

void deleteNodeList(ListAlpha **alphaf, ListAlpha **alphab, char *s){
    ListAlpha *aux;

    aux = *alphaf;
    while(( aux != NULL ) && (strcmp(s,aux->word) != 0)){
        aux = aux->pnextWord;
    }

    if(aux == NULL)
        return;
    else{
        if(*alphaf == *alphab){
            *alphaf = *alphab = NULL;
        }
        else if(aux->pbackWord == NULL)
            *alphaf = aux->pnextWord;
        else if(aux->pnextWord == NULL)
            *alphab = aux->pbackWord;
            else{
                aux->pbackWord->pnextWord = aux->pnextWord;
                aux->pnextWord->pbackWord = aux->pbackWord;
            }
    }
    free(aux);
}

void printTreeVet(ListWord *rootT) { /*print in-order a tree of words from specific vector position*/
    if (rootT == NULL)
        return ;
    printTreeVet(rootT->pleftWord);
    printf("%s ", rootT->word);
    printTreeVet(rootT->prightWord);
}

void printRange(ListAlpha *alphaF, ListAlpha *alphaB, char *ch, char *s1, char *s2) {
    ListAlpha * testeF = alphaF;
    ListAlpha *testeB = alphaB;

    if (*ch == 'c') { /*print range in crescent order*/
        while (testeF != NULL) { /*cover from first node even to last*/
            if ((strcmp(testeF->word, s1) >= 0) && (strcmp(testeF->word, s2) < 0))
                if (testeF->pnextWord != NULL) {
                    printf("%s\n", testeF->word);
                    if (testeF->pnextWord->pnextWord == NULL)
                        printf("%s\n", testeF->pnextWord->word);
                }
            testeF = testeF->pnextWord;
        }
    }
    if (*ch == 'd') { /*print range in decrescent order*/
        while (testeB != NULL) { /*cover from last node to first*/
            if ((strcmp(testeB->word, s1) < 0) && (strcmp(testeB->word, s2) > 0))
                if (testeB->pbackWord != NULL) {
                    if (strcmp(testeB->pbackWord->word, testeB->word) != 0)
                        printf("%s\n", testeB->word);
                    if (testeB->pbackWord->pbackWord == NULL)
                        printf("%s\n", testeB->pbackWord->word);
                }
            testeB = testeB->pbackWord;
        }
    }
}

void startPath(ListWord *rootT, int level) {
    char *path[level+1];
    int pathLevel = 0;

    listLevelTree(rootT, path, pathLevel, level);
}

void listLevelTree(ListWord *rootT, char *path[], int pathLevel, int level) {
    if(rootT == NULL)
        return;

    path[pathLevel] = rootT->word;
    if(pathLevel+1 == level)
        printf("%s\n", path[pathLevel]);
    pathLevel++;


    listLevelTree(rootT->pleftWord, path, pathLevel, level);
    listLevelTree(rootT->prightWord, path, pathLevel, level);
}

void listLines(ParagList *parag, char *s) {
    unsigned int i, j, k = 0;
    ParagList *testeP = parag;
    ListLine *testeL;

    while (testeP != NULL) {
        testeL = testeP->pnodeParagraph;
        while (testeL != NULL) {
            for (i = 0;i < (strlen(testeL->caracter));i++) {
                for (j = 0;j < (strlen(s));j++) {
                    if (s[j] == testeL->caracter[i + j]) {
                        k++;
                        if (k == (strlen(s)))
                            if ((ispunct(testeL->caracter[i + j + 1])) || (testeL->caracter[i + j + 1] == '\0') || (testeL->caracter[i + j + 1] == ' '))
                                if (!isalnum(testeL->caracter[i - 1]))
                                    printf("%d %d\n", testeP->paragraph, testeL->line);
                    } else
                        break;
                }
                k = 0;
            }
            testeL = testeL->pnextLine;
        }
        testeP = testeP->pnextParagraph;
    }
}

void listPosLines(ParagList *parag, char *s) {
    unsigned int i, j, k = 0;
    ParagList *testeP = parag;
    ListLine *testeL;

    while (testeP != NULL) {
        testeL = testeP->pnodeParagraph;
        while (testeL != NULL) {
            for (i = 0;i < (strlen(testeL->caracter));i++) {
                for (j = 0;j < (strlen(s));j++) {
                    if (s[j] == testeL->caracter[i + j]) {
                        k++;
                        if (k == (strlen(s)))
                            if ((ispunct(testeL->caracter[i + j + 1])) || (testeL->caracter[i + j + 1] == '\0') || (testeL->caracter[i + j + 1] == ' '))
                                if (!isalnum(testeL->caracter[i - 1]))
                                    printf("%d %d %d\n", testeP->paragraph, testeL->line, i + 1);
                    } else
                        break;
                }
                k = 0;
            }
            testeL = testeL->pnextLine;
        }
        testeP = testeP->pnextParagraph;
    }
}

void lineParag(ParagList *parag, int np, int nl) {
    ParagList * testeP = parag;
    ListLine *testeL;

    while (testeP != NULL) {
        if (testeP->paragraph == np) {
            testeL = testeP->pnodeParagraph;
            while (testeL != NULL) {
                if (testeL->line == nl)
                    printf("%s\n", testeL->caracter);
                testeL = testeL->pnextLine;
            }
        }
        testeP = testeP->pnextParagraph;
    }
}

void listLinesPos(ParagList *parag, int nl, int np, int pos) {
    int i;
    ParagList *testeP = parag;
    ListLine *testeL;

    while (testeP != NULL) {
        testeL = testeP->pnodeParagraph;
        if (testeP->paragraph == np) {
            for (i = 1; i < nl;i++) {
                if (testeL != NULL)
                    testeL = testeL->pnextLine;
                else
                    exit (0);
            }
            pos--;
            do {
                printf("%c", testeL->caracter[pos]);
                pos++;
            } while (testeL->caracter[pos] != '\0');
            printf("\n");
            break;
        }
        testeP = testeP->pnextParagraph;
    }
}

void listNumWords(ParagList *parag, char *s) {
    unsigned int i, j, k = 0;
    int value = 0;
    ParagList *testeP = parag;
    ListLine *testeL;

    while (testeP != NULL) {
        testeL = testeP->pnodeParagraph;
        while (testeL != NULL) {
            for (i = 0;i < (strlen(testeL->caracter));i++) {
                for (j = 0;j < (strlen(s));j++) {
                    if (s[j] == testeL->caracter[i + j]) {
                        k++;
                        if (k == (strlen(s)))
                            if ((ispunct(testeL->caracter[i + j + 1])) || (testeL->caracter[i + j + 1] == '\0') || (testeL->caracter[i + j + 1] == ' '))
                                if (!isalnum(testeL->caracter[i - 1]))
                                    value++;
                    } else
                        break;
                }
                k = 0;
            }
            testeL = testeL->pnextLine;
        }
        testeP = testeP->pnextParagraph;
    }
    printf("%d\n", value);
}