/* Before compiling this program, un-comment JUST ONE of the following
   macro definitions, depending on your C compiler.  If you do not
   have one of the compilers mentioned, un-comment the PLAINTEXT line. */

/* #define MICROSOFT 1  */
/* #define TOPSPEED 1 */
/* #define POWERC 1    */
/* #define BORLAND 1 */
/* #define PLAINTEXT 1 */

/**** The following lines set up screen limits.  Except for PLAINTEXT,
which assumes an 80*24 screen, the others assume an EGA 640*350 screen.
When testing this program, ensure your data points range fit within
0 <= x < XMAX and 0 <= y < YMAX.  */

#ifdef PLAINTEXT
    #define XMAX 79
    #define YMAX 24
#else
    #define SCRN_MODE 16
    #define XMAX 640
    #define YMAX 350
#endif

/********************************************************/

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

typedef struct {
    int x, y;     /* x,y co-ordinates, top left == 0,0 */
} point;

typedef struct vertex {
    point p;
    struct vertex * next;
} vertex;

typedef struct {
    vertex *phead, *ptail;
} point_list;

#define EMPTY_LIST {NULL, NULL}

/****** add_node ******
 Adds a node to a point_list.
 On entry: plist points to a point_list.
           where points to a node in that list, or is NULL.
           pt is a point to be stored in the new node.
           NB: None of these requirements are checked!
 On exit: EITHER: A new node, containing a copy of pt, is added to plist's
            list after node where.  (If where is NULL, the new node
            is at the front.)  The function returns 0. (normal return)
          OR: plist's list is unaltered, add_node returns 1. (error return)
*/
int add_node(point_list *plist, vertex *where, point pt) {
    vertex *newnode;
    /* Try to obtain space for the new node. */
    newnode = (vertex*)malloc(sizeof(vertex));
    if (newnode == NULL) {            /* Allocation failed - Return 1. */
        return 1;
    }
    newnode->p = pt;                  /* Fill the new node with data */
    if (where == NULL) {              /* Adding at head of list? */
        /* Add the new node at the start */
        newnode->next = plist->phead; /* Previous 1st entry is now 2nd */
        plist->phead = newnode;       /* new entry is first */
    } else {                          /* Add the new node after where */
        newnode->next = where->next;  /* new node points to node that was
                                         previously straight after where */
        where->next = newnode;        /* where->next points to new node */
    }
    if (newnode->next == NULL) {      /* Was the node added at the end? */
        plist->ptail = newnode;       /* If so, it becomes the tail node */
    }
    return 0;
}

/****** find_pt ******
 Locates the which'th vertex in a list.
 On entry: plist points to a point_list, which is the index of the node to
           locate (0=before first, 1=first, etc.).
 On exit:  Returns pointer to vertex, or NULL if which<=0 or > no. vertices
*/
vertex *find_pt(point_list *plist, int which) {
    vertex * pnode;                /* To be used to advance through list */
    if (which <= 0) {
        return NULL;
    }
    pnode = plist->phead;          /* Pointer to first node */
    which--;                       /* which now == no. of nodes to skip. */
    /* Loop, decrementing which, until which==0 or we fall off the end */
    while (pnode != NULL && which > 0) {
        pnode = pnode->next;       /* Skip one node */
        which--;                   /* One fewer left to skip */
    }
    return pnode;
}

/****** del_pt ******
 Disconnects a node from the list, and destroys it.
 On entry: plist points to a list, which points to a node in the list, or
           is NULL to indicate the list head.
 On exit:  The node AFTER the node indicated by which is deleted.
           If there is no such following node, nothing happens.
*/
void del_pt(point_list *plist, vertex *which) {
    vertex * next_node;
    if (which == NULL) {           /* Disconnect the very first node */
        next_node = plist->phead;
        if (next_node != NULL) {   /* There is a node there to delete */
            plist->phead = next_node->next;  /* Yes, disconnect it */
            if (next_node == plist->ptail) { /* Deleting the final node? */
                plist->ptail = NULL;         /* yes, list empty-alter ptail*/
            }
            free(next_node);                 /* Reclaim space */
        }
    } else {                   /* Disconnect a subsequent node */
        next_node = which->next;
        if (next_node != NULL) {   /* There is a node there to delete */
            which->next = next_node->next;   /* Yes, disconnect it */
            if (next_node == plist->ptail) { /* Deleting the final node? */
                plist->ptail = which;        /* yes - set ptail to new tail*/
            }
            free(next_node);                 /* Reclaim space */
        }
    }
}

/*************************************************************/

point_list input_points(void);
void display_shape(point_list);
void display_menu(void);
char user_choice(void);
void add_point(point_list *ppoly);
void delete_point(point_list *ppoly);
void move_point(point_list polygon);
void output(point_list polygon);

main() {
    point_list polygon;         /* The list of points in the polygon */
    char choice;
    #ifdef BORLAND
        void setupborland(void);
        setupborland();
    #endif
    polygon = input_points();
    do {
        display_shape(polygon);
        display_menu();         /* choices (add, delete, move or quit) */
        choice = user_choice();
        if (choice != 'q') {
            switch (choice) {
                case 'a': add_point(&polygon); break;
                case 'd': delete_point(&polygon); break;
                case 'm': move_point(polygon); break;
            }
        }
    } while (choice != 'q');
    output(polygon);
    return 0;
}

void display_menu(void) {
    printf(
        "\n\n\tOptions:\n\n"
        "A  Add a point to the polygon\n"
        "D  Delete a point from the polygon\n"
        "M  Move a point in the polygon (alter its position on screen)\n"
        "Q  Quit.\n\nEnter choice (A, D, M or Q):"
    );
}

#include <ctype.h>      /* For function tolower() */
#include <string.h>

char user_choice(void) {
    /* Inputs user's menu choice.  Insists on a correct answer. */
    char choice;
    /* Input the choice, and discard the rest of the input line: */
    scanf("%c%*[^\n]", &choice);getchar();
    choice = tolower(choice);     /* Convert to lower case letter */

    while (strchr("admq", choice) == NULL) { /* while choice not in the
                                                  allowed options */
        printf("You must answer one of A, D, M or Q:");
        /* Input the choice, and discard the rest of the input line: */
        scanf("%c%*[^\n]", &choice);getchar();
        choice = tolower(choice);     /* Convert to lower case letter */
    }
    return choice;
}

void add_point(point_list *ppoly) {
    /* Adds a point to the polygon at location entered by user */
    int where;  point pt;  vertex *v;
    printf("After which point in the polygon should the point be added?\n");
    printf("(0=before 1st point, 1= after 1st, 2=after 2nd, etc.)? ");
    scanf("%d", &where);
    printf("Enter x,y co-ordinates of point (0,0 = top left): ");
    scanf("%d %d%*[^\n]", &pt.x, &pt.y); getchar();
    v = find_pt(ppoly, where);
    if (add_node(ppoly, v, pt)) {       /* failure */
        fprintf(stderr, "ERROR: space for list exhausted - hit Enter\n");
        getchar();
    }

}

void delete_point(point_list *ppoly) {
    /* Deletes the point nominated by the user */
    int where;  vertex *v;
    printf("Which point in the polygon should be deleted?\n");
    printf("(1= 1st, 2=2nd, etc.)? ");
    scanf("%d%*[^\n]", &where);getchar();
    if (where < 1) {
        return;
    }
    v = find_pt(ppoly, where-1);  /* The point BEFORE the one to delete */
    if (where != 1 && v == NULL) {
        return;         /* Off the end of the list - nothing to delete */
    }
    del_pt(ppoly, v);
}

void move_point(point_list polygon) {
    /* Relocates the co-ordinates of a point nominated by user */
    int where;  point pt;  vertex *v;
    printf("Which point in the polygon should be relocated?\n");
    printf("(1= 1st, 2=2nd, etc.)? ");
    scanf("%d", &where);
    v = find_pt(&polygon, where);
    if (v == NULL ) {
        return;         /* No such point */
    }
    printf(
        "Point is currently at %d,%d\n Enter new co-ordinates: ",
        v->p.x, v->p.y
    );
    scanf("%d %d%*[^\n]", &pt.x, &pt.y); getchar();
    v->p = pt;
}

point_list input_points(void) {
    /* Inputs a list of x,y pairs representing a polygon from a file */
    char fname[81];  FILE * f;  int status;
    point_list poly = EMPTY_LIST;  point pt;
    do {
        printf("Input file: ");
        scanf("%s%*[^\n]", fname);getchar();
        f = fopen(fname, "r");
    } while (f==NULL);
    while (fscanf(f,"%d %d", &pt.x, &pt.y) == 2) {  /* 2 items read */
        /* Add the new item after the existing last node in the list */
        status = add_node(&poly, poly.ptail, pt);
        if (status) {    /* error allocating list node */
            fprintf(stderr, "ERROR: space for list exhausted\n");
            exit(EXIT_FAILURE);
        }
    }
    fclose(f);
    return poly;
}

void output(point_list poly) {
    /* Outputs a list of x,y pairs representing a polygon to a file */
    char fname[81];  FILE * f;
    vertex *vp;
    do {
        printf("Output file: ");
        scanf("%s%*[^\n]", fname);getchar();
        f = fopen(fname, "w");
    } while (f==NULL);

    /* Now traverse the list from head to tail, printing each node's
       point in turn. */
    vp = poly.phead;
    while (vp != NULL) {
        /* Print the point at the current node in the list */
        if (fprintf(f, "%d %d\n", vp->p.x, vp->p.y) < 0) {  /* error */
            fprintf(stderr, "ERROR writing file\n");
            fclose(f);
            exit(EXIT_FAILURE);
        }
        vp = vp->next;
    }
    fclose(f);
}

/********* display_shape **********
 This function displays the polygon pictorially, and then asks the user
 to hit Enter to proceed with the program.  It will compile under the
 following C compilers:
 MicroSoft
 TopSpeed
 Power C
 Borland
 "Vanilla" ANSI C with a text screen
 ******************************/

/* Version for Microsoft C/C++ or Quick C, or TopSpeed C: */

#if defined(TOPSPEED) || defined(MICROSOFT)
#include <graph.h>
void display_shape(point_list poly) {
    vertex * vp;
    if (poly.phead == poly.ptail) {  /* either empty or just one point */
        printf("No lines to display.\n");
        return;
    }
    if (_setvideomode(SCRN_MODE)==0) {
        printf("Failed to select video mode.  Try PLAINTEXT mode.\n");
        exit(EXIT_FAILURE);
    }
    _setbkcolor(_BLACK);
    _setcolor(_WHITE);
    _clearscreen(_GCLEARSCREEN);
    _moveto(poly.phead->p.x, poly.phead->p.y);  /* Get to first point */
    vp = poly.phead->next;
    while (vp != NULL) {
		_lineto(vp->p.x, vp->p.y);              /* Line to next point */
        vp = vp->next;
    }
    _setcolor(_GRAY);
    _lineto(poly.phead->p.x, poly.phead->p.y);  /* Line to close polygon */
    _settextposition(25,1);
    _outtext("Hit Enter to continue");
    getchar();               /* Wait for user to press return */
    _setvideomode(_DEFAULTMODE);
}
#endif

/********** Version for Power C *******************/

#ifdef POWERC
#include <graphics.h>
void display_shape(point_list poly) {
    vertex * vp;
    if (poly.phead == poly.ptail) {  /* either empty or just one point */
        printf("No lines to display.\n");
        return;
    }
    if (setvmode(SCRN_MODE)==DEFAULTMODE) {
        printf("Failed to select video mode.  Try PLAINTEXT mode.\n");
        exit(EXIT_FAILURE);
    }
    pen_color(15);
    move_to(poly.phead->p.x, poly.phead->p.y);  /* Get to first point */
    vp = poly.phead->next;
    while (vp != NULL) {
        line_to(vp->p.x, vp->p.y);              /* Line to next point */
        vp = vp->next;
	}
    pen_color(7);
    line_to(poly.phead->p.x, poly.phead->p.y);  /* Line to close polygon */
    move_to(0, YMAX-8);
    plots("Hit Enter to continue");
    getchar();               /* Wait for user to press return */
    setvmode(DEFAULTMODE);
}
#endif

/********** Version for Borland C *******************/

#if defined(BORLAND)
#include <graphics.h>
void setupborland(void) {
    int gdriver = EGA, gmode = EGAHI, err;
        /* The following line should contain the correct directory for
           your ".BGI" graphic drivers. */
	initgraph(&gdriver, &gmode, "c:\\borlandc\\bgi");
    err = graphresult();
    if (err != grOk) {
		printf("Cannot select graphics (err %d). Try PLAINTEXT mode.\n", err);
        exit(EXIT_FAILURE);
    }
}

void display_shape(point_list poly) {
    vertex * vp;
    if (poly.phead == poly.ptail) {  /* either empty or just one point */
        printf("No lines to display.\n");
        return;
    }
    setgraphmode(getgraphmode());
    moveto(poly.phead->p.x, poly.phead->p.y);  /* Get to first point */
    vp = poly.phead->next;
    while (vp != NULL) {
        lineto(vp->p.x, vp->p.y);              /* Line to next point */
        vp = vp->next;
    }
    lineto(poly.phead->p.x, poly.phead->p.y);  /* Line to close polygon */
    outtextxy(0, YMAX-15, "Hit Enter to continue");
    getchar();               /* Wait for user to press return */
    restorecrtmode();
}
#endif

/********** Version for "Vanilla" C *******************/

#ifdef PLAINTEXT
/* This option 'fakes' the graphics using stars on the text screen */
int X=0, Y=0;
char screen[YMAX][XMAX+1];

void clearscrn(void) {
    int i,j;
    for (i=0; i<YMAX; i++) {
        for (j=0; j<XMAX; j++) {
            screen[i][j] = ' ';
        }
        screen[i][XMAX] = '\0';
    }
}

void move_to(int x, int y) {
    X=x;Y=y;
}

void line_to(int x, int y) {
    /* Advance a column or row at a time, finding the best place for the
       asterisk.  'Clip' to screen array limits. */
    int i, j; float startx, starty, finx, finy;
    if (abs(x-X) > abs(y-Y)) {
        /* Line closer to horizontal, advance by columns. */
        if (x > X) {
            startx = X; finx = x;
            starty = Y; finy = y;
        } else {
            startx = x; finx = X;
            starty = y; finy = Y;
        }
        for (i=startx; i<=finx; i++) {
            j = (int)(starty + (finy-starty)*(i-startx)/(finx-startx) + 0.5);
            if (i>=0 && i<XMAX && j>=0 && j<YMAX) { /* On screen? */
                screen[j][i] = '*';
            }
        }
    } else {
        /* Line closer to vertical, advance by rows. */
        if (y > Y) {
            startx = X; finx = x;
            starty = Y; finy = y;
        } else {
            startx = x; finx = X;
            starty = y; finy = Y;
        }
        for (i=starty; i<=finy; i++) {
            j = (int)(startx + (finx-startx)*(i-starty)/(finy-starty) + 0.5);
            if (j>=0 && j<XMAX && i>=0 && i<YMAX) { /* On screen? */
                screen[i][j] = '*';
            }
        }
    }
    move_to(x,y);
}

void display_shape(point_list poly) {
    vertex * vp; int i;
    if (poly.phead == poly.ptail) {  /* either empty or just one point */
        printf("No lines to display.\n");
        return;
    }
    clearscrn();
    move_to(poly.phead->p.x, poly.phead->p.y);  /* Get to first point */
    vp = poly.phead->next;
    while (vp != NULL) {
        line_to(vp->p.x, vp->p.y);              /* Line to next point */
        vp = vp->next;
    }
    line_to(poly.phead->p.x, poly.phead->p.y);  /* Line to close polygon */
    for (i=0; i<YMAX; i++) {
        printf("%*.*s\n", XMAX, XMAX, screen[i]);
    }
    printf("Hit Enter to continue");
    getchar();               /* Wait for user to press return */
    printf("\n\n\n");
}
#endif